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

[Sebastian Lackner]

On 25.08.2016 15:30, Jacek Caban wrote:
> Hi Sebastian,
> 
[...]
>> 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.

Well, I do not think allocators in general are a problem. It is only a problem if
important operations can fail because of out of memory errors. The Scapegoat
tree uses it only for the rebuild operation which is not critical (performance
will get worse, but everything will continue to work as expected).
Also, I do not think its possible to replace the array with an ordered list -
the rebuild operation requires computation of the median which would be way too
expensive for regular lists.

> 
> 
> Jacek
>