Add m-esr52 at 52.6.0

1 files changed, 308 insertions, 0 deletions

diff --git a/js/src/ds/SplayTree.h b/js/src/ds/SplayTree.h
new file mode 100644
index 000000000..f130706e5
--- /dev/null
+++ b/js/src/ds/SplayTree.h
@@ -0,0 +1,308 @@
+/* -*- 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 ds_SplayTree_h
+#define ds_SplayTree_h
+
+#include "ds/LifoAlloc.h"
+
+namespace js {
+
+/*
+ * Class which represents a splay tree with nodes allocated from a LifoAlloc.
+ * Splay trees are balanced binary search trees for which search, insert and
+ * remove are all amortized O(log n).
+ *
+ * T indicates the type of tree elements, C must have a static
+ * compare(const T&, const T&) method ordering the elements. As for LifoAlloc
+ * objects, T objects stored in the tree will not be explicitly destroyed.
+ */
+template <class T, class C>
+class SplayTree
+{
+    struct Node {
+        T item;
+        Node* left;
+        Node* right;
+        Node* parent;
+
+        explicit Node(const T& item)
+          : item(item), left(nullptr), right(nullptr), parent(nullptr)
+        {}
+    };
+
+    LifoAlloc* alloc;
+    Node* root;
+    Node* freeList;
+
+#ifdef DEBUG
+    bool enableCheckCoherency;
+#endif
+
+    SplayTree(const SplayTree&) = delete;
+    SplayTree& operator=(const SplayTree&) = delete;
+
+  public:
+
+    explicit SplayTree(LifoAlloc* alloc = nullptr)
+      : alloc(alloc), root(nullptr), freeList(nullptr)
+#ifdef DEBUG
+      , enableCheckCoherency(true)
+#endif
+    {}
+
+    void setAllocator(LifoAlloc* alloc) {
+        this->alloc = alloc;
+    }
+
+    void disableCheckCoherency() {
+#ifdef DEBUG
+        enableCheckCoherency = false;
+#endif
+    }
+
+    bool empty() const {
+        return !root;
+    }
+
+    T* maybeLookup(const T& v)
+    {
+        if (!root)
+            return nullptr;
+        Node* last = lookup(v);
+        return (C::compare(v, last->item) == 0) ? &(last->item) : nullptr;
+    }
+
+    bool contains(const T& v, T* res)
+    {
+        if (!root)
+            return false;
+        Node* last = lookup(v);
+        splay(last);
+        checkCoherency(root, nullptr);
+        if (C::compare(v, last->item) == 0) {
+            *res = last->item;
+            return true;
+        }
+        return false;
+    }
+
+    MOZ_MUST_USE bool insert(const T& v)
+    {
+        Node* element = allocateNode(v);
+        if (!element)
+            return false;
+
+        if (!root) {
+            root = element;
+            return true;
+        }
+        Node* last = lookup(v);
+        int cmp = C::compare(v, last->item);
+
+        // Don't tolerate duplicate elements.
+        MOZ_ASSERT(cmp);
+
+        Node*& parentPointer = (cmp < 0) ? last->left : last->right;
+        MOZ_ASSERT(!parentPointer);
+        parentPointer = element;
+        element->parent = last;
+
+        splay(element);
+        checkCoherency(root, nullptr);
+        return true;
+    }
+
+    void remove(const T& v)
+    {
+        Node* last = lookup(v);
+        MOZ_ASSERT(last && C::compare(v, last->item) == 0);
+
+        splay(last);
+        MOZ_ASSERT(last == root);
+
+        // Find another node which can be swapped in for the root: either the
+        // rightmost child of the root's left, or the leftmost child of the
+        // root's right.
+        Node* swap;
+        Node* swapChild;
+        if (root->left) {
+            swap = root->left;
+            while (swap->right)
+                swap = swap->right;
+            swapChild = swap->left;
+        } else if (root->right) {
+            swap = root->right;
+            while (swap->left)
+                swap = swap->left;
+            swapChild = swap->right;
+        } else {
+            freeNode(root);
+            root = nullptr;
+            return;
+        }
+
+        // The selected node has at most one child, in swapChild. Detach it
+        // from the subtree by replacing it with that child.
+        if (swap == swap->parent->left)
+            swap->parent->left = swapChild;
+        else
+            swap->parent->right = swapChild;
+        if (swapChild)
+            swapChild->parent = swap->parent;
+
+        root->item = swap->item;
+        freeNode(swap);
+
+        checkCoherency(root, nullptr);
+    }
+
+    template <class Op>
+    void forEach(Op op)
+    {
+        forEachInner<Op>(op, root);
+    }
+
+  private:
+
+    Node* lookup(const T& v)
+    {
+        MOZ_ASSERT(root);
+        Node* node = root;
+        Node* parent;
+        do {
+            parent = node;
+            int c = C::compare(v, node->item);
+            if (c == 0)
+                return node;
+            else if (c < 0)
+                node = node->left;
+            else
+                node = node->right;
+        } while (node);
+        return parent;
+    }
+
+    Node* allocateNode(const T& v)
+    {
+        Node* node = freeList;
+        if (node) {
+            freeList = node->left;
+            new(node) Node(v);
+            return node;
+        }
+        return alloc->new_<Node>(v);
+    }
+
+    void freeNode(Node* node)
+    {
+        node->left = freeList;
+        freeList = node;
+    }
+
+    void splay(Node* node)
+    {
+        // Rotate the element until it is at the root of the tree. Performing
+        // the rotations in this fashion preserves the amortized balancing of
+        // the tree.
+        MOZ_ASSERT(node);
+        while (node != root) {
+            Node* parent = node->parent;
+            if (parent == root) {
+                // Zig rotation.
+                rotate(node);
+                MOZ_ASSERT(node == root);
+                return;
+            }
+            Node* grandparent = parent->parent;
+            if ((parent->left == node) == (grandparent->left == parent)) {
+                // Zig-zig rotation.
+                rotate(parent);
+                rotate(node);
+            } else {
+                // Zig-zag rotation.
+                rotate(node);
+                rotate(node);
+            }
+        }
+    }
+
+    void rotate(Node* node)
+    {
+        // Rearrange nodes so that node becomes the parent of its current
+        // parent, while preserving the sortedness of the tree.
+        Node* parent = node->parent;
+        if (parent->left == node) {
+            //     x          y
+            //   y  c  ==>  a  x
+            //  a b           b c
+            parent->left = node->right;
+            if (node->right)
+                node->right->parent = parent;
+            node->right = parent;
+        } else {
+            MOZ_ASSERT(parent->right == node);
+            //   x             y
+            //  a  y   ==>   x  c
+            //    b c       a b
+            parent->right = node->left;
+            if (node->left)
+                node->left->parent = parent;
+            node->left = parent;
+        }
+        node->parent = parent->parent;
+        parent->parent = node;
+        if (Node* grandparent = node->parent) {
+            if (grandparent->left == parent)
+                grandparent->left = node;
+            else
+                grandparent->right = node;
+        } else {
+            root = node;
+        }
+    }
+
+    template <class Op>
+    void forEachInner(Op op, Node* node)
+    {
+        if (!node)
+            return;
+
+        forEachInner<Op>(op, node->left);
+        op(node->item);
+        forEachInner<Op>(op, node->right);
+    }
+
+    Node* checkCoherency(Node* node, Node* minimum)
+    {
+#ifdef DEBUG
+        if (!enableCheckCoherency)
+            return nullptr;
+        if (!node) {
+            MOZ_ASSERT(!root);
+            return nullptr;
+        }
+        MOZ_ASSERT_IF(!node->parent, node == root);
+        MOZ_ASSERT_IF(minimum, C::compare(minimum->item, node->item) < 0);
+        if (node->left) {
+            MOZ_ASSERT(node->left->parent == node);
+            Node* leftMaximum = checkCoherency(node->left, minimum);
+            MOZ_ASSERT(C::compare(leftMaximum->item, node->item) < 0);
+        }
+        if (node->right) {
+            MOZ_ASSERT(node->right->parent == node);
+            return checkCoherency(node->right, node);
+        }
+        return node;
+#else
+        return nullptr;
+#endif
+    }
+};
+
+}  /* namespace js */
+
+#endif /* ds_SplayTree_h */