LCOV - code coverage report
Current view: top level - include/llvm/ADT - BreadthFirstIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 34 34 100.0 %
Date: 2017-09-14 15:23:50 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          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          16 : 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          12 : 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           6 :   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          12 :     VisitQueue.push(QueueElement(Node, None));
      73           8 :     VisitQueue.push(None);
      74           2 :   }
      75             : 
      76           6 :   inline bf_iterator() = default;
      77             : 
      78           8 :   inline void toNext() {
      79          31 :     Optional<QueueElement> Head = VisitQueue.front();
      80          23 :     QueueElement H = Head.getValue();
      81           8 :     NodeRef Node = H.first;
      82           8 :     Optional<ChildItTy> &ChildIt = H.second;
      83             : 
      84           8 :     if (!ChildIt)
      85          16 :       ChildIt.emplace(GT::child_begin(Node));
      86          57 :     while (*ChildIt != GT::child_end(Node)) {
      87          22 :       NodeRef Next = *(*ChildIt)++;
      88             : 
      89             :       // Already visited?
      90          11 :       if (this->Visited.insert(Next).second)
      91          36 :         VisitQueue.push(QueueElement(Next, None));
      92             :     }
      93          16 :     VisitQueue.pop();
      94             : 
      95             :     // Go to the next element skipping markers if needed.
      96          16 :     if (!VisitQueue.empty()) {
      97          24 :       Head = VisitQueue.front();
      98          16 :       if (Head != None)
      99           1 :         return;
     100           7 :       Level += 1;
     101          14 :       VisitQueue.pop();
     102             : 
     103             :       // Don't push another marker if this is the last
     104             :       // element.
     105          14 :       if (!VisitQueue.empty())
     106          20 :         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           4 :     return VisitQueue == RHS.VisitQueue;
     122             :   }
     123             : 
     124             :   bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
     125             : 
     126          24 :   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             :   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

Generated by: LCOV version 1.13