LLVM  14.0.0git
BreadthFirstIterator.h
Go to the documentation of this file.
1 //===- llvm/ADT/BreadthFirstIterator.h - Breadth First iterator -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file builds on the ADT/GraphTraits.h file to build a generic breadth
10 // first graph iterator. This file exposes the following functions/types:
11 //
12 // bf_begin/bf_end/bf_iterator
13 // * Normal breadth-first iteration - visit a graph level-by-level.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_ADT_BREADTHFIRSTITERATOR_H
18 #define LLVM_ADT_BREADTHFIRSTITERATOR_H
19 
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/None.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/SmallPtrSet.h"
25 #include <iterator>
26 #include <queue>
27 #include <utility>
28 
29 namespace llvm {
30 
31 // bf_iterator_storage - A private class which is used to figure out where to
32 // store the visited set. We only provide a non-external variant for now.
33 template <class SetType> class bf_iterator_storage {
34 public:
35  SetType Visited;
36 };
37 
38 // The visited state for the iteration is a simple set.
39 template <typename NodeRef, unsigned SmallSize = 8>
41 
42 // Generic Breadth first search iterator.
43 template <class GraphT,
44  class SetType =
46  class GT = GraphTraits<GraphT>>
47 class bf_iterator : public bf_iterator_storage<SetType> {
48 public:
49  using iterator_category = std::forward_iterator_tag;
50  using value_type = typename GT::NodeRef;
51  using difference_type = std::ptrdiff_t;
52  using pointer = value_type *;
53  using reference = value_type &;
54 
55 private:
56  using NodeRef = typename GT::NodeRef;
57  using ChildItTy = typename GT::ChildIteratorType;
58 
59  // First element is the node reference, second is the next child to visit.
60  using QueueElement = std::pair<NodeRef, Optional<ChildItTy>>;
61 
62  // Visit queue - used to maintain BFS ordering.
63  // Optional<> because we need markers for levels.
64  std::queue<Optional<QueueElement>> VisitQueue;
65 
66  // Current level.
67  unsigned Level = 0;
68 
69  inline bf_iterator(NodeRef Node) {
70  this->Visited.insert(Node);
71  Level = 0;
72 
73  // Also, insert a dummy node as marker.
74  VisitQueue.push(QueueElement(Node, None));
75  VisitQueue.push(None);
76  }
77 
78  inline bf_iterator() = default;
79 
80  inline void toNext() {
81  Optional<QueueElement> Head = VisitQueue.front();
82  QueueElement H = Head.getValue();
83  NodeRef Node = H.first;
84  Optional<ChildItTy> &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  // Already visited?
92  if (this->Visited.insert(Next).second)
93  VisitQueue.push(QueueElement(Next, None));
94  }
95  VisitQueue.pop();
96 
97  // Go to the next element skipping markers if needed.
98  if (!VisitQueue.empty()) {
99  Head = VisitQueue.front();
100  if (Head != None)
101  return;
102  Level += 1;
103  VisitQueue.pop();
104 
105  // Don't push another marker if this is the last
106  // element.
107  if (!VisitQueue.empty())
108  VisitQueue.push(None);
109  }
110  }
111 
112 public:
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 dereferences 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
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::bf_iterator::reference
value_type & reference
Definition: BreadthFirstIterator.h:53
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::bf_iterator::operator!=
bool operator!=(const bf_iterator &RHS) const
Definition: BreadthFirstIterator.h:124
llvm::bf_iterator::pointer
value_type * pointer
Definition: BreadthFirstIterator.h:52
llvm::bf_iterator::operator++
bf_iterator operator++(int)
Definition: BreadthFirstIterator.h:138
GraphTraits.h
llvm::bf_iterator::difference_type
std::ptrdiff_t difference_type
Definition: BreadthFirstIterator.h:51
llvm::breadth_first
iterator_range< bf_iterator< T > > breadth_first(const T &G)
Definition: BreadthFirstIterator.h:157
llvm::bf_iterator::value_type
typename GT::NodeRef value_type
Definition: BreadthFirstIterator.h:50
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
SmallPtrSet.h
llvm::bf_iterator::getLevel
unsigned getLevel() const
Definition: BreadthFirstIterator.h:144
llvm::None
const NoneType None
Definition: None.h:23
llvm::bf_iterator::begin
static bf_iterator begin(const GraphT &G)
Definition: BreadthFirstIterator.h:114
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::bf_iterator::operator->
NodeRef operator->() const
Definition: BreadthFirstIterator.h:131
llvm::bf_iterator_storage
Definition: BreadthFirstIterator.h:33
llvm::bf_iterator::end
static bf_iterator end(const GraphT &G)
Definition: BreadthFirstIterator.h:118
llvm::Optional::emplace
void emplace(ArgTypes &&... Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:264
llvm::bf_iterator_storage::Visited
SetType Visited
Definition: BreadthFirstIterator.h:35
iterator_range.h
llvm::bf_end
bf_iterator< T > bf_end(const T &G)
Definition: BreadthFirstIterator.h:152
None.h
Node
Definition: ItaniumDemangle.h:235
llvm::bf_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: BreadthFirstIterator.h:49
llvm::bf_iterator
Definition: BreadthFirstIterator.h:47
H
#define H(x, y, z)
Definition: MD5.cpp:58
llvm::bf_begin
bf_iterator< T > bf_begin(const T &G)
Definition: BreadthFirstIterator.h:148
llvm::bf_iterator::operator++
bf_iterator & operator++()
Definition: BreadthFirstIterator.h:133
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:267
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::bf_iterator::operator*
const NodeRef & operator*() const
Definition: BreadthFirstIterator.h:126
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::Optional::getValue
constexpr const T & getValue() const LLVM_LVALUE_FUNCTION
Definition: Optional.h:282
llvm::bf_iterator::operator==
bool operator==(const bf_iterator &RHS) const
Definition: BreadthFirstIterator.h:120