On 15 August 2016 at 21:57, Jacek Caban jacek@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?