On 03/21/16 14:04, Henri Verbeet wrote:
On 21 March 2016 at 12:54, Jacek Caban jacek@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