util/tree.h

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