LLVM: include/llvm/ADT/BreadthFirstIterator.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18#ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
19#define LLVM_ADT_BREADTHFIRSTITERATOR_H
20
24#include
25#include
26#include
27#include
28
29namespace llvm {
30
31
32
37
38
39template <typename NodeRef, unsigned SmallSize = 8>
41
42
43template <class GraphT,
44 class SetType =
48public:
54
55private:
56 using NodeRef = typename GT::NodeRef;
57 using ChildItTy = typename GT::ChildIteratorType;
58
59
60 using QueueElement = std::pair<NodeRef, std::optional>;
61
62
63
64 std::queue<std::optional> VisitQueue;
65
66
67 unsigned Level = 0;
68
69 inline bf_iterator(NodeRef Node) {
71 Level = 0;
72
73
74 VisitQueue.push(QueueElement(Node, std::nullopt));
75 VisitQueue.push(std::nullopt);
76 }
77
79
80 inline void toNext() {
81 std::optional Head = VisitQueue.front();
82 QueueElement H = *Head;
84 std::optional &ChildIt = H.second;
85
86 if (!ChildIt)
87 ChildIt.emplace(GT::child_begin(Node));
88 while (*ChildIt != GT::child_end(Node)) {
89 NodeRef Next = *(*ChildIt)++;
90
91
92 if (this->Visited.insert(Next).second)
93 VisitQueue.push(QueueElement(Next, std::nullopt));
94 }
95 VisitQueue.pop();
96
97
98 if (!VisitQueue.empty()) {
99 Head = VisitQueue.front();
100 if (Head != std::nullopt)
101 return;
102 Level += 1;
103 VisitQueue.pop();
104
105
106
107 if (!VisitQueue.empty())
108 VisitQueue.push(std::nullopt);
109 }
110 }
111
112public:
113
114 static bf_iterator begin(const GraphT &G) {
115 return bf_iterator(GT::getEntryNode(G));
116 }
117
118 static bf_iterator end(const GraphT &G) { return bf_iterator(); }
119
121 return VisitQueue == RHS.VisitQueue;
122 }
123
124 bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
125
127
128
129
130
132
134 toNext();
135 return *this;
136 }
137
139 bf_iterator ItCopy = *this;
140 ++*this;
141 return ItCopy;
142 }
143
144 unsigned getLevel() const { return Level; }
145};
146
147
151
155
156
160
161}
162
163#endif
This file defines the little GraphTraits template class that should be specialized by classes that...
This file defines the SmallPtrSet class.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SetType Visited
Definition BreadthFirstIterator.h:35
const value_type & reference
Definition BreadthFirstIterator.h:53
bf_iterator operator++(int)
Definition BreadthFirstIterator.h:138
std::ptrdiff_t difference_type
Definition BreadthFirstIterator.h:51
static bf_iterator begin(const GraphT &G)
Definition BreadthFirstIterator.h:114
NodeRef operator->() const
Definition BreadthFirstIterator.h:131
typename GT::NodeRef value_type
Definition BreadthFirstIterator.h:50
value_type * pointer
Definition BreadthFirstIterator.h:52
reference operator*() const
Definition BreadthFirstIterator.h:126
bf_iterator & operator++()
Definition BreadthFirstIterator.h:133
bool operator==(const bf_iterator &RHS) const
Definition BreadthFirstIterator.h:120
bool operator!=(const bf_iterator &RHS) const
Definition BreadthFirstIterator.h:124
std::forward_iterator_tag iterator_category
Definition BreadthFirstIterator.h:49
unsigned getLevel() const
Definition BreadthFirstIterator.h:144
static bf_iterator end(const GraphT &G)
Definition BreadthFirstIterator.h:118
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bf_iterator< T > bf_end(const T &G)
Definition BreadthFirstIterator.h:152
SmallPtrSet< NodeRef, SmallSize > bf_iterator_default_set
Definition BreadthFirstIterator.h:40
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition BreadthFirstIterator.h:157
FunctionAddr VTableAddr Next
bf_iterator< T > bf_begin(const T &G)
Definition BreadthFirstIterator.h:148