unittests/ADT/TestGraph.h

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