Differential D3095 Diff 13993 libraries/source/spidermonkey/include-win32-debug/js/UbiNodeBreadthFirst.h
Changeset View
Changeset View
Standalone View
Standalone View
libraries/source/spidermonkey/include-win32-debug/js/UbiNodeBreadthFirst.h
Show First 20 Lines • Show All 77 Lines • ▼ Show 20 Lines | |||||
struct BreadthFirst { | struct BreadthFirst { | ||||
// Construct a breadth-first traversal object that reports the nodes it | // Construct a breadth-first traversal object that reports the nodes it | ||||
// reaches to |handler|. The traversal asserts that no GC happens in its | // reaches to |handler|. The traversal asserts that no GC happens in its | ||||
// runtime during its lifetime. | // runtime during its lifetime. | ||||
// | // | ||||
// We do nothing with noGC, other than require it to exist, with a lifetime | // We do nothing with noGC, other than require it to exist, with a lifetime | ||||
// that encloses our own. | // that encloses our own. | ||||
BreadthFirst(JSRuntime* rt, Handler& handler, const JS::AutoCheckCannotGC& noGC) | BreadthFirst(JSContext* cx, Handler& handler, const JS::AutoCheckCannotGC& noGC) | ||||
: wantNames(true), rt(rt), visited(), handler(handler), pending(), | : wantNames(true), cx(cx), visited(), handler(handler), pending(), | ||||
traversalBegun(false), stopRequested(false), abandonRequested(false) | traversalBegun(false), stopRequested(false), abandonRequested(false) | ||||
{ } | { } | ||||
// Initialize this traversal object. Return false on OOM. | // Initialize this traversal object. Return false on OOM. | ||||
bool init() { return visited.init(); } | bool init() { return visited.init(); } | ||||
// Add |node| as a starting point for the traversal. You may add | // Add |node| as a starting point for the traversal. You may add | ||||
// as many starting points as you like. Return false on OOM. | // as many starting points as you like. Return false on OOM. | ||||
Show All 25 Lines | bool traverse() | ||||
traversalBegun = true; | traversalBegun = true; | ||||
// While there are pending nodes, visit them. | // While there are pending nodes, visit them. | ||||
while (!pending.empty()) { | while (!pending.empty()) { | ||||
Node origin = pending.front(); | Node origin = pending.front(); | ||||
pending.popFront(); | pending.popFront(); | ||||
// Get a range containing all origin's outgoing edges. | // Get a range containing all origin's outgoing edges. | ||||
auto range = origin.edges(rt, wantNames); | auto range = origin.edges(cx, wantNames); | ||||
if (!range) | if (!range) | ||||
return false; | return false; | ||||
// Traverse each edge. | // Traverse each edge. | ||||
for (; !range->empty(); range->popFront()) { | for (; !range->empty(); range->popFront()) { | ||||
MOZ_ASSERT(!stopRequested); | MOZ_ASSERT(!stopRequested); | ||||
const Edge& edge = range->front(); | Edge& edge = range->front(); | ||||
typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent); | typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent); | ||||
bool first = !a; | bool first = !a; | ||||
if (first) { | if (first) { | ||||
// This is the first time we've reached |edge.referent|. | // This is the first time we've reached |edge.referent|. | ||||
// Mark it as visited. | // Mark it as visited. | ||||
if (!visited.add(a, edge.referent, typename Handler::NodeData())) | if (!visited.add(a, edge.referent, typename Handler::NodeData())) | ||||
return false; | return false; | ||||
Show All 30 Lines | struct BreadthFirst { | ||||
// error. | // error. | ||||
void stop() { stopRequested = true; } | void stop() { stopRequested = true; } | ||||
// Request that the current edge's referent's outgoing edges not be | // Request that the current edge's referent's outgoing edges not be | ||||
// traversed. This must be called the first time that referent is reached. | // traversed. This must be called the first time that referent is reached. | ||||
// Other edges *to* that referent will still be traversed. | // Other edges *to* that referent will still be traversed. | ||||
void abandonReferent() { abandonRequested = true; } | void abandonReferent() { abandonRequested = true; } | ||||
// The runtime with which we were constructed. | // The context with which we were constructed. | ||||
JSRuntime* rt; | JSContext* cx; | ||||
// A map associating each node N that we have reached with a | // A map associating each node N that we have reached with a | ||||
// Handler::NodeData, for |handler|'s use. This is public, so that | // Handler::NodeData, for |handler|'s use. This is public, so that | ||||
// |handler| can access it to see the traversal thus far. | // |handler| can access it to see the traversal thus far. | ||||
using NodeMap = js::HashMap<Node, typename Handler::NodeData, js::DefaultHasher<Node>, | using NodeMap = js::HashMap<Node, typename Handler::NodeData, js::DefaultHasher<Node>, | ||||
js::SystemAllocPolicy>; | js::SystemAllocPolicy>; | ||||
NodeMap visited; | NodeMap visited; | ||||
▲ Show 20 Lines • Show All 51 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator