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

[Jacek Caban]

On 25.08.2016 15:59, Sebastian Lackner wrote:
> 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).

Sure, failing operations is the most annoying part of allocators, so
it's a step forward. Still, avoiding overhead of adding allocators in
each tree user would be nice.


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

I think that should be doable, but with a different algorithm in wine_rb_build. That's what I meant by tricky. Here is first that comes first into my mind:

let's say that nodes are in list1

while(list1 length > 1) {
    while(list1 length > 0) {
        take first 3 elements node1, node2, node3 from list1 (*)
        node2->left = node1
        node2->right = node3
	append node2 into list2
    }
    list1 = list2
}

root = the only element in list1

(*) if list length 2, use NULL for node3, if length is 1,
node1=node3=NULL, node2=the only node in list

Since on every outer loop iteration length of new list is 3 times
shorter than previous length, the complexity is O(n), just like with the
array.


Jacek