1*0Sigor@sysoev.ru 2*0Sigor@sysoev.ru /* 3*0Sigor@sysoev.ru * Copyright (C) Igor Sysoev 4*0Sigor@sysoev.ru * Copyright (C) NGINX, Inc. 5*0Sigor@sysoev.ru */ 6*0Sigor@sysoev.ru 7*0Sigor@sysoev.ru #include <nxt_main.h> 8*0Sigor@sysoev.ru 9*0Sigor@sysoev.ru 10*0Sigor@sysoev.ru /* 11*0Sigor@sysoev.ru * The red-black tree code is based on the algorithm described in 12*0Sigor@sysoev.ru * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. 13*0Sigor@sysoev.ru */ 14*0Sigor@sysoev.ru 15*0Sigor@sysoev.ru 16*0Sigor@sysoev.ru static void nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node); 17*0Sigor@sysoev.ru static void nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, 18*0Sigor@sysoev.ru nxt_rbtree_node_t *node); 19*0Sigor@sysoev.ru nxt_inline void nxt_rbtree_left_rotate(nxt_rbtree_node_t *node); 20*0Sigor@sysoev.ru nxt_inline void nxt_rbtree_right_rotate(nxt_rbtree_node_t *node); 21*0Sigor@sysoev.ru nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, 22*0Sigor@sysoev.ru nxt_rbtree_node_t *node); 23*0Sigor@sysoev.ru 24*0Sigor@sysoev.ru 25*0Sigor@sysoev.ru #define NXT_RBTREE_BLACK 0 26*0Sigor@sysoev.ru #define NXT_RBTREE_RED 1 27*0Sigor@sysoev.ru 28*0Sigor@sysoev.ru 29*0Sigor@sysoev.ru #define nxt_rbtree_set_callback_type(tree, type) \ 30*0Sigor@sysoev.ru (tree)->sentinel.spare = type 31*0Sigor@sysoev.ru 32*0Sigor@sysoev.ru #define nxt_rbtree_has_insertion_callback(tree) \ 33*0Sigor@sysoev.ru ((tree)->sentinel.spare != 0) 34*0Sigor@sysoev.ru 35*0Sigor@sysoev.ru #define nxt_rbtree_comparison_callback(tree) \ 36*0Sigor@sysoev.ru ((nxt_rbtree_compare_t) (tree)->sentinel.right) 37*0Sigor@sysoev.ru 38*0Sigor@sysoev.ru 39*0Sigor@sysoev.ru void 40*0Sigor@sysoev.ru nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare, 41*0Sigor@sysoev.ru nxt_rbtree_insert_t insert) 42*0Sigor@sysoev.ru { 43*0Sigor@sysoev.ru void *callback; 44*0Sigor@sysoev.ru nxt_bool_t insertion; 45*0Sigor@sysoev.ru 46*0Sigor@sysoev.ru /* 47*0Sigor@sysoev.ru * The sentinel is used as a leaf node sentinel and as a tree root 48*0Sigor@sysoev.ru * sentinel: it is a parent of a root node and the root node is 49*0Sigor@sysoev.ru * the left child of the sentinel. Combining two sentinels in one 50*0Sigor@sysoev.ru * entry and the fact that the sentinel's left child is a root node 51*0Sigor@sysoev.ru * simplifies nxt_rbtree_node_successor() and eliminates explicit 52*0Sigor@sysoev.ru * root node test before or inside nxt_rbtree_min(). 53*0Sigor@sysoev.ru */ 54*0Sigor@sysoev.ru 55*0Sigor@sysoev.ru /* The root is empty. */ 56*0Sigor@sysoev.ru tree->sentinel.left = &tree->sentinel; 57*0Sigor@sysoev.ru 58*0Sigor@sysoev.ru /* 59*0Sigor@sysoev.ru * The sentinel's right child is never used so either insertion 60*0Sigor@sysoev.ru * or comparison callback can be safely stored here. 61*0Sigor@sysoev.ru */ 62*0Sigor@sysoev.ru insertion = (insert != NULL); 63*0Sigor@sysoev.ru nxt_rbtree_set_callback_type(tree, insertion); 64*0Sigor@sysoev.ru callback = insertion ? (void *) insert : (void *) compare; 65*0Sigor@sysoev.ru tree->sentinel.right = callback; 66*0Sigor@sysoev.ru 67*0Sigor@sysoev.ru /* The root and leaf sentinel must be black. */ 68*0Sigor@sysoev.ru tree->sentinel.color = NXT_RBTREE_BLACK; 69*0Sigor@sysoev.ru } 70*0Sigor@sysoev.ru 71*0Sigor@sysoev.ru 72*0Sigor@sysoev.ru void 73*0Sigor@sysoev.ru nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part) 74*0Sigor@sysoev.ru { 75*0Sigor@sysoev.ru void *callback; 76*0Sigor@sysoev.ru nxt_rbtree_node_t *node, *new_node, *sentinel, **child; 77*0Sigor@sysoev.ru nxt_rbtree_insert_t insert; 78*0Sigor@sysoev.ru nxt_rbtree_compare_t compare; 79*0Sigor@sysoev.ru 80*0Sigor@sysoev.ru new_node = (nxt_rbtree_node_t *) part; 81*0Sigor@sysoev.ru 82*0Sigor@sysoev.ru node = nxt_rbtree_root(tree); 83*0Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 84*0Sigor@sysoev.ru 85*0Sigor@sysoev.ru new_node->left = sentinel; 86*0Sigor@sysoev.ru new_node->right = sentinel; 87*0Sigor@sysoev.ru new_node->color = NXT_RBTREE_RED; 88*0Sigor@sysoev.ru 89*0Sigor@sysoev.ru callback = tree->sentinel.right; 90*0Sigor@sysoev.ru 91*0Sigor@sysoev.ru if (nxt_rbtree_has_insertion_callback(tree)) { 92*0Sigor@sysoev.ru insert = (nxt_rbtree_insert_t) callback; 93*0Sigor@sysoev.ru 94*0Sigor@sysoev.ru insert(node, new_node, sentinel); 95*0Sigor@sysoev.ru 96*0Sigor@sysoev.ru } else { 97*0Sigor@sysoev.ru compare = (nxt_rbtree_compare_t) callback; 98*0Sigor@sysoev.ru 99*0Sigor@sysoev.ru child = &nxt_rbtree_root(tree); 100*0Sigor@sysoev.ru 101*0Sigor@sysoev.ru while (*child != sentinel) { 102*0Sigor@sysoev.ru node = *child; 103*0Sigor@sysoev.ru 104*0Sigor@sysoev.ru nxt_prefetch(node->left); 105*0Sigor@sysoev.ru nxt_prefetch(node->right); 106*0Sigor@sysoev.ru 107*0Sigor@sysoev.ru child = (compare(new_node, node) < 0) ? &node->left : &node->right; 108*0Sigor@sysoev.ru } 109*0Sigor@sysoev.ru 110*0Sigor@sysoev.ru *child = new_node; 111*0Sigor@sysoev.ru 112*0Sigor@sysoev.ru new_node->parent = node; 113*0Sigor@sysoev.ru } 114*0Sigor@sysoev.ru 115*0Sigor@sysoev.ru nxt_rbtree_insert_fixup(new_node); 116*0Sigor@sysoev.ru 117*0Sigor@sysoev.ru node = nxt_rbtree_root(tree); 118*0Sigor@sysoev.ru node->color = NXT_RBTREE_BLACK; 119*0Sigor@sysoev.ru } 120*0Sigor@sysoev.ru 121*0Sigor@sysoev.ru 122*0Sigor@sysoev.ru static void 123*0Sigor@sysoev.ru nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node) 124*0Sigor@sysoev.ru { 125*0Sigor@sysoev.ru nxt_rbtree_node_t *parent, *grandparent, *uncle; 126*0Sigor@sysoev.ru 127*0Sigor@sysoev.ru /* 128*0Sigor@sysoev.ru * Prefetching parent nodes does not help here because they are 129*0Sigor@sysoev.ru * already traversed during insertion. 130*0Sigor@sysoev.ru */ 131*0Sigor@sysoev.ru 132*0Sigor@sysoev.ru for ( ;; ) { 133*0Sigor@sysoev.ru parent = node->parent; 134*0Sigor@sysoev.ru 135*0Sigor@sysoev.ru /* 136*0Sigor@sysoev.ru * Testing whether a node is a tree root is not required here since 137*0Sigor@sysoev.ru * a root node's parent is the sentinel and it is always black. 138*0Sigor@sysoev.ru */ 139*0Sigor@sysoev.ru if (parent->color == NXT_RBTREE_BLACK) { 140*0Sigor@sysoev.ru return; 141*0Sigor@sysoev.ru } 142*0Sigor@sysoev.ru 143*0Sigor@sysoev.ru grandparent = parent->parent; 144*0Sigor@sysoev.ru 145*0Sigor@sysoev.ru if (parent == grandparent->left) { 146*0Sigor@sysoev.ru uncle = grandparent->right; 147*0Sigor@sysoev.ru 148*0Sigor@sysoev.ru if (uncle->color == NXT_RBTREE_BLACK) { 149*0Sigor@sysoev.ru 150*0Sigor@sysoev.ru if (node == parent->right) { 151*0Sigor@sysoev.ru node = parent; 152*0Sigor@sysoev.ru nxt_rbtree_left_rotate(node); 153*0Sigor@sysoev.ru } 154*0Sigor@sysoev.ru 155*0Sigor@sysoev.ru parent = node->parent; 156*0Sigor@sysoev.ru parent->color = NXT_RBTREE_BLACK; 157*0Sigor@sysoev.ru 158*0Sigor@sysoev.ru grandparent = parent->parent; 159*0Sigor@sysoev.ru grandparent->color = NXT_RBTREE_RED; 160*0Sigor@sysoev.ru nxt_rbtree_right_rotate(grandparent); 161*0Sigor@sysoev.ru 162*0Sigor@sysoev.ru continue; 163*0Sigor@sysoev.ru } 164*0Sigor@sysoev.ru 165*0Sigor@sysoev.ru } else { 166*0Sigor@sysoev.ru uncle = grandparent->left; 167*0Sigor@sysoev.ru 168*0Sigor@sysoev.ru if (uncle->color == NXT_RBTREE_BLACK) { 169*0Sigor@sysoev.ru 170*0Sigor@sysoev.ru if (node == parent->left) { 171*0Sigor@sysoev.ru node = parent; 172*0Sigor@sysoev.ru nxt_rbtree_right_rotate(node); 173*0Sigor@sysoev.ru } 174*0Sigor@sysoev.ru 175*0Sigor@sysoev.ru parent = node->parent; 176*0Sigor@sysoev.ru parent->color = NXT_RBTREE_BLACK; 177*0Sigor@sysoev.ru 178*0Sigor@sysoev.ru grandparent = parent->parent; 179*0Sigor@sysoev.ru grandparent->color = NXT_RBTREE_RED; 180*0Sigor@sysoev.ru nxt_rbtree_left_rotate(grandparent); 181*0Sigor@sysoev.ru 182*0Sigor@sysoev.ru continue; 183*0Sigor@sysoev.ru } 184*0Sigor@sysoev.ru } 185*0Sigor@sysoev.ru 186*0Sigor@sysoev.ru uncle->color = NXT_RBTREE_BLACK; 187*0Sigor@sysoev.ru parent->color = NXT_RBTREE_BLACK; 188*0Sigor@sysoev.ru grandparent->color = NXT_RBTREE_RED; 189*0Sigor@sysoev.ru 190*0Sigor@sysoev.ru node = grandparent; 191*0Sigor@sysoev.ru } 192*0Sigor@sysoev.ru } 193*0Sigor@sysoev.ru 194*0Sigor@sysoev.ru 195*0Sigor@sysoev.ru nxt_rbtree_node_t * 196*0Sigor@sysoev.ru nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part) 197*0Sigor@sysoev.ru { 198*0Sigor@sysoev.ru nxt_int_t n; 199*0Sigor@sysoev.ru nxt_rbtree_node_t *node, *next, *sentinel; 200*0Sigor@sysoev.ru nxt_rbtree_compare_t compare; 201*0Sigor@sysoev.ru 202*0Sigor@sysoev.ru node = (nxt_rbtree_node_t *) part; 203*0Sigor@sysoev.ru 204*0Sigor@sysoev.ru next = nxt_rbtree_root(tree); 205*0Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 206*0Sigor@sysoev.ru compare = nxt_rbtree_comparison_callback(tree); 207*0Sigor@sysoev.ru 208*0Sigor@sysoev.ru while (next != sentinel) { 209*0Sigor@sysoev.ru nxt_prefetch(next->left); 210*0Sigor@sysoev.ru nxt_prefetch(next->right); 211*0Sigor@sysoev.ru 212*0Sigor@sysoev.ru n = compare(node, next); 213*0Sigor@sysoev.ru 214*0Sigor@sysoev.ru if (n < 0) { 215*0Sigor@sysoev.ru next = next->left; 216*0Sigor@sysoev.ru 217*0Sigor@sysoev.ru } else if (n > 0) { 218*0Sigor@sysoev.ru next = next->right; 219*0Sigor@sysoev.ru 220*0Sigor@sysoev.ru } else { 221*0Sigor@sysoev.ru return next; 222*0Sigor@sysoev.ru } 223*0Sigor@sysoev.ru } 224*0Sigor@sysoev.ru 225*0Sigor@sysoev.ru return NULL; 226*0Sigor@sysoev.ru } 227*0Sigor@sysoev.ru 228*0Sigor@sysoev.ru 229*0Sigor@sysoev.ru nxt_rbtree_node_t * 230*0Sigor@sysoev.ru nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part) 231*0Sigor@sysoev.ru { 232*0Sigor@sysoev.ru nxt_int_t n; 233*0Sigor@sysoev.ru nxt_rbtree_node_t *node, *retval, *next, *sentinel; 234*0Sigor@sysoev.ru nxt_rbtree_compare_t compare; 235*0Sigor@sysoev.ru 236*0Sigor@sysoev.ru node = (nxt_rbtree_node_t *) part; 237*0Sigor@sysoev.ru 238*0Sigor@sysoev.ru retval = NULL; 239*0Sigor@sysoev.ru next = nxt_rbtree_root(tree); 240*0Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 241*0Sigor@sysoev.ru compare = nxt_rbtree_comparison_callback(tree); 242*0Sigor@sysoev.ru 243*0Sigor@sysoev.ru while (next != sentinel) { 244*0Sigor@sysoev.ru nxt_prefetch(next->left); 245*0Sigor@sysoev.ru nxt_prefetch(next->right); 246*0Sigor@sysoev.ru 247*0Sigor@sysoev.ru n = compare(node, next); 248*0Sigor@sysoev.ru 249*0Sigor@sysoev.ru if (n < 0) { 250*0Sigor@sysoev.ru next = next->left; 251*0Sigor@sysoev.ru 252*0Sigor@sysoev.ru } else if (n > 0) { 253*0Sigor@sysoev.ru retval = next; 254*0Sigor@sysoev.ru next = next->right; 255*0Sigor@sysoev.ru 256*0Sigor@sysoev.ru } else { 257*0Sigor@sysoev.ru /* Exact match. */ 258*0Sigor@sysoev.ru return next; 259*0Sigor@sysoev.ru } 260*0Sigor@sysoev.ru } 261*0Sigor@sysoev.ru 262*0Sigor@sysoev.ru return retval; 263*0Sigor@sysoev.ru } 264*0Sigor@sysoev.ru 265*0Sigor@sysoev.ru 266*0Sigor@sysoev.ru nxt_rbtree_node_t * 267*0Sigor@sysoev.ru nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part) 268*0Sigor@sysoev.ru { 269*0Sigor@sysoev.ru nxt_int_t n; 270*0Sigor@sysoev.ru nxt_rbtree_node_t *node, *retval, *next, *sentinel; 271*0Sigor@sysoev.ru nxt_rbtree_compare_t compare; 272*0Sigor@sysoev.ru 273*0Sigor@sysoev.ru node = (nxt_rbtree_node_t *) part; 274*0Sigor@sysoev.ru 275*0Sigor@sysoev.ru retval = NULL; 276*0Sigor@sysoev.ru next = nxt_rbtree_root(tree); 277*0Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 278*0Sigor@sysoev.ru compare = nxt_rbtree_comparison_callback(tree); 279*0Sigor@sysoev.ru 280*0Sigor@sysoev.ru while (next != sentinel) { 281*0Sigor@sysoev.ru nxt_prefetch(next->left); 282*0Sigor@sysoev.ru nxt_prefetch(next->right); 283*0Sigor@sysoev.ru 284*0Sigor@sysoev.ru n = compare(node, next); 285*0Sigor@sysoev.ru 286*0Sigor@sysoev.ru if (n < 0) { 287*0Sigor@sysoev.ru retval = next; 288*0Sigor@sysoev.ru next = next->left; 289*0Sigor@sysoev.ru 290*0Sigor@sysoev.ru } else if (n > 0) { 291*0Sigor@sysoev.ru next = next->right; 292*0Sigor@sysoev.ru 293*0Sigor@sysoev.ru } else { 294*0Sigor@sysoev.ru /* Exact match. */ 295*0Sigor@sysoev.ru return next; 296*0Sigor@sysoev.ru } 297*0Sigor@sysoev.ru } 298*0Sigor@sysoev.ru 299*0Sigor@sysoev.ru return retval; 300*0Sigor@sysoev.ru } 301*0Sigor@sysoev.ru 302*0Sigor@sysoev.ru 303*0Sigor@sysoev.ru void 304*0Sigor@sysoev.ru nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part) 305*0Sigor@sysoev.ru { 306*0Sigor@sysoev.ru nxt_uint_t color; 307*0Sigor@sysoev.ru nxt_rbtree_node_t *node, *sentinel, *subst, *child; 308*0Sigor@sysoev.ru 309*0Sigor@sysoev.ru node = (nxt_rbtree_node_t *) part; 310*0Sigor@sysoev.ru 311*0Sigor@sysoev.ru subst = node; 312*0Sigor@sysoev.ru sentinel = nxt_rbtree_sentinel(tree); 313*0Sigor@sysoev.ru 314*0Sigor@sysoev.ru if (node->left == sentinel) { 315*0Sigor@sysoev.ru child = node->right; 316*0Sigor@sysoev.ru 317*0Sigor@sysoev.ru } else if (node->right == sentinel) { 318*0Sigor@sysoev.ru child = node->left; 319*0Sigor@sysoev.ru 320*0Sigor@sysoev.ru } else { 321*0Sigor@sysoev.ru subst = nxt_rbtree_branch_min(tree, node->right); 322*0Sigor@sysoev.ru child = subst->right; 323*0Sigor@sysoev.ru } 324*0Sigor@sysoev.ru 325*0Sigor@sysoev.ru nxt_rbtree_parent_relink(child, subst); 326*0Sigor@sysoev.ru 327*0Sigor@sysoev.ru color = subst->color; 328*0Sigor@sysoev.ru 329*0Sigor@sysoev.ru if (subst != node) { 330*0Sigor@sysoev.ru /* Move the subst node to the deleted node position in the tree. */ 331*0Sigor@sysoev.ru 332*0Sigor@sysoev.ru subst->color = node->color; 333*0Sigor@sysoev.ru 334*0Sigor@sysoev.ru subst->left = node->left; 335*0Sigor@sysoev.ru subst->left->parent = subst; 336*0Sigor@sysoev.ru 337*0Sigor@sysoev.ru subst->right = node->right; 338*0Sigor@sysoev.ru subst->right->parent = subst; 339*0Sigor@sysoev.ru 340*0Sigor@sysoev.ru nxt_rbtree_parent_relink(subst, node); 341*0Sigor@sysoev.ru } 342*0Sigor@sysoev.ru 343*0Sigor@sysoev.ru #if (NXT_DEBUG) 344*0Sigor@sysoev.ru node->left = NULL; 345*0Sigor@sysoev.ru node->right = NULL; 346*0Sigor@sysoev.ru node->parent = NULL; 347*0Sigor@sysoev.ru #endif 348*0Sigor@sysoev.ru 349*0Sigor@sysoev.ru if (color == NXT_RBTREE_BLACK) { 350*0Sigor@sysoev.ru nxt_rbtree_delete_fixup(tree, child); 351*0Sigor@sysoev.ru } 352*0Sigor@sysoev.ru } 353*0Sigor@sysoev.ru 354*0Sigor@sysoev.ru 355*0Sigor@sysoev.ru static void 356*0Sigor@sysoev.ru nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node) 357*0Sigor@sysoev.ru { 358*0Sigor@sysoev.ru nxt_rbtree_node_t *parent, *sibling; 359*0Sigor@sysoev.ru 360*0Sigor@sysoev.ru while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) { 361*0Sigor@sysoev.ru /* 362*0Sigor@sysoev.ru * Prefetching parent nodes does not help here according 363*0Sigor@sysoev.ru * to microbenchmarks. 364*0Sigor@sysoev.ru */ 365*0Sigor@sysoev.ru 366*0Sigor@sysoev.ru parent = node->parent; 367*0Sigor@sysoev.ru 368*0Sigor@sysoev.ru if (node == parent->left) { 369*0Sigor@sysoev.ru sibling = parent->right; 370*0Sigor@sysoev.ru 371*0Sigor@sysoev.ru if (sibling->color != NXT_RBTREE_BLACK) { 372*0Sigor@sysoev.ru 373*0Sigor@sysoev.ru sibling->color = NXT_RBTREE_BLACK; 374*0Sigor@sysoev.ru parent->color = NXT_RBTREE_RED; 375*0Sigor@sysoev.ru 376*0Sigor@sysoev.ru nxt_rbtree_left_rotate(parent); 377*0Sigor@sysoev.ru 378*0Sigor@sysoev.ru sibling = parent->right; 379*0Sigor@sysoev.ru } 380*0Sigor@sysoev.ru 381*0Sigor@sysoev.ru if (sibling->right->color == NXT_RBTREE_BLACK) { 382*0Sigor@sysoev.ru 383*0Sigor@sysoev.ru sibling->color = NXT_RBTREE_RED; 384*0Sigor@sysoev.ru 385*0Sigor@sysoev.ru if (sibling->left->color == NXT_RBTREE_BLACK) { 386*0Sigor@sysoev.ru node = parent; 387*0Sigor@sysoev.ru continue; 388*0Sigor@sysoev.ru } 389*0Sigor@sysoev.ru 390*0Sigor@sysoev.ru sibling->left->color = NXT_RBTREE_BLACK; 391*0Sigor@sysoev.ru 392*0Sigor@sysoev.ru nxt_rbtree_right_rotate(sibling); 393*0Sigor@sysoev.ru /* 394*0Sigor@sysoev.ru * If the node is the leaf sentinel then the right 395*0Sigor@sysoev.ru * rotate above changes its parent so a sibling below 396*0Sigor@sysoev.ru * becames the leaf sentinel as well and this causes 397*0Sigor@sysoev.ru * segmentation fault. This is the reason why usual 398*0Sigor@sysoev.ru * red-black tree implementations with a leaf sentinel 399*0Sigor@sysoev.ru * which does not require to test leaf nodes at all 400*0Sigor@sysoev.ru * nevertheless test the leaf sentinel in the left and 401*0Sigor@sysoev.ru * right rotate procedures. Since according to the 402*0Sigor@sysoev.ru * algorithm node->parent must not be changed by both 403*0Sigor@sysoev.ru * the left and right rotates above, it can be cached 404*0Sigor@sysoev.ru * in a local variable. This not only eliminates the 405*0Sigor@sysoev.ru * sentinel test in nxt_rbtree_parent_relink() but also 406*0Sigor@sysoev.ru * decreases the code size because C forces to reload 407*0Sigor@sysoev.ru * non-restrict pointers. 408*0Sigor@sysoev.ru */ 409*0Sigor@sysoev.ru sibling = parent->right; 410*0Sigor@sysoev.ru } 411*0Sigor@sysoev.ru 412*0Sigor@sysoev.ru sibling->color = parent->color; 413*0Sigor@sysoev.ru parent->color = NXT_RBTREE_BLACK; 414*0Sigor@sysoev.ru sibling->right->color = NXT_RBTREE_BLACK; 415*0Sigor@sysoev.ru 416*0Sigor@sysoev.ru nxt_rbtree_left_rotate(parent); 417*0Sigor@sysoev.ru 418*0Sigor@sysoev.ru break; 419*0Sigor@sysoev.ru 420*0Sigor@sysoev.ru } else { 421*0Sigor@sysoev.ru sibling = parent->left; 422*0Sigor@sysoev.ru 423*0Sigor@sysoev.ru if (sibling->color != NXT_RBTREE_BLACK) { 424*0Sigor@sysoev.ru 425*0Sigor@sysoev.ru sibling->color = NXT_RBTREE_BLACK; 426*0Sigor@sysoev.ru parent->color = NXT_RBTREE_RED; 427*0Sigor@sysoev.ru 428*0Sigor@sysoev.ru nxt_rbtree_right_rotate(parent); 429*0Sigor@sysoev.ru 430*0Sigor@sysoev.ru sibling = parent->left; 431*0Sigor@sysoev.ru } 432*0Sigor@sysoev.ru 433*0Sigor@sysoev.ru if (sibling->left->color == NXT_RBTREE_BLACK) { 434*0Sigor@sysoev.ru 435*0Sigor@sysoev.ru sibling->color = NXT_RBTREE_RED; 436*0Sigor@sysoev.ru 437*0Sigor@sysoev.ru if (sibling->right->color == NXT_RBTREE_BLACK) { 438*0Sigor@sysoev.ru node = parent; 439*0Sigor@sysoev.ru continue; 440*0Sigor@sysoev.ru } 441*0Sigor@sysoev.ru 442*0Sigor@sysoev.ru sibling->right->color = NXT_RBTREE_BLACK; 443*0Sigor@sysoev.ru 444*0Sigor@sysoev.ru nxt_rbtree_left_rotate(sibling); 445*0Sigor@sysoev.ru 446*0Sigor@sysoev.ru /* See the comment in the symmetric branch above. */ 447*0Sigor@sysoev.ru sibling = parent->left; 448*0Sigor@sysoev.ru } 449*0Sigor@sysoev.ru 450*0Sigor@sysoev.ru sibling->color = parent->color; 451*0Sigor@sysoev.ru parent->color = NXT_RBTREE_BLACK; 452*0Sigor@sysoev.ru sibling->left->color = NXT_RBTREE_BLACK; 453*0Sigor@sysoev.ru 454*0Sigor@sysoev.ru nxt_rbtree_right_rotate(parent); 455*0Sigor@sysoev.ru 456*0Sigor@sysoev.ru break; 457*0Sigor@sysoev.ru } 458*0Sigor@sysoev.ru } 459*0Sigor@sysoev.ru 460*0Sigor@sysoev.ru node->color = NXT_RBTREE_BLACK; 461*0Sigor@sysoev.ru } 462*0Sigor@sysoev.ru 463*0Sigor@sysoev.ru 464*0Sigor@sysoev.ru nxt_inline void 465*0Sigor@sysoev.ru nxt_rbtree_left_rotate(nxt_rbtree_node_t *node) 466*0Sigor@sysoev.ru { 467*0Sigor@sysoev.ru nxt_rbtree_node_t *child; 468*0Sigor@sysoev.ru 469*0Sigor@sysoev.ru child = node->right; 470*0Sigor@sysoev.ru node->right = child->left; 471*0Sigor@sysoev.ru child->left->parent = node; 472*0Sigor@sysoev.ru child->left = node; 473*0Sigor@sysoev.ru 474*0Sigor@sysoev.ru nxt_rbtree_parent_relink(child, node); 475*0Sigor@sysoev.ru 476*0Sigor@sysoev.ru node->parent = child; 477*0Sigor@sysoev.ru } 478*0Sigor@sysoev.ru 479*0Sigor@sysoev.ru 480*0Sigor@sysoev.ru nxt_inline void 481*0Sigor@sysoev.ru nxt_rbtree_right_rotate(nxt_rbtree_node_t *node) 482*0Sigor@sysoev.ru { 483*0Sigor@sysoev.ru nxt_rbtree_node_t *child; 484*0Sigor@sysoev.ru 485*0Sigor@sysoev.ru child = node->left; 486*0Sigor@sysoev.ru node->left = child->right; 487*0Sigor@sysoev.ru child->right->parent = node; 488*0Sigor@sysoev.ru child->right = node; 489*0Sigor@sysoev.ru 490*0Sigor@sysoev.ru nxt_rbtree_parent_relink(child, node); 491*0Sigor@sysoev.ru 492*0Sigor@sysoev.ru node->parent = child; 493*0Sigor@sysoev.ru } 494*0Sigor@sysoev.ru 495*0Sigor@sysoev.ru 496*0Sigor@sysoev.ru /* Relink a parent from the node to the subst node. */ 497*0Sigor@sysoev.ru 498*0Sigor@sysoev.ru nxt_inline void 499*0Sigor@sysoev.ru nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node) 500*0Sigor@sysoev.ru { 501*0Sigor@sysoev.ru nxt_rbtree_node_t *parent, **link; 502*0Sigor@sysoev.ru 503*0Sigor@sysoev.ru parent = node->parent; 504*0Sigor@sysoev.ru /* 505*0Sigor@sysoev.ru * The leaf sentinel's parent can be safely changed here. 506*0Sigor@sysoev.ru * See the comment in nxt_rbtree_delete_fixup() for details. 507*0Sigor@sysoev.ru */ 508*0Sigor@sysoev.ru subst->parent = parent; 509*0Sigor@sysoev.ru /* 510*0Sigor@sysoev.ru * If the node's parent is the root sentinel it is safely changed 511*0Sigor@sysoev.ru * because the root sentinel's left child is the tree root. 512*0Sigor@sysoev.ru */ 513*0Sigor@sysoev.ru link = (node == parent->left) ? &parent->left : &parent->right; 514*0Sigor@sysoev.ru *link = subst; 515*0Sigor@sysoev.ru } 516