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

[Henri Verbeet]

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.

> - 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. What is the issue with
wine_rb_for_each_entry() though?