1 /*- 2 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #ifndef UV_TREE_H_ 27 #define UV_TREE_H_ 28 29 #ifndef UV__UNUSED 30 # if __GNUC__ 31 # define UV__UNUSED __attribute__((unused)) 32 # else 33 # define UV__UNUSED 34 # endif 35 #endif 36 37 /* 38 * This file defines data structures for red-black trees. 39 * A red-black tree is a binary search tree with the node color as an 40 * extra attribute. It fulfills a set of conditions: 41 * - every search path from the root to a leaf consists of the 42 * same number of black nodes, 43 * - each red node (except for the root) has a black parent, 44 * - each leaf node is black. 45 * 46 * Every operation on a red-black tree is bounded as O(lg n). 47 * The maximum height of a red-black tree is 2lg (n+1). 48 */ 49 50 /* Macros that define a red-black tree */ 51 #define RB_HEAD(name, type) \ 52 struct name { \ 53 struct type *rbh_root; /* root of the tree */ \ 54 } 55 56 #define RB_INITIALIZER(root) \ 57 { NULL } 58 59 #define RB_INIT(root) do { \ 60 (root)->rbh_root = NULL; \ 61 } while (/*CONSTCOND*/ 0) 62 63 #define RB_BLACK 0 64 #define RB_RED 1 65 #define RB_ENTRY(type) \ 66 struct { \ 67 struct type *rbe_left; /* left element */ \ 68 struct type *rbe_right; /* right element */ \ 69 struct type *rbe_parent; /* parent element */ \ 70 int rbe_color; /* node color */ \ 71 } 72 73 #define RB_LEFT(elm, field) (elm)->field.rbe_left 74 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 75 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 76 #define RB_COLOR(elm, field) (elm)->field.rbe_color 77 #define RB_ROOT(head) (head)->rbh_root 78 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 79 80 #define RB_SET(elm, parent, field) do { \ 81 RB_PARENT(elm, field) = parent; \ 82 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 83 RB_COLOR(elm, field) = RB_RED; \ 84 } while (/*CONSTCOND*/ 0) 85 86 #define RB_SET_BLACKRED(black, red, field) do { \ 87 RB_COLOR(black, field) = RB_BLACK; \ 88 RB_COLOR(red, field) = RB_RED; \ 89 } while (/*CONSTCOND*/ 0) 90 91 #ifndef RB_AUGMENT 92 #define RB_AUGMENT(x) do {} while (0) 93 #endif 94 95 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 96 (tmp) = RB_RIGHT(elm, field); \ 97 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 98 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 99 } \ 100 RB_AUGMENT(elm); \ 101 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 102 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 103 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 104 else \ 105 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 106 } else \ 107 (head)->rbh_root = (tmp); \ 108 RB_LEFT(tmp, field) = (elm); \ 109 RB_PARENT(elm, field) = (tmp); \ 110 RB_AUGMENT(tmp); \ 111 if ((RB_PARENT(tmp, field))) \ 112 RB_AUGMENT(RB_PARENT(tmp, field)); \ 113 } while (/*CONSTCOND*/ 0) 114 115 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 116 (tmp) = RB_LEFT(elm, field); \ 117 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 118 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 119 } \ 120 RB_AUGMENT(elm); \ 121 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 122 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 123 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 124 else \ 125 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 126 } else \ 127 (head)->rbh_root = (tmp); \ 128 RB_RIGHT(tmp, field) = (elm); \ 129 RB_PARENT(elm, field) = (tmp); \ 130 RB_AUGMENT(tmp); \ 131 if ((RB_PARENT(tmp, field))) \ 132 RB_AUGMENT(RB_PARENT(tmp, field)); \ 133 } while (/*CONSTCOND*/ 0) 134 135 /* Generates prototypes and inline functions */ 136 #define RB_PROTOTYPE(name, type, field, cmp) \ 137 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 138 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 139 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 140 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 141 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 142 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 143 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 144 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 145 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 146 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 147 attr struct type *name##_RB_NEXT(struct type *); \ 148 attr struct type *name##_RB_PREV(struct type *); \ 149 attr struct type *name##_RB_MINMAX(struct name *, int); \ 150 \ 151 152 /* Main rb operation. 153 * Moves node close to the key of elm to top 154 */ 155 #define RB_GENERATE(name, type, field, cmp) \ 156 RB_GENERATE_INTERNAL(name, type, field, cmp,) 157 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 158 RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 159 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 160 attr void \ 161 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 162 { \ 163 struct type *parent, *gparent, *tmp; \ 164 while ((parent = RB_PARENT(elm, field)) != NULL && \ 165 RB_COLOR(parent, field) == RB_RED) { \ 166 gparent = RB_PARENT(parent, field); \ 167 if (parent == RB_LEFT(gparent, field)) { \ 168 tmp = RB_RIGHT(gparent, field); \ 169 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 170 RB_COLOR(tmp, field) = RB_BLACK; \ 171 RB_SET_BLACKRED(parent, gparent, field); \ 172 elm = gparent; \ 173 continue; \ 174 } \ 175 if (RB_RIGHT(parent, field) == elm) { \ 176 RB_ROTATE_LEFT(head, parent, tmp, field); \ 177 tmp = parent; \ 178 parent = elm; \ 179 elm = tmp; \ 180 } \ 181 RB_SET_BLACKRED(parent, gparent, field); \ 182 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 183 } else { \ 184 tmp = RB_LEFT(gparent, field); \ 185 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 186 RB_COLOR(tmp, field) = RB_BLACK; \ 187 RB_SET_BLACKRED(parent, gparent, field); \ 188 elm = gparent; \ 189 continue; \ 190 } \ 191 if (RB_LEFT(parent, field) == elm) { \ 192 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 193 tmp = parent; \ 194 parent = elm; \ 195 elm = tmp; \ 196 } \ 197 RB_SET_BLACKRED(parent, gparent, field); \ 198 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 199 } \ 200 } \ 201 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 202 } \ 203 \ 204 attr void \ 205 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 206 struct type *elm) \ 207 { \ 208 struct type *tmp; \ 209 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 210 elm != RB_ROOT(head)) { \ 211 if (RB_LEFT(parent, field) == elm) { \ 212 tmp = RB_RIGHT(parent, field); \ 213 if (RB_COLOR(tmp, field) == RB_RED) { \ 214 RB_SET_BLACKRED(tmp, parent, field); \ 215 RB_ROTATE_LEFT(head, parent, tmp, field); \ 216 tmp = RB_RIGHT(parent, field); \ 217 } \ 218 if ((RB_LEFT(tmp, field) == NULL || \ 219 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 220 (RB_RIGHT(tmp, field) == NULL || \ 221 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 222 RB_COLOR(tmp, field) = RB_RED; \ 223 elm = parent; \ 224 parent = RB_PARENT(elm, field); \ 225 } else { \ 226 if (RB_RIGHT(tmp, field) == NULL || \ 227 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 228 struct type *oleft; \ 229 if ((oleft = RB_LEFT(tmp, field)) \ 230 != NULL) \ 231 RB_COLOR(oleft, field) = RB_BLACK; \ 232 RB_COLOR(tmp, field) = RB_RED; \ 233 RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 234 tmp = RB_RIGHT(parent, field); \ 235 } \ 236 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 237 RB_COLOR(parent, field) = RB_BLACK; \ 238 if (RB_RIGHT(tmp, field)) \ 239 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 240 RB_ROTATE_LEFT(head, parent, tmp, field); \ 241 elm = RB_ROOT(head); \ 242 break; \ 243 } \ 244 } else { \ 245 tmp = RB_LEFT(parent, field); \ 246 if (RB_COLOR(tmp, field) == RB_RED) { \ 247 RB_SET_BLACKRED(tmp, parent, field); \ 248 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 249 tmp = RB_LEFT(parent, field); \ 250 } \ 251 if ((RB_LEFT(tmp, field) == NULL || \ 252 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 253 (RB_RIGHT(tmp, field) == NULL || \ 254 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 255 RB_COLOR(tmp, field) = RB_RED; \ 256 elm = parent; \ 257 parent = RB_PARENT(elm, field); \ 258 } else { \ 259 if (RB_LEFT(tmp, field) == NULL || \ 260 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 261 struct type *oright; \ 262 if ((oright = RB_RIGHT(tmp, field)) \ 263 != NULL) \ 264 RB_COLOR(oright, field) = RB_BLACK; \ 265 RB_COLOR(tmp, field) = RB_RED; \ 266 RB_ROTATE_LEFT(head, tmp, oright, field); \ 267 tmp = RB_LEFT(parent, field); \ 268 } \ 269 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 270 RB_COLOR(parent, field) = RB_BLACK; \ 271 if (RB_LEFT(tmp, field)) \ 272 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 273 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 274 elm = RB_ROOT(head); \ 275 break; \ 276 } \ 277 } \ 278 } \ 279 if (elm) \ 280 RB_COLOR(elm, field) = RB_BLACK; \ 281 } \ 282 \ 283 attr struct type * \ 284 name##_RB_REMOVE(struct name *head, struct type *elm) \ 285 { \ 286 struct type *child, *parent, *old = elm; \ 287 int color; \ 288 if (RB_LEFT(elm, field) == NULL) \ 289 child = RB_RIGHT(elm, field); \ 290 else if (RB_RIGHT(elm, field) == NULL) \ 291 child = RB_LEFT(elm, field); \ 292 else { \ 293 struct type *left; \ 294 elm = RB_RIGHT(elm, field); \ 295 while ((left = RB_LEFT(elm, field)) != NULL) \ 296 elm = left; \ 297 child = RB_RIGHT(elm, field); \ 298 parent = RB_PARENT(elm, field); \ 299 color = RB_COLOR(elm, field); \ 300 if (child) \ 301 RB_PARENT(child, field) = parent; \ 302 if (parent) { \ 303 if (RB_LEFT(parent, field) == elm) \ 304 RB_LEFT(parent, field) = child; \ 305 else \ 306 RB_RIGHT(parent, field) = child; \ 307 RB_AUGMENT(parent); \ 308 } else \ 309 RB_ROOT(head) = child; \ 310 if (RB_PARENT(elm, field) == old) \ 311 parent = elm; \ 312 (elm)->field = (old)->field; \ 313 if (RB_PARENT(old, field)) { \ 314 if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 315 RB_LEFT(RB_PARENT(old, field), field) = elm; \ 316 else \ 317 RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 318 RB_AUGMENT(RB_PARENT(old, field)); \ 319 } else \ 320 RB_ROOT(head) = elm; \ 321 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 322 if (RB_RIGHT(old, field)) \ 323 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 324 if (parent) { \ 325 left = parent; \ 326 do { \ 327 RB_AUGMENT(left); \ 328 } while ((left = RB_PARENT(left, field)) != NULL); \ 329 } \ 330 goto color; \ 331 } \ 332 parent = RB_PARENT(elm, field); \ 333 color = RB_COLOR(elm, field); \ 334 if (child) \ 335 RB_PARENT(child, field) = parent; \ 336 if (parent) { \ 337 if (RB_LEFT(parent, field) == elm) \ 338 RB_LEFT(parent, field) = child; \ 339 else \ 340 RB_RIGHT(parent, field) = child; \ 341 RB_AUGMENT(parent); \ 342 } else \ 343 RB_ROOT(head) = child; \ 344 color: \ 345 if (color == RB_BLACK) \ 346 name##_RB_REMOVE_COLOR(head, parent, child); \ 347 return (old); \ 348 } \ 349 \ 350 /* Inserts a node into the RB tree */ \ 351 attr struct type * \ 352 name##_RB_INSERT(struct name *head, struct type *elm) \ 353 { \ 354 struct type *tmp; \ 355 struct type *parent = NULL; \ 356 int comp = 0; \ 357 tmp = RB_ROOT(head); \ 358 while (tmp) { \ 359 parent = tmp; \ 360 comp = (cmp)(elm, parent); \ 361 if (comp < 0) \ 362 tmp = RB_LEFT(tmp, field); \ 363 else if (comp > 0) \ 364 tmp = RB_RIGHT(tmp, field); \ 365 else \ 366 return (tmp); \ 367 } \ 368 RB_SET(elm, parent, field); \ 369 if (parent != NULL) { \ 370 if (comp < 0) \ 371 RB_LEFT(parent, field) = elm; \ 372 else \ 373 RB_RIGHT(parent, field) = elm; \ 374 RB_AUGMENT(parent); \ 375 } else \ 376 RB_ROOT(head) = elm; \ 377 name##_RB_INSERT_COLOR(head, elm); \ 378 return (NULL); \ 379 } \ 380 \ 381 /* Finds the node with the same key as elm */ \ 382 attr struct type * \ 383 name##_RB_FIND(struct name *head, struct type *elm) \ 384 { \ 385 struct type *tmp = RB_ROOT(head); \ 386 int comp; \ 387 while (tmp) { \ 388 comp = cmp(elm, tmp); \ 389 if (comp < 0) \ 390 tmp = RB_LEFT(tmp, field); \ 391 else if (comp > 0) \ 392 tmp = RB_RIGHT(tmp, field); \ 393 else \ 394 return (tmp); \ 395 } \ 396 return (NULL); \ 397 } \ 398 \ 399 /* Finds the first node greater than or equal to the search key */ \ 400 attr struct type * \ 401 name##_RB_NFIND(struct name *head, struct type *elm) \ 402 { \ 403 struct type *tmp = RB_ROOT(head); \ 404 struct type *res = NULL; \ 405 int comp; \ 406 while (tmp) { \ 407 comp = cmp(elm, tmp); \ 408 if (comp < 0) { \ 409 res = tmp; \ 410 tmp = RB_LEFT(tmp, field); \ 411 } \ 412 else if (comp > 0) \ 413 tmp = RB_RIGHT(tmp, field); \ 414 else \ 415 return (tmp); \ 416 } \ 417 return (res); \ 418 } \ 419 \ 420 /* ARGSUSED */ \ 421 attr struct type * \ 422 name##_RB_NEXT(struct type *elm) \ 423 { \ 424 if (RB_RIGHT(elm, field)) { \ 425 elm = RB_RIGHT(elm, field); \ 426 while (RB_LEFT(elm, field)) \ 427 elm = RB_LEFT(elm, field); \ 428 } else { \ 429 if (RB_PARENT(elm, field) && \ 430 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 431 elm = RB_PARENT(elm, field); \ 432 else { \ 433 while (RB_PARENT(elm, field) && \ 434 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 435 elm = RB_PARENT(elm, field); \ 436 elm = RB_PARENT(elm, field); \ 437 } \ 438 } \ 439 return (elm); \ 440 } \ 441 \ 442 /* ARGSUSED */ \ 443 attr struct type * \ 444 name##_RB_PREV(struct type *elm) \ 445 { \ 446 if (RB_LEFT(elm, field)) { \ 447 elm = RB_LEFT(elm, field); \ 448 while (RB_RIGHT(elm, field)) \ 449 elm = RB_RIGHT(elm, field); \ 450 } else { \ 451 if (RB_PARENT(elm, field) && \ 452 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 453 elm = RB_PARENT(elm, field); \ 454 else { \ 455 while (RB_PARENT(elm, field) && \ 456 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 457 elm = RB_PARENT(elm, field); \ 458 elm = RB_PARENT(elm, field); \ 459 } \ 460 } \ 461 return (elm); \ 462 } \ 463 \ 464 attr struct type * \ 465 name##_RB_MINMAX(struct name *head, int val) \ 466 { \ 467 struct type *tmp = RB_ROOT(head); \ 468 struct type *parent = NULL; \ 469 while (tmp) { \ 470 parent = tmp; \ 471 if (val < 0) \ 472 tmp = RB_LEFT(tmp, field); \ 473 else \ 474 tmp = RB_RIGHT(tmp, field); \ 475 } \ 476 return (parent); \ 477 } 478 479 #define RB_NEGINF -1 480 #define RB_INF 1 481 482 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 483 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 484 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 485 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 486 #define RB_NEXT(name, x) name##_RB_NEXT(x) 487 #define RB_PREV(name, x) name##_RB_PREV(x) 488 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 489 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 490 491 #define RB_FOREACH(x, name, head) \ 492 for ((x) = RB_MIN(name, head); \ 493 (x) != NULL; \ 494 (x) = name##_RB_NEXT(x)) 495 496 #define RB_FOREACH_FROM(x, name, y) \ 497 for ((x) = (y); \ 498 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 499 (x) = (y)) 500 501 #define RB_FOREACH_SAFE(x, name, head, y) \ 502 for ((x) = RB_MIN(name, head); \ 503 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 504 (x) = (y)) 505 506 #define RB_FOREACH_REVERSE(x, name, head) \ 507 for ((x) = RB_MAX(name, head); \ 508 (x) != NULL; \ 509 (x) = name##_RB_PREV(x)) 510 511 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 512 for ((x) = (y); \ 513 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 514 (x) = (y)) 515 516 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 517 for ((x) = RB_MAX(name, head); \ 518 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 519 (x) = (y)) 520 521 #endif /* UV_TREE_H_ */ 522
