1 /***************************************************************************** 2 * 3 * Copyright (C) 2001 Mark Edel 4 * Copyright (C) 2008 Andreas Öman 5 6 * This is free software; you can redistribute it and/or modify it under the 7 * terms of the GNU General Public License as published by the Free Software 8 * Foundation; either version 2 of the License, or (at your option) any later 9 * version. 10 * 11 * This software is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * for more details. 15 * 16 * You should have received a copy of the GNU General Public License along with 17 * software; if not, write to the Free Software Foundation, Inc., 51 Franklin 18 * Street, Fifth Floor, Boston, MA 02110-1301 USA 19 * 20 * Written by Mark Edel 21 * Macroified + additional support functions by Andreas Öman 22 * 23 *****************************************************************************/ 24 25 #ifndef REDBLACK_H_ 26 #define REDBLACK_H_ 27 28 #define RB_TREE_NODE_RED 0 29 #define RB_TREE_NODE_BLACK 1 30 31 32 #define RB_HEAD(name, type) \ 33 struct name { \ 34 struct type *first, *last, *root; \ 35 int entries; \ 36 } 37 38 #define RB_ENTRY(type) \ 39 struct { \ 40 struct type *left, *right, *parent; \ 41 int color; \ 42 } 43 44 #define RB_INIT(head) \ 45 do { \ 46 (head)->first = NULL; \ 47 (head)->last = NULL; \ 48 (head)->root = NULL; \ 49 (head)->entries = 0; \ 50 } while(0) 51 52 53 54 #define RB_ROTATE_LEFT(x, field, root) \ 55 do { \ 56 typeof(x) xx = x; \ 57 typeof(x) yy = xx->field.right; \ 58 \ 59 xx->field.right = yy->field.left; \ 60 if(yy->field.left != NULL) \ 61 yy->field.left->field.parent = xx; \ 62 \ 63 yy->field.parent = xx->field.parent; \ 64 \ 65 if(xx == root) \ 66 root = yy; \ 67 else if(xx == xx->field.parent->field.left) \ 68 xx->field.parent->field.left = yy; \ 69 else \ 70 xx->field.parent->field.right = yy; \ 71 yy->field.left = xx; \ 72 xx->field.parent = yy; \ 73 } while(0) 74 75 76 #define RB_ROTATE_RIGHT(x, field, root) \ 77 do { \ 78 typeof(x) xx = x; \ 79 typeof(x) yy = xx->field.left; \ 80 \ 81 xx->field.left = yy->field.right; \ 82 if (yy->field.right != NULL) \ 83 yy->field.right->field.parent = xx; \ 84 yy->field.parent = xx->field.parent; \ 85 \ 86 if (xx == root) \ 87 root = yy; \ 88 else if (xx == xx->field.parent->field.right) \ 89 xx->field.parent->field.right = yy; \ 90 else \ 91 xx->field.parent->field.left = yy; \ 92 yy->field.right = xx; \ 93 xx->field.parent = yy; \ 94 } while(0) 95 96 97 98 #define RB_INSERT_BALANCE(x, field, root) \ 99 do { \ 100 typeof(x) y; \ 101 \ 102 x->field.color = RB_TREE_NODE_RED; \ 103 while (x != root && x->field.parent->field.color == RB_TREE_NODE_RED) { \ 104 if (x->field.parent == x->field.parent->field.parent->field.left) { \ 105 y = x->field.parent->field.parent->field.right; \ 106 if (y && y->field.color == RB_TREE_NODE_RED) { \ 107 x->field.parent->field.color = RB_TREE_NODE_BLACK; \ 108 y->field.color = RB_TREE_NODE_BLACK; \ 109 x->field.parent->field.parent->field.color = RB_TREE_NODE_RED; \ 110 x = x->field.parent->field.parent; \ 111 } \ 112 else { \ 113 if (x == x->field.parent->field.right) { \ 114 x = x->field.parent; \ 115 RB_ROTATE_LEFT(x, field, root); \ 116 } \ 117 x->field.parent->field.color = RB_TREE_NODE_BLACK; \ 118 x->field.parent->field.parent->field.color = RB_TREE_NODE_RED; \ 119 RB_ROTATE_RIGHT(x->field.parent->field.parent, field, root); \ 120 } \ 121 } \ 122 else { \ 123 y = x->field.parent->field.parent->field.left; \ 124 if (y && y->field.color == RB_TREE_NODE_RED) { \ 125 x->field.parent->field.color = RB_TREE_NODE_BLACK; \ 126 y->field.color = RB_TREE_NODE_BLACK; \ 127 x->field.parent->field.parent->field.color = RB_TREE_NODE_RED; \ 128 x = x->field.parent->field.parent; \ 129 } \ 130 else { \ 131 if (x == x->field.parent->field.left) { \ 132 x = x->field.parent; \ 133 RB_ROTATE_RIGHT(x, field, root); \ 134 } \ 135 x->field.parent->field.color = RB_TREE_NODE_BLACK; \ 136 x->field.parent->field.parent->field.color = RB_TREE_NODE_RED; \ 137 RB_ROTATE_LEFT(x->field.parent->field.parent, field, root); \ 138 } \ 139 } \ 140 } \ 141 root->field.color = RB_TREE_NODE_BLACK; \ 142 } while(0); 143 144 145 /** 146 * Insert a new node, if a collision occures the colliding node is returned 147 */ 148 #define RB_INSERT_SORTED(head, skel, field, cmpfunc) \ 149 ({ \ 150 int res, fromleft = 0; \ 151 typeof(skel) x = skel, c, parent = NULL; \ 152 \ 153 c = (head)->root; \ 154 while(c != NULL) { \ 155 res = cmpfunc(x, c); \ 156 if(res < 0) { \ 157 parent = c; \ 158 c = c->field.left; \ 159 fromleft = 1; \ 160 } else if(res > 0) { \ 161 parent = c; \ 162 c = c->field.right; \ 163 fromleft = 0; \ 164 } else { \ 165 break; \ 166 } \ 167 } \ 168 if(c == NULL) { \ 169 x->field.parent = parent; \ 170 x->field.left = NULL; \ 171 x->field.right = NULL; \ 172 x->field.color = RB_TREE_NODE_RED; \ 173 \ 174 if(parent) { \ 175 if(fromleft) \ 176 parent->field.left = x; \ 177 else \ 178 parent->field.right = x; \ 179 } else { \ 180 (head)->root = x; \ 181 } \ 182 (head)->entries++; \ 183 \ 184 if(x->field.parent == (head)->first && \ 185 (x->field.parent == NULL || x->field.parent->field.left == x)) { \ 186 (head)->first = x; \ 187 } \ 188 \ 189 if(x->field.parent == (head)->last && \ 190 (x->field.parent == NULL || x->field.parent->field.right == x)) { \ 191 (head)->last = x; \ 192 } \ 193 RB_INSERT_BALANCE(x, field, (head)->root); \ 194 } \ 195 c; \ 196 }) 197 198 199 /** 200 * Returns next node 201 */ 202 #define RB_NEXT(e, field) \ 203 ({ \ 204 typeof(e) xx = e, f; \ 205 if (xx->field.right != NULL) { \ 206 xx = xx->field.right; \ 207 while (xx->field.left != NULL) { \ 208 xx = xx->field.left; \ 209 } \ 210 } \ 211 else { \ 212 do { \ 213 f = xx; \ 214 xx = xx->field.parent; \ 215 } while (xx && f == xx->field.right); \ 216 } \ 217 xx; \ 218 }) 219 220 221 /** 222 * Returns previous node 223 */ 224 #define RB_PREV(e, field) \ 225 ({ \ 226 typeof(e) xx = e, f; \ 227 if (xx->field.left != NULL) { \ 228 xx = xx->field.left; \ 229 while (xx->field.right != NULL) { \ 230 xx = xx->field.right; \ 231 } \ 232 } \ 233 else { \ 234 do { \ 235 f = xx; \ 236 xx = xx->field.parent; \ 237 } while (xx && f == xx->field.left); \ 238 } \ 239 xx; \ 240 }) 241 242 243 /** 244 * Returns first node 245 */ 246 #define RB_FIRST(head) ((head)->first) 247 248 /** 249 * Returns last node 250 */ 251 #define RB_LAST(head) ((head)->last) 252 253 /** 254 * Iterate thru all nodes 255 */ 256 #define RB_FOREACH(e, head, field) \ 257 for(e = (head)->first; e != NULL; \ 258 ({ \ 259 if(e->field.right != NULL) { \ 260 e = e->field.right; \ 261 while(e->field.left != NULL) { \ 262 e = e->field.left; \ 263 } \ 264 } else { \ 265 typeof(e) f; \ 266 do { \ 267 f = e; \ 268 e = e->field.parent; \ 269 } while(e && f == e->field.right); \ 270 } \ 271 })) 272 273 274 /** 275 * Iterate thru all nodes in reverse order 276 */ 277 #define RB_FOREACH_REVERSE(e, head, field) \ 278 for(e = (head)->last; e != NULL; \ 279 ({ \ 280 if(e->field.left != NULL) { \ 281 e = e->field.left; \ 282 while(e->field.right != NULL) { \ 283 e = e->field.right; \ 284 } \ 285 } else { \ 286 typeof(e) f; \ 287 do { \ 288 f = e; \ 289 e = e->field.parent; \ 290 } while(e && f == e->field.left); \ 291 } \ 292 })) 293 294 /** 295 * Remove the given node 296 */ 297 #define RB_REMOVE(head, e, field) \ 298 do { \ 299 int swapColor; \ 300 typeof(e) x, y, z = e, x_parent, w; \ 301 \ 302 y = z; \ 303 if (y == (head)->first) { \ 304 (head)->first = RB_NEXT(y, field); \ 305 } \ 306 if (y == (head)->last) { \ 307 (head)->last = RB_PREV(y, field); \ 308 } \ 309 if (y->field.left == NULL) { \ 310 x = y->field.right; \ 311 } \ 312 else { \ 313 if (y->field.right == NULL) { \ 314 x = y->field.left; \ 315 } \ 316 else { \ 317 y = y->field.right; \ 318 while (y->field.left != NULL) { \ 319 y = y->field.left; \ 320 } \ 321 x = y->field.right; \ 322 } \ 323 } \ 324 if (y != z) { \ 325 z->field.left->field.parent = y; \ 326 y->field.left = z->field.left; \ 327 if (y != z->field.right) { \ 328 x_parent = y->field.parent; \ 329 if (x != NULL) { \ 330 x->field.parent = y->field.parent; \ 331 } \ 332 y->field.parent->field.left = x; \ 333 y->field.right = z->field.right; \ 334 z->field.right->field.parent = y; \ 335 } \ 336 else { \ 337 x_parent = y; \ 338 } \ 339 if ((head)->root == z) { \ 340 (head)->root = y; \ 341 } \ 342 else if (z->field.parent->field.left == z) { \ 343 z->field.parent->field.left = y; \ 344 } \ 345 else { \ 346 z->field.parent->field.right = y; \ 347 } \ 348 y->field.parent = z->field.parent; \ 349 \ 350 swapColor = y->field.color; \ 351 y->field.color = z->field.color; \ 352 z->field.color = swapColor; \ 353 \ 354 y = z; \ 355 } \ 356 else { \ 357 x_parent = y->field.parent; \ 358 if (x != NULL) { \ 359 x->field.parent = y->field.parent; \ 360 } \ 361 if ((head)->root == z) { \ 362 (head)->root = x; \ 363 } \ 364 else { \ 365 if (z->field.parent->field.left == z) { \ 366 z->field.parent->field.left = x; \ 367 } \ 368 else { \ 369 z->field.parent->field.right = x; \ 370 } \ 371 } \ 372 } \ 373 \ 374 (head)->entries--; \ 375 \ 376 if (y->field.color != RB_TREE_NODE_RED) { \ 377 while (x != (head)->root && \ 378 (x == NULL || x->field.color == RB_TREE_NODE_BLACK)) { \ 379 if (x == x_parent->field.left) { \ 380 w = x_parent->field.right; \ 381 if (w->field.color == RB_TREE_NODE_RED) { \ 382 w->field.color = RB_TREE_NODE_BLACK; \ 383 x_parent->field.color = RB_TREE_NODE_RED; \ 384 RB_ROTATE_LEFT(x_parent, field, (head)->root); \ 385 w = x_parent->field.right; \ 386 } \ 387 if ((w->field.left == NULL || \ 388 w->field.left->field.color == RB_TREE_NODE_BLACK) && \ 389 (w->field.right == NULL || \ 390 w->field.right->field.color == RB_TREE_NODE_BLACK)) { \ 391 \ 392 w->field.color = RB_TREE_NODE_RED; \ 393 x = x_parent; \ 394 x_parent = x_parent->field.parent; \ 395 } else { \ 396 if (w->field.right == NULL || \ 397 w->field.right->field.color == RB_TREE_NODE_BLACK) { \ 398 \ 399 if (w->field.left) { \ 400 w->field.left->field.color = RB_TREE_NODE_BLACK; \ 401 } \ 402 w->field.color = RB_TREE_NODE_RED; \ 403 RB_ROTATE_RIGHT(w, field, (head)->root); \ 404 w = x_parent->field.right; \ 405 } \ 406 w->field.color = x_parent->field.color; \ 407 x_parent->field.color = RB_TREE_NODE_BLACK; \ 408 if (w->field.right) { \ 409 w->field.right->field.color = RB_TREE_NODE_BLACK; \ 410 } \ 411 RB_ROTATE_LEFT(x_parent, field, (head)->root); \ 412 break; \ 413 } \ 414 } \ 415 else { \ 416 w = x_parent->field.left; \ 417 if (w->field.color == RB_TREE_NODE_RED) { \ 418 w->field.color = RB_TREE_NODE_BLACK; \ 419 x_parent->field.color = RB_TREE_NODE_RED; \ 420 RB_ROTATE_RIGHT(x_parent, field, (head)->root); \ 421 w = x_parent->field.left; \ 422 } \ 423 if ((w->field.right == NULL || \ 424 w->field.right->field.color == RB_TREE_NODE_BLACK) && \ 425 (w->field.left == NULL || \ 426 w->field.left->field.color == RB_TREE_NODE_BLACK)) { \ 427 \ 428 w->field.color = RB_TREE_NODE_RED; \ 429 x = x_parent; \ 430 x_parent = x_parent->field.parent; \ 431 } \ 432 else { \ 433 if (w->field.left == NULL || \ 434 w->field.left->field.color == RB_TREE_NODE_BLACK) { \ 435 \ 436 if (w->field.right) { \ 437 w->field.right->field.color = RB_TREE_NODE_BLACK; \ 438 } \ 439 w->field.color = RB_TREE_NODE_RED; \ 440 RB_ROTATE_LEFT(w, field, (head)->root); \ 441 w = x_parent->field.left; \ 442 } \ 443 w->field.color = x_parent->field.color; \ 444 x_parent->field.color = RB_TREE_NODE_BLACK; \ 445 if (w->field.left) { \ 446 w->field.left->field.color = RB_TREE_NODE_BLACK; \ 447 } \ 448 RB_ROTATE_RIGHT(x_parent, field, (head)->root); \ 449 break; \ 450 } \ 451 } \ 452 } \ 453 if (x) { \ 454 x->field.color = RB_TREE_NODE_BLACK; \ 455 } \ 456 } \ 457 } while(0) 458 459 460 461 /** 462 * Finds a node 463 */ 464 #define RB_FIND(head, skel, field, cmpfunc) \ 465 ({ \ 466 int res; \ 467 typeof(skel) c = (head)->root; \ 468 while(c != NULL) { \ 469 res = cmpfunc(skel, c); \ 470 if(res < 0) { \ 471 c = c->field.left; \ 472 } else if(res > 0) { \ 473 c = c->field.right; \ 474 } else { \ 475 break; \ 476 } \ 477 } \ 478 c; \ 479 }) 480 481 482 483 /** 484 * Finds first node greater than 'skel' 485 */ 486 #define RB_FIND_GT(head, skel, field, cmpfunc) \ 487 ({ \ 488 int res; \ 489 typeof(skel) c = (head)->root, x = NULL; \ 490 while(c != NULL) { \ 491 res = cmpfunc(skel, c); \ 492 if(res < 0) { \ 493 x = c; \ 494 c = c->field.left; \ 495 } else if(res > 0) { \ 496 c = c->field.right; \ 497 } else { \ 498 x = RB_NEXT(c, field); \ 499 break; \ 500 } \ 501 } \ 502 x; \ 503 }) 504 505 /** 506 * Finds a node greater or equal to 'skel' 507 */ 508 #define RB_FIND_GE(head, skel, field, cmpfunc) \ 509 ({ \ 510 int res; \ 511 typeof(skel) c = (head)->root, x = NULL; \ 512 while(c != NULL) { \ 513 res = cmpfunc(skel, c); \ 514 if(res < 0) { \ 515 x = c; \ 516 c = c->field.left; \ 517 } else if(res > 0) { \ 518 c = c->field.right; \ 519 } else { \ 520 x = c; \ 521 break; \ 522 } \ 523 } \ 524 x; \ 525 }) 526 527 528 /** 529 * Finds first node lesser than 'skel' 530 */ 531 #define RB_FIND_LT(head, skel, field, cmpfunc) \ 532 ({ \ 533 int res; \ 534 typeof(skel) c = (head)->root, x = NULL; \ 535 while(c != NULL) { \ 536 res = cmpfunc(skel, c); \ 537 if(res < 0) { \ 538 c = c->field.left; \ 539 } else if(res > 0) { \ 540 x = c; \ 541 c = c->field.right; \ 542 } else { \ 543 x = RB_PREV(c, field); \ 544 break; \ 545 } \ 546 } \ 547 x; \ 548 }) 549 550 /** 551 * Finds a node lesser or equal to 'skel' 552 */ 553 #define RB_FIND_LE(head, skel, field, cmpfunc) \ 554 ({ \ 555 int res; \ 556 typeof(skel) c = (head)->root, x = NULL; \ 557 while(c != NULL) { \ 558 res = cmpfunc(skel, c); \ 559 if(res < 0) { \ 560 c = c->field.left; \ 561 } else if(res > 0) { \ 562 x = c; \ 563 c = c->field.right; \ 564 } else { \ 565 x = c; \ 566 break; \ 567 } \ 568 } \ 569 x; \ 570 }) 571 572 #endif /* REDBLACK_H_ */ 573