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: src/sys/sys/tree.h,v 1.9.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $ */ 4 5/*- 6 * Copyright 2002 Niels Provos <provos@citi.umich.edu> 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#ifndef _SYS_TREE_H_ 31#define _SYS_TREE_H_ 32 33/* Ommit "struct" prefix if this code is built with C++, 34 * so it can build. */ 35#ifdef __cplusplus 36#define SYS_TREE_STRUCT 37#else 38#define SYS_TREE_STRUCT struct 39#endif 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) \ 69struct name { \ 70 SYS_TREE_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) \ 81struct { \ 82 SYS_TREE_STRUCT type *spe_left; /* left element */ \ 83 SYS_TREE_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) \ 126void name##_SPLAY(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 127void name##_SPLAY_MINMAX(SYS_TREE_STRUCT name *, int); \ 128SYS_TREE_STRUCT type *name##_SPLAY_INSERT(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 129SYS_TREE_STRUCT type *name##_SPLAY_REMOVE(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 130 \ 131/* Finds the node with the same key as elm */ \ 132static __inline SYS_TREE_STRUCT type * \ 133name##_SPLAY_FIND(SYS_TREE_STRUCT name *head, SYS_TREE_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 \ 143static __inline SYS_TREE_STRUCT type * \ 144name##_SPLAY_NEXT(SYS_TREE_STRUCT name *head, SYS_TREE_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 \ 157static __inline SYS_TREE_STRUCT type * \ 158name##_SPLAY_MIN_MAX(SYS_TREE_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) \ 168SYS_TREE_STRUCT type * \ 169name##_SPLAY_INSERT(SYS_TREE_STRUCT name *head, SYS_TREE_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 \ 192SYS_TREE_STRUCT type * \ 193name##_SPLAY_REMOVE(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 194{ \ 195 SYS_TREE_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 \ 213void \ 214name##_SPLAY(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 215{ \ 216 SYS_TREE_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 */ \ 251void name##_SPLAY_MINMAX(SYS_TREE_STRUCT name *head, int __comp) \ 252{ \ 253 SYS_TREE_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) \ 303struct name { \ 304 SYS_TREE_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) \ 317struct { \ 318 SYS_TREE_STRUCT type *rbe_left; /* left element */ \ 319 SYS_TREE_STRUCT type *rbe_right; /* right element */ \ 320 SYS_TREE_STRUCT type *rbe_parent; /* parent element */ \ 321 int rbe_color; /* node color */ \ 322} 323 324#define RB_LEFT(elm, field) (elm)->field.rbe_left 325#define RB_RIGHT(elm, field) (elm)->field.rbe_right 326#define RB_PARENT(elm, field) (elm)->field.rbe_parent 327#define RB_COLOR(elm, field) (elm)->field.rbe_color 328#define RB_ROOT(head) (head)->rbh_root 329#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 330 331#define RB_SET(elm, parent, field) do { \ 332 RB_PARENT(elm, field) = parent; \ 333 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 334 RB_COLOR(elm, field) = RB_RED; \ 335} while (/*CONSTCOND*/ 0) 336 337#define RB_SET_BLACKRED(black, red, field) do { \ 338 RB_COLOR(black, field) = RB_BLACK; \ 339 RB_COLOR(red, field) = RB_RED; \ 340} while (/*CONSTCOND*/ 0) 341 342#ifndef RB_AUGMENT 343#define RB_AUGMENT(x) do {} while (0) 344#endif 345 346#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 347 (tmp) = RB_RIGHT(elm, field); \ 348 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 349 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 350 } \ 351 RB_AUGMENT(elm); \ 352 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 353 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 354 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 355 else \ 356 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 357 } else \ 358 (head)->rbh_root = (tmp); \ 359 RB_LEFT(tmp, field) = (elm); \ 360 RB_PARENT(elm, field) = (tmp); \ 361 RB_AUGMENT(tmp); \ 362 if ((RB_PARENT(tmp, field))) \ 363 RB_AUGMENT(RB_PARENT(tmp, field)); \ 364} while (/*CONSTCOND*/ 0) 365 366#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 367 (tmp) = RB_LEFT(elm, field); \ 368 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 369 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 370 } \ 371 RB_AUGMENT(elm); \ 372 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 373 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 374 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 375 else \ 376 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 377 } else \ 378 (head)->rbh_root = (tmp); \ 379 RB_RIGHT(tmp, field) = (elm); \ 380 RB_PARENT(elm, field) = (tmp); \ 381 RB_AUGMENT(tmp); \ 382 if ((RB_PARENT(tmp, field))) \ 383 RB_AUGMENT(RB_PARENT(tmp, field)); \ 384} while (/*CONSTCOND*/ 0) 385 386/* Generates prototypes and inline functions */ 387#define RB_PROTOTYPE(name, type, field, cmp) \ 388 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 389#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 390 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static) 391#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 392attr void name##_RB_INSERT_COLOR(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 393attr void name##_RB_REMOVE_COLOR(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *, SYS_TREE_STRUCT type *);\ 394attr SYS_TREE_STRUCT type *name##_RB_REMOVE(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 395attr SYS_TREE_STRUCT type *name##_RB_INSERT(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 396attr SYS_TREE_STRUCT type *name##_RB_FIND(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 397attr SYS_TREE_STRUCT type *name##_RB_NFIND(SYS_TREE_STRUCT name *, SYS_TREE_STRUCT type *); \ 398attr SYS_TREE_STRUCT type *name##_RB_NEXT(SYS_TREE_STRUCT type *); \ 399attr SYS_TREE_STRUCT type *name##_RB_PREV(SYS_TREE_STRUCT type *); \ 400attr SYS_TREE_STRUCT type *name##_RB_MINMAX(SYS_TREE_STRUCT name *, int); \ 401 \ 402 403/* Main rb operation. 404 * Moves node close to the key of elm to top 405 */ 406#define RB_GENERATE(name, type, field, cmp) \ 407 RB_GENERATE_INTERNAL(name, type, field, cmp,) 408#define RB_GENERATE_STATIC(name, type, field, cmp) \ 409 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static) 410#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 411attr void \ 412name##_RB_INSERT_COLOR(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 413{ \ 414 SYS_TREE_STRUCT type *parent, *gparent, *tmp; \ 415 while ((parent = RB_PARENT(elm, field)) != NULL && \ 416 RB_COLOR(parent, field) == RB_RED) { \ 417 gparent = RB_PARENT(parent, field); \ 418 if (parent == RB_LEFT(gparent, field)) { \ 419 tmp = RB_RIGHT(gparent, field); \ 420 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 421 RB_COLOR(tmp, field) = RB_BLACK; \ 422 RB_SET_BLACKRED(parent, gparent, field);\ 423 elm = gparent; \ 424 continue; \ 425 } \ 426 if (RB_RIGHT(parent, field) == elm) { \ 427 RB_ROTATE_LEFT(head, parent, tmp, field);\ 428 tmp = parent; \ 429 parent = elm; \ 430 elm = tmp; \ 431 } \ 432 RB_SET_BLACKRED(parent, gparent, field); \ 433 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 434 } else { \ 435 tmp = RB_LEFT(gparent, field); \ 436 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 437 RB_COLOR(tmp, field) = RB_BLACK; \ 438 RB_SET_BLACKRED(parent, gparent, field);\ 439 elm = gparent; \ 440 continue; \ 441 } \ 442 if (RB_LEFT(parent, field) == elm) { \ 443 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 444 tmp = parent; \ 445 parent = elm; \ 446 elm = tmp; \ 447 } \ 448 RB_SET_BLACKRED(parent, gparent, field); \ 449 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 450 } \ 451 } \ 452 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 453} \ 454 \ 455attr void \ 456name##_RB_REMOVE_COLOR(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *parent, SYS_TREE_STRUCT type *elm) \ 457{ \ 458 SYS_TREE_STRUCT type *tmp; \ 459 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 460 elm != RB_ROOT(head)) { \ 461 if (RB_LEFT(parent, field) == elm) { \ 462 tmp = RB_RIGHT(parent, field); \ 463 if (RB_COLOR(tmp, field) == RB_RED) { \ 464 RB_SET_BLACKRED(tmp, parent, field); \ 465 RB_ROTATE_LEFT(head, parent, tmp, field);\ 466 tmp = RB_RIGHT(parent, field); \ 467 } \ 468 if ((RB_LEFT(tmp, field) == NULL || \ 469 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 470 (RB_RIGHT(tmp, field) == NULL || \ 471 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 472 RB_COLOR(tmp, field) = RB_RED; \ 473 elm = parent; \ 474 parent = RB_PARENT(elm, field); \ 475 } else { \ 476 if (RB_RIGHT(tmp, field) == NULL || \ 477 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 478 SYS_TREE_STRUCT type *oleft; \ 479 if ((oleft = RB_LEFT(tmp, field)) \ 480 != NULL) \ 481 RB_COLOR(oleft, field) = RB_BLACK;\ 482 RB_COLOR(tmp, field) = RB_RED; \ 483 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 484 tmp = RB_RIGHT(parent, field); \ 485 } \ 486 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 487 RB_COLOR(parent, field) = RB_BLACK; \ 488 if (RB_RIGHT(tmp, field)) \ 489 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 490 RB_ROTATE_LEFT(head, parent, tmp, field);\ 491 elm = RB_ROOT(head); \ 492 break; \ 493 } \ 494 } else { \ 495 tmp = RB_LEFT(parent, field); \ 496 if (RB_COLOR(tmp, field) == RB_RED) { \ 497 RB_SET_BLACKRED(tmp, parent, field); \ 498 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 499 tmp = RB_LEFT(parent, field); \ 500 } \ 501 if ((RB_LEFT(tmp, field) == NULL || \ 502 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 503 (RB_RIGHT(tmp, field) == NULL || \ 504 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 505 RB_COLOR(tmp, field) = RB_RED; \ 506 elm = parent; \ 507 parent = RB_PARENT(elm, field); \ 508 } else { \ 509 if (RB_LEFT(tmp, field) == NULL || \ 510 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 511 SYS_TREE_STRUCT type *oright; \ 512 if ((oright = RB_RIGHT(tmp, field)) \ 513 != NULL) \ 514 RB_COLOR(oright, field) = RB_BLACK;\ 515 RB_COLOR(tmp, field) = RB_RED; \ 516 RB_ROTATE_LEFT(head, tmp, oright, field);\ 517 tmp = RB_LEFT(parent, field); \ 518 } \ 519 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 520 RB_COLOR(parent, field) = RB_BLACK; \ 521 if (RB_LEFT(tmp, field)) \ 522 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 523 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 524 elm = RB_ROOT(head); \ 525 break; \ 526 } \ 527 } \ 528 } \ 529 if (elm) \ 530 RB_COLOR(elm, field) = RB_BLACK; \ 531} \ 532 \ 533attr SYS_TREE_STRUCT type * \ 534name##_RB_REMOVE(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 535{ \ 536 SYS_TREE_STRUCT type *child, *parent, *old = elm; \ 537 int color; \ 538 if (RB_LEFT(elm, field) == NULL) \ 539 child = RB_RIGHT(elm, field); \ 540 else if (RB_RIGHT(elm, field) == NULL) \ 541 child = RB_LEFT(elm, field); \ 542 else { \ 543 SYS_TREE_STRUCT type *left; \ 544 elm = RB_RIGHT(elm, field); \ 545 while ((left = RB_LEFT(elm, field)) != NULL) \ 546 elm = left; \ 547 child = RB_RIGHT(elm, field); \ 548 parent = RB_PARENT(elm, field); \ 549 color = RB_COLOR(elm, field); \ 550 if (child) \ 551 RB_PARENT(child, field) = parent; \ 552 if (parent) { \ 553 if (RB_LEFT(parent, field) == elm) \ 554 RB_LEFT(parent, field) = child; \ 555 else \ 556 RB_RIGHT(parent, field) = child; \ 557 RB_AUGMENT(parent); \ 558 } else \ 559 RB_ROOT(head) = child; \ 560 if (RB_PARENT(elm, field) == old) \ 561 parent = elm; \ 562 (elm)->field = (old)->field; \ 563 if (RB_PARENT(old, field)) { \ 564 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 565 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 566 else \ 567 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 568 RB_AUGMENT(RB_PARENT(old, field)); \ 569 } else \ 570 RB_ROOT(head) = elm; \ 571 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 572 if (RB_RIGHT(old, field)) \ 573 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 574 if (parent) { \ 575 left = parent; \ 576 do { \ 577 RB_AUGMENT(left); \ 578 } while ((left = RB_PARENT(left, field)) != NULL); \ 579 } \ 580 goto color; \ 581 } \ 582 parent = RB_PARENT(elm, field); \ 583 color = RB_COLOR(elm, field); \ 584 if (child) \ 585 RB_PARENT(child, field) = parent; \ 586 if (parent) { \ 587 if (RB_LEFT(parent, field) == elm) \ 588 RB_LEFT(parent, field) = child; \ 589 else \ 590 RB_RIGHT(parent, field) = child; \ 591 RB_AUGMENT(parent); \ 592 } else \ 593 RB_ROOT(head) = child; \ 594color: \ 595 if (color == RB_BLACK) \ 596 name##_RB_REMOVE_COLOR(head, parent, child); \ 597 return (old); \ 598} \ 599 \ 600/* Inserts a node into the RB tree */ \ 601attr SYS_TREE_STRUCT type * \ 602name##_RB_INSERT(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 603{ \ 604 SYS_TREE_STRUCT type *tmp; \ 605 SYS_TREE_STRUCT type *parent = NULL; \ 606 int comp = 0; \ 607 tmp = RB_ROOT(head); \ 608 while (tmp) { \ 609 parent = tmp; \ 610 comp = (cmp)(elm, parent); \ 611 if (comp < 0) \ 612 tmp = RB_LEFT(tmp, field); \ 613 else if (comp > 0) \ 614 tmp = RB_RIGHT(tmp, field); \ 615 else \ 616 return (tmp); \ 617 } \ 618 RB_SET(elm, parent, field); \ 619 if (parent != NULL) { \ 620 if (comp < 0) \ 621 RB_LEFT(parent, field) = elm; \ 622 else \ 623 RB_RIGHT(parent, field) = elm; \ 624 RB_AUGMENT(parent); \ 625 } else \ 626 RB_ROOT(head) = elm; \ 627 name##_RB_INSERT_COLOR(head, elm); \ 628 return (NULL); \ 629} \ 630 \ 631/* Finds the node with the same key as elm */ \ 632attr SYS_TREE_STRUCT type * \ 633name##_RB_FIND(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 634{ \ 635 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \ 636 int comp; \ 637 while (tmp) { \ 638 comp = cmp(elm, tmp); \ 639 if (comp < 0) \ 640 tmp = RB_LEFT(tmp, field); \ 641 else if (comp > 0) \ 642 tmp = RB_RIGHT(tmp, field); \ 643 else \ 644 return (tmp); \ 645 } \ 646 return (NULL); \ 647} \ 648 \ 649/* Finds the first node greater than or equal to the search key */ \ 650attr SYS_TREE_STRUCT type * \ 651name##_RB_NFIND(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \ 652{ \ 653 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \ 654 SYS_TREE_STRUCT type *res = NULL; \ 655 int comp; \ 656 while (tmp) { \ 657 comp = cmp(elm, tmp); \ 658 if (comp < 0) { \ 659 res = tmp; \ 660 tmp = RB_LEFT(tmp, field); \ 661 } \ 662 else if (comp > 0) \ 663 tmp = RB_RIGHT(tmp, field); \ 664 else \ 665 return (tmp); \ 666 } \ 667 return (res); \ 668} \ 669 \ 670/* ARGSUSED */ \ 671attr SYS_TREE_STRUCT type * \ 672name##_RB_NEXT(SYS_TREE_STRUCT type *elm) \ 673{ \ 674 if (RB_RIGHT(elm, field)) { \ 675 elm = RB_RIGHT(elm, field); \ 676 while (RB_LEFT(elm, field)) \ 677 elm = RB_LEFT(elm, field); \ 678 } else { \ 679 if (RB_PARENT(elm, field) && \ 680 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 681 elm = RB_PARENT(elm, field); \ 682 else { \ 683 while (RB_PARENT(elm, field) && \ 684 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 685 elm = RB_PARENT(elm, field); \ 686 elm = RB_PARENT(elm, field); \ 687 } \ 688 } \ 689 return (elm); \ 690} \ 691 \ 692/* ARGSUSED */ \ 693attr SYS_TREE_STRUCT type * \ 694name##_RB_PREV(SYS_TREE_STRUCT type *elm) \ 695{ \ 696 if (RB_LEFT(elm, field)) { \ 697 elm = RB_LEFT(elm, field); \ 698 while (RB_RIGHT(elm, field)) \ 699 elm = RB_RIGHT(elm, field); \ 700 } else { \ 701 if (RB_PARENT(elm, field) && \ 702 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 703 elm = RB_PARENT(elm, field); \ 704 else { \ 705 while (RB_PARENT(elm, field) && \ 706 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ 707 elm = RB_PARENT(elm, field); \ 708 elm = RB_PARENT(elm, field); \ 709 } \ 710 } \ 711 return (elm); \ 712} \ 713 \ 714attr SYS_TREE_STRUCT type * \ 715name##_RB_MINMAX(SYS_TREE_STRUCT name *head, int val) \ 716{ \ 717 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \ 718 SYS_TREE_STRUCT type *parent = NULL; \ 719 while (tmp) { \ 720 parent = tmp; \ 721 if (val < 0) \ 722 tmp = RB_LEFT(tmp, field); \ 723 else \ 724 tmp = RB_RIGHT(tmp, field); \ 725 } \ 726 return (parent); \ 727} 728 729#define RB_NEGINF -1 730#define RB_INF 1 731 732#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 733#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 734#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 735#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 736#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 737#define RB_PREV(name, x, y) name##_RB_PREV(y) 738#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 739#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 740 741#define RB_FOREACH(x, name, head) \ 742 for ((x) = RB_MIN(name, head); \ 743 (x) != NULL; \ 744 (x) = name##_RB_NEXT(x)) 745 746#define RB_FOREACH_FROM(x, name, y) \ 747 for ((x) = (y); \ 748 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 749 (x) = (y)) 750 751#define RB_FOREACH_SAFE(x, name, head, y) \ 752 for ((x) = RB_MIN(name, head); \ 753 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 754 (x) = (y)) 755 756#define RB_FOREACH_REVERSE(x, name, head) \ 757 for ((x) = RB_MAX(name, head); \ 758 (x) != NULL; \ 759 (x) = name##_RB_PREV(x)) 760 761#define RB_FOREACH_REVERSE_FROM(x, name, y) \ 762 for ((x) = (y); \ 763 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 764 (x) = (y)) 765 766#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 767 for ((x) = RB_MAX(name, head); \ 768 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 769 (x) = (y)) 770 771#endif /* _SYS_TREE_H_ */ 772