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

[Henri Verbeet]

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, to the
point that the patch touches over half of the lines in the file and I
think deletion for example ends up just being a different algorithm.
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().