/home/arjun/llvm-project/llvm/include/llvm/ADT/ilist_iterator.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | |
9 | | #ifndef LLVM_ADT_ILIST_ITERATOR_H |
10 | | #define LLVM_ADT_ILIST_ITERATOR_H |
11 | | |
12 | | #include "llvm/ADT/ilist_node.h" |
13 | | #include <cassert> |
14 | | #include <cstddef> |
15 | | #include <iterator> |
16 | | #include <type_traits> |
17 | | |
18 | | namespace llvm { |
19 | | |
20 | | namespace ilist_detail { |
21 | | |
22 | | /// Find const-correct node types. |
23 | | template <class OptionsT, bool IsConst> struct IteratorTraits; |
24 | | template <class OptionsT> struct IteratorTraits<OptionsT, false> { |
25 | | using value_type = typename OptionsT::value_type; |
26 | | using pointer = typename OptionsT::pointer; |
27 | | using reference = typename OptionsT::reference; |
28 | | using node_pointer = ilist_node_impl<OptionsT> *; |
29 | | using node_reference = ilist_node_impl<OptionsT> &; |
30 | | }; |
31 | | template <class OptionsT> struct IteratorTraits<OptionsT, true> { |
32 | | using value_type = const typename OptionsT::value_type; |
33 | | using pointer = typename OptionsT::const_pointer; |
34 | | using reference = typename OptionsT::const_reference; |
35 | | using node_pointer = const ilist_node_impl<OptionsT> *; |
36 | | using node_reference = const ilist_node_impl<OptionsT> &; |
37 | | }; |
38 | | |
39 | | template <bool IsReverse> struct IteratorHelper; |
40 | | template <> struct IteratorHelper<false> : ilist_detail::NodeAccess { |
41 | | using Access = ilist_detail::NodeAccess; |
42 | | |
43 | | template <class T> static void increment(T *&I) { I = Access::getNext(*I); } |
44 | | template <class T> static void decrement(T *&I) { I = Access::getPrev(*I); } |
45 | | }; |
46 | | template <> struct IteratorHelper<true> : ilist_detail::NodeAccess { |
47 | | using Access = ilist_detail::NodeAccess; |
48 | | |
49 | | template <class T> static void increment(T *&I) { I = Access::getPrev(*I); } |
50 | | template <class T> static void decrement(T *&I) { I = Access::getNext(*I); } |
51 | | }; |
52 | | |
53 | | } // end namespace ilist_detail |
54 | | |
55 | | /// Iterator for intrusive lists based on ilist_node. |
56 | | template <class OptionsT, bool IsReverse, bool IsConst> |
57 | | class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> { |
58 | | friend ilist_iterator<OptionsT, IsReverse, !IsConst>; |
59 | | friend ilist_iterator<OptionsT, !IsReverse, IsConst>; |
60 | | friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; |
61 | | |
62 | | using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; |
63 | | using Access = ilist_detail::SpecificNodeAccess<OptionsT>; |
64 | | |
65 | | public: |
66 | | using value_type = typename Traits::value_type; |
67 | | using pointer = typename Traits::pointer; |
68 | | using reference = typename Traits::reference; |
69 | | using difference_type = ptrdiff_t; |
70 | | using iterator_category = std::bidirectional_iterator_tag; |
71 | | using const_pointer = typename OptionsT::const_pointer; |
72 | | using const_reference = typename OptionsT::const_reference; |
73 | | |
74 | | private: |
75 | | using node_pointer = typename Traits::node_pointer; |
76 | | using node_reference = typename Traits::node_reference; |
77 | | |
78 | | node_pointer NodePtr = nullptr; |
79 | | |
80 | | public: |
81 | | /// Create from an ilist_node. |
82 | 0 | explicit ilist_iterator(node_reference N) : NodePtr(&N) {} Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEC2ERNS_15ilist_node_implISB_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEC2ERNS_15ilist_node_implIS5_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEC2ERNS_15ilist_node_implIS5_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb1ELb0EEC2ERNS_15ilist_node_implIS5_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb1EEC2ERKNS_15ilist_node_implIS5_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb1ELb0EEC2ERNS_15ilist_node_implIS5_EE Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb1EEC2ERKNS_15ilist_node_implIS5_EE |
83 | | |
84 | 0 | explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {} Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEC2EPSA_ Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEC2EPS4_ Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEC2EPS4_ |
85 | | explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {} |
86 | 0 | ilist_iterator() = default; Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEC2Ev Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEC2Ev Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEC2Ev |
87 | | |
88 | | // This is templated so that we can allow constructing a const iterator from |
89 | | // a nonconst iterator... |
90 | | template <bool RHSIsConst> |
91 | | ilist_iterator(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, |
92 | | std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) |
93 | 0 | : NodePtr(RHS.NodePtr) {} |
94 | | |
95 | | // This is templated so that we can allow assigning to a const iterator from |
96 | | // a nonconst iterator... |
97 | | template <bool RHSIsConst> |
98 | | std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &> |
99 | | operator=(const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) { |
100 | | NodePtr = RHS.NodePtr; |
101 | | return *this; |
102 | | } |
103 | | |
104 | | /// Explicit conversion between forward/reverse iterators. |
105 | | /// |
106 | | /// Translate between forward and reverse iterators without changing range |
107 | | /// boundaries. The resulting iterator will dereference (and have a handle) |
108 | | /// to the previous node, which is somewhat unexpected; but converting the |
109 | | /// two endpoints in a range will give the same range in reverse. |
110 | | /// |
111 | | /// This matches std::reverse_iterator conversions. |
112 | | explicit ilist_iterator( |
113 | | const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) |
114 | | : ilist_iterator(++RHS.getReverse()) {} |
115 | | |
116 | | /// Get a reverse iterator to the same node. |
117 | | /// |
118 | | /// Gives a reverse iterator that will dereference (and have a handle) to the |
119 | | /// same node. Converting the endpoint iterators in a range will give a |
120 | | /// different range; for range operations, use the explicit conversions. |
121 | | ilist_iterator<OptionsT, !IsReverse, IsConst> getReverse() const { |
122 | | if (NodePtr) |
123 | | return ilist_iterator<OptionsT, !IsReverse, IsConst>(*NodePtr); |
124 | | return ilist_iterator<OptionsT, !IsReverse, IsConst>(); |
125 | | } |
126 | | |
127 | | /// Const-cast. |
128 | | ilist_iterator<OptionsT, IsReverse, false> getNonConst() const { |
129 | | if (NodePtr) |
130 | | return ilist_iterator<OptionsT, IsReverse, false>( |
131 | | const_cast<typename ilist_iterator<OptionsT, IsReverse, |
132 | | false>::node_reference>(*NodePtr)); |
133 | | return ilist_iterator<OptionsT, IsReverse, false>(); |
134 | | } |
135 | | |
136 | | // Accessors... |
137 | 0 | reference operator*() const { |
138 | 0 | assert(!NodePtr->isKnownSentinel()); |
139 | 0 | return *Access::getValuePtr(NodePtr); |
140 | 0 | } Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb1ELb0EEdeEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb1ELb0EEdeEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEdeEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEdeEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEdeEv |
141 | 0 | pointer operator->() const { return &operator*(); } Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEptEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEptEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEptEv |
142 | | |
143 | | // Comparison operators |
144 | 0 | friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
145 | 0 | return LHS.NodePtr == RHS.NodePtr; |
146 | 0 | } Unexecuted instantiation: _ZN4llvmeqERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEES8_ Unexecuted instantiation: _ZN4llvmeqERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEES8_ Unexecuted instantiation: _ZN4llvmeqERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEESE_ Unexecuted instantiation: _ZN4llvmeqERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb1EEES8_ Unexecuted instantiation: _ZN4llvmeqERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb1ELb0EEES8_ |
147 | 0 | friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) { |
148 | 0 | return LHS.NodePtr != RHS.NodePtr; |
149 | 0 | } Unexecuted instantiation: _ZN4llvmneERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEES8_ Unexecuted instantiation: _ZN4llvmneERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEES8_ Unexecuted instantiation: _ZN4llvmneERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEESE_ Unexecuted instantiation: _ZN4llvmneERKNS_14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb1EEES8_ |
150 | | |
151 | | // Increment and decrement operators... |
152 | 0 | ilist_iterator &operator--() { |
153 | 0 | NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev(); |
154 | 0 | return *this; |
155 | 0 | } Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEmmEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEmmEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEmmEv |
156 | 0 | ilist_iterator &operator++() { |
157 | 0 | NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext(); |
158 | 0 | return *this; |
159 | 0 | } Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb1ELb0EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb1ELb0EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb1EEppEv Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb1EEppEv |
160 | | ilist_iterator operator--(int) { |
161 | | ilist_iterator tmp = *this; |
162 | | --*this; |
163 | | return tmp; |
164 | | } |
165 | 0 | ilist_iterator operator++(int) { |
166 | 0 | ilist_iterator tmp = *this; |
167 | 0 | ++*this; |
168 | 0 | return tmp; |
169 | 0 | } Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EEppEi Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EEppEi Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EEppEi Unexecuted instantiation: _ZN4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb1ELb0EEppEi |
170 | | |
171 | | /// Get the underlying ilist_node. |
172 | 0 | node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); } Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir9OperationELb1ELb0EvEELb0ELb0EE10getNodePtrEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsIN4mlir5BlockELb1ELb0EvEELb0ELb0EE10getNodePtrEv Unexecuted instantiation: _ZNK4llvm14ilist_iteratorINS_12ilist_detail12node_optionsINS_13AllocatorListINS_4yaml5TokenENS_20BumpPtrAllocatorImplINS_15MallocAllocatorELm4096ELm4096ELm128EEEE4NodeELb1ELb0EvEELb0ELb0EE10getNodePtrEv |
173 | | |
174 | | /// Check for end. Only valid if ilist_sentinel_tracking<true>. |
175 | | bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; } |
176 | | }; |
177 | | |
178 | | template <typename From> struct simplify_type; |
179 | | |
180 | | /// Allow ilist_iterators to convert into pointers to a node automatically when |
181 | | /// used by the dyn_cast, cast, isa mechanisms... |
182 | | /// |
183 | | /// FIXME: remove this, since there is no implicit conversion to NodeTy. |
184 | | template <class OptionsT, bool IsConst> |
185 | | struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> { |
186 | | using iterator = ilist_iterator<OptionsT, false, IsConst>; |
187 | | using SimpleType = typename iterator::pointer; |
188 | | |
189 | | static SimpleType getSimplifiedValue(const iterator &Node) { return &*Node; } |
190 | | }; |
191 | | template <class OptionsT, bool IsConst> |
192 | | struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> |
193 | | : simplify_type<ilist_iterator<OptionsT, false, IsConst>> {}; |
194 | | |
195 | | } // end namespace llvm |
196 | | |
197 | | #endif // LLVM_ADT_ILIST_ITERATOR_H |