On Mon, Jul 4, 2011 at 2:23 PM, Richard Sandiford
<richard.sandif...@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
>
