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