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 inline bf_iterator(NodeRef Node) { 68 this->Visited.insert(Node); 69 Level = 0; 70 71 // Also, insert a dummy node as marker. 72 VisitQueue.push(QueueElement(Node, None)); 73 VisitQueue.push(None); 74 } 75 76 inline bf_iterator() = default; 77 78 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 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 if (this->Visited.insert(Next).second) 91 VisitQueue.push(QueueElement(Next, None)); 92 } 93 VisitQueue.pop(); 94 95 // Go to the next element skipping markers if needed. 96 if (!VisitQueue.empty()) { 97 Head = VisitQueue.front(); 98 if (Head != None) 99 return; 100 Level += 1; 101 VisitQueue.pop(); 102 103 // Don't push another marker if this is the last 104 // element. 105 if (!VisitQueue.empty()) 106 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 return bf_iterator(GT::getEntryNode(G)); 116 } 117 118 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 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 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 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 164
