1/****************************************************************************** 2 * 3 * Copyright (C) 2002 Jason Evans <jasone@canonware.com>. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice(s), this list of conditions and the following disclaimer 11 * unmodified other than the allowable addition of one or more 12 * copyright notices. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice(s), this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY 19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE 22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 25 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 27 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 28 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 ****************************************************************************** 31 * 32 * cpp macro implementation of red-black trees. Red-black trees are difficult 33 * to explain without lots of diagrams, so little attempt is made to document 34 * this code. However, an excellent discussion can be found in the following 35 * book, which was used as the reference for writing this implementation: 36 * 37 * Introduction to Algorithms 38 * Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest 39 * MIT Press (1990) 40 * ISBN 0-07-013143-0 41 * 42 * Some macros use a comparison function pointer, which is expected to have the 43 * following prototype: 44 * 45 * int (compare *)(<a_type> *a_a, <a_type> *a_b); 46 * 47 * Interpretation of comparision function return values: 48 * 49 * -1 : a_a < a_b 50 * 0 : a_a == a_b 51 * 1 : a_a > a_b 52 * 53 * Some of the macros expand out to be quite a bit of code, so if they are 54 * called in a program in more than a couple of places for a particular type, it 55 * is probably a good idea to create functions that wrap the macros to keep code 56 * size down. 57 * 58 ******************************************************************************/ 59 60/* Node structure. */ 61#define rb_node(a_type) \ 62struct \ 63{ \ 64 a_type *rbn_par; \ 65 a_type *rbn_left; \ 66 a_type *rbn_right; \ 67 boolean_t rbn_red; \ 68} 69 70#define rb_node_new(a_tree, a_node, a_field) \ 71 do \ 72 { \ 73 (a_node)->a_field.rbn_par = &(a_tree)->rbt_nil; \ 74 (a_node)->a_field.rbn_left = &(a_tree)->rbt_nil; \ 75 (a_node)->a_field.rbn_right = &(a_tree)->rbt_nil; \ 76 (a_node)->a_field.rbn_red = FALSE; \ 77 } while (0) 78 79/* Root structure. */ 80#define rb_tree(a_type) \ 81struct \ 82{ \ 83 a_type *rbt_root; \ 84 a_type rbt_nil; \ 85} 86 87#define rb_tree_new(a_tree, a_field) \ 88 do \ 89 { \ 90 (a_tree)->rbt_root = &((a_tree)->rbt_nil); \ 91 rb_node_new(a_tree, &(a_tree)->rbt_nil, a_field); \ 92 } while (0) 93 94#define rb_tree_nil(a_tree) (&(a_tree)->rbt_nil) 95 96/* Operations. */ 97#define rb_root(a_tree) (a_tree)->rbt_root 98 99#define rb_p_first(a_tree, a_root, a_field, r_node) \ 100 do \ 101 { \ 102 for ((r_node) = (a_root); \ 103 (r_node)->a_field.rbn_left != &(a_tree)->rbt_nil; \ 104 (r_node) = (r_node)->a_field.rbn_left) \ 105 { \ 106 } \ 107 } while (0) 108 109#define rb_p_last(a_tree, a_root, a_field, r_node) \ 110 do \ 111 { \ 112 for ((r_node) = (a_root); \ 113 (r_node)->a_field.rbn_right != &(a_tree)->rbt_nil; \ 114 (r_node) = (r_node)->a_field.rbn_right) \ 115 { \ 116 } \ 117 } while (0) 118 119#define rb_first(a_tree, a_field, r_node) \ 120 rb_p_first(a_tree, rb_root(a_tree), a_field, r_node) 121 122#define rb_last(a_tree, a_field, r_node) \ 123 rb_p_last(a_tree, rb_root(a_tree), a_field, r_node) 124 125#define rb_next(a_tree, a_node, a_type, a_field, r_node) \ 126 do \ 127 { \ 128 if ((a_node)->a_field.rbn_right != &(a_tree)->rbt_nil) \ 129 { \ 130 rb_p_first(a_tree, (a_node)->a_field.rbn_right, a_field, \ 131 r_node); \ 132 } \ 133 else \ 134 { \ 135 a_type *t = (a_node); \ 136 (r_node) = (a_node)->a_field.rbn_par; \ 137 while ((r_node) != &(a_tree)->rbt_nil \ 138 && t == (r_node)->a_field.rbn_right) \ 139 { \ 140 t = (r_node); \ 141 (r_node) = (r_node)->a_field.rbn_par; \ 142 } \ 143 } \ 144 } while (0) 145 146#define rb_prev(a_tree, a_node, a_type, a_field, r_node) \ 147 do \ 148 { \ 149 if ((a_node)->a_field.rbn_left != &(a_tree)->rbt_nil) \ 150 { \ 151 rb_p_last(a_tree, (a_node)->a_field.rbn_left, a_field, \ 152 r_node); \ 153 } \ 154 else \ 155 { \ 156 a_type *t = (a_node); \ 157 (r_node) = (a_node)->a_field.rbn_par; \ 158 while ((r_node) != &(a_tree)->rbt_nil \ 159 && t == (r_node)->a_field.rbn_left) \ 160 { \ 161 t = (r_node); \ 162 (r_node) = (r_node)->a_field.rbn_par; \ 163 } \ 164 } \ 165 } while (0) 166 167/* a_key is always the first argument to a_comp. */ 168#define rb_search(a_tree, a_key, a_comp, a_field, r_node) \ 169 do \ 170 { \ 171 int t; \ 172 (r_node) = (a_tree)->rbt_root; \ 173 while ((r_node) != &(a_tree)->rbt_nil \ 174 && (t = (a_comp)((a_key), (r_node))) != 0) \ 175 { \ 176 if (t == -1) \ 177 { \ 178 (r_node) = (r_node)->a_field.rbn_left; \ 179 } \ 180 else \ 181 { \ 182 (r_node) = (r_node)->a_field.rbn_right; \ 183 } \ 184 } \ 185 } while (0) 186 187/* Find a match if it exists. Otherwise, find the next greater node, if one 188 * exists. */ 189#define rb_nsearch(a_tree, a_key, a_comp, a_type, a_field, r_node) \ 190 do \ 191 { \ 192 int t; \ 193 (r_node) = (a_tree)->rbt_root; \ 194 while ((r_node) != &(a_tree)->rbt_nil \ 195 && (t = (a_comp)((a_key), (r_node))) != 0) \ 196 { \ 197 if (t == -1) \ 198 { \ 199 if ((r_node)->a_field.rbn_left == &(a_tree)->rbt_nil) \ 200 { \ 201 break; \ 202 } \ 203 (r_node) = (r_node)->a_field.rbn_left; \ 204 } \ 205 else \ 206 { \ 207 if ((r_node)->a_field.rbn_right == &(a_tree)->rbt_nil) \ 208 { \ 209 a_type *n = (r_node); \ 210 (r_node) = (r_node)->a_field.rbn_par; \ 211 while ((r_node) != &(a_tree)->rbt_nil \ 212 && n == (r_node)->a_field.rbn_right) \ 213 { \ 214 n = (r_node); \ 215 (r_node) = (r_node)->a_field.rbn_par; \ 216 } \ 217 break; \ 218 } \ 219 (r_node) = (r_node)->a_field.rbn_right; \ 220 } \ 221 } \ 222 } while (0) 223 224#define rb_p_left_rotate(a_tree, a_node, a_type, a_field) \ 225 do \ 226 { \ 227 a_type *t = (a_node)->a_field.rbn_right; \ 228 (a_node)->a_field.rbn_right = t->a_field.rbn_left; \ 229 if (t->a_field.rbn_left != &(a_tree)->rbt_nil) \ 230 { \ 231 t->a_field.rbn_left->a_field.rbn_par = (a_node); \ 232 } \ 233 t->a_field.rbn_par = (a_node)->a_field.rbn_par; \ 234 if ((a_node)->a_field.rbn_par == &(a_tree)->rbt_nil) \ 235 { \ 236 (a_tree)->rbt_root = t; \ 237 } \ 238 else if ((a_node) \ 239 == (a_node)->a_field.rbn_par->a_field.rbn_left) \ 240 { \ 241 (a_node)->a_field.rbn_par->a_field.rbn_left = t; \ 242 } \ 243 else \ 244 { \ 245 (a_node)->a_field.rbn_par->a_field.rbn_right = t; \ 246 } \ 247 t->a_field.rbn_left = (a_node); \ 248 (a_node)->a_field.rbn_par = t; \ 249 } while (0) 250 251#define rb_p_right_rotate(a_tree, a_node, a_type, a_field) \ 252 do \ 253 { \ 254 a_type *t = (a_node)->a_field.rbn_left; \ 255 (a_node)->a_field.rbn_left = t->a_field.rbn_right; \ 256 if (t->a_field.rbn_right != &(a_tree)->rbt_nil) \ 257 { \ 258 t->a_field.rbn_right->a_field.rbn_par = (a_node); \ 259 } \ 260 t->a_field.rbn_par = (a_node)->a_field.rbn_par; \ 261 if ((a_node)->a_field.rbn_par == &(a_tree)->rbt_nil) \ 262 { \ 263 (a_tree)->rbt_root = t; \ 264 } \ 265 else if ((a_node) \ 266 == (a_node)->a_field.rbn_par->a_field.rbn_right) \ 267 { \ 268 (a_node)->a_field.rbn_par->a_field.rbn_right = t; \ 269 } \ 270 else \ 271 { \ 272 (a_node)->a_field.rbn_par->a_field.rbn_left = t; \ 273 } \ 274 t->a_field.rbn_right = (a_node); \ 275 (a_node)->a_field.rbn_par = t; \ 276 } while (0) 277 278/* a_node is always the first argument to a_comp. */ 279#define rb_insert(a_tree, a_node, a_comp, a_type, a_field) \ 280 do \ 281 { \ 282 /* Insert. */ \ 283 a_type *x = &(a_tree)->rbt_nil; \ 284 a_type *y = (a_tree)->rbt_root; \ 285 int c = 0; \ 286 while (y != &(a_tree)->rbt_nil) \ 287 { \ 288 x = y; \ 289 c = (a_comp)((a_node), y); \ 290 if (c == -1) \ 291 { \ 292 y = y->a_field.rbn_left; \ 293 } \ 294 else \ 295 { \ 296 y = y->a_field.rbn_right; \ 297 } \ 298 } \ 299 (a_node)->a_field.rbn_par = x; \ 300 if (x == &(a_tree)->rbt_nil) \ 301 { \ 302 (a_tree)->rbt_root = (a_node); \ 303 } \ 304 else if (c == -1) \ 305 { \ 306 x->a_field.rbn_left = (a_node); \ 307 } \ 308 else \ 309 { \ 310 x->a_field.rbn_right = (a_node); \ 311 } \ 312 /* Fix up. */ \ 313 x = (a_node); \ 314 x->a_field.rbn_red = TRUE; \ 315 while (x != (a_tree)->rbt_root \ 316 && x->a_field.rbn_par->a_field.rbn_red) \ 317 { \ 318 y = x->a_field.rbn_par; \ 319 if (y == y->a_field.rbn_par->a_field.rbn_left) \ 320 { \ 321 y = y->a_field.rbn_par->a_field.rbn_right; \ 322 if (y->a_field.rbn_red) \ 323 { \ 324 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 325 y->a_field.rbn_red = FALSE; \ 326 x->a_field.rbn_par->a_field.rbn_par \ 327 ->a_field.rbn_red = TRUE; \ 328 x = x->a_field.rbn_par->a_field.rbn_par; \ 329 } \ 330 else \ 331 { \ 332 if (x == x->a_field.rbn_par->a_field.rbn_right) \ 333 { \ 334 x = x->a_field.rbn_par; \ 335 rb_p_left_rotate(a_tree, x, a_type, a_field); \ 336 } \ 337 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 338 x->a_field.rbn_par->a_field.rbn_par \ 339 ->a_field.rbn_red = TRUE; \ 340 x = x->a_field.rbn_par->a_field.rbn_par; \ 341 rb_p_right_rotate(a_tree, x, a_type, a_field); \ 342 } \ 343 } \ 344 else \ 345 { \ 346 y = y->a_field.rbn_par->a_field.rbn_left; \ 347 if (y->a_field.rbn_red) \ 348 { \ 349 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 350 y->a_field.rbn_red = FALSE; \ 351 x->a_field.rbn_par->a_field.rbn_par \ 352 ->a_field.rbn_red = TRUE; \ 353 x = x->a_field.rbn_par->a_field.rbn_par; \ 354 } \ 355 else \ 356 { \ 357 if (x == x->a_field.rbn_par->a_field.rbn_left) \ 358 { \ 359 x = x->a_field.rbn_par; \ 360 rb_p_right_rotate(a_tree, x, a_type, a_field); \ 361 } \ 362 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 363 x->a_field.rbn_par->a_field.rbn_par \ 364 ->a_field.rbn_red = TRUE; \ 365 x = x->a_field.rbn_par->a_field.rbn_par; \ 366 rb_p_left_rotate(a_tree, x, a_type, a_field); \ 367 } \ 368 } \ 369 } \ 370 (a_tree)->rbt_root->a_field.rbn_red = FALSE; \ 371 } while (0) 372 373#define rb_remove(a_tree, a_node, a_type, a_field) \ 374 do \ 375 { \ 376 boolean_t fixup; \ 377 a_type *x, *y; \ 378 if ((a_node)->a_field.rbn_left == &(a_tree)->rbt_nil \ 379 || (a_node)->a_field.rbn_right == &(a_tree)->rbt_nil) \ 380 { \ 381 y = (a_node); \ 382 } \ 383 else \ 384 { \ 385 rb_next(a_tree, a_node, a_type, a_field, y); \ 386 } \ 387 if (y->a_field.rbn_left != &(a_tree)->rbt_nil) \ 388 { \ 389 x = y->a_field.rbn_left; \ 390 } \ 391 else \ 392 { \ 393 x = y->a_field.rbn_right; \ 394 } \ 395 x->a_field.rbn_par = y->a_field.rbn_par; \ 396 if (y->a_field.rbn_par == &(a_tree)->rbt_nil) \ 397 { \ 398 (a_tree)->rbt_root = x; \ 399 } \ 400 else if (y == y->a_field.rbn_par->a_field.rbn_left) \ 401 { \ 402 y->a_field.rbn_par->a_field.rbn_left = x; \ 403 } \ 404 else \ 405 { \ 406 y->a_field.rbn_par->a_field.rbn_right = x; \ 407 } \ 408 if (y->a_field.rbn_red == FALSE) \ 409 { \ 410 fixup = TRUE; \ 411 } \ 412 else \ 413 { \ 414 fixup = FALSE; \ 415 } \ 416 if (y != (a_node)) \ 417 { \ 418 /* Splice y into a_node's location. */ \ 419 y->a_field.rbn_par = (a_node)->a_field.rbn_par; \ 420 y->a_field.rbn_left = (a_node)->a_field.rbn_left; \ 421 y->a_field.rbn_right = (a_node)->a_field.rbn_right; \ 422 y->a_field.rbn_red = (a_node)->a_field.rbn_red; \ 423 if (y->a_field.rbn_par != &(a_tree)->rbt_nil) \ 424 { \ 425 if (y->a_field.rbn_par->a_field.rbn_left == (a_node)) \ 426 { \ 427 y->a_field.rbn_par->a_field.rbn_left = y; \ 428 } \ 429 else \ 430 { \ 431 y->a_field.rbn_par->a_field.rbn_right = y; \ 432 } \ 433 } \ 434 else \ 435 { \ 436 (a_tree)->rbt_root = y; \ 437 } \ 438 y->a_field.rbn_right->a_field.rbn_par = y; \ 439 y->a_field.rbn_left->a_field.rbn_par = y; \ 440 } \ 441 rb_node_new(a_tree, a_node, a_field); \ 442 if (fixup) \ 443 { \ 444 /* Fix up. */ \ 445 a_type *v, *w; \ 446 while (x != (a_tree)->rbt_root \ 447 && x->a_field.rbn_red == FALSE) \ 448 { \ 449 if (x == x->a_field.rbn_par->a_field.rbn_left) \ 450 { \ 451 w = x->a_field.rbn_par->a_field.rbn_right; \ 452 if (w->a_field.rbn_red) \ 453 { \ 454 w->a_field.rbn_red = FALSE; \ 455 v = x->a_field.rbn_par; \ 456 v->a_field.rbn_red = TRUE; \ 457 rb_p_left_rotate(a_tree, v, a_type, a_field); \ 458 w = x->a_field.rbn_par->a_field.rbn_right; \ 459 } \ 460 if (w->a_field.rbn_left->a_field.rbn_red \ 461 == FALSE \ 462 && w->a_field.rbn_right->a_field.rbn_red \ 463 == FALSE) \ 464 { \ 465 w->a_field.rbn_red = TRUE; \ 466 x = x->a_field.rbn_par; \ 467 } \ 468 else \ 469 { \ 470 if (w->a_field.rbn_right->a_field.rbn_red \ 471 == FALSE) \ 472 { \ 473 w->a_field.rbn_left->a_field.rbn_red \ 474 = FALSE; \ 475 w->a_field.rbn_red = TRUE; \ 476 rb_p_right_rotate(a_tree, w, a_type, \ 477 a_field); \ 478 w = x->a_field.rbn_par->a_field.rbn_right; \ 479 } \ 480 w->a_field.rbn_red \ 481 = x->a_field.rbn_par->a_field.rbn_red; \ 482 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 483 w->a_field.rbn_right->a_field.rbn_red = FALSE; \ 484 v = x->a_field.rbn_par; \ 485 rb_p_left_rotate(a_tree, v, a_type, a_field); \ 486 break; \ 487 } \ 488 } \ 489 else \ 490 { \ 491 w = x->a_field.rbn_par->a_field.rbn_left; \ 492 if (w->a_field.rbn_red) \ 493 { \ 494 w->a_field.rbn_red = FALSE; \ 495 v = x->a_field.rbn_par; \ 496 v->a_field.rbn_red = TRUE; \ 497 rb_p_right_rotate(a_tree, v, a_type, a_field); \ 498 w = x->a_field.rbn_par->a_field.rbn_left; \ 499 } \ 500 if (w->a_field.rbn_right->a_field.rbn_red \ 501 == FALSE \ 502 && w->a_field.rbn_left->a_field.rbn_red \ 503 == FALSE) \ 504 { \ 505 w->a_field.rbn_red = TRUE; \ 506 x = x->a_field.rbn_par; \ 507 } \ 508 else \ 509 { \ 510 if (w->a_field.rbn_left->a_field.rbn_red \ 511 == FALSE) \ 512 { \ 513 w->a_field.rbn_right->a_field.rbn_red \ 514 = FALSE; \ 515 w->a_field.rbn_red = TRUE; \ 516 rb_p_left_rotate(a_tree, w, a_type, \ 517 a_field); \ 518 w = x->a_field.rbn_par->a_field.rbn_left; \ 519 } \ 520 w->a_field.rbn_red \ 521 = x->a_field.rbn_par->a_field.rbn_red; \ 522 x->a_field.rbn_par->a_field.rbn_red = FALSE; \ 523 w->a_field.rbn_left->a_field.rbn_red = FALSE; \ 524 v = x->a_field.rbn_par; \ 525 rb_p_right_rotate(a_tree, v, a_type, a_field); \ 526 break; \ 527 } \ 528 } \ 529 } \ 530 x->a_field.rbn_red = FALSE; \ 531 } \ 532 } while (0) 533