diff options
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. */ |