[nginx] Core: introduced ngx_rbtree_next().

[Maxim Dounin]

details:   http://hg.nginx.org/nginx/rev/e0cc454aafe4
branches:  
changeset: 6928:e0cc454aafe4
user:      Maxim Dounin <mdounin at mdounin.ru>
date:      Tue Mar 07 18:51:13 2017 +0300
description:
Core: introduced ngx_rbtree_next().

diffstat:

 src/core/ngx_rbtree.c |  29 +++++++++++++++++++++++++++++
 src/core/ngx_rbtree.h |   2 ++
 2 files changed, 31 insertions(+), 0 deletions(-)

diffs (48 lines):

diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
--- a/src/core/ngx_rbtree.c
+++ b/src/core/ngx_rbtree.c
@@ -378,3 +378,32 @@ ngx_rbtree_right_rotate(ngx_rbtree_node_
     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;
+    }
+}
diff --git a/src/core/ngx_rbtree.h b/src/core/ngx_rbtree.h
--- a/src/core/ngx_rbtree.h
+++ b/src/core/ngx_rbtree.h
@@ -54,6 +54,8 @@ void ngx_rbtree_insert_value(ngx_rbtree_
     ngx_rbtree_node_t *sentinel);
 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
+ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree,
+    ngx_rbtree_node_t *node);
 
 
 #define ngx_rbt_red(node)               ((node)->color = 1)