The Tor Browser: js/src/gc/FindSCCs.h@129ffea94266 (annotated)

js/src/gc/FindSCCs.h@129ffea94266 (annotated)

js/src/gc/FindSCCs.h

Sat, 03 Jan 2015 20:18:00 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Sat, 03 Jan 2015 20:18:00 +0100
branch: TOR_BUG_3246
changeset 7: 129ffea94266
permissions: -rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

 /* -*- 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 "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 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 sl)
       : clock(1),
         stack(nullptr),
         firstComponent(nullptr),
         cur(nullptr),
         stackLimit(sl),
         stackFull(false)
     {}
     ~ComponentFinder() {
         JS_ASSERT(!stack);
         JS_ASSERT(!firstComponent);
     }
     /* Forces all nodes to be added to a single component. */
     void useOneComponent() { stackFull = true; }
     void addNode(Node *v) {
         if (v->gcDiscoveryTime == Undefined) {
             JS_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;
         }
         JS_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(*this);
         cur = old;
         if (stackFull)
             return;
         if (v->gcLowLink == v->gcDiscoveryTime) {
             Node *nextComponent = firstComponent;
             Node *w;
             do {
                 JS_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 */

The Tor Browser / annotate

js/src/gc/FindSCCs.h@129ffea94266 (annotated)

js/src/gc/FindSCCs.h