core/musl/files/tree.h

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