js/src/gc/FindSCCs.h@129ffea94266
js/src/gc/FindSCCs.h
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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/. */
7 #ifndef gc_FindSCCs_h
8 #define gc_FindSCCs_h
10 #include "jsfriendapi.h"
11 #include "jsutil.h"
13 namespace js {
14 namespace gc {
16 template<class Node>
17 struct GraphNodeBase
18 {
19 Node *gcNextGraphNode;
20 Node *gcNextGraphComponent;
21 unsigned gcDiscoveryTime;
22 unsigned gcLowLink;
24 GraphNodeBase()
25 : gcNextGraphNode(nullptr),
26 gcNextGraphComponent(nullptr),
27 gcDiscoveryTime(0),
28 gcLowLink(0) {}
30 ~GraphNodeBase() {}
32 Node *nextNodeInGroup() const {
33 if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent)
34 return gcNextGraphNode;
35 return nullptr;
36 }
38 Node *nextGroup() const {
39 return gcNextGraphComponent;
40 }
41 };
43 /*
44 * Find the strongly connected components of a graph using Tarjan's algorithm,
45 * and return them in topological order.
46 *
47 * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls
48 * finder.addEdgeTo to describe the outgoing edges from that node:
49 *
50 * struct MyGraphNode : public GraphNodeBase
51 * {
52 * void findOutgoingEdges(ComponentFinder<MyGraphNode> &finder)
53 * {
54 * for edge in my_outgoing_edges:
55 * if is_relevant(edge):
56 * finder.addEdgeTo(edge.destination)
57 * }
58 * }
59 *
60 * ComponentFinder<MyGraphNode> finder;
61 * finder.addNode(v);
62 */
63 template<class Node>
64 class ComponentFinder
65 {
66 public:
67 ComponentFinder(uintptr_t sl)
68 : clock(1),
69 stack(nullptr),
70 firstComponent(nullptr),
71 cur(nullptr),
72 stackLimit(sl),
73 stackFull(false)
74 {}
76 ~ComponentFinder() {
77 JS_ASSERT(!stack);
78 JS_ASSERT(!firstComponent);
79 }
81 /* Forces all nodes to be added to a single component. */
82 void useOneComponent() { stackFull = true; }
84 void addNode(Node *v) {
85 if (v->gcDiscoveryTime == Undefined) {
86 JS_ASSERT(v->gcLowLink == Undefined);
87 processNode(v);
88 }
89 }
91 Node *getResultsList() {
92 if (stackFull) {
93 /*
94 * All nodes after the stack overflow are in |stack|. Put them all in
95 * one big component of their own.
96 */
97 Node *firstGoodComponent = firstComponent;
98 for (Node *v = stack; v; v = stack) {
99 stack = v->gcNextGraphNode;
100 v->gcNextGraphComponent = firstGoodComponent;
101 v->gcNextGraphNode = firstComponent;
102 firstComponent = v;
103 }
104 stackFull = false;
105 }
107 JS_ASSERT(!stack);
109 Node *result = firstComponent;
110 firstComponent = nullptr;
112 for (Node *v = result; v; v = v->gcNextGraphNode) {
113 v->gcDiscoveryTime = Undefined;
114 v->gcLowLink = Undefined;
115 }
117 return result;
118 }
120 static void mergeGroups(Node *first) {
121 for (Node *v = first; v; v = v->gcNextGraphNode)
122 v->gcNextGraphComponent = nullptr;
123 }
125 public:
126 /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */
127 void addEdgeTo(Node *w) {
128 if (w->gcDiscoveryTime == Undefined) {
129 processNode(w);
130 cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink);
131 } else if (w->gcDiscoveryTime != Finished) {
132 cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime);
133 }
134 }
136 private:
137 /* Constant used to indicate an unprocessed vertex. */
138 static const unsigned Undefined = 0;
140 /* Constant used to indicate an processed vertex that is no longer on the stack. */
141 static const unsigned Finished = (unsigned)-1;
143 void processNode(Node *v) {
144 v->gcDiscoveryTime = clock;
145 v->gcLowLink = clock;
146 ++clock;
148 v->gcNextGraphNode = stack;
149 stack = v;
151 int stackDummy;
152 if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) {
153 stackFull = true;
154 return;
155 }
157 Node *old = cur;
158 cur = v;
159 cur->findOutgoingEdges(*this);
160 cur = old;
162 if (stackFull)
163 return;
165 if (v->gcLowLink == v->gcDiscoveryTime) {
166 Node *nextComponent = firstComponent;
167 Node *w;
168 do {
169 JS_ASSERT(stack);
170 w = stack;
171 stack = w->gcNextGraphNode;
173 /*
174 * Record that the element is no longer on the stack by setting the
175 * discovery time to a special value that's not Undefined.
176 */
177 w->gcDiscoveryTime = Finished;
179 /* Figure out which group we're in. */
180 w->gcNextGraphComponent = nextComponent;
182 /*
183 * Prepend the component to the beginning of the output list to
184 * reverse the list and achieve the desired order.
185 */
186 w->gcNextGraphNode = firstComponent;
187 firstComponent = w;
188 } while (w != v);
189 }
190 }
192 private:
193 unsigned clock;
194 Node *stack;
195 Node *firstComponent;
196 Node *cur;
197 uintptr_t stackLimit;
198 bool stackFull;
199 };
201 } /* namespace gc */
202 } /* namespace js */
204 #endif /* gc_FindSCCs_h */
