Jacek Caban : rbtree.h: Use parent pointer instead of stack in wine_rb_postorder.

[Alexandre Julliard]

Module: wine
Branch: master
Commit: 20740d849e443bc47d1850791897394a12ff779a
URL:    http://source.winehq.org/git/wine.git/?a=commit;h=20740d849e443bc47d1850791897394a12ff779a

Author: Jacek Caban <jacek at 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 at codeweavers.com>
Signed-off-by: Alexandre Julliard <julliard at 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);
     }
 }