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

[Henri Verbeet]

On 21 March 2016 at 14:53, Jacek Caban <jacek at codeweavers.com> wrote:
> 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?
>
"Like" is perhaps stronger than what I'd use, but I'm not necessarily
opposed to it.

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

>> 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.
>
Right. Perhaps it's mostly lack of imagination, but I can't think of a
lot of cases where you'd use a hypothetical wine_rb_next() /
wine_rb_prev() instead of applying an operation on the entire tree,
and wouldn't already have the entries be part of some sort of existing
list. But yeah, parent pointers would make that easier.

> 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?
>
I think parent pointers would be fine. I didn't use those originally
because it's an extra field and I didn't really need them, but if
there's a good use-case for them that's probably worth it.