crypto/openssh/openbsd-compat/tree.h

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