contrib/llvm/include/llvm/ADT/BreadthFirstIterator.h

   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