1/*
2 * Copyright (C) 2015-2016 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/HashSet.h>
29
30namespace WTF {
31
32template<typename Node, typename Set = HashSet<Node>>
33class GraphNodeWorklist {
34public:
35 GraphNodeWorklist() { }
36 ~GraphNodeWorklist() { }
37
38 // Returns true if we didn't know about the node before.
39 bool push(Node node)
40 {
41 if (!m_seen.add(node))
42 return false;
43 m_stack.append(node);
44 return true;
45 }
46
47 template<typename Iterable>
48 void pushAll(const Iterable& iterable)
49 {
50 for (Node node : iterable)
51 push(node);
52 }
53
54 bool isEmpty() const { return m_stack.isEmpty(); }
55 bool notEmpty() const { return !m_stack.isEmpty(); }
56
57 Node pop()
58 {
59 if (m_stack.isEmpty())
60 return Node();
61 return m_stack.takeLast();
62 }
63
64 bool saw(Node node) { return m_seen.contains(node); }
65
66 const Set& seen() const { return m_seen; }
67
68private:
69 Set m_seen;
70 Vector<Node, 16> m_stack;
71};
72
73template<typename Node, typename T>
74struct GraphNodeWith {
75 GraphNodeWith()
76 : node()
77 , data()
78 {
79 }
80
81 GraphNodeWith(Node node, const T& data)
82 : node(node)
83 , data(data)
84 {
85 }
86
87 explicit operator bool() const { return !!node; }
88
89 Node node;
90 T data;
91};
92
93template<typename Node, typename T, typename Set = HashSet<Node>>
94class ExtendedGraphNodeWorklist {
95public:
96 ExtendedGraphNodeWorklist() { }
97
98 void forcePush(const GraphNodeWith<Node, T>& entry)
99 {
100 m_stack.append(entry);
101 }
102
103 void forcePush(Node node, const T& data)
104 {
105 forcePush(GraphNodeWith<Node, T>(node, data));
106 }
107
108 bool push(const GraphNodeWith<Node, T>& entry)
109 {
110 if (!m_seen.add(entry.node))
111 return false;
112
113 forcePush(entry);
114 return true;
115 }
116
117 bool push(Node node, const T& data)
118 {
119 return push(GraphNodeWith<Node, T>(node, data));
120 }
121
122 bool notEmpty() const { return !m_stack.isEmpty(); }
123
124 GraphNodeWith<Node, T> pop()
125 {
126 if (m_stack.isEmpty())
127 return GraphNodeWith<Node, T>();
128
129 return m_stack.takeLast();
130 }
131
132private:
133 Set m_seen;
134 Vector<GraphNodeWith<Node, T>> m_stack;
135};
136
137enum class GraphVisitOrder : uint8_t {
138 Pre,
139 Post
140};
141
142template<typename Node>
143struct GraphNodeWithOrder {
144 GraphNodeWithOrder()
145 : node()
146 , order(GraphVisitOrder::Pre)
147 {
148 }
149
150 GraphNodeWithOrder(Node node, GraphVisitOrder order)
151 : node(node)
152 , order(order)
153 {
154 }
155
156 explicit operator bool() const { return node; }
157
158 Node node;
159 GraphVisitOrder order;
160};
161
162template<typename Node, typename Set = HashSet<Node>>
163class PostOrderGraphNodeWorklist {
164public:
165 PostOrderGraphNodeWorklist()
166 {
167 }
168
169 ~PostOrderGraphNodeWorklist()
170 {
171 }
172
173 bool pushPre(Node node)
174 {
175 return m_worklist.push(node, GraphVisitOrder::Pre);
176 }
177
178 void pushPost(Node node)
179 {
180 m_worklist.forcePush(node, GraphVisitOrder::Post);
181 }
182
183 bool push(Node node, GraphVisitOrder order = GraphVisitOrder::Pre)
184 {
185 switch (order) {
186 case GraphVisitOrder::Pre:
187 return pushPre(node);
188 case GraphVisitOrder::Post:
189 pushPost(node);
190 return true;
191 }
192 RELEASE_ASSERT_NOT_REACHED();
193 return false;
194 }
195 bool push(const GraphNodeWithOrder<Node>& data)
196 {
197 return push(data.node, data.order);
198 }
199
200 bool notEmpty() const { return m_worklist.notEmpty(); }
201
202 GraphNodeWithOrder<Node> pop()
203 {
204 GraphNodeWith<Node, GraphVisitOrder> result = m_worklist.pop();
205 return GraphNodeWithOrder<Node>(result.node, result.data);
206 }
207
208private:
209 ExtendedGraphNodeWorklist<Node, GraphVisitOrder, Set> m_worklist;
210};
211
212} // namespace WTF
213
214using WTF::GraphNodeWorklist;
215using WTF::GraphNodeWith;
216using WTF::ExtendedGraphNodeWorklist;
217using WTF::GraphVisitOrder;
218using WTF::GraphNodeWithOrder;
219using WTF::PostOrderGraphNodeWorklist;
220