From 97c569b7808171f8695552025bd4c93b5c101dc8 Mon Sep 17 00:00:00 2001 From: Igor Sysoev Date: Mon, 29 May 2017 10:17:36 +0300 Subject: [PATCH] A small rbtree delete fixup optimization. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Setting node color to black is not required here because it is already black. Besides in the original algorithm the node pointer is discarded and the node is set to tree root just to quit the loop. Thanks to 洪志道 (Hong Zhi Dao). --- nxt/nxt_rbtree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/nxt/nxt_rbtree.c b/nxt/nxt_rbtree.c index 6b5cd1be..390464f6 100644 --- a/nxt/nxt_rbtree.c +++ b/nxt/nxt_rbtree.c @@ -402,7 +402,7 @@ nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) nxt_rbtree_left_rotate(parent); - break; + return; } else { sibling = parent->left; @@ -440,7 +440,7 @@ nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) nxt_rbtree_right_rotate(parent); - break; + return; } } -- 2.47.3