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

[Jacek Caban]

Hi Sebastian,

On 25.08.2016 03:57, Sebastian Lackner wrote:
> 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.

As discussed earlier, if memory becomes a real problem, we may reduce it
to three pointers at the cost of requiring aligned pointers.

> This makes me wonder if it wouldn't be useful have multiple tree implementations
> targeting different use-cases and performance requirements.

I guess we could if we had convincing reason. I think that improved
existing implementation should be enough so far.

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

Sure. Since you posted it, I had a quick look. That implementation
requires allocators, which is what we should avoid to simplify usage of
the tree. You could get rid of the array by storing another pointer in
nodes that would be used to link them into ordered list instead of an
array (that would require a bit more tricky wine_rb_build, but it should
be doable without much perf cost). However, then you'd give up memory
advantage.


Jacek