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