bsd/sys/tree.h

   1 /*
   2  * Copyright (c) 2008 Apple Computer, 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 _SYS_TREE_H_
  57 #define _SYS_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_ENTRY(type)                                                  \
 335 struct {                                                                \
 336         struct type *rbe_left;          /* left element */              \
 337         struct type *rbe_right;         /* right element */             \
 338         struct type *rbe_parent;        /* parent element */            \
 339         int rbe_color;                  /* node color */                \
 340 }
 341
 342 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
 343 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
 344 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
 345 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
 346 #define RB_ROOT(head)                   (head)->rbh_root
 347 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 348
 349 #define RB_SET(elm, parent, field) do {                                 \
 350         RB_PARENT(elm, field) = parent;                                 \
 351         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
 352         RB_COLOR(elm, field) = RB_RED;                                  \
 353 } while (/*CONSTCOND*/ 0)
 354
 355 #define RB_SET_BLACKRED(black, red, field) do {                         \
 356         RB_COLOR(black, field) = RB_BLACK;                              \
 357         RB_COLOR(red, field) = 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(head, elm, tmp, field) do {                      \
 365         (tmp) = RB_RIGHT(elm, field);                                   \
 366         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
 367                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
 368         }                                                               \
 369         RB_AUGMENT(elm);                                                \
 370         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
 371                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 372                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 373                 else                                                    \
 374                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 375         } else                                                          \
 376                 (head)->rbh_root = (tmp);                               \
 377         RB_LEFT(tmp, field) = (elm);                                    \
 378         RB_PARENT(elm, field) = (tmp);                                  \
 379         RB_AUGMENT(tmp);                                                \
 380         if ((RB_PARENT(tmp, field)))                                    \
 381                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
 382 } while (/*CONSTCOND*/ 0)
 383
 384 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
 385         (tmp) = RB_LEFT(elm, field);                                    \
 386         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
 387                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
 388         }                                                               \
 389         RB_AUGMENT(elm);                                                \
 390         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
 391                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 392                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 393                 else                                                    \
 394                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 395         } else                                                          \
 396                 (head)->rbh_root = (tmp);                               \
 397         RB_RIGHT(tmp, field) = (elm);                                   \
 398         RB_PARENT(elm, field) = (tmp);                                  \
 399         RB_AUGMENT(tmp);                                                \
 400         if ((RB_PARENT(tmp, field)))                                    \
 401                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
 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
 414 /* Generates prototypes (with storage class) and inline functions */
 415 #define RB_PROTOTYPE_SC(_sc_, name, type, field, cmp)                   \
 416 _sc_ void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
 417 _sc_ void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *); \
 418 _sc_ struct type *name##_RB_REMOVE(struct name *, struct type *);       \
 419 _sc_ struct type *name##_RB_INSERT(struct name *, struct type *);       \
 420 _sc_ struct type *name##_RB_FIND(struct name *, struct type *);         \
 421 _sc_ struct type *name##_RB_NEXT(struct type *);                        \
 422 _sc_ struct type *name##_RB_MINMAX(struct name *, int);
 423
 424 /* Main rb operation.
 425  * Moves node close to the key of elm to top
 426  */
 427 #define RB_GENERATE(name, type, field, cmp)                             \
 428 void                                                                    \
 429 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
 430 {                                                                       \
 431         struct type *parent, *gparent, *tmp;                            \
 432         while ((parent = RB_PARENT(elm, field)) != NULL &&              \
 433             RB_COLOR(parent, field) == RB_RED) {                        \
 434                 gparent = RB_PARENT(parent, field);                     \
 435                 if (parent == RB_LEFT(gparent, field)) {                \
 436                         tmp = RB_RIGHT(gparent, field);                 \
 437                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 438                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 439                                 RB_SET_BLACKRED(parent, gparent, field);\
 440                                 elm = gparent;                          \
 441                                 continue;                               \
 442                         }                                               \
 443                         if (RB_RIGHT(parent, field) == elm) {           \
 444                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 445                                 tmp = parent;                           \
 446                                 parent = elm;                           \
 447                                 elm = tmp;                              \
 448                         }                                               \
 449                         RB_SET_BLACKRED(parent, gparent, field);        \
 450                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
 451                 } else {                                                \
 452                         tmp = RB_LEFT(gparent, field);                  \
 453                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 454                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 455                                 RB_SET_BLACKRED(parent, gparent, field);\
 456                                 elm = gparent;                          \
 457                                 continue;                               \
 458                         }                                               \
 459                         if (RB_LEFT(parent, field) == elm) {            \
 460                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 461                                 tmp = parent;                           \
 462                                 parent = elm;                           \
 463                                 elm = tmp;                              \
 464                         }                                               \
 465                         RB_SET_BLACKRED(parent, gparent, field);        \
 466                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
 467                 }                                                       \
 468         }                                                               \
 469         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
 470 }                                                                       \
 471                                                                         \
 472 void                                                                    \
 473 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 474 {                                                                       \
 475         struct type *tmp;                                               \
 476         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
 477             elm != RB_ROOT(head)) {                                     \
 478                 if (RB_LEFT(parent, field) == elm) {                    \
 479                         tmp = RB_RIGHT(parent, field);                  \
 480                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 481                                 RB_SET_BLACKRED(tmp, parent, field);    \
 482                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 483                                 tmp = RB_RIGHT(parent, field);          \
 484                         }                                               \
 485                         if ((RB_LEFT(tmp, field) == NULL ||             \
 486                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 487                             (RB_RIGHT(tmp, field) == NULL ||            \
 488                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 489                                 RB_COLOR(tmp, field) = RB_RED;          \
 490                                 elm = parent;                           \
 491                                 parent = RB_PARENT(elm, field);         \
 492                         } else {                                        \
 493                                 if (RB_RIGHT(tmp, field) == NULL ||     \
 494                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
 495                                         struct type *oleft;             \
 496                                         if ((oleft = RB_LEFT(tmp, field)) \
 497                                             != NULL)                    \
 498                                                 RB_COLOR(oleft, field) = RB_BLACK;\
 499                                         RB_COLOR(tmp, field) = RB_RED;  \
 500                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
 501                                         tmp = RB_RIGHT(parent, field);  \
 502                                 }                                       \
 503                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 504                                 RB_COLOR(parent, field) = RB_BLACK;     \
 505                                 if (RB_RIGHT(tmp, field))               \
 506                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
 507                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 508                                 elm = RB_ROOT(head);                    \
 509                                 break;                                  \
 510                         }                                               \
 511                 } else {                                                \
 512                         tmp = RB_LEFT(parent, field);                   \
 513                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 514                                 RB_SET_BLACKRED(tmp, parent, field);    \
 515                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 516                                 tmp = RB_LEFT(parent, field);           \
 517                         }                                               \
 518                         if ((RB_LEFT(tmp, field) == NULL ||             \
 519                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 520                             (RB_RIGHT(tmp, field) == NULL ||            \
 521                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 522                                 RB_COLOR(tmp, field) = RB_RED;          \
 523                                 elm = parent;                           \
 524                                 parent = RB_PARENT(elm, field);         \
 525                         } else {                                        \
 526                                 if (RB_LEFT(tmp, field) == NULL ||      \
 527                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
 528                                         struct type *oright;            \
 529                                         if ((oright = RB_RIGHT(tmp, field)) \
 530                                             != NULL)                    \
 531                                                 RB_COLOR(oright, field) = RB_BLACK;\
 532                                         RB_COLOR(tmp, field) = RB_RED;  \
 533                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
 534                                         tmp = RB_LEFT(parent, field);   \
 535                                 }                                       \
 536                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 537                                 RB_COLOR(parent, field) = RB_BLACK;     \
 538                                 if (RB_LEFT(tmp, field))                \
 539                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
 540                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 541                                 elm = RB_ROOT(head);                    \
 542                                 break;                                  \
 543                         }                                               \
 544                 }                                                       \
 545         }                                                               \
 546         if (elm)                                                        \
 547                 RB_COLOR(elm, field) = RB_BLACK;                        \
 548 }                                                                       \
 549                                                                         \
 550 struct type *                                                           \
 551 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
 552 {                                                                       \
 553         struct type *child, *parent, *old = elm;                        \
 554         int color;                                                      \
 555         if (RB_LEFT(elm, field) == NULL)                                \
 556                 child = RB_RIGHT(elm, field);                           \
 557         else if (RB_RIGHT(elm, field) == NULL)                          \
 558                 child = RB_LEFT(elm, field);                            \
 559         else {                                                          \
 560                 struct type *left;                                      \
 561                 elm = RB_RIGHT(elm, field);                             \
 562                 while ((left = RB_LEFT(elm, field)) != NULL)            \
 563                         elm = left;                                     \
 564                 child = RB_RIGHT(elm, field);                           \
 565                 parent = RB_PARENT(elm, field);                         \
 566                 color = RB_COLOR(elm, field);                           \
 567                 if (child)                                              \
 568                         RB_PARENT(child, field) = parent;               \
 569                 if (parent) {                                           \
 570                         if (RB_LEFT(parent, field) == elm)              \
 571                                 RB_LEFT(parent, field) = child;         \
 572                         else                                            \
 573                                 RB_RIGHT(parent, field) = child;        \
 574                         RB_AUGMENT(parent);                             \
 575                 } else                                                  \
 576                         RB_ROOT(head) = child;                          \
 577                 if (RB_PARENT(elm, field) == old)                       \
 578                         parent = elm;                                   \
 579                 (elm)->field = (old)->field;                            \
 580                 if (RB_PARENT(old, field)) {                            \
 581                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
 582                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
 583                         else                                            \
 584                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
 585                         RB_AUGMENT(RB_PARENT(old, field));              \
 586                 } else                                                  \
 587                         RB_ROOT(head) = elm;                            \
 588                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
 589                 if (RB_RIGHT(old, field))                               \
 590                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
 591                 if (parent) {                                           \
 592                         left = parent;                                  \
 593                         do {                                            \
 594                                 RB_AUGMENT(left);                       \
 595                         } while ((left = RB_PARENT(left, field)) != NULL); \
 596                 }                                                       \
 597                 goto color;                                             \
 598         }                                                               \
 599         parent = RB_PARENT(elm, field);                                 \
 600         color = RB_COLOR(elm, field);                                   \
 601         if (child)                                                      \
 602                 RB_PARENT(child, field) = parent;                       \
 603         if (parent) {                                                   \
 604                 if (RB_LEFT(parent, field) == elm)                      \
 605                         RB_LEFT(parent, field) = child;                 \
 606                 else                                                    \
 607                         RB_RIGHT(parent, field) = child;                \
 608                 RB_AUGMENT(parent);                                     \
 609         } else                                                          \
 610                 RB_ROOT(head) = child;                                  \
 611 color:                                                                  \
 612         if (color == RB_BLACK)                                          \
 613                 name##_RB_REMOVE_COLOR(head, parent, child);            \
 614         return (old);                                                   \
 615 }                                                                       \
 616                                                                         \
 617 /* Inserts a node into the RB tree */                                   \
 618 struct type *                                                           \
 619 name##_RB_INSERT(struct name *head, struct type *elm)                   \
 620 {                                                                       \
 621         struct type *tmp;                                               \
 622         struct type *parent = NULL;                                     \
 623         int comp = 0;                                                   \
 624         tmp = RB_ROOT(head);                                            \
 625         while (tmp) {                                                   \
 626                 parent = tmp;                                           \
 627                 comp = (cmp)(elm, parent);                              \
 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         RB_SET(elm, parent, field);                                     \
 636         if (parent != NULL) {                                           \
 637                 if (comp < 0)                                           \
 638                         RB_LEFT(parent, field) = elm;                   \
 639                 else                                                    \
 640                         RB_RIGHT(parent, field) = elm;                  \
 641                 RB_AUGMENT(parent);                                     \
 642         } else                                                          \
 643                 RB_ROOT(head) = elm;                                    \
 644         name##_RB_INSERT_COLOR(head, elm);                              \
 645         return (NULL);                                                  \
 646 }                                                                       \
 647                                                                         \
 648 /* Finds the node with the same key as elm */                           \
 649 struct type *                                                           \
 650 name##_RB_FIND(struct name *head, struct type *elm)                     \
 651 {                                                                       \
 652         struct type *tmp = RB_ROOT(head);                               \
 653         int comp;                                                       \
 654         while (tmp) {                                                   \
 655                 comp = cmp(elm, tmp);                                   \
 656                 if (comp < 0)                                           \
 657                         tmp = RB_LEFT(tmp, field);                      \
 658                 else if (comp > 0)                                      \
 659                         tmp = RB_RIGHT(tmp, field);                     \
 660                 else                                                    \
 661                         return (tmp);                                   \
 662         }                                                               \
 663         return (NULL);                                                  \
 664 }                                                                       \
 665                                                                         \
 666 /* ARGSUSED */                                                          \
 667 struct type *                                                           \
 668 name##_RB_NEXT(struct type *elm)                                        \
 669 {                                                                       \
 670         if (RB_RIGHT(elm, field)) {                                     \
 671                 elm = RB_RIGHT(elm, field);                             \
 672                 while (RB_LEFT(elm, field))                             \
 673                         elm = RB_LEFT(elm, field);                      \
 674         } else {                                                        \
 675                 if (RB_PARENT(elm, field) &&                            \
 676                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
 677                         elm = RB_PARENT(elm, field);                    \
 678                 else {                                                  \
 679                         while (RB_PARENT(elm, field) &&                 \
 680                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
 681                                 elm = RB_PARENT(elm, field);            \
 682                         elm = RB_PARENT(elm, field);                    \
 683                 }                                                       \
 684         }                                                               \
 685         return (elm);                                                   \
 686 }                                                                       \
 687                                                                         \
 688 struct type *                                                           \
 689 name##_RB_MINMAX(struct name *head, int val)                            \
 690 {                                                                       \
 691         struct type *tmp = RB_ROOT(head);                               \
 692         struct type *parent = NULL;                                     \
 693         while (tmp) {                                                   \
 694                 parent = tmp;                                           \
 695                 if (val < 0)                                            \
 696                         tmp = RB_LEFT(tmp, field);                      \
 697                 else                                                    \
 698                         tmp = RB_RIGHT(tmp, field);                     \
 699         }                                                               \
 700         return (parent);                                                \
 701 }
 702
 703 #define RB_NEGINF       -1
 704 #define RB_INF  1
 705
 706 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
 707 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
 708 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
 709 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
 710 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
 711 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
 712
 713 #define RB_FOREACH(x, name, head)                                       \
 714         for ((x) = RB_MIN(name, head);                                  \
 715              (x) != NULL;                                               \
 716              (x) = name##_RB_NEXT(x))
 717
 718 #endif  /* _SYS_TREE_H_ */