details: http://hg.nginx.org/njs/rev/6bda82d5bd54
branches:
changeset: 312:6bda82d5bd54
user: Igor Sysoev <igor@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_ */
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel