diff options
| -rw-r--r-- | llvm/include/llvm/ADT/ilist.h | 379 | ||||
| -rw-r--r-- | llvm/include/llvm/ADT/ilist_node.h | 89 | ||||
| -rw-r--r-- | llvm/unittests/ADT/ilistTest.cpp | 62 |
3 files changed, 243 insertions, 287 deletions
diff --git a/llvm/include/llvm/ADT/ilist.h b/llvm/include/llvm/ADT/ilist.h index 3723039bbad..10ff088dcd6 100644 --- a/llvm/include/llvm/ADT/ilist.h +++ b/llvm/include/llvm/ADT/ilist.h @@ -15,17 +15,16 @@ // 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 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. +// 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(). // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_ILIST_H #define LLVM_ADT_ILIST_H +#include "llvm/ADT/ilist_node.h" #include "llvm/Support/Compiler.h" #include <algorithm> #include <cassert> @@ -38,37 +37,42 @@ namespace llvm { template<typename NodeTy, typename Traits> class iplist; template<typename NodeTy> class ilist_iterator; -/// An access class for next/prev on ilist_nodes. +/// An access class for ilist_node private API. /// /// 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 ilist +/// It's strongly discouraged to *use* this class outside of the ilist /// implementation. struct ilist_node_access { - template <typename NodeTy> static NodeTy *getPrev(NodeTy *N) { + template <typename T> static ilist_node<T> *getNodePtr(T *N) { return N; } + template <typename T> static const ilist_node<T> *getNodePtr(const T *N) { + return N; + } + + template <typename T> static ilist_node<T> *getPrev(ilist_node<T> *N) { return N->getPrev(); } - template <typename NodeTy> static NodeTy *getNext(NodeTy *N) { + template <typename T> static ilist_node<T> *getNext(ilist_node<T> *N) { return N->getNext(); } - template <typename NodeTy> static const NodeTy *getPrev(const NodeTy *N) { + template <typename T> static const ilist_node<T> *getPrev(const ilist_node<T> *N) { return N->getPrev(); } - template <typename NodeTy> static const NodeTy *getNext(const NodeTy *N) { + template <typename T> static const ilist_node<T> *getNext(const ilist_node<T> *N) { return N->getNext(); } - template <typename NodeTy> static void setPrev(NodeTy *N, NodeTy *Prev) { + template <typename T> static void setPrev(ilist_node<T> *N, ilist_node<T> *Prev) { N->setPrev(Prev); } - template <typename NodeTy> static void setNext(NodeTy *N, NodeTy *Next) { + template <typename T> static void setNext(ilist_node<T> *N, ilist_node<T> *Next) { N->setNext(Next); } - template <typename NodeTy> static void setPrev(NodeTy *N, std::nullptr_t) { + template <typename T> static void setPrev(ilist_node<T> *N, std::nullptr_t) { N->setPrev(nullptr); } - template <typename NodeTy> static void setNext(NodeTy *N, std::nullptr_t) { + template <typename T> static void setNext(ilist_node<T> *N, std::nullptr_t) { N->setNext(nullptr); } }; @@ -93,111 +97,31 @@ template <class TraitsT, class NodeT> struct HasGetNext { static const bool value = sizeof(hasGetNext<TraitsT>(nullptr)) == sizeof(Yes); }; -} // end namespace ilist_detail - -template<typename NodeTy> -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<typename NodeTy> -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<NodeTy>::createSentinel(); - ilist_traits<NodeTy>::noteHead(Head, Head); - ilist_node_access::setNext(Head, nullptr); - return Head; - } - return ilist_node_access::getPrev(Head); - } - - /// noteHead - stash the sentinel into its default location - static void noteHead(NodeTy *NewHead, NodeTy *Sentinel) { - ilist_node_access::setPrev(NewHead, Sentinel); - } -}; - -template <typename NodeTy> class ilist_half_node; -template <typename NodeTy> class ilist_node; - -/// Traits with an embedded ilist_node as a sentinel. -template <typename NodeTy> 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<NodeTy>, - // 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<NodeTy>), so no one will ever notice the superposition. - return static_cast<NodeTy *>(&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<NodeTy> Sentinel; -}; - -/// Trait with an embedded ilist_half_node as a sentinel. -template <typename NodeTy> 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<NodeTy *>(&Sentinel); - } - static void destroySentinel(NodeTy *) {} +/// 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 <class TraitsT> struct HasCreateSentinel { + typedef char Yes[1]; + typedef char No[2]; + template <size_t N> struct SFINAE {}; - NodeTy *provideInitialHead() const { return createSentinel(); } - NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } - static void noteHead(NodeTy *, NodeTy *) {} + template <class U> + static Yes & + hasCreateSentinel(SFINAE<sizeof(make<U>().createSentinel())> * = 0); + template <class U> static No &hasCreateSentinel(...); -private: - mutable ilist_half_node<NodeTy> Sentinel; + static const bool value = + sizeof(hasCreateSentinel<TraitsT>(nullptr)) == sizeof(Yes); }; -/// Traits with an embedded full node as a sentinel. -template <typename NodeTy> 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 *) {} +} // end namespace ilist_detail - NodeTy *provideInitialHead() const { return createSentinel(); } - NodeTy *ensureHead(NodeTy *) const { return createSentinel(); } - static void noteHead(NodeTy *, NodeTy *) {} +template <typename NodeTy> struct ilist_traits; -private: - mutable NodeTy Sentinel; -}; +// TODO: Delete uses from subprojects, then delete these. +template <typename NodeTy> struct ilist_sentinel_traits {}; +template <typename NodeTy> struct ilist_embedded_sentinel_traits {}; +template <typename NodeTy> struct ilist_half_embedded_sentinel_traits {}; +template <typename NodeTy> struct ilist_full_embedded_sentinel_traits {}; /// ilist_node_traits - A fragment for template traits for intrusive list /// that provides default node related operations. @@ -219,8 +143,7 @@ struct ilist_node_traits { /// for all common operations. /// template <typename NodeTy> -struct ilist_default_traits : public ilist_sentinel_traits<NodeTy>, - public ilist_node_traits<NodeTy> {}; +struct ilist_default_traits : public ilist_node_traits<NodeTy> {}; // Template traits for intrusive list. By specializing this template class, you // can change what next/prev fields are used to store the links... @@ -263,16 +186,15 @@ public: typedef node_type &node_reference; private: - pointer NodePtr; + node_pointer NodePtr = nullptr; public: /// Create from an ilist_node. - explicit ilist_iterator(node_reference N) - : NodePtr(static_cast<NodeTy *>(&N)) {} + explicit ilist_iterator(node_reference N) : NodePtr(&N) {} explicit ilist_iterator(pointer NP) : NodePtr(NP) {} explicit ilist_iterator(reference NR) : NodePtr(&NR) {} - ilist_iterator() : NodePtr(nullptr) {} + ilist_iterator() = default; // This is templated so that we can allow constructing a const iterator from // a nonconst iterator... @@ -281,20 +203,23 @@ public: const ilist_iterator<node_ty> &RHS, typename std::enable_if<std::is_convertible<node_ty *, NodeTy *>::value, void *>::type = nullptr) - : NodePtr(RHS.getNodePtrUnchecked()) {} + : NodePtr(RHS.getNodePtr()) {} // This is templated so that we can allow assigning to a const iterator from // a nonconst iterator... template <class node_ty> const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) { - NodePtr = RHS.getNodePtrUnchecked(); + NodePtr = RHS.getNodePtr(); return *this; } void reset(pointer NP) { NodePtr = NP; } // Accessors... - reference operator*() const { return *NodePtr; } + reference operator*() const { + assert(!NodePtr->isKnownSentinel()); + return static_cast<NodeTy &>(*getNodePtr()); + } pointer operator->() const { return &operator*(); } // Comparison operators @@ -328,9 +253,6 @@ public: /// Get the underlying ilist_node. node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } - - // Internal interface, do not use... - pointer getNodePtrUnchecked() const { return NodePtr; } }; // Allow ilist_iterators to convert into pointers to a node automatically when @@ -356,56 +278,33 @@ template<typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy> > { //===----------------------------------------------------------------------===// // -/// 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. -/// +/// 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. template <typename NodeTy, typename Traits = ilist_traits<NodeTy>> 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<Traits, NodeTy>::value, "ilist next and prev links are not customizable!"); + static_assert(!ilist_detail::HasCreateSentinel<Traits>::value, + "ilist sentinel is not customizable!"); #endif - 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); } + ilist_sentinel<NodeTy> Sentinel; - /// 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); - } + typedef ilist_node<NodeTy> node_type; + typedef const ilist_node<NodeTy> const_node_type; static bool op_less(NodeTy &L, NodeTy &R) { return L < R; } static bool op_equal(NodeTy &L, NodeTy &R) { return L == R; } - // No fundamental reason why iplist can't be copyable, but the default - // copy/copy-assign won't do. + // Copying intrusively linked nodes doesn't make sense. iplist(const iplist &) = delete; void operator=(const iplist &) = delete; @@ -422,30 +321,14 @@ public: typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; - iplist() : Head(this->provideInitialHead()) {} - ~iplist() { - if (!Head) return; - clear(); - Traits::destroySentinel(getTail()); - } + iplist() = default; + ~iplist() { clear(); } // Iterator creation methods. - 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()); - } + 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); } // reverse iterator creation methods. reverse_iterator rbegin() { return reverse_iterator(end()); } @@ -456,44 +339,39 @@ public: // Miscellaneous inspection routines. size_type max_size() const { return size_type(-1); } - bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { - return !Head || Head == getTail(); - } + bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); } // Front and back accessor functions... reference front() { assert(!empty() && "Called front() on empty list!"); - return *Head; + return *begin(); } const_reference front() const { assert(!empty() && "Called front() on empty list!"); - return *Head; + return *begin(); } reference back() { assert(!empty() && "Called back() on empty list!"); - return *this->getPrev(getTail()); + return *--end(); } const_reference back() const { assert(!empty() && "Called back() on empty list!"); - return *this->getPrev(getTail()); + return *--end(); } void swap(iplist &RHS) { assert(0 && "Swap does not use list traits callback correctly yet!"); - std::swap(Head, RHS.Head); + std::swap(Sentinel, RHS.Sentinel); } iterator insert(iterator where, NodeTy *New) { - 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); + 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); this->addNodeToList(New); // Notify traits that we added a node... return iterator(New); @@ -513,24 +391,23 @@ public: NodeTy *remove(iterator &IT) { assert(IT != end() && "Cannot remove end of list!"); NodeTy *Node = &*IT; - NodeTy *NextNode = this->getNext(Node); - NodeTy *PrevNode = this->getPrev(Node); + node_type *Base = this->getNodePtr(Node); + node_type *Next = this->getNext(Base); + node_type *Prev = this->getPrev(Base); - 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->setNext(Prev, Next); + this->setPrev(Next, Prev); + IT = iterator(*Next); 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. - // 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); + // 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); return Node; } @@ -556,12 +433,7 @@ 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() { - if (Head) { - Head = getTail(); - this->setPrev(Head, Head); - } - } + void clearAndLeakNodesUnsafely() { Sentinel.reset(); } private: // transfer - The heart of the splice function. Move linked list nodes from @@ -570,48 +442,34 @@ 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) { - // 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); - } + 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); } public: @@ -621,7 +479,6 @@ 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()); } @@ -631,7 +488,7 @@ public: return last; } - void clear() { if (Head) erase(begin(), end()); } + void clear() { 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 afac2f33f70..3a414a3364b 100644 --- a/llvm/include/llvm/ADT/ilist_node.h +++ b/llvm/include/llvm/ADT/ilist_node.h @@ -15,6 +15,8 @@ #ifndef LLVM_ADT_ILIST_NODE_H #define LLVM_ADT_ILIST_NODE_H +#include <llvm/ADT/PointerIntPair.h> + namespace llvm { template<typename NodeTy> @@ -22,46 +24,81 @@ struct ilist_traits; template <typename NodeTy> struct ilist_embedded_sentinel_traits; template <typename NodeTy> struct ilist_half_embedded_sentinel_traits; -/// ilist_half_node - Base class that provides prev services for sentinels. -/// -template<typename NodeTy> -class ilist_half_node { - friend struct ilist_traits<NodeTy>; - friend struct ilist_half_embedded_sentinel_traits<NodeTy>; - NodeTy *Prev; -protected: - NodeTy *getPrev() { return Prev; } - const NodeTy *getPrev() const { return Prev; } - void setPrev(NodeTy *P) { Prev = P; } - ilist_half_node() : Prev(nullptr) {} +/// Base class for ilist nodes. +struct ilist_node_base { +#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS + PointerIntPair<ilist_node_base *, 1> 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; }; struct ilist_node_access; template <typename NodeTy> class ilist_iterator; +template <typename NodeTy> class ilist_sentinel; -/// Base class that provides next/prev services for ilist nodes. -template<typename NodeTy> -class ilist_node : private ilist_half_node<NodeTy> { +/// Templated wrapper class. +template <typename NodeTy> class ilist_node : ilist_node_base { friend struct ilist_node_access; friend struct ilist_traits<NodeTy>; friend struct ilist_half_embedded_sentinel_traits<NodeTy>; friend struct ilist_embedded_sentinel_traits<NodeTy>; - NodeTy *Next; - NodeTy *getNext() { return Next; } - const NodeTy *getNext() const { return Next; } - void setNext(NodeTy *N) { Next = N; } + friend class ilist_iterator<NodeTy>; + friend class ilist_sentinel<NodeTy>; + protected: - ilist_node() : Next(nullptr) {} + ilist_node() = default; -public: - ilist_iterator<NodeTy> getIterator() { - // FIXME: Stop downcasting to create the iterator (potential UB). - return ilist_iterator<NodeTy>(static_cast<NodeTy *>(this)); +private: + ilist_node *getPrev() { + return static_cast<ilist_node *>(ilist_node_base::getPrev()); + } + ilist_node *getNext() { return static_cast<ilist_node *>(Next); } + + const ilist_node *getPrev() const { + return static_cast<ilist_node *>(ilist_node_base::getPrev()); } + const ilist_node *getNext() const { return static_cast<ilist_node *>(Next); } + + void setPrev(ilist_node *N) { ilist_node_base::setPrev(N); } + void setNext(ilist_node *N) { Next = N; } + +public: + ilist_iterator<NodeTy> getIterator() { return ilist_iterator<NodeTy>(*this); } ilist_iterator<const NodeTy> getIterator() const { - // FIXME: Stop downcasting to create the iterator (potential UB). - return ilist_iterator<const NodeTy>(static_cast<const NodeTy *>(this)); + return ilist_iterator<const NodeTy>(*this); + } + + using ilist_node_base::isKnownSentinel; +}; + +template <typename NodeTy> class ilist_sentinel : public ilist_node<NodeTy> { +public: + ilist_sentinel() { + ilist_node_base::initializeSentinel(); + reset(); } + + void reset() { + this->setPrev(this); + this->setNext(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 b63cfd6310c..a8ea63ed464 100644 --- a/llvm/unittests/ADT/ilistTest.cpp +++ b/llvm/unittests/ADT/ilistTest.cpp @@ -128,4 +128,66 @@ TEST(ilistTest, UnsafeClear) { EXPECT_EQ(6, List.back().Value); } +struct NodeWithCallback : ilist_node<NodeWithCallback> { + 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<NodeWithCallback> + : public ilist_node_traits<NodeWithCallback> { + void addNodeToList(NodeWithCallback *N) { N->IsInList = true; } + void removeNodeFromList(NodeWithCallback *N) { N->IsInList = false; } +}; +} // end namespace llvm + +namespace { + +TEST(ilistTest, addNodeToList) { + ilist<NodeWithCallback> 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<PrivateNode> { + 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<NodeWithCallback> L; + NodeWithCallback N(7); + L.insert(L.begin(), &N); + ++L.begin(); + (void)*L.begin(); + (void)(L.begin() == L.end()); + + ilist<NodeWithCallback> L2; + L2.splice(L2.end(), L); + L2.remove(&N); } + +} // end namespace |
