sys/sys/tree.h

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