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