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

[Jacek Caban]

Hi Henri,


On 8/23/16 5:54 PM, Henri Verbeet wrote:
> On 15 August 2016 at 21:57, Jacek Caban <jacek at codeweavers.com> wrote:
> 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.

Sure, my patches address mostly friendly and more flexible API (more
about that bellow), so let's concentrate on 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,

Yes, those are subjective. I find the new code actually cleaner and
easier to follow and I have some subjective thoughts about the other
solution as well. How about we both skip those subjective
considerations? If you have concrete improvements suggestions, I'm happy
to address them.

> 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?

Not really. I obviously considered something along those lines, you
could have asked before writing the patch. This solution wouldn't allow
something I'm planning as a follow up, which is friendly (callback free)
iterations. Something like
WINE_RB_FOR_EACH_SAFE/WINE_RB_FOR_EACH_ENTRY_SAFE macros (just like
their list.h counterparts) is just a matter of adding those defines with
my patches.

Also ordered iterations would be an useful addition. I had usage example
in my very recent jscript work, when I missed something like that and I
ended up having simplicity-oriented ad-hoc solution. It would be nice to
change that. Macros WINE_RB_FOR_EACH/WINE_RB_FOR_EACH_ENTRY doing
ordered, mutation-safe, iterations would be straightforward with my
patches. They are exactly what I needed.

Also, being able to efficiently iterate to the next node (something like
wine_rb_next(), which could cope with tree mutations) is important if we
want to use it for any of IDispatchEx implementations.

Jacek
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20160824/17001904/attachment.html>