[PATCH 1/2] rbtree.h: Store parent in each entry and use that to manipulate the tree without a stack.

[Henri Verbeet]

On 15 August 2016 at 21:57, Jacek Caban <jacek at codeweavers.com> wrote:
> Yes, that's intentional and there are reasons for that. The algorithm that I
> used (see implementation from Introduction to Algorithms book for reference)
> needs only bottom-up traversal once you have the node, which is perfect for
> following parent chain. Instead of doing rotations on way down and up, we do
> them just when going up. And, although asymptotically it's the same
> complexity, it usually needs fewer steps since it stops at the first red
> parent. Further, the traversal down can be a simple wine_rb_get call (and I
> intend to change it further so that wine_rb_remove takes wine_rb_entry as an
> argument, but that's something for future discussion). All that wasn't
> possible when we had to record the path to root on the stack, but when I had
> to make significant changes to the function anyway, I think that's a good
> moment to do full rewrite and take those little advantages.
>
Well, the original code was written the way it was because of
simplicity more than anything else. The part that's performance
critical is wine_rb_get(), but that depends largely on the performance
of the compare function. Inserts and removals shouldn't be slow of
course, but I think it's reasonable to balance performance against
simplicity there. If in practice there are concrete performance
advantages to doing it a different way we could of course reconsider
that.

One of the things I don't like about these patches is that I think
full-blown parent pointers make it harder to reason about the code.
Similarly, I don't think the amount of branching and fiddling with
flags in e.g. wine_rb_remove() is an improvement. I realise those are
pretty subjective considerations, and the patches do work as intended
in my tests. Any performance differences I found seemed to be within
the margin of error. Nevertheless, would the attached patch work for
you?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-rbtree-Get-rid-of-the-explicit-stack.patch
Type: text/x-diff
Size: 9062 bytes
Desc: not available
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20160823/0087a61c/attachment-0001.patch>