Line data Source code
1 : //===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- 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 builds on the ADT/GraphTraits.h file to build a generic breadth
11 : // first graph iterator. This file exposes the following functions/types:
12 : //
13 : // bf_begin/bf_end/bf_iterator
14 : // * Normal breadth-first iteration - visit a graph level-by-level.
15 : //
16 : //===----------------------------------------------------------------------===//
17 :
18 : #ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
19 : #define LLVM_ADT_BREADTHFIRSTITERATOR_H
20 :
21 : #include "llvm/ADT/GraphTraits.h"
22 : #include "llvm/ADT/None.h"
23 : #include "llvm/ADT/Optional.h"
24 : #include "llvm/ADT/SmallPtrSet.h"
25 : #include "llvm/ADT/iterator_range.h"
26 : #include <iterator>
27 : #include <queue>
28 : #include <utility>
29 :
30 : namespace llvm {
31 :
32 : // bf_iterator_storage - A private class which is used to figure out where to
33 : // store the visited set. We only provide a non-external variant for now.
34 : template <class SetType> class bf_iterator_storage {
35 : public:
36 : SetType Visited;
37 : };
38 :
39 : // The visited state for the iteration is a simple set.
40 : template <typename NodeRef, unsigned SmallSize = 8>
41 : using bf_iterator_default_set = SmallPtrSet<NodeRef, SmallSize>;
42 :
43 : // Generic Breadth first search iterator.
44 : template <class GraphT,
45 : class SetType =
46 : bf_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
47 : class GT = GraphTraits<GraphT>>
48 : class bf_iterator
49 : : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
50 : public bf_iterator_storage<SetType> {
51 : using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
52 :
53 : using NodeRef = typename GT::NodeRef;
54 : using ChildItTy = typename GT::ChildIteratorType;
55 :
56 : // First element is the node reference, second is the next child to visit.
57 : using QueueElement = std::pair<NodeRef, Optional<ChildItTy>>;
58 :
59 : // Visit queue - used to maintain BFS ordering.
60 : // Optional<> because we need markers for levels.
61 : std::queue<Optional<QueueElement>> VisitQueue;
62 :
63 : // Current level.
64 : unsigned Level;
65 :
66 : private:
67 2 : inline bf_iterator(NodeRef Node) {
68 2 : this->Visited.insert(Node);
69 2 : Level = 0;
70 :
71 : // Also, insert a dummy node as marker.
72 2 : VisitQueue.push(QueueElement(Node, None));
73 2 : VisitQueue.push(None);
74 2 : }
75 :
76 2 : inline bf_iterator() = default;
77 :
78 8 : inline void toNext() {
79 : Optional<QueueElement> Head = VisitQueue.front();
80 : QueueElement H = Head.getValue();
81 : NodeRef Node = H.first;
82 : Optional<ChildItTy> &ChildIt = H.second;
83 :
84 8 : if (!ChildIt)
85 : ChildIt.emplace(GT::child_begin(Node));
86 : while (*ChildIt != GT::child_end(Node)) {
87 : NodeRef Next = *(*ChildIt)++;
88 :
89 : // Already visited?
90 11 : if (this->Visited.insert(Next).second)
91 6 : VisitQueue.push(QueueElement(Next, None));
92 : }
93 : VisitQueue.pop();
94 :
95 : // Go to the next element skipping markers if needed.
96 8 : if (!VisitQueue.empty()) {
97 : Head = VisitQueue.front();
98 8 : if (Head != None)
99 : return;
100 7 : Level += 1;
101 : VisitQueue.pop();
102 :
103 : // Don't push another marker if this is the last
104 : // element.
105 7 : if (!VisitQueue.empty())
106 5 : VisitQueue.push(None);
107 : }
108 : }
109 :
110 : public:
111 : using pointer = typename super::pointer;
112 :
113 : // Provide static begin and end methods as our public "constructors"
114 : static bf_iterator begin(const GraphT &G) {
115 2 : return bf_iterator(GT::getEntryNode(G));
116 : }
117 :
118 2 : static bf_iterator end(const GraphT &G) { return bf_iterator(); }
119 :
120 : bool operator==(const bf_iterator &RHS) const {
121 : return VisitQueue == RHS.VisitQueue;
122 : }
123 :
124 : bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
125 :
126 8 : const NodeRef &operator*() const { return VisitQueue.front()->first; }
127 :
128 : // This is a nonstandard operator-> that dereferenfces the pointer an extra
129 : // time so that you can actually call methods on the node, because the
130 : // contained type is a pointer.
131 : NodeRef operator->() const { return **this; }
132 :
133 : bf_iterator &operator++() { // Pre-increment
134 8 : toNext();
135 : return *this;
136 : }
137 :
138 : bf_iterator operator++(int) { // Post-increment
139 : bf_iterator ItCopy = *this;
140 : ++*this;
141 : return ItCopy;
142 : }
143 :
144 0 : unsigned getLevel() const { return Level; }
145 : };
146 :
147 : // Provide global constructors that automatically figure out correct types.
148 : template <class T> bf_iterator<T> bf_begin(const T &G) {
149 : return bf_iterator<T>::begin(G);
150 : }
151 :
152 : template <class T> bf_iterator<T> bf_end(const T &G) {
153 : return bf_iterator<T>::end(G);
154 : }
155 :
156 : // Provide an accessor method to use them in range-based patterns.
157 : template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) {
158 : return make_range(bf_begin(G), bf_end(G));
159 : }
160 :
161 : } // end namespace llvm
162 :
163 : #endif // LLVM_ADT_BREADTHFIRSTITERATOR_H
|
