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
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 // 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 }
34public:
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
102private:
103 /// Nodes - The list of nodes for this graph.
104 NodeType Nodes[N];
105public:
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(Idx: 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(Idx: 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) = 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 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
234template <unsigned N>
235struct 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
251

source code of llvm/unittests/ADT/TestGraph.h