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

[Sebastian Lackner]

On 24.08.2016 12:49, Jacek Caban wrote:
>> 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

(Non-safe) iterator macros with different orders could also be added without
bigger code changes, but I assume that alone would still not be sufficient
for your requirements. In order to implement safe iterator callbacks (and to
get rid of the stack) those parent pointers would really be useful, although
they have the disadvantage that they increase memory usage a bit. This makes
me wonder if it wouldn't be useful have multiple tree implementations
targeting different use-cases and performance requirements.

I assume that there are currently no plans to exchange the RBTree with
something else, nevertheless it shouldn't hurt to share some code. I've
attached a proof-of-concept patch to replace the RBTree with a Scapegoat
tree I wrote a while ago. In contrast to other trees a nice property is that
it is not really required to keep the tree balanced all the time, instead we
have rebuild operations which will automatically detect it if the performance
gets too bad and build a binary search tree. When deleting lots of elements
for example we could disable rebuild temporarily to avoid too much overhead.
If someone has code to measure performance differences in practice, feel free
to give it a try. ;)

Regards,
Sebastian

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-include-Use-a-Scapegoat-tree-instead-of-a-R-B-tree.patch
Type: text/x-patch
Size: 16467 bytes
Desc: not available
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20160825/9bd4b2c1/attachment.bin>