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 /* $DragonFly: src/sys/sys/tree.h,v 1.11 2008/01/07 01:22:30 corecode Exp $ */ 4 /* 5 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #ifndef _SYS_TREE_H_ 30 #define _SYS_TREE_H_ 31 32 /* 33 * This file defines data structures for different types of trees: 34 * splay trees and red-black trees. 35 * 36 * A splay tree is a self-organizing data structure. Every operation 37 * on the tree causes a splay to happen. The splay moves the requested 38 * node to the root of the tree and partly rebalances it. 39 * 40 * This has the benefit that request locality causes faster lookups as 41 * the requested nodes move to the top of the tree. On the other hand, 42 * every lookup causes memory writes. 43 * 44 * The Balance Theorem bounds the total access time for m operations 45 * and n inserts on an initially empty tree as O((m + n)lg n). The 46 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 47 * 48 * A red-black tree is a binary search tree with the node color as an 49 * extra attribute. It fulfills a set of conditions: 50 * - every search path from the root to a leaf consists of the 51 * same number of black nodes, 52 * - each red node (except for the root) has a black parent, 53 * - each leaf node is black. 54 * 55 * Every operation on a red-black tree is bounded as O(lg n). 56 * The maximum height of a red-black tree is 2lg (n+1). 57 */ 58 59 #define SPLAY_HEAD(name, type) \ 60 struct name { \ 61 struct type *sph_root; /* root of the tree */ \ 62 } 63 64 #define SPLAY_INITIALIZER(root) \ 65 { NULL } 66 67 #define SPLAY_INIT(root) do { \ 68 (root)->sph_root = NULL; \ 69 } while (/*CONSTCOND*/ 0) 70 71 #define SPLAY_ENTRY(type) \ 72 struct { \ 73 struct type *spe_left; /* left element */ \ 74 struct type *spe_right; /* right element */ \ 75 } 76 77 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 78 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 79 #define SPLAY_ROOT(head) (head)->sph_root 80 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 81 82 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 83 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 84 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 85 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 86 (head)->sph_root = tmp; \ 87 } while (/*CONSTCOND*/ 0) 88 89 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 90 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 91 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 92 (head)->sph_root = tmp; \ 93 } while (/*CONSTCOND*/ 0) 94 95 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97 tmp = (head)->sph_root; \ 98 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 99 } while (/*CONSTCOND*/ 0) 100 101 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 102 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 103 tmp = (head)->sph_root; \ 104 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 105 } while (/*CONSTCOND*/ 0) 106 107 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 108 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 109 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 110 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 111 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 112 } while (/*CONSTCOND*/ 0) 113 114 /* Generates prototypes and inline functions */ 115 116 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 117 void name##_SPLAY(struct name *, struct type *); \ 118 void name##_SPLAY_MINMAX(struct name *, int); \ 119 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 120 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 121 \ 122 /* Finds the node with the same key as elm */ \ 123 static __inline struct type * \ 124 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 125 { \ 126 if (SPLAY_EMPTY(head)) \ 127 return(NULL); \ 128 name##_SPLAY(head, elm); \ 129 if ((cmp)(elm, (head)->sph_root) == 0) \ 130 return (head->sph_root); \ 131 return (NULL); \ 132 } \ 133 \ 134 static __inline struct type * \ 135 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 136 { \ 137 name##_SPLAY(head, elm); \ 138 if (SPLAY_RIGHT(elm, field) != NULL) { \ 139 elm = SPLAY_RIGHT(elm, field); \ 140 while (SPLAY_LEFT(elm, field) != NULL) { \ 141 elm = SPLAY_LEFT(elm, field); \ 142 } \ 143 } else \ 144 elm = NULL; \ 145 return (elm); \ 146 } \ 147 \ 148 static __inline struct type * \ 149 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 150 { \ 151 name##_SPLAY_MINMAX(head, val); \ 152 return (SPLAY_ROOT(head)); \ 153 } 154 155 /* Main splay operation. 156 * Moves node close to the key of elm to top 157 */ 158 #define SPLAY_GENERATE(name, type, field, cmp) \ 159 struct type * \ 160 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 161 { \ 162 if (SPLAY_EMPTY(head)) { \ 163 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 164 } else { \ 165 int __comp; \ 166 name##_SPLAY(head, elm); \ 167 __comp = (cmp)(elm, (head)->sph_root); \ 168 if(__comp < 0) { \ 169 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 170 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 171 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 172 } else if (__comp > 0) { \ 173 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 174 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 175 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 176 } else \ 177 return ((head)->sph_root); \ 178 } \ 179 (head)->sph_root = (elm); \ 180 return (NULL); \ 181 } \ 182 \ 183 struct type * \ 184 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 185 { \ 186 struct type *__tmp; \ 187 if (SPLAY_EMPTY(head)) \ 188 return (NULL); \ 189 name##_SPLAY(head, elm); \ 190 if ((cmp)(elm, (head)->sph_root) == 0) { \ 191 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 192 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 193 } else { \ 194 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 195 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 196 name##_SPLAY(head, elm); \ 197 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 198 } \ 199 return (elm); \ 200 } \ 201 return (NULL); \ 202 } \ 203 \ 204 void \ 205 name##_SPLAY(struct name *head, struct type *elm) \ 206 { \ 207 struct type __node, *__left, *__right, *__tmp; \ 208 int __comp; \ 209 \ 210 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 211 __left = __right = &__node; \ 212 \ 213 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 214 if (__comp < 0) { \ 215 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 216 if (__tmp == NULL) \ 217 break; \ 218 if ((cmp)(elm, __tmp) < 0){ \ 219 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 220 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 221 break; \ 222 } \ 223 SPLAY_LINKLEFT(head, __right, field); \ 224 } else if (__comp > 0) { \ 225 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 226 if (__tmp == NULL) \ 227 break; \ 228 if ((cmp)(elm, __tmp) > 0){ \ 229 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 230 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 231 break; \ 232 } \ 233 SPLAY_LINKRIGHT(head, __left, field); \ 234 } \ 235 } \ 236 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 237 } \ 238 \ 239 /* Splay with either the minimum or the maximum element \ 240 * Used to find minimum or maximum element in tree. \ 241 */ \ 242 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 243 { \ 244 struct type __node, *__left, *__right, *__tmp; \ 245 \ 246 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 247 __left = __right = &__node; \ 248 \ 249 while (1) { \ 250 if (__comp < 0) { \ 251 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 252 if (__tmp == NULL) \ 253 break; \ 254 if (__comp < 0){ \ 255 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 256 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 257 break; \ 258 } \ 259 SPLAY_LINKLEFT(head, __right, field); \ 260 } else if (__comp > 0) { \ 261 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 262 if (__tmp == NULL) \ 263 break; \ 264 if (__comp > 0) { \ 265 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 266 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 267 break; \ 268 } \ 269 SPLAY_LINKRIGHT(head, __left, field); \ 270 } \ 271 } \ 272 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 273 } 274 275 #define SPLAY_NEGINF -1 276 #define SPLAY_INF 1 277 278 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 279 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 280 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 281 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 282 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 283 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 284 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 285 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 286 287 #define SPLAY_FOREACH(x, name, head) \ 288 for ((x) = SPLAY_MIN(name, head); \ 289 (x) != NULL; \ 290 (x) = SPLAY_NEXT(name, head, x)) 291 292 /* Macros that define a red-black tree */ 293 294 #define RB_SCAN_INFO(name, type) \ 295 struct name##_scan_info { \ 296 struct name##_scan_info *link; \ 297 struct type *node; \ 298 } 299 300 #define RB_HEAD(name, type) \ 301 struct name { \ 302 struct type *rbh_root; /* root of the tree */ \ 303 struct name##_scan_info *rbh_inprog; /* scans in progress */ \ 304 } 305 306 #define RB_INITIALIZER(root) \ 307 { NULL, NULL } 308 309 #define RB_INIT(root) do { \ 310 (root)->rbh_root = NULL; \ 311 (root)->rbh_inprog = NULL; \ 312 } while (/*CONSTCOND*/ 0) 313 314 #define RB_BLACK 0 315 #define RB_RED 1 316 #define RB_ENTRY(type) \ 317 struct { \ 318 struct type *rbe_left; /* left element */ \ 319 struct type *rbe_right; /* right element */ \ 320 struct type *rbe_parent; /* parent element */ \ 321 int rbe_color; /* node color */ \ 322 } 323 324 #define RB_LEFT(elm, field) (elm)->field.rbe_left 325 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 326 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 327 #define RB_COLOR(elm, field) (elm)->field.rbe_color 328 #define RB_ROOT(head) (head)->rbh_root 329 #define RB_INPROG(head) (head)->rbh_inprog 330 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 331 332 #define RB_SET(elm, parent, field) do { \ 333 RB_PARENT(elm, field) = parent; \ 334 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 335 RB_COLOR(elm, field) = RB_RED; \ 336 } while (/*CONSTCOND*/ 0) 337 338 #define RB_SET_BLACKRED(black, red, field) do { \ 339 RB_COLOR(black, field) = RB_BLACK; \ 340 RB_COLOR(red, field) = RB_RED; \ 341 } while (/*CONSTCOND*/ 0) 342 343 #ifndef RB_AUGMENT 344 #define RB_AUGMENT(x) 345 #endif 346 347 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 348 (tmp) = RB_RIGHT(elm, field); \ 349 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 350 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 351 } \ 352 RB_AUGMENT(elm); \ 353 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 354 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 355 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 356 else \ 357 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 358 } else \ 359 (head)->rbh_root = (tmp); \ 360 RB_LEFT(tmp, field) = (elm); \ 361 RB_PARENT(elm, field) = (tmp); \ 362 RB_AUGMENT(tmp); \ 363 if ((RB_PARENT(tmp, field))) \ 364 RB_AUGMENT(RB_PARENT(tmp, field)); \ 365 } while (/*CONSTCOND*/ 0) 366 367 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 368 (tmp) = RB_LEFT(elm, field); \ 369 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 370 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 371 } \ 372 RB_AUGMENT(elm); \ 373 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 374 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 375 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 376 else \ 377 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 378 } else \ 379 (head)->rbh_root = (tmp); \ 380 RB_RIGHT(tmp, field) = (elm); \ 381 RB_PARENT(elm, field) = (tmp); \ 382 RB_AUGMENT(tmp); \ 383 if ((RB_PARENT(tmp, field))) \ 384 RB_AUGMENT(RB_PARENT(tmp, field)); \ 385 } while (/*CONSTCOND*/ 0) 386 387 /* Generates prototypes and inline functions */ 388 #define RB_PROTOTYPE(name, type, field, cmp) \ 389 _RB_PROTOTYPE(name, type, field, cmp,) 390 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 391 _RB_PROTOTYPE(name, type, field, cmp, __unused static) 392 393 #define _RB_PROTOTYPE(name, type, field, cmp, STORQUAL) \ 394 STORQUAL struct type *name##_RB_REMOVE(struct name *, struct type *); \ 395 STORQUAL struct type *name##_RB_INSERT(struct name *, struct type *); \ 396 STORQUAL struct type *name##_RB_FIND(struct name *, struct type *); \ 397 STORQUAL int name##_RB_SCAN(struct name *, int (*)(struct type *, void *),\ 398 int (*)(struct type *, void *), void *); \ 399 STORQUAL struct type *name##_RB_NEXT(struct type *); \ 400 STORQUAL struct type *name##_RB_PREV(struct type *); \ 401 STORQUAL struct type *name##_RB_MINMAX(struct name *, int); \ 402 RB_SCAN_INFO(name, type) \ 403 404 /* 405 * A version which supplies a fast lookup routine for an exact match 406 * on a numeric field. 407 */ 408 #define RB_PROTOTYPE2(name, type, field, cmp, datatype) \ 409 RB_PROTOTYPE(name, type, field, cmp); \ 410 struct type *name##_RB_LOOKUP(struct name *, datatype) \ 411 412 /* 413 * A version which supplies a fast lookup routine for a numeric 414 * field which resides within a ranged object, either using (begin,end), 415 * or using (begin,size). 416 */ 417 #define RB_PROTOTYPE3(name, type, field, cmp, datatype) \ 418 RB_PROTOTYPE2(name, type, field, cmp, datatype); \ 419 struct type *name##_RB_RLOOKUP(struct name *, datatype) \ 420 421 #define RB_PROTOTYPE4(name, type, field, cmp, datatype) \ 422 RB_PROTOTYPE2(name, type, field, cmp, datatype); \ 423 struct type *name##_RB_RLOOKUP(struct name *, datatype) \ 424 425 #define RB_PROTOTYPEX(name, ext, type, field, cmp, datatype) \ 426 RB_PROTOTYPE(name, type, field, cmp); \ 427 struct type *name##_RB_LOOKUP_##ext (struct name *, datatype) \ 428 429 /* Main rb operation. 430 * Moves node close to the key of elm to top 431 */ 432 #define RB_GENERATE(name, type, field, cmp) \ 433 _RB_GENERATE(name, type, field, cmp,) 434 435 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 436 _RB_GENERATE(name, type, field, cmp, __unused static) 437 438 #define _RB_GENERATE(name, type, field, cmp, STORQUAL) \ 439 static void \ 440 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 441 { \ 442 struct type *parent, *gparent, *tmp; \ 443 while ((parent = RB_PARENT(elm, field)) != NULL && \ 444 RB_COLOR(parent, field) == RB_RED) { \ 445 gparent = RB_PARENT(parent, field); \ 446 if (parent == RB_LEFT(gparent, field)) { \ 447 tmp = RB_RIGHT(gparent, field); \ 448 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 449 RB_COLOR(tmp, field) = RB_BLACK; \ 450 RB_SET_BLACKRED(parent, gparent, field);\ 451 elm = gparent; \ 452 continue; \ 453 } \ 454 if (RB_RIGHT(parent, field) == elm) { \ 455 RB_ROTATE_LEFT(head, parent, tmp, field);\ 456 tmp = parent; \ 457 parent = elm; \ 458 elm = tmp; \ 459 } \ 460 RB_SET_BLACKRED(parent, gparent, field); \ 461 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 462 } else { \ 463 tmp = RB_LEFT(gparent, field); \ 464 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 465 RB_COLOR(tmp, field) = RB_BLACK; \ 466 RB_SET_BLACKRED(parent, gparent, field);\ 467 elm = gparent; \ 468 continue; \ 469 } \ 470 if (RB_LEFT(parent, field) == elm) { \ 471 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 472 tmp = parent; \ 473 parent = elm; \ 474 elm = tmp; \ 475 } \ 476 RB_SET_BLACKRED(parent, gparent, field); \ 477 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 478 } \ 479 } \ 480 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 481 } \ 482 \ 483 static void \ 484 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 485 struct type *elm) \ 486 { \ 487 struct type *tmp; \ 488 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 489 elm != RB_ROOT(head)) { \ 490 if (RB_LEFT(parent, field) == elm) { \ 491 tmp = RB_RIGHT(parent, field); \ 492 if (RB_COLOR(tmp, field) == RB_RED) { \ 493 RB_SET_BLACKRED(tmp, parent, field); \ 494 RB_ROTATE_LEFT(head, parent, tmp, field);\ 495 tmp = RB_RIGHT(parent, field); \ 496 } \ 497 if ((RB_LEFT(tmp, field) == NULL || \ 498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 499 (RB_RIGHT(tmp, field) == NULL || \ 500 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 501 RB_COLOR(tmp, field) = RB_RED; \ 502 elm = parent; \ 503 parent = RB_PARENT(elm, field); \ 504 } else { \ 505 if (RB_RIGHT(tmp, field) == NULL || \ 506 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 507 struct type *oleft; \ 508 if ((oleft = RB_LEFT(tmp, field)) \ 509 != NULL) \ 510 RB_COLOR(oleft, field) = RB_BLACK;\ 511 RB_COLOR(tmp, field) = RB_RED; \ 512 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 513 tmp = RB_RIGHT(parent, field); \ 514 } \ 515 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 516 RB_COLOR(parent, field) = RB_BLACK; \ 517 if (RB_RIGHT(tmp, field)) \ 518 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 519 RB_ROTATE_LEFT(head, parent, tmp, field);\ 520 elm = RB_ROOT(head); \ 521 break; \ 522 } \ 523 } else { \ 524 tmp = RB_LEFT(parent, field); \ 525 if (RB_COLOR(tmp, field) == RB_RED) { \ 526 RB_SET_BLACKRED(tmp, parent, field); \ 527 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 528 tmp = RB_LEFT(parent, field); \ 529 } \ 530 if ((RB_LEFT(tmp, field) == NULL || \ 531 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 532 (RB_RIGHT(tmp, field) == NULL || \ 533 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 534 RB_COLOR(tmp, field) = RB_RED; \ 535 elm = parent; \ 536 parent = RB_PARENT(elm, field); \ 537 } else { \ 538 if (RB_LEFT(tmp, field) == NULL || \ 539 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 540 struct type *oright; \ 541 if ((oright = RB_RIGHT(tmp, field)) \ 542 != NULL) \ 543 RB_COLOR(oright, field) = RB_BLACK;\ 544 RB_COLOR(tmp, field) = RB_RED; \ 545 RB_ROTATE_LEFT(head, tmp, oright, field);\ 546 tmp = RB_LEFT(parent, field); \ 547 } \ 548 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 549 RB_COLOR(parent, field) = RB_BLACK; \ 550 if (RB_LEFT(tmp, field)) \ 551 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 552 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 553 elm = RB_ROOT(head); \ 554 break; \ 555 } \ 556 } \ 557 } \ 558 if (elm) \ 559 RB_COLOR(elm, field) = RB_BLACK; \ 560 } \ 561 \ 562 STORQUAL struct type * \ 563 name##_RB_REMOVE(struct name *head, struct type *elm) \ 564 { \ 565 struct type *child, *parent, *old; \ 566 struct name##_scan_info *inprog; \ 567 int color; \ 568 \ 569 for (inprog = RB_INPROG(head); inprog; inprog = inprog->link) { \ 570 if (inprog->node == elm) \ 571 inprog->node = RB_NEXT(name, head, elm); \ 572 } \ 573 \ 574 old = elm; \ 575 if (RB_LEFT(elm, field) == NULL) \ 576 child = RB_RIGHT(elm, field); \ 577 else if (RB_RIGHT(elm, field) == NULL) \ 578 child = RB_LEFT(elm, field); \ 579 else { \ 580 struct type *left; \ 581 elm = RB_RIGHT(elm, field); \ 582 while ((left = RB_LEFT(elm, field)) != NULL) \ 583 elm = left; \ 584 child = RB_RIGHT(elm, field); \ 585 parent = RB_PARENT(elm, field); \ 586 color = RB_COLOR(elm, field); \ 587 if (child) \ 588 RB_PARENT(child, field) = parent; \ 589 if (parent) { \ 590 if (RB_LEFT(parent, field) == elm) \ 591 RB_LEFT(parent, field) = child; \ 592 else \ 593 RB_RIGHT(parent, field) = child; \ 594 RB_AUGMENT(parent); \ 595 } else \ 596 RB_ROOT(head) = child; \ 597 if (RB_PARENT(elm, field) == old) \ 598 parent = elm; \ 599 (elm)->field = (old)->field; \ 600 if (RB_PARENT(old, field)) { \ 601 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 602 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 603 else \ 604 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 605 RB_AUGMENT(RB_PARENT(old, field)); \ 606 } else \ 607 RB_ROOT(head) = elm; \ 608 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 609 if (RB_RIGHT(old, field)) \ 610 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 611 if (parent) { \ 612 left = parent; \ 613 do { \ 614 RB_AUGMENT(left); \ 615 } while ((left = RB_PARENT(left, field)) != NULL); \ 616 } \ 617 goto color; \ 618 } \ 619 parent = RB_PARENT(elm, field); \ 620 color = RB_COLOR(elm, field); \ 621 if (child) \ 622 RB_PARENT(child, field) = parent; \ 623 if (parent) { \ 624 if (RB_LEFT(parent, field) == elm) \ 625 RB_LEFT(parent, field) = child; \ 626 else \ 627 RB_RIGHT(parent, field) = child; \ 628 RB_AUGMENT(parent); \ 629 } else \ 630 RB_ROOT(head) = child; \ 631 color: \ 632 if (color == RB_BLACK) \ 633 name##_RB_REMOVE_COLOR(head, parent, child); \ 634 return (old); \ 635 } \ 636 \ 637 /* Inserts a node into the RB tree */ \ 638 STORQUAL struct type * \ 639 name##_RB_INSERT(struct name *head, struct type *elm) \ 640 { \ 641 struct type *tmp; \ 642 struct type *parent = NULL; \ 643 int comp = 0; \ 644 tmp = RB_ROOT(head); \ 645 while (tmp) { \ 646 parent = tmp; \ 647 comp = (cmp)(elm, parent); \ 648 if (comp < 0) \ 649 tmp = RB_LEFT(tmp, field); \ 650 else if (comp > 0) \ 651 tmp = RB_RIGHT(tmp, field); \ 652 else \ 653 return(tmp); \ 654 } \ 655 RB_SET(elm, parent, field); \ 656 if (parent != NULL) { \ 657 if (comp < 0) \ 658 RB_LEFT(parent, field) = elm; \ 659 else \ 660 RB_RIGHT(parent, field) = elm; \ 661 RB_AUGMENT(parent); \ 662 } else \ 663 RB_ROOT(head) = elm; \ 664 name##_RB_INSERT_COLOR(head, elm); \ 665 return (NULL); \ 666 } \ 667 \ 668 /* Finds the node with the same key as elm */ \ 669 STORQUAL struct type * \ 670 name##_RB_FIND(struct name *head, struct type *elm) \ 671 { \ 672 struct type *tmp = RB_ROOT(head); \ 673 int comp; \ 674 while (tmp) { \ 675 comp = cmp(elm, tmp); \ 676 if (comp < 0) \ 677 tmp = RB_LEFT(tmp, field); \ 678 else if (comp > 0) \ 679 tmp = RB_RIGHT(tmp, field); \ 680 else \ 681 return (tmp); \ 682 } \ 683 return (NULL); \ 684 } \ 685 \ 686 /* \ 687 * Issue a callback for all matching items. The scan function must \ 688 * return < 0 for items below the desired range, 0 for items within \ 689 * the range, and > 0 for items beyond the range. Any item may be \ 690 * deleted while the scan is in progress. \ 691 */ \ 692 static int \ 693 name##_SCANCMP_ALL(struct type *type, void *data) \ 694 { \ 695 return(0); \ 696 } \ 697 \ 698 static __inline void \ 699 name##_scan_info_link(struct name##_scan_info *scan, struct name *head) \ 700 { \ 701 scan->link = RB_INPROG(head); \ 702 RB_INPROG(head) = scan; \ 703 } \ 704 \ 705 static __inline void \ 706 name##_scan_info_done(struct name##_scan_info *scan, struct name *head) \ 707 { \ 708 struct name##_scan_info **infopp; \ 709 \ 710 infopp = &RB_INPROG(head); \ 711 while (*infopp != scan) \ 712 infopp = &(*infopp)->link; \ 713 *infopp = scan->link; \ 714 } \ 715 \ 716 STORQUAL int \ 717 name##_RB_SCAN(struct name *head, \ 718 int (*scancmp)(struct type *, void *), \ 719 int (*callback)(struct type *, void *), \ 720 void *data) \ 721 { \ 722 struct name##_scan_info info; \ 723 struct type *best; \ 724 struct type *tmp; \ 725 int count; \ 726 int comp; \ 727 \ 728 if (scancmp == NULL) \ 729 scancmp = name##_SCANCMP_ALL; \ 730 \ 731 /* \ 732 * Locate the first element. \ 733 */ \ 734 tmp = RB_ROOT(head); \ 735 best = NULL; \ 736 while (tmp) { \ 737 comp = scancmp(tmp, data); \ 738 if (comp < 0) { \ 739 tmp = RB_RIGHT(tmp, field); \ 740 } else if (comp > 0) { \ 741 tmp = RB_LEFT(tmp, field); \ 742 } else { \ 743 best = tmp; \ 744 if (RB_LEFT(tmp, field) == NULL) \ 745 break; \ 746 tmp = RB_LEFT(tmp, field); \ 747 } \ 748 } \ 749 count = 0; \ 750 if (best) { \ 751 info.node = RB_NEXT(name, head, best); \ 752 name##_scan_info_link(&info, head); \ 753 while ((comp = callback(best, data)) >= 0) { \ 754 count += comp; \ 755 best = info.node; \ 756 if (best == NULL || scancmp(best, data) != 0) \ 757 break; \ 758 info.node = RB_NEXT(name, head, best); \ 759 } \ 760 name##_scan_info_done(&info, head); \ 761 if (comp < 0) /* error or termination */ \ 762 count = comp; \ 763 } \ 764 return(count); \ 765 } \ 766 \ 767 /* ARGSUSED */ \ 768 STORQUAL struct type * \ 769 name##_RB_NEXT(struct type *elm) \ 770 { \ 771 if (RB_RIGHT(elm, field)) { \ 772 elm = RB_RIGHT(elm, field); \ 773 while (RB_LEFT(elm, field)) \ 774 elm = RB_LEFT(elm, field); \ 775 } else { \ 776 if (RB_PARENT(elm, field) && \ 777 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 778 elm = RB_PARENT(elm, field); \ 779 else { \ 780 while (RB_PARENT(elm, field) && \ 781 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 782 elm = RB_PARENT(elm, field); \ 783 elm = RB_PARENT(elm, field); \ 784 } \ 785 } \ 786 return (elm); \ 787 } \ 788 \ 789 /* ARGSUSED */ \ 790 STORQUAL struct type * \ 791 name##_RB_PREV(struct type *elm) \ 792 { \ 793 if (RB_LEFT(elm, field)) { \ 794 elm = RB_LEFT(elm, field); \ 795 while (RB_RIGHT(elm, field)) \ 796 elm = RB_RIGHT(elm, field); \ 797 } else { \ 798 if (RB_PARENT(elm, field) && \ 799 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 800 elm = RB_PARENT(elm, field); \ 801 else { \ 802 while (RB_PARENT(elm, field) && \ 803 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 804 elm = RB_PARENT(elm, field); \ 805 elm = RB_PARENT(elm, field); \ 806 } \ 807 } \ 808 return (elm); \ 809 } \ 810 \ 811 STORQUAL struct type * \ 812 name##_RB_MINMAX(struct name *head, int val) \ 813 { \ 814 struct type *tmp = RB_ROOT(head); \ 815 struct type *parent = NULL; \ 816 while (tmp) { \ 817 parent = tmp; \ 818 if (val < 0) \ 819 tmp = RB_LEFT(tmp, field); \ 820 else \ 821 tmp = RB_RIGHT(tmp, field); \ 822 } \ 823 return (parent); \ 824 } 825 826 /* 827 * This extended version implements a fast LOOKUP function given 828 * a numeric data type. 829 * 830 * The element whos index/offset field is exactly the specified value 831 * will be returned, or NULL. 832 */ 833 #define RB_GENERATE2(name, type, field, cmp, datatype, indexfield) \ 834 RB_GENERATE(name, type, field, cmp) \ 835 \ 836 struct type * \ 837 name##_RB_LOOKUP(struct name *head, datatype value) \ 838 { \ 839 struct type *tmp; \ 840 \ 841 tmp = RB_ROOT(head); \ 842 while (tmp) { \ 843 if (value > tmp->indexfield) \ 844 tmp = RB_RIGHT(tmp, field); \ 845 else if (value < tmp->indexfield) \ 846 tmp = RB_LEFT(tmp, field); \ 847 else \ 848 return(tmp); \ 849 } \ 850 return(NULL); \ 851 } \ 852 853 /* 854 * This extended version implements a fast ranged-based LOOKUP function 855 * given a numeric data type, for data types with a beginning and end 856 * (end is inclusive). 857 * 858 * The element whos range contains the specified value is returned, or NULL 859 */ 860 #define RB_GENERATE3(name, type, field, cmp, datatype, begfield, endfield) \ 861 RB_GENERATE2(name, type, field, cmp, datatype, begfield) \ 862 \ 863 struct type * \ 864 name##_RB_RLOOKUP(struct name *head, datatype value) \ 865 { \ 866 struct type *tmp; \ 867 \ 868 tmp = RB_ROOT(head); \ 869 while (tmp) { \ 870 if (value >= tmp->begfield && value <= tmp->endfield) \ 871 return(tmp); \ 872 if (value > tmp->begfield) \ 873 tmp = RB_RIGHT(tmp, field); \ 874 else \ 875 tmp = RB_LEFT(tmp, field); \ 876 } \ 877 return(NULL); \ 878 } \ 879 880 /* 881 * This extended version implements a fast ranged-based LOOKUP function 882 * given a numeric data type, for data types with a beginning and size. 883 * 884 * WARNING: The full range of the data type is not supported due to a 885 * boundary condition at the end, where (beginning + size) might overflow. 886 * 887 * The element whos range contains the specified value is returned, or NULL 888 */ 889 #define RB_GENERATE4(name, type, field, cmp, datatype, begfield, sizefield) \ 890 RB_GENERATE2(name, type, field, cmp, datatype, begfield) \ 891 \ 892 struct type * \ 893 name##_RB_RLOOKUP(struct name *head, datatype value) \ 894 { \ 895 struct type *tmp; \ 896 \ 897 tmp = RB_ROOT(head); \ 898 while (tmp) { \ 899 if (value >= tmp->begfield && \ 900 value < tmp->begfield + tmp->sizefield) { \ 901 return(tmp); \ 902 } \ 903 if (value > tmp->begfield) \ 904 tmp = RB_RIGHT(tmp, field); \ 905 else \ 906 tmp = RB_LEFT(tmp, field); \ 907 } \ 908 return(NULL); \ 909 } \ 910 911 /* 912 * This generates a custom lookup function for a red-black tree. 913 * Note that the macro may be used with a storage qualifier. 914 */ 915 916 #define RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype) \ 917 _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype,) 918 #define RB_GENERATE_XLOOKUP_STATIC(name, ext, type, field, xcmp, datatype) \ 919 _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype, __unused static) 920 921 #define _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype, STORQUAL)\ 922 \ 923 STORQUAL struct type * \ 924 name##_RB_LOOKUP_##ext (struct name *head, datatype value) \ 925 { \ 926 struct type *tmp; \ 927 int r; \ 928 \ 929 tmp = RB_ROOT(head); \ 930 while (tmp) { \ 931 r = xcmp(value, tmp); \ 932 if (r == 0) \ 933 return(tmp); \ 934 if (r > 0) \ 935 tmp = RB_RIGHT(tmp, field); \ 936 else \ 937 tmp = RB_LEFT(tmp, field); \ 938 } \ 939 return(NULL); \ 940 } \ 941 942 943 #define RB_NEGINF -1 944 #define RB_INF 1 945 946 #define RB_INSERT(name, root, elm) name##_RB_INSERT(root, elm) 947 #define RB_REMOVE(name, root, elm) name##_RB_REMOVE(root, elm) 948 #define RB_FIND(name, root, elm) name##_RB_FIND(root, elm) 949 #define RB_LOOKUP(name, root, value) name##_RB_LOOKUP(root, value) 950 #define RB_RLOOKUP(name, root, value) name##_RB_RLOOKUP(root, value) 951 #define RB_SCAN(name, root, cmp, callback, data) \ 952 name##_RB_SCAN(root, cmp, callback, data) 953 #define RB_FIRST(name, root) name##_RB_MINMAX(root, RB_NEGINF) 954 #define RB_NEXT(name, root, elm) name##_RB_NEXT(elm) 955 #define RB_PREV(name, root, elm) name##_RB_PREV(elm) 956 #define RB_MIN(name, root) name##_RB_MINMAX(root, RB_NEGINF) 957 #define RB_MAX(name, root) name##_RB_MINMAX(root, RB_INF) 958 959 #define RB_FOREACH(x, name, head) \ 960 for ((x) = RB_MIN(name, head); \ 961 (x) != NULL; \ 962 (x) = name##_RB_NEXT(x)) 963 964 #endif /* _SYS_TREE_H_ */ 965