Add splay tree utility class

RESOLVED FIXED in mozilla20

Status

()

defect
RESOLVED FIXED
7 years ago
7 years ago

People

(Reporter: bhackett, Unassigned)

Tracking

Other Branch
mozilla20
x86
macOS
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

Posted patch patchSplinter Review
Bug 814966 needs some sort of balanced search tree for quickly deciding whether a given interval can be allocated to a physical register without colliding with existing allocations.  Splay trees are nice for this because they are very simple and take amortized logarithmic time for all common operations.  Similar to bug 817769, it would be nice to make this a generic class.
Attachment #691660 - Flags: review?(luke)
Comment on attachment 691660 [details] [diff] [review]
patch

Review of attachment 691660 [details] [diff] [review]:
-----------------------------------------------------------------

Nice

::: js/src/ds/SplayTree.h
@@ +14,5 @@
> +
> +/*
> + * 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).

s/amortized/average/

@@ +17,5 @@
> + * 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.

This container doesn't call T's destructor so it should only be used for PODs.  Could you mention this in the comment and then static assert IsPodType<T> in the class.  Note: JS_STATIC_ASSERT doesn't work in template class bodies or assert at all in member functions, so you'll want to:
  typedef typename tl::StaticAssert<tl::IsPodType<T>::result>::result isPodAssert;
or something.

@@ +139,5 @@
> +
> +    Node *lookup(const T &v)
> +    {
> +        JS_ASSERT(root);
> +        Node *node = root, *last = root;

I think it'd be a bit more clear to rename 'last' to 'parent' and either leave it uninitialized (since it is immediately clobbered) or, if you'd like, assign it to NULL since the parent of the root is NULL.

@@ +173,5 @@
> +
> +    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

s/amortized/average/ or "expected" or something probabilistic sounding.

@@ +205,5 @@
> +        Node *parent = node->parent;
> +        if (parent->left == node) {
> +            //     x          y
> +            //   y  c  ==>  a  x
> +            //  a b           b c

pretty

@@ +223,5 @@
> +        }
> +        node->parent = parent->parent;
> +        parent->parent = node;
> +        if (node->parent) {
> +            Node *grandparent = node->parent;

if (Node *grandparent = node->parent) {
Attachment #691660 - Flags: review?(luke) → review+
Oops, Bill pointed out that splay trees are indeed amortized O(log(n)).  While the height of the tree can be O(n), making a worst-case *particular* access O(n), a sequence of m operations is O(m * log(n)).  Splay trees are even cooler than I thought!
Comment on attachment 691660 [details] [diff] [review]
patch

Review of attachment 691660 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/ds/SplayTree.h
@@ +17,5 @@
> + * 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.

You could use the normal static-assert macro inside a method if you make sure the method's called by something every SplayTree user will use.  Putting a call to staticAsserts(), say, in the constructor would do the trick just fine.
I added destructor invokes when freeing nodes to avoid the IsPodType asserts.  Instantiating tl::IsPodType for the class being used in BacktrackingAllocator required hoisting it out of BacktrackingAllocator and making related code far uglier.

https://hg.mozilla.org/integration/mozilla-inbound/rev/e4da3fe4a9da
It's still not safe for regular non-POD object usage, though, as the splay tree destructor would need to destroy whatever objects remained.
Fair enough, this patch gives consistent destructor behavior (i.e. it is not called) and adds a comment describing the situation at the top of the class.  This interface is the same as for lifoAlloc->new_<...> objects, which are not required to be POD types.  Until this class has more users I don't think it's worth overengineering.
Attachment #692335 - Flags: review?(luke)
Attachment #692335 - Flags: review?(luke) → review+
https://hg.mozilla.org/mozilla-central/rev/e4da3fe4a9da
https://hg.mozilla.org/mozilla-central/rev/aafa9e2de532
Status: NEW → RESOLVED
Closed: 7 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla20
You need to log in before you can comment on or make changes to this bug.