1 /* 2 * rbtree.c -- generic red black tree 3 * 4 * Copyright (c) 2001-2011, NLnet Labs. All rights reserved. 5 * 6 * See LICENSE for the license. 7 * 8 */ 9 10 #include <config.h> 11 12 #include <assert.h> 13 #include <stdlib.h> 14 15 #include "rbtree.h" 16 17 #define BLACK 0 18 #define RED 1 19 20 rbnode_t rbtree_null_node = { 21 RBTREE_NULL, /* Parent. */ 22 RBTREE_NULL, /* Left. */ 23 RBTREE_NULL, /* Right. */ 24 NULL, /* Key. */ 25 BLACK /* Color. */ 26 }; 27 28 static void rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node); 29 static void rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node); 30 static void rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node); 31 static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent); 32 33 /* 34 * Creates a new red black tree, intializes and returns a pointer to it. 35 * 36 * Return NULL on failure. 37 * 38 */ 39 rbtree_t * 40 rbtree_create (region_type *region, int (*cmpf)(const void *, const void *)) 41 { 42 rbtree_t *rbtree; 43 44 /* Allocate memory for it */ 45 rbtree = (rbtree_t *) region_alloc(region, sizeof(rbtree_t)); 46 if (!rbtree) { 47 return NULL; 48 } 49 50 /* Initialize it */ 51 rbtree->root = RBTREE_NULL; 52 rbtree->count = 0; 53 rbtree->region = region; 54 rbtree->cmp = cmpf; 55 56 return rbtree; 57 } 58 59 /* 60 * Rotates the node to the left. 61 * 62 */ 63 static void 64 rbtree_rotate_left(rbtree_t *rbtree, rbnode_t *node) 65 { 66 rbnode_t *right = node->right; 67 node->right = right->left; 68 if (right->left != RBTREE_NULL) 69 right->left->parent = node; 70 71 right->parent = node->parent; 72 73 if (node->parent != RBTREE_NULL) { 74 if (node == node->parent->left) { 75 node->parent->left = right; 76 } else { 77 node->parent->right = right; 78 } 79 } else { 80 rbtree->root = right; 81 } 82 right->left = node; 83 node->parent = right; 84 } 85 86 /* 87 * Rotates the node to the right. 88 * 89 */ 90 static void 91 rbtree_rotate_right(rbtree_t *rbtree, rbnode_t *node) 92 { 93 rbnode_t *left = node->left; 94 node->left = left->right; 95 if (left->right != RBTREE_NULL) 96 left->right->parent = node; 97 98 left->parent = node->parent; 99 100 if (node->parent != RBTREE_NULL) { 101 if (node == node->parent->right) { 102 node->parent->right = left; 103 } else { 104 node->parent->left = left; 105 } 106 } else { 107 rbtree->root = left; 108 } 109 left->right = node; 110 node->parent = left; 111 } 112 113 static void 114 rbtree_insert_fixup(rbtree_t *rbtree, rbnode_t *node) 115 { 116 rbnode_t *uncle; 117 118 /* While not at the root and need fixing... */ 119 while (node != rbtree->root && node->parent->color == RED) { 120 /* If our parent is left child of our grandparent... */ 121 if (node->parent == node->parent->parent->left) { 122 uncle = node->parent->parent->right; 123 124 /* If our uncle is red... */ 125 if (uncle->color == RED) { 126 /* Paint the parent and the uncle black... */ 127 node->parent->color = BLACK; 128 uncle->color = BLACK; 129 130 /* And the grandparent red... */ 131 node->parent->parent->color = RED; 132 133 /* And continue fixing the grandparent */ 134 node = node->parent->parent; 135 } else { /* Our uncle is black... */ 136 /* Are we the right child? */ 137 if (node == node->parent->right) { 138 node = node->parent; 139 rbtree_rotate_left(rbtree, node); 140 } 141 /* Now we're the left child, repaint and rotate... */ 142 node->parent->color = BLACK; 143 node->parent->parent->color = RED; 144 rbtree_rotate_right(rbtree, node->parent->parent); 145 } 146 } else { 147 uncle = node->parent->parent->left; 148 149 /* If our uncle is red... */ 150 if (uncle->color == RED) { 151 /* Paint the parent and the uncle black... */ 152 node->parent->color = BLACK; 153 uncle->color = BLACK; 154 155 /* And the grandparent red... */ 156 node->parent->parent->color = RED; 157 158 /* And continue fixing the grandparent */ 159 node = node->parent->parent; 160 } else { /* Our uncle is black... */ 161 /* Are we the right child? */ 162 if (node == node->parent->left) { 163 node = node->parent; 164 rbtree_rotate_right(rbtree, node); 165 } 166 /* Now we're the right child, repaint and rotate... */ 167 node->parent->color = BLACK; 168 node->parent->parent->color = RED; 169 rbtree_rotate_left(rbtree, node->parent->parent); 170 } 171 } 172 } 173 rbtree->root->color = BLACK; 174 } 175 176 177 /* 178 * Inserts a node into a red black tree. 179 * 180 * Returns NULL on failure or the pointer to the newly added node 181 * otherwise. 182 */ 183 rbnode_t * 184 rbtree_insert (rbtree_t *rbtree, rbnode_t *data) 185 { 186 /* XXX Not necessary, but keeps compiler quiet... */ 187 int r = 0; 188 189 /* We start at the root of the tree */ 190 rbnode_t *node = rbtree->root; 191 rbnode_t *parent = RBTREE_NULL; 192 193 /* Lets find the new parent... */ 194 while (node != RBTREE_NULL) { 195 /* Compare two keys, do we have a duplicate? */ 196 if ((r = rbtree->cmp(data->key, node->key)) == 0) { 197 return NULL; 198 } 199 parent = node; 200 201 if (r < 0) { 202 node = node->left; 203 } else { 204 node = node->right; 205 } 206 } 207 208 /* Initialize the new node */ 209 data->parent = parent; 210 data->left = data->right = RBTREE_NULL; 211 data->color = RED; 212 rbtree->count++; 213 214 /* Insert it into the tree... */ 215 if (parent != RBTREE_NULL) { 216 if (r < 0) { 217 parent->left = data; 218 } else { 219 parent->right = data; 220 } 221 } else { 222 rbtree->root = data; 223 } 224 225 /* Fix up the red-black properties... */ 226 rbtree_insert_fixup(rbtree, data); 227 228 return data; 229 } 230 231 /* 232 * Searches the red black tree, returns the data if key is found or NULL otherwise. 233 * 234 */ 235 rbnode_t * 236 rbtree_search (rbtree_t *rbtree, const void *key) 237 { 238 rbnode_t *node; 239 240 if (rbtree_find_less_equal(rbtree, key, &node)) { 241 return node; 242 } else { 243 return NULL; 244 } 245 } 246 247 /* helpers for delete */ 248 static void swap_int8(uint8_t* x, uint8_t* y) 249 { 250 uint8_t t = *x; *x = *y; *y = t; 251 } 252 253 static void swap_np(rbnode_t** x, rbnode_t** y) 254 { 255 rbnode_t* t = *x; *x = *y; *y = t; 256 } 257 258 static void change_parent_ptr(rbtree_t* rbtree, rbnode_t* parent, rbnode_t* old, rbnode_t* new) 259 { 260 if(parent == RBTREE_NULL) 261 { 262 assert(rbtree->root == old); 263 if(rbtree->root == old) rbtree->root = new; 264 return; 265 } 266 assert(parent->left == old || parent->right == old 267 || parent->left == new || parent->right == new); 268 if(parent->left == old) parent->left = new; 269 if(parent->right == old) parent->right = new; 270 } 271 static void change_child_ptr(rbnode_t* child, rbnode_t* old, rbnode_t* new) 272 { 273 if(child == RBTREE_NULL) return; 274 assert(child->parent == old || child->parent == new); 275 if(child->parent == old) child->parent = new; 276 } 277 278 rbnode_t* 279 rbtree_delete(rbtree_t *rbtree, const void *key) 280 { 281 rbnode_t *to_delete; 282 rbnode_t *child; 283 if((to_delete = rbtree_search(rbtree, key)) == 0) return 0; 284 rbtree->count--; 285 286 /* make sure we have at most one non-leaf child */ 287 if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL) 288 { 289 /* swap with smallest from right subtree (or largest from left) */ 290 rbnode_t *smright = to_delete->right; 291 while(smright->left != RBTREE_NULL) 292 smright = smright->left; 293 /* swap the smright and to_delete elements in the tree, 294 * but the rbnode_t is first part of user data struct 295 * so cannot just swap the keys and data pointers. Instead 296 * readjust the pointers left,right,parent */ 297 298 /* swap colors - colors are tied to the position in the tree */ 299 swap_int8(&to_delete->color, &smright->color); 300 301 /* swap child pointers in parents of smright/to_delete */ 302 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright); 303 if(to_delete->right != smright) 304 change_parent_ptr(rbtree, smright->parent, smright, to_delete); 305 306 /* swap parent pointers in children of smright/to_delete */ 307 change_child_ptr(smright->left, smright, to_delete); 308 change_child_ptr(smright->left, smright, to_delete); 309 change_child_ptr(smright->right, smright, to_delete); 310 change_child_ptr(smright->right, smright, to_delete); 311 change_child_ptr(to_delete->left, to_delete, smright); 312 if(to_delete->right != smright) 313 change_child_ptr(to_delete->right, to_delete, smright); 314 if(to_delete->right == smright) 315 { 316 /* set up so after swap they work */ 317 to_delete->right = to_delete; 318 smright->parent = smright; 319 } 320 321 /* swap pointers in to_delete/smright nodes */ 322 swap_np(&to_delete->parent, &smright->parent); 323 swap_np(&to_delete->left, &smright->left); 324 swap_np(&to_delete->right, &smright->right); 325 326 /* now delete to_delete (which is at the location where the smright previously was) */ 327 } 328 assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL); 329 330 if(to_delete->left != RBTREE_NULL) child = to_delete->left; 331 else child = to_delete->right; 332 333 /* unlink to_delete from the tree, replace to_delete with child */ 334 change_parent_ptr(rbtree, to_delete->parent, to_delete, child); 335 change_child_ptr(child, to_delete, to_delete->parent); 336 337 if(to_delete->color == RED) 338 { 339 /* if node is red then the child (black) can be swapped in */ 340 } 341 else if(child->color == RED) 342 { 343 /* change child to BLACK, removing a RED node is no problem */ 344 if(child!=RBTREE_NULL) child->color = BLACK; 345 } 346 else rbtree_delete_fixup(rbtree, child, to_delete->parent); 347 348 /* unlink completely */ 349 to_delete->parent = RBTREE_NULL; 350 to_delete->left = RBTREE_NULL; 351 to_delete->right = RBTREE_NULL; 352 to_delete->color = BLACK; 353 return to_delete; 354 } 355 356 static void rbtree_delete_fixup(rbtree_t* rbtree, rbnode_t* child, rbnode_t* child_parent) 357 { 358 rbnode_t* sibling; 359 int go_up = 1; 360 361 /* determine sibling to the node that is one-black short */ 362 if(child_parent->right == child) sibling = child_parent->left; 363 else sibling = child_parent->right; 364 365 while(go_up) 366 { 367 if(child_parent == RBTREE_NULL) 368 { 369 /* removed parent==black from root, every path, so ok */ 370 return; 371 } 372 373 if(sibling->color == RED) 374 { /* rotate to get a black sibling */ 375 child_parent->color = RED; 376 sibling->color = BLACK; 377 if(child_parent->right == child) 378 rbtree_rotate_right(rbtree, child_parent); 379 else rbtree_rotate_left(rbtree, child_parent); 380 /* new sibling after rotation */ 381 if(child_parent->right == child) sibling = child_parent->left; 382 else sibling = child_parent->right; 383 } 384 385 if(child_parent->color == BLACK 386 && sibling->color == BLACK 387 && sibling->left->color == BLACK 388 && sibling->right->color == BLACK) 389 { /* fixup local with recolor of sibling */ 390 if(sibling != RBTREE_NULL) 391 sibling->color = RED; 392 393 child = child_parent; 394 child_parent = child_parent->parent; 395 /* prepare to go up, new sibling */ 396 if(child_parent->right == child) sibling = child_parent->left; 397 else sibling = child_parent->right; 398 } 399 else go_up = 0; 400 } 401 402 if(child_parent->color == RED 403 && sibling->color == BLACK 404 && sibling->left->color == BLACK 405 && sibling->right->color == BLACK) 406 { 407 /* move red to sibling to rebalance */ 408 if(sibling != RBTREE_NULL) 409 sibling->color = RED; 410 child_parent->color = BLACK; 411 return; 412 } 413 assert(sibling != RBTREE_NULL); 414 415 /* get a new sibling, by rotating at sibling. See which child 416 of sibling is red */ 417 if(child_parent->right == child 418 && sibling->color == BLACK 419 && sibling->right->color == RED 420 && sibling->left->color == BLACK) 421 { 422 sibling->color = RED; 423 sibling->right->color = BLACK; 424 rbtree_rotate_left(rbtree, sibling); 425 /* new sibling after rotation */ 426 if(child_parent->right == child) sibling = child_parent->left; 427 else sibling = child_parent->right; 428 } 429 else if(child_parent->left == child 430 && sibling->color == BLACK 431 && sibling->left->color == RED 432 && sibling->right->color == BLACK) 433 { 434 sibling->color = RED; 435 sibling->left->color = BLACK; 436 rbtree_rotate_right(rbtree, sibling); 437 /* new sibling after rotation */ 438 if(child_parent->right == child) sibling = child_parent->left; 439 else sibling = child_parent->right; 440 } 441 442 /* now we have a black sibling with a red child. rotate and exchange colors. */ 443 sibling->color = child_parent->color; 444 child_parent->color = BLACK; 445 if(child_parent->right == child) 446 { 447 assert(sibling->left->color == RED); 448 sibling->left->color = BLACK; 449 rbtree_rotate_right(rbtree, child_parent); 450 } 451 else 452 { 453 assert(sibling->right->color == RED); 454 sibling->right->color = BLACK; 455 rbtree_rotate_left(rbtree, child_parent); 456 } 457 } 458 459 int 460 rbtree_find_less_equal(rbtree_t *rbtree, const void *key, rbnode_t **result) 461 { 462 int r; 463 rbnode_t *node; 464 465 assert(result); 466 467 /* We start at root... */ 468 node = rbtree->root; 469 470 *result = NULL; 471 472 /* While there are children... */ 473 while (node != RBTREE_NULL) { 474 r = rbtree->cmp(key, node->key); 475 if (r == 0) { 476 /* Exact match */ 477 *result = node; 478 return 1; 479 } 480 if (r < 0) { 481 node = node->left; 482 } else { 483 /* Temporary match */ 484 *result = node; 485 node = node->right; 486 } 487 } 488 return 0; 489 } 490 491 /* 492 * Finds the first element in the red black tree 493 * 494 */ 495 rbnode_t * 496 rbtree_first (rbtree_t *rbtree) 497 { 498 rbnode_t *node; 499 500 for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left); 501 return node; 502 } 503 504 rbnode_t * 505 rbtree_last (rbtree_t *rbtree) 506 { 507 rbnode_t *node; 508 509 for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right); 510 return node; 511 } 512 513 /* 514 * Returns the next node... 515 * 516 */ 517 rbnode_t * 518 rbtree_next (rbnode_t *node) 519 { 520 rbnode_t *parent; 521 522 if (node->right != RBTREE_NULL) { 523 /* One right, then keep on going left... */ 524 for (node = node->right; node->left != RBTREE_NULL; node = node->left); 525 } else { 526 parent = node->parent; 527 while (parent != RBTREE_NULL && node == parent->right) { 528 node = parent; 529 parent = parent->parent; 530 } 531 node = parent; 532 } 533 return node; 534 } 535 536 rbnode_t * 537 rbtree_previous(rbnode_t *node) 538 { 539 rbnode_t *parent; 540 541 if (node->left != RBTREE_NULL) { 542 /* One left, then keep on going right... */ 543 for (node = node->left; node->right != RBTREE_NULL; node = node->right); 544 } else { 545 parent = node->parent; 546 while (parent != RBTREE_NULL && node == parent->left) { 547 node = parent; 548 parent = parent->parent; 549 } 550 node = parent; 551 } 552 return node; 553 } 554