Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef gc_FindSCCs_h
8 : #define gc_FindSCCs_h
9 :
10 : #include "mozilla/Move.h"
11 :
12 : #include "jsfriendapi.h"
13 : #include "jsutil.h"
14 :
15 : namespace js {
16 : namespace gc {
17 :
18 : template<class Node>
19 : struct GraphNodeBase
20 : {
21 : Node* gcNextGraphNode;
22 : Node* gcNextGraphComponent;
23 : unsigned gcDiscoveryTime;
24 : unsigned gcLowLink;
25 :
26 31 : GraphNodeBase()
27 : : gcNextGraphNode(nullptr),
28 : gcNextGraphComponent(nullptr),
29 : gcDiscoveryTime(0),
30 31 : gcLowLink(0) {}
31 :
32 0 : ~GraphNodeBase() {}
33 :
34 0 : Node* nextNodeInGroup() const {
35 0 : if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent)
36 0 : return gcNextGraphNode;
37 0 : return nullptr;
38 : }
39 :
40 0 : Node* nextGroup() const {
41 0 : return gcNextGraphComponent;
42 : }
43 : };
44 :
45 : /*
46 : * Find the strongly connected components of a graph using Tarjan's algorithm,
47 : * and return them in topological order.
48 : *
49 : * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls
50 : * finder.addEdgeTo to describe the outgoing edges from that node:
51 : *
52 : * struct MyComponentFinder;
53 : *
54 : * struct MyGraphNode : public GraphNodeBase
55 : * {
56 : * void findOutgoingEdges(MyComponentFinder& finder)
57 : * {
58 : * for edge in my_outgoing_edges:
59 : * if is_relevant(edge):
60 : * finder.addEdgeTo(edge.destination)
61 : * }
62 : * }
63 : *
64 : * struct MyComponentFinder : public ComponentFinder<MyGraphNode, MyComponentFinder>
65 : * {
66 : * ...
67 : * };
68 : *
69 : * MyComponentFinder finder;
70 : * finder.addNode(v);
71 : */
72 :
73 : template <typename Node, typename Derived>
74 : class ComponentFinder
75 : {
76 : public:
77 0 : explicit ComponentFinder(uintptr_t sl)
78 : : clock(1),
79 : stack(nullptr),
80 : firstComponent(nullptr),
81 : cur(nullptr),
82 : stackLimit(sl),
83 0 : stackFull(false)
84 0 : {}
85 :
86 0 : ~ComponentFinder() {
87 0 : MOZ_ASSERT(!stack);
88 0 : MOZ_ASSERT(!firstComponent);
89 0 : }
90 :
91 : /* Forces all nodes to be added to a single component. */
92 0 : void useOneComponent() { stackFull = true; }
93 :
94 0 : void addNode(Node* v) {
95 0 : if (v->gcDiscoveryTime == Undefined) {
96 0 : MOZ_ASSERT(v->gcLowLink == Undefined);
97 0 : processNode(v);
98 : }
99 0 : }
100 :
101 0 : Node* getResultsList() {
102 0 : if (stackFull) {
103 : /*
104 : * All nodes after the stack overflow are in |stack|. Put them all in
105 : * one big component of their own.
106 : */
107 0 : Node* firstGoodComponent = firstComponent;
108 0 : for (Node* v = stack; v; v = stack) {
109 0 : stack = v->gcNextGraphNode;
110 0 : v->gcNextGraphComponent = firstGoodComponent;
111 0 : v->gcNextGraphNode = firstComponent;
112 0 : firstComponent = v;
113 : }
114 0 : stackFull = false;
115 : }
116 :
117 0 : MOZ_ASSERT(!stack);
118 :
119 0 : Node* result = firstComponent;
120 0 : firstComponent = nullptr;
121 :
122 0 : for (Node* v = result; v; v = v->gcNextGraphNode) {
123 0 : v->gcDiscoveryTime = Undefined;
124 0 : v->gcLowLink = Undefined;
125 : }
126 :
127 0 : return result;
128 : }
129 :
130 0 : static void mergeGroups(Node* first) {
131 0 : for (Node* v = first; v; v = v->gcNextGraphNode)
132 0 : v->gcNextGraphComponent = nullptr;
133 0 : }
134 :
135 : public:
136 : /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */
137 0 : void addEdgeTo(Node* w) {
138 0 : if (w->gcDiscoveryTime == Undefined) {
139 0 : processNode(w);
140 0 : cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink);
141 0 : } else if (w->gcDiscoveryTime != Finished) {
142 0 : cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime);
143 : }
144 0 : }
145 :
146 : private:
147 : /* Constant used to indicate an unprocessed vertex. */
148 : static const unsigned Undefined = 0;
149 :
150 : /* Constant used to indicate an processed vertex that is no longer on the stack. */
151 : static const unsigned Finished = (unsigned)-1;
152 :
153 0 : void processNode(Node* v) {
154 0 : v->gcDiscoveryTime = clock;
155 0 : v->gcLowLink = clock;
156 0 : ++clock;
157 :
158 0 : v->gcNextGraphNode = stack;
159 0 : stack = v;
160 :
161 : int stackDummy;
162 0 : if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) {
163 0 : stackFull = true;
164 0 : return;
165 : }
166 :
167 0 : Node* old = cur;
168 0 : cur = v;
169 0 : cur->findOutgoingEdges(*static_cast<Derived*>(this));
170 0 : cur = old;
171 :
172 0 : if (stackFull)
173 0 : return;
174 :
175 0 : if (v->gcLowLink == v->gcDiscoveryTime) {
176 0 : Node* nextComponent = firstComponent;
177 : Node* w;
178 0 : do {
179 0 : MOZ_ASSERT(stack);
180 0 : w = stack;
181 0 : stack = w->gcNextGraphNode;
182 :
183 : /*
184 : * Record that the element is no longer on the stack by setting the
185 : * discovery time to a special value that's not Undefined.
186 : */
187 0 : w->gcDiscoveryTime = Finished;
188 :
189 : /* Figure out which group we're in. */
190 0 : w->gcNextGraphComponent = nextComponent;
191 :
192 : /*
193 : * Prepend the component to the beginning of the output list to
194 : * reverse the list and achieve the desired order.
195 : */
196 0 : w->gcNextGraphNode = firstComponent;
197 0 : firstComponent = w;
198 0 : } while (w != v);
199 : }
200 : }
201 :
202 : private:
203 : unsigned clock;
204 : Node* stack;
205 : Node* firstComponent;
206 : Node* cur;
207 : uintptr_t stackLimit;
208 : bool stackFull;
209 : };
210 :
211 : } /* namespace gc */
212 : } /* namespace js */
213 :
214 : #endif /* gc_FindSCCs_h */
|
