251 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// Common graph data structure for testing.10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_UNITTESTS_ADT_TEST_GRAPH_H14#define LLVM_UNITTESTS_ADT_TEST_GRAPH_H15 16#include "llvm/ADT/GraphTraits.h"17#include <cassert>18#include <climits>19#include <utility>20 21namespace llvm {22 23/// Graph<N> - A graph with N nodes. Note that N can be at most 8.24template <unsigned N>25class Graph {26private:27 static void ValidateIndex(unsigned Idx) {28 assert(Idx < N && "Invalid node index!");29 }30public:31 // Disable copying.32 Graph(const Graph &) = delete;33 Graph &operator=(const Graph &) = delete;34 35 /// NodeSubset - A subset of the graph's nodes.36 class NodeSubset {37 using BitVector = unsigned char; // Where the limitation N <= 8 comes from.38 BitVector Elements;39 NodeSubset(BitVector e) : Elements(e) {}40 public:41 /// NodeSubset - Default constructor, creates an empty subset.42 NodeSubset() : Elements(0) {43 assert(N <= sizeof(BitVector)*CHAR_BIT && "Graph too big!");44 }45 46 /// Comparison operators.47 bool operator==(const NodeSubset &other) const {48 return other.Elements == this->Elements;49 }50 bool operator!=(const NodeSubset &other) const {51 return !(*this == other);52 }53 54 /// AddNode - Add the node with the given index to the subset.55 void AddNode(unsigned Idx) {56 ValidateIndex(Idx);57 Elements |= 1U << Idx;58 }59 60 /// DeleteNode - Remove the node with the given index from the subset.61 void DeleteNode(unsigned Idx) {62 ValidateIndex(Idx);63 Elements &= ~(1U << Idx);64 }65 66 /// count - Return true if the node with the given index is in the subset.67 bool count(unsigned Idx) {68 ValidateIndex(Idx);69 return (Elements & (1U << Idx)) != 0;70 }71 72 /// isEmpty - Return true if this is the empty set.73 bool isEmpty() const {74 return Elements == 0;75 }76 77 /// isSubsetOf - Return true if this set is a subset of the given one.78 bool isSubsetOf(const NodeSubset &other) const {79 return (this->Elements | other.Elements) == other.Elements;80 }81 82 /// Complement - Return the complement of this subset.83 NodeSubset Complement() const {84 return ~(unsigned)this->Elements & ((1U << N) - 1);85 }86 87 /// Join - Return the union of this subset and the given one.88 NodeSubset Join(const NodeSubset &other) const {89 return this->Elements | other.Elements;90 }91 92 /// Meet - Return the intersection of this subset and the given one.93 NodeSubset Meet(const NodeSubset &other) const {94 return this->Elements & other.Elements;95 }96 };97 98 /// NodeType - Node index and set of children of the node.99 using NodeType = std::pair<unsigned, NodeSubset>;100 101private:102 /// Nodes - The list of nodes for this graph.103 NodeType Nodes[N];104public:105 106 /// Graph - Default constructor. Creates an empty graph.107 Graph() {108 // Let each node know which node it is. This allows us to find the start of109 // the Nodes array given a pointer to any element of it.110 for (unsigned i = 0; i != N; ++i)111 Nodes[i].first = i;112 }113 114 /// AddEdge - Add an edge from the node with index FromIdx to the node with115 /// index ToIdx.116 void AddEdge(unsigned FromIdx, unsigned ToIdx) {117 ValidateIndex(FromIdx);118 Nodes[FromIdx].second.AddNode(ToIdx);119 }120 121 /// DeleteEdge - Remove the edge (if any) from the node with index FromIdx to122 /// the node with index ToIdx.123 void DeleteEdge(unsigned FromIdx, unsigned ToIdx) {124 ValidateIndex(FromIdx);125 Nodes[FromIdx].second.DeleteNode(ToIdx);126 }127 128 /// AccessNode - Get a pointer to the node with the given index.129 NodeType *AccessNode(unsigned Idx) const {130 ValidateIndex(Idx);131 // The constant cast is needed when working with GraphTraits, which insists132 // on taking a constant Graph.133 return const_cast<NodeType *>(&Nodes[Idx]);134 }135 136 /// NodesReachableFrom - Return the set of all nodes reachable from the given137 /// node.138 NodeSubset NodesReachableFrom(unsigned Idx) const {139 // This algorithm doesn't scale, but that doesn't matter given the small140 // size of our graphs.141 NodeSubset Reachable;142 143 // The initial node is reachable.144 Reachable.AddNode(Idx);145 do {146 NodeSubset Previous(Reachable);147 148 // Add in all nodes which are children of a reachable node.149 for (unsigned i = 0; i != N; ++i)150 if (Previous.count(i))151 Reachable = Reachable.Join(Nodes[i].second);152 153 // If nothing changed then we have found all reachable nodes.154 if (Reachable == Previous)155 return Reachable;156 157 // Rinse and repeat.158 } while (1);159 }160 161 /// ChildIterator - Visit all children of a node.162 class ChildIterator {163 friend class Graph;164 165 /// FirstNode - Pointer to first node in the graph's Nodes array.166 NodeType *FirstNode;167 /// Children - Set of nodes which are children of this one and that haven't168 /// yet been visited.169 NodeSubset Children;170 171 protected:172 ChildIterator(NodeType *F, NodeSubset C) : FirstNode(F), Children(C) {}173 174 public:175 ChildIterator() = delete; // Disable default constructor.176 177 /// ChildIterator - Copy constructor.178 ChildIterator(const ChildIterator &other) = default;179 ChildIterator &operator=(const ChildIterator &other) = default;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 given223 /// 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 234template <unsigned N>235struct GraphTraits<Graph<N> > {236 using NodeRef = typename Graph<N>::NodeType *;237 using ChildIteratorType = typename Graph<N>::ChildIterator;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 llvm249 250#endif251