unittests/ADT/TestGraph.h

   1 //===- llvm/unittest/ADT/TestGraph.h - Graph for testing ------------------===//
   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 // Common graph data structure for testing.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H
  14 #define LLVM_UNITTESTS_ADT_TEST_GRAPH_H
  15
  16 #include "llvm/ADT/GraphTraits.h"
  17 #include <cassert>
  18 #include <climits>
  19 #include <utility>
  20
  21 namespace llvm {
  22
  23 /// Graph<N> - A graph with N nodes.  Note that N can be at most 8.
  24 template <unsigned N>
  25 class Graph {
  26 private:
  27   // Disable copying.
  28   Graph(const Graph&);
  29   Graph& operator=(const Graph&);
  30
  31   static void ValidateIndex(unsigned Idx) {
  32     assert(Idx < N && "Invalid node index!");
  33   }
  34 public:
  35
  36   /// NodeSubset - A subset of the graph's nodes.
  37   class NodeSubset {
  38     typedef unsigned char BitVector; // Where the limitation N <= 8 comes from.
  39     BitVector Elements;
  40     NodeSubset(BitVector e) : Elements(e) {}
  41   public:
  42     /// NodeSubset - Default constructor, creates an empty subset.
  43     NodeSubset() : Elements(0) {
  44       assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");
  45     }
  46
  47     /// Comparison operators.
  48     bool operator==(const NodeSubset &other) const {
  49       return other.Elements == this->Elements;
  50     }
  51     bool operator!=(const NodeSubset &other) const {
  52       return !(*this == other);
  53     }
  54
  55     /// AddNode - Add the node with the given index to the subset.
  56     void AddNode(unsigned Idx) {
  57       ValidateIndex(Idx);
  58       Elements |= 1U << Idx;
  59     }
  60
  61     /// DeleteNode - Remove the node with the given index from the subset.
  62     void DeleteNode(unsigned Idx) {
  63       ValidateIndex(Idx);
  64       Elements &= ~(1U << Idx);
  65     }
  66
  67     /// count - Return true if the node with the given index is in the subset.
  68     bool count(unsigned Idx) {
  69       ValidateIndex(Idx);
  70       return (Elements & (1U << Idx)) != 0;
  71     }
  72
  73     /// isEmpty - Return true if this is the empty set.
  74     bool isEmpty() const {
  75       return Elements == 0;
  76     }
  77
  78     /// isSubsetOf - Return true if this set is a subset of the given one.
  79     bool isSubsetOf(const NodeSubset &other) const {
  80       return (this->Elements | other.Elements) == other.Elements;
  81     }
  82
  83     /// Complement - Return the complement of this subset.
  84     NodeSubset Complement() const {
  85       return ~(unsigned)this->Elements & ((1U << N) - 1);
  86     }
  87
  88     /// Join - Return the union of this subset and the given one.
  89     NodeSubset Join(const NodeSubset &other) const {
  90       return this->Elements | other.Elements;
  91     }
  92
  93     /// Meet - Return the intersection of this subset and the given one.
  94     NodeSubset Meet(const NodeSubset &other) const {
  95       return this->Elements & other.Elements;
  96     }
  97   };
  98
  99   /// NodeType - Node index and set of children of the node.
 100   typedef std::pair<unsigned, NodeSubset> NodeType;
 101
 102 private:
 103   /// Nodes - The list of nodes for this graph.
 104   NodeType Nodes[N];
 105 public:
 106
 107   /// Graph - Default constructor.  Creates an empty graph.
 108   Graph() {
 109     // Let each node know which node it is.  This allows us to find the start of
 110     // the Nodes array given a pointer to any element of it.
 111     for (unsigned i = 0; i != N; ++i)
 112       Nodes[i].first = i;
 113   }
 114
 115   /// AddEdge - Add an edge from the node with index FromIdx to the node with
 116   /// index ToIdx.
 117   void AddEdge(unsigned FromIdx, unsigned ToIdx) {
 118     ValidateIndex(FromIdx);
 119     Nodes[FromIdx].second.AddNode(ToIdx);
 120   }
 121
 122   /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to
 123   /// the node with index ToIdx.
 124   void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {
 125     ValidateIndex(FromIdx);
 126     Nodes[FromIdx].second.DeleteNode(ToIdx);
 127   }
 128
 129   /// AccessNode - Get a pointer to the node with the given index.
 130   NodeType *AccessNode(unsigned Idx) const {
 131     ValidateIndex(Idx);
 132     // The constant cast is needed when working with GraphTraits, which insists
 133     // on taking a constant Graph.
 134     return const_cast<NodeType *>(&Nodes[Idx]);
 135   }
 136
 137   /// NodesReachableFrom - Return the set of all nodes reachable from the given
 138   /// node.
 139   NodeSubset NodesReachableFrom(unsigned Idx) const {
 140     // This algorithm doesn't scale, but that doesn't matter given the small
 141     // size of our graphs.
 142     NodeSubset Reachable;
 143
 144     // The initial node is reachable.
 145     Reachable.AddNode(Idx);
 146     do {
 147       NodeSubset Previous(Reachable);
 148
 149       // Add in all nodes which are children of a reachable node.
 150       for (unsigned i = 0; i != N; ++i)
 151         if (Previous.count(i))
 152           Reachable = Reachable.Join(Nodes[i].second);
 153
 154       // If nothing changed then we have found all reachable nodes.
 155       if (Reachable == Previous)
 156         return Reachable;
 157
 158       // Rinse and repeat.
 159     } while (1);
 160   }
 161
 162   /// ChildIterator - Visit all children of a node.
 163   class ChildIterator {
 164     friend class Graph;
 165
 166     /// FirstNode - Pointer to first node in the graph's Nodes array.
 167     NodeType *FirstNode;
 168     /// Children - Set of nodes which are children of this one and that haven't
 169     /// yet been visited.
 170     NodeSubset Children;
 171
 172     ChildIterator(); // Disable default constructor.
 173   protected:
 174     ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}
 175
 176   public:
 177     /// ChildIterator - Copy constructor.
 178     ChildIterator(const ChildIterator& other) : FirstNode(other.FirstNode),
 179       Children(other.Children) {}
 180
 181     /// Comparison operators.
 182     bool operator==(const ChildIterator &other) const {
 183       return other.FirstNode == this->FirstNode &&
 184         other.Children == this->Children;
 185     }
 186     bool operator!=(const ChildIterator &other) const {
 187       return !(*this == other);
 188     }
 189
 190     /// Prefix increment operator.
 191     ChildIterator& operator++() {
 192       // Find the next unvisited child node.
 193       for (unsigned i = 0; i != N; ++i)
 194         if (Children.count(i)) {
 195           // Remove that child - it has been visited.  This is the increment!
 196           Children.DeleteNode(i);
 197           return *this;
 198         }
 199       assert(false && "Incrementing end iterator!");
 200       return *this; // Avoid compiler warnings.
 201     }
 202
 203     /// Postfix increment operator.
 204     ChildIterator operator++(int) {
 205       ChildIterator Result(*this);
 206       ++(*this);
 207       return Result;
 208     }
 209
 210     /// Dereference operator.
 211     NodeType *operator*() {
 212       // Find the next unvisited child node.
 213       for (unsigned i = 0; i != N; ++i)
 214         if (Children.count(i))
 215           // Return a pointer to it.
 216           return FirstNode + i;
 217       assert(false && "Dereferencing end iterator!");
 218       return nullptr; // Avoid compiler warning.
 219     }
 220   };
 221
 222   /// child_begin - Return an iterator pointing to the first child of the given
 223   /// node.
 224   static ChildIterator child_begin(NodeType *Parent) {
 225     return ChildIterator(Parent - Parent->first, Parent->second);
 226   }
 227
 228   /// child_end - Return the end iterator for children of the given node.
 229   static ChildIterator child_end(NodeType *Parent) {
 230     return ChildIterator(Parent - Parent->first, NodeSubset());
 231   }
 232 };
 233
 234 template <unsigned N>
 235 struct GraphTraits<Graph<N> > {
 236   typedef typename Graph<N>::NodeType *NodeRef;
 237   typedef typename Graph<N>::ChildIterator ChildIteratorType;
 238
 239   static NodeRef getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
 240   static ChildIteratorType child_begin(NodeRef Node) {
 241     return Graph<N>::child_begin(Node);
 242   }
 243   static ChildIteratorType child_end(NodeRef Node) {
 244     return Graph<N>::child_end(Node);
 245   }
 246 };
 247
 248 } // End namespace llvm
 249
 250 #endif