Re: [2/5] libwine: Add a generic red-black tree.

[Alexandre Julliard]

Henri Verbeet  writes:
> +void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t *compare)
> +{
> - tree->compare = compare;
> - tree->root = NULL;
> - tree->stack.entries = malloc(16 * sizeof(*tree->stack.entries));
> - if (!tree->stack.entries)
> - {
> -
>    ERR("Failed to allocate stack memory.\n");
> - }

You can't hardcode malloc(), the allocator needs to be configurable,
particularly for use from the memory management code. Also printing an
ERR in that sort of code is not acceptable, errors need to be propagated
correctly and handled by the user.

I also still think this would be better as inline functions, at least
until it stabilizes. We don't want to change the libwine interface any
more than strictly necessary.

[2/5] libwine: Add a generic red-black tree.

[Henri Verbeet]

Alexandre Julliard wrote:
> You can't hardcode malloc(), the allocator needs to be configurable,
> particularly for use from the memory management code. Also printing an
> ERR in that sort of code is not acceptable, errors need to be propagated
> correctly and handled by the user.
>
> I also still think this would be better as inline functions, at least
> until it stabilizes. We don't want to change the libwine interface any
> more than strictly necessary.

How about something like the attached patch?

commit 2d1c3777494fe7bf31283c4c51ced3ea83093d2c
Author: Henri Verbeet 
Date:   Tue Jun 2 15:14:18 2009 +0200

include: Add a generic red-black tree.

diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h
new file mode 100644
index 0000000..da80b7f
--- /dev/null
+++ b/include/wine/rbtree.h
@@ -0,0 +1,368 @@
+/*
+ * Red-black search tree support
+ *
+ * Copyright 2009 Henri Verbeet
+ * Copyright 2009 Andrew Riedi
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
+ */
+
+#ifndef __WINE_WINE_RBTREE_H
+#define __WINE_WINE_RBTREE_H
+
+#define WINE_RB_ENTRY_VALUE(element, type, field) \
+    ((type *)((char *)(element) - FIELD_OFFSET(type, field)))
+
+struct wine_rb_entry
+{
+    struct wine_rb_entry *left;
+    struct wine_rb_entry *right;
+    unsigned int flags;
+};
+
+struct wine_rb_allocator
+{
+    void *(*alloc)(size_t size);
+    void *(*realloc)(void *ptr, size_t size);
+    void (*free)(void *ptr);
+};
+
+struct wine_rb_stack
+{
+    struct wine_rb_allocator allocator;
+    struct wine_rb_entry ***entries;
+    size_t count;
+    size_t size;
+};
+
+typedef int (wine_rb_compare_func_t)(const void *key, const struct wine_rb_entry *entry);
+typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *context);
+
+struct wine_rb_tree
+{
+    wine_rb_compare_func_t *compare;
+    struct wine_rb_entry *root;
+    struct wine_rb_stack stack;
+};
+
+#define WINE_RB_FLAG_RED                0x1
+#define WINE_RB_FLAG_STOP               0x2
+#define WINE_RB_FLAG_TRAVERSED_LEFT     0x4
+#define WINE_RB_FLAG_TRAVERSED_RIGHT    0x8
+
+static inline int wine_rb_is_red(struct wine_rb_entry *entry)
+{
+    return entry && (entry->flags & WINE_RB_FLAG_RED);
+}
+
+static inline void wine_rb_stack_clear(struct wine_rb_stack *stack)
+{
+    stack->count = 0;
+}
+
+static inline void wine_rb_rotate_left(struct wine_rb_entry **entry)
+{
+    struct wine_rb_entry *e = *entry;
+    struct wine_rb_entry *right = e->right;
+
+    e->right = right->left;
+    right->left = e;
+    right->flags &= ~WINE_RB_FLAG_RED;
+    right->flags |= e->flags & WINE_RB_FLAG_RED;
+    e->flags |= WINE_RB_FLAG_RED;
+    *entry = right;
+}
+
+static inline void wine_rb_rotate_right(struct wine_rb_entry **entry)
+{
+    struct wine_rb_entry *e = *entry;
+    struct wine_rb_entry *left = e->left;
+
+    e->left = left->right;
+    left->right = e;
+    left->flags &= ~WINE_RB_FLAG_RED;
+    left->flags |= e->flags & WINE_RB_FLAG_RED;
+    e->flags |= WINE_RB_FLAG_RED;
+    *entry = left;
+}
+
+static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
+{
+    entry->flags ^= WINE_RB_FLAG_RED;
+    entry->left->flags ^= WINE_RB_FLAG_RED;
+    entry->right->flags ^= WINE_RB_FLAG_RED;
+}
+
+static inline void wine_rb_fixup(struct wine_rb_stack *stack)
+{
+    while (stack->count)
+    {
+        struct wine_rb_entry **entry = stack->entries[stack->count - 1];
+
+        if ((*entry)->flags & WINE_RB_FLAG_STOP)
+        {
+            (*entry)->flags &= ~WINE_RB_FLAG_STOP;
+            return;
+        }
+
+        if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(entry);
+        if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(entry);
+        if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->right)) wine_rb_flip_color(*entry);
+        --stack->count;
+    }
+}
+
+static inline void wine_rb_move_red_left(struct wine_rb_entry **entry)
+{
+    wine_rb_flip_color(*entry);
+    if (wine_rb_is_red((*entry)->right->left))
+    {
+        wine_rb_rotate_right(&(*entry)->right);
+        wine_rb_rotate_left(entry);
+        wine_rb_flip_color(*entry);
+    }
+}
+
+static inline void wine_rb_move_red_right(struct wine_rb_entry **entry)
+{
+    wine_rb_flip_color(*entry);
+    if (wine_rb_is_red((*entry)->left->left))
+    {
+        wine_rb_rotate_right(entry);
+        wine_rb_flip_color(*entry);
+    }
+}
+
+static inline int wine_rb_stack_push(struct wine_rb_stack *stack, struct wine_rb_entry **entry)
+{
+    if (stack->count == stack->size)
+    {
+        size_t new_size = stack->size << 1;
+        struct wine_rb_entry ***new_entries = stack->allocator.realloc(stack->entries,
+                new_size * sizeof(*stack->entries));
+
+        if (!new_entries) return -1;
+
+        stack->entries = new_entries;
+        stack->size = new_size;
+    }
+
+    stack->entries[stack->count++] = entry;
+    return 0;
+}
+
+static inline void wine_rb_clear_traverse_stack(struct wine_rb_stack *stack)
+{
+    unsigned int i;
+
+    for (i = 0; i < stack->count; ++i)
+    {
+        (*stack->entries[i])->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT);
+    }
+
+    wine_rb_stack_clear(stack);
+}
+
+static inline int wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+{
+    struct wine_rb_entry **entry;
+
+    if (!tree->root) return 0;
+
+    for (entry = &tree->root;;)
+    {
+        struct wine_rb_entry *e = *entry;
+
+        if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT))
+        {
+            if (wine_rb_stack_push(&tree->stack, entry) == -1)
+            {
+                wine_rb_clear_traverse_stack(&tree->stack);
+                return -1;
+            }
+            e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;
+            entry = &e->left;
+            continue;
+        }
+
+        if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT))
+        {
+            if (wine_rb_stack_push(&tree->stack, entry) == -1)
+            {
+                wine_rb_clear_traverse_stack(&tree->stack);
+                return -1;
+            }
+            e->flags |= WINE_RB_FLAG_TRAVERSED_RIGHT;
+            entry = &e->right;
+            continue;
+        }
+
+        e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT);
+        callback(e, context);
+
+        if (!tree->stack.count) break;
+        entry = tree->stack.entries[--tree->stack.count];
+    }
+
+    return 0;
+}
+
+static inline int wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t *compare,
+        const struct wine_rb_allocator *allocator)
+{
+    tree->compare = compare;
+    tree->root = NULL;
+
+    tree->stack.allocator = *allocator;
+    tree->stack.entries = tree->stack.allocator.alloc(16 * sizeof(*tree->stack.entries));
+    if (!tree->stack.entries) return -1;
+    tree->stack.size = 16;
+    tree->stack.count = 0;
+
+    return 0;
+}
+
+static inline int wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+{
+    return wine_rb_postorder(tree, callback, context);
+}
+
+static inline int wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+{
+    /* Note that we use postorder here because the callback will likely free the entry. */
+    if (callback)
+    {
+        if (wine_rb_postorder(tree, callback, context) == -1) return -1;
+    }
+
+    tree->root = NULL;
+    tree->stack.allocator.free(tree->stack.entries);
+
+    return 0;
+}
+
+static inline struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key)
+{
+    struct wine_rb_entry *entry = tree->root;
+    while (entry)
+    {
+        int c = tree->compare(key, entry);
+        if (!c) return entry;
+        entry = c < 0 ? entry->left : entry->right;
+    }
+    return NULL;
+}
+
+static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry)
+{
+    struct wine_rb_entry **parent = &tree->root;
+
+    while (*parent)
+    {
+        int c;
+
+        if (wine_rb_stack_push(&tree->stack, parent) == -1)
+        {
+            wine_rb_stack_clear(&tree->stack);
+            return -1;
+        }
+
+        c = tree->compare(key, *parent);
+        if (!c)
+        {
+            wine_rb_stack_clear(&tree->stack);
+            return -1;
+        }
+        else if (c < 0) parent = &(*parent)->left;
+        else parent = &(*parent)->right;
+    }
+
+    entry->flags = WINE_RB_FLAG_RED;
+    entry->left = NULL;
+    entry->right = NULL;
+    *parent = entry;
+
+    wine_rb_fixup(&tree->stack);
+    tree->root->flags &= ~WINE_RB_FLAG_RED;
+
+    return 0;
+}
+
+static inline int wine_rb_remove(struct wine_rb_tree *tree, const void *key)
+{
+    struct wine_rb_entry **entry = &tree->root;
+    int ret = 0;
+
+    while (*entry)
+    {
+        if (tree->compare(key, *entry) < 0)
+        {
+            if ((ret = wine_rb_stack_push(&tree->stack, entry)) == -1) break;
+            if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
+            entry = &(*entry)->left;
+        }
+        else
+        {
+            if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(entry);
+            if (!tree->compare(key, *entry) && !(*entry)->right)
+            {
+                *entry = NULL;
+                break;
+            }
+            if (!wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->right->left))
+                wine_rb_move_red_right(entry);
+            if (!tree->compare(key, *entry))
+            {
+                struct wine_rb_entry **e = &(*entry)->right;
+                struct wine_rb_entry *m = *e;
+                while (m->left) m = m->left;
+
+                if ((ret = wine_rb_stack_push(&tree->stack, entry)) == -1) break;
+                (*entry)->flags |= WINE_RB_FLAG_STOP;
+
+                while ((*e)->left)
+                {
+                    if ((ret = wine_rb_stack_push(&tree->stack, e)) == -1)
+                    {
+                        wine_rb_fixup(&tree->stack);
+                        goto err;
+                    }
+                    if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);
+                    e = &(*e)->left;
+                }
+                *e = NULL;
+                wine_rb_fixup(&tree->stack);
+
+                *m = **entry;
+                *entry = m;
+
+                break;
+            }
+            else
+            {
+                if ((ret = wine_rb_stack_push(&tree->stack, entry)) == -1) break;
+                entry = &(*entry)->right;
+            }
+        }
+    }
+
+err:
+    wine_rb_fixup(&tree->stack);
+    if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
+
+    return ret;
+}
+
+#endif  /* __WINE_WINE_RBTREE_H */

[2/5] libwine: Add a generic red-black tree.

[Alexandre Julliard]

Henri Verbeet  writes:
> Alexandre Julliard wrote:
> > You can't hardcode malloc(), the allocator needs to be configurable,
> > particularly for use from the memory management code. Also printing an
> > ERR in that sort of code is not acceptable, errors need to be propagated
> > correctly and handled by the user.
> >
> > I also still think this would be better as inline functions, at least
> > until it stabilizes. We don't want to change the libwine interface any
> > more than strictly necessary.
>
> How about something like the attached patch?

Yes, that looks fine. It would probably look nicer to merge the
allocator and the compare function into a single structure, and just
store a pointer to it like a vtbl; but that's a minor detail.

[2/5] libwine: Add a generic red-black tree.

[Henri Verbeet]

Alexandre Julliard wrote:
> Yes, that looks fine. It would probably look nicer to merge the
> allocator and the compare function into a single structure, and just
> store a pointer to it like a vtbl; but that's a minor detail.

It's easy enough to store a pointer to the allocator instead of making a 
copy, but wouldn't merging the compare function into the same structure 
be inconvenient when using multiple trees with different compare 
functions but the same allocator, like in in wined3d?

[2/5] libwine: Add a generic red-black tree.

[Alexandre Julliard]

Henri Verbeet  writes:
> Alexandre Julliard wrote:
> > Yes, that looks fine. It would probably look nicer to merge the
> > allocator and the compare function into a single structure, and just
> > store a pointer to it like a vtbl; but that's a minor detail.
>
> It's easy enough to store a pointer to the allocator instead of making
> a copy, but wouldn't merging the compare function into the same
> structure be inconvenient when using multiple trees with different
> compare functions but the same allocator, like in in wined3d?

You could still share the allocations functions of course, you'd only
need an extra structure. My feeling is that having all the functions
described in the same structure makes the interface cleaner, even if it
means you need one such structure for each usage of the tree. But it's a
cosmetic detail, I don't feel strongly about it.