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