1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/FastMalloc.h>
29#include <wtf/GraphNodeWorklist.h>
30#include <wtf/Noncopyable.h>
31#include <wtf/StdLibExtras.h>
32
33namespace WTF {
34
35template <typename Graph>
36class SingleRootGraphNode {
37public:
38 // We use "#root" to refer to the synthetic root we have created.
39 static const char* rootName() { return "#root"; };
40
41 SingleRootGraphNode(typename Graph::Node node = typename Graph::Node())
42 : m_node(node)
43 {
44 }
45
46 static SingleRootGraphNode root()
47 {
48 SingleRootGraphNode result;
49 result.m_node = 0;
50 result.m_isRoot = true;
51 return result;
52 }
53
54 bool operator==(const SingleRootGraphNode& other) const
55 {
56 return m_node == other.m_node
57 && m_isRoot == other.m_isRoot;
58 }
59
60 bool operator!=(const SingleRootGraphNode& other) const
61 {
62 return !(*this == other);
63 }
64
65 explicit operator bool() const { return *this != SingleRootGraphNode(); }
66
67 bool isRoot() const
68 {
69 return m_isRoot;
70 }
71
72 typename Graph::Node node() const
73 {
74 ASSERT(!m_isRoot);
75 return m_node;
76 }
77
78private:
79 typename Graph::Node m_node;
80 bool m_isRoot { false };
81};
82
83template <typename Graph>
84class SingleRootGraphSet {
85 using Node = SingleRootGraphNode<Graph>;
86public:
87 SingleRootGraphSet() = default;
88
89 bool add(const Node& node)
90 {
91 if (node.isRoot())
92 return checkAndSet(m_hasRoot, true);
93 return m_set.add(node.node());
94 }
95
96 bool remove(const Node& node)
97 {
98 if (node.isRoot())
99 return checkAndSet(m_hasRoot, false);
100 return m_set.remove(node.node());
101 }
102
103 bool contains(const Node& node)
104 {
105 if (node.isRoot())
106 return m_hasRoot;
107 return m_set.contains(node.node());
108 }
109
110 void dump(PrintStream& out) const
111 {
112 if (m_hasRoot)
113 out.print(Node::rootName(), " ");
114 out.print(m_set);
115 }
116
117private:
118 typename Graph::Set m_set;
119 bool m_hasRoot { false };
120};
121
122template<typename T, typename Graph>
123class SingleRootMap {
124 using Node = SingleRootGraphNode<Graph>;
125public:
126 SingleRootMap(Graph& graph)
127 : m_map(graph.template newMap<T>())
128 {
129 }
130
131 SingleRootMap(SingleRootMap&& other)
132 : m_map(WTFMove(other.m_map))
133 , m_root(WTFMove(other.m_root))
134 {
135 }
136
137 void clear()
138 {
139 m_map.clear();
140 m_root = T();
141 }
142
143 size_t size() const { return m_map.size() + 1; }
144
145 T& operator[](size_t index)
146 {
147 if (!index)
148 return m_root;
149 return m_map[index - 1];
150 }
151
152 const T& operator[](size_t index) const
153 {
154 return (*const_cast<SingleRootMap*>(this))[index];
155 }
156
157 T& operator[](const Node& node)
158 {
159 if (node.isRoot())
160 return m_root;
161 return m_map[node.node()];
162 }
163
164 const T& operator[](const Node& node) const
165 {
166 return (*const_cast<SingleRootMap*>(this))[node];
167 }
168
169private:
170 typename Graph::template Map<T> m_map;
171 T m_root;
172};
173
174template<typename Graph>
175class SingleRootGraph {
176 WTF_MAKE_NONCOPYABLE(SingleRootGraph);
177 WTF_MAKE_FAST_ALLOCATED;
178public:
179
180 using Node = SingleRootGraphNode<Graph>;
181 using Set = SingleRootGraphSet<Graph>;
182 template <typename T> using Map = SingleRootMap<T, Graph>;
183 using List = Vector<Node, 4>;
184
185 SingleRootGraph(Graph& graph)
186 : m_graph(graph)
187 {
188 for (typename Graph::Node realRoot : m_graph.roots()) {
189 ASSERT(m_graph.predecessors(realRoot).isEmpty());
190 m_rootSuccessorList.append(realRoot);
191 m_rootSuccessorSet.add(realRoot);
192 }
193 ASSERT(m_rootSuccessorList.size());
194 }
195
196 Node root() const { return Node::root(); }
197
198 template<typename T>
199 Map<T> newMap() { return Map<T>(m_graph); }
200
201 List successors(const Node& node) const
202 {
203 assertIsConsistent();
204
205 if (node.isRoot())
206 return m_rootSuccessorList;
207 List result;
208 for (typename Graph::Node successor : m_graph.successors(node.node()))
209 result.append(successor);
210 return result;
211 }
212
213 List predecessors(const Node& node) const
214 {
215 assertIsConsistent();
216
217 if (node.isRoot())
218 return List { };
219
220 if (m_rootSuccessorSet.contains(node.node())) {
221 ASSERT(m_graph.predecessors(node.node()).isEmpty());
222 return List { root() };
223 }
224
225 List result;
226 for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
227 result.append(predecessor);
228 return result;
229 }
230
231 unsigned index(const Node& node) const
232 {
233 if (node.isRoot())
234 return 0;
235 return m_graph.index(node.node()) + 1;
236 }
237
238 Node node(unsigned index) const
239 {
240 if (!index)
241 return root();
242 return m_graph.node(index - 1);
243 }
244
245 unsigned numNodes() const
246 {
247 return m_graph.numNodes() + 1;
248 }
249
250 CString dump(Node node) const
251 {
252 StringPrintStream out;
253 if (!node)
254 out.print("<null>");
255 else if (node.isRoot())
256 out.print(Node::rootName());
257 else
258 out.print(m_graph.dump(node.node()));
259 return out.toCString();
260 }
261
262 void dump(PrintStream& out) const
263 {
264 for (unsigned i = 0; i < numNodes(); ++i) {
265 Node node = this->node(i);
266 if (!node)
267 continue;
268 out.print(dump(node), ":\n");
269 out.print(" Preds: ");
270 CommaPrinter comma;
271 for (Node predecessor : predecessors(node))
272 out.print(comma, dump(predecessor));
273 out.print("\n");
274 out.print(" Succs: ");
275 comma = CommaPrinter();
276 for (Node successor : successors(node))
277 out.print(comma, dump(successor));
278 out.print("\n");
279 }
280 }
281
282private:
283 ALWAYS_INLINE void assertIsConsistent() const
284 {
285#if !ASSERT_DISABLED
286 // We expect the roots() function to be idempotent while we're alive so we can cache
287 // the result in the constructor. If a user of this changes the result of its roots()
288 // function, it's expected that the user will create a new instance of this class.
289 List rootSuccessorList;
290 for (typename Graph::Node realRoot : m_graph.roots()) {
291 ASSERT(m_graph.predecessors(realRoot).isEmpty());
292 rootSuccessorList.append(realRoot);
293 }
294 ASSERT(rootSuccessorList.size());
295 ASSERT(rootSuccessorList == m_rootSuccessorList);
296#endif
297 }
298
299 Graph& m_graph;
300 List m_rootSuccessorList;
301 typename Graph::Set m_rootSuccessorSet;
302};
303
304} // namespace WTF
305
306using WTF::SingleRootGraph;
307