contrib/ipfilter/sys/tree.h

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