1 /* $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $ */ 2 /* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3 /* $FreeBSD$ */ 4 5 /*- 6 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #ifndef _SYS_TREE_H_ 31 #define _SYS_TREE_H_ 32 33 #include <sys/cdefs.h> 34 35 /* 36 * This file defines data structures for different types of trees: 37 * splay trees and red-black trees. 38 * 39 * A splay tree is a self-organizing data structure. Every operation 40 * on the tree causes a splay to happen. The splay moves the requested 41 * node to the root of the tree and partly rebalances it. 42 * 43 * This has the benefit that request locality causes faster lookups as 44 * the requested nodes move to the top of the tree. On the other hand, 45 * every lookup causes memory writes. 46 * 47 * The Balance Theorem bounds the total access time for m operations 48 * and n inserts on an initially empty tree as O((m + n)lg n). The 49 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 50 * 51 * A red-black tree is a binary search tree with the node color as an 52 * extra attribute. It fulfills a set of conditions: 53 * - every search path from the root to a leaf consists of the 54 * same number of black nodes, 55 * - each red node (except for the root) has a black parent, 56 * - each leaf node is black. 57 * 58 * Every operation on a red-black tree is bounded as O(lg n). 59 * The maximum height of a red-black tree is 2lg (n+1). 60 */ 61 62 #define SPLAY_HEAD(name, type) \ 63 struct name { \ 64 struct type *sph_root; /* root of the tree */ \ 65 } 66 67 #define SPLAY_INITIALIZER(root) \ 68 { NULL } 69 70 #define SPLAY_INIT(root) do { \ 71 (root)->sph_root = NULL; \ 72 } while (/*CONSTCOND*/ 0) 73 74 #define SPLAY_ENTRY(type) \ 75 struct { \ 76 struct type *spe_left; /* left element */ \ 77 struct type *spe_right; /* right element */ \ 78 } 79 80 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 81 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 82 #define SPLAY_ROOT(head) (head)->sph_root 83 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 84 85 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 86 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 87 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 88 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 89 (head)->sph_root = tmp; \ 90 } while (/*CONSTCOND*/ 0) 91 92 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 93 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 95 (head)->sph_root = tmp; \ 96 } while (/*CONSTCOND*/ 0) 97 98 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 99 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 100 tmp = (head)->sph_root; \ 101 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 102 } while (/*CONSTCOND*/ 0) 103 104 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 105 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 106 tmp = (head)->sph_root; \ 107 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 108 } while (/*CONSTCOND*/ 0) 109 110 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 111 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 112 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 113 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 114 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 115 } while (/*CONSTCOND*/ 0) 116 117 /* Generates prototypes and inline functions */ 118 119 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 120 void name##_SPLAY(struct name *, struct type *); \ 121 void name##_SPLAY_MINMAX(struct name *, int); \ 122 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 123 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 124 \ 125 /* Finds the node with the same key as elm */ \ 126 static __inline struct type * \ 127 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 128 { \ 129 if (SPLAY_EMPTY(head)) \ 130 return(NULL); \ 131 name##_SPLAY(head, elm); \ 132 if ((cmp)(elm, (head)->sph_root) == 0) \ 133 return (head->sph_root); \ 134 return (NULL); \ 135 } \ 136 \ 137 static __inline struct type * \ 138 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 139 { \ 140 name##_SPLAY(head, elm); \ 141 if (SPLAY_RIGHT(elm, field) != NULL) { \ 142 elm = SPLAY_RIGHT(elm, field); \ 143 while (SPLAY_LEFT(elm, field) != NULL) { \ 144 elm = SPLAY_LEFT(elm, field); \ 145 } \ 146 } else \ 147 elm = NULL; \ 148 return (elm); \ 149 } \ 150 \ 151 static __inline struct type * \ 152 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 153 { \ 154 name##_SPLAY_MINMAX(head, val); \ 155 return (SPLAY_ROOT(head)); \ 156 } 157 158 /* Main splay operation. 159 * Moves node close to the key of elm to top 160 */ 161 #define SPLAY_GENERATE(name, type, field, cmp) \ 162 struct type * \ 163 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 164 { \ 165 if (SPLAY_EMPTY(head)) { \ 166 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 167 } else { \ 168 int __comp; \ 169 name##_SPLAY(head, elm); \ 170 __comp = (cmp)(elm, (head)->sph_root); \ 171 if(__comp < 0) { \ 172 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 173 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 174 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 175 } else if (__comp > 0) { \ 176 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 177 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 178 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 179 } else \ 180 return ((head)->sph_root); \ 181 } \ 182 (head)->sph_root = (elm); \ 183 return (NULL); \ 184 } \ 185 \ 186 struct type * \ 187 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 188 { \ 189 struct type *__tmp; \ 190 if (SPLAY_EMPTY(head)) \ 191 return (NULL); \ 192 name##_SPLAY(head, elm); \ 193 if ((cmp)(elm, (head)->sph_root) == 0) { \ 194 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 195 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 196 } else { \ 197 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 198 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 199 name##_SPLAY(head, elm); \ 200 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 201 } \ 202 return (elm); \ 203 } \ 204 return (NULL); \ 205 } \ 206 \ 207 void \ 208 name##_SPLAY(struct name *head, struct type *elm) \ 209 { \ 210 struct type __node, *__left, *__right, *__tmp; \ 211 int __comp; \ 212 \ 213 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 214 __left = __right = &__node; \ 215 \ 216 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 217 if (__comp < 0) { \ 218 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 219 if (__tmp == NULL) \ 220 break; \ 221 if ((cmp)(elm, __tmp) < 0){ \ 222 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 223 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 224 break; \ 225 } \ 226 SPLAY_LINKLEFT(head, __right, field); \ 227 } else if (__comp > 0) { \ 228 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 229 if (__tmp == NULL) \ 230 break; \ 231 if ((cmp)(elm, __tmp) > 0){ \ 232 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 233 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 234 break; \ 235 } \ 236 SPLAY_LINKRIGHT(head, __left, field); \ 237 } \ 238 } \ 239 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 240 } \ 241 \ 242 /* Splay with either the minimum or the maximum element \ 243 * Used to find minimum or maximum element in tree. \ 244 */ \ 245 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 246 { \ 247 struct type __node, *__left, *__right, *__tmp; \ 248 \ 249 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 250 __left = __right = &__node; \ 251 \ 252 while (1) { \ 253 if (__comp < 0) { \ 254 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 255 if (__tmp == NULL) \ 256 break; \ 257 if (__comp < 0){ \ 258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 259 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 260 break; \ 261 } \ 262 SPLAY_LINKLEFT(head, __right, field); \ 263 } else if (__comp > 0) { \ 264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 265 if (__tmp == NULL) \ 266 break; \ 267 if (__comp > 0) { \ 268 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 270 break; \ 271 } \ 272 SPLAY_LINKRIGHT(head, __left, field); \ 273 } \ 274 } \ 275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 276 } 277 278 #define SPLAY_NEGINF -1 279 #define SPLAY_INF 1 280 281 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 282 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 283 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 284 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 285 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 286 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 287 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 288 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 289 290 #define SPLAY_FOREACH(x, name, head) \ 291 for ((x) = SPLAY_MIN(name, head); \ 292 (x) != NULL; \ 293 (x) = SPLAY_NEXT(name, head, x)) 294 295 /* Macros that define a red-black tree */ 296 #define RB_HEAD(name, type) \ 297 struct name { \ 298 struct type *rbh_root; /* root of the tree */ \ 299 } 300 301 #define RB_INITIALIZER(root) \ 302 { NULL } 303 304 #define RB_INIT(root) do { \ 305 (root)->rbh_root = NULL; \ 306 } while (/*CONSTCOND*/ 0) 307 308 #define RB_BLACK 0 309 #define RB_RED 1 310 #define RB_ENTRY(type) \ 311 struct { \ 312 struct type *rbe_left; /* left element */ \ 313 struct type *rbe_right; /* right element */ \ 314 struct type *rbe_parent; /* parent element */ \ 315 int rbe_color; /* node color */ \ 316 } 317 318 #define RB_LEFT(elm, field) (elm)->field.rbe_left 319 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 320 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 321 #define RB_COLOR(elm, field) (elm)->field.rbe_color 322 #define RB_ROOT(head) (head)->rbh_root 323 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 324 325 #define RB_SET(elm, parent, field) do { \ 326 RB_PARENT(elm, field) = parent; \ 327 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 328 RB_COLOR(elm, field) = RB_RED; \ 329 } while (/*CONSTCOND*/ 0) 330 331 #define RB_SET_BLACKRED(black, red, field) do { \ 332 RB_COLOR(black, field) = RB_BLACK; \ 333 RB_COLOR(red, field) = RB_RED; \ 334 } while (/*CONSTCOND*/ 0) 335 336 #ifndef RB_AUGMENT 337 #define RB_AUGMENT(x) do {} while (0) 338 #endif 339 340 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 341 (tmp) = RB_RIGHT(elm, field); \ 342 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 343 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 344 } \ 345 RB_AUGMENT(elm); \ 346 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 347 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 348 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 349 else \ 350 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 351 } else \ 352 (head)->rbh_root = (tmp); \ 353 RB_LEFT(tmp, field) = (elm); \ 354 RB_PARENT(elm, field) = (tmp); \ 355 RB_AUGMENT(tmp); \ 356 if ((RB_PARENT(tmp, field))) \ 357 RB_AUGMENT(RB_PARENT(tmp, field)); \ 358 } while (/*CONSTCOND*/ 0) 359 360 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 361 (tmp) = RB_LEFT(elm, field); \ 362 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 363 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 364 } \ 365 RB_AUGMENT(elm); \ 366 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 367 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 368 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 369 else \ 370 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 371 } else \ 372 (head)->rbh_root = (tmp); \ 373 RB_RIGHT(tmp, field) = (elm); \ 374 RB_PARENT(elm, field) = (tmp); \ 375 RB_AUGMENT(tmp); \ 376 if ((RB_PARENT(tmp, field))) \ 377 RB_AUGMENT(RB_PARENT(tmp, field)); \ 378 } while (/*CONSTCOND*/ 0) 379 380 /* Generates prototypes and inline functions */ 381 #define RB_PROTOTYPE(name, type, field, cmp) \ 382 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 383 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 384 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 385 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 386 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 387 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 388 RB_PROTOTYPE_INSERT(name, type, attr); \ 389 RB_PROTOTYPE_REMOVE(name, type, attr); \ 390 RB_PROTOTYPE_FIND(name, type, attr); \ 391 RB_PROTOTYPE_NFIND(name, type, attr); \ 392 RB_PROTOTYPE_NEXT(name, type, attr); \ 393 RB_PROTOTYPE_PREV(name, type, attr); \ 394 RB_PROTOTYPE_MINMAX(name, type, attr); 395 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 396 attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 397 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 398 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *) 399 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 400 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 401 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 402 attr struct type *name##_RB_INSERT(struct name *, struct type *) 403 #define RB_PROTOTYPE_FIND(name, type, attr) \ 404 attr struct type *name##_RB_FIND(struct name *, struct type *) 405 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 406 attr struct type *name##_RB_NFIND(struct name *, struct type *) 407 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 408 attr struct type *name##_RB_NEXT(struct type *) 409 #define RB_PROTOTYPE_PREV(name, type, attr) \ 410 attr struct type *name##_RB_PREV(struct type *) 411 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 412 attr struct type *name##_RB_MINMAX(struct name *, int) 413 414 /* Main rb operation. 415 * Moves node close to the key of elm to top 416 */ 417 #define RB_GENERATE(name, type, field, cmp) \ 418 RB_GENERATE_INTERNAL(name, type, field, cmp,) 419 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 420 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 421 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 422 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 423 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 424 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 425 RB_GENERATE_REMOVE(name, type, field, attr) \ 426 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 427 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 428 RB_GENERATE_NEXT(name, type, field, attr) \ 429 RB_GENERATE_PREV(name, type, field, attr) \ 430 RB_GENERATE_MINMAX(name, type, field, attr) 431 432 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 433 attr void \ 434 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 435 { \ 436 struct type *parent, *gparent, *tmp; \ 437 while ((parent = RB_PARENT(elm, field)) != NULL && \ 438 RB_COLOR(parent, field) == RB_RED) { \ 439 gparent = RB_PARENT(parent, field); \ 440 if (parent == RB_LEFT(gparent, field)) { \ 441 tmp = RB_RIGHT(gparent, field); \ 442 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 443 RB_COLOR(tmp, field) = RB_BLACK; \ 444 RB_SET_BLACKRED(parent, gparent, field);\ 445 elm = gparent; \ 446 continue; \ 447 } \ 448 if (RB_RIGHT(parent, field) == elm) { \ 449 RB_ROTATE_LEFT(head, parent, tmp, field);\ 450 tmp = parent; \ 451 parent = elm; \ 452 elm = tmp; \ 453 } \ 454 RB_SET_BLACKRED(parent, gparent, field); \ 455 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 456 } else { \ 457 tmp = RB_LEFT(gparent, field); \ 458 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 459 RB_COLOR(tmp, field) = RB_BLACK; \ 460 RB_SET_BLACKRED(parent, gparent, field);\ 461 elm = gparent; \ 462 continue; \ 463 } \ 464 if (RB_LEFT(parent, field) == elm) { \ 465 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 466 tmp = parent; \ 467 parent = elm; \ 468 elm = tmp; \ 469 } \ 470 RB_SET_BLACKRED(parent, gparent, field); \ 471 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 472 } \ 473 } \ 474 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 475 } 476 477 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 478 attr void \ 479 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 480 { \ 481 struct type *tmp; \ 482 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 483 elm != RB_ROOT(head)) { \ 484 if (RB_LEFT(parent, field) == elm) { \ 485 tmp = RB_RIGHT(parent, field); \ 486 if (RB_COLOR(tmp, field) == RB_RED) { \ 487 RB_SET_BLACKRED(tmp, parent, field); \ 488 RB_ROTATE_LEFT(head, parent, tmp, field);\ 489 tmp = RB_RIGHT(parent, field); \ 490 } \ 491 if ((RB_LEFT(tmp, field) == NULL || \ 492 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 493 (RB_RIGHT(tmp, field) == NULL || \ 494 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 495 RB_COLOR(tmp, field) = RB_RED; \ 496 elm = parent; \ 497 parent = RB_PARENT(elm, field); \ 498 } else { \ 499 if (RB_RIGHT(tmp, field) == NULL || \ 500 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 501 struct type *oleft; \ 502 if ((oleft = RB_LEFT(tmp, field)) \ 503 != NULL) \ 504 RB_COLOR(oleft, field) = RB_BLACK;\ 505 RB_COLOR(tmp, field) = RB_RED; \ 506 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 507 tmp = RB_RIGHT(parent, field); \ 508 } \ 509 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 510 RB_COLOR(parent, field) = RB_BLACK; \ 511 if (RB_RIGHT(tmp, field)) \ 512 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 513 RB_ROTATE_LEFT(head, parent, tmp, field);\ 514 elm = RB_ROOT(head); \ 515 break; \ 516 } \ 517 } else { \ 518 tmp = RB_LEFT(parent, field); \ 519 if (RB_COLOR(tmp, field) == RB_RED) { \ 520 RB_SET_BLACKRED(tmp, parent, field); \ 521 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 522 tmp = RB_LEFT(parent, field); \ 523 } \ 524 if ((RB_LEFT(tmp, field) == NULL || \ 525 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 526 (RB_RIGHT(tmp, field) == NULL || \ 527 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 528 RB_COLOR(tmp, field) = RB_RED; \ 529 elm = parent; \ 530 parent = RB_PARENT(elm, field); \ 531 } else { \ 532 if (RB_LEFT(tmp, field) == NULL || \ 533 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 534 struct type *oright; \ 535 if ((oright = RB_RIGHT(tmp, field)) \ 536 != NULL) \ 537 RB_COLOR(oright, field) = RB_BLACK;\ 538 RB_COLOR(tmp, field) = RB_RED; \ 539 RB_ROTATE_LEFT(head, tmp, oright, field);\ 540 tmp = RB_LEFT(parent, field); \ 541 } \ 542 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 543 RB_COLOR(parent, field) = RB_BLACK; \ 544 if (RB_LEFT(tmp, field)) \ 545 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 546 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 547 elm = RB_ROOT(head); \ 548 break; \ 549 } \ 550 } \ 551 } \ 552 if (elm) \ 553 RB_COLOR(elm, field) = RB_BLACK; \ 554 } 555 556 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 557 attr struct type * \ 558 name##_RB_REMOVE(struct name *head, struct type *elm) \ 559 { \ 560 struct type *child, *parent, *old = elm; \ 561 int color; \ 562 if (RB_LEFT(elm, field) == NULL) \ 563 child = RB_RIGHT(elm, field); \ 564 else if (RB_RIGHT(elm, field) == NULL) \ 565 child = RB_LEFT(elm, field); \ 566 else { \ 567 struct type *left; \ 568 elm = RB_RIGHT(elm, field); \ 569 while ((left = RB_LEFT(elm, field)) != NULL) \ 570 elm = left; \ 571 child = RB_RIGHT(elm, field); \ 572 parent = RB_PARENT(elm, field); \ 573 color = RB_COLOR(elm, field); \ 574 if (child) \ 575 RB_PARENT(child, field) = parent; \ 576 if (parent) { \ 577 if (RB_LEFT(parent, field) == elm) \ 578 RB_LEFT(parent, field) = child; \ 579 else \ 580 RB_RIGHT(parent, field) = child; \ 581 RB_AUGMENT(parent); \ 582 } else \ 583 RB_ROOT(head) = child; \ 584 if (RB_PARENT(elm, field) == old) \ 585 parent = elm; \ 586 (elm)->field = (old)->field; \ 587 if (RB_PARENT(old, field)) { \ 588 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 589 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 590 else \ 591 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 592 RB_AUGMENT(RB_PARENT(old, field)); \ 593 } else \ 594 RB_ROOT(head) = elm; \ 595 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 596 if (RB_RIGHT(old, field)) \ 597 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 598 if (parent) { \ 599 left = parent; \ 600 do { \ 601 RB_AUGMENT(left); \ 602 } while ((left = RB_PARENT(left, field)) != NULL); \ 603 } \ 604 goto color; \ 605 } \ 606 parent = RB_PARENT(elm, field); \ 607 color = RB_COLOR(elm, field); \ 608 if (child) \ 609 RB_PARENT(child, field) = parent; \ 610 if (parent) { \ 611 if (RB_LEFT(parent, field) == elm) \ 612 RB_LEFT(parent, field) = child; \ 613 else \ 614 RB_RIGHT(parent, field) = child; \ 615 RB_AUGMENT(parent); \ 616 } else \ 617 RB_ROOT(head) = child; \ 618 color: \ 619 if (color == RB_BLACK) \ 620 name##_RB_REMOVE_COLOR(head, parent, child); \ 621 return (old); \ 622 } \ 623 624 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 625 /* Inserts a node into the RB tree */ \ 626 attr struct type * \ 627 name##_RB_INSERT(struct name *head, struct type *elm) \ 628 { \ 629 struct type *tmp; \ 630 struct type *parent = NULL; \ 631 int comp = 0; \ 632 tmp = RB_ROOT(head); \ 633 while (tmp) { \ 634 parent = tmp; \ 635 comp = (cmp)(elm, parent); \ 636 if (comp < 0) \ 637 tmp = RB_LEFT(tmp, field); \ 638 else if (comp > 0) \ 639 tmp = RB_RIGHT(tmp, field); \ 640 else \ 641 return (tmp); \ 642 } \ 643 RB_SET(elm, parent, field); \ 644 if (parent != NULL) { \ 645 if (comp < 0) \ 646 RB_LEFT(parent, field) = elm; \ 647 else \ 648 RB_RIGHT(parent, field) = elm; \ 649 RB_AUGMENT(parent); \ 650 } else \ 651 RB_ROOT(head) = elm; \ 652 name##_RB_INSERT_COLOR(head, elm); \ 653 return (NULL); \ 654 } 655 656 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 657 /* Finds the node with the same key as elm */ \ 658 attr struct type * \ 659 name##_RB_FIND(struct name *head, struct type *elm) \ 660 { \ 661 struct type *tmp = RB_ROOT(head); \ 662 int comp; \ 663 while (tmp) { \ 664 comp = cmp(elm, tmp); \ 665 if (comp < 0) \ 666 tmp = RB_LEFT(tmp, field); \ 667 else if (comp > 0) \ 668 tmp = RB_RIGHT(tmp, field); \ 669 else \ 670 return (tmp); \ 671 } \ 672 return (NULL); \ 673 } 674 675 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 676 /* Finds the first node greater than or equal to the search key */ \ 677 attr struct type * \ 678 name##_RB_NFIND(struct name *head, struct type *elm) \ 679 { \ 680 struct type *tmp = RB_ROOT(head); \ 681 struct type *res = NULL; \ 682 int comp; \ 683 while (tmp) { \ 684 comp = cmp(elm, tmp); \ 685 if (comp < 0) { \ 686 res = tmp; \ 687 tmp = RB_LEFT(tmp, field); \ 688 } \ 689 else if (comp > 0) \ 690 tmp = RB_RIGHT(tmp, field); \ 691 else \ 692 return (tmp); \ 693 } \ 694 return (res); \ 695 } 696 697 #define RB_GENERATE_NEXT(name, type, field, attr) \ 698 /* ARGSUSED */ \ 699 attr struct type * \ 700 name##_RB_NEXT(struct type *elm) \ 701 { \ 702 if (RB_RIGHT(elm, field)) { \ 703 elm = RB_RIGHT(elm, field); \ 704 while (RB_LEFT(elm, field)) \ 705 elm = RB_LEFT(elm, field); \ 706 } else { \ 707 if (RB_PARENT(elm, field) && \ 708 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 709 elm = RB_PARENT(elm, field); \ 710 else { \ 711 while (RB_PARENT(elm, field) && \ 712 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 713 elm = RB_PARENT(elm, field); \ 714 elm = RB_PARENT(elm, field); \ 715 } \ 716 } \ 717 return (elm); \ 718 } 719 720 #define RB_GENERATE_PREV(name, type, field, attr) \ 721 /* ARGSUSED */ \ 722 attr struct type * \ 723 name##_RB_PREV(struct type *elm) \ 724 { \ 725 if (RB_LEFT(elm, field)) { \ 726 elm = RB_LEFT(elm, field); \ 727 while (RB_RIGHT(elm, field)) \ 728 elm = RB_RIGHT(elm, field); \ 729 } else { \ 730 if (RB_PARENT(elm, field) && \ 731 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 732 elm = RB_PARENT(elm, field); \ 733 else { \ 734 while (RB_PARENT(elm, field) && \ 735 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 736 elm = RB_PARENT(elm, field); \ 737 elm = RB_PARENT(elm, field); \ 738 } \ 739 } \ 740 return (elm); \ 741 } 742 743 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 744 attr struct type * \ 745 name##_RB_MINMAX(struct name *head, int val) \ 746 { \ 747 struct type *tmp = RB_ROOT(head); \ 748 struct type *parent = NULL; \ 749 while (tmp) { \ 750 parent = tmp; \ 751 if (val < 0) \ 752 tmp = RB_LEFT(tmp, field); \ 753 else \ 754 tmp = RB_RIGHT(tmp, field); \ 755 } \ 756 return (parent); \ 757 } 758 759 #define RB_NEGINF -1 760 #define RB_INF 1 761 762 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 763 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 764 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 765 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 766 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 767 #define RB_PREV(name, x, y) name##_RB_PREV(y) 768 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 769 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 770 771 #define RB_FOREACH(x, name, head) \ 772 for ((x) = RB_MIN(name, head); \ 773 (x) != NULL; \ 774 (x) = name##_RB_NEXT(x)) 775 776 #define RB_FOREACH_FROM(x, name, y) \ 777 for ((x) = (y); \ 778 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 779 (x) = (y)) 780 781 #define RB_FOREACH_SAFE(x, name, head, y) \ 782 for ((x) = RB_MIN(name, head); \ 783 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 784 (x) = (y)) 785 786 #define RB_FOREACH_REVERSE(x, name, head) \ 787 for ((x) = RB_MAX(name, head); \ 788 (x) != NULL; \ 789 (x) = name##_RB_PREV(x)) 790 791 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 792 for ((x) = (y); \ 793 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 794 (x) = (y)) 795 796 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 797 for ((x) = RB_MAX(name, head); \ 798 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 799 (x) = (y)) 800 801 #endif /* _SYS_TREE_H_ */ 802