Jacek Caban : rbtree.h: Rewrite wine_rb_remove to use parent pointers instead of stack.
Alexandre Julliard
julliard at winehq.org
Tue Aug 30 10:30:45 CDT 2016
Module: wine
Branch: master
Commit: f9dc4832ed64a1948341e14e945b77454c603019
URL: http://source.winehq.org/git/wine.git/?a=commit;h=f9dc4832ed64a1948341e14e945b77454c603019
Author: Jacek Caban <jacek at codeweavers.com>
Date: Mon Aug 15 21:53:53 2016 +0200
rbtree.h: Rewrite wine_rb_remove to use parent pointers instead of stack.
Signed-off-by: Jacek Caban <jacek at codeweavers.com>
Signed-off-by: Alexandre Julliard <julliard at winehq.org>
---
include/wine/rbtree.h | 179 ++++++++++++++++++++++++++++++--------------------
1 file changed, 108 insertions(+), 71 deletions(-)
diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h
index 2d364e3..a549a87 100644
--- a/include/wine/rbtree.h
+++ b/include/wine/rbtree.h
@@ -94,7 +94,7 @@ 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_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e)
+static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb_entry *e, int change_color)
{
struct wine_rb_entry *right = e->right;
@@ -110,12 +110,15 @@ static inline void wine_rb_rotate_left(struct wine_rb_tree *tree, struct wine_rb
right->left = e;
right->parent = e->parent;
e->parent = right;
- right->flags &= ~WINE_RB_FLAG_RED;
- right->flags |= e->flags & WINE_RB_FLAG_RED;
- e->flags |= WINE_RB_FLAG_RED;
+ if (change_color)
+ {
+ right->flags &= ~WINE_RB_FLAG_RED;
+ right->flags |= e->flags & WINE_RB_FLAG_RED;
+ e->flags |= WINE_RB_FLAG_RED;
+ }
}
-static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e)
+static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_rb_entry *e, int change_color)
{
struct wine_rb_entry *left = e->left;
@@ -131,9 +134,12 @@ static inline void wine_rb_rotate_right(struct wine_rb_tree *tree, struct wine_r
left->right = e;
left->parent = e->parent;
e->parent = left;
- left->flags &= ~WINE_RB_FLAG_RED;
- left->flags |= e->flags & WINE_RB_FLAG_RED;
- e->flags |= WINE_RB_FLAG_RED;
+ if (change_color)
+ {
+ left->flags &= ~WINE_RB_FLAG_RED;
+ left->flags |= e->flags & WINE_RB_FLAG_RED;
+ e->flags |= WINE_RB_FLAG_RED;
+ }
}
static inline void wine_rb_flip_color(struct wine_rb_entry *entry)
@@ -155,34 +161,13 @@ static inline void wine_rb_fixup(struct wine_rb_tree *tree, struct wine_rb_stack
return;
}
- if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(tree, *entry);
- if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(tree, *entry);
+ if (wine_rb_is_red((*entry)->right) && !wine_rb_is_red((*entry)->left)) wine_rb_rotate_left(tree, *entry, 1);
+ if (wine_rb_is_red((*entry)->left) && wine_rb_is_red((*entry)->left->left)) wine_rb_rotate_right(tree, *entry, 1);
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_tree *tree, struct wine_rb_entry **entry)
-{
- wine_rb_flip_color(*entry);
- if (wine_rb_is_red((*entry)->right->left))
- {
- wine_rb_rotate_right(tree, (*entry)->right);
- wine_rb_rotate_left(tree, *entry);
- wine_rb_flip_color(*entry);
- }
-}
-
-static inline void wine_rb_move_red_right(struct wine_rb_tree *tree, struct wine_rb_entry **entry)
-{
- wine_rb_flip_color(*entry);
- if (wine_rb_is_red((*entry)->left->left))
- {
- wine_rb_rotate_right(tree, *entry);
- wine_rb_flip_color(*entry);
- }
-}
-
static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter)
{
if (!iter) return NULL;
@@ -300,60 +285,112 @@ static inline int wine_rb_put(struct wine_rb_tree *tree, const void *key, struct
static inline void wine_rb_remove(struct wine_rb_tree *tree, const void *key)
{
- struct wine_rb_entry **entry = &tree->root;
+ struct wine_rb_entry *entry, *iter, *child, *parent, *w;
+ int need_fixup;
+
+ if (!(entry = wine_rb_get(tree, key))) return;
+
+ if (entry->right && entry->left)
+ for(iter = entry->right; iter->left; iter = iter->left);
+ else
+ iter = entry;
+
+ child = iter->left ? iter->left : iter->right;
+
+ if (!iter->parent)
+ tree->root = child;
+ else if (iter == iter->parent->left)
+ iter->parent->left = child;
+ else
+ iter->parent->right = child;
+
+ if (child) child->parent = iter->parent;
+ parent = iter->parent;
- while (*entry)
+ need_fixup = !wine_rb_is_red(iter);
+
+ if (entry != iter)
{
- if (tree->functions->compare(key, *entry) < 0)
- {
- wine_rb_stack_push(&tree->stack, entry);
- if (!wine_rb_is_red((*entry)->left) && !wine_rb_is_red((*entry)->left->left)) wine_rb_move_red_left(tree, entry);
- entry = &(*entry)->left;
- }
+ *iter = *entry;
+ if (!iter->parent)
+ tree->root = iter;
+ else if (entry == iter->parent->left)
+ iter->parent->left = iter;
else
- {
- if (wine_rb_is_red((*entry)->left)) wine_rb_rotate_right(tree, *entry);
- if (!tree->functions->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(tree, entry);
- if (!tree->functions->compare(key, *entry))
- {
- struct wine_rb_entry **e = &(*entry)->right;
- struct wine_rb_entry *m = *e;
- while (m->left) m = m->left;
+ iter->parent->right = iter;
- wine_rb_stack_push(&tree->stack, entry);
- (*entry)->flags |= WINE_RB_FLAG_STOP;
+ if (iter->right) iter->right->parent = iter;
+ if (iter->left) iter->left->parent = iter;
+ if (parent == entry) parent = iter;
+ }
- while ((*e)->left)
+ if (need_fixup)
+ {
+ while (parent && !wine_rb_is_red(child))
+ {
+ if (child == parent->left)
+ {
+ w = parent->right;
+ if (wine_rb_is_red(w))
{
- wine_rb_stack_push(&tree->stack, e);
- if (!wine_rb_is_red((*e)->left) && !wine_rb_is_red((*e)->left->left)) wine_rb_move_red_left(tree, e);
- e = &(*e)->left;
+ w->flags &= ~WINE_RB_FLAG_RED;
+ parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, parent, 0);
+ w = parent->right;
+ }
+ if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
+ {
+ if (!wine_rb_is_red(w->right))
+ {
+ w->left->flags &= ~WINE_RB_FLAG_RED;
+ w->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, w, 0);
+ w = parent->right;
+ }
+ w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
+ parent->flags &= ~WINE_RB_FLAG_RED;
+ if (w->right)
+ w->right->flags &= ~WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, parent, 0);
+ child = NULL;
+ break;
}
- *e = NULL;
- wine_rb_fixup(tree, &tree->stack);
-
- *m = **entry;
- *entry = m;
- if (m->right) m->right->parent = m;
- if (m->left) m->left->parent = m;
-
- break;
}
else
{
- wine_rb_stack_push(&tree->stack, entry);
- entry = &(*entry)->right;
+ w = parent->left;
+ if (wine_rb_is_red(w))
+ {
+ w->flags &= ~WINE_RB_FLAG_RED;
+ parent->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, parent, 0);
+ w = parent->left;
+ }
+ if (wine_rb_is_red(w->left) || wine_rb_is_red(w->right))
+ {
+ if (!wine_rb_is_red(w->left))
+ {
+ w->right->flags &= ~WINE_RB_FLAG_RED;
+ w->flags |= WINE_RB_FLAG_RED;
+ wine_rb_rotate_left(tree, w, 0);
+ w = parent->left;
+ }
+ w->flags = (w->flags & ~WINE_RB_FLAG_RED) | (parent->flags & WINE_RB_FLAG_RED);
+ parent->flags &= ~WINE_RB_FLAG_RED;
+ if (w->left)
+ w->left->flags &= ~WINE_RB_FLAG_RED;
+ wine_rb_rotate_right(tree, parent, 0);
+ child = NULL;
+ break;
+ }
}
+ w->flags |= WINE_RB_FLAG_RED;
+ child = parent;
+ parent = child->parent;
}
+ if (child) child->flags &= ~WINE_RB_FLAG_RED;
}
- wine_rb_fixup(tree, &tree->stack);
if (tree->root) tree->root->flags &= ~WINE_RB_FLAG_RED;
}
More information about the wine-cvs
mailing list