Core: introduced ngx_rbtree_next().

1 files changed, 29 insertions, 0 deletions

diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
index 331254c6f..969d549c8 100644
--- a/src/core/ngx_rbtree.c
+++ b/src/core/ngx_rbtree.c
@@ -378,3 +378,32 @@ ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
     temp->right = node;
     node->parent = temp;
 }
+
+
+ngx_rbtree_node_t *
+ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
+{
+    ngx_rbtree_node_t  *root, *sentinel, *parent;
+
+    sentinel = tree->sentinel;
+
+    if (node->right != sentinel) {
+        return ngx_rbtree_min(node->right, sentinel);
+    }
+
+    root = tree->root;
+
+    for ( ;; ) {
+        parent = node->parent;
+
+        if (node == root) {
+            return NULL;
+        }
+
+        if (node == parent->left) {
+            return parent;
+        }
+
+        node = parent;
+    }
+}