1127664Sbms/* $NetBSD: tree.h,v 1.1.1.2 2017/01/31 21:14:53 christos Exp $ */ 2127664Sbms/* $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $ */ 3127664Sbms/* 4127664Sbms * Copyright 2002 Niels Provos <provos@citi.umich.edu> 5127664Sbms * All rights reserved. 6127664Sbms * 7127664Sbms * Redistribution and use in source and binary forms, with or without 8127664Sbms * modification, are permitted provided that the following conditions 9127664Sbms * are met: 10127664Sbms * 1. Redistributions of source code must retain the above copyright 11127664Sbms * notice, this list of conditions and the following disclaimer. 12127664Sbms * 2. Redistributions in binary form must reproduce the above copyright 13127664Sbms * notice, this list of conditions and the following disclaimer in the 14127664Sbms * documentation and/or other materials provided with the distribution. 15127664Sbms * 16127664Sbms * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17127664Sbms * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18127664Sbms * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19127664Sbms * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20127664Sbms * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21127664Sbms * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22127664Sbms * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23127664Sbms * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24127664Sbms * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25127664Sbms * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26127664Sbms */ 27127664Sbms 28127664Sbms#ifndef _SYS_TREE_H_ 29127664Sbms#define _SYS_TREE_H_ 30127664Sbms 31127664Sbms/* 32214518Srpaulo * This file defines data structures for different types of trees: 33127664Sbms * splay trees and red-black trees. 34127664Sbms * 35127664Sbms * A splay tree is a self-organizing data structure. Every operation 36127664Sbms * on the tree causes a splay to happen. The splay moves the requested 37127664Sbms * node to the root of the tree and partly rebalances it. 38190225Srpaulo * 39190225Srpaulo * This has the benefit that request locality causes faster lookups as 40190225Srpaulo * the requested nodes move to the top of the tree. On the other hand, 41190225Srpaulo * every lookup causes memory writes. 42190225Srpaulo * 43190225Srpaulo * The Balance Theorem bounds the total access time for m operations 44127664Sbms * and n inserts on an initially empty tree as O((m + n)lg n). The 45127664Sbms * amortized cost for a sequence of m accesses to a splay tree is O(lg n); 46127664Sbms * 47127664Sbms * A red-black tree is a binary search tree with the node color as an 48127664Sbms * extra attribute. It fulfills a set of conditions: 49127664Sbms * - every search path from the root to a leaf consists of the 50127664Sbms * same number of black nodes, 51127664Sbms * - each red node (except for the root) has a black parent, 52127664Sbms * - each leaf node is black. 53127664Sbms * 54127664Sbms * Every operation on a red-black tree is bounded as O(lg n). 55127664Sbms * The maximum height of a red-black tree is 2lg (n+1). 56127664Sbms */ 57127664Sbms 58127664Sbms#define SPLAY_HEAD(name, type) \ 59127664Sbmsstruct name { \ 60127664Sbms struct type *sph_root; /* root of the tree */ \ 61127664Sbms} 62127664Sbms 63127664Sbms#define SPLAY_INITIALIZER(root) \ 64127664Sbms { NULL } 65127664Sbms 66127664Sbms#define SPLAY_INIT(root) do { \ 67127664Sbms (root)->sph_root = NULL; \ 68127664Sbms} while (0) 69127664Sbms 70127664Sbms#define SPLAY_ENTRY(type) \ 71127664Sbmsstruct { \ 72127664Sbms struct type *spe_left; /* left element */ \ 73127664Sbms struct type *spe_right; /* right element */ \ 74127664Sbms} 75127664Sbms 76127664Sbms#define SPLAY_LEFT(elm, field) (elm)->field.spe_left 77127664Sbms#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 78127664Sbms#define SPLAY_ROOT(head) (head)->sph_root 79127664Sbms#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 80127664Sbms 81127664Sbms/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ 82127664Sbms#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 83127664Sbms SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 84127664Sbms SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 85127664Sbms (head)->sph_root = tmp; \ 86127664Sbms} while (0) 87127664Sbms 88#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 89 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 90 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 91 (head)->sph_root = tmp; \ 92} while (0) 93 94#define SPLAY_LINKLEFT(head, tmp, field) do { \ 95 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 96 tmp = (head)->sph_root; \ 97 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 98} while (0) 99 100#define SPLAY_LINKRIGHT(head, tmp, field) do { \ 101 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 102 tmp = (head)->sph_root; \ 103 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 104} while (0) 105 106#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 107 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 108 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ 109 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 110 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 111} while (0) 112 113/* Generates prototypes and inline functions */ 114 115#define SPLAY_PROTOTYPE(name, type, field, cmp) \ 116void name##_SPLAY(struct name *, struct type *); \ 117void name##_SPLAY_MINMAX(struct name *, int); \ 118struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 119struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 120 \ 121/* Finds the node with the same key as elm */ \ 122static __inline struct type * \ 123name##_SPLAY_FIND(struct name *head, struct type *elm) \ 124{ \ 125 if (SPLAY_EMPTY(head)) \ 126 return(NULL); \ 127 name##_SPLAY(head, elm); \ 128 if ((cmp)(elm, (head)->sph_root) == 0) \ 129 return (head->sph_root); \ 130 return (NULL); \ 131} \ 132 \ 133static __inline struct type * \ 134name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 135{ \ 136 name##_SPLAY(head, elm); \ 137 if (SPLAY_RIGHT(elm, field) != NULL) { \ 138 elm = SPLAY_RIGHT(elm, field); \ 139 while (SPLAY_LEFT(elm, field) != NULL) { \ 140 elm = SPLAY_LEFT(elm, field); \ 141 } \ 142 } else \ 143 elm = NULL; \ 144 return (elm); \ 145} \ 146 \ 147static __inline struct type * \ 148name##_SPLAY_MIN_MAX(struct name *head, int val) \ 149{ \ 150 name##_SPLAY_MINMAX(head, val); \ 151 return (SPLAY_ROOT(head)); \ 152} 153 154/* Main splay operation. 155 * Moves node close to the key of elm to top 156 */ 157#define SPLAY_GENERATE(name, type, field, cmp) \ 158struct type * \ 159name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 160{ \ 161 if (SPLAY_EMPTY(head)) { \ 162 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 163 } else { \ 164 int __comp; \ 165 name##_SPLAY(head, elm); \ 166 __comp = (cmp)(elm, (head)->sph_root); \ 167 if(__comp < 0) { \ 168 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ 169 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 170 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 171 } else if (__comp > 0) { \ 172 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ 173 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 174 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 175 } else \ 176 return ((head)->sph_root); \ 177 } \ 178 (head)->sph_root = (elm); \ 179 return (NULL); \ 180} \ 181 \ 182struct type * \ 183name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 184{ \ 185 struct type *__tmp; \ 186 if (SPLAY_EMPTY(head)) \ 187 return (NULL); \ 188 name##_SPLAY(head, elm); \ 189 if ((cmp)(elm, (head)->sph_root) == 0) { \ 190 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 191 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ 192 } else { \ 193 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 194 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ 195 name##_SPLAY(head, elm); \ 196 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 197 } \ 198 return (elm); \ 199 } \ 200 return (NULL); \ 201} \ 202 \ 203void \ 204name##_SPLAY(struct name *head, struct type *elm) \ 205{ \ 206 struct type __node, *__left, *__right, *__tmp; \ 207 int __comp; \ 208\ 209 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 210 __left = __right = &__node; \ 211\ 212 while ((__comp = (cmp)(elm, (head)->sph_root))) { \ 213 if (__comp < 0) { \ 214 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 215 if (__tmp == NULL) \ 216 break; \ 217 if ((cmp)(elm, __tmp) < 0){ \ 218 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 219 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 220 break; \ 221 } \ 222 SPLAY_LINKLEFT(head, __right, field); \ 223 } else if (__comp > 0) { \ 224 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 225 if (__tmp == NULL) \ 226 break; \ 227 if ((cmp)(elm, __tmp) > 0){ \ 228 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 229 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 230 break; \ 231 } \ 232 SPLAY_LINKRIGHT(head, __left, field); \ 233 } \ 234 } \ 235 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 236} \ 237 \ 238/* Splay with either the minimum or the maximum element \ 239 * Used to find minimum or maximum element in tree. \ 240 */ \ 241void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 242{ \ 243 struct type __node, *__left, *__right, *__tmp; \ 244\ 245 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ 246 __left = __right = &__node; \ 247\ 248 while (1) { \ 249 if (__comp < 0) { \ 250 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 251 if (__tmp == NULL) \ 252 break; \ 253 if (__comp < 0){ \ 254 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 255 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ 256 break; \ 257 } \ 258 SPLAY_LINKLEFT(head, __right, field); \ 259 } else if (__comp > 0) { \ 260 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 261 if (__tmp == NULL) \ 262 break; \ 263 if (__comp > 0) { \ 264 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 265 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ 266 break; \ 267 } \ 268 SPLAY_LINKRIGHT(head, __left, field); \ 269 } \ 270 } \ 271 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 272} 273 274#define SPLAY_NEGINF -1 275#define SPLAY_INF 1 276 277#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 278#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 279#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 280#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 281#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 282 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 283#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 284 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 285 286#define SPLAY_FOREACH(x, name, head) \ 287 for ((x) = SPLAY_MIN(name, head); \ 288 (x) != NULL; \ 289 (x) = SPLAY_NEXT(name, head, x)) 290 291/* Macros that define a red-back tree */ 292#define RB_HEAD(name, type) \ 293struct name { \ 294 struct type *rbh_root; /* root of the tree */ \ 295} 296 297#define RB_INITIALIZER(root) \ 298 { NULL } 299 300#define RB_INIT(root) do { \ 301 (root)->rbh_root = NULL; \ 302} while (0) 303 304#define RB_BLACK 0 305#define RB_RED 1 306#define RB_ENTRY(type) \ 307struct { \ 308 struct type *rbe_left; /* left element */ \ 309 struct type *rbe_right; /* right element */ \ 310 struct type *rbe_parent; /* parent element */ \ 311 int rbe_color; /* node color */ \ 312} 313 314#define RB_LEFT(elm, field) (elm)->field.rbe_left 315#define RB_RIGHT(elm, field) (elm)->field.rbe_right 316#define RB_PARENT(elm, field) (elm)->field.rbe_parent 317#define RB_COLOR(elm, field) (elm)->field.rbe_color 318#define RB_ROOT(head) (head)->rbh_root 319#define RB_EMPTY(head) (RB_ROOT(head) == NULL) 320 321#define RB_SET(elm, parent, field) do { \ 322 RB_PARENT(elm, field) = parent; \ 323 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 324 RB_COLOR(elm, field) = RB_RED; \ 325} while (0) 326 327#define RB_SET_BLACKRED(black, red, field) do { \ 328 RB_COLOR(black, field) = RB_BLACK; \ 329 RB_COLOR(red, field) = RB_RED; \ 330} while (0) 331 332#ifndef RB_AUGMENT 333#define RB_AUGMENT(x) 334#endif 335 336#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 337 (tmp) = RB_RIGHT(elm, field); \ 338 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ 339 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 340 } \ 341 RB_AUGMENT(elm); \ 342 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 343 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 344 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 345 else \ 346 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 347 } else \ 348 (head)->rbh_root = (tmp); \ 349 RB_LEFT(tmp, field) = (elm); \ 350 RB_PARENT(elm, field) = (tmp); \ 351 RB_AUGMENT(tmp); \ 352 if ((RB_PARENT(tmp, field))) \ 353 RB_AUGMENT(RB_PARENT(tmp, field)); \ 354} while (0) 355 356#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 357 (tmp) = RB_LEFT(elm, field); \ 358 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ 359 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 360 } \ 361 RB_AUGMENT(elm); \ 362 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ 363 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 364 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 365 else \ 366 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 367 } else \ 368 (head)->rbh_root = (tmp); \ 369 RB_RIGHT(tmp, field) = (elm); \ 370 RB_PARENT(elm, field) = (tmp); \ 371 RB_AUGMENT(tmp); \ 372 if ((RB_PARENT(tmp, field))) \ 373 RB_AUGMENT(RB_PARENT(tmp, field)); \ 374} while (0) 375 376/* Generates prototypes and inline functions */ 377#define RB_PROTOTYPE(name, type, field, cmp) \ 378void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 379void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 380struct type *name##_RB_REMOVE(struct name *, struct type *); \ 381struct type *name##_RB_INSERT(struct name *, struct type *); \ 382struct type *name##_RB_FIND(struct name *, struct type *); \ 383struct type *name##_RB_NEXT(struct type *); \ 384struct type *name##_RB_MINMAX(struct name *, int); \ 385 \ 386 387/* Main rb operation. 388 * Moves node close to the key of elm to top 389 */ 390#define RB_GENERATE(name, type, field, cmp) \ 391void \ 392name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 393{ \ 394 struct type *parent, *gparent, *tmp; \ 395 while ((parent = RB_PARENT(elm, field)) && \ 396 RB_COLOR(parent, field) == RB_RED) { \ 397 gparent = RB_PARENT(parent, field); \ 398 if (parent == RB_LEFT(gparent, field)) { \ 399 tmp = RB_RIGHT(gparent, field); \ 400 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 401 RB_COLOR(tmp, field) = RB_BLACK; \ 402 RB_SET_BLACKRED(parent, gparent, field);\ 403 elm = gparent; \ 404 continue; \ 405 } \ 406 if (RB_RIGHT(parent, field) == elm) { \ 407 RB_ROTATE_LEFT(head, parent, tmp, field);\ 408 tmp = parent; \ 409 parent = elm; \ 410 elm = tmp; \ 411 } \ 412 RB_SET_BLACKRED(parent, gparent, field); \ 413 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 414 } else { \ 415 tmp = RB_LEFT(gparent, field); \ 416 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 417 RB_COLOR(tmp, field) = RB_BLACK; \ 418 RB_SET_BLACKRED(parent, gparent, field);\ 419 elm = gparent; \ 420 continue; \ 421 } \ 422 if (RB_LEFT(parent, field) == elm) { \ 423 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 424 tmp = parent; \ 425 parent = elm; \ 426 elm = tmp; \ 427 } \ 428 RB_SET_BLACKRED(parent, gparent, field); \ 429 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 430 } \ 431 } \ 432 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 433} \ 434 \ 435void \ 436name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ 437{ \ 438 struct type *tmp; \ 439 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 440 elm != RB_ROOT(head)) { \ 441 if (RB_LEFT(parent, field) == elm) { \ 442 tmp = RB_RIGHT(parent, field); \ 443 if (RB_COLOR(tmp, field) == RB_RED) { \ 444 RB_SET_BLACKRED(tmp, parent, field); \ 445 RB_ROTATE_LEFT(head, parent, tmp, field);\ 446 tmp = RB_RIGHT(parent, field); \ 447 } \ 448 if ((RB_LEFT(tmp, field) == NULL || \ 449 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 450 (RB_RIGHT(tmp, field) == NULL || \ 451 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 452 RB_COLOR(tmp, field) = RB_RED; \ 453 elm = parent; \ 454 parent = RB_PARENT(elm, field); \ 455 } else { \ 456 if (RB_RIGHT(tmp, field) == NULL || \ 457 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ 458 struct type *oleft; \ 459 if ((oleft = RB_LEFT(tmp, field)))\ 460 RB_COLOR(oleft, field) = RB_BLACK;\ 461 RB_COLOR(tmp, field) = RB_RED; \ 462 RB_ROTATE_RIGHT(head, tmp, oleft, field);\ 463 tmp = RB_RIGHT(parent, field); \ 464 } \ 465 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 466 RB_COLOR(parent, field) = RB_BLACK; \ 467 if (RB_RIGHT(tmp, field)) \ 468 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ 469 RB_ROTATE_LEFT(head, parent, tmp, field);\ 470 elm = RB_ROOT(head); \ 471 break; \ 472 } \ 473 } else { \ 474 tmp = RB_LEFT(parent, field); \ 475 if (RB_COLOR(tmp, field) == RB_RED) { \ 476 RB_SET_BLACKRED(tmp, parent, field); \ 477 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 478 tmp = RB_LEFT(parent, field); \ 479 } \ 480 if ((RB_LEFT(tmp, field) == NULL || \ 481 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ 482 (RB_RIGHT(tmp, field) == NULL || \ 483 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ 484 RB_COLOR(tmp, field) = RB_RED; \ 485 elm = parent; \ 486 parent = RB_PARENT(elm, field); \ 487 } else { \ 488 if (RB_LEFT(tmp, field) == NULL || \ 489 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ 490 struct type *oright; \ 491 if ((oright = RB_RIGHT(tmp, field)))\ 492 RB_COLOR(oright, field) = RB_BLACK;\ 493 RB_COLOR(tmp, field) = RB_RED; \ 494 RB_ROTATE_LEFT(head, tmp, oright, field);\ 495 tmp = RB_LEFT(parent, field); \ 496 } \ 497 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ 498 RB_COLOR(parent, field) = RB_BLACK; \ 499 if (RB_LEFT(tmp, field)) \ 500 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ 501 RB_ROTATE_RIGHT(head, parent, tmp, field);\ 502 elm = RB_ROOT(head); \ 503 break; \ 504 } \ 505 } \ 506 } \ 507 if (elm) \ 508 RB_COLOR(elm, field) = RB_BLACK; \ 509} \ 510 \ 511struct type * \ 512name##_RB_REMOVE(struct name *head, struct type *elm) \ 513{ \ 514 struct type *child, *parent, *old = elm; \ 515 int color; \ 516 if (RB_LEFT(elm, field) == NULL) \ 517 child = RB_RIGHT(elm, field); \ 518 else if (RB_RIGHT(elm, field) == NULL) \ 519 child = RB_LEFT(elm, field); \ 520 else { \ 521 struct type *left; \ 522 elm = RB_RIGHT(elm, field); \ 523 while ((left = RB_LEFT(elm, field))) \ 524 elm = left; \ 525 child = RB_RIGHT(elm, field); \ 526 parent = RB_PARENT(elm, field); \ 527 color = RB_COLOR(elm, field); \ 528 if (child) \ 529 RB_PARENT(child, field) = parent; \ 530 if (parent) { \ 531 if (RB_LEFT(parent, field) == elm) \ 532 RB_LEFT(parent, field) = child; \ 533 else \ 534 RB_RIGHT(parent, field) = child; \ 535 RB_AUGMENT(parent); \ 536 } else \ 537 RB_ROOT(head) = child; \ 538 if (RB_PARENT(elm, field) == old) \ 539 parent = elm; \ 540 (elm)->field = (old)->field; \ 541 if (RB_PARENT(old, field)) { \ 542 if (RB_LEFT(RB_PARENT(old, field), field) == old)\ 543 RB_LEFT(RB_PARENT(old, field), field) = elm;\ 544 else \ 545 RB_RIGHT(RB_PARENT(old, field), field) = elm;\ 546 RB_AUGMENT(RB_PARENT(old, field)); \ 547 } else \ 548 RB_ROOT(head) = elm; \ 549 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 550 if (RB_RIGHT(old, field)) \ 551 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 552 if (parent) { \ 553 left = parent; \ 554 do { \ 555 RB_AUGMENT(left); \ 556 } while ((left = RB_PARENT(left, field))); \ 557 } \ 558 goto color; \ 559 } \ 560 parent = RB_PARENT(elm, field); \ 561 color = RB_COLOR(elm, field); \ 562 if (child) \ 563 RB_PARENT(child, field) = parent; \ 564 if (parent) { \ 565 if (RB_LEFT(parent, field) == elm) \ 566 RB_LEFT(parent, field) = child; \ 567 else \ 568 RB_RIGHT(parent, field) = child; \ 569 RB_AUGMENT(parent); \ 570 } else \ 571 RB_ROOT(head) = child; \ 572color: \ 573 if (color == RB_BLACK) \ 574 name##_RB_REMOVE_COLOR(head, parent, child); \ 575 return (old); \ 576} \ 577 \ 578/* Inserts a node into the RB tree */ \ 579struct type * \ 580name##_RB_INSERT(struct name *head, struct type *elm) \ 581{ \ 582 struct type *tmp; \ 583 struct type *parent = NULL; \ 584 int comp = 0; \ 585 tmp = RB_ROOT(head); \ 586 while (tmp) { \ 587 parent = tmp; \ 588 comp = (cmp)(elm, parent); \ 589 if (comp < 0) \ 590 tmp = RB_LEFT(tmp, field); \ 591 else if (comp > 0) \ 592 tmp = RB_RIGHT(tmp, field); \ 593 else \ 594 return (tmp); \ 595 } \ 596 RB_SET(elm, parent, field); \ 597 if (parent != NULL) { \ 598 if (comp < 0) \ 599 RB_LEFT(parent, field) = elm; \ 600 else \ 601 RB_RIGHT(parent, field) = elm; \ 602 RB_AUGMENT(parent); \ 603 } else \ 604 RB_ROOT(head) = elm; \ 605 name##_RB_INSERT_COLOR(head, elm); \ 606 return (NULL); \ 607} \ 608 \ 609/* Finds the node with the same key as elm */ \ 610struct type * \ 611name##_RB_FIND(struct name *head, struct type *elm) \ 612{ \ 613 struct type *tmp = RB_ROOT(head); \ 614 int comp; \ 615 while (tmp) { \ 616 comp = cmp(elm, tmp); \ 617 if (comp < 0) \ 618 tmp = RB_LEFT(tmp, field); \ 619 else if (comp > 0) \ 620 tmp = RB_RIGHT(tmp, field); \ 621 else \ 622 return (tmp); \ 623 } \ 624 return (NULL); \ 625} \ 626 \ 627struct type * \ 628name##_RB_NEXT(struct type *elm) \ 629{ \ 630 if (RB_RIGHT(elm, field)) { \ 631 elm = RB_RIGHT(elm, field); \ 632 while (RB_LEFT(elm, field)) \ 633 elm = RB_LEFT(elm, field); \ 634 } else { \ 635 if (RB_PARENT(elm, field) && \ 636 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 637 elm = RB_PARENT(elm, field); \ 638 else { \ 639 while (RB_PARENT(elm, field) && \ 640 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ 641 elm = RB_PARENT(elm, field); \ 642 elm = RB_PARENT(elm, field); \ 643 } \ 644 } \ 645 return (elm); \ 646} \ 647 \ 648struct type * \ 649name##_RB_MINMAX(struct name *head, int val) \ 650{ \ 651 struct type *tmp = RB_ROOT(head); \ 652 struct type *parent = NULL; \ 653 while (tmp) { \ 654 parent = tmp; \ 655 if (val < 0) \ 656 tmp = RB_LEFT(tmp, field); \ 657 else \ 658 tmp = RB_RIGHT(tmp, field); \ 659 } \ 660 return (parent); \ 661} 662 663#define RB_NEGINF -1 664#define RB_INF 1 665 666#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 667#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 668#define RB_FIND(name, x, y) name##_RB_FIND(x, y) 669#define RB_NEXT(name, x, y) name##_RB_NEXT(y) 670#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 671#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 672 673#define RB_FOREACH(x, name, head) \ 674 for ((x) = RB_MIN(name, head); \ 675 (x) != NULL; \ 676 (x) = name##_RB_NEXT(x)) 677 678#endif /* _SYS_TREE_H_ */ 679