1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/gc/FindSCCs.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,204 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef gc_FindSCCs_h
1.11 +#define gc_FindSCCs_h
1.12 +
1.13 +#include "jsfriendapi.h"
1.14 +#include "jsutil.h"
1.15 +
1.16 +namespace js {
1.17 +namespace gc {
1.18 +
1.19 +template<class Node>
1.20 +struct GraphNodeBase
1.21 +{
1.22 + Node *gcNextGraphNode;
1.23 + Node *gcNextGraphComponent;
1.24 + unsigned gcDiscoveryTime;
1.25 + unsigned gcLowLink;
1.26 +
1.27 + GraphNodeBase()
1.28 + : gcNextGraphNode(nullptr),
1.29 + gcNextGraphComponent(nullptr),
1.30 + gcDiscoveryTime(0),
1.31 + gcLowLink(0) {}
1.32 +
1.33 + ~GraphNodeBase() {}
1.34 +
1.35 + Node *nextNodeInGroup() const {
1.36 + if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent)
1.37 + return gcNextGraphNode;
1.38 + return nullptr;
1.39 + }
1.40 +
1.41 + Node *nextGroup() const {
1.42 + return gcNextGraphComponent;
1.43 + }
1.44 +};
1.45 +
1.46 +/*
1.47 + * Find the strongly connected components of a graph using Tarjan's algorithm,
1.48 + * and return them in topological order.
1.49 + *
1.50 + * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls
1.51 + * finder.addEdgeTo to describe the outgoing edges from that node:
1.52 + *
1.53 + * struct MyGraphNode : public GraphNodeBase
1.54 + * {
1.55 + * void findOutgoingEdges(ComponentFinder<MyGraphNode> &finder)
1.56 + * {
1.57 + * for edge in my_outgoing_edges:
1.58 + * if is_relevant(edge):
1.59 + * finder.addEdgeTo(edge.destination)
1.60 + * }
1.61 + * }
1.62 + *
1.63 + * ComponentFinder<MyGraphNode> finder;
1.64 + * finder.addNode(v);
1.65 + */
1.66 +template<class Node>
1.67 +class ComponentFinder
1.68 +{
1.69 + public:
1.70 + ComponentFinder(uintptr_t sl)
1.71 + : clock(1),
1.72 + stack(nullptr),
1.73 + firstComponent(nullptr),
1.74 + cur(nullptr),
1.75 + stackLimit(sl),
1.76 + stackFull(false)
1.77 + {}
1.78 +
1.79 + ~ComponentFinder() {
1.80 + JS_ASSERT(!stack);
1.81 + JS_ASSERT(!firstComponent);
1.82 + }
1.83 +
1.84 + /* Forces all nodes to be added to a single component. */
1.85 + void useOneComponent() { stackFull = true; }
1.86 +
1.87 + void addNode(Node *v) {
1.88 + if (v->gcDiscoveryTime == Undefined) {
1.89 + JS_ASSERT(v->gcLowLink == Undefined);
1.90 + processNode(v);
1.91 + }
1.92 + }
1.93 +
1.94 + Node *getResultsList() {
1.95 + if (stackFull) {
1.96 + /*
1.97 + * All nodes after the stack overflow are in |stack|. Put them all in
1.98 + * one big component of their own.
1.99 + */
1.100 + Node *firstGoodComponent = firstComponent;
1.101 + for (Node *v = stack; v; v = stack) {
1.102 + stack = v->gcNextGraphNode;
1.103 + v->gcNextGraphComponent = firstGoodComponent;
1.104 + v->gcNextGraphNode = firstComponent;
1.105 + firstComponent = v;
1.106 + }
1.107 + stackFull = false;
1.108 + }
1.109 +
1.110 + JS_ASSERT(!stack);
1.111 +
1.112 + Node *result = firstComponent;
1.113 + firstComponent = nullptr;
1.114 +
1.115 + for (Node *v = result; v; v = v->gcNextGraphNode) {
1.116 + v->gcDiscoveryTime = Undefined;
1.117 + v->gcLowLink = Undefined;
1.118 + }
1.119 +
1.120 + return result;
1.121 + }
1.122 +
1.123 + static void mergeGroups(Node *first) {
1.124 + for (Node *v = first; v; v = v->gcNextGraphNode)
1.125 + v->gcNextGraphComponent = nullptr;
1.126 + }
1.127 +
1.128 + public:
1.129 + /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */
1.130 + void addEdgeTo(Node *w) {
1.131 + if (w->gcDiscoveryTime == Undefined) {
1.132 + processNode(w);
1.133 + cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink);
1.134 + } else if (w->gcDiscoveryTime != Finished) {
1.135 + cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime);
1.136 + }
1.137 + }
1.138 +
1.139 + private:
1.140 + /* Constant used to indicate an unprocessed vertex. */
1.141 + static const unsigned Undefined = 0;
1.142 +
1.143 + /* Constant used to indicate an processed vertex that is no longer on the stack. */
1.144 + static const unsigned Finished = (unsigned)-1;
1.145 +
1.146 + void processNode(Node *v) {
1.147 + v->gcDiscoveryTime = clock;
1.148 + v->gcLowLink = clock;
1.149 + ++clock;
1.150 +
1.151 + v->gcNextGraphNode = stack;
1.152 + stack = v;
1.153 +
1.154 + int stackDummy;
1.155 + if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) {
1.156 + stackFull = true;
1.157 + return;
1.158 + }
1.159 +
1.160 + Node *old = cur;
1.161 + cur = v;
1.162 + cur->findOutgoingEdges(*this);
1.163 + cur = old;
1.164 +
1.165 + if (stackFull)
1.166 + return;
1.167 +
1.168 + if (v->gcLowLink == v->gcDiscoveryTime) {
1.169 + Node *nextComponent = firstComponent;
1.170 + Node *w;
1.171 + do {
1.172 + JS_ASSERT(stack);
1.173 + w = stack;
1.174 + stack = w->gcNextGraphNode;
1.175 +
1.176 + /*
1.177 + * Record that the element is no longer on the stack by setting the
1.178 + * discovery time to a special value that's not Undefined.
1.179 + */
1.180 + w->gcDiscoveryTime = Finished;
1.181 +
1.182 + /* Figure out which group we're in. */
1.183 + w->gcNextGraphComponent = nextComponent;
1.184 +
1.185 + /*
1.186 + * Prepend the component to the beginning of the output list to
1.187 + * reverse the list and achieve the desired order.
1.188 + */
1.189 + w->gcNextGraphNode = firstComponent;
1.190 + firstComponent = w;
1.191 + } while (w != v);
1.192 + }
1.193 + }
1.194 +
1.195 + private:
1.196 + unsigned clock;
1.197 + Node *stack;
1.198 + Node *firstComponent;
1.199 + Node *cur;
1.200 + uintptr_t stackLimit;
1.201 + bool stackFull;
1.202 +};
1.203 +
1.204 +} /* namespace gc */
1.205 +} /* namespace js */
1.206 +
1.207 +#endif /* gc_FindSCCs_h */
