1 //==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the ilist_node class template, which is a convenient 11 // base class for creating classes that can be used with ilists. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ADT_ILIST_NODE_H 16 #define LLVM_ADT_ILIST_NODE_H 17 18 namespace llvm { 19 20 template<typename NodeTy> 21 struct ilist_traits; 22 template <typename NodeTy> struct ilist_embedded_sentinel_traits; 23 template <typename NodeTy> struct ilist_half_embedded_sentinel_traits; 24 25 /// ilist_half_node - Base class that provides prev services for sentinels. 26 /// 27 template<typename NodeTy> 28 class ilist_half_node { 29 friend struct ilist_traits<NodeTy>; 30 friend struct ilist_half_embedded_sentinel_traits<NodeTy>; 31 NodeTy *Prev; 32 protected: 33 NodeTy *getPrev() { return Prev; } 34 const NodeTy *getPrev() const { return Prev; } 35 void setPrev(NodeTy *P) { Prev = P; } 36 ilist_half_node() : Prev(nullptr) {} 37 }; 38 39 template<typename NodeTy> 40 struct ilist_nextprev_traits; 41 42 template <typename NodeTy> class ilist_iterator; 43 44 /// ilist_node - Base class that provides next/prev services for nodes 45 /// that use ilist_nextprev_traits or ilist_default_traits. 46 /// 47 template<typename NodeTy> 48 class ilist_node : private ilist_half_node<NodeTy> { 49 friend struct ilist_nextprev_traits<NodeTy>; 50 friend struct ilist_traits<NodeTy>; 51 friend struct ilist_half_embedded_sentinel_traits<NodeTy>; 52 friend struct ilist_embedded_sentinel_traits<NodeTy>; 53 NodeTy *Next; 54 NodeTy *getNext() { return Next; } 55 const NodeTy *getNext() const { return Next; } 56 void setNext(NodeTy *N) { Next = N; } 57 protected: 58 ilist_node() : Next(nullptr) {} 59 60 public: 61 ilist_iterator<NodeTy> getIterator() { 62 // FIXME: Stop downcasting to create the iterator (potential UB). 63 return ilist_iterator<NodeTy>(static_cast<NodeTy *>(this)); 64 } 65 ilist_iterator<const NodeTy> getIterator() const { 66 // FIXME: Stop downcasting to create the iterator (potential UB). 67 return ilist_iterator<const NodeTy>(static_cast<const NodeTy *>(this)); 68 } 69 }; 70 71 /// An ilist node that can access its parent list. 72 /// 73 /// Requires \c NodeTy to have \a getParent() to find the parent node, and the 74 /// \c ParentTy to have \a getSublistAccess() to get a reference to the list. 75 template <typename NodeTy, typename ParentTy> 76 class ilist_node_with_parent : public ilist_node<NodeTy> { 77 protected: 78 ilist_node_with_parent() = default; 79 80 private: 81 /// Forward to NodeTy::getParent(). 82 /// 83 /// Note: do not use the name "getParent()". We want a compile error 84 /// (instead of recursion) when the subclass fails to implement \a 85 /// getParent(). 86 const ParentTy *getNodeParent() const { 87 return static_cast<const NodeTy *>(this)->getParent(); 88 } 89 90 public: 91 /// @name Adjacent Node Accessors 92 /// @{ 93 /// \brief Get the previous node, or \c nullptr for the list head. 94 NodeTy *getPrevNode() { 95 // Should be separated to a reused function, but then we couldn't use auto 96 // (and would need the type of the list). 97 const auto &List = 98 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); 99 return List.getPrevNode(*static_cast<NodeTy *>(this)); 100 } 101 /// \brief Get the previous node, or \c nullptr for the list head. 102 const NodeTy *getPrevNode() const { 103 return const_cast<ilist_node_with_parent *>(this)->getPrevNode(); 104 } 105 106 /// \brief Get the next node, or \c nullptr for the list tail. 107 NodeTy *getNextNode() { 108 // Should be separated to a reused function, but then we couldn't use auto 109 // (and would need the type of the list). 110 const auto &List = 111 getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); 112 return List.getNextNode(*static_cast<NodeTy *>(this)); 113 } 114 /// \brief Get the next node, or \c nullptr for the list tail. 115 const NodeTy *getNextNode() const { 116 return const_cast<ilist_node_with_parent *>(this)->getNextNode(); 117 } 118 /// @} 119 }; 120 121 } // End llvm namespace 122 123 #endif 124