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