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