On 21 March 2016 at 14:53, Jacek Caban jacek@codeweavers.com wrote:
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?
"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.