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 /*      $DragonFly: src/sys/sys/tree.h,v 1.11 2008/01/07 01:22:30 corecode Exp $ */
   4 /*
   5  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #ifndef _SYS_TREE_H_
  30 #define _SYS_TREE_H_
  31
  32 /*
  33  * This file defines data structures for different types of trees:
  34  * splay trees and red-black trees.
  35  *
  36  * A splay tree is a self-organizing data structure.  Every operation
  37  * on the tree causes a splay to happen.  The splay moves the requested
  38  * node to the root of the tree and partly rebalances it.
  39  *
  40  * This has the benefit that request locality causes faster lookups as
  41  * the requested nodes move to the top of the tree.  On the other hand,
  42  * every lookup causes memory writes.
  43  *
  44  * The Balance Theorem bounds the total access time for m operations
  45  * and n inserts on an initially empty tree as O((m + n)lg n).  The
  46  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  47  *
  48  * A red-black tree is a binary search tree with the node color as an
  49  * extra attribute.  It fulfills a set of conditions:
  50  *      - every search path from the root to a leaf consists of the
  51  *        same number of black nodes,
  52  *      - each red node (except for the root) has a black parent,
  53  *      - each leaf node is black.
  54  *
  55  * Every operation on a red-black tree is bounded as O(lg n).
  56  * The maximum height of a red-black tree is 2lg (n+1).
  57  */
  58
  59 #define SPLAY_HEAD(name, type)                                          \
  60 struct name {                                                           \
  61         struct type *sph_root; /* root of the tree */                   \
  62 }
  63
  64 #define SPLAY_INITIALIZER(root)                                         \
  65         { NULL }
  66
  67 #define SPLAY_INIT(root) do {                                           \
  68         (root)->sph_root = NULL;                                        \
  69 } while (/*CONSTCOND*/ 0)
  70
  71 #define SPLAY_ENTRY(type)                                               \
  72 struct {                                                                \
  73         struct type *spe_left; /* left element */                       \
  74         struct type *spe_right; /* right element */                     \
  75 }
  76
  77 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
  78 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
  79 #define SPLAY_ROOT(head)                (head)->sph_root
  80 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
  81
  82 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  83 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
  84         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
  85         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
  86         (head)->sph_root = tmp;                                         \
  87 } while (/*CONSTCOND*/ 0)
  88
  89 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
  90         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
  91         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
  92         (head)->sph_root = tmp;                                         \
  93 } while (/*CONSTCOND*/ 0)
  94
  95 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
  96         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
  97         tmp = (head)->sph_root;                                         \
  98         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
  99 } while (/*CONSTCOND*/ 0)
 100
 101 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
 102         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 103         tmp = (head)->sph_root;                                         \
 104         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
 105 } while (/*CONSTCOND*/ 0)
 106
 107 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
 108         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
 109         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
 110         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
 111         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
 112 } while (/*CONSTCOND*/ 0)
 113
 114 /* Generates prototypes and inline functions */
 115
 116 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
 117 void name##_SPLAY(struct name *, struct type *);                        \
 118 void name##_SPLAY_MINMAX(struct name *, int);                           \
 119 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
 120 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
 121                                                                         \
 122 /* Finds the node with the same key as elm */                           \
 123 static __inline struct type *                                           \
 124 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
 125 {                                                                       \
 126         if (SPLAY_EMPTY(head))                                          \
 127                 return(NULL);                                           \
 128         name##_SPLAY(head, elm);                                        \
 129         if ((cmp)(elm, (head)->sph_root) == 0)                          \
 130                 return (head->sph_root);                                \
 131         return (NULL);                                                  \
 132 }                                                                       \
 133                                                                         \
 134 static __inline struct type *                                           \
 135 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
 136 {                                                                       \
 137         name##_SPLAY(head, elm);                                        \
 138         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
 139                 elm = SPLAY_RIGHT(elm, field);                          \
 140                 while (SPLAY_LEFT(elm, field) != NULL) {                \
 141                         elm = SPLAY_LEFT(elm, field);                   \
 142                 }                                                       \
 143         } else                                                          \
 144                 elm = NULL;                                             \
 145         return (elm);                                                   \
 146 }                                                                       \
 147                                                                         \
 148 static __inline struct type *                                           \
 149 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
 150 {                                                                       \
 151         name##_SPLAY_MINMAX(head, val);                                 \
 152         return (SPLAY_ROOT(head));                                      \
 153 }
 154
 155 /* Main splay operation.
 156  * Moves node close to the key of elm to top
 157  */
 158 #define SPLAY_GENERATE(name, type, field, cmp)                          \
 159 struct type *                                                           \
 160 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
 161 {                                                                       \
 162     if (SPLAY_EMPTY(head)) {                                            \
 163             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
 164     } else {                                                            \
 165             int __comp;                                                 \
 166             name##_SPLAY(head, elm);                                    \
 167             __comp = (cmp)(elm, (head)->sph_root);                      \
 168             if(__comp < 0) {                                            \
 169                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
 170                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
 171                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
 172             } else if (__comp > 0) {                                    \
 173                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
 174                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
 175                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
 176             } else                                                      \
 177                     return ((head)->sph_root);                          \
 178     }                                                                   \
 179     (head)->sph_root = (elm);                                           \
 180     return (NULL);                                                      \
 181 }                                                                       \
 182                                                                         \
 183 struct type *                                                           \
 184 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
 185 {                                                                       \
 186         struct type *__tmp;                                             \
 187         if (SPLAY_EMPTY(head))                                          \
 188                 return (NULL);                                          \
 189         name##_SPLAY(head, elm);                                        \
 190         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
 191                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
 192                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
 193                 } else {                                                \
 194                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 195                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
 196                         name##_SPLAY(head, elm);                        \
 197                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
 198                 }                                                       \
 199                 return (elm);                                           \
 200         }                                                               \
 201         return (NULL);                                                  \
 202 }                                                                       \
 203                                                                         \
 204 void                                                                    \
 205 name##_SPLAY(struct name *head, struct type *elm)                       \
 206 {                                                                       \
 207         struct type __node, *__left, *__right, *__tmp;                  \
 208         int __comp;                                                     \
 209 \
 210         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 211         __left = __right = &__node;                                     \
 212 \
 213         while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
 214                 if (__comp < 0) {                                       \
 215                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 216                         if (__tmp == NULL)                              \
 217                                 break;                                  \
 218                         if ((cmp)(elm, __tmp) < 0){                     \
 219                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 220                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 221                                         break;                          \
 222                         }                                               \
 223                         SPLAY_LINKLEFT(head, __right, field);           \
 224                 } else if (__comp > 0) {                                \
 225                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 226                         if (__tmp == NULL)                              \
 227                                 break;                                  \
 228                         if ((cmp)(elm, __tmp) > 0){                     \
 229                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 230                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 231                                         break;                          \
 232                         }                                               \
 233                         SPLAY_LINKRIGHT(head, __left, field);           \
 234                 }                                                       \
 235         }                                                               \
 236         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 237 }                                                                       \
 238                                                                         \
 239 /* Splay with either the minimum or the maximum element                 \
 240  * Used to find minimum or maximum element in tree.                     \
 241  */                                                                     \
 242 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 243 {                                                                       \
 244         struct type __node, *__left, *__right, *__tmp;                  \
 245 \
 246         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 247         __left = __right = &__node;                                     \
 248 \
 249         while (1) {                                                     \
 250                 if (__comp < 0) {                                       \
 251                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 252                         if (__tmp == NULL)                              \
 253                                 break;                                  \
 254                         if (__comp < 0){                                \
 255                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 256                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 257                                         break;                          \
 258                         }                                               \
 259                         SPLAY_LINKLEFT(head, __right, field);           \
 260                 } else if (__comp > 0) {                                \
 261                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 262                         if (__tmp == NULL)                              \
 263                                 break;                                  \
 264                         if (__comp > 0) {                               \
 265                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 266                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 267                                         break;                          \
 268                         }                                               \
 269                         SPLAY_LINKRIGHT(head, __left, field);           \
 270                 }                                                       \
 271         }                                                               \
 272         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 273 }
 274
 275 #define SPLAY_NEGINF    -1
 276 #define SPLAY_INF       1
 277
 278 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 279 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 280 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 281 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 282 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 283                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 284 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 285                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 286
 287 #define SPLAY_FOREACH(x, name, head)                                    \
 288         for ((x) = SPLAY_MIN(name, head);                               \
 289              (x) != NULL;                                               \
 290              (x) = SPLAY_NEXT(name, head, x))
 291
 292 /* Macros that define a red-black tree */
 293
 294 #define RB_SCAN_INFO(name, type)                                        \
 295 struct name##_scan_info {                                               \
 296         struct name##_scan_info *link;                                  \
 297         struct type     *node;                                          \
 298 }
 299
 300 #define RB_HEAD(name, type)                                             \
 301 struct name {                                                           \
 302         struct type *rbh_root;               /* root of the tree */     \
 303         struct name##_scan_info *rbh_inprog; /* scans in progress */    \
 304 }
 305
 306 #define RB_INITIALIZER(root)                                            \
 307         { NULL, NULL }
 308
 309 #define RB_INIT(root) do {                                              \
 310         (root)->rbh_root = NULL;                                        \
 311         (root)->rbh_inprog = NULL;                                      \
 312 } while (/*CONSTCOND*/ 0)
 313
 314 #define RB_BLACK        0
 315 #define RB_RED          1
 316 #define RB_ENTRY(type)                                                  \
 317 struct {                                                                \
 318         struct type *rbe_left;          /* left element */              \
 319         struct type *rbe_right;         /* right element */             \
 320         struct type *rbe_parent;        /* parent element */            \
 321         int rbe_color;                  /* node color */                \
 322 }
 323
 324 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
 325 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
 326 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
 327 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
 328 #define RB_ROOT(head)                   (head)->rbh_root
 329 #define RB_INPROG(head)                 (head)->rbh_inprog
 330 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 331
 332 #define RB_SET(elm, parent, field) do {                                 \
 333         RB_PARENT(elm, field) = parent;                                 \
 334         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
 335         RB_COLOR(elm, field) = RB_RED;                                  \
 336 } while (/*CONSTCOND*/ 0)
 337
 338 #define RB_SET_BLACKRED(black, red, field) do {                         \
 339         RB_COLOR(black, field) = RB_BLACK;                              \
 340         RB_COLOR(red, field) = RB_RED;                                  \
 341 } while (/*CONSTCOND*/ 0)
 342
 343 #ifdef RB_AUGMENT
 344 #error "RB_AUGMENT not supported by DragonFly"
 345 #endif
 346
 347 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
 348         (tmp) = RB_RIGHT(elm, field);                                   \
 349         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
 350                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
 351         }                                                               \
 352         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
 353                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 354                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 355                 else                                                    \
 356                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 357         } else                                                          \
 358                 (head)->rbh_root = (tmp);                               \
 359         RB_LEFT(tmp, field) = (elm);                                    \
 360         RB_PARENT(elm, field) = (tmp);                                  \
 361 } while (/*CONSTCOND*/ 0)
 362
 363 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
 364         (tmp) = RB_LEFT(elm, field);                                    \
 365         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
 366                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
 367         }                                                               \
 368         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
 369                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 370                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 371                 else                                                    \
 372                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 373         } else                                                          \
 374                 (head)->rbh_root = (tmp);                               \
 375         RB_RIGHT(tmp, field) = (elm);                                   \
 376         RB_PARENT(elm, field) = (tmp);                                  \
 377 } while (/*CONSTCOND*/ 0)
 378
 379 /* Generates prototypes and inline functions */
 380 #define RB_PROTOTYPE(name, type, field, cmp)                            \
 381         _RB_PROTOTYPE(name, type, field, cmp,)
 382 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
 383         _RB_PROTOTYPE(name, type, field, cmp, __unused static)
 384
 385 #define _RB_PROTOTYPE(name, type, field, cmp, STORQUAL)                 \
 386 STORQUAL struct type *name##_RB_REMOVE(struct name *, struct type *);   \
 387 STORQUAL struct type *name##_RB_INSERT(struct name *, struct type *);   \
 388 STORQUAL struct type *name##_RB_FIND(struct name *, struct type *);     \
 389 STORQUAL int name##_RB_SCAN(struct name *, int (*)(struct type *, void *),\
 390                         int (*)(struct type *, void *), void *);        \
 391 STORQUAL struct type *name##_RB_NEXT(struct type *);                    \
 392 STORQUAL struct type *name##_RB_PREV(struct type *);                    \
 393 STORQUAL struct type *name##_RB_MINMAX(struct name *, int);             \
 394 RB_SCAN_INFO(name, type)                                                \
 395
 396 /*
 397  * A version which supplies a fast lookup routine for an exact match
 398  * on a numeric field.
 399  */
 400 #define RB_PROTOTYPE2(name, type, field, cmp, datatype)                 \
 401 RB_PROTOTYPE(name, type, field, cmp);                                   \
 402 struct type *name##_RB_LOOKUP(struct name *, datatype)                  \
 403
 404 /*
 405  * A version which supplies a fast lookup routine for a numeric
 406  * field which resides within a ranged object, either using (begin,end),
 407  * or using (begin,size).
 408  */
 409 #define RB_PROTOTYPE3(name, type, field, cmp, datatype)                 \
 410 RB_PROTOTYPE2(name, type, field, cmp, datatype);                        \
 411 struct type *name##_RB_RLOOKUP(struct name *, datatype)                 \
 412
 413 #define RB_PROTOTYPE4(name, type, field, cmp, datatype)                 \
 414 RB_PROTOTYPE2(name, type, field, cmp, datatype);                        \
 415 struct type *name##_RB_RLOOKUP(struct name *, datatype)                 \
 416
 417 #define RB_PROTOTYPEX(name, ext, type, field, cmp, datatype)            \
 418 RB_PROTOTYPE(name, type, field, cmp);                                   \
 419 struct type *name##_RB_LOOKUP_##ext (struct name *, datatype)           \
 420
 421 /* Main rb operation.
 422  * Moves node close to the key of elm to top
 423  */
 424 #define RB_GENERATE(name, type, field, cmp)                             \
 425         _RB_GENERATE(name, type, field, cmp,)
 426
 427 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
 428         _RB_GENERATE(name, type, field, cmp, __unused static)
 429
 430 #define _RB_GENERATE(name, type, field, cmp, STORQUAL)                  \
 431 static void                                                             \
 432 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
 433 {                                                                       \
 434         struct type *parent, *gparent, *tmp;                            \
 435         while ((parent = RB_PARENT(elm, field)) != NULL &&              \
 436             RB_COLOR(parent, field) == RB_RED) {                        \
 437                 gparent = RB_PARENT(parent, field);                     \
 438                 if (parent == RB_LEFT(gparent, field)) {                \
 439                         tmp = RB_RIGHT(gparent, field);                 \
 440                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 441                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 442                                 RB_SET_BLACKRED(parent, gparent, field);\
 443                                 elm = gparent;                          \
 444                                 continue;                               \
 445                         }                                               \
 446                         if (RB_RIGHT(parent, field) == elm) {           \
 447                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 448                                 tmp = parent;                           \
 449                                 parent = elm;                           \
 450                                 elm = tmp;                              \
 451                         }                                               \
 452                         RB_SET_BLACKRED(parent, gparent, field);        \
 453                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
 454                 } else {                                                \
 455                         tmp = RB_LEFT(gparent, field);                  \
 456                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 457                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 458                                 RB_SET_BLACKRED(parent, gparent, field);\
 459                                 elm = gparent;                          \
 460                                 continue;                               \
 461                         }                                               \
 462                         if (RB_LEFT(parent, field) == elm) {            \
 463                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 464                                 tmp = parent;                           \
 465                                 parent = elm;                           \
 466                                 elm = tmp;                              \
 467                         }                                               \
 468                         RB_SET_BLACKRED(parent, gparent, field);        \
 469                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
 470                 }                                                       \
 471         }                                                               \
 472         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
 473 }                                                                       \
 474                                                                         \
 475 static void                                                             \
 476 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent,          \
 477                         struct type *elm)                               \
 478 {                                                                       \
 479         struct type *tmp;                                               \
 480         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
 481             elm != RB_ROOT(head)) {                                     \
 482                 if (RB_LEFT(parent, field) == elm) {                    \
 483                         tmp = RB_RIGHT(parent, field);                  \
 484                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 485                                 RB_SET_BLACKRED(tmp, parent, field);    \
 486                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 487                                 tmp = RB_RIGHT(parent, field);          \
 488                         }                                               \
 489                         if ((RB_LEFT(tmp, field) == NULL ||             \
 490                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 491                             (RB_RIGHT(tmp, field) == NULL ||            \
 492                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 493                                 RB_COLOR(tmp, field) = RB_RED;          \
 494                                 elm = parent;                           \
 495                                 parent = RB_PARENT(elm, field);         \
 496                         } else {                                        \
 497                                 if (RB_RIGHT(tmp, field) == NULL ||     \
 498                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
 499                                         struct type *oleft;             \
 500                                         if ((oleft = RB_LEFT(tmp, field)) \
 501                                             != NULL)                    \
 502                                                 RB_COLOR(oleft, field) = RB_BLACK;\
 503                                         RB_COLOR(tmp, field) = RB_RED;  \
 504                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
 505                                         tmp = RB_RIGHT(parent, field);  \
 506                                 }                                       \
 507                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 508                                 RB_COLOR(parent, field) = RB_BLACK;     \
 509                                 if (RB_RIGHT(tmp, field))               \
 510                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
 511                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 512                                 elm = RB_ROOT(head);                    \
 513                                 break;                                  \
 514                         }                                               \
 515                 } else {                                                \
 516                         tmp = RB_LEFT(parent, field);                   \
 517                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 518                                 RB_SET_BLACKRED(tmp, parent, field);    \
 519                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 520                                 tmp = RB_LEFT(parent, field);           \
 521                         }                                               \
 522                         if ((RB_LEFT(tmp, field) == NULL ||             \
 523                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 524                             (RB_RIGHT(tmp, field) == NULL ||            \
 525                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 526                                 RB_COLOR(tmp, field) = RB_RED;          \
 527                                 elm = parent;                           \
 528                                 parent = RB_PARENT(elm, field);         \
 529                         } else {                                        \
 530                                 if (RB_LEFT(tmp, field) == NULL ||      \
 531                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
 532                                         struct type *oright;            \
 533                                         if ((oright = RB_RIGHT(tmp, field)) \
 534                                             != NULL)                    \
 535                                                 RB_COLOR(oright, field) = RB_BLACK;\
 536                                         RB_COLOR(tmp, field) = RB_RED;  \
 537                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
 538                                         tmp = RB_LEFT(parent, field);   \
 539                                 }                                       \
 540                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 541                                 RB_COLOR(parent, field) = RB_BLACK;     \
 542                                 if (RB_LEFT(tmp, field))                \
 543                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
 544                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 545                                 elm = RB_ROOT(head);                    \
 546                                 break;                                  \
 547                         }                                               \
 548                 }                                                       \
 549         }                                                               \
 550         if (elm)                                                        \
 551                 RB_COLOR(elm, field) = RB_BLACK;                        \
 552 }                                                                       \
 553                                                                         \
 554 STORQUAL struct type *                                                  \
 555 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
 556 {                                                                       \
 557         struct type *child, *parent, *old;                              \
 558         struct name##_scan_info *inprog;                                \
 559         int color;                                                      \
 560                                                                         \
 561         for (inprog = RB_INPROG(head); inprog; inprog = inprog->link) { \
 562                 if (inprog->node == elm)                                \
 563                         inprog->node = RB_NEXT(name, head, elm);        \
 564         }                                                               \
 565                                                                         \
 566         old = elm;                                                      \
 567         if (RB_LEFT(elm, field) == NULL)                                \
 568                 child = RB_RIGHT(elm, field);                           \
 569         else if (RB_RIGHT(elm, field) == NULL)                          \
 570                 child = RB_LEFT(elm, field);                            \
 571         else {                                                          \
 572                 struct type *left;                                      \
 573                 elm = RB_RIGHT(elm, field);                             \
 574                 while ((left = RB_LEFT(elm, field)) != NULL)            \
 575                         elm = left;                                     \
 576                 child = RB_RIGHT(elm, field);                           \
 577                 parent = RB_PARENT(elm, field);                         \
 578                 color = RB_COLOR(elm, field);                           \
 579                 if (child)                                              \
 580                         RB_PARENT(child, field) = parent;               \
 581                 if (parent) {                                           \
 582                         if (RB_LEFT(parent, field) == elm)              \
 583                                 RB_LEFT(parent, field) = child;         \
 584                         else                                            \
 585                                 RB_RIGHT(parent, field) = child;        \
 586                 } else                                                  \
 587                         RB_ROOT(head) = child;                          \
 588                 if (RB_PARENT(elm, field) == old)                       \
 589                         parent = elm;                                   \
 590                 (elm)->field = (old)->field;                            \
 591                 if (RB_PARENT(old, field)) {                            \
 592                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
 593                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
 594                         else                                            \
 595                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
 596                 } else                                                  \
 597                         RB_ROOT(head) = elm;                            \
 598                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
 599                 if (RB_RIGHT(old, field))                               \
 600                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
 601                 goto color;                                             \
 602         }                                                               \
 603         parent = RB_PARENT(elm, field);                                 \
 604         color = RB_COLOR(elm, field);                                   \
 605         if (child)                                                      \
 606                 RB_PARENT(child, field) = parent;                       \
 607         if (parent) {                                                   \
 608                 if (RB_LEFT(parent, field) == elm)                      \
 609                         RB_LEFT(parent, field) = child;                 \
 610                 else                                                    \
 611                         RB_RIGHT(parent, field) = child;                \
 612         } else                                                          \
 613                 RB_ROOT(head) = child;                                  \
 614 color:                                                                  \
 615         if (color == RB_BLACK)                                          \
 616                 name##_RB_REMOVE_COLOR(head, parent, child);            \
 617         return (old);                                                   \
 618 }                                                                       \
 619                                                                         \
 620 /* Inserts a node into the RB tree */                                   \
 621 STORQUAL struct type *                                                  \
 622 name##_RB_INSERT(struct name *head, struct type *elm)                   \
 623 {                                                                       \
 624         struct type *tmp;                                               \
 625         struct type *parent = NULL;                                     \
 626         int comp = 0;                                                   \
 627         tmp = RB_ROOT(head);                                            \
 628         while (tmp) {                                                   \
 629                 parent = tmp;                                           \
 630                 comp = (cmp)(elm, parent);                              \
 631                 if (comp < 0)                                           \
 632                         tmp = RB_LEFT(tmp, field);                      \
 633                 else if (comp > 0)                                      \
 634                         tmp = RB_RIGHT(tmp, field);                     \
 635                 else                                                    \
 636                         return(tmp);                                    \
 637         }                                                               \
 638         RB_SET(elm, parent, field);                                     \
 639         if (parent != NULL) {                                           \
 640                 if (comp < 0)                                           \
 641                         RB_LEFT(parent, field) = elm;                   \
 642                 else                                                    \
 643                         RB_RIGHT(parent, field) = elm;                  \
 644         } else                                                          \
 645                 RB_ROOT(head) = elm;                                    \
 646         name##_RB_INSERT_COLOR(head, elm);                              \
 647         return (NULL);                                                  \
 648 }                                                                       \
 649                                                                         \
 650 /* Finds the node with the same key as elm */                           \
 651 STORQUAL struct type *                                                  \
 652 name##_RB_FIND(struct name *head, struct type *elm)                     \
 653 {                                                                       \
 654         struct type *tmp = RB_ROOT(head);                               \
 655         int comp;                                                       \
 656         while (tmp) {                                                   \
 657                 comp = cmp(elm, tmp);                                   \
 658                 if (comp < 0)                                           \
 659                         tmp = RB_LEFT(tmp, field);                      \
 660                 else if (comp > 0)                                      \
 661                         tmp = RB_RIGHT(tmp, field);                     \
 662                 else                                                    \
 663                         return (tmp);                                   \
 664         }                                                               \
 665         return (NULL);                                                  \
 666 }                                                                       \
 667                                                                         \
 668 /*                                                                      \
 669  * Issue a callback for all matching items.  The scan function must     \
 670  * return < 0 for items below the desired range, 0 for items within     \
 671  * the range, and > 0 for items beyond the range.   Any item may be     \
 672  * deleted while the scan is in progress.                               \
 673  */                                                                     \
 674 static int                                                              \
 675 name##_SCANCMP_ALL(struct type *type __unused, void *data __unused)     \
 676 {                                                                       \
 677         return(0);                                                      \
 678 }                                                                       \
 679                                                                         \
 680 static __inline void                                                    \
 681 name##_scan_info_link(struct name##_scan_info *scan, struct name *head) \
 682 {                                                                       \
 683         scan->link = RB_INPROG(head);                                   \
 684         RB_INPROG(head) = scan;                                         \
 685 }                                                                       \
 686                                                                         \
 687 static __inline void                                                    \
 688 name##_scan_info_done(struct name##_scan_info *scan, struct name *head) \
 689 {                                                                       \
 690         struct name##_scan_info **infopp;                               \
 691                                                                         \
 692         infopp = &RB_INPROG(head);                                      \
 693         while (*infopp != scan)                                         \
 694                 infopp = &(*infopp)->link;                              \
 695         *infopp = scan->link;                                           \
 696 }                                                                       \
 697                                                                         \
 698 STORQUAL int                                                            \
 699 name##_RB_SCAN(struct name *head,                                       \
 700                 int (*scancmp)(struct type *, void *),                  \
 701                 int (*callback)(struct type *, void *),                 \
 702                 void *data)                                             \
 703 {                                                                       \
 704         struct name##_scan_info info;                                   \
 705         struct type *best;                                              \
 706         struct type *tmp;                                               \
 707         int count;                                                      \
 708         int comp;                                                       \
 709                                                                         \
 710         if (scancmp == NULL)                                            \
 711                 scancmp = name##_SCANCMP_ALL;                           \
 712                                                                         \
 713         /*                                                              \
 714          * Locate the first element.                                    \
 715          */                                                             \
 716         tmp = RB_ROOT(head);                                            \
 717         best = NULL;                                                    \
 718         while (tmp) {                                                   \
 719                 comp = scancmp(tmp, data);                              \
 720                 if (comp < 0) {                                         \
 721                         tmp = RB_RIGHT(tmp, field);                     \
 722                 } else if (comp > 0) {                                  \
 723                         tmp = RB_LEFT(tmp, field);                      \
 724                 } else {                                                \
 725                         best = tmp;                                     \
 726                         if (RB_LEFT(tmp, field) == NULL)                \
 727                                 break;                                  \
 728                         tmp = RB_LEFT(tmp, field);                      \
 729                 }                                                       \
 730         }                                                               \
 731         count = 0;                                                      \
 732         if (best) {                                                     \
 733                 info.node = RB_NEXT(name, head, best);                  \
 734                 name##_scan_info_link(&info, head);                     \
 735                 while ((comp = callback(best, data)) >= 0) {            \
 736                         count += comp;                                  \
 737                         best = info.node;                               \
 738                         if (best == NULL || scancmp(best, data) != 0)   \
 739                                 break;                                  \
 740                         info.node = RB_NEXT(name, head, best);          \
 741                 }                                                       \
 742                 name##_scan_info_done(&info, head);                     \
 743                 if (comp < 0)   /* error or termination */              \
 744                         count = comp;                                   \
 745         }                                                               \
 746         return(count);                                                  \
 747 }                                                                       \
 748                                                                         \
 749 /* ARGSUSED */                                                          \
 750 STORQUAL struct type *                                                  \
 751 name##_RB_NEXT(struct type *elm)                                        \
 752 {                                                                       \
 753         if (RB_RIGHT(elm, field)) {                                     \
 754                 elm = RB_RIGHT(elm, field);                             \
 755                 while (RB_LEFT(elm, field))                             \
 756                         elm = RB_LEFT(elm, field);                      \
 757         } else {                                                        \
 758                 if (RB_PARENT(elm, field) &&                            \
 759                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
 760                         elm = RB_PARENT(elm, field);                    \
 761                 else {                                                  \
 762                         while (RB_PARENT(elm, field) &&                 \
 763                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
 764                                 elm = RB_PARENT(elm, field);            \
 765                         elm = RB_PARENT(elm, field);                    \
 766                 }                                                       \
 767         }                                                               \
 768         return (elm);                                                   \
 769 }                                                                       \
 770                                                                         \
 771 /* ARGSUSED */                                                          \
 772 STORQUAL struct type *                                                  \
 773 name##_RB_PREV(struct type *elm)                                        \
 774 {                                                                       \
 775         if (RB_LEFT(elm, field)) {                                      \
 776                 elm = RB_LEFT(elm, field);                              \
 777                 while (RB_RIGHT(elm, field))                            \
 778                         elm = RB_RIGHT(elm, field);                     \
 779         } else {                                                        \
 780                 if (RB_PARENT(elm, field) &&                            \
 781                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
 782                         elm = RB_PARENT(elm, field);                    \
 783                 else {                                                  \
 784                         while (RB_PARENT(elm, field) &&                 \
 785                             (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
 786                                 elm = RB_PARENT(elm, field);            \
 787                         elm = RB_PARENT(elm, field);                    \
 788                 }                                                       \
 789         }                                                               \
 790         return (elm);                                                   \
 791 }                                                                       \
 792                                                                         \
 793 STORQUAL struct type *                                                  \
 794 name##_RB_MINMAX(struct name *head, int val)                            \
 795 {                                                                       \
 796         struct type *tmp = RB_ROOT(head);                               \
 797         struct type *parent = NULL;                                     \
 798         while (tmp) {                                                   \
 799                 parent = tmp;                                           \
 800                 if (val < 0)                                            \
 801                         tmp = RB_LEFT(tmp, field);                      \
 802                 else                                                    \
 803                         tmp = RB_RIGHT(tmp, field);                     \
 804         }                                                               \
 805         return (parent);                                                \
 806 }
 807
 808 /*
 809  * This extended version implements a fast LOOKUP function given
 810  * a numeric data type.
 811  *
 812  * The element whos index/offset field is exactly the specified value
 813  * will be returned, or NULL.
 814  */
 815 #define RB_GENERATE2(name, type, field, cmp, datatype, indexfield)      \
 816 RB_GENERATE(name, type, field, cmp)                                     \
 817                                                                         \
 818 struct type *                                                           \
 819 name##_RB_LOOKUP(struct name *head, datatype value)                     \
 820 {                                                                       \
 821         struct type *tmp;                                               \
 822                                                                         \
 823         tmp = RB_ROOT(head);                                            \
 824         while (tmp) {                                                   \
 825                 if (value > tmp->indexfield)                            \
 826                         tmp = RB_RIGHT(tmp, field);                     \
 827                 else if (value < tmp->indexfield)                       \
 828                         tmp = RB_LEFT(tmp, field);                      \
 829                 else                                                    \
 830                         return(tmp);                                    \
 831         }                                                               \
 832         return(NULL);                                                   \
 833 }                                                                       \
 834
 835 /*
 836  * This extended version implements a fast ranged-based LOOKUP function
 837  * given a numeric data type, for data types with a beginning and end
 838  * (end is inclusive).
 839  *
 840  * The element whos range contains the specified value is returned, or NULL
 841  */
 842 #define RB_GENERATE3(name, type, field, cmp, datatype, begfield, endfield) \
 843 RB_GENERATE2(name, type, field, cmp, datatype, begfield)                \
 844                                                                         \
 845 struct type *                                                           \
 846 name##_RB_RLOOKUP(struct name *head, datatype value)                    \
 847 {                                                                       \
 848         struct type *tmp;                                               \
 849                                                                         \
 850         tmp = RB_ROOT(head);                                            \
 851         while (tmp) {                                                   \
 852                 if (value >= tmp->begfield && value <= tmp->endfield)   \
 853                         return(tmp);                                    \
 854                 if (value > tmp->begfield)                              \
 855                         tmp = RB_RIGHT(tmp, field);                     \
 856                 else                                                    \
 857                         tmp = RB_LEFT(tmp, field);                      \
 858         }                                                               \
 859         return(NULL);                                                   \
 860 }                                                                       \
 861
 862 /*
 863  * This extended version implements a fast ranged-based LOOKUP function
 864  * given a numeric data type, for data types with a beginning and size.
 865  *
 866  * WARNING: The full range of the data type is not supported due to a
 867  * boundary condition at the end, where (beginning + size) might overflow.
 868  *
 869  * The element whos range contains the specified value is returned, or NULL
 870  */
 871 #define RB_GENERATE4(name, type, field, cmp, datatype, begfield, sizefield) \
 872 RB_GENERATE2(name, type, field, cmp, datatype, begfield)                \
 873                                                                         \
 874 struct type *                                                           \
 875 name##_RB_RLOOKUP(struct name *head, datatype value)                    \
 876 {                                                                       \
 877         struct type *tmp;                                               \
 878                                                                         \
 879         tmp = RB_ROOT(head);                                            \
 880         while (tmp) {                                                   \
 881                 if (value >= tmp->begfield &&                           \
 882                     value < tmp->begfield + tmp->sizefield) {           \
 883                         return(tmp);                                    \
 884                 }                                                       \
 885                 if (value > tmp->begfield)                              \
 886                         tmp = RB_RIGHT(tmp, field);                     \
 887                 else                                                    \
 888                         tmp = RB_LEFT(tmp, field);                      \
 889         }                                                               \
 890         return(NULL);                                                   \
 891 }                                                                       \
 892
 893 /*
 894  * This generates a custom lookup function for a red-black tree.
 895  * Note that the macro may be used with a storage qualifier.
 896  */
 897
 898 #define RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype)        \
 899         _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype,)
 900 #define RB_GENERATE_XLOOKUP_STATIC(name, ext, type, field, xcmp, datatype) \
 901         _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype, __unused static)
 902
 903 #define _RB_GENERATE_XLOOKUP(name, ext, type, field, xcmp, datatype, STORQUAL)\
 904                                                                         \
 905 STORQUAL struct type *                                                  \
 906 name##_RB_LOOKUP_##ext (struct name *head, datatype value)              \
 907 {                                                                       \
 908         struct type *tmp;                                               \
 909         int r;                                                          \
 910                                                                         \
 911         tmp = RB_ROOT(head);                                            \
 912         while (tmp) {                                                   \
 913                 r = xcmp(value, tmp);                                   \
 914                 if (r == 0)                                             \
 915                         return(tmp);                                    \
 916                 if (r > 0)                                              \
 917                         tmp = RB_RIGHT(tmp, field);                     \
 918                 else                                                    \
 919                         tmp = RB_LEFT(tmp, field);                      \
 920         }                                                               \
 921         return(NULL);                                                   \
 922 }                                                                       \
 923
 924
 925 #define RB_NEGINF       -1
 926 #define RB_INF  1
 927
 928 #define RB_INSERT(name, root, elm)      name##_RB_INSERT(root, elm)
 929 #define RB_REMOVE(name, root, elm)      name##_RB_REMOVE(root, elm)
 930 #define RB_FIND(name, root, elm)        name##_RB_FIND(root, elm)
 931 #define RB_LOOKUP(name, root, value)    name##_RB_LOOKUP(root, value)
 932 #define RB_RLOOKUP(name, root, value)   name##_RB_RLOOKUP(root, value)
 933 #define RB_SCAN(name, root, cmp, callback, data)                        \
 934                                 name##_RB_SCAN(root, cmp, callback, data)
 935 #define RB_FIRST(name, root)            name##_RB_MINMAX(root, RB_NEGINF)
 936 #define RB_NEXT(name, root, elm)        name##_RB_NEXT(elm)
 937 #define RB_PREV(name, root, elm)        name##_RB_PREV(elm)
 938 #define RB_MIN(name, root)              name##_RB_MINMAX(root, RB_NEGINF)
 939 #define RB_MAX(name, root)              name##_RB_MINMAX(root, RB_INF)
 940
 941 #define RB_FOREACH(x, name, head)                                       \
 942         for ((x) = RB_MIN(name, head);                                  \
 943              (x) != NULL;                                               \
 944              (x) = name##_RB_NEXT(x))
 945
 946 #endif  /* _SYS_TREE_H_ */