The Tor Browser / file comparison
comparison: js/src/gc/FindSCCs.h
js/src/gc/FindSCCs.h
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:0c9e74a939a1 |
|---|---|
| 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 "jsfriendapi.h" | |
| 11 #include "jsutil.h" | |
| 12 | |
| 13 namespace js { | |
| 14 namespace gc { | |
| 15 | |
| 16 template<class Node> | |
| 17 struct GraphNodeBase | |
| 18 { | |
| 19 Node *gcNextGraphNode; | |
| 20 Node *gcNextGraphComponent; | |
| 21 unsigned gcDiscoveryTime; | |
| 22 unsigned gcLowLink; | |
| 23 | |
| 24 GraphNodeBase() | |
| 25 : gcNextGraphNode(nullptr), | |
| 26 gcNextGraphComponent(nullptr), | |
| 27 gcDiscoveryTime(0), | |
| 28 gcLowLink(0) {} | |
| 29 | |
| 30 ~GraphNodeBase() {} | |
| 31 | |
| 32 Node *nextNodeInGroup() const { | |
| 33 if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent) | |
| 34 return gcNextGraphNode; | |
| 35 return nullptr; | |
| 36 } | |
| 37 | |
| 38 Node *nextGroup() const { | |
| 39 return gcNextGraphComponent; | |
| 40 } | |
| 41 }; | |
| 42 | |
| 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 {} | |
| 75 | |
| 76 ~ComponentFinder() { | |
| 77 JS_ASSERT(!stack); | |
| 78 JS_ASSERT(!firstComponent); | |
| 79 } | |
| 80 | |
| 81 /* Forces all nodes to be added to a single component. */ | |
| 82 void useOneComponent() { stackFull = true; } | |
| 83 | |
| 84 void addNode(Node *v) { | |
| 85 if (v->gcDiscoveryTime == Undefined) { | |
| 86 JS_ASSERT(v->gcLowLink == Undefined); | |
| 87 processNode(v); | |
| 88 } | |
| 89 } | |
| 90 | |
| 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 } | |
| 106 | |
| 107 JS_ASSERT(!stack); | |
| 108 | |
| 109 Node *result = firstComponent; | |
| 110 firstComponent = nullptr; | |
| 111 | |
| 112 for (Node *v = result; v; v = v->gcNextGraphNode) { | |
| 113 v->gcDiscoveryTime = Undefined; | |
| 114 v->gcLowLink = Undefined; | |
| 115 } | |
| 116 | |
| 117 return result; | |
| 118 } | |
| 119 | |
| 120 static void mergeGroups(Node *first) { | |
| 121 for (Node *v = first; v; v = v->gcNextGraphNode) | |
| 122 v->gcNextGraphComponent = nullptr; | |
| 123 } | |
| 124 | |
| 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 } | |
| 135 | |
| 136 private: | |
| 137 /* Constant used to indicate an unprocessed vertex. */ | |
| 138 static const unsigned Undefined = 0; | |
| 139 | |
| 140 /* Constant used to indicate an processed vertex that is no longer on the stack. */ | |
| 141 static const unsigned Finished = (unsigned)-1; | |
| 142 | |
| 143 void processNode(Node *v) { | |
| 144 v->gcDiscoveryTime = clock; | |
| 145 v->gcLowLink = clock; | |
| 146 ++clock; | |
| 147 | |
| 148 v->gcNextGraphNode = stack; | |
| 149 stack = v; | |
| 150 | |
| 151 int stackDummy; | |
| 152 if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) { | |
| 153 stackFull = true; | |
| 154 return; | |
| 155 } | |
| 156 | |
| 157 Node *old = cur; | |
| 158 cur = v; | |
| 159 cur->findOutgoingEdges(*this); | |
| 160 cur = old; | |
| 161 | |
| 162 if (stackFull) | |
| 163 return; | |
| 164 | |
| 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; | |
| 172 | |
| 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; | |
| 178 | |
| 179 /* Figure out which group we're in. */ | |
| 180 w->gcNextGraphComponent = nextComponent; | |
| 181 | |
| 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 } | |
| 191 | |
| 192 private: | |
| 193 unsigned clock; | |
| 194 Node *stack; | |
| 195 Node *firstComponent; | |
| 196 Node *cur; | |
| 197 uintptr_t stackLimit; | |
| 198 bool stackFull; | |
| 199 }; | |
| 200 | |
| 201 } /* namespace gc */ | |
| 202 } /* namespace js */ | |
| 203 | |
| 204 #endif /* gc_FindSCCs_h */ |
