| /* -*- 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 "jsutil.h" |
| |
| namespace js { |
| namespace gc { |
| |
| template<class Node> |
| struct GraphNodeBase |
| { |
| Node *gcNextGraphNode; |
| Node *gcNextGraphComponent; |
| unsigned gcDiscoveryTime; |
| unsigned gcLowLink; |
| |
| GraphNodeBase() |
| : gcNextGraphNode(NULL), |
| gcNextGraphComponent(NULL), |
| gcDiscoveryTime(0), |
| gcLowLink(0) {} |
| |
| ~GraphNodeBase() {} |
| |
| Node *nextNodeInGroup() const { |
| if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent) |
| return gcNextGraphNode; |
| return NULL; |
| } |
| |
| 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 MyGraphNode : public GraphNodeBase |
| * { |
| * void findOutgoingEdges(ComponentFinder<MyGraphNode> &finder) |
| * { |
| * for edge in my_outgoing_edges: |
| * if is_relevant(edge): |
| * finder.addEdgeTo(edge.destination) |
| * } |
| * } |
| * |
| * ComponentFinder<MyGraphNode> finder; |
| * finder.addNode(v); |
| */ |
| template<class Node> |
| class ComponentFinder |
| { |
| public: |
| ComponentFinder(uintptr_t stackLimit); |
| ~ComponentFinder(); |
| |
| /* Forces all nodes to be added to a single component. */ |
| void useOneComponent() { stackFull = true; } |
| |
| void addNode(Node *v); |
| Node *getResultsList(); |
| |
| static void mergeGroups(Node *first); |
| |
| public: |
| /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */ |
| void addEdgeTo(Node *w); |
| |
| 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); |
| |
| private: |
| unsigned clock; |
| Node *stack; |
| Node *firstComponent; |
| Node *cur; |
| uintptr_t stackLimit; |
| bool stackFull; |
| }; |
| |
| } /* namespace gc */ |
| } /* namespace js */ |
| |
| #endif /* gc_FindSCCs_h */ |