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 18namespace llvm { 19 20template<typename NodeTy> 21struct ilist_traits; 22template <typename NodeTy> struct ilist_embedded_sentinel_traits; 23template <typename NodeTy> struct ilist_half_embedded_sentinel_traits; 24 25/// ilist_half_node - Base class that provides prev services for sentinels. 26/// 27template<typename NodeTy> 28class ilist_half_node { 29 friend struct ilist_traits<NodeTy>; 30 friend struct ilist_half_embedded_sentinel_traits<NodeTy>; 31 NodeTy *Prev; 32protected: 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 39template<typename NodeTy> 40struct ilist_nextprev_traits; 41 42template <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/// 47template<typename NodeTy> 48class 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; } 57protected: 58 ilist_node() : Next(nullptr) {} 59 60public: 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. 75template <typename NodeTy, typename ParentTy> 76class ilist_node_with_parent : public ilist_node<NodeTy> { 77protected: 78 ilist_node_with_parent() = default; 79 80private: 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 90public: 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