libwine: Add a generic red-black tree.
Henri Verbeet
hverbeet at codeweavers.com
Tue Jun 2 02:01:17 CDT 2009
---
include/wine/rbtree.h | 59 ++++++++++
libs/wine/Makefile.in | 1 +
libs/wine/rbtree.c | 296 +++++++++++++++++++++++++++++++++++++++++++++++++
libs/wine/wine.def | 6 +
libs/wine/wine.map | 6 +
5 files changed, 368 insertions(+), 0 deletions(-)
create mode 100644 include/wine/rbtree.h
create mode 100644 libs/wine/rbtree.c
diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h
new file mode 100644
index 0000000..b5db007
--- /dev/null
+++ b/include/wine/rbtree.h
@@ -0,0 +1,59 @@
+/*
+ * 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_stack
+{
+ 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;
+};
+
+void wine_rb_destroy(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context);
+void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context);
+struct wine_rb_entry *wine_rb_get(const struct wine_rb_tree *tree, const void *key);
+void wine_rb_init(struct wine_rb_tree *tree, wine_rb_compare_func_t *compare);
+void wine_rb_put(struct wine_rb_tree *tree, const void *key, struct wine_rb_entry *entry);
+void wine_rb_remove(struct wine_rb_tree *tree, const void *key);
+
+#endif /* __WINE_WINE_RBTREE_H */
diff --git a/libs/wine/Makefile.in b/libs/wine/Makefile.in
index c846848..8e7a911 100644
--- a/libs/wine/Makefile.in
+++ b/libs/wine/Makefile.in
@@ -29,6 +29,7 @@ C_SRCS = \
mbtowc.c \
mmap.c \
port.c \
+ rbtree.c \
sortkey.c \
string.c \
utf8.c \
diff --git a/libs/wine/rbtree.c b/libs/wine/rbtree.c
new file mode 100644
index 0000000..5645a06
--- /dev/null
+++ b/libs/wine/rbtree.c
@@ -0,0 +1,296 @@
+/*
+ * 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
+ */
+
+#include "config.h"
+#include "wine/port.h"
+
+#include <stdlib.h>
+
+#include "wine/debug.h"
+#include "wine/rbtree.h"
+
+WINE_DEFAULT_DEBUG_CHANNEL(rbtree);
+
+#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 void wine_rb_stack_clear(struct wine_rb_stack *stack)
+{
+ stack->count = 0;
+}
+
+static 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 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 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 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 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 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 void 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 = realloc(stack->entries, new_size * sizeof(*stack->entries));
+
+ if (!new_entries)
+ {
+ ERR("Failed to allocate memory.\n");
+ return;
+ }
+
+ stack->entries = new_entries;
+ stack->size = new_size;
+ }
+
+ stack->entries[stack->count++] = entry;
+}
+
+static void 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;
+
+ for (entry = &tree->root;;)
+ {
+ struct wine_rb_entry *e = *entry;
+
+ if (e->left && !(e->flags & WINE_RB_FLAG_TRAVERSED_LEFT))
+ {
+ wine_rb_stack_push(&tree->stack, entry);
+ e->flags |= WINE_RB_FLAG_TRAVERSED_LEFT;
+ entry = &e->left;
+ continue;
+ }
+
+ if (e->right && !(e->flags & WINE_RB_FLAG_TRAVERSED_RIGHT))
+ {
+ wine_rb_stack_push(&tree->stack, entry);
+ 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];
+ }
+}
+
+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");
+ }
+ tree->stack.size = 16;
+ tree->stack.count = 0;
+}
+
+void wine_rb_for_each_entry(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context)
+{
+ wine_rb_postorder(tree, callback, context);
+}
+
+void 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) wine_rb_postorder(tree, callback, context);
+ tree->root = NULL;
+ free(tree->stack.entries);
+}
+
+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;
+}
+
+void 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;
+
+ wine_rb_stack_push(&tree->stack, parent);
+ c = tree->compare(key, *parent);
+ if (!c)
+ {
+ wine_rb_stack_clear(&tree->stack);
+ ERR("Trying to replace an existing entry.\n");
+ return;
+ }
+ 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;
+}
+
+void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
+{
+ struct wine_rb_entry **entry = &tree->root;
+
+ while (*entry)
+ {
+ if (tree->compare(key, *entry) < 0)
+ {
+ if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(entry);
+ wine_rb_stack_push(&tree->stack, 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;
+
+ wine_rb_stack_push(&tree->stack, entry);
+ (*entry)->flags |= WINE_RB_FLAG_STOP;
+
+ while ((*e)->left)
+ {
+ if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(e);
+ wine_rb_stack_push(&tree->stack, e);
+ e = &(*e)->left;
+ }
+ *e = NULL;
+ wine_rb_fixup(&tree->stack);
+
+ *m = **entry;
+ *entry = m;
+
+ break;
+ }
+ else
+ {
+ wine_rb_stack_push(&tree->stack, entry);
+ entry = &(*entry)->right;
+ }
+ }
+ }
+
+ wine_rb_fixup(&tree->stack);
+ if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
+}
diff --git a/libs/wine/wine.def b/libs/wine/wine.def
index a99c170..a8452b6 100644
--- a/libs/wine/wine.def
+++ b/libs/wine/wine.def
@@ -97,6 +97,12 @@ EXPORTS
wine_ldt_set_entry
wine_pthread_get_functions
wine_pthread_set_functions
+ wine_rb_destroy
+ wine_rb_for_each_entry
+ wine_rb_get
+ wine_rb_init
+ wine_rb_put
+ wine_rb_remove
wine_switch_to_stack
wine_utf8_mbstowcs
wine_utf8_wcstombs
diff --git a/libs/wine/wine.map b/libs/wine/wine.map
index 2159fac..bab6b61 100644
--- a/libs/wine/wine.map
+++ b/libs/wine/wine.map
@@ -111,6 +111,12 @@ WINE_1.0
wine_mmap_remove_reserved_area;
wine_pthread_get_functions;
wine_pthread_set_functions;
+ wine_rb_destroy;
+ wine_rb_for_each_entry;
+ wine_rb_get;
+ wine_rb_init;
+ wine_rb_put;
+ wine_rb_remove;
wine_set_fs;
wine_set_gs;
wine_switch_to_stack;
--
1.6.0.6
--------------070103090201000105010700--
More information about the wine-patches
mailing list