[PATCH 1/2] rbtree.h: Store parent in each entry and use that to manipulate the tree without a stack.

[Jacek Caban]

Hi Henri,


On 8/11/16 2:50 PM, Henri Verbeet wrote:
> On 10 August 2016 at 16:01, Jacek Caban <jacek at codeweavers.com> wrote:
>>   include/wine/rbtree.h | 376
>> +++++++++++++++++++++++++++-----------------------
>>   1 file changed, 200 insertions(+), 176 deletions(-)
>>
> Since this patch was assigned to me...
>
> I think this patch has quite a number of unrelated changes,

Implementation details that I change in helper functions affect other 
parts in such a way, that one patch felt appropriate. Anyway, I sent a 
split version (at the cost of temporary arguments).

> to the point that the patch touches over half of the lines in the file

Yes, that's more or less a rewrite, so it's not surprising.

> and I think deletion for example ends up just being a different algorithm.

Yes, that's intentional and there are reasons for that. The algorithm 
that I used (see implementation from Introduction to Algorithms book for 
reference) needs only bottom-up traversal once you have the node, which 
is perfect for following parent chain. Instead of doing rotations on way 
down and up, we do them just when going up. And, although asymptotically 
it's the same complexity, it usually needs fewer steps since it stops at 
the first red parent. Further, the traversal down can be a simple 
wine_rb_get call (and I intend to change it further so that 
wine_rb_remove takes wine_rb_entry as an argument, but that's something 
for future discussion). All that wasn't possible when we had to record 
the path to root on the stack, but when I had to make significant 
changes to the function anyway, I think that's a good moment to do full 
rewrite and take those little advantages.

> And while the aforementioned means I didn't look at everything in
> quite the amount of detail that would otherwise be appropriate, I do
> think some of those changes make things overly complicated. For
> example, a straightforward modification to wine_rb_put() would turn it
> into something like the following:
>
>
>      static inline int wine_rb_put(struct wine_rb_tree *tree, const
> void *key, struct wine_rb_entry *entry)
>      {
>         struct wine_rb_entry **node = &tree->root;
>         struct wine_rb_entry *parent = *node;
>
>         while (*node)
>         {
>             int c;
>
>             if (!(c = tree->functions->compare(key, *node)))
>                 return -1;
>             parent = *node;
>             if (c < 0) node = &(*node)->left;
>             else node = &(*node)->right;
>         }
>
>         entry->flags = WINE_RB_FLAG_RED;
>         entry->parent = parent;
>         entry->left = NULL;
>         entry->right = NULL;
>         *node = entry;
>
>         wine_rb_fixup(&tree->root, entry);
>         tree->root->flags &= ~WINE_RB_FLAG_RED;
>
>         return 0;
>      }
>
>
> I think that's much clearer than what this patch does with wine_rb_put().

Well, I don't see why one or another is cleaner, but it indeed slightly 
reduces the diff, so I changed that.

Thanks,
Jacek