[njs] Using nxt_rbtree_destroy_next() iterator for nxt_mem_cache_pool

[Igor Sysoev]

details:   http://hg.nginx.org/njs/rev/6bda82d5bd54
branches:  
changeset: 312:6bda82d5bd54
user:      Igor Sysoev <igor at sysoev.ru>
date:      Sun Mar 12 22:40:13 2017 +0300
description:
Using nxt_rbtree_destroy_next() iterator for nxt_mem_cache_pool
destruction without rbtree rebalancing.

diffstat:

 nxt/nxt_mem_cache_pool.c |  13 +++++--------
 nxt/nxt_rbtree.c         |  34 ++++++++++++++++++++++++++++++++++
 nxt/nxt_rbtree.h         |  11 +++++++++++
 3 files changed, 50 insertions(+), 8 deletions(-)

diffs (90 lines):

diff -r 214afa2466a0 -r 6bda82d5bd54 nxt/nxt_mem_cache_pool.c
--- a/nxt/nxt_mem_cache_pool.c	Wed Feb 01 11:33:05 2017 +0300
+++ b/nxt/nxt_mem_cache_pool.c	Sun Mar 12 22:40:13 2017 +0300
@@ -257,20 +257,17 @@ nxt_mem_cache_pool_is_empty(nxt_mem_cach
 void
 nxt_mem_cache_pool_destroy(nxt_mem_cache_pool_t *pool)
 {
-    void                  *p;
+    void                   *p;
     nxt_rbtree_node_t      *node, *next;
     nxt_mem_cache_block_t  *block;
 
-    for (node = nxt_rbtree_min(&pool->blocks);
-         nxt_rbtree_is_there_successor(&pool->blocks, node);
-         node = next)
-    {
-        next = nxt_rbtree_node_successor(&pool->blocks, node);
+    next = nxt_rbtree_root(&pool->blocks);
 
+    while (next != nxt_rbtree_sentinel(&pool->blocks)) {
+
+        node = nxt_rbtree_destroy_next(&pool->blocks, &next);
         block = (nxt_mem_cache_block_t *) node;
 
-        nxt_rbtree_delete(&pool->blocks, &block->node);
-
         p = block->start;
 
         if (block->type != NXT_MEM_CACHE_EMBEDDED_BLOCK) {
diff -r 214afa2466a0 -r 6bda82d5bd54 nxt/nxt_rbtree.c
--- a/nxt/nxt_rbtree.c	Wed Feb 01 11:33:05 2017 +0300
+++ b/nxt/nxt_rbtree.c	Sun Mar 12 22:40:13 2017 +0300
@@ -495,3 +495,37 @@ nxt_rbtree_parent_relink(nxt_rbtree_node
     link = (node == parent->left) ? &parent->left : &parent->right;
     *link = subst;
 }
+
+
+nxt_rbtree_node_t *
+nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
+{
+    nxt_rbtree_node_t  *node, *subst, *parent, *sentinel;
+
+    sentinel = nxt_rbtree_sentinel(tree);
+
+    /* Find the leftmost node. */
+    for (node = *next; node->left != sentinel; node = node->left);
+
+    /* Replace the leftmost node with its right child. */
+    subst = node->right;
+    parent = node->parent;
+
+    parent->left = subst;
+    subst->parent = parent;
+
+    /*
+     * The right child is used as the next start node.  If the right child
+     * is the sentinel then parent of the leftmost node is used as the next
+     * start node.  The parent of the root node is the sentinel so after
+     * the single root node will be replaced with the sentinel, the next
+     * start node will be equal to the sentinel and iteration will stop.
+     */
+    if (subst == sentinel) {
+        subst = parent;
+    }
+
+    *next = subst;
+
+    return node;
+}
diff -r 214afa2466a0 -r 6bda82d5bd54 nxt/nxt_rbtree.h
--- a/nxt/nxt_rbtree.h	Wed Feb 01 11:33:05 2017 +0300
+++ b/nxt/nxt_rbtree.h	Sun Mar 12 22:40:13 2017 +0300
@@ -111,5 +111,16 @@ NXT_EXPORT nxt_rbtree_node_t
     nxt_rbtree_part_t *node);
 NXT_EXPORT void nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *node);
 
+/*
+ * nxt_rbtree_destroy_next() is iterator to use only while rbtree destruction.
+ * It deletes a node from rbtree and returns the node.  The rbtree is not
+ * rebalanced after deletion.  At the beginning the "next" parameter should
+ * be equal to rbtree root.  The iterator should be called in loop until
+ * the "next" parameter will be equal to the rbtree sentinel.  No other
+ * operations must be performed on the rbtree while destruction.
+ */
+NXT_EXPORT nxt_rbtree_node_t *nxt_rbtree_destroy_next(nxt_rbtree_t *tree,
+    nxt_rbtree_node_t **next);
+
 
 #endif /* _NXT_RBTREE_H_INCLUDED_ */