Module: wine Branch: master Commit: 20740d849e443bc47d1850791897394a12ff779a URL: http://source.winehq.org/git/wine.git/?a=commit;h=20740d849e443bc47d1850791… Author: Jacek Caban <jacek(a)codeweavers.com> Date: Mon Aug 15 21:53:26 2016 +0200 rbtree.h: Use parent pointer instead of stack in wine_rb_postorder. Signed-off-by: Jacek Caban <jacek(a)codeweavers.com> Signed-off-by: Alexandre Julliard <julliard(a)winehq.org> --- include/wine/rbtree.h | 49 +++++++++++++++++++++---------------------------- 1 file changed, 21 insertions(+), 28 deletions(-) diff --git a/include/wine/rbtree.h b/include/wine/rbtree.h index 11f42f7..2d364e3 100644 --- a/include/wine/rbtree.h +++ b/include/wine/rbtree.h @@ -59,8 +59,6 @@ typedef void (wine_rb_traverse_func_t)(struct wine_rb_entry *entry, void *contex #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 void wine_rb_stack_clear(struct wine_rb_stack *stack) { @@ -185,37 +183,32 @@ static inline void wine_rb_move_red_right(struct wine_rb_tree *tree, struct wine } } -static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) +static inline struct wine_rb_entry *wine_rb_postorder_head(struct wine_rb_entry *iter) { - struct wine_rb_entry **entry; - - if (!tree->root) return; + if (!iter) return NULL; - 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; - } + for (;;) { + while (iter->left) iter = iter->left; + if (!iter->right) return iter; + iter = iter->right; + } +} - 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; - } +static inline struct wine_rb_entry *wine_rb_postorder_next(struct wine_rb_entry *iter) +{ + if (!iter->parent) return NULL; + if (iter == iter->parent->right || !iter->parent->right) return iter->parent; + return wine_rb_postorder_head(iter->parent->right); +} - e->flags &= ~(WINE_RB_FLAG_TRAVERSED_LEFT | WINE_RB_FLAG_TRAVERSED_RIGHT); - callback(e, context); +static inline void wine_rb_postorder(struct wine_rb_tree *tree, wine_rb_traverse_func_t *callback, void *context) +{ + struct wine_rb_entry *iter, *next; - if (!tree->stack.count) break; - entry = tree->stack.entries[--tree->stack.count]; + for (iter = wine_rb_postorder_head(tree->root); iter; iter = next) + { + next = wine_rb_postorder_next(iter); + callback(iter, context); } }