From 9405ae704beaf2e47121e41f3042e819d8db507a Mon Sep 17 00:00:00 2001 From: Diana Picus Date: Thu, 18 Aug 2016 11:17:53 +0000 Subject: [PATCH] Revert "ADT: Remove UB in ilist (and use a circular linked list)" This reverts commit r278974 which broke some of our bots (e.g. clang-cmake-aarch64-42vma, clang-cmake-aarch64-full). llvm-svn: 279053 --- llvm/include/llvm/ADT/ilist.h | 379 +++++++++++++++++++++++++------------ llvm/include/llvm/ADT/ilist_node.h | 89 +++------ llvm/unittests/ADT/ilistTest.cpp | 62 ------ 3 files changed, 287 insertions(+), 243 deletions(-) diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h index 10ff088..3723039 100644 --- a/llvm/include/llvm/ADT/ilist.h +++ b/llvm/include/llvm/ADT/ilist.h @@ -15,16 +15,17 @@ // replacement does not provide a constant time size() method, so be careful to // use empty() when you really want to know if it's empty. // -// The ilist class is implemented as a circular list. The list itself contains -// a sentinel node, whose Next points at begin() and whose Prev points at -// rbegin(). The sentinel node itself serves as end() and rend(). +// The ilist class is implemented by allocating a 'tail' node when the list is +// created (using ilist_traits<>::createSentinel()). This tail node is +// absolutely required because the user must be able to compute end()-1. Because +// of this, users of the direct next/prev links will see an extra link on the +// end of the list, which should be ignored. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_ILIST_H #define LLVM_ADT_ILIST_H -#include "llvm/ADT/ilist_node.h" #include "llvm/Support/Compiler.h" #include #include @@ -37,42 +38,37 @@ namespace llvm { template class iplist; template class ilist_iterator; -/// An access class for ilist_node private API. +/// An access class for next/prev on ilist_nodes. /// /// This gives access to the private parts of ilist nodes. Nodes for an ilist /// should friend this class if they inherit privately from ilist_node. /// -/// It's strongly discouraged to *use* this class outside of the ilist +/// It's strongly discouraged to *use* this class outside of ilist /// implementation. struct ilist_node_access { - template static ilist_node *getNodePtr(T *N) { return N; } - template static const ilist_node *getNodePtr(const T *N) { - return N; - } - - template static ilist_node *getPrev(ilist_node *N) { + template static NodeTy *getPrev(NodeTy *N) { return N->getPrev(); } - template static ilist_node *getNext(ilist_node *N) { + template static NodeTy *getNext(NodeTy *N) { return N->getNext(); } - template static const ilist_node *getPrev(const ilist_node *N) { + template static const NodeTy *getPrev(const NodeTy *N) { return N->getPrev(); } - template static const ilist_node *getNext(const ilist_node *N) { + template static const NodeTy *getNext(const NodeTy *N) { return N->getNext(); } - template static void setPrev(ilist_node *N, ilist_node *Prev) { + template static void setPrev(NodeTy *N, NodeTy *Prev) { N->setPrev(Prev); } - template static void setNext(ilist_node *N, ilist_node *Next) { + template static void setNext(NodeTy *N, NodeTy *Next) { N->setNext(Next); } - template static void setPrev(ilist_node *N, std::nullptr_t) { + template static void setPrev(NodeTy *N, std::nullptr_t) { N->setPrev(nullptr); } - template static void setNext(ilist_node *N, std::nullptr_t) { + template static void setNext(NodeTy *N, std::nullptr_t) { N->setNext(nullptr); } }; @@ -97,31 +93,111 @@ template struct HasGetNext { static const bool value = sizeof(hasGetNext(nullptr)) == sizeof(Yes); }; -/// Type trait to check for a traits class that has a createSentinel member (as -/// a canary for any of the ilist_sentinel_traits API). -template struct HasCreateSentinel { - typedef char Yes[1]; - typedef char No[2]; - template struct SFINAE {}; +} // end namespace ilist_detail - template - static Yes & - hasCreateSentinel(SFINAE().createSentinel())> * = 0); - template static No &hasCreateSentinel(...); +template +struct ilist_traits; + +/// ilist_sentinel_traits - A fragment for template traits for intrusive list +/// that provides default sentinel implementations for common operations. +/// +/// ilist_sentinel_traits implements a lazy dynamic sentinel allocation +/// strategy. The sentinel is stored in the prev field of ilist's Head. +/// +template +struct ilist_sentinel_traits { + /// createSentinel - create the dynamic sentinel + static NodeTy *createSentinel() { return new NodeTy(); } + + /// destroySentinel - deallocate the dynamic sentinel + static void destroySentinel(NodeTy *N) { delete N; } + + /// provideInitialHead - when constructing an ilist, provide a starting + /// value for its Head + /// @return null node to indicate that it needs to be allocated later + static NodeTy *provideInitialHead() { return nullptr; } + + /// ensureHead - make sure that Head is either already + /// initialized or assigned a fresh sentinel + /// @return the sentinel + static NodeTy *ensureHead(NodeTy *&Head) { + if (!Head) { + Head = ilist_traits::createSentinel(); + ilist_traits::noteHead(Head, Head); + ilist_node_access::setNext(Head, nullptr); + return Head; + } + return ilist_node_access::getPrev(Head); + } - static const bool value = - sizeof(hasCreateSentinel(nullptr)) == sizeof(Yes); + /// noteHead - stash the sentinel into its default location + static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { + ilist_node_access::setPrev(NewHead, Sentinel); + } }; -} // end namespace ilist_detail +template class ilist_half_node; +template class ilist_node; + +/// Traits with an embedded ilist_node as a sentinel. +template struct ilist_embedded_sentinel_traits { + /// Get hold of the node that marks the end of the list. + /// + /// FIXME: This downcast is UB. See llvm.org/PR26753. + LLVM_NO_SANITIZE("object-size") + NodeTy *createSentinel() const { + // Since i(p)lists always publicly derive from their corresponding traits, + // placing a data member in this class will augment the i(p)list. But since + // the NodeTy is expected to be publicly derive from ilist_node, + // there is a legal viable downcast from it to NodeTy. We use this trick to + // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the + // sentinel. Dereferencing the sentinel is forbidden (save the + // ilist_node), so no one will ever notice the superposition. + return static_cast(&Sentinel); + } + static void destroySentinel(NodeTy *) {} + + NodeTy *provideInitialHead() const { return createSentinel(); } + NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } + static void noteHead(NodeTy *, NodeTy *) {} + +private: + mutable ilist_node Sentinel; +}; + +/// Trait with an embedded ilist_half_node as a sentinel. +template struct ilist_half_embedded_sentinel_traits { + /// Get hold of the node that marks the end of the list. + /// + /// FIXME: This downcast is UB. See llvm.org/PR26753. + LLVM_NO_SANITIZE("object-size") + NodeTy *createSentinel() const { + // See comment in ilist_embedded_sentinel_traits::createSentinel(). + return static_cast(&Sentinel); + } + static void destroySentinel(NodeTy *) {} + + NodeTy *provideInitialHead() const { return createSentinel(); } + NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } + static void noteHead(NodeTy *, NodeTy *) {} + +private: + mutable ilist_half_node Sentinel; +}; + +/// Traits with an embedded full node as a sentinel. +template struct ilist_full_embedded_sentinel_traits { + /// Get hold of the node that marks the end of the list. + NodeTy *createSentinel() const { return &Sentinel; } + static void destroySentinel(NodeTy *) {} -template struct ilist_traits; + NodeTy *provideInitialHead() const { return createSentinel(); } + NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } + static void noteHead(NodeTy *, NodeTy *) {} -// TODO: Delete uses from subprojects, then delete these. -template struct ilist_sentinel_traits {}; -template struct ilist_embedded_sentinel_traits {}; -template struct ilist_half_embedded_sentinel_traits {}; -template struct ilist_full_embedded_sentinel_traits {}; +private: + mutable NodeTy Sentinel; +}; /// ilist_node_traits - A fragment for template traits for intrusive list /// that provides default node related operations. @@ -143,7 +219,8 @@ struct ilist_node_traits { /// for all common operations. /// template -struct ilist_default_traits : public ilist_node_traits {}; +struct ilist_default_traits : public ilist_sentinel_traits, + public ilist_node_traits {}; // Template traits for intrusive list. By specializing this template class, you // can change what next/prev fields are used to store the links... @@ -186,15 +263,16 @@ public: typedef node_type &node_reference; private: - node_pointer NodePtr = nullptr; + pointer NodePtr; public: /// Create from an ilist_node. - explicit ilist_iterator(node_reference N) : NodePtr(&N) {} + explicit ilist_iterator(node_reference N) + : NodePtr(static_cast(&N)) {} explicit ilist_iterator(pointer NP) : NodePtr(NP) {} explicit ilist_iterator(reference NR) : NodePtr(&NR) {} - ilist_iterator() = default; + ilist_iterator() : NodePtr(nullptr) {} // This is templated so that we can allow constructing a const iterator from // a nonconst iterator... @@ -203,23 +281,20 @@ public: const ilist_iterator &RHS, typename std::enable_if::value, void *>::type = nullptr) - : NodePtr(RHS.getNodePtr()) {} + : NodePtr(RHS.getNodePtrUnchecked()) {} // This is templated so that we can allow assigning to a const iterator from // a nonconst iterator... template const ilist_iterator &operator=(const ilist_iterator &RHS) { - NodePtr = RHS.getNodePtr(); + NodePtr = RHS.getNodePtrUnchecked(); return *this; } void reset(pointer NP) { NodePtr = NP; } // Accessors... - reference operator*() const { - assert(!NodePtr->isKnownSentinel()); - return static_cast(*getNodePtr()); - } + reference operator*() const { return *NodePtr; } pointer operator->() const { return &operator*(); } // Comparison operators @@ -253,6 +328,9 @@ public: /// Get the underlying ilist_node. node_pointer getNodePtr() const { return static_cast(NodePtr); } + + // Internal interface, do not use... + pointer getNodePtrUnchecked() const { return NodePtr; } }; // Allow ilist_iterators to convert into pointers to a node automatically when @@ -278,33 +356,56 @@ template struct simplify_type > { //===----------------------------------------------------------------------===// // -/// The subset of list functionality that can safely be used on nodes of -/// polymorphic types, i.e. a heterogeneous list with a common base class that -/// holds the next/prev pointers. The only state of the list itself is an -/// ilist_sentinel, which holds pointers to the first and last nodes in the -/// list. +/// iplist - The subset of list functionality that can safely be used on nodes +/// of polymorphic types, i.e. a heterogeneous list with a common base class that +/// holds the next/prev pointers. The only state of the list itself is a single +/// pointer to the head of the list. +/// +/// This list can be in one of three interesting states: +/// 1. The list may be completely unconstructed. In this case, the head +/// pointer is null. When in this form, any query for an iterator (e.g. +/// begin() or end()) causes the list to transparently change to state #2. +/// 2. The list may be empty, but contain a sentinel for the end iterator. This +/// sentinel is created by the Traits::createSentinel method and is a link +/// in the list. When the list is empty, the pointer in the iplist points +/// to the sentinel. Once the sentinel is constructed, it +/// is not destroyed until the list is. +/// 3. The list may contain actual objects in it, which are stored as a doubly +/// linked list of nodes. One invariant of the list is that the predecessor +/// of the first node in the list always points to the last node in the list, +/// and the successor pointer for the sentinel (which always stays at the +/// end of the list) is always null. +/// template > class iplist : public Traits, ilist_node_access { - // TODO: Drop these assertions anytime after 4.0 is branched (keep them for - // one release to help out-of-tree code update). #if !defined(_MSC_VER) // FIXME: This fails in MSVC, but it's worth keeping around to help // non-Windows users root out bugs in their ilist_traits. static_assert(!ilist_detail::HasGetNext::value, "ilist next and prev links are not customizable!"); - static_assert(!ilist_detail::HasCreateSentinel::value, - "ilist sentinel is not customizable!"); #endif - ilist_sentinel Sentinel; + mutable NodeTy *Head; + + // Use the prev node pointer of 'head' as the tail pointer. This is really a + // circularly linked list where we snip the 'next' link from the sentinel node + // back to the first node in the list (to preserve assertions about going off + // the end of the list). + NodeTy *getTail() { return this->ensureHead(Head); } + const NodeTy *getTail() const { return this->ensureHead(Head); } + void setTail(NodeTy *N) const { this->noteHead(Head, N); } - typedef ilist_node node_type; - typedef const ilist_node const_node_type; + /// CreateLazySentinel - This method verifies whether the sentinel for the + /// list has been created and lazily makes it if not. + void CreateLazySentinel() const { + this->ensureHead(Head); + } static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } - // Copying intrusively linked nodes doesn't make sense. + // No fundamental reason why iplist can't be copyable, but the default + // copy/copy-assign won't do. iplist(const iplist &) = delete; void operator=(const iplist &) = delete; @@ -321,14 +422,30 @@ public: typedef std::reverse_iterator const_reverse_iterator; typedef std::reverse_iterator reverse_iterator; - iplist() = default; - ~iplist() { clear(); } + iplist() : Head(this->provideInitialHead()) {} + ~iplist() { + if (!Head) return; + clear(); + Traits::destroySentinel(getTail()); + } // Iterator creation methods. - iterator begin() { return ++iterator(Sentinel); } - const_iterator begin() const { return ++const_iterator(Sentinel); } - iterator end() { return iterator(Sentinel); } - const_iterator end() const { return const_iterator(Sentinel); } + iterator begin() { + CreateLazySentinel(); + return iterator(Head); + } + const_iterator begin() const { + CreateLazySentinel(); + return const_iterator(Head); + } + iterator end() { + CreateLazySentinel(); + return iterator(getTail()); + } + const_iterator end() const { + CreateLazySentinel(); + return const_iterator(getTail()); + } // reverse iterator creation methods. reverse_iterator rbegin() { return reverse_iterator(end()); } @@ -339,39 +456,44 @@ public: // Miscellaneous inspection routines. size_type max_size() const { return size_type(-1); } - bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); } + bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { + return !Head || Head == getTail(); + } // Front and back accessor functions... reference front() { assert(!empty() && "Called front() on empty list!"); - return *begin(); + return *Head; } const_reference front() const { assert(!empty() && "Called front() on empty list!"); - return *begin(); + return *Head; } reference back() { assert(!empty() && "Called back() on empty list!"); - return *--end(); + return *this->getPrev(getTail()); } const_reference back() const { assert(!empty() && "Called back() on empty list!"); - return *--end(); + return *this->getPrev(getTail()); } void swap(iplist &RHS) { assert(0 && "Swap does not use list traits callback correctly yet!"); - std::swap(Sentinel, RHS.Sentinel); + std::swap(Head, RHS.Head); } iterator insert(iterator where, NodeTy *New) { - node_type *NewN = this->getNodePtr(New); - node_type *Next = where.getNodePtr(); - node_type *Prev = this->getPrev(Next); - this->setNext(NewN, Next); - this->setPrev(NewN, Prev); - this->setNext(Prev, NewN); - this->setPrev(Next, NewN); + NodeTy *CurNode = where.getNodePtrUnchecked(); + NodeTy *PrevNode = this->getPrev(CurNode); + this->setNext(New, CurNode); + this->setPrev(New, PrevNode); + + if (CurNode != Head) // Is PrevNode off the beginning of the list? + this->setNext(PrevNode, New); + else + Head = New; + this->setPrev(CurNode, New); this->addNodeToList(New); // Notify traits that we added a node... return iterator(New); @@ -391,23 +513,24 @@ public: NodeTy *remove(iterator &IT) { assert(IT != end() && "Cannot remove end of list!"); NodeTy *Node = &*IT; - node_type *Base = this->getNodePtr(Node); - node_type *Next = this->getNext(Base); - node_type *Prev = this->getPrev(Base); + NodeTy *NextNode = this->getNext(Node); + NodeTy *PrevNode = this->getPrev(Node); - this->setNext(Prev, Next); - this->setPrev(Next, Prev); - IT = iterator(*Next); + if (Node != Head) // Is PrevNode off the beginning of the list? + this->setNext(PrevNode, NextNode); + else + Head = NextNode; + this->setPrev(NextNode, PrevNode); + IT.reset(NextNode); this->removeNodeFromList(Node); // Notify traits that we removed a node... // Set the next/prev pointers of the current node to null. This isn't // strictly required, but this catches errors where a node is removed from // an ilist (and potentially deleted) with iterators still pointing at it. - // After those iterators are incremented or decremented, they become - // default-constructed iterators, and will assert on increment, decrement, - // and dereference instead of "usually working". - this->setNext(Base, nullptr); - this->setPrev(Base, nullptr); + // When those iterators are incremented or decremented, they will assert on + // the null next/prev pointer instead of "usually working". + this->setNext(Node, nullptr); + this->setPrev(Node, nullptr); return Node; } @@ -433,7 +556,12 @@ public: /// /// This should only be used immediately before freeing nodes in bulk to /// avoid traversing the list and bringing all the nodes into cache. - void clearAndLeakNodesUnsafely() { Sentinel.reset(); } + void clearAndLeakNodesUnsafely() { + if (Head) { + Head = getTail(); + this->setPrev(Head, Head); + } + } private: // transfer - The heart of the splice function. Move linked list nodes from @@ -442,34 +570,48 @@ private: void transfer(iterator position, iplist &L2, iterator first, iterator last) { assert(first != last && "Should be checked by callers"); // Position cannot be contained in the range to be transferred. + // Check for the most common mistake. assert(position != first && - // Check for the most common mistake. "Insertion point can't be one of the transferred nodes"); - if (position == last) - return; - - // Get raw hooks to the first and final nodes being transferred. - node_type *First = first.getNodePtr(); - node_type *Final = (--last).getNodePtr(); - - // Detach from old list/position. - node_type *Prev = this->getPrev(First); - node_type *Next = this->getNext(Final); - this->setNext(Prev, Next); - this->setPrev(Next, Prev); - - // Splice [First, Final] into its new list/position. - Next = position.getNodePtr(); - Prev = this->getPrev(Next); - this->setNext(Final, Next); - this->setPrev(First, Prev); - this->setNext(Prev, First); - this->setPrev(Next, Final); - - // Callback. Note that the nodes have moved from before-last to - // before-position. - this->transferNodesFromList(L2, first, position); + if (position != last) { + // Note: we have to be careful about the case when we move the first node + // in the list. This node is the list sentinel node and we can't move it. + NodeTy *ThisSentinel = getTail(); + setTail(nullptr); + NodeTy *L2Sentinel = L2.getTail(); + L2.setTail(nullptr); + + // Remove [first, last) from its old position. + NodeTy *First = &*first, *Prev = this->getPrev(First); + NodeTy *Next = last.getNodePtrUnchecked(), *Last = this->getPrev(Next); + if (Prev) + this->setNext(Prev, Next); + else + L2.Head = Next; + this->setPrev(Next, Prev); + + // Splice [first, last) into its new position. + NodeTy *PosNext = position.getNodePtrUnchecked(); + NodeTy *PosPrev = this->getPrev(PosNext); + + // Fix head of list... + if (PosPrev) + this->setNext(PosPrev, First); + else + Head = First; + this->setPrev(First, PosPrev); + + // Fix end of list... + this->setNext(Last, PosNext); + this->setPrev(PosNext, Last); + + this->transferNodesFromList(L2, iterator(First), iterator(PosNext)); + + // Now that everything is set, restore the pointers to the list sentinels. + L2.setTail(L2Sentinel); + setTail(ThisSentinel); + } } public: @@ -479,6 +621,7 @@ public: // size_type LLVM_ATTRIBUTE_UNUSED_RESULT size() const { + if (!Head) return 0; // Don't require construction of sentinel if empty. return std::distance(begin(), end()); } @@ -488,7 +631,7 @@ public: return last; } - void clear() { erase(begin(), end()); } + void clear() { if (Head) erase(begin(), end()); } // Front and back inserters... void push_front(NodeTy *val) { insert(begin(), val); } diff --git a/llvm/include/llvm/ADT/ilist_node.h b/llvm/include/llvm/ADT/ilist_node.h index 3a414a3..afac2f3 100644 --- a/llvm/include/llvm/ADT/ilist_node.h +++ b/llvm/include/llvm/ADT/ilist_node.h @@ -15,8 +15,6 @@ #ifndef LLVM_ADT_ILIST_NODE_H #define LLVM_ADT_ILIST_NODE_H -#include - namespace llvm { template @@ -24,81 +22,46 @@ struct ilist_traits; template struct ilist_embedded_sentinel_traits; template struct ilist_half_embedded_sentinel_traits; -/// Base class for ilist nodes. -struct ilist_node_base { -#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS - PointerIntPair PrevAndSentinel; - - void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); } - ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); } - - bool isKnownSentinel() const { return PrevAndSentinel.getInt(); } - void initializeSentinel() { PrevAndSentinel.setInt(true); } -#else - ilist_node_base *Prev = nullptr; - - void setPrev(ilist_node_base *Prev) { this->Prev = Prev; } - ilist_node_base *getPrev() const { return Prev; } - - bool isKnownSentinel() const { return false; } - void initializeSentinel() {} -#endif - - ilist_node_base *Next = nullptr; +/// ilist_half_node - Base class that provides prev services for sentinels. +/// +template +class ilist_half_node { + friend struct ilist_traits; + friend struct ilist_half_embedded_sentinel_traits; + NodeTy *Prev; +protected: + NodeTy *getPrev() { return Prev; } + const NodeTy *getPrev() const { return Prev; } + void setPrev(NodeTy *P) { Prev = P; } + ilist_half_node() : Prev(nullptr) {} }; struct ilist_node_access; template class ilist_iterator; -template class ilist_sentinel; -/// Templated wrapper class. -template class ilist_node : ilist_node_base { +/// Base class that provides next/prev services for ilist nodes. +template +class ilist_node : private ilist_half_node { friend struct ilist_node_access; friend struct ilist_traits; friend struct ilist_half_embedded_sentinel_traits; friend struct ilist_embedded_sentinel_traits; - friend class ilist_iterator; - friend class ilist_sentinel; - + NodeTy *Next; + NodeTy *getNext() { return Next; } + const NodeTy *getNext() const { return Next; } + void setNext(NodeTy *N) { Next = N; } protected: - ilist_node() = default; + ilist_node() : Next(nullptr) {} -private: - ilist_node *getPrev() { - return static_cast(ilist_node_base::getPrev()); - } - ilist_node *getNext() { return static_cast(Next); } - - const ilist_node *getPrev() const { - return static_cast(ilist_node_base::getPrev()); - } - const ilist_node *getNext() const { return static_cast(Next); } - - void setPrev(ilist_node *N) { ilist_node_base::setPrev(N); } - void setNext(ilist_node *N) { Next = N; } - -public: - ilist_iterator getIterator() { return ilist_iterator(*this); } - ilist_iterator getIterator() const { - return ilist_iterator(*this); - } - - using ilist_node_base::isKnownSentinel; -}; - -template class ilist_sentinel : public ilist_node { public: - ilist_sentinel() { - ilist_node_base::initializeSentinel(); - reset(); + ilist_iterator getIterator() { + // FIXME: Stop downcasting to create the iterator (potential UB). + return ilist_iterator(static_cast(this)); } - - void reset() { - this->setPrev(this); - this->setNext(this); + ilist_iterator getIterator() const { + // FIXME: Stop downcasting to create the iterator (potential UB). + return ilist_iterator(static_cast(this)); } - - bool empty() const { return this == this->getPrev(); } }; /// An ilist node that can access its parent list. diff --git a/llvm/unittests/ADT/ilistTest.cpp b/llvm/unittests/ADT/ilistTest.cpp index a8ea63e..b63cfd6 100644 --- a/llvm/unittests/ADT/ilistTest.cpp +++ b/llvm/unittests/ADT/ilistTest.cpp @@ -128,66 +128,4 @@ TEST(ilistTest, UnsafeClear) { EXPECT_EQ(6, List.back().Value); } -struct NodeWithCallback : ilist_node { - int Value = 0; - bool IsInList = false; - - NodeWithCallback() = default; - NodeWithCallback(int Value) : Value(Value) {} - NodeWithCallback(const NodeWithCallback &) = delete; -}; - -} // end namespace - -namespace llvm { -template <> -struct ilist_traits - : public ilist_node_traits { - void addNodeToList(NodeWithCallback *N) { N->IsInList = true; } - void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; } -}; -} // end namespace llvm - -namespace { - -TEST(ilistTest, addNodeToList) { - ilist L; - NodeWithCallback N(7); - ASSERT_FALSE(N.IsInList); - - L.insert(L.begin(), &N); - ASSERT_EQ(1u, L.size()); - ASSERT_EQ(&N, &*L.begin()); - ASSERT_TRUE(N.IsInList); - - L.remove(&N); - ASSERT_EQ(0u, L.size()); - ASSERT_FALSE(N.IsInList); -} - -struct PrivateNode : private ilist_node { - friend struct llvm::ilist_node_access; - - int Value = 0; - - PrivateNode() = default; - PrivateNode(int Value) : Value(Value) {} - PrivateNode(const PrivateNode &) = delete; -}; - -TEST(ilistTest, privateNode) { - // Instantiate various APIs to be sure they're callable when ilist_node is - // inherited privately. - ilist L; - NodeWithCallback N(7); - L.insert(L.begin(), &N); - ++L.begin(); - (void)*L.begin(); - (void)(L.begin() == L.end()); - - ilist L2; - L2.splice(L2.end(), L); - L2.remove(&N); } - -} // end namespace -- 2.7.4