diff options
Diffstat (limited to 'js/src/gc/FindSCCs.h')
| -rw-r--r-- | js/src/gc/FindSCCs.h | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/js/src/gc/FindSCCs.h b/js/src/gc/FindSCCs.h new file mode 100644 index 000000000..037557e3e --- /dev/null +++ b/js/src/gc/FindSCCs.h @@ -0,0 +1,214 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef gc_FindSCCs_h +#define gc_FindSCCs_h + +#include "mozilla/Move.h" + +#include "jsfriendapi.h" +#include "jsutil.h" + +namespace js { +namespace gc { + +template<class Node> +struct GraphNodeBase +{ + Node* gcNextGraphNode; + Node* gcNextGraphComponent; + unsigned gcDiscoveryTime; + unsigned gcLowLink; + + GraphNodeBase() + : gcNextGraphNode(nullptr), + gcNextGraphComponent(nullptr), + gcDiscoveryTime(0), + gcLowLink(0) {} + + ~GraphNodeBase() {} + + Node* nextNodeInGroup() const { + if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent) + return gcNextGraphNode; + return nullptr; + } + + Node* nextGroup() const { + return gcNextGraphComponent; + } +}; + +/* + * Find the strongly connected components of a graph using Tarjan's algorithm, + * and return them in topological order. + * + * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls + * finder.addEdgeTo to describe the outgoing edges from that node: + * + * struct MyComponentFinder; + * + * struct MyGraphNode : public GraphNodeBase + * { + * void findOutgoingEdges(MyComponentFinder& finder) + * { + * for edge in my_outgoing_edges: + * if is_relevant(edge): + * finder.addEdgeTo(edge.destination) + * } + * } + * + * struct MyComponentFinder : public ComponentFinder<MyGraphNode, MyComponentFinder> + * { + * ... + * }; + * + * MyComponentFinder finder; + * finder.addNode(v); + */ + +template <typename Node, typename Derived> +class ComponentFinder +{ + public: + explicit ComponentFinder(uintptr_t sl) + : clock(1), + stack(nullptr), + firstComponent(nullptr), + cur(nullptr), + stackLimit(sl), + stackFull(false) + {} + + ~ComponentFinder() { + MOZ_ASSERT(!stack); + MOZ_ASSERT(!firstComponent); + } + + /* Forces all nodes to be added to a single component. */ + void useOneComponent() { stackFull = true; } + + void addNode(Node* v) { + if (v->gcDiscoveryTime == Undefined) { + MOZ_ASSERT(v->gcLowLink == Undefined); + processNode(v); + } + } + + Node* getResultsList() { + if (stackFull) { + /* + * All nodes after the stack overflow are in |stack|. Put them all in + * one big component of their own. + */ + Node* firstGoodComponent = firstComponent; + for (Node* v = stack; v; v = stack) { + stack = v->gcNextGraphNode; + v->gcNextGraphComponent = firstGoodComponent; + v->gcNextGraphNode = firstComponent; + firstComponent = v; + } + stackFull = false; + } + + MOZ_ASSERT(!stack); + + Node* result = firstComponent; + firstComponent = nullptr; + + for (Node* v = result; v; v = v->gcNextGraphNode) { + v->gcDiscoveryTime = Undefined; + v->gcLowLink = Undefined; + } + + return result; + } + + static void mergeGroups(Node* first) { + for (Node* v = first; v; v = v->gcNextGraphNode) + v->gcNextGraphComponent = nullptr; + } + + public: + /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */ + void addEdgeTo(Node* w) { + if (w->gcDiscoveryTime == Undefined) { + processNode(w); + cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink); + } else if (w->gcDiscoveryTime != Finished) { + cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime); + } + } + + private: + /* Constant used to indicate an unprocessed vertex. */ + static const unsigned Undefined = 0; + + /* Constant used to indicate an processed vertex that is no longer on the stack. */ + static const unsigned Finished = (unsigned)-1; + + void processNode(Node* v) { + v->gcDiscoveryTime = clock; + v->gcLowLink = clock; + ++clock; + + v->gcNextGraphNode = stack; + stack = v; + + int stackDummy; + if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) { + stackFull = true; + return; + } + + Node* old = cur; + cur = v; + cur->findOutgoingEdges(*static_cast<Derived*>(this)); + cur = old; + + if (stackFull) + return; + + if (v->gcLowLink == v->gcDiscoveryTime) { + Node* nextComponent = firstComponent; + Node* w; + do { + MOZ_ASSERT(stack); + w = stack; + stack = w->gcNextGraphNode; + + /* + * Record that the element is no longer on the stack by setting the + * discovery time to a special value that's not Undefined. + */ + w->gcDiscoveryTime = Finished; + + /* Figure out which group we're in. */ + w->gcNextGraphComponent = nextComponent; + + /* + * Prepend the component to the beginning of the output list to + * reverse the list and achieve the desired order. + */ + w->gcNextGraphNode = firstComponent; + firstComponent = w; + } while (w != v); + } + } + + private: + unsigned clock; + Node* stack; + Node* firstComponent; + Node* cur; + uintptr_t stackLimit; + bool stackFull; +}; + +} /* namespace gc */ +} /* namespace js */ + +#endif /* gc_FindSCCs_h */ |