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