[PATCH] include: Use fixed stack size for rbtree.

[Jacek Caban]

On 03/21/16 14:04, Henri Verbeet wrote:
> On 21 March 2016 at 12:54, Jacek Caban <jacek at codeweavers.com> wrote:
>> - If constant stack size is enough, we could simply have it as a regular
>> C array in functions that need the stack. The array doesn't seem to big
>> to worry about stack usage and we'd have wine_rb_tree even smaller this
>> way. It's also faster than allocating stack on the heap.
> I don't think allocation speed is really an issue here.

That's just an additional advantage, not the main point. If that's your
only concern, should I understand that you like the idea?

>> - Since depth of the stack doesn't seem too bad, we could easily use
>> recursion for the implementation. Doing it in a smart way would avoid
>> the need for the stack at all (at cost of higher C stack usage).
> It's certainly possible to do a recursive implementation. I tend to
> find explicit stacks easier to follow though.
>> - If we stored parent in each node, I think we could get away without
>> having the stack at all. It would have its drawback of increasing memory
>> usage by O(n) and possibly fixup time would be O(log n ^2) instead of
>> O(log n) (although I'm pretty sure we could make it O(log n) in
>> practice). The big potential gain from this is that we could easily
>> implement linear-time traversal with this, so we'd potentially have more
>> use cases. Lack of iteration capabilities in current implementation is
>> the main reason it can't be used in places like vbscript for storing
>> object properties.
> If you don't mind requiring aligned pointers, you could merge the
> parent pointer with the flags field.

Yes, that's true even without parent pointers (we could merge them with
left/right pointers). I personally find such requirement something
that's better avoided, but if concerns about memory usage would prevent
implementing things this way, I think it would be worth it the requirement.

> What is the issue with wine_rb_for_each_entry() though?

wine_rb_for_each_entry can only walk the whole tree, you can't just do something like next_node() with it. Even in cases where it's enough, I find a loop cleaner than having to create new callback function. We could even have something like LIST_FOR_EACH for rb trees.


I tend to like that last option the most with preference like 3 > 2 > 1 > any solution storing stack in the tree. What's your opinion?

Jacek