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 #ifndef __PERMIT_DEPRECATED_SYS_TREE_H 36 #warning "sys/tree.h is deprecated and will be removed in the future." 37 #endif 38 39 #include <sys/cdefs.h> 40 41 /* 42 * This file defines data structures for different types of trees: 43 * splay trees and red-black trees. 44 * 45 * A splay tree is a self-organizing data structure. Every operation 46 * on the tree causes a splay to happen. The splay moves the requested 47 * node to the root of the tree and partly rebalances it. 48 * 49 * This has the benefit that request locality causes faster lookups as 50 * the requested nodes move to the top of the tree. On the other hand, 51 * every lookup causes memory writes. 52 * 53 * The Balance Theorem bounds the total access time for m operations 54 * and n inserts on an initially empty tree as O((m + n)lg n). The 55 * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 56 * 57 * A red-black tree is a binary search tree with the node color as an 58 * extra attribute. It fulfills a set of conditions: 59 * - every search path from the root to a leaf consists of the 60 * same number of black nodes, 61 * - each red node (except for the root) has a black parent, 62 * - each leaf node is black. 63 * 64 * Every operation on a red-black tree is bounded as O(lg n). 65 * The maximum height of a red-black tree is 2lg (n+1). 66 */ 67 68 #define SPLAY_HEAD(name, type) \ 69 struct name { \ 70 struct type *sph_root; /* root of the tree */ \ 71 } 72 73 #define SPLAY_INITIALIZER(root) \ 74 { NULL } 75 76 #define SPLAY_INIT(root) do { \ 77 (root)->sph_root = NULL; \ 78 } while (/*CONSTCOND*/ 0) 79 80 #define SPLAY_ENTRY(type) \ 81 struct { \ 82 struct type *spe_left; /* left element */ \ 83 struct type *spe_right; /* right element */ \ 84 } 85 86 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 87 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 88 #define SPLAY_ROOT(head) (head)->sph_root 89 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 90 91 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 92 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 93 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 94 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 95 (head)->sph_root = tmp; \ 96 } while (/*CONSTCOND*/ 0) 97 98 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 99 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 100 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 101 (head)->sph_root = tmp; \ 102 } while (/*CONSTCOND*/ 0) 103 104 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 106 tmp = (head)->sph_root; \ 107 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 108 } while (/*CONSTCOND*/ 0) 109 110 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 111 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 112 tmp = (head)->sph_root; \ 113 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 114 } while (/*CONSTCOND*/ 0) 115 116 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 117 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 118 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 119 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 120 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 121 } while (/*CONSTCOND*/ 0) 122 123 /* Generates prototypes and inline functions */ 124 125 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 126 void name##_SPLAY(struct name *, struct type *); \ 127 void name##_SPLAY_MINMAX(struct name *, int); \ 128 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 129 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 130 \ 131 /* Finds the node with the same key as elm */ \ 132 static __unused __inline struct type * \ 133 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 134 { \ 135 if (SPLAY_EMPTY(head)) \ 136 return(NULL); \ 137 name##_SPLAY(head, elm); \ 138 if ((cmp)(elm, (head)->sph_root) == 0) \ 139 return (head->sph_root); \ 140 return (NULL); \ 141 } \ 142 \ 143 static __unused __inline struct type * \ 144 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 145 { \ 146 name##_SPLAY(head, elm); \ 147 if (SPLAY_RIGHT(elm, field) != NULL) { \ 148 elm = SPLAY_RIGHT(elm, field); \ 149 while (SPLAY_LEFT(elm, field) != NULL) { \ 150 elm = SPLAY_LEFT(elm, field); \ 151 } \ 152 } else \ 153 elm = NULL; \ 154 return (elm); \ 155 } \ 156 \ 157 static __unused __inline struct type * \ 158 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 159 { \ 160 name##_SPLAY_MINMAX(head, val); \ 161 return (SPLAY_ROOT(head)); \ 162 } 163 164 /* Main splay operation. 165 * Moves node close to the key of elm to top 166 */ 167 #define SPLAY_GENERATE(name, type, field, cmp) \ 168 struct type * \ 169 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 170 { \ 171 if (SPLAY_EMPTY(head)) { \ 172 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 173 } else { \ 174 int __comp; \ 175 name##_SPLAY(head, elm); \ 176 __comp = (cmp)(elm, (head)->sph_root); \ 177 if(__comp < 0) { \ 178 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 179 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 180 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 181 } else if (__comp > 0) { \ 182 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 183 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 184 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 185 } else \ 186 return ((head)->sph_root); \ 187 } \ 188 (head)->sph_root = (elm); \ 189 return (NULL); \ 190 } \ 191 \ 192 struct type * \ 193 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 194 { \ 195 struct type *__tmp; \ 196 if (SPLAY_EMPTY(head)) \ 197 return (NULL); \ 198 name##_SPLAY(head, elm); \ 199 if ((cmp)(elm, (head)->sph_root) == 0) { \ 200 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 201 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 202 } else { \ 203 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 204 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 205 name##_SPLAY(head, elm); \ 206 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 207 } \ 208 return (elm); \ 209 } \ 210 return (NULL); \ 211 } \ 212 \ 213 void \ 214 name##_SPLAY(struct name *head, struct type *elm) \ 215 { \ 216 struct type __node, *__left, *__right, *__tmp; \ 217 int __comp; \ 218 \ 219 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 220 __left = __right = &__node; \ 221 \ 222 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 223 if (__comp < 0) { \ 224 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 225 if (__tmp == NULL) \ 226 break; \ 227 if ((cmp)(elm, __tmp) < 0){ \ 228 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 229 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 230 break; \ 231 } \ 232 SPLAY_LINKLEFT(head, __right, field); \ 233 } else if (__comp > 0) { \ 234 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 235 if (__tmp == NULL) \ 236 break; \ 237 if ((cmp)(elm, __tmp) > 0){ \ 238 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 239 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 240 break; \ 241 } \ 242 SPLAY_LINKRIGHT(head, __left, field); \ 243 } \ 244 } \ 245 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 246 } \ 247 \ 248 /* Splay with either the minimum or the maximum element \ 249 * Used to find minimum or maximum element in tree. \ 250 */ \ 251 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 252 { \ 253 struct type __node, *__left, *__right, *__tmp; \ 254 \ 255 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 256 __left = __right = &__node; \ 257 \ 258 while (1) { \ 259 if (__comp < 0) { \ 260 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 261 if (__tmp == NULL) \ 262 break; \ 263 if (__comp < 0){ \ 264 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 265 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 266 break; \ 267 } \ 268 SPLAY_LINKLEFT(head, __right, field); \ 269 } else if (__comp > 0) { \ 270 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 271 if (__tmp == NULL) \ 272 break; \ 273 if (__comp > 0) { \ 274 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 275 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 276 break; \ 277 } \ 278 SPLAY_LINKRIGHT(head, __left, field); \ 279 } \ 280 } \ 281 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 282 } 283 284 #define SPLAY_NEGINF -1 285 #define SPLAY_INF 1 286 287 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 288 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 289 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 290 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 291 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 292 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 293 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 294 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 295 296 #define SPLAY_FOREACH(x, name, head) \ 297 for ((x) = SPLAY_MIN(name, head); \ 298 (x) != NULL; \ 299 (x) = SPLAY_NEXT(name, head, x)) 300 301 /* Macros that define a red-black tree */ 302 #define RB_HEAD(name, type) \ 303 struct name { \ 304 struct type *rbh_root; /* root of the tree */ \ 305 } 306 307 #define RB_INITIALIZER(root) \ 308 { NULL } 309 310 #define RB_INIT(root) do { \ 311 (root)->rbh_root = 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_ISRED(elm, field) ((elm) != NULL && RB_COLOR(elm, field) == RB_RED) 329 #define RB_ROOT(head) (head)->rbh_root 330 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 331 332 #define RB_SET_PARENT(dst, src, field) do { \ 333 RB_PARENT(dst, field) = src; \ 334 } while (/*CONSTCOND*/ 0) 335 336 #define RB_SET(elm, parent, field) do { \ 337 RB_SET_PARENT(elm, parent, field); \ 338 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 339 RB_COLOR(elm, field) = RB_RED; \ 340 } while (/*CONSTCOND*/ 0) 341 342 #define RB_SET_BLACKRED(black, red, field) do { \ 343 RB_COLOR(black, field) = RB_BLACK; \ 344 RB_COLOR(red, field) = RB_RED; \ 345 } while (/*CONSTCOND*/ 0) 346 347 /* 348 * Something to be invoked in a loop at the root of every modified subtree, 349 * from the bottom up to the root, to update augmented node data. 350 */ 351 #ifndef RB_AUGMENT 352 #define RB_AUGMENT(x) break 353 #endif 354 355 #define RB_SWAP_CHILD(head, out, in, field) do { \ 356 if (RB_PARENT(out, field) == NULL) \ 357 RB_ROOT(head) = (in); \ 358 else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \ 359 RB_LEFT(RB_PARENT(out, field), field) = (in); \ 360 else \ 361 RB_RIGHT(RB_PARENT(out, field), field) = (in); \ 362 } while (/*CONSTCOND*/ 0) 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_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ 368 } \ 369 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 370 RB_SWAP_CHILD(head, elm, tmp, field); \ 371 RB_LEFT(tmp, field) = (elm); \ 372 RB_SET_PARENT(elm, tmp, field); \ 373 RB_AUGMENT(elm); \ 374 } while (/*CONSTCOND*/ 0) 375 376 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 377 (tmp) = RB_LEFT(elm, field); \ 378 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 379 RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ 380 } \ 381 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 382 RB_SWAP_CHILD(head, elm, tmp, field); \ 383 RB_RIGHT(tmp, field) = (elm); \ 384 RB_SET_PARENT(elm, tmp, field); \ 385 RB_AUGMENT(elm); \ 386 } while (/*CONSTCOND*/ 0) 387 388 /* 389 * The RB_PARENT_ROTATE_LEFT() and RB_PARENT_ROTATE_RIGHT() rotations are 390 * specialized versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be 391 * used if the parent node exists and the direction of the child element is 392 * known. 393 */ 394 395 #define RB_PARENT_ROTATE_LEFT(parent, left, tmp, field) do { \ 396 (tmp) = RB_RIGHT(left, field); \ 397 if ((RB_RIGHT(left, field) = RB_LEFT(tmp, field)) != NULL) { \ 398 RB_SET_PARENT(RB_RIGHT(left, field), left, field); \ 399 } \ 400 RB_SET_PARENT(tmp, parent, field); \ 401 RB_LEFT(parent, field) = (tmp); \ 402 RB_LEFT(tmp, field) = (left); \ 403 RB_SET_PARENT(left, tmp, field); \ 404 RB_AUGMENT(left); \ 405 } while (/*CONSTCOND*/ 0) 406 407 #define RB_PARENT_ROTATE_RIGHT(parent, right, tmp, field) do { \ 408 (tmp) = RB_LEFT(right, field); \ 409 if ((RB_LEFT(right, field) = RB_RIGHT(tmp, field)) != NULL) { \ 410 RB_SET_PARENT(RB_LEFT(right, field), right, field); \ 411 } \ 412 RB_SET_PARENT(tmp, parent, field); \ 413 RB_RIGHT(parent, field) = (tmp); \ 414 RB_RIGHT(tmp, field) = (right); \ 415 RB_SET_PARENT(right, tmp, field); \ 416 RB_AUGMENT(right); \ 417 } while (/*CONSTCOND*/ 0) 418 419 /* 420 * The RB_RED_ROTATE_LEFT() and RB_RED_ROTATE_RIGHT() rotations are specialized 421 * versions of RB_ROTATE_LEFT() and RB_ROTATE_RIGHT() which may be used if we 422 * rotate an element with a red child which has a black sibling. Such a red 423 * node must have at least two child nodes so that the following red-black tree 424 * invariant is fulfilled: 425 * 426 * Every path from a given node to any of its descendant NULL nodes goes 427 * through the same number of black nodes. 428 * 429 * elm (could be the root) 430 * / \ 431 * BLACK RED (left or right child) 432 * / \ 433 * BLACK BLACK 434 */ 435 436 #define RB_RED_ROTATE_LEFT(head, elm, tmp, field) do { \ 437 (tmp) = RB_RIGHT(elm, field); \ 438 RB_RIGHT(elm, field) = RB_LEFT(tmp, field); \ 439 RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \ 440 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 441 RB_SWAP_CHILD(head, elm, tmp, field); \ 442 RB_LEFT(tmp, field) = (elm); \ 443 RB_SET_PARENT(elm, tmp, field); \ 444 RB_AUGMENT(elm); \ 445 } while (/*CONSTCOND*/ 0) 446 447 #define RB_RED_ROTATE_RIGHT(head, elm, tmp, field) do { \ 448 (tmp) = RB_LEFT(elm, field); \ 449 RB_LEFT(elm, field) = RB_RIGHT(tmp, field); \ 450 RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \ 451 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \ 452 RB_SWAP_CHILD(head, elm, tmp, field); \ 453 RB_RIGHT(tmp, field) = (elm); \ 454 RB_SET_PARENT(elm, tmp, field); \ 455 RB_AUGMENT(elm); \ 456 } while (/*CONSTCOND*/ 0) 457 458 /* Generates prototypes and inline functions */ 459 #define RB_PROTOTYPE(name, type, field, cmp) \ 460 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 461 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 462 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 463 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 464 RB_PROTOTYPE_INSERT_COLOR(name, type, attr); \ 465 RB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \ 466 RB_PROTOTYPE_INSERT(name, type, attr); \ 467 RB_PROTOTYPE_REMOVE(name, type, attr); \ 468 RB_PROTOTYPE_FIND(name, type, attr); \ 469 RB_PROTOTYPE_NFIND(name, type, attr); \ 470 RB_PROTOTYPE_NEXT(name, type, attr); \ 471 RB_PROTOTYPE_PREV(name, type, attr); \ 472 RB_PROTOTYPE_MINMAX(name, type, attr); \ 473 RB_PROTOTYPE_REINSERT(name, type, attr); 474 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \ 475 attr void name##_RB_INSERT_COLOR(struct name *, struct type *) 476 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \ 477 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *) 478 #define RB_PROTOTYPE_REMOVE(name, type, attr) \ 479 attr struct type *name##_RB_REMOVE(struct name *, struct type *) 480 #define RB_PROTOTYPE_INSERT(name, type, attr) \ 481 attr struct type *name##_RB_INSERT(struct name *, struct type *) 482 #define RB_PROTOTYPE_FIND(name, type, attr) \ 483 attr struct type *name##_RB_FIND(struct name *, struct type *) 484 #define RB_PROTOTYPE_NFIND(name, type, attr) \ 485 attr struct type *name##_RB_NFIND(struct name *, struct type *) 486 #define RB_PROTOTYPE_NEXT(name, type, attr) \ 487 attr struct type *name##_RB_NEXT(struct type *) 488 #define RB_PROTOTYPE_PREV(name, type, attr) \ 489 attr struct type *name##_RB_PREV(struct type *) 490 #define RB_PROTOTYPE_MINMAX(name, type, attr) \ 491 attr struct type *name##_RB_MINMAX(struct name *, int) 492 #define RB_PROTOTYPE_REINSERT(name, type, attr) \ 493 attr struct type *name##_RB_REINSERT(struct name *, struct type *) 494 495 /* Main rb operation. 496 * Moves node close to the key of elm to top 497 */ 498 #define RB_GENERATE(name, type, field, cmp) \ 499 RB_GENERATE_INTERNAL(name, type, field, cmp,) 500 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 501 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 502 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 503 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 504 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 505 RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 506 RB_GENERATE_REMOVE(name, type, field, attr) \ 507 RB_GENERATE_FIND(name, type, field, cmp, attr) \ 508 RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 509 RB_GENERATE_NEXT(name, type, field, attr) \ 510 RB_GENERATE_PREV(name, type, field, attr) \ 511 RB_GENERATE_MINMAX(name, type, field, attr) \ 512 RB_GENERATE_REINSERT(name, type, field, cmp, attr) 513 514 515 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ 516 attr void \ 517 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 518 { \ 519 struct type *parent, *gparent, *tmp; \ 520 while (RB_ISRED((parent = RB_PARENT(elm, field)), field)) { \ 521 gparent = RB_PARENT(parent, field); \ 522 if (parent == RB_LEFT(gparent, field)) { \ 523 tmp = RB_RIGHT(gparent, field); \ 524 if (RB_ISRED(tmp, field)) { \ 525 RB_COLOR(tmp, field) = RB_BLACK; \ 526 RB_SET_BLACKRED(parent, gparent, field);\ 527 elm = gparent; \ 528 continue; \ 529 } \ 530 if (RB_RIGHT(parent, field) == elm) { \ 531 RB_PARENT_ROTATE_LEFT(gparent, parent, \ 532 tmp, field); \ 533 tmp = parent; \ 534 parent = elm; \ 535 elm = tmp; \ 536 } \ 537 RB_SET_BLACKRED(parent, gparent, field); \ 538 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 539 } else { \ 540 tmp = RB_LEFT(gparent, field); \ 541 if (RB_ISRED(tmp, field)) { \ 542 RB_COLOR(tmp, field) = RB_BLACK; \ 543 RB_SET_BLACKRED(parent, gparent, field);\ 544 elm = gparent; \ 545 continue; \ 546 } \ 547 if (RB_LEFT(parent, field) == elm) { \ 548 RB_PARENT_ROTATE_RIGHT(gparent, parent, \ 549 tmp, field); \ 550 tmp = parent; \ 551 parent = elm; \ 552 elm = tmp; \ 553 } \ 554 RB_SET_BLACKRED(parent, gparent, field); \ 555 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 556 } \ 557 } \ 558 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 559 } 560 561 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ 562 attr void \ 563 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent) \ 564 { \ 565 struct type *elm, *tmp; \ 566 elm = NULL; \ 567 do { \ 568 if (RB_LEFT(parent, field) == elm) { \ 569 tmp = RB_RIGHT(parent, field); \ 570 if (RB_COLOR(tmp, field) == RB_RED) { \ 571 RB_SET_BLACKRED(tmp, parent, field); \ 572 RB_RED_ROTATE_LEFT(head, parent, tmp, field); \ 573 tmp = RB_RIGHT(parent, field); \ 574 } \ 575 if (RB_ISRED(RB_RIGHT(tmp, field), field)) \ 576 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 577 else if (RB_ISRED(RB_LEFT(tmp, field), field)) { \ 578 struct type *oleft; \ 579 RB_PARENT_ROTATE_RIGHT(parent, tmp, \ 580 oleft, field); \ 581 RB_COLOR(oleft, field) = RB_BLACK; \ 582 tmp = oleft; \ 583 } else { \ 584 RB_COLOR(tmp, field) = RB_RED; \ 585 elm = parent; \ 586 parent = RB_PARENT(elm, field); \ 587 continue; \ 588 } \ 589 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 590 RB_COLOR(parent, field) = RB_BLACK; \ 591 RB_ROTATE_LEFT(head, parent, tmp, field); \ 592 elm = RB_ROOT(head); \ 593 break; \ 594 } else { \ 595 tmp = RB_LEFT(parent, field); \ 596 if (RB_COLOR(tmp, field) == RB_RED) { \ 597 RB_SET_BLACKRED(tmp, parent, field); \ 598 RB_RED_ROTATE_RIGHT(head, parent, tmp, field); \ 599 tmp = RB_LEFT(parent, field); \ 600 } \ 601 if (RB_ISRED(RB_LEFT(tmp, field), field)) \ 602 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 603 else if (RB_ISRED(RB_RIGHT(tmp, field), field)) { \ 604 struct type *oright; \ 605 RB_PARENT_ROTATE_LEFT(parent, tmp, \ 606 oright, field); \ 607 RB_COLOR(oright, field) = RB_BLACK; \ 608 tmp = oright; \ 609 } else { \ 610 RB_COLOR(tmp, field) = RB_RED; \ 611 elm = parent; \ 612 parent = RB_PARENT(elm, field); \ 613 continue; \ 614 } \ 615 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 616 RB_COLOR(parent, field) = RB_BLACK; \ 617 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 618 elm = RB_ROOT(head); \ 619 break; \ 620 } \ 621 } while (RB_COLOR(elm, field) == RB_BLACK && parent != NULL); \ 622 RB_COLOR(elm, field) = RB_BLACK; \ 623 } 624 625 #define RB_GENERATE_REMOVE(name, type, field, attr) \ 626 attr struct type * \ 627 name##_RB_REMOVE(struct name *head, struct type *elm) \ 628 { \ 629 struct type *child, *old, *parent, *right; \ 630 int color; \ 631 \ 632 old = elm; \ 633 parent = RB_PARENT(elm, field); \ 634 right = RB_RIGHT(elm, field); \ 635 color = RB_COLOR(elm, field); \ 636 if (RB_LEFT(elm, field) == NULL) \ 637 elm = child = right; \ 638 else if (right == NULL) \ 639 elm = child = RB_LEFT(elm, field); \ 640 else { \ 641 if ((child = RB_LEFT(right, field)) == NULL) { \ 642 child = RB_RIGHT(right, field); \ 643 RB_RIGHT(old, field) = child; \ 644 parent = elm = right; \ 645 } else { \ 646 do \ 647 elm = child; \ 648 while ((child = RB_LEFT(elm, field)) != NULL); \ 649 child = RB_RIGHT(elm, field); \ 650 parent = RB_PARENT(elm, field); \ 651 RB_LEFT(parent, field) = child; \ 652 RB_SET_PARENT(RB_RIGHT(old, field), elm, field); \ 653 } \ 654 RB_SET_PARENT(RB_LEFT(old, field), elm, field); \ 655 color = RB_COLOR(elm, field); \ 656 elm->field = old->field; \ 657 } \ 658 RB_SWAP_CHILD(head, old, elm, field); \ 659 if (child != NULL) { \ 660 RB_SET_PARENT(child, parent, field); \ 661 RB_COLOR(child, field) = RB_BLACK; \ 662 } else if (color != RB_RED && parent != NULL) \ 663 name##_RB_REMOVE_COLOR(head, parent); \ 664 while (parent != NULL) { \ 665 RB_AUGMENT(parent); \ 666 parent = RB_PARENT(parent, field); \ 667 } \ 668 return (old); \ 669 } 670 671 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ 672 /* Inserts a node into the RB tree */ \ 673 attr struct type * \ 674 name##_RB_INSERT(struct name *head, struct type *elm) \ 675 { \ 676 struct type *tmp; \ 677 struct type *parent = NULL; \ 678 int comp = 0; \ 679 tmp = RB_ROOT(head); \ 680 while (tmp) { \ 681 parent = tmp; \ 682 comp = (cmp)(elm, parent); \ 683 if (comp < 0) \ 684 tmp = RB_LEFT(tmp, field); \ 685 else if (comp > 0) \ 686 tmp = RB_RIGHT(tmp, field); \ 687 else \ 688 return (tmp); \ 689 } \ 690 RB_SET(elm, parent, field); \ 691 if (parent != NULL) { \ 692 if (comp < 0) \ 693 RB_LEFT(parent, field) = elm; \ 694 else \ 695 RB_RIGHT(parent, field) = elm; \ 696 } else \ 697 RB_ROOT(head) = elm; \ 698 name##_RB_INSERT_COLOR(head, elm); \ 699 while (elm != NULL) { \ 700 RB_AUGMENT(elm); \ 701 elm = RB_PARENT(elm, field); \ 702 } \ 703 return (NULL); \ 704 } 705 706 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ 707 /* Finds the node with the same key as elm */ \ 708 attr struct type * \ 709 name##_RB_FIND(struct name *head, struct type *elm) \ 710 { \ 711 struct type *tmp = RB_ROOT(head); \ 712 int comp; \ 713 while (tmp) { \ 714 comp = cmp(elm, tmp); \ 715 if (comp < 0) \ 716 tmp = RB_LEFT(tmp, field); \ 717 else if (comp > 0) \ 718 tmp = RB_RIGHT(tmp, field); \ 719 else \ 720 return (tmp); \ 721 } \ 722 return (NULL); \ 723 } 724 725 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ 726 /* Finds the first node greater than or equal to the search key */ \ 727 attr struct type * \ 728 name##_RB_NFIND(struct name *head, struct type *elm) \ 729 { \ 730 struct type *tmp = RB_ROOT(head); \ 731 struct type *res = NULL; \ 732 int comp; \ 733 while (tmp) { \ 734 comp = cmp(elm, tmp); \ 735 if (comp < 0) { \ 736 res = tmp; \ 737 tmp = RB_LEFT(tmp, field); \ 738 } \ 739 else if (comp > 0) \ 740 tmp = RB_RIGHT(tmp, field); \ 741 else \ 742 return (tmp); \ 743 } \ 744 return (res); \ 745 } 746 747 #define RB_GENERATE_NEXT(name, type, field, attr) \ 748 /* ARGSUSED */ \ 749 attr struct type * \ 750 name##_RB_NEXT(struct type *elm) \ 751 { \ 752 if (RB_RIGHT(elm, field)) { \ 753 elm = RB_RIGHT(elm, field); \ 754 while (RB_LEFT(elm, field)) \ 755 elm = RB_LEFT(elm, field); \ 756 } else { \ 757 if (RB_PARENT(elm, field) && \ 758 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 759 elm = RB_PARENT(elm, field); \ 760 else { \ 761 while (RB_PARENT(elm, field) && \ 762 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 763 elm = RB_PARENT(elm, field); \ 764 elm = RB_PARENT(elm, field); \ 765 } \ 766 } \ 767 return (elm); \ 768 } 769 770 #define RB_GENERATE_PREV(name, type, field, attr) \ 771 /* ARGSUSED */ \ 772 attr struct type * \ 773 name##_RB_PREV(struct type *elm) \ 774 { \ 775 if (RB_LEFT(elm, field)) { \ 776 elm = RB_LEFT(elm, field); \ 777 while (RB_RIGHT(elm, field)) \ 778 elm = RB_RIGHT(elm, field); \ 779 } else { \ 780 if (RB_PARENT(elm, field) && \ 781 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 782 elm = RB_PARENT(elm, field); \ 783 else { \ 784 while (RB_PARENT(elm, field) && \ 785 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 786 elm = RB_PARENT(elm, field); \ 787 elm = RB_PARENT(elm, field); \ 788 } \ 789 } \ 790 return (elm); \ 791 } 792 793 #define RB_GENERATE_MINMAX(name, type, field, attr) \ 794 attr struct type * \ 795 name##_RB_MINMAX(struct name *head, int val) \ 796 { \ 797 struct type *tmp = RB_ROOT(head); \ 798 struct type *parent = NULL; \ 799 while (tmp) { \ 800 parent = tmp; \ 801 if (val < 0) \ 802 tmp = RB_LEFT(tmp, field); \ 803 else \ 804 tmp = RB_RIGHT(tmp, field); \ 805 } \ 806 return (parent); \ 807 } 808 809 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ 810 attr struct type * \ 811 name##_RB_REINSERT(struct name *head, struct type *elm) \ 812 { \ 813 struct type *cmpelm; \ 814 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \ 815 cmp(cmpelm, elm) >= 0) || \ 816 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \ 817 cmp(elm, cmpelm) >= 0)) { \ 818 /* XXXLAS: Remove/insert is heavy handed. */ \ 819 RB_REMOVE(name, head, elm); \ 820 return (RB_INSERT(name, head, elm)); \ 821 } \ 822 return (NULL); \ 823 } \ 824 825 #define RB_NEGINF -1 826 #define RB_INF 1 827 828 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 829 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 830 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 831 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 832 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 833 #define RB_PREV(name, x, y) name##_RB_PREV(y) 834 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 835 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 836 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y) 837 838 #define RB_FOREACH(x, name, head) \ 839 for ((x) = RB_MIN(name, head); \ 840 (x) != NULL; \ 841 (x) = name##_RB_NEXT(x)) 842 843 #define RB_FOREACH_FROM(x, name, y) \ 844 for ((x) = (y); \ 845 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 846 (x) = (y)) 847 848 #define RB_FOREACH_SAFE(x, name, head, y) \ 849 for ((x) = RB_MIN(name, head); \ 850 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 851 (x) = (y)) 852 853 #define RB_FOREACH_REVERSE(x, name, head) \ 854 for ((x) = RB_MAX(name, head); \ 855 (x) != NULL; \ 856 (x) = name##_RB_PREV(x)) 857 858 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 859 for ((x) = (y); \ 860 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 861 (x) = (y)) 862 863 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 864 for ((x) = RB_MAX(name, head); \ 865 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 866 (x) = (y)) 867 868 #endif /* _SYS_TREE_H_ */ 869
