1/* $OpenBSD: tree.h,v 1.30 2020/10/10 18:03:41 otto Exp $ */ 2/* 3 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27#ifndef _SYS_TREE_H_ 28#define _SYS_TREE_H_ 29 30#include <sys/_null.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) \ 60struct 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 (0) 70 71#define SPLAY_ENTRY(type) \ 72struct { \ 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 (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 (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 (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 (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 (0) 113 114/* Generates prototypes and inline functions */ 115 116#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 117void name##_SPLAY(struct name *, struct type *); \ 118void name##_SPLAY_MINMAX(struct name *, int); \ 119struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 120struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 121 \ 122/* Finds the node with the same key as elm */ \ 123static __unused __inline struct type * \ 124name##_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 \ 134static __unused __inline struct type * \ 135name##_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 \ 148static __unused __inline struct type * \ 149name##_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) \ 159struct type * \ 160name##_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 \ 183struct type * \ 184name##_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 \ 204void \ 205name##_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))) { \ 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 */ \ 242void 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#define RB_HEAD(name, type) \ 294struct name { \ 295 struct type *rbh_root; /* root of the tree */ \ 296} 297 298#define RB_INITIALIZER(root) \ 299 { NULL } 300 301#define RB_INIT(root) do { \ 302 (root)->rbh_root = NULL; \ 303} while (0) 304 305#define RB_BLACK 0 306#define RB_RED 1 307#define RB_ENTRY(type) \ 308struct { \ 309 struct type *rbe_left; /* left element */ \ 310 struct type *rbe_right; /* right element */ \ 311 struct type *rbe_parent; /* parent element */ \ 312 int rbe_color; /* node color */ \ 313} 314 315#define RB_LEFT(elm, field) (elm)->field.rbe_left 316#define RB_RIGHT(elm, field) (elm)->field.rbe_right 317#define RB_PARENT(elm, field) (elm)->field.rbe_parent 318#define RB_COLOR(elm, field) (elm)->field.rbe_color 319#define RB_ROOT(head) (head)->rbh_root 320#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 321 322#define RB_SET(elm, parent, field) do { \ 323 RB_PARENT(elm, field) = parent; \ 324 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 325 RB_COLOR(elm, field) = RB_RED; \ 326} while (0) 327 328#define RB_SET_BLACKRED(black, red, field) do { \ 329 RB_COLOR(black, field) = RB_BLACK; \ 330 RB_COLOR(red, field) = RB_RED; \ 331} while (0) 332 333#ifndef RB_AUGMENT 334#define RB_AUGMENT(x) do {} while (0) 335#endif 336 337#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 338 (tmp) = RB_RIGHT(elm, field); \ 339 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 340 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 341 } \ 342 RB_AUGMENT(elm); \ 343 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 344 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 345 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 346 else \ 347 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 348 } else \ 349 (head)->rbh_root = (tmp); \ 350 RB_LEFT(tmp, field) = (elm); \ 351 RB_PARENT(elm, field) = (tmp); \ 352 RB_AUGMENT(tmp); \ 353 if ((RB_PARENT(tmp, field))) \ 354 RB_AUGMENT(RB_PARENT(tmp, field)); \ 355} while (0) 356 357#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 358 (tmp) = RB_LEFT(elm, field); \ 359 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 360 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 361 } \ 362 RB_AUGMENT(elm); \ 363 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 364 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 365 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 366 else \ 367 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 368 } else \ 369 (head)->rbh_root = (tmp); \ 370 RB_RIGHT(tmp, field) = (elm); \ 371 RB_PARENT(elm, field) = (tmp); \ 372 RB_AUGMENT(tmp); \ 373 if ((RB_PARENT(tmp, field))) \ 374 RB_AUGMENT(RB_PARENT(tmp, field)); \ 375} while (0) 376 377/* Generates prototypes and inline functions */ 378#define RB_PROTOTYPE(name, type, field, cmp) \ 379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 380#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 381 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 382#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 383attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 384attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 385attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 386attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 387attr struct type *name##_RB_FIND(struct name *, struct type *); \ 388attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 389attr struct type *name##_RB_NEXT(struct type *); \ 390attr struct type *name##_RB_PREV(struct type *); \ 391attr struct type *name##_RB_MINMAX(struct name *, int); \ 392 \ 393 394/* Main rb operation. 395 * Moves node close to the key of elm to top 396 */ 397#define RB_GENERATE(name, type, field, cmp) \ 398 RB_GENERATE_INTERNAL(name, type, field, cmp,) 399#define RB_GENERATE_STATIC(name, type, field, cmp) \ 400 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) 401#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 402attr void \ 403name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 404{ \ 405 struct type *parent, *gparent, *tmp; \ 406 while ((parent = RB_PARENT(elm, field)) && \ 407 RB_COLOR(parent, field) == RB_RED) { \ 408 gparent = RB_PARENT(parent, field); \ 409 if (parent == RB_LEFT(gparent, field)) { \ 410 tmp = RB_RIGHT(gparent, field); \ 411 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 412 RB_COLOR(tmp, field) = RB_BLACK; \ 413 RB_SET_BLACKRED(parent, gparent, field);\ 414 elm = gparent; \ 415 continue; \ 416 } \ 417 if (RB_RIGHT(parent, field) == elm) { \ 418 RB_ROTATE_LEFT(head, parent, tmp, field);\ 419 tmp = parent; \ 420 parent = elm; \ 421 elm = tmp; \ 422 } \ 423 RB_SET_BLACKRED(parent, gparent, field); \ 424 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 425 } else { \ 426 tmp = RB_LEFT(gparent, field); \ 427 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 428 RB_COLOR(tmp, field) = RB_BLACK; \ 429 RB_SET_BLACKRED(parent, gparent, field);\ 430 elm = gparent; \ 431 continue; \ 432 } \ 433 if (RB_LEFT(parent, field) == elm) { \ 434 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 435 tmp = parent; \ 436 parent = elm; \ 437 elm = tmp; \ 438 } \ 439 RB_SET_BLACKRED(parent, gparent, field); \ 440 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 441 } \ 442 } \ 443 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 444} \ 445 \ 446attr void \ 447name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 448{ \ 449 struct type *tmp; \ 450 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 451 elm != RB_ROOT(head)) { \ 452 if (RB_LEFT(parent, field) == elm) { \ 453 tmp = RB_RIGHT(parent, field); \ 454 if (RB_COLOR(tmp, field) == RB_RED) { \ 455 RB_SET_BLACKRED(tmp, parent, field); \ 456 RB_ROTATE_LEFT(head, parent, tmp, field);\ 457 tmp = RB_RIGHT(parent, field); \ 458 } \ 459 if ((RB_LEFT(tmp, field) == NULL || \ 460 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 461 (RB_RIGHT(tmp, field) == NULL || \ 462 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 463 RB_COLOR(tmp, field) = RB_RED; \ 464 elm = parent; \ 465 parent = RB_PARENT(elm, field); \ 466 } else { \ 467 if (RB_RIGHT(tmp, field) == NULL || \ 468 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 469 struct type *oleft; \ 470 if ((oleft = RB_LEFT(tmp, field)))\ 471 RB_COLOR(oleft, field) = RB_BLACK;\ 472 RB_COLOR(tmp, field) = RB_RED; \ 473 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 474 tmp = RB_RIGHT(parent, field); \ 475 } \ 476 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 477 RB_COLOR(parent, field) = RB_BLACK; \ 478 if (RB_RIGHT(tmp, field)) \ 479 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 480 RB_ROTATE_LEFT(head, parent, tmp, field);\ 481 elm = RB_ROOT(head); \ 482 break; \ 483 } \ 484 } else { \ 485 tmp = RB_LEFT(parent, field); \ 486 if (RB_COLOR(tmp, field) == RB_RED) { \ 487 RB_SET_BLACKRED(tmp, parent, field); \ 488 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 489 tmp = RB_LEFT(parent, field); \ 490 } \ 491 if ((RB_LEFT(tmp, field) == NULL || \ 492 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 493 (RB_RIGHT(tmp, field) == NULL || \ 494 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 495 RB_COLOR(tmp, field) = RB_RED; \ 496 elm = parent; \ 497 parent = RB_PARENT(elm, field); \ 498 } else { \ 499 if (RB_LEFT(tmp, field) == NULL || \ 500 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 501 struct type *oright; \ 502 if ((oright = RB_RIGHT(tmp, field)))\ 503 RB_COLOR(oright, field) = RB_BLACK;\ 504 RB_COLOR(tmp, field) = RB_RED; \ 505 RB_ROTATE_LEFT(head, tmp, oright, field);\ 506 tmp = RB_LEFT(parent, field); \ 507 } \ 508 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 509 RB_COLOR(parent, field) = RB_BLACK; \ 510 if (RB_LEFT(tmp, field)) \ 511 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 512 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 513 elm = RB_ROOT(head); \ 514 break; \ 515 } \ 516 } \ 517 } \ 518 if (elm) \ 519 RB_COLOR(elm, field) = RB_BLACK; \ 520} \ 521 \ 522attr struct type * \ 523name##_RB_REMOVE(struct name *head, struct type *elm) \ 524{ \ 525 struct type *child, *parent, *old = elm; \ 526 int color; \ 527 if (RB_LEFT(elm, field) == NULL) \ 528 child = RB_RIGHT(elm, field); \ 529 else if (RB_RIGHT(elm, field) == NULL) \ 530 child = RB_LEFT(elm, field); \ 531 else { \ 532 struct type *left; \ 533 elm = RB_RIGHT(elm, field); \ 534 while ((left = RB_LEFT(elm, field))) \ 535 elm = left; \ 536 child = RB_RIGHT(elm, field); \ 537 parent = RB_PARENT(elm, field); \ 538 color = RB_COLOR(elm, field); \ 539 if (child) \ 540 RB_PARENT(child, field) = parent; \ 541 if (parent) { \ 542 if (RB_LEFT(parent, field) == elm) \ 543 RB_LEFT(parent, field) = child; \ 544 else \ 545 RB_RIGHT(parent, field) = child; \ 546 RB_AUGMENT(parent); \ 547 } else \ 548 RB_ROOT(head) = child; \ 549 if (RB_PARENT(elm, field) == old) \ 550 parent = elm; \ 551 (elm)->field = (old)->field; \ 552 if (RB_PARENT(old, field)) { \ 553 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 554 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 555 else \ 556 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 557 RB_AUGMENT(RB_PARENT(old, field)); \ 558 } else \ 559 RB_ROOT(head) = elm; \ 560 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 561 if (RB_RIGHT(old, field)) \ 562 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 563 if (parent) { \ 564 left = parent; \ 565 do { \ 566 RB_AUGMENT(left); \ 567 } while ((left = RB_PARENT(left, field))); \ 568 } \ 569 goto color; \ 570 } \ 571 parent = RB_PARENT(elm, field); \ 572 color = RB_COLOR(elm, field); \ 573 if (child) \ 574 RB_PARENT(child, field) = parent; \ 575 if (parent) { \ 576 if (RB_LEFT(parent, field) == elm) \ 577 RB_LEFT(parent, field) = child; \ 578 else \ 579 RB_RIGHT(parent, field) = child; \ 580 RB_AUGMENT(parent); \ 581 } else \ 582 RB_ROOT(head) = child; \ 583color: \ 584 if (color == RB_BLACK) \ 585 name##_RB_REMOVE_COLOR(head, parent, child); \ 586 return (old); \ 587} \ 588 \ 589/* Inserts a node into the RB tree */ \ 590attr struct type * \ 591name##_RB_INSERT(struct name *head, struct type *elm) \ 592{ \ 593 struct type *tmp; \ 594 struct type *parent = NULL; \ 595 int comp = 0; \ 596 tmp = RB_ROOT(head); \ 597 while (tmp) { \ 598 parent = tmp; \ 599 comp = (cmp)(elm, parent); \ 600 if (comp < 0) \ 601 tmp = RB_LEFT(tmp, field); \ 602 else if (comp > 0) \ 603 tmp = RB_RIGHT(tmp, field); \ 604 else \ 605 return (tmp); \ 606 } \ 607 RB_SET(elm, parent, field); \ 608 if (parent != NULL) { \ 609 if (comp < 0) \ 610 RB_LEFT(parent, field) = elm; \ 611 else \ 612 RB_RIGHT(parent, field) = elm; \ 613 RB_AUGMENT(parent); \ 614 } else \ 615 RB_ROOT(head) = elm; \ 616 name##_RB_INSERT_COLOR(head, elm); \ 617 return (NULL); \ 618} \ 619 \ 620/* Finds the node with the same key as elm */ \ 621attr struct type * \ 622name##_RB_FIND(struct name *head, struct type *elm) \ 623{ \ 624 struct type *tmp = RB_ROOT(head); \ 625 int comp; \ 626 while (tmp) { \ 627 comp = cmp(elm, tmp); \ 628 if (comp < 0) \ 629 tmp = RB_LEFT(tmp, field); \ 630 else if (comp > 0) \ 631 tmp = RB_RIGHT(tmp, field); \ 632 else \ 633 return (tmp); \ 634 } \ 635 return (NULL); \ 636} \ 637 \ 638/* Finds the first node greater than or equal to the search key */ \ 639attr struct type * \ 640name##_RB_NFIND(struct name *head, struct type *elm) \ 641{ \ 642 struct type *tmp = RB_ROOT(head); \ 643 struct type *res = NULL; \ 644 int comp; \ 645 while (tmp) { \ 646 comp = cmp(elm, tmp); \ 647 if (comp < 0) { \ 648 res = tmp; \ 649 tmp = RB_LEFT(tmp, field); \ 650 } \ 651 else if (comp > 0) \ 652 tmp = RB_RIGHT(tmp, field); \ 653 else \ 654 return (tmp); \ 655 } \ 656 return (res); \ 657} \ 658 \ 659/* ARGSUSED */ \ 660attr struct type * \ 661name##_RB_NEXT(struct type *elm) \ 662{ \ 663 if (RB_RIGHT(elm, field)) { \ 664 elm = RB_RIGHT(elm, field); \ 665 while (RB_LEFT(elm, field)) \ 666 elm = RB_LEFT(elm, field); \ 667 } else { \ 668 if (RB_PARENT(elm, field) && \ 669 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 670 elm = RB_PARENT(elm, field); \ 671 else { \ 672 while (RB_PARENT(elm, field) && \ 673 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 674 elm = RB_PARENT(elm, field); \ 675 elm = RB_PARENT(elm, field); \ 676 } \ 677 } \ 678 return (elm); \ 679} \ 680 \ 681/* ARGSUSED */ \ 682attr struct type * \ 683name##_RB_PREV(struct type *elm) \ 684{ \ 685 if (RB_LEFT(elm, field)) { \ 686 elm = RB_LEFT(elm, field); \ 687 while (RB_RIGHT(elm, field)) \ 688 elm = RB_RIGHT(elm, field); \ 689 } else { \ 690 if (RB_PARENT(elm, field) && \ 691 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 692 elm = RB_PARENT(elm, field); \ 693 else { \ 694 while (RB_PARENT(elm, field) && \ 695 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 696 elm = RB_PARENT(elm, field); \ 697 elm = RB_PARENT(elm, field); \ 698 } \ 699 } \ 700 return (elm); \ 701} \ 702 \ 703attr struct type * \ 704name##_RB_MINMAX(struct name *head, int val) \ 705{ \ 706 struct type *tmp = RB_ROOT(head); \ 707 struct type *parent = NULL; \ 708 while (tmp) { \ 709 parent = tmp; \ 710 if (val < 0) \ 711 tmp = RB_LEFT(tmp, field); \ 712 else \ 713 tmp = RB_RIGHT(tmp, field); \ 714 } \ 715 return (parent); \ 716} 717 718#define RB_NEGINF -1 719#define RB_INF 1 720 721#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 722#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 723#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 724#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 725#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 726#define RB_PREV(name, x, y) name##_RB_PREV(y) 727#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 728#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 729 730#define RB_FOREACH(x, name, head) \ 731 for ((x) = RB_MIN(name, head); \ 732 (x) != NULL; \ 733 (x) = name##_RB_NEXT(x)) 734 735#define RB_FOREACH_SAFE(x, name, head, y) \ 736 for ((x) = RB_MIN(name, head); \ 737 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ 738 (x) = (y)) 739 740#define RB_FOREACH_REVERSE(x, name, head) \ 741 for ((x) = RB_MAX(name, head); \ 742 (x) != NULL; \ 743 (x) = name##_RB_PREV(x)) 744 745#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 746 for ((x) = RB_MAX(name, head); \ 747 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ 748 (x) = (y)) 749 750 751/* 752 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> 753 * 754 * Permission to use, copy, modify, and distribute this software for any 755 * purpose with or without fee is hereby granted, provided that the above 756 * copyright notice and this permission notice appear in all copies. 757 * 758 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 759 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 760 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 761 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 762 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 763 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 764 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 765 */ 766 767struct rb_type { 768 int (*t_compare)(const void *, const void *); 769 void (*t_augment)(void *); 770 unsigned int t_offset; /* offset of rb_entry in type */ 771}; 772 773struct rb_tree { 774 struct rb_entry *rbt_root; 775}; 776 777struct rb_entry { 778 struct rb_entry *rbt_parent; 779 struct rb_entry *rbt_left; 780 struct rb_entry *rbt_right; 781 unsigned int rbt_color; 782}; 783 784#define RBT_HEAD(_name, _type) \ 785struct _name { \ 786 struct rb_tree rbh_root; \ 787} 788 789#define RBT_ENTRY(_type) struct rb_entry 790 791static inline void 792_rb_init(struct rb_tree *rbt) 793{ 794 rbt->rbt_root = NULL; 795} 796 797static inline int 798_rb_empty(struct rb_tree *rbt) 799{ 800 return (rbt->rbt_root == NULL); 801} 802 803void *_rb_insert(const struct rb_type *, struct rb_tree *, void *); 804void *_rb_remove(const struct rb_type *, struct rb_tree *, void *); 805void *_rb_find(const struct rb_type *, struct rb_tree *, const void *); 806void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *); 807void *_rb_root(const struct rb_type *, struct rb_tree *); 808void *_rb_min(const struct rb_type *, struct rb_tree *); 809void *_rb_max(const struct rb_type *, struct rb_tree *); 810void *_rb_next(const struct rb_type *, void *); 811void *_rb_prev(const struct rb_type *, void *); 812void *_rb_left(const struct rb_type *, void *); 813void *_rb_right(const struct rb_type *, void *); 814void *_rb_parent(const struct rb_type *, void *); 815void _rb_set_left(const struct rb_type *, void *, void *); 816void _rb_set_right(const struct rb_type *, void *, void *); 817void _rb_set_parent(const struct rb_type *, void *, void *); 818void _rb_poison(const struct rb_type *, void *, unsigned long); 819int _rb_check(const struct rb_type *, void *, unsigned long); 820 821#define RBT_INITIALIZER(_head) { { NULL } } 822 823#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \ 824extern const struct rb_type *const _name##_RBT_TYPE; \ 825 \ 826__unused static inline void \ 827_name##_RBT_INIT(struct _name *head) \ 828{ \ 829 _rb_init(&head->rbh_root); \ 830} \ 831 \ 832__unused static inline struct _type * \ 833_name##_RBT_INSERT(struct _name *head, struct _type *elm) \ 834{ \ 835 return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \ 836} \ 837 \ 838__unused static inline struct _type * \ 839_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \ 840{ \ 841 return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \ 842} \ 843 \ 844__unused static inline struct _type * \ 845_name##_RBT_FIND(struct _name *head, const struct _type *key) \ 846{ \ 847 return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \ 848} \ 849 \ 850__unused static inline struct _type * \ 851_name##_RBT_NFIND(struct _name *head, const struct _type *key) \ 852{ \ 853 return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \ 854} \ 855 \ 856__unused static inline struct _type * \ 857_name##_RBT_ROOT(struct _name *head) \ 858{ \ 859 return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \ 860} \ 861 \ 862__unused static inline int \ 863_name##_RBT_EMPTY(struct _name *head) \ 864{ \ 865 return _rb_empty(&head->rbh_root); \ 866} \ 867 \ 868__unused static inline struct _type * \ 869_name##_RBT_MIN(struct _name *head) \ 870{ \ 871 return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \ 872} \ 873 \ 874__unused static inline struct _type * \ 875_name##_RBT_MAX(struct _name *head) \ 876{ \ 877 return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \ 878} \ 879 \ 880__unused static inline struct _type * \ 881_name##_RBT_NEXT(struct _type *elm) \ 882{ \ 883 return _rb_next(_name##_RBT_TYPE, elm); \ 884} \ 885 \ 886__unused static inline struct _type * \ 887_name##_RBT_PREV(struct _type *elm) \ 888{ \ 889 return _rb_prev(_name##_RBT_TYPE, elm); \ 890} \ 891 \ 892__unused static inline struct _type * \ 893_name##_RBT_LEFT(struct _type *elm) \ 894{ \ 895 return _rb_left(_name##_RBT_TYPE, elm); \ 896} \ 897 \ 898__unused static inline struct _type * \ 899_name##_RBT_RIGHT(struct _type *elm) \ 900{ \ 901 return _rb_right(_name##_RBT_TYPE, elm); \ 902} \ 903 \ 904__unused static inline struct _type * \ 905_name##_RBT_PARENT(struct _type *elm) \ 906{ \ 907 return _rb_parent(_name##_RBT_TYPE, elm); \ 908} \ 909 \ 910__unused static inline void \ 911_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \ 912{ \ 913 _rb_set_left(_name##_RBT_TYPE, elm, left); \ 914} \ 915 \ 916__unused static inline void \ 917_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \ 918{ \ 919 _rb_set_right(_name##_RBT_TYPE, elm, right); \ 920} \ 921 \ 922__unused static inline void \ 923_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \ 924{ \ 925 _rb_set_parent(_name##_RBT_TYPE, elm, parent); \ 926} \ 927 \ 928__unused static inline void \ 929_name##_RBT_POISON(struct _type *elm, unsigned long poison) \ 930{ \ 931 _rb_poison(_name##_RBT_TYPE, elm, poison); \ 932} \ 933 \ 934__unused static inline int \ 935_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \ 936{ \ 937 return _rb_check(_name##_RBT_TYPE, elm, poison); \ 938} 939 940#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ 941static int \ 942_name##_RBT_COMPARE(const void *lptr, const void *rptr) \ 943{ \ 944 const struct _type *l = lptr, *r = rptr; \ 945 return _cmp(l, r); \ 946} \ 947static const struct rb_type _name##_RBT_INFO = { \ 948 _name##_RBT_COMPARE, \ 949 _aug, \ 950 offsetof(struct _type, _field), \ 951}; \ 952const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO 953 954#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ 955static void \ 956_name##_RBT_AUGMENT(void *ptr) \ 957{ \ 958 struct _type *p = ptr; \ 959 return _aug(p); \ 960} \ 961RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT) 962 963#define RBT_GENERATE(_name, _type, _field, _cmp) \ 964 RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) 965 966#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head) 967#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm) 968#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm) 969#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key) 970#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key) 971#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head) 972#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head) 973#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head) 974#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head) 975#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm) 976#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm) 977#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm) 978#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm) 979#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm) 980#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l) 981#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r) 982#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p) 983#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p) 984#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p) 985 986#define RBT_FOREACH(_e, _name, _head) \ 987 for ((_e) = RBT_MIN(_name, (_head)); \ 988 (_e) != NULL; \ 989 (_e) = RBT_NEXT(_name, (_e))) 990 991#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \ 992 for ((_e) = RBT_MIN(_name, (_head)); \ 993 (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \ 994 (_e) = (_n)) 995 996#define RBT_FOREACH_REVERSE(_e, _name, _head) \ 997 for ((_e) = RBT_MAX(_name, (_head)); \ 998 (_e) != NULL; \ 999 (_e) = RBT_PREV(_name, (_e))) 1000 1001#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ 1002 for ((_e) = RBT_MAX(_name, (_head)); \ 1003 (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \ 1004 (_e) = (_n)) 1005 1006#endif /* _SYS_TREE_H_ */ 1007