xref: /unit/src/nxt_rbtree.c (revision 50:3a785db4b3ad)
10Sigor@sysoev.ru 
20Sigor@sysoev.ru /*
30Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
40Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
50Sigor@sysoev.ru  */
60Sigor@sysoev.ru 
70Sigor@sysoev.ru #include <nxt_main.h>
80Sigor@sysoev.ru 
90Sigor@sysoev.ru 
100Sigor@sysoev.ru /*
110Sigor@sysoev.ru  * The red-black tree code is based on the algorithm described in
120Sigor@sysoev.ru  * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
130Sigor@sysoev.ru  */
140Sigor@sysoev.ru 
150Sigor@sysoev.ru 
160Sigor@sysoev.ru static void nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node);
170Sigor@sysoev.ru static void nxt_rbtree_delete_fixup(nxt_rbtree_t *tree,
180Sigor@sysoev.ru     nxt_rbtree_node_t *node);
190Sigor@sysoev.ru nxt_inline void nxt_rbtree_left_rotate(nxt_rbtree_node_t *node);
200Sigor@sysoev.ru nxt_inline void nxt_rbtree_right_rotate(nxt_rbtree_node_t *node);
210Sigor@sysoev.ru nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst,
220Sigor@sysoev.ru     nxt_rbtree_node_t *node);
230Sigor@sysoev.ru 
240Sigor@sysoev.ru 
250Sigor@sysoev.ru #define NXT_RBTREE_BLACK  0
260Sigor@sysoev.ru #define NXT_RBTREE_RED    1
270Sigor@sysoev.ru 
280Sigor@sysoev.ru 
290Sigor@sysoev.ru #define nxt_rbtree_comparison_callback(tree)                                  \
300Sigor@sysoev.ru     ((nxt_rbtree_compare_t) (tree)->sentinel.right)
310Sigor@sysoev.ru 
320Sigor@sysoev.ru 
330Sigor@sysoev.ru void
nxt_rbtree_init(nxt_rbtree_t * tree,nxt_rbtree_compare_t compare)345Sigor@sysoev.ru nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare)
350Sigor@sysoev.ru {
360Sigor@sysoev.ru     /*
370Sigor@sysoev.ru      * The sentinel is used as a leaf node sentinel and as a tree root
380Sigor@sysoev.ru      * sentinel: it is a parent of a root node and the root node is
390Sigor@sysoev.ru      * the left child of the sentinel.  Combining two sentinels in one
400Sigor@sysoev.ru      * entry and the fact that the sentinel's left child is a root node
410Sigor@sysoev.ru      * simplifies nxt_rbtree_node_successor() and eliminates explicit
420Sigor@sysoev.ru      * root node test before or inside nxt_rbtree_min().
430Sigor@sysoev.ru      */
440Sigor@sysoev.ru 
450Sigor@sysoev.ru     /* The root is empty. */
460Sigor@sysoev.ru     tree->sentinel.left = &tree->sentinel;
470Sigor@sysoev.ru 
480Sigor@sysoev.ru     /*
495Sigor@sysoev.ru      * The sentinel's right child is never used so
505Sigor@sysoev.ru      * comparison callback can be safely stored here.
510Sigor@sysoev.ru      */
525Sigor@sysoev.ru     tree->sentinel.right = (void *) compare;
530Sigor@sysoev.ru 
540Sigor@sysoev.ru     /* The root and leaf sentinel must be black. */
550Sigor@sysoev.ru     tree->sentinel.color = NXT_RBTREE_BLACK;
560Sigor@sysoev.ru }
570Sigor@sysoev.ru 
580Sigor@sysoev.ru 
590Sigor@sysoev.ru void
nxt_rbtree_insert(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)600Sigor@sysoev.ru nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
610Sigor@sysoev.ru {
620Sigor@sysoev.ru     nxt_rbtree_node_t     *node, *new_node, *sentinel, **child;
630Sigor@sysoev.ru     nxt_rbtree_compare_t  compare;
640Sigor@sysoev.ru 
650Sigor@sysoev.ru     new_node = (nxt_rbtree_node_t *) part;
660Sigor@sysoev.ru 
670Sigor@sysoev.ru     node = nxt_rbtree_root(tree);
680Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
690Sigor@sysoev.ru 
700Sigor@sysoev.ru     new_node->left = sentinel;
710Sigor@sysoev.ru     new_node->right = sentinel;
720Sigor@sysoev.ru     new_node->color = NXT_RBTREE_RED;
730Sigor@sysoev.ru 
745Sigor@sysoev.ru     compare = (nxt_rbtree_compare_t) tree->sentinel.right;
755Sigor@sysoev.ru     child = &nxt_rbtree_root(tree);
760Sigor@sysoev.ru 
775Sigor@sysoev.ru     while (*child != sentinel) {
785Sigor@sysoev.ru         node = *child;
790Sigor@sysoev.ru 
805Sigor@sysoev.ru         nxt_prefetch(node->left);
815Sigor@sysoev.ru         nxt_prefetch(node->right);
820Sigor@sysoev.ru 
835Sigor@sysoev.ru         child = (compare(new_node, node) < 0) ? &node->left : &node->right;
845Sigor@sysoev.ru     }
850Sigor@sysoev.ru 
865Sigor@sysoev.ru     *child = new_node;
875Sigor@sysoev.ru     new_node->parent = node;
880Sigor@sysoev.ru 
890Sigor@sysoev.ru     nxt_rbtree_insert_fixup(new_node);
900Sigor@sysoev.ru 
910Sigor@sysoev.ru     node = nxt_rbtree_root(tree);
920Sigor@sysoev.ru     node->color = NXT_RBTREE_BLACK;
930Sigor@sysoev.ru }
940Sigor@sysoev.ru 
950Sigor@sysoev.ru 
960Sigor@sysoev.ru static void
nxt_rbtree_insert_fixup(nxt_rbtree_node_t * node)970Sigor@sysoev.ru nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
980Sigor@sysoev.ru {
990Sigor@sysoev.ru     nxt_rbtree_node_t  *parent, *grandparent, *uncle;
1000Sigor@sysoev.ru 
1010Sigor@sysoev.ru     /*
1020Sigor@sysoev.ru      * Prefetching parent nodes does not help here because they are
1030Sigor@sysoev.ru      * already traversed during insertion.
1040Sigor@sysoev.ru      */
1050Sigor@sysoev.ru 
1060Sigor@sysoev.ru     for ( ;; ) {
1070Sigor@sysoev.ru         parent = node->parent;
1080Sigor@sysoev.ru 
1090Sigor@sysoev.ru         /*
1100Sigor@sysoev.ru          * Testing whether a node is a tree root is not required here since
1110Sigor@sysoev.ru          * a root node's parent is the sentinel and it is always black.
1120Sigor@sysoev.ru          */
1130Sigor@sysoev.ru         if (parent->color == NXT_RBTREE_BLACK) {
1140Sigor@sysoev.ru             return;
1150Sigor@sysoev.ru         }
1160Sigor@sysoev.ru 
1170Sigor@sysoev.ru         grandparent = parent->parent;
1180Sigor@sysoev.ru 
1190Sigor@sysoev.ru         if (parent == grandparent->left) {
1200Sigor@sysoev.ru             uncle = grandparent->right;
1210Sigor@sysoev.ru 
1220Sigor@sysoev.ru             if (uncle->color == NXT_RBTREE_BLACK) {
1230Sigor@sysoev.ru 
1240Sigor@sysoev.ru                 if (node == parent->right) {
1250Sigor@sysoev.ru                     node = parent;
1260Sigor@sysoev.ru                     nxt_rbtree_left_rotate(node);
1270Sigor@sysoev.ru                 }
1280Sigor@sysoev.ru 
12948Sigor@sysoev.ru                 /*
13048Sigor@sysoev.ru                  * nxt_rbtree_left_rotate() swaps parent and
13148Sigor@sysoev.ru                  * child whilst keeps grandparent the same.
13248Sigor@sysoev.ru                  */
1330Sigor@sysoev.ru                 parent = node->parent;
1340Sigor@sysoev.ru 
13548Sigor@sysoev.ru                 parent->color = NXT_RBTREE_BLACK;
1360Sigor@sysoev.ru                 grandparent->color = NXT_RBTREE_RED;
13748Sigor@sysoev.ru 
1380Sigor@sysoev.ru                 nxt_rbtree_right_rotate(grandparent);
1395Sigor@sysoev.ru                 /*
1405Sigor@sysoev.ru                  * nxt_rbtree_right_rotate() does not change node->parent
1415Sigor@sysoev.ru                  * color which is now black, so testing color is not required
1425Sigor@sysoev.ru                  * to return from function.
1435Sigor@sysoev.ru                  */
1445Sigor@sysoev.ru                 return;
1450Sigor@sysoev.ru             }
1460Sigor@sysoev.ru 
1470Sigor@sysoev.ru         } else {
1480Sigor@sysoev.ru             uncle = grandparent->left;
1490Sigor@sysoev.ru 
1500Sigor@sysoev.ru             if (uncle->color == NXT_RBTREE_BLACK) {
1510Sigor@sysoev.ru 
1520Sigor@sysoev.ru                 if (node == parent->left) {
1530Sigor@sysoev.ru                     node = parent;
1540Sigor@sysoev.ru                     nxt_rbtree_right_rotate(node);
1550Sigor@sysoev.ru                 }
1560Sigor@sysoev.ru 
15748Sigor@sysoev.ru                 /* See the comment in the symmetric branch above. */
1580Sigor@sysoev.ru                 parent = node->parent;
1590Sigor@sysoev.ru 
16048Sigor@sysoev.ru                 parent->color = NXT_RBTREE_BLACK;
1610Sigor@sysoev.ru                 grandparent->color = NXT_RBTREE_RED;
16248Sigor@sysoev.ru 
1630Sigor@sysoev.ru                 nxt_rbtree_left_rotate(grandparent);
1640Sigor@sysoev.ru 
1655Sigor@sysoev.ru                 /* See the comment in the symmetric branch above. */
1665Sigor@sysoev.ru                 return;
1670Sigor@sysoev.ru             }
1680Sigor@sysoev.ru         }
1690Sigor@sysoev.ru 
1700Sigor@sysoev.ru         uncle->color = NXT_RBTREE_BLACK;
1710Sigor@sysoev.ru         parent->color = NXT_RBTREE_BLACK;
1720Sigor@sysoev.ru         grandparent->color = NXT_RBTREE_RED;
1730Sigor@sysoev.ru 
1740Sigor@sysoev.ru         node = grandparent;
1750Sigor@sysoev.ru     }
1760Sigor@sysoev.ru }
1770Sigor@sysoev.ru 
1780Sigor@sysoev.ru 
1790Sigor@sysoev.ru nxt_rbtree_node_t *
nxt_rbtree_find(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)1800Sigor@sysoev.ru nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
1810Sigor@sysoev.ru {
1825Sigor@sysoev.ru     intptr_t              n;
1830Sigor@sysoev.ru     nxt_rbtree_node_t     *node, *next, *sentinel;
1840Sigor@sysoev.ru     nxt_rbtree_compare_t  compare;
1850Sigor@sysoev.ru 
1860Sigor@sysoev.ru     node = (nxt_rbtree_node_t *) part;
1870Sigor@sysoev.ru 
1880Sigor@sysoev.ru     next = nxt_rbtree_root(tree);
1890Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
1900Sigor@sysoev.ru     compare = nxt_rbtree_comparison_callback(tree);
1910Sigor@sysoev.ru 
1920Sigor@sysoev.ru     while (next != sentinel) {
1930Sigor@sysoev.ru         nxt_prefetch(next->left);
1940Sigor@sysoev.ru         nxt_prefetch(next->right);
1950Sigor@sysoev.ru 
1960Sigor@sysoev.ru         n = compare(node, next);
1970Sigor@sysoev.ru 
1980Sigor@sysoev.ru         if (n < 0) {
1990Sigor@sysoev.ru             next = next->left;
2000Sigor@sysoev.ru 
2010Sigor@sysoev.ru         } else if (n > 0) {
2020Sigor@sysoev.ru             next = next->right;
2030Sigor@sysoev.ru 
2040Sigor@sysoev.ru         } else {
2050Sigor@sysoev.ru             return next;
2060Sigor@sysoev.ru         }
2070Sigor@sysoev.ru     }
2080Sigor@sysoev.ru 
2090Sigor@sysoev.ru     return NULL;
2100Sigor@sysoev.ru }
2110Sigor@sysoev.ru 
2120Sigor@sysoev.ru 
2130Sigor@sysoev.ru nxt_rbtree_node_t *
nxt_rbtree_find_less_or_equal(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)2140Sigor@sysoev.ru nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
2150Sigor@sysoev.ru {
2165Sigor@sysoev.ru     intptr_t              n;
2170Sigor@sysoev.ru     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
2180Sigor@sysoev.ru     nxt_rbtree_compare_t  compare;
2190Sigor@sysoev.ru 
2200Sigor@sysoev.ru     node = (nxt_rbtree_node_t *) part;
2210Sigor@sysoev.ru 
2220Sigor@sysoev.ru     retval = NULL;
2230Sigor@sysoev.ru     next = nxt_rbtree_root(tree);
2240Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
2250Sigor@sysoev.ru     compare = nxt_rbtree_comparison_callback(tree);
2260Sigor@sysoev.ru 
2270Sigor@sysoev.ru     while (next != sentinel) {
2280Sigor@sysoev.ru         nxt_prefetch(next->left);
2290Sigor@sysoev.ru         nxt_prefetch(next->right);
2300Sigor@sysoev.ru 
2310Sigor@sysoev.ru         n = compare(node, next);
2320Sigor@sysoev.ru 
2330Sigor@sysoev.ru         if (n < 0) {
2340Sigor@sysoev.ru             next = next->left;
2350Sigor@sysoev.ru 
2360Sigor@sysoev.ru         } else if (n > 0) {
2370Sigor@sysoev.ru             retval = next;
2380Sigor@sysoev.ru             next = next->right;
2390Sigor@sysoev.ru 
2400Sigor@sysoev.ru         } else {
2410Sigor@sysoev.ru             /* Exact match. */
2420Sigor@sysoev.ru             return next;
2430Sigor@sysoev.ru         }
2440Sigor@sysoev.ru     }
2450Sigor@sysoev.ru 
2460Sigor@sysoev.ru     return retval;
2470Sigor@sysoev.ru }
2480Sigor@sysoev.ru 
2490Sigor@sysoev.ru 
2500Sigor@sysoev.ru nxt_rbtree_node_t *
nxt_rbtree_find_greater_or_equal(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)2510Sigor@sysoev.ru nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
2520Sigor@sysoev.ru {
2535Sigor@sysoev.ru     intptr_t              n;
2540Sigor@sysoev.ru     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
2550Sigor@sysoev.ru     nxt_rbtree_compare_t  compare;
2560Sigor@sysoev.ru 
2570Sigor@sysoev.ru     node = (nxt_rbtree_node_t *) part;
2580Sigor@sysoev.ru 
2590Sigor@sysoev.ru     retval = NULL;
2600Sigor@sysoev.ru     next = nxt_rbtree_root(tree);
2610Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
2620Sigor@sysoev.ru     compare = nxt_rbtree_comparison_callback(tree);
2630Sigor@sysoev.ru 
2640Sigor@sysoev.ru     while (next != sentinel) {
2650Sigor@sysoev.ru         nxt_prefetch(next->left);
2660Sigor@sysoev.ru         nxt_prefetch(next->right);
2670Sigor@sysoev.ru 
2680Sigor@sysoev.ru         n = compare(node, next);
2690Sigor@sysoev.ru 
2700Sigor@sysoev.ru         if (n < 0) {
2710Sigor@sysoev.ru             retval = next;
2720Sigor@sysoev.ru             next = next->left;
2730Sigor@sysoev.ru 
2740Sigor@sysoev.ru         } else if (n > 0) {
2750Sigor@sysoev.ru             next = next->right;
2760Sigor@sysoev.ru 
2770Sigor@sysoev.ru         } else {
2780Sigor@sysoev.ru             /* Exact match. */
2790Sigor@sysoev.ru             return next;
2800Sigor@sysoev.ru         }
2810Sigor@sysoev.ru     }
2820Sigor@sysoev.ru 
2830Sigor@sysoev.ru     return retval;
2840Sigor@sysoev.ru }
2850Sigor@sysoev.ru 
2860Sigor@sysoev.ru 
2870Sigor@sysoev.ru void
nxt_rbtree_delete(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)2880Sigor@sysoev.ru nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
2890Sigor@sysoev.ru {
2905Sigor@sysoev.ru     uint8_t            color;
2910Sigor@sysoev.ru     nxt_rbtree_node_t  *node, *sentinel, *subst, *child;
2920Sigor@sysoev.ru 
2930Sigor@sysoev.ru     node = (nxt_rbtree_node_t *) part;
2940Sigor@sysoev.ru 
2950Sigor@sysoev.ru     subst = node;
2960Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
2970Sigor@sysoev.ru 
2980Sigor@sysoev.ru     if (node->left == sentinel) {
2990Sigor@sysoev.ru         child = node->right;
3000Sigor@sysoev.ru 
3010Sigor@sysoev.ru     } else if (node->right == sentinel) {
3020Sigor@sysoev.ru         child = node->left;
3030Sigor@sysoev.ru 
3040Sigor@sysoev.ru     } else {
3050Sigor@sysoev.ru         subst = nxt_rbtree_branch_min(tree, node->right);
3060Sigor@sysoev.ru         child = subst->right;
3070Sigor@sysoev.ru     }
3080Sigor@sysoev.ru 
3090Sigor@sysoev.ru     nxt_rbtree_parent_relink(child, subst);
3100Sigor@sysoev.ru 
3110Sigor@sysoev.ru     color = subst->color;
3120Sigor@sysoev.ru 
3130Sigor@sysoev.ru     if (subst != node) {
3140Sigor@sysoev.ru         /* Move the subst node to the deleted node position in the tree. */
3150Sigor@sysoev.ru 
3160Sigor@sysoev.ru         subst->color = node->color;
3170Sigor@sysoev.ru 
3180Sigor@sysoev.ru         subst->left = node->left;
3190Sigor@sysoev.ru         subst->left->parent = subst;
3200Sigor@sysoev.ru 
3210Sigor@sysoev.ru         subst->right = node->right;
3220Sigor@sysoev.ru         subst->right->parent = subst;
3230Sigor@sysoev.ru 
3240Sigor@sysoev.ru         nxt_rbtree_parent_relink(subst, node);
3250Sigor@sysoev.ru     }
3260Sigor@sysoev.ru 
3270Sigor@sysoev.ru #if (NXT_DEBUG)
3280Sigor@sysoev.ru     node->left = NULL;
3290Sigor@sysoev.ru     node->right = NULL;
3300Sigor@sysoev.ru     node->parent = NULL;
3310Sigor@sysoev.ru #endif
3320Sigor@sysoev.ru 
3330Sigor@sysoev.ru     if (color == NXT_RBTREE_BLACK) {
3340Sigor@sysoev.ru         nxt_rbtree_delete_fixup(tree, child);
3350Sigor@sysoev.ru     }
3360Sigor@sysoev.ru }
3370Sigor@sysoev.ru 
3380Sigor@sysoev.ru 
3390Sigor@sysoev.ru static void
nxt_rbtree_delete_fixup(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)3400Sigor@sysoev.ru nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
3410Sigor@sysoev.ru {
3420Sigor@sysoev.ru     nxt_rbtree_node_t  *parent, *sibling;
3430Sigor@sysoev.ru 
3440Sigor@sysoev.ru     while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) {
3450Sigor@sysoev.ru         /*
3460Sigor@sysoev.ru          * Prefetching parent nodes does not help here according
3470Sigor@sysoev.ru          * to microbenchmarks.
3480Sigor@sysoev.ru          */
3490Sigor@sysoev.ru 
3500Sigor@sysoev.ru         parent = node->parent;
3510Sigor@sysoev.ru 
3520Sigor@sysoev.ru         if (node == parent->left) {
3530Sigor@sysoev.ru             sibling = parent->right;
3540Sigor@sysoev.ru 
3550Sigor@sysoev.ru             if (sibling->color != NXT_RBTREE_BLACK) {
3560Sigor@sysoev.ru 
3570Sigor@sysoev.ru                 sibling->color = NXT_RBTREE_BLACK;
3580Sigor@sysoev.ru                 parent->color = NXT_RBTREE_RED;
3590Sigor@sysoev.ru 
3600Sigor@sysoev.ru                 nxt_rbtree_left_rotate(parent);
3610Sigor@sysoev.ru 
3620Sigor@sysoev.ru                 sibling = parent->right;
3630Sigor@sysoev.ru             }
3640Sigor@sysoev.ru 
3650Sigor@sysoev.ru             if (sibling->right->color == NXT_RBTREE_BLACK) {
3660Sigor@sysoev.ru 
3670Sigor@sysoev.ru                 sibling->color = NXT_RBTREE_RED;
3680Sigor@sysoev.ru 
3690Sigor@sysoev.ru                 if (sibling->left->color == NXT_RBTREE_BLACK) {
3700Sigor@sysoev.ru                     node = parent;
3710Sigor@sysoev.ru                     continue;
3720Sigor@sysoev.ru                 }
3730Sigor@sysoev.ru 
3740Sigor@sysoev.ru                 sibling->left->color = NXT_RBTREE_BLACK;
3750Sigor@sysoev.ru 
3760Sigor@sysoev.ru                 nxt_rbtree_right_rotate(sibling);
3770Sigor@sysoev.ru                 /*
3780Sigor@sysoev.ru                  * If the node is the leaf sentinel then the right
3790Sigor@sysoev.ru                  * rotate above changes its parent so a sibling below
3800Sigor@sysoev.ru                  * becames the leaf sentinel as well and this causes
3810Sigor@sysoev.ru                  * segmentation fault.  This is the reason why usual
3820Sigor@sysoev.ru                  * red-black tree implementations with a leaf sentinel
3830Sigor@sysoev.ru                  * which does not require to test leaf nodes at all
3840Sigor@sysoev.ru                  * nevertheless test the leaf sentinel in the left and
3850Sigor@sysoev.ru                  * right rotate procedures.  Since according to the
3860Sigor@sysoev.ru                  * algorithm node->parent must not be changed by both
3870Sigor@sysoev.ru                  * the left and right rotates above, it can be cached
3880Sigor@sysoev.ru                  * in a local variable.  This not only eliminates the
3890Sigor@sysoev.ru                  * sentinel test in nxt_rbtree_parent_relink() but also
3900Sigor@sysoev.ru                  * decreases the code size because C forces to reload
3910Sigor@sysoev.ru                  * non-restrict pointers.
3920Sigor@sysoev.ru                  */
3930Sigor@sysoev.ru                 sibling = parent->right;
3940Sigor@sysoev.ru             }
3950Sigor@sysoev.ru 
3960Sigor@sysoev.ru             sibling->color = parent->color;
3970Sigor@sysoev.ru             parent->color = NXT_RBTREE_BLACK;
3980Sigor@sysoev.ru             sibling->right->color = NXT_RBTREE_BLACK;
3990Sigor@sysoev.ru 
4000Sigor@sysoev.ru             nxt_rbtree_left_rotate(parent);
4010Sigor@sysoev.ru 
402*50Sigor@sysoev.ru             return;
4030Sigor@sysoev.ru 
4040Sigor@sysoev.ru         } else {
4050Sigor@sysoev.ru             sibling = parent->left;
4060Sigor@sysoev.ru 
4070Sigor@sysoev.ru             if (sibling->color != NXT_RBTREE_BLACK) {
4080Sigor@sysoev.ru 
4090Sigor@sysoev.ru                 sibling->color = NXT_RBTREE_BLACK;
4100Sigor@sysoev.ru                 parent->color = NXT_RBTREE_RED;
4110Sigor@sysoev.ru 
4120Sigor@sysoev.ru                 nxt_rbtree_right_rotate(parent);
4130Sigor@sysoev.ru 
4140Sigor@sysoev.ru                 sibling = parent->left;
4150Sigor@sysoev.ru             }
4160Sigor@sysoev.ru 
4170Sigor@sysoev.ru             if (sibling->left->color == NXT_RBTREE_BLACK) {
4180Sigor@sysoev.ru 
4190Sigor@sysoev.ru                 sibling->color = NXT_RBTREE_RED;
4200Sigor@sysoev.ru 
4210Sigor@sysoev.ru                 if (sibling->right->color == NXT_RBTREE_BLACK) {
4220Sigor@sysoev.ru                     node = parent;
4230Sigor@sysoev.ru                     continue;
4240Sigor@sysoev.ru                 }
4250Sigor@sysoev.ru 
4260Sigor@sysoev.ru                 sibling->right->color = NXT_RBTREE_BLACK;
4270Sigor@sysoev.ru 
4280Sigor@sysoev.ru                 nxt_rbtree_left_rotate(sibling);
4290Sigor@sysoev.ru 
4300Sigor@sysoev.ru                 /* See the comment in the symmetric branch above. */
4310Sigor@sysoev.ru                 sibling = parent->left;
4320Sigor@sysoev.ru             }
4330Sigor@sysoev.ru 
4340Sigor@sysoev.ru             sibling->color = parent->color;
4350Sigor@sysoev.ru             parent->color = NXT_RBTREE_BLACK;
4360Sigor@sysoev.ru             sibling->left->color = NXT_RBTREE_BLACK;
4370Sigor@sysoev.ru 
4380Sigor@sysoev.ru             nxt_rbtree_right_rotate(parent);
4390Sigor@sysoev.ru 
440*50Sigor@sysoev.ru             return;
4410Sigor@sysoev.ru         }
4420Sigor@sysoev.ru     }
4430Sigor@sysoev.ru 
4440Sigor@sysoev.ru     node->color = NXT_RBTREE_BLACK;
4450Sigor@sysoev.ru }
4460Sigor@sysoev.ru 
4470Sigor@sysoev.ru 
4480Sigor@sysoev.ru nxt_inline void
nxt_rbtree_left_rotate(nxt_rbtree_node_t * node)4490Sigor@sysoev.ru nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
4500Sigor@sysoev.ru {
4510Sigor@sysoev.ru     nxt_rbtree_node_t  *child;
4520Sigor@sysoev.ru 
4530Sigor@sysoev.ru     child = node->right;
4540Sigor@sysoev.ru     node->right = child->left;
4550Sigor@sysoev.ru     child->left->parent = node;
4560Sigor@sysoev.ru     child->left = node;
4570Sigor@sysoev.ru 
4580Sigor@sysoev.ru     nxt_rbtree_parent_relink(child, node);
4590Sigor@sysoev.ru 
4600Sigor@sysoev.ru     node->parent = child;
4610Sigor@sysoev.ru }
4620Sigor@sysoev.ru 
4630Sigor@sysoev.ru 
4640Sigor@sysoev.ru nxt_inline void
nxt_rbtree_right_rotate(nxt_rbtree_node_t * node)4650Sigor@sysoev.ru nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
4660Sigor@sysoev.ru {
4670Sigor@sysoev.ru     nxt_rbtree_node_t  *child;
4680Sigor@sysoev.ru 
4690Sigor@sysoev.ru     child = node->left;
4700Sigor@sysoev.ru     node->left = child->right;
4710Sigor@sysoev.ru     child->right->parent = node;
4720Sigor@sysoev.ru     child->right = node;
4730Sigor@sysoev.ru 
4740Sigor@sysoev.ru     nxt_rbtree_parent_relink(child, node);
4750Sigor@sysoev.ru 
4760Sigor@sysoev.ru     node->parent = child;
4770Sigor@sysoev.ru }
4780Sigor@sysoev.ru 
4790Sigor@sysoev.ru 
4800Sigor@sysoev.ru /* Relink a parent from the node to the subst node. */
4810Sigor@sysoev.ru 
4820Sigor@sysoev.ru nxt_inline void
nxt_rbtree_parent_relink(nxt_rbtree_node_t * subst,nxt_rbtree_node_t * node)4830Sigor@sysoev.ru nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node)
4840Sigor@sysoev.ru {
4850Sigor@sysoev.ru     nxt_rbtree_node_t  *parent, **link;
4860Sigor@sysoev.ru 
4870Sigor@sysoev.ru     parent = node->parent;
4880Sigor@sysoev.ru     /*
4890Sigor@sysoev.ru      * The leaf sentinel's parent can be safely changed here.
4900Sigor@sysoev.ru      * See the comment in nxt_rbtree_delete_fixup() for details.
4910Sigor@sysoev.ru      */
4920Sigor@sysoev.ru     subst->parent = parent;
4930Sigor@sysoev.ru     /*
4940Sigor@sysoev.ru      * If the node's parent is the root sentinel it is safely changed
4950Sigor@sysoev.ru      * because the root sentinel's left child is the tree root.
4960Sigor@sysoev.ru      */
4970Sigor@sysoev.ru     link = (node == parent->left) ? &parent->left : &parent->right;
4980Sigor@sysoev.ru     *link = subst;
4990Sigor@sysoev.ru }
50023Sigor@sysoev.ru 
50123Sigor@sysoev.ru 
50223Sigor@sysoev.ru nxt_rbtree_node_t *
nxt_rbtree_destroy_next(nxt_rbtree_t * tree,nxt_rbtree_node_t ** next)50323Sigor@sysoev.ru nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
50423Sigor@sysoev.ru {
50523Sigor@sysoev.ru     nxt_rbtree_node_t  *node, *subst, *parent, *sentinel;
50623Sigor@sysoev.ru 
50723Sigor@sysoev.ru     sentinel = nxt_rbtree_sentinel(tree);
50823Sigor@sysoev.ru 
50923Sigor@sysoev.ru     /* Find the leftmost node. */
51023Sigor@sysoev.ru     for (node = *next; node->left != sentinel; node = node->left);
51123Sigor@sysoev.ru 
51223Sigor@sysoev.ru     /* Replace the leftmost node with its right child. */
51323Sigor@sysoev.ru     subst = node->right;
51423Sigor@sysoev.ru     parent = node->parent;
51523Sigor@sysoev.ru 
51623Sigor@sysoev.ru     parent->left = subst;
51723Sigor@sysoev.ru     subst->parent = parent;
51823Sigor@sysoev.ru 
51923Sigor@sysoev.ru     /*
52023Sigor@sysoev.ru      * The right child is used as the next start node.  If the right child
52123Sigor@sysoev.ru      * is the sentinel then parent of the leftmost node is used as the next
52223Sigor@sysoev.ru      * start node.  The parent of the root node is the sentinel so after
52323Sigor@sysoev.ru      * the single root node will be replaced with the sentinel, the next
52423Sigor@sysoev.ru      * start node will be equal to the sentinel and iteration will stop.
52523Sigor@sysoev.ru      */
52623Sigor@sysoev.ru     if (subst == sentinel) {
52723Sigor@sysoev.ru         subst = parent;
52823Sigor@sysoev.ru     }
52923Sigor@sysoev.ru 
53023Sigor@sysoev.ru     *next = subst;
53123Sigor@sysoev.ru 
53223Sigor@sysoev.ru     return node;
53323Sigor@sysoev.ru }
534