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

[Jacek Caban]

On 03/21/16 12:38, Henri Verbeet wrote:
> On 21 March 2016 at 11:25, Alexandre Julliard <julliard at winehq.org> wrote:
>> Henri Verbeet <hverbeet at gmail.com> writes:
>>
>>> On 21 March 2016 at 04:50, Alexandre Julliard <julliard at winehq.org> wrote:
>>>> While we probably don't want that in all cases, having the option of a
>>>> simpler, allocation-free rbtree would be nice. I suspect there are a
>>>> number of global lists that could benefit from that.
>>>>
>>> I don't know. I think that outside of D3D it's only used in dbghelp
>>> and winemenubuilder, and at least in the winemenubuilder case it might
>>> be better to just sort the prog ID list before using it to generate
>>> associations. As for the usage in D3D, I think there could potentially
>>> be value in having a stack per-thread instead of per-rbtree, but I
>>> don't think that would necessarily make things simpler. Having a fixed
>>> stack size could certainly be done, but I don't think simply
>>> increasing the size of struct wine_rb_tree would make things better
>>> for any of the existing cases.
>> Sure, for the existing cases it's fine. My feeling is that there may be
>> more use cases if it was more straightforward to use. I know that a
>> couple of times I considered using an rbtree but didn't, because I felt
>> the potential gain wasn't worth the complexity (not only the extra
>> functions, but also the need to add error handling for allocation
>> failures).
>>
> Allocating the maximum stack size on initialisation in exchange for
> never having allocation failures could be worth it, yeah. Note that
> wine_rb_put() can also fail when trying to insert duplicate values
> though. I suppose we could change that to either replace the existing
> entry or to fail silently.

There are more options to consider. A few that come to mind are:

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

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

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

Cheers,
Jacek