From 4bf4fd5e41e59b0c983c2824bd32ebd0385e99ab Mon Sep 17 00:00:00 2001 From: Igor Sysoev Date: Fri, 26 May 2017 20:10:22 +0300 Subject: [PATCH] A small rbtree insert fixup optimization. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Thanks to 洪志道 (Hong Zhi Dao). --- nxt/nxt_rbtree.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) diff --git a/nxt/nxt_rbtree.c b/nxt/nxt_rbtree.c index 18e8acca..6b5cd1be 100644 --- a/nxt/nxt_rbtree.c +++ b/nxt/nxt_rbtree.c @@ -129,11 +129,15 @@ nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node) nxt_rbtree_left_rotate(node); } + /* + * nxt_rbtree_left_rotate() swaps parent and + * child whilst keeps grandparent the same. + */ parent = node->parent; - parent->color = NXT_RBTREE_BLACK; - grandparent = parent->parent; + parent->color = NXT_RBTREE_BLACK; grandparent->color = NXT_RBTREE_RED; + nxt_rbtree_right_rotate(grandparent); /* * nxt_rbtree_right_rotate() does not change node->parent @@ -153,11 +157,12 @@ nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node) nxt_rbtree_right_rotate(node); } + /* See the comment in the symmetric branch above. */ parent = node->parent; - parent->color = NXT_RBTREE_BLACK; - grandparent = parent->parent; + parent->color = NXT_RBTREE_BLACK; grandparent->color = NXT_RBTREE_RED; + nxt_rbtree_left_rotate(grandparent); /* See the comment in the symmetric branch above. */ -- 2.47.3