diff options
| author | Igor Sysoev <igor@sysoev.ru> | 2017-05-26 19:12:47 +0300 |
|---|---|---|
| committer | Igor Sysoev <igor@sysoev.ru> | 2017-05-26 19:12:47 +0300 |
| commit | 4f9f4637990f0cf2811318a4c19c223b3d894d57 (patch) | |
| tree | 50ad69608bf46c7ce29a3f645683273b2cb992bf /src/nxt_rbtree.c | |
| parent | 48155f3a492beb101b5615dc7ff97f525133b434 (diff) | |
| download | unit-4f9f4637990f0cf2811318a4c19c223b3d894d57.tar.gz unit-4f9f4637990f0cf2811318a4c19c223b3d894d57.tar.bz2 | |
A small rbtree insert fixup optimization.
Thanks to 洪志道 (Hong Zhi Dao).
Diffstat (limited to 'src/nxt_rbtree.c')
| -rw-r--r-- | src/nxt_rbtree.c | 13 |
1 files changed, 9 insertions, 4 deletions
diff --git a/src/nxt_rbtree.c b/src/nxt_rbtree.c index fd64486f..66ff3665 100644 --- a/src/nxt_rbtree.c +++ b/src/nxt_rbtree.c @@ -126,11 +126,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 @@ -150,11 +154,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. */ |