util/tree.h

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