Is libiberty's splay-tree.c really a splay tree?

[Richard Guenther]

On Mon, Jul 4, 2011 at 2:23 PM, Richard Sandiford
<richard.sandiford@linaro.org> wrote:
> OK, I know I'm embarrassing myself here, but is libiberty's splay-tree.c
> doing the right thing for the zig-zig and zag-zag cases?  The code reads:
>
>    /* Now we have the four cases of double-rotation.  */
>    if (cmp1 < 0 && cmp2 < 0)
>      {
>        rotate_left (&n->left, c, c->left);
>        rotate_left (&sp->root, n, n->left);
>      }
>    else if (cmp1 > 0 && cmp2 > 0)
>      {
>        rotate_right (&n->right, c, c->right);
>        rotate_right (&sp->root, n, n->right);
>      }
>    else ...
>
> whereas I thought you were supposed to rotate on the root first
> for these cases.  E.g. instead of:
>
>         X                     Y                Z
>        / \                  /   \             / \
>       Y   D                Z     X           A   Y
>      / \                  / \   / \             / \
>     Z   C      --->      A   B C   D   --->    B   X
>    / \                                            / \
>   A   B                                          C   D
>
> the above seems to implement:
>
>         X                 X                    Z
>        / \               / \                  / \
>       Y   D             Z   D                A   X
>      / \               / \                      / \
>     Z   C      --->   A   Y          ---->     Y   D
>    / \                   / \                  / \
>   A   B                 B   C                B   C
>
> (The other two cases seem fine.)

There were other people pointing out issues with the splay tree
(but all w/o copyright assignment and much larger patches).

I know I did the last re-write of this piece of code but it's been
a long time ... in any case, previous reports were that the
current implementation degenerates in some cases.

So yes, it could be that there is a bug ...

Richard.

> Richard
>