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(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 | |
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 |
251 | |