libevent/WIN32-Code/tree.h

   1 /*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
   2 /*
   3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #ifndef _SYS_TREE_H_
  28 #define _SYS_TREE_H_
  29
  30 /*
  31  * This file defines data structures for different types of trees:
  32  * splay trees and red-black trees.
  33  *
  34  * A splay tree is a self-organizing data structure.  Every operation
  35  * on the tree causes a splay to happen.  The splay moves the requested
  36  * node to the root of the tree and partly rebalances it.
  37  *
  38  * This has the benefit that request locality causes faster lookups as
  39  * the requested nodes move to the top of the tree.  On the other hand,
  40  * every lookup causes memory writes.
  41  *
  42  * The Balance Theorem bounds the total access time for m operations
  43  * and n inserts on an initially empty tree as O((m + n)lg n).  The
  44  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  45  *
  46  * A red-black tree is a binary search tree with the node color as an
  47  * extra attribute.  It fulfills a set of conditions:
  48  *      - every search path from the root to a leaf consists of the
  49  *        same number of black nodes,
  50  *      - each red node (except for the root) has a black parent,
  51  *      - each leaf node is black.
  52  *
  53  * Every operation on a red-black tree is bounded as O(lg n).
  54  * The maximum height of a red-black tree is 2lg (n+1).
  55  */
  56
  57 #define SPLAY_HEAD(name, type)                                          \
  58 struct name {                                                           \
  59         struct type *sph_root; /* root of the tree */                   \
  60 }
  61
  62 #define SPLAY_INITIALIZER(root)                                         \
  63         { NULL }
  64
  65 #define SPLAY_INIT(root) do {                                           \
  66         (root)->sph_root = NULL;                                        \
  67 } while (0)
  68
  69 #define SPLAY_ENTRY(type)                                               \
  70 struct {                                                                \
  71         struct type *spe_left; /* left element */                       \
  72         struct type *spe_right; /* right element */                     \
  73 }
  74
  75 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
  76 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
  77 #define SPLAY_ROOT(head)                (head)->sph_root
  78 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
  79
  80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
  82         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
  83         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
  84         (head)->sph_root = tmp;                                         \
  85 } while (0)
  86
  87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
  88         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
  89         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
  90         (head)->sph_root = tmp;                                         \
  91 } while (0)
  92
  93 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
  94         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
  95         tmp = (head)->sph_root;                                         \
  96         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
  97 } while (0)
  98
  99 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
 100         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 101         tmp = (head)->sph_root;                                         \
 102         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
 103 } while (0)
 104
 105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
 106         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
 107         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
 108         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
 109         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
 110 } while (0)
 111
 112 /* Generates prototypes and inline functions */
 113
 114 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
 115 void name##_SPLAY(struct name *, struct type *);                        \
 116 void name##_SPLAY_MINMAX(struct name *, int);                           \
 117 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
 118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
 119                                                                         \
 120 /* Finds the node with the same key as elm */                           \
 121 static __inline struct type *                                           \
 122 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
 123 {                                                                       \
 124         if (SPLAY_EMPTY(head))                                          \
 125                 return(NULL);                                           \
 126         name##_SPLAY(head, elm);                                        \
 127         if ((cmp)(elm, (head)->sph_root) == 0)                          \
 128                 return (head->sph_root);                                \
 129         return (NULL);                                                  \
 130 }                                                                       \
 131                                                                         \
 132 static __inline struct type *                                           \
 133 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
 134 {                                                                       \
 135         name##_SPLAY(head, elm);                                        \
 136         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
 137                 elm = SPLAY_RIGHT(elm, field);                          \
 138                 while (SPLAY_LEFT(elm, field) != NULL) {                \
 139                         elm = SPLAY_LEFT(elm, field);                   \
 140                 }                                                       \
 141         } else                                                          \
 142                 elm = NULL;                                             \
 143         return (elm);                                                   \
 144 }                                                                       \
 145                                                                         \
 146 static __inline struct type *                                           \
 147 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
 148 {                                                                       \
 149         name##_SPLAY_MINMAX(head, val);                                 \
 150         return (SPLAY_ROOT(head));                                      \
 151 }
 152
 153 /* Main splay operation.
 154  * Moves node close to the key of elm to top
 155  */
 156 #define SPLAY_GENERATE(name, type, field, cmp)                          \
 157 struct type *                                                           \
 158 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
 159 {                                                                       \
 160     if (SPLAY_EMPTY(head)) {                                            \
 161             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
 162     } else {                                                            \
 163             int __comp;                                                 \
 164             name##_SPLAY(head, elm);                                    \
 165             __comp = (cmp)(elm, (head)->sph_root);                      \
 166             if(__comp < 0) {                                            \
 167                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
 168                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
 169                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
 170             } else if (__comp > 0) {                                    \
 171                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
 172                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
 173                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
 174             } else                                                      \
 175                     return ((head)->sph_root);                          \
 176     }                                                                   \
 177     (head)->sph_root = (elm);                                           \
 178     return (NULL);                                                      \
 179 }                                                                       \
 180                                                                         \
 181 struct type *                                                           \
 182 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
 183 {                                                                       \
 184         struct type *__tmp;                                             \
 185         if (SPLAY_EMPTY(head))                                          \
 186                 return (NULL);                                          \
 187         name##_SPLAY(head, elm);                                        \
 188         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
 189                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
 190                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
 191                 } else {                                                \
 192                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 193                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
 194                         name##_SPLAY(head, elm);                        \
 195                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
 196                 }                                                       \
 197                 return (elm);                                           \
 198         }                                                               \
 199         return (NULL);                                                  \
 200 }                                                                       \
 201                                                                         \
 202 void                                                                    \
 203 name##_SPLAY(struct name *head, struct type *elm)                       \
 204 {                                                                       \
 205         struct type __node, *__left, *__right, *__tmp;                  \
 206         int __comp;                                                     \
 207 \
 208         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 209         __left = __right = &__node;                                     \
 210 \
 211         while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
 212                 if (__comp < 0) {                                       \
 213                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 214                         if (__tmp == NULL)                              \
 215                                 break;                                  \
 216                         if ((cmp)(elm, __tmp) < 0){                     \
 217                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 218                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 219                                         break;                          \
 220                         }                                               \
 221                         SPLAY_LINKLEFT(head, __right, field);           \
 222                 } else if (__comp > 0) {                                \
 223                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 224                         if (__tmp == NULL)                              \
 225                                 break;                                  \
 226                         if ((cmp)(elm, __tmp) > 0){                     \
 227                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 228                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 229                                         break;                          \
 230                         }                                               \
 231                         SPLAY_LINKRIGHT(head, __left, field);           \
 232                 }                                                       \
 233         }                                                               \
 234         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 235 }                                                                       \
 236                                                                         \
 237 /* Splay with either the minimum or the maximum element                 \
 238  * Used to find minimum or maximum element in tree.                     \
 239  */                                                                     \
 240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 241 {                                                                       \
 242         struct type __node, *__left, *__right, *__tmp;                  \
 243 \
 244         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 245         __left = __right = &__node;                                     \
 246 \
 247         while (1) {                                                     \
 248                 if (__comp < 0) {                                       \
 249                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 250                         if (__tmp == NULL)                              \
 251                                 break;                                  \
 252                         if (__comp < 0){                                \
 253                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 254                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 255                                         break;                          \
 256                         }                                               \
 257                         SPLAY_LINKLEFT(head, __right, field);           \
 258                 } else if (__comp > 0) {                                \
 259                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 260                         if (__tmp == NULL)                              \
 261                                 break;                                  \
 262                         if (__comp > 0) {                               \
 263                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 264                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 265                                         break;                          \
 266                         }                                               \
 267                         SPLAY_LINKRIGHT(head, __left, field);           \
 268                 }                                                       \
 269         }                                                               \
 270         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 271 }
 272
 273 #define SPLAY_NEGINF    -1
 274 #define SPLAY_INF       1
 275
 276 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 277 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 278 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 279 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 280 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 281                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 282 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 283                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 284
 285 #define SPLAY_FOREACH(x, name, head)                                    \
 286         for ((x) = SPLAY_MIN(name, head);                               \
 287              (x) != NULL;                                               \
 288              (x) = SPLAY_NEXT(name, head, x))
 289
 290 /* Macros that define a red-back tree */
 291 #define RB_HEAD(name, type)                                             \
 292 struct name {                                                           \
 293         struct type *rbh_root; /* root of the tree */                   \
 294 }
 295
 296 #define RB_INITIALIZER(root)                                            \
 297         { NULL }
 298
 299 #define RB_INIT(root) do {                                              \
 300         (root)->rbh_root = NULL;                                        \
 301 } while (0)
 302
 303 #define RB_BLACK        0
 304 #define RB_RED          1
 305 #define RB_ENTRY(type)                                                  \
 306 struct {                                                                \
 307         struct type *rbe_left;          /* left element */              \
 308         struct type *rbe_right;         /* right element */             \
 309         struct type *rbe_parent;        /* parent element */            \
 310         int rbe_color;                  /* node color */                \
 311 }
 312
 313 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
 314 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
 315 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
 316 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
 317 #define RB_ROOT(head)                   (head)->rbh_root
 318 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 319
 320 #define RB_SET(elm, parent, field) do {                                 \
 321         RB_PARENT(elm, field) = parent;                                 \
 322         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
 323         RB_COLOR(elm, field) = RB_RED;                                  \
 324 } while (0)
 325
 326 #define RB_SET_BLACKRED(black, red, field) do {                         \
 327         RB_COLOR(black, field) = RB_BLACK;                              \
 328         RB_COLOR(red, field) = RB_RED;                                  \
 329 } while (0)
 330
 331 #ifndef RB_AUGMENT
 332 #define RB_AUGMENT(x)
 333 #endif
 334
 335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
 336         (tmp) = RB_RIGHT(elm, field);                                   \
 337         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
 338                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
 339         }                                                               \
 340         RB_AUGMENT(elm);                                                \
 341         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
 342                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 343                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 344                 else                                                    \
 345                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 346         } else                                                          \
 347                 (head)->rbh_root = (tmp);                               \
 348         RB_LEFT(tmp, field) = (elm);                                    \
 349         RB_PARENT(elm, field) = (tmp);                                  \
 350         RB_AUGMENT(tmp);                                                \
 351         if ((RB_PARENT(tmp, field)))                                    \
 352                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
 353 } while (0)
 354
 355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
 356         (tmp) = RB_LEFT(elm, field);                                    \
 357         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
 358                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
 359         }                                                               \
 360         RB_AUGMENT(elm);                                                \
 361         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
 362                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
 363                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
 364                 else                                                    \
 365                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
 366         } else                                                          \
 367                 (head)->rbh_root = (tmp);                               \
 368         RB_RIGHT(tmp, field) = (elm);                                   \
 369         RB_PARENT(elm, field) = (tmp);                                  \
 370         RB_AUGMENT(tmp);                                                \
 371         if ((RB_PARENT(tmp, field)))                                    \
 372                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
 373 } while (0)
 374
 375 /* Generates prototypes and inline functions */
 376 #define RB_PROTOTYPE(name, type, field, cmp)                            \
 377 void name##_RB_INSERT_COLOR(struct name *, struct type *);      \
 378 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
 379 struct type *name##_RB_REMOVE(struct name *, struct type *);            \
 380 struct type *name##_RB_INSERT(struct name *, struct type *);            \
 381 struct type *name##_RB_FIND(struct name *, struct type *);              \
 382 struct type *name##_RB_NEXT(struct type *);                             \
 383 struct type *name##_RB_MINMAX(struct name *, int);                      \
 384                                                                         \
 385
 386 /* Main rb operation.
 387  * Moves node close to the key of elm to top
 388  */
 389 #define RB_GENERATE(name, type, field, cmp)                             \
 390 void                                                                    \
 391 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
 392 {                                                                       \
 393         struct type *parent, *gparent, *tmp;                            \
 394         while ((parent = RB_PARENT(elm, field)) &&                      \
 395             RB_COLOR(parent, field) == RB_RED) {                        \
 396                 gparent = RB_PARENT(parent, field);                     \
 397                 if (parent == RB_LEFT(gparent, field)) {                \
 398                         tmp = RB_RIGHT(gparent, field);                 \
 399                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 400                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 401                                 RB_SET_BLACKRED(parent, gparent, field);\
 402                                 elm = gparent;                          \
 403                                 continue;                               \
 404                         }                                               \
 405                         if (RB_RIGHT(parent, field) == elm) {           \
 406                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 407                                 tmp = parent;                           \
 408                                 parent = elm;                           \
 409                                 elm = tmp;                              \
 410                         }                                               \
 411                         RB_SET_BLACKRED(parent, gparent, field);        \
 412                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
 413                 } else {                                                \
 414                         tmp = RB_LEFT(gparent, field);                  \
 415                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
 416                                 RB_COLOR(tmp, field) = RB_BLACK;        \
 417                                 RB_SET_BLACKRED(parent, gparent, field);\
 418                                 elm = gparent;                          \
 419                                 continue;                               \
 420                         }                                               \
 421                         if (RB_LEFT(parent, field) == elm) {            \
 422                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 423                                 tmp = parent;                           \
 424                                 parent = elm;                           \
 425                                 elm = tmp;                              \
 426                         }                                               \
 427                         RB_SET_BLACKRED(parent, gparent, field);        \
 428                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
 429                 }                                                       \
 430         }                                                               \
 431         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
 432 }                                                                       \
 433                                                                         \
 434 void                                                                    \
 435 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 436 {                                                                       \
 437         struct type *tmp;                                               \
 438         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
 439             elm != RB_ROOT(head)) {                                     \
 440                 if (RB_LEFT(parent, field) == elm) {                    \
 441                         tmp = RB_RIGHT(parent, field);                  \
 442                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 443                                 RB_SET_BLACKRED(tmp, parent, field);    \
 444                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 445                                 tmp = RB_RIGHT(parent, field);          \
 446                         }                                               \
 447                         if ((RB_LEFT(tmp, field) == NULL ||             \
 448                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 449                             (RB_RIGHT(tmp, field) == NULL ||            \
 450                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 451                                 RB_COLOR(tmp, field) = RB_RED;          \
 452                                 elm = parent;                           \
 453                                 parent = RB_PARENT(elm, field);         \
 454                         } else {                                        \
 455                                 if (RB_RIGHT(tmp, field) == NULL ||     \
 456                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
 457                                         struct type *oleft;             \
 458                                         if ((oleft = RB_LEFT(tmp, field)))\
 459                                                 RB_COLOR(oleft, field) = RB_BLACK;\
 460                                         RB_COLOR(tmp, field) = RB_RED;  \
 461                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
 462                                         tmp = RB_RIGHT(parent, field);  \
 463                                 }                                       \
 464                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 465                                 RB_COLOR(parent, field) = RB_BLACK;     \
 466                                 if (RB_RIGHT(tmp, field))               \
 467                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
 468                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
 469                                 elm = RB_ROOT(head);                    \
 470                                 break;                                  \
 471                         }                                               \
 472                 } else {                                                \
 473                         tmp = RB_LEFT(parent, field);                   \
 474                         if (RB_COLOR(tmp, field) == RB_RED) {           \
 475                                 RB_SET_BLACKRED(tmp, parent, field);    \
 476                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 477                                 tmp = RB_LEFT(parent, field);           \
 478                         }                                               \
 479                         if ((RB_LEFT(tmp, field) == NULL ||             \
 480                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 481                             (RB_RIGHT(tmp, field) == NULL ||            \
 482                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 483                                 RB_COLOR(tmp, field) = RB_RED;          \
 484                                 elm = parent;                           \
 485                                 parent = RB_PARENT(elm, field);         \
 486                         } else {                                        \
 487                                 if (RB_LEFT(tmp, field) == NULL ||      \
 488                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
 489                                         struct type *oright;            \
 490                                         if ((oright = RB_RIGHT(tmp, field)))\
 491                                                 RB_COLOR(oright, field) = RB_BLACK;\
 492                                         RB_COLOR(tmp, field) = RB_RED;  \
 493                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
 494                                         tmp = RB_LEFT(parent, field);   \
 495                                 }                                       \
 496                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 497                                 RB_COLOR(parent, field) = RB_BLACK;     \
 498                                 if (RB_LEFT(tmp, field))                \
 499                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
 500                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
 501                                 elm = RB_ROOT(head);                    \
 502                                 break;                                  \
 503                         }                                               \
 504                 }                                                       \
 505         }                                                               \
 506         if (elm)                                                        \
 507                 RB_COLOR(elm, field) = RB_BLACK;                        \
 508 }                                                                       \
 509                                                                         \
 510 struct type *                                                           \
 511 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
 512 {                                                                       \
 513         struct type *child, *parent, *old = elm;                        \
 514         int color;                                                      \
 515         if (RB_LEFT(elm, field) == NULL)                                \
 516                 child = RB_RIGHT(elm, field);                           \
 517         else if (RB_RIGHT(elm, field) == NULL)                          \
 518                 child = RB_LEFT(elm, field);                            \
 519         else {                                                          \
 520                 struct type *left;                                      \
 521                 elm = RB_RIGHT(elm, field);                             \
 522                 while ((left = RB_LEFT(elm, field)))                    \
 523                         elm = left;                                     \
 524                 child = RB_RIGHT(elm, field);                           \
 525                 parent = RB_PARENT(elm, field);                         \
 526                 color = RB_COLOR(elm, field);                           \
 527                 if (child)                                              \
 528                         RB_PARENT(child, field) = parent;               \
 529                 if (parent) {                                           \
 530                         if (RB_LEFT(parent, field) == elm)              \
 531                                 RB_LEFT(parent, field) = child;         \
 532                         else                                            \
 533                                 RB_RIGHT(parent, field) = child;        \
 534                         RB_AUGMENT(parent);                             \
 535                 } else                                                  \
 536                         RB_ROOT(head) = child;                          \
 537                 if (RB_PARENT(elm, field) == old)                       \
 538                         parent = elm;                                   \
 539                 (elm)->field = (old)->field;                            \
 540                 if (RB_PARENT(old, field)) {                            \
 541                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
 542                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
 543                         else                                            \
 544                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
 545                         RB_AUGMENT(RB_PARENT(old, field));              \
 546                 } else                                                  \
 547                         RB_ROOT(head) = elm;                            \
 548                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
 549                 if (RB_RIGHT(old, field))                               \
 550                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
 551                 if (parent) {                                           \
 552                         left = parent;                                  \
 553                         do {                                            \
 554                                 RB_AUGMENT(left);                       \
 555                         } while ((left = RB_PARENT(left, field)));      \
 556                 }                                                       \
 557                 goto color;                                             \
 558         }                                                               \
 559         parent = RB_PARENT(elm, field);                                 \
 560         color = RB_COLOR(elm, field);                                   \
 561         if (child)                                                      \
 562                 RB_PARENT(child, field) = parent;                       \
 563         if (parent) {                                                   \
 564                 if (RB_LEFT(parent, field) == elm)                      \
 565                         RB_LEFT(parent, field) = child;                 \
 566                 else                                                    \
 567                         RB_RIGHT(parent, field) = child;                \
 568                 RB_AUGMENT(parent);                                     \
 569         } else                                                          \
 570                 RB_ROOT(head) = child;                                  \
 571 color:                                                                  \
 572         if (color == RB_BLACK)                                          \
 573                 name##_RB_REMOVE_COLOR(head, parent, child);            \
 574         return (old);                                                   \
 575 }                                                                       \
 576                                                                         \
 577 /* Inserts a node into the RB tree */                                   \
 578 struct type *                                                           \
 579 name##_RB_INSERT(struct name *head, struct type *elm)                   \
 580 {                                                                       \
 581         struct type *tmp;                                               \
 582         struct type *parent = NULL;                                     \
 583         int comp = 0;                                                   \
 584         tmp = RB_ROOT(head);                                            \
 585         while (tmp) {                                                   \
 586                 parent = tmp;                                           \
 587                 comp = (cmp)(elm, parent);                              \
 588                 if (comp < 0)                                           \
 589                         tmp = RB_LEFT(tmp, field);                      \
 590                 else if (comp > 0)                                      \
 591                         tmp = RB_RIGHT(tmp, field);                     \
 592                 else                                                    \
 593                         return (tmp);                                   \
 594         }                                                               \
 595         RB_SET(elm, parent, field);                                     \
 596         if (parent != NULL) {                                           \
 597                 if (comp < 0)                                           \
 598                         RB_LEFT(parent, field) = elm;                   \
 599                 else                                                    \
 600                         RB_RIGHT(parent, field) = elm;                  \
 601                 RB_AUGMENT(parent);                                     \
 602         } else                                                          \
 603                 RB_ROOT(head) = elm;                                    \
 604         name##_RB_INSERT_COLOR(head, elm);                              \
 605         return (NULL);                                                  \
 606 }                                                                       \
 607                                                                         \
 608 /* Finds the node with the same key as elm */                           \
 609 struct type *                                                           \
 610 name##_RB_FIND(struct name *head, struct type *elm)                     \
 611 {                                                                       \
 612         struct type *tmp = RB_ROOT(head);                               \
 613         int comp;                                                       \
 614         while (tmp) {                                                   \
 615                 comp = cmp(elm, tmp);                                   \
 616                 if (comp < 0)                                           \
 617                         tmp = RB_LEFT(tmp, field);                      \
 618                 else if (comp > 0)                                      \
 619                         tmp = RB_RIGHT(tmp, field);                     \
 620                 else                                                    \
 621                         return (tmp);                                   \
 622         }                                                               \
 623         return (NULL);                                                  \
 624 }                                                                       \
 625                                                                         \
 626 struct type *                                                           \
 627 name##_RB_NEXT(struct type *elm)                                        \
 628 {                                                                       \
 629         if (RB_RIGHT(elm, field)) {                                     \
 630                 elm = RB_RIGHT(elm, field);                             \
 631                 while (RB_LEFT(elm, field))                             \
 632                         elm = RB_LEFT(elm, field);                      \
 633         } else {                                                        \
 634                 if (RB_PARENT(elm, field) &&                            \
 635                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
 636                         elm = RB_PARENT(elm, field);                    \
 637                 else {                                                  \
 638                         while (RB_PARENT(elm, field) &&                 \
 639                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
 640                                 elm = RB_PARENT(elm, field);            \
 641                         elm = RB_PARENT(elm, field);                    \
 642                 }                                                       \
 643         }                                                               \
 644         return (elm);                                                   \
 645 }                                                                       \
 646                                                                         \
 647 struct type *                                                           \
 648 name##_RB_MINMAX(struct name *head, int val)                            \
 649 {                                                                       \
 650         struct type *tmp = RB_ROOT(head);                               \
 651         struct type *parent = NULL;                                     \
 652         while (tmp) {                                                   \
 653                 parent = tmp;                                           \
 654                 if (val < 0)                                            \
 655                         tmp = RB_LEFT(tmp, field);                      \
 656                 else                                                    \
 657                         tmp = RB_RIGHT(tmp, field);                     \
 658         }                                                               \
 659         return (parent);                                                \
 660 }
 661
 662 #define RB_NEGINF       -1
 663 #define RB_INF  1
 664
 665 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
 666 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
 667 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
 668 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
 669 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
 670 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
 671
 672 #define RB_FOREACH(x, name, head)                                       \
 673         for ((x) = RB_MIN(name, head);                                  \
 674              (x) != NULL;                                               \
 675              (x) = name##_RB_NEXT(x))
 676
 677 #endif  /* _SYS_TREE_H_ */
 678 /*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
 679 /*
 680  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 681  * All rights reserved.
 682  *
 683  * Redistribution and use in source and binary forms, with or without
 684  * modification, are permitted provided that the following conditions
 685  * are met:
 686  * 1. Redistributions of source code must retain the above copyright
 687  *    notice, this list of conditions and the following disclaimer.
 688  * 2. Redistributions in binary form must reproduce the above copyright
 689  *    notice, this list of conditions and the following disclaimer in the
 690  *    documentation and/or other materials provided with the distribution.
 691  *
 692  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 693  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 694  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 695  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 696  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 697  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 698  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 699  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 700  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 701  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 702  */
 703
 704 #ifndef _SYS_TREE_H_
 705 #define _SYS_TREE_H_
 706
 707 /*
 708  * This file defines data structures for different types of trees:
 709  * splay trees and red-black trees.
 710  *
 711  * A splay tree is a self-organizing data structure.  Every operation
 712  * on the tree causes a splay to happen.  The splay moves the requested
 713  * node to the root of the tree and partly rebalances it.
 714  *
 715  * This has the benefit that request locality causes faster lookups as
 716  * the requested nodes move to the top of the tree.  On the other hand,
 717  * every lookup causes memory writes.
 718  *
 719  * The Balance Theorem bounds the total access time for m operations
 720  * and n inserts on an initially empty tree as O((m + n)lg n).  The
 721  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
 722  *
 723  * A red-black tree is a binary search tree with the node color as an
 724  * extra attribute.  It fulfills a set of conditions:
 725  *      - every search path from the root to a leaf consists of the
 726  *        same number of black nodes,
 727  *      - each red node (except for the root) has a black parent,
 728  *      - each leaf node is black.
 729  *
 730  * Every operation on a red-black tree is bounded as O(lg n).
 731  * The maximum height of a red-black tree is 2lg (n+1).
 732  */
 733
 734 #define SPLAY_HEAD(name, type)                                          \
 735 struct name {                                                           \
 736         struct type *sph_root; /* root of the tree */                   \
 737 }
 738
 739 #define SPLAY_INITIALIZER(root)                                         \
 740         { NULL }
 741
 742 #define SPLAY_INIT(root) do {                                           \
 743         (root)->sph_root = NULL;                                        \
 744 } while (0)
 745
 746 #define SPLAY_ENTRY(type)                                               \
 747 struct {                                                                \
 748         struct type *spe_left; /* left element */                       \
 749         struct type *spe_right; /* right element */                     \
 750 }
 751
 752 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
 753 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
 754 #define SPLAY_ROOT(head)                (head)->sph_root
 755 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
 756
 757 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
 758 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
 759         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
 760         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 761         (head)->sph_root = tmp;                                         \
 762 } while (0)
 763
 764 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
 765         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
 766         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 767         (head)->sph_root = tmp;                                         \
 768 } while (0)
 769
 770 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
 771         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 772         tmp = (head)->sph_root;                                         \
 773         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
 774 } while (0)
 775
 776 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
 777         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 778         tmp = (head)->sph_root;                                         \
 779         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
 780 } while (0)
 781
 782 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
 783         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
 784         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
 785         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
 786         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
 787 } while (0)
 788
 789 /* Generates prototypes and inline functions */
 790
 791 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
 792 void name##_SPLAY(struct name *, struct type *);                        \
 793 void name##_SPLAY_MINMAX(struct name *, int);                           \
 794 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
 795 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
 796                                                                         \
 797 /* Finds the node with the same key as elm */                           \
 798 static __inline struct type *                                           \
 799 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
 800 {                                                                       \
 801         if (SPLAY_EMPTY(head))                                          \
 802                 return(NULL);                                           \
 803         name##_SPLAY(head, elm);                                        \
 804         if ((cmp)(elm, (head)->sph_root) == 0)                          \
 805                 return (head->sph_root);                                \
 806         return (NULL);                                                  \
 807 }                                                                       \
 808                                                                         \
 809 static __inline struct type *                                           \
 810 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
 811 {                                                                       \
 812         name##_SPLAY(head, elm);                                        \
 813         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
 814                 elm = SPLAY_RIGHT(elm, field);                          \
 815                 while (SPLAY_LEFT(elm, field) != NULL) {                \
 816                         elm = SPLAY_LEFT(elm, field);                   \
 817                 }                                                       \
 818         } else                                                          \
 819                 elm = NULL;                                             \
 820         return (elm);                                                   \
 821 }                                                                       \
 822                                                                         \
 823 static __inline struct type *                                           \
 824 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
 825 {                                                                       \
 826         name##_SPLAY_MINMAX(head, val);                                 \
 827         return (SPLAY_ROOT(head));                                      \
 828 }
 829
 830 /* Main splay operation.
 831  * Moves node close to the key of elm to top
 832  */
 833 #define SPLAY_GENERATE(name, type, field, cmp)                          \
 834 struct type *                                                           \
 835 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
 836 {                                                                       \
 837     if (SPLAY_EMPTY(head)) {                                            \
 838             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
 839     } else {                                                            \
 840             int __comp;                                                 \
 841             name##_SPLAY(head, elm);                                    \
 842             __comp = (cmp)(elm, (head)->sph_root);                      \
 843             if(__comp < 0) {                                            \
 844                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
 845                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
 846                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
 847             } else if (__comp > 0) {                                    \
 848                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
 849                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
 850                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
 851             } else                                                      \
 852                     return ((head)->sph_root);                          \
 853     }                                                                   \
 854     (head)->sph_root = (elm);                                           \
 855     return (NULL);                                                      \
 856 }                                                                       \
 857                                                                         \
 858 struct type *                                                           \
 859 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
 860 {                                                                       \
 861         struct type *__tmp;                                             \
 862         if (SPLAY_EMPTY(head))                                          \
 863                 return (NULL);                                          \
 864         name##_SPLAY(head, elm);                                        \
 865         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
 866                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
 867                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
 868                 } else {                                                \
 869                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 870                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
 871                         name##_SPLAY(head, elm);                        \
 872                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
 873                 }                                                       \
 874                 return (elm);                                           \
 875         }                                                               \
 876         return (NULL);                                                  \
 877 }                                                                       \
 878                                                                         \
 879 void                                                                    \
 880 name##_SPLAY(struct name *head, struct type *elm)                       \
 881 {                                                                       \
 882         struct type __node, *__left, *__right, *__tmp;                  \
 883         int __comp;                                                     \
 884 \
 885         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 886         __left = __right = &__node;                                     \
 887 \
 888         while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
 889                 if (__comp < 0) {                                       \
 890                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 891                         if (__tmp == NULL)                              \
 892                                 break;                                  \
 893                         if ((cmp)(elm, __tmp) < 0){                     \
 894                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 895                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 896                                         break;                          \
 897                         }                                               \
 898                         SPLAY_LINKLEFT(head, __right, field);           \
 899                 } else if (__comp > 0) {                                \
 900                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 901                         if (__tmp == NULL)                              \
 902                                 break;                                  \
 903                         if ((cmp)(elm, __tmp) > 0){                     \
 904                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 905                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 906                                         break;                          \
 907                         }                                               \
 908                         SPLAY_LINKRIGHT(head, __left, field);           \
 909                 }                                                       \
 910         }                                                               \
 911         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 912 }                                                                       \
 913                                                                         \
 914 /* Splay with either the minimum or the maximum element                 \
 915  * Used to find minimum or maximum element in tree.                     \
 916  */                                                                     \
 917 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 918 {                                                                       \
 919         struct type __node, *__left, *__right, *__tmp;                  \
 920 \
 921         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 922         __left = __right = &__node;                                     \
 923 \
 924         while (1) {                                                     \
 925                 if (__comp < 0) {                                       \
 926                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 927                         if (__tmp == NULL)                              \
 928                                 break;                                  \
 929                         if (__comp < 0){                                \
 930                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 931                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 932                                         break;                          \
 933                         }                                               \
 934                         SPLAY_LINKLEFT(head, __right, field);           \
 935                 } else if (__comp > 0) {                                \
 936                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 937                         if (__tmp == NULL)                              \
 938                                 break;                                  \
 939                         if (__comp > 0) {                               \
 940                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 941                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 942                                         break;                          \
 943                         }                                               \
 944                         SPLAY_LINKRIGHT(head, __left, field);           \
 945                 }                                                       \
 946         }                                                               \
 947         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 948 }
 949
 950 #define SPLAY_NEGINF    -1
 951 #define SPLAY_INF       1
 952
 953 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 954 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 955 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 956 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 957 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 958                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 959 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 960                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 961
 962 #define SPLAY_FOREACH(x, name, head)                                    \
 963         for ((x) = SPLAY_MIN(name, head);                               \
 964              (x) != NULL;                                               \
 965              (x) = SPLAY_NEXT(name, head, x))
 966
 967 /* Macros that define a red-back tree */
 968 #define RB_HEAD(name, type)                                             \
 969 struct name {                                                           \
 970         struct type *rbh_root; /* root of the tree */                   \
 971 }
 972
 973 #define RB_INITIALIZER(root)                                            \
 974         { NULL }
 975
 976 #define RB_INIT(root) do {                                              \
 977         (root)->rbh_root = NULL;                                        \
 978 } while (0)
 979
 980 #define RB_BLACK        0
 981 #define RB_RED          1
 982 #define RB_ENTRY(type)                                                  \
 983 struct {                                                                \
 984         struct type *rbe_left;          /* left element */              \
 985         struct type *rbe_right;         /* right element */             \
 986         struct type *rbe_parent;        /* parent element */            \
 987         int rbe_color;                  /* node color */                \
 988 }
 989
 990 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
 991 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
 992 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
 993 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
 994 #define RB_ROOT(head)                   (head)->rbh_root
 995 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 996
 997 #define RB_SET(elm, parent, field) do {                                 \
 998         RB_PARENT(elm, field) = parent;                                 \
 999         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
1000         RB_COLOR(elm, field) = RB_RED;                                  \
1001 } while (0)
1002
1003 #define RB_SET_BLACKRED(black, red, field) do {                         \
1004         RB_COLOR(black, field) = RB_BLACK;                              \
1005         RB_COLOR(red, field) = RB_RED;                                  \
1006 } while (0)
1007
1008 #ifndef RB_AUGMENT
1009 #define RB_AUGMENT(x)
1010 #endif
1011
1012 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
1013         (tmp) = RB_RIGHT(elm, field);                                   \
1014         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
1015                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
1016         }                                                               \
1017         RB_AUGMENT(elm);                                                \
1018         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
1019                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
1020                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
1021                 else                                                    \
1022                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1023         } else                                                          \
1024                 (head)->rbh_root = (tmp);                               \
1025         RB_LEFT(tmp, field) = (elm);                                    \
1026         RB_PARENT(elm, field) = (tmp);                                  \
1027         RB_AUGMENT(tmp);                                                \
1028         if ((RB_PARENT(tmp, field)))                                    \
1029                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
1030 } while (0)
1031
1032 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
1033         (tmp) = RB_LEFT(elm, field);                                    \
1034         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
1035                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
1036         }                                                               \
1037         RB_AUGMENT(elm);                                                \
1038         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
1039                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
1040                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
1041                 else                                                    \
1042                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
1043         } else                                                          \
1044                 (head)->rbh_root = (tmp);                               \
1045         RB_RIGHT(tmp, field) = (elm);                                   \
1046         RB_PARENT(elm, field) = (tmp);                                  \
1047         RB_AUGMENT(tmp);                                                \
1048         if ((RB_PARENT(tmp, field)))                                    \
1049                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
1050 } while (0)
1051
1052 /* Generates prototypes and inline functions */
1053 #define RB_PROTOTYPE(name, type, field, cmp)                            \
1054 void name##_RB_INSERT_COLOR(struct name *, struct type *);      \
1055 void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
1056 struct type *name##_RB_REMOVE(struct name *, struct type *);            \
1057 struct type *name##_RB_INSERT(struct name *, struct type *);            \
1058 struct type *name##_RB_FIND(struct name *, struct type *);              \
1059 struct type *name##_RB_NEXT(struct type *);                             \
1060 struct type *name##_RB_MINMAX(struct name *, int);                      \
1061                                                                         \
1062
1063 /* Main rb operation.
1064  * Moves node close to the key of elm to top
1065  */
1066 #define RB_GENERATE(name, type, field, cmp)                             \
1067 void                                                                    \
1068 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
1069 {                                                                       \
1070         struct type *parent, *gparent, *tmp;                            \
1071         while ((parent = RB_PARENT(elm, field)) &&                      \
1072             RB_COLOR(parent, field) == RB_RED) {                        \
1073                 gparent = RB_PARENT(parent, field);                     \
1074                 if (parent == RB_LEFT(gparent, field)) {                \
1075                         tmp = RB_RIGHT(gparent, field);                 \
1076                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
1077                                 RB_COLOR(tmp, field) = RB_BLACK;        \
1078                                 RB_SET_BLACKRED(parent, gparent, field);\
1079                                 elm = gparent;                          \
1080                                 continue;                               \
1081                         }                                               \
1082                         if (RB_RIGHT(parent, field) == elm) {           \
1083                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
1084                                 tmp = parent;                           \
1085                                 parent = elm;                           \
1086                                 elm = tmp;                              \
1087                         }                                               \
1088                         RB_SET_BLACKRED(parent, gparent, field);        \
1089                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
1090                 } else {                                                \
1091                         tmp = RB_LEFT(gparent, field);                  \
1092                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
1093                                 RB_COLOR(tmp, field) = RB_BLACK;        \
1094                                 RB_SET_BLACKRED(parent, gparent, field);\
1095                                 elm = gparent;                          \
1096                                 continue;                               \
1097                         }                                               \
1098                         if (RB_LEFT(parent, field) == elm) {            \
1099                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
1100                                 tmp = parent;                           \
1101                                 parent = elm;                           \
1102                                 elm = tmp;                              \
1103                         }                                               \
1104                         RB_SET_BLACKRED(parent, gparent, field);        \
1105                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
1106                 }                                                       \
1107         }                                                               \
1108         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
1109 }                                                                       \
1110                                                                         \
1111 void                                                                    \
1112 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
1113 {                                                                       \
1114         struct type *tmp;                                               \
1115         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
1116             elm != RB_ROOT(head)) {                                     \
1117                 if (RB_LEFT(parent, field) == elm) {                    \
1118                         tmp = RB_RIGHT(parent, field);                  \
1119                         if (RB_COLOR(tmp, field) == RB_RED) {           \
1120                                 RB_SET_BLACKRED(tmp, parent, field);    \
1121                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
1122                                 tmp = RB_RIGHT(parent, field);          \
1123                         }                                               \
1124                         if ((RB_LEFT(tmp, field) == NULL ||             \
1125                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1126                             (RB_RIGHT(tmp, field) == NULL ||            \
1127                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1128                                 RB_COLOR(tmp, field) = RB_RED;          \
1129                                 elm = parent;                           \
1130                                 parent = RB_PARENT(elm, field);         \
1131                         } else {                                        \
1132                                 if (RB_RIGHT(tmp, field) == NULL ||     \
1133                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
1134                                         struct type *oleft;             \
1135                                         if ((oleft = RB_LEFT(tmp, field)))\
1136                                                 RB_COLOR(oleft, field) = RB_BLACK;\
1137                                         RB_COLOR(tmp, field) = RB_RED;  \
1138                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
1139                                         tmp = RB_RIGHT(parent, field);  \
1140                                 }                                       \
1141                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1142                                 RB_COLOR(parent, field) = RB_BLACK;     \
1143                                 if (RB_RIGHT(tmp, field))               \
1144                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
1145                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
1146                                 elm = RB_ROOT(head);                    \
1147                                 break;                                  \
1148                         }                                               \
1149                 } else {                                                \
1150                         tmp = RB_LEFT(parent, field);                   \
1151                         if (RB_COLOR(tmp, field) == RB_RED) {           \
1152                                 RB_SET_BLACKRED(tmp, parent, field);    \
1153                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
1154                                 tmp = RB_LEFT(parent, field);           \
1155                         }                                               \
1156                         if ((RB_LEFT(tmp, field) == NULL ||             \
1157                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
1158                             (RB_RIGHT(tmp, field) == NULL ||            \
1159                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
1160                                 RB_COLOR(tmp, field) = RB_RED;          \
1161                                 elm = parent;                           \
1162                                 parent = RB_PARENT(elm, field);         \
1163                         } else {                                        \
1164                                 if (RB_LEFT(tmp, field) == NULL ||      \
1165                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
1166                                         struct type *oright;            \
1167                                         if ((oright = RB_RIGHT(tmp, field)))\
1168                                                 RB_COLOR(oright, field) = RB_BLACK;\
1169                                         RB_COLOR(tmp, field) = RB_RED;  \
1170                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
1171                                         tmp = RB_LEFT(parent, field);   \
1172                                 }                                       \
1173                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
1174                                 RB_COLOR(parent, field) = RB_BLACK;     \
1175                                 if (RB_LEFT(tmp, field))                \
1176                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
1177                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
1178                                 elm = RB_ROOT(head);                    \
1179                                 break;                                  \
1180                         }                                               \
1181                 }                                                       \
1182         }                                                               \
1183         if (elm)                                                        \
1184                 RB_COLOR(elm, field) = RB_BLACK;                        \
1185 }                                                                       \
1186                                                                         \
1187 struct type *                                                           \
1188 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
1189 {                                                                       \
1190         struct type *child, *parent, *old = elm;                        \
1191         int color;                                                      \
1192         if (RB_LEFT(elm, field) == NULL)                                \
1193                 child = RB_RIGHT(elm, field);                           \
1194         else if (RB_RIGHT(elm, field) == NULL)                          \
1195                 child = RB_LEFT(elm, field);                            \
1196         else {                                                          \
1197                 struct type *left;                                      \
1198                 elm = RB_RIGHT(elm, field);                             \
1199                 while ((left = RB_LEFT(elm, field)))                    \
1200                         elm = left;                                     \
1201                 child = RB_RIGHT(elm, field);                           \
1202                 parent = RB_PARENT(elm, field);                         \
1203                 color = RB_COLOR(elm, field);                           \
1204                 if (child)                                              \
1205                         RB_PARENT(child, field) = parent;               \
1206                 if (parent) {                                           \
1207                         if (RB_LEFT(parent, field) == elm)              \
1208                                 RB_LEFT(parent, field) = child;         \
1209                         else                                            \
1210                                 RB_RIGHT(parent, field) = child;        \
1211                         RB_AUGMENT(parent);                             \
1212                 } else                                                  \
1213                         RB_ROOT(head) = child;                          \
1214                 if (RB_PARENT(elm, field) == old)                       \
1215                         parent = elm;                                   \
1216                 (elm)->field = (old)->field;                            \
1217                 if (RB_PARENT(old, field)) {                            \
1218                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
1219                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
1220                         else                                            \
1221                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
1222                         RB_AUGMENT(RB_PARENT(old, field));              \
1223                 } else                                                  \
1224                         RB_ROOT(head) = elm;                            \
1225                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
1226                 if (RB_RIGHT(old, field))                               \
1227                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
1228                 if (parent) {                                           \
1229                         left = parent;                                  \
1230                         do {                                            \
1231                                 RB_AUGMENT(left);                       \
1232                         } while ((left = RB_PARENT(left, field)));      \
1233                 }                                                       \
1234                 goto color;                                             \
1235         }                                                               \
1236         parent = RB_PARENT(elm, field);                                 \
1237         color = RB_COLOR(elm, field);                                   \
1238         if (child)                                                      \
1239                 RB_PARENT(child, field) = parent;                       \
1240         if (parent) {                                                   \
1241                 if (RB_LEFT(parent, field) == elm)                      \
1242                         RB_LEFT(parent, field) = child;                 \
1243                 else                                                    \
1244                         RB_RIGHT(parent, field) = child;                \
1245                 RB_AUGMENT(parent);                                     \
1246         } else                                                          \
1247                 RB_ROOT(head) = child;                                  \
1248 color:                                                                  \
1249         if (color == RB_BLACK)                                          \
1250                 name##_RB_REMOVE_COLOR(head, parent, child);            \
1251         return (old);                                                   \
1252 }                                                                       \
1253                                                                         \
1254 /* Inserts a node into the RB tree */                                   \
1255 struct type *                                                           \
1256 name##_RB_INSERT(struct name *head, struct type *elm)                   \
1257 {                                                                       \
1258         struct type *tmp;                                               \
1259         struct type *parent = NULL;                                     \
1260         int comp = 0;                                                   \
1261         tmp = RB_ROOT(head);                                            \
1262         while (tmp) {                                                   \
1263                 parent = tmp;                                           \
1264                 comp = (cmp)(elm, parent);                              \
1265                 if (comp < 0)                                           \
1266                         tmp = RB_LEFT(tmp, field);                      \
1267                 else if (comp > 0)                                      \
1268                         tmp = RB_RIGHT(tmp, field);                     \
1269                 else                                                    \
1270                         return (tmp);                                   \
1271         }                                                               \
1272         RB_SET(elm, parent, field);                                     \
1273         if (parent != NULL) {                                           \
1274                 if (comp < 0)                                           \
1275                         RB_LEFT(parent, field) = elm;                   \
1276                 else                                                    \
1277                         RB_RIGHT(parent, field) = elm;                  \
1278                 RB_AUGMENT(parent);                                     \
1279         } else                                                          \
1280                 RB_ROOT(head) = elm;                                    \
1281         name##_RB_INSERT_COLOR(head, elm);                              \
1282         return (NULL);                                                  \
1283 }                                                                       \
1284                                                                         \
1285 /* Finds the node with the same key as elm */                           \
1286 struct type *                                                           \
1287 name##_RB_FIND(struct name *head, struct type *elm)                     \
1288 {                                                                       \
1289         struct type *tmp = RB_ROOT(head);                               \
1290         int comp;                                                       \
1291         while (tmp) {                                                   \
1292                 comp = cmp(elm, tmp);                                   \
1293                 if (comp < 0)                                           \
1294                         tmp = RB_LEFT(tmp, field);                      \
1295                 else if (comp > 0)                                      \
1296                         tmp = RB_RIGHT(tmp, field);                     \
1297                 else                                                    \
1298                         return (tmp);                                   \
1299         }                                                               \
1300         return (NULL);                                                  \
1301 }                                                                       \
1302                                                                         \
1303 struct type *                                                           \
1304 name##_RB_NEXT(struct type *elm)                                        \
1305 {                                                                       \
1306         if (RB_RIGHT(elm, field)) {                                     \
1307                 elm = RB_RIGHT(elm, field);                             \
1308                 while (RB_LEFT(elm, field))                             \
1309                         elm = RB_LEFT(elm, field);                      \
1310         } else {                                                        \
1311                 if (RB_PARENT(elm, field) &&                            \
1312                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
1313                         elm = RB_PARENT(elm, field);                    \
1314                 else {                                                  \
1315                         while (RB_PARENT(elm, field) &&                 \
1316                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
1317                                 elm = RB_PARENT(elm, field);            \
1318                         elm = RB_PARENT(elm, field);                    \
1319                 }                                                       \
1320         }                                                               \
1321         return (elm);                                                   \
1322 }                                                                       \
1323                                                                         \
1324 struct type *                                                           \
1325 name##_RB_MINMAX(struct name *head, int val)                            \
1326 {                                                                       \
1327         struct type *tmp = RB_ROOT(head);                               \
1328         struct type *parent = NULL;                                     \
1329         while (tmp) {                                                   \
1330                 parent = tmp;                                           \
1331                 if (val < 0)                                            \
1332                         tmp = RB_LEFT(tmp, field);                      \
1333                 else                                                    \
1334                         tmp = RB_RIGHT(tmp, field);                     \
1335         }                                                               \
1336         return (parent);                                                \
1337 }
1338
1339 #define RB_NEGINF       -1
1340 #define RB_INF  1
1341
1342 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
1343 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
1344 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
1345 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
1346 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
1347 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
1348
1349 #define RB_FOREACH(x, name, head)                                       \
1350         for ((x) = RB_MIN(name, head);                                  \
1351              (x) != NULL;                                               \
1352              (x) = name##_RB_NEXT(x))
1353
1354 #endif  /* _SYS_TREE_H_ */