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