[njs] A small rbtree insert fixup optimization.

Igor Sysoev igor at sysoev.ru
Fri May 26 17:14:32 UTC 2017


details:   http://hg.nginx.org/njs/rev/7156ba123eae
branches:  
changeset: 343:7156ba123eae
user:      Igor Sysoev <igor at sysoev.ru>
date:      Fri May 26 20:10:22 2017 +0300
description:
A small rbtree insert fixup optimization.

Thanks to ??? (Hong Zhi Dao).

diffstat:

 nxt/nxt_rbtree.c |  13 +++++++++----
 1 files changed, 9 insertions(+), 4 deletions(-)

diffs (36 lines):

diff -r be8d68d4b8b5 -r 7156ba123eae nxt/nxt_rbtree.c
--- a/nxt/nxt_rbtree.c	Fri May 26 20:07:24 2017 +0300
+++ b/nxt/nxt_rbtree.c	Fri May 26 20:10:22 2017 +0300
@@ -129,11 +129,15 @@ nxt_rbtree_insert_fixup(nxt_rbtree_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->color = NXT_RBTREE_RED;
 
-                grandparent = parent->parent;
-                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_
                     nxt_rbtree_right_rotate(node);
                 }
 
+                /* See the comment in the symmetric branch above. */
                 parent = node->parent;
+
                 parent->color = NXT_RBTREE_BLACK;
+                grandparent->color = NXT_RBTREE_RED;
 
-                grandparent = parent->parent;
-                grandparent->color = NXT_RBTREE_RED;
                 nxt_rbtree_left_rotate(grandparent);
 
                 /* See the comment in the symmetric branch above. */


More information about the nginx-devel mailing list