From: Alexandre Julliard julliard@winehq.org
--- include/private/wine/rbtree.h | 54 ++++++++++++++++++++++++++++++----- 1 file changed, 47 insertions(+), 7 deletions(-)
diff --git a/include/private/wine/rbtree.h b/include/private/wine/rbtree.h index b5d38bca..81367f3f 100644 --- a/include/private/wine/rbtree.h +++ b/include/private/wine/rbtree.h @@ -101,6 +101,13 @@ static inline struct rb_entry *rb_head(struct rb_entry *iter) return iter; }
+static inline struct rb_entry *rb_tail(struct rb_entry *iter) +{ + if (!iter) return NULL; + while (iter->right) iter = iter->right; + return iter; +} + static inline struct rb_entry *rb_next(struct rb_entry *iter) { if (iter->right) return rb_head(iter->right); @@ -108,6 +115,13 @@ static inline struct rb_entry *rb_next(struct rb_entry *iter) return iter->parent; }
+static inline struct rb_entry *rb_prev(struct rb_entry *iter) +{ + if (iter->left) return rb_tail(iter->left); + while (iter->parent && iter->parent->left == iter) iter = iter->parent; + return iter->parent; +} + static inline struct rb_entry *rb_postorder_head(struct rb_entry *iter) { if (!iter) return NULL; @@ -145,7 +159,7 @@ static inline struct rb_entry *rb_postorder_next(struct rb_entry *iter) /* iterate through the tree using a tree entry and postorder, making it safe to free the entry */ #define RB_FOR_EACH_ENTRY_DESTRUCTOR(elem, elem2, tree, type, field) \ for ((elem) = RB_ENTRY_VALUE(rb_postorder_head((tree)->root), type, field); \ - (elem) != WINE_RB_ENTRY_VALUE(0, type, field) \ + (elem) != RB_ENTRY_VALUE(0, type, field) \ && (((elem2) = RB_ENTRY_VALUE(rb_postorder_next(&(elem)->field), type, field)) || 1); \ (elem) = (elem2))
@@ -168,18 +182,13 @@ static inline void rb_for_each_entry(struct rb_tree *tree, rb_traverse_func *cal RB_FOR_EACH(iter, tree) callback(iter, context); }
-static inline void rb_clear(struct rb_tree *tree, rb_traverse_func *callback, void *context) +static inline void rb_destroy(struct rb_tree *tree, rb_traverse_func *callback, void *context) { /* Note that we use postorder here because the callback will likely free the entry. */ if (callback) rb_postorder(tree, callback, context); tree->root = NULL; }
-static inline void rb_destroy(struct rb_tree *tree, rb_traverse_func *callback, void *context) -{ - rb_clear(tree, callback, context); -} - static inline struct rb_entry *rb_get(const struct rb_tree *tree, const void *key) { struct rb_entry *entry = tree->root; @@ -375,4 +384,35 @@ static inline void rb_remove_key(struct rb_tree *tree, const void *key) if (entry) rb_remove(tree, entry); }
+static inline void rb_replace(struct rb_tree *tree, struct rb_entry *dst, struct rb_entry *src) +{ + if (!(src->parent = dst->parent)) + tree->root = src; + else if (dst->parent->left == dst) + dst->parent->left = src; + else + dst->parent->right = src; + + if ((src->left = dst->left)) + src->left->parent = src; + if ((src->right = dst->right)) + src->right->parent = src; + src->flags = dst->flags; +} + +/* old names for backwards compatibility */ +#define wine_rb_entry rb_entry +#define wine_rb_tree rb_tree +#define wine_rb_init rb_init +#define wine_rb_for_each_entry rb_for_each_entry +#define wine_rb_destroy rb_destroy +#define wine_rb_get rb_get +#define wine_rb_put rb_put +#define wine_rb_remove rb_remove +#define wine_rb_remove_key rb_remove_key +#define wine_rb_replace rb_replace +#define WINE_RB_ENTRY_VALUE RB_ENTRY_VALUE +#define WINE_RB_FOR_EACH_ENTRY RB_FOR_EACH_ENTRY +#define WINE_RB_FOR_EACH_ENTRY_DESTRUCTOR RB_FOR_EACH_ENTRY_DESTRUCTOR + #endif /* __WINE_WINE_RBTREE_H */