The Tor Browser: mfbt/SplayTree.h@97036ab72558

Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

     2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */

     3 /* This Source Code Form is subject to the terms of the Mozilla Public

     4  * License, v. 2.0. If a copy of the MPL was not distributed with this

     5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     7 /**

     8  * A sorted tree with optimal access times, where recently-accessed elements

     9  * are faster to access again.

    10  */

    12 #ifndef mozilla_SplayTree_h

    13 #define mozilla_SplayTree_h

    15 #include "mozilla/Assertions.h"

    16 #include "mozilla/NullPtr.h"

    18 namespace mozilla {

    20 template<class T, class C>

    21 class SplayTree;

    23 template<typename T>

    24 class SplayTreeNode

    25 {

    26   public:

    27     template<class A, class B>

    28     friend class SplayTree;

    30     SplayTreeNode()

    31       : left(nullptr), right(nullptr), parent(nullptr)

    32     {}

    34   private:

    35     T* left;

    36     T* right;

    37     T* parent;

    38 };

    41 /**

    42  * Class which represents a splay tree.

    43  * Splay trees are balanced binary search trees for which search, insert and

    44  * remove are all amortized O(log n), but where accessing a node makes it

    45  * faster to access that node in the future.

    46  *

    47  * T indicates the type of tree elements, Comparator must have a static

    48  * compare(const T&, const T&) method ordering the elements. The compare

    49  * method must be free from side effects.

    50  */

    51 template<typename T, class Comparator>

    52 class SplayTree

    53 {

    54     T* root;

    56   public:

    57     SplayTree()

    58       : root(nullptr)

    59     {}

    61     bool empty() const {

    62       return !root;

    63     }

    65     T* find(const T& v)

    66     {

    67       if (empty())

    68         return nullptr;

    70       T* last = lookup(v);

    71       splay(last);

    72       checkCoherency(root, nullptr);

    73       return Comparator::compare(v, *last) == 0 ? last : nullptr;

    74     }

    76     bool insert(T* v)

    77     {

    78       MOZ_ASSERT(!find(*v), "Duplicate elements are not allowed.");

    80       if (!root) {

    81         root = v;

    82         return true;

    83       }

    84       T* last = lookup(*v);

    85       int cmp = Comparator::compare(*v, *last);

    87       T** parentPointer = (cmp < 0) ? &last->left : &last->right;

    88       MOZ_ASSERT(!*parentPointer);

    89       *parentPointer = v;

    90       v->parent = last;

    92       splay(v);

    93       checkCoherency(root, nullptr);

    94       return true;

    95     }

    97     T* remove(const T& v)

    98     {

    99       T* last = lookup(v);

   100       MOZ_ASSERT(last, "This tree must contain the element being removed.");

   101       MOZ_ASSERT(Comparator::compare(v, *last) == 0);

   103       // Splay the tree so that the item to remove is the root.

   104       splay(last);

   105       MOZ_ASSERT(last == root);

   107       // Find another node which can be swapped in for the root: either the

   108       // rightmost child of the root's left, or the leftmost child of the

   109       // root's right.

   110       T* swap;

   111       T* swapChild;

   112       if (root->left) {

   113         swap = root->left;

   114         while (swap->right)

   115           swap = swap->right;

   116         swapChild = swap->left;

   117       } else if (root->right) {

   118         swap = root->right;

   119         while (swap->left)

   120           swap = swap->left;

   121         swapChild = swap->right;

   122       } else {

   123         T* result = root;

   124         root = nullptr;

   125         return result;

   126       }

   128       // The selected node has at most one child, in swapChild. Detach it

   129       // from the subtree by replacing it with that child.

   130       if (swap == swap->parent->left)

   131         swap->parent->left = swapChild;

   132       else

   133         swap->parent->right = swapChild;

   134       if (swapChild)

   135         swapChild->parent = swap->parent;

   137       // Make the selected node the new root.

   138       root = swap;

   139       root->parent = nullptr;

   140       root->left = last->left;

   141       root->right = last->right;

   142       if (root->left) {

   143         root->left->parent = root;

   144       }

   145       if (root->right) {

   146         root->right->parent = root;

   147       }

   149       checkCoherency(root, nullptr);

   150       return last;

   151     }

   153     T* removeMin()

   154     {

   155       MOZ_ASSERT(root, "No min to remove!");

   157       T* min = root;

   158       while (min->left)

   159         min = min->left;

   160       return remove(*min);

   161     }

   163   private:

   164     /**

   165      * Returns the node in this comparing equal to |v|, or a node just greater or

   166      * just less than |v| if there is no such node.

   167      */

   168     T* lookup(const T& v)

   169     {

   170       MOZ_ASSERT(!empty());

   172       T* node = root;

   173       T* parent;

   174       do {

   175         parent = node;

   176         int c = Comparator::compare(v, *node);

   177         if (c == 0)

   178           return node;

   179         else if (c < 0)

   180           node = node->left;

   181         else

   182           node = node->right;

   183       } while (node);

   184       return parent;

   185     }

   187     /**

   188      * Rotate the tree until |node| is at the root of the tree. Performing

   189      * the rotations in this fashion preserves the amortized balancing of

   190      * the tree.

   191      */

   192     void splay(T* node)

   193     {

   194       MOZ_ASSERT(node);

   196       while (node != root) {

   197         T* parent = node->parent;

   198         if (parent == root) {

   199           // Zig rotation.

   200           rotate(node);

   201           MOZ_ASSERT(node == root);

   202           return;

   203         }

   204         T* grandparent = parent->parent;

   205         if ((parent->left == node) == (grandparent->left == parent)) {

   206           // Zig-zig rotation.

   207           rotate(parent);

   208           rotate(node);

   209         } else {

   210           // Zig-zag rotation.

   211           rotate(node);

   212           rotate(node);

   213         }

   214       }

   215     }

   217     void rotate(T* node)

   218     {

   219       // Rearrange nodes so that node becomes the parent of its current

   220       // parent, while preserving the sortedness of the tree.

   221       T* parent = node->parent;

   222       if (parent->left == node) {

   223         //     x          y

   224         //   y  c  ==>  a  x

   225         //  a b           b c

   226         parent->left = node->right;

   227         if (node->right)

   228           node->right->parent = parent;

   229         node->right = parent;

   230       } else {

   231         MOZ_ASSERT(parent->right == node);

   232         //   x             y

   233         //  a  y   ==>   x  c

   234         //    b c       a b

   235         parent->right = node->left;

   236         if (node->left)

   237           node->left->parent = parent;

   238         node->left = parent;

   239       }

   240       node->parent = parent->parent;

   241       parent->parent = node;

   242       if (T* grandparent = node->parent) {

   243         if (grandparent->left == parent)

   244           grandparent->left = node;

   245         else

   246           grandparent->right = node;

   247       } else {

   248         root = node;

   249       }

   250     }

   252     T* checkCoherency(T* node, T* minimum)

   253     {

   254 #ifdef DEBUG

   255       MOZ_ASSERT_IF(root, !root->parent);

   256       if (!node) {

   257         MOZ_ASSERT(!root);

   258         return nullptr;

   259       }

   260       MOZ_ASSERT_IF(!node->parent, node == root);

   261       MOZ_ASSERT_IF(minimum, Comparator::compare(*minimum, *node) < 0);

   262       if (node->left) {

   263         MOZ_ASSERT(node->left->parent == node);

   264         T* leftMaximum = checkCoherency(node->left, minimum);

   265         MOZ_ASSERT(Comparator::compare(*leftMaximum, *node) < 0);

   266       }

   267       if (node->right) {

   268         MOZ_ASSERT(node->right->parent == node);

   269         return checkCoherency(node->right, node);

   270       }

   271       return node;

   272 #else

   273       return nullptr;

   274 #endif

   275     }

   277     SplayTree(const SplayTree&) MOZ_DELETE;

   278     void operator=(const SplayTree&) MOZ_DELETE;

   279 };

   281 }  /* namespace mozilla */

   283 #endif /* mozilla_SplayTree_h */

The Tor Browser / file revision

mfbt/SplayTree.h@97036ab72558

mfbt/SplayTree.h