third_party/bsdtrees/tree.h

   1 /*  $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
   2 /*
   3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #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-black 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) do {} while (0)
 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   RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
 378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)     \
 379   RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
 380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)   \
 381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);   \
 382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
 383 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
 384 attr struct type *name##_RB_INSERT(struct name *, struct type *); \
 385 attr struct type *name##_RB_FIND(struct name *, struct type *);   \
 386 attr struct type *name##_RB_NFIND(struct name *, struct type *);  \
 387 attr struct type *name##_RB_NEXT(struct type *);      \
 388 attr struct type *name##_RB_PREV(struct type *);      \
 389 attr struct type *name##_RB_MINMAX(struct name *, int);     \
 390                   \
 391
 392 /* Main rb operation.
 393  * Moves node close to the key of elm to top
 394  */
 395 #define RB_GENERATE(name, type, field, cmp)       \
 396   RB_GENERATE_INTERNAL(name, type, field, cmp,)
 397 #define RB_GENERATE_STATIC(name, type, field, cmp)      \
 398   RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
 399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)    \
 400 attr void               \
 401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)   \
 402 {                 \
 403   struct type *parent, *gparent, *tmp;        \
 404   while ((parent = RB_PARENT(elm, field)) &&      \
 405       RB_COLOR(parent, field) == RB_RED) {      \
 406     gparent = RB_PARENT(parent, field);     \
 407     if (parent == RB_LEFT(gparent, field)) {    \
 408       tmp = RB_RIGHT(gparent, field);     \
 409       if (tmp && RB_COLOR(tmp, field) == RB_RED) {  \
 410         RB_COLOR(tmp, field) = RB_BLACK;  \
 411         RB_SET_BLACKRED(parent, gparent, field);\
 412         elm = gparent;        \
 413         continue;       \
 414       }           \
 415       if (RB_RIGHT(parent, field) == elm) {   \
 416         RB_ROTATE_LEFT(head, parent, tmp, field);\
 417         tmp = parent;       \
 418         parent = elm;       \
 419         elm = tmp;        \
 420       }           \
 421       RB_SET_BLACKRED(parent, gparent, field);  \
 422       RB_ROTATE_RIGHT(head, gparent, tmp, field); \
 423     } else {            \
 424       tmp = RB_LEFT(gparent, field);      \
 425       if (tmp && RB_COLOR(tmp, field) == RB_RED) {  \
 426         RB_COLOR(tmp, field) = RB_BLACK;  \
 427         RB_SET_BLACKRED(parent, gparent, field);\
 428         elm = gparent;        \
 429         continue;       \
 430       }           \
 431       if (RB_LEFT(parent, field) == elm) {    \
 432         RB_ROTATE_RIGHT(head, parent, tmp, field);\
 433         tmp = parent;       \
 434         parent = elm;       \
 435         elm = tmp;        \
 436       }           \
 437       RB_SET_BLACKRED(parent, gparent, field);  \
 438       RB_ROTATE_LEFT(head, gparent, tmp, field);  \
 439     }             \
 440   }               \
 441   RB_COLOR(head->rbh_root, field) = RB_BLACK;     \
 442 }                 \
 443                   \
 444 attr void               \
 445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 446 {                 \
 447   struct type *tmp;           \
 448   while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
 449       elm != RB_ROOT(head)) {         \
 450     if (RB_LEFT(parent, field) == elm) {      \
 451       tmp = RB_RIGHT(parent, field);      \
 452       if (RB_COLOR(tmp, field) == RB_RED) {   \
 453         RB_SET_BLACKRED(tmp, parent, field);  \
 454         RB_ROTATE_LEFT(head, parent, tmp, field);\
 455         tmp = RB_RIGHT(parent, field);    \
 456       }           \
 457       if ((RB_LEFT(tmp, field) == NULL ||   \
 458           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 459           (RB_RIGHT(tmp, field) == NULL ||    \
 460           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 461         RB_COLOR(tmp, field) = RB_RED;    \
 462         elm = parent;       \
 463         parent = RB_PARENT(elm, field);   \
 464       } else {          \
 465         if (RB_RIGHT(tmp, field) == NULL || \
 466             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
 467           struct type *oleft;   \
 468           if ((oleft = RB_LEFT(tmp, field)))\
 469             RB_COLOR(oleft, field) = RB_BLACK;\
 470           RB_COLOR(tmp, field) = RB_RED;  \
 471           RB_ROTATE_RIGHT(head, tmp, oleft, field);\
 472           tmp = RB_RIGHT(parent, field);  \
 473         }         \
 474         RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 475         RB_COLOR(parent, field) = RB_BLACK; \
 476         if (RB_RIGHT(tmp, field))   \
 477           RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
 478         RB_ROTATE_LEFT(head, parent, tmp, field);\
 479         elm = RB_ROOT(head);      \
 480         break;          \
 481       }           \
 482     } else {            \
 483       tmp = RB_LEFT(parent, field);     \
 484       if (RB_COLOR(tmp, field) == RB_RED) {   \
 485         RB_SET_BLACKRED(tmp, parent, field);  \
 486         RB_ROTATE_RIGHT(head, parent, tmp, field);\
 487         tmp = RB_LEFT(parent, field);   \
 488       }           \
 489       if ((RB_LEFT(tmp, field) == NULL ||   \
 490           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
 491           (RB_RIGHT(tmp, field) == NULL ||    \
 492           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
 493         RB_COLOR(tmp, field) = RB_RED;    \
 494         elm = parent;       \
 495         parent = RB_PARENT(elm, field);   \
 496       } else {          \
 497         if (RB_LEFT(tmp, field) == NULL ||  \
 498             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
 499           struct type *oright;    \
 500           if ((oright = RB_RIGHT(tmp, field)))\
 501             RB_COLOR(oright, field) = RB_BLACK;\
 502           RB_COLOR(tmp, field) = RB_RED;  \
 503           RB_ROTATE_LEFT(head, tmp, oright, field);\
 504           tmp = RB_LEFT(parent, field); \
 505         }         \
 506         RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
 507         RB_COLOR(parent, field) = RB_BLACK; \
 508         if (RB_LEFT(tmp, field))    \
 509           RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
 510         RB_ROTATE_RIGHT(head, parent, tmp, field);\
 511         elm = RB_ROOT(head);      \
 512         break;          \
 513       }           \
 514     }             \
 515   }               \
 516   if (elm)              \
 517     RB_COLOR(elm, field) = RB_BLACK;      \
 518 }                 \
 519                   \
 520 attr struct type *              \
 521 name##_RB_REMOVE(struct name *head, struct type *elm)     \
 522 {                 \
 523   struct type *child, *parent, *old = elm;      \
 524   int color;              \
 525   if (RB_LEFT(elm, field) == NULL)        \
 526     child = RB_RIGHT(elm, field);       \
 527   else if (RB_RIGHT(elm, field) == NULL)        \
 528     child = RB_LEFT(elm, field);        \
 529   else {                \
 530     struct type *left;          \
 531     elm = RB_RIGHT(elm, field);       \
 532     while ((left = RB_LEFT(elm, field)))      \
 533       elm = left;         \
 534     child = RB_RIGHT(elm, field);       \
 535     parent = RB_PARENT(elm, field);       \
 536     color = RB_COLOR(elm, field);       \
 537     if (child)            \
 538       RB_PARENT(child, field) = parent;   \
 539     if (parent) {           \
 540       if (RB_LEFT(parent, field) == elm)    \
 541         RB_LEFT(parent, field) = child;   \
 542       else            \
 543         RB_RIGHT(parent, field) = child;  \
 544       RB_AUGMENT(parent);       \
 545     } else              \
 546       RB_ROOT(head) = child;        \
 547     if (RB_PARENT(elm, field) == old)     \
 548       parent = elm;         \
 549     (elm)->field = (old)->field;        \
 550     if (RB_PARENT(old, field)) {        \
 551       if (RB_LEFT(RB_PARENT(old, field), field) == old)\
 552         RB_LEFT(RB_PARENT(old, field), field) = elm;\
 553       else            \
 554         RB_RIGHT(RB_PARENT(old, field), field) = elm;\
 555       RB_AUGMENT(RB_PARENT(old, field));    \
 556     } else              \
 557       RB_ROOT(head) = elm;        \
 558     RB_PARENT(RB_LEFT(old, field), field) = elm;    \
 559     if (RB_RIGHT(old, field))       \
 560       RB_PARENT(RB_RIGHT(old, field), field) = elm; \
 561     if (parent) {           \
 562       left = parent;          \
 563       do {            \
 564         RB_AUGMENT(left);     \
 565       } while ((left = RB_PARENT(left, field)));  \
 566     }             \
 567     goto color;           \
 568   }               \
 569   parent = RB_PARENT(elm, field);         \
 570   color = RB_COLOR(elm, field);         \
 571   if (child)              \
 572     RB_PARENT(child, field) = parent;     \
 573   if (parent) {             \
 574     if (RB_LEFT(parent, field) == elm)      \
 575       RB_LEFT(parent, field) = child;     \
 576     else              \
 577       RB_RIGHT(parent, field) = child;    \
 578     RB_AUGMENT(parent);         \
 579   } else                \
 580     RB_ROOT(head) = child;          \
 581 color:                  \
 582   if (color == RB_BLACK)            \
 583     name##_RB_REMOVE_COLOR(head, parent, child);    \
 584   return (old);             \
 585 }                 \
 586                   \
 587 /* Inserts a node into the RB tree */         \
 588 attr struct type *              \
 589 name##_RB_INSERT(struct name *head, struct type *elm)     \
 590 {                 \
 591   struct type *tmp;           \
 592   struct type *parent = NULL;         \
 593   int comp = 0;             \
 594   tmp = RB_ROOT(head);            \
 595   while (tmp) {             \
 596     parent = tmp;           \
 597     comp = (cmp)(elm, parent);        \
 598     if (comp < 0)           \
 599       tmp = RB_LEFT(tmp, field);      \
 600     else if (comp > 0)          \
 601       tmp = RB_RIGHT(tmp, field);     \
 602     else              \
 603       return (tmp);         \
 604   }               \
 605   RB_SET(elm, parent, field);         \
 606   if (parent != NULL) {           \
 607     if (comp < 0)           \
 608       RB_LEFT(parent, field) = elm;     \
 609     else              \
 610       RB_RIGHT(parent, field) = elm;      \
 611     RB_AUGMENT(parent);         \
 612   } else                \
 613     RB_ROOT(head) = elm;          \
 614   name##_RB_INSERT_COLOR(head, elm);        \
 615   return (NULL);              \
 616 }                 \
 617                   \
 618 /* Finds the node with the same key as elm */       \
 619 attr struct type *              \
 620 name##_RB_FIND(struct name *head, struct type *elm)     \
 621 {                 \
 622   struct type *tmp = RB_ROOT(head);       \
 623   int comp;             \
 624   while (tmp) {             \
 625     comp = cmp(elm, tmp);         \
 626     if (comp < 0)           \
 627       tmp = RB_LEFT(tmp, field);      \
 628     else if (comp > 0)          \
 629       tmp = RB_RIGHT(tmp, field);     \
 630     else              \
 631       return (tmp);         \
 632   }               \
 633   return (NULL);              \
 634 }                 \
 635                   \
 636 /* Finds the first node greater than or equal to the search key */  \
 637 attr struct type *              \
 638 name##_RB_NFIND(struct name *head, struct type *elm)      \
 639 {                 \
 640   struct type *tmp = RB_ROOT(head);       \
 641   struct type *res = NULL;          \
 642   int comp;             \
 643   while (tmp) {             \
 644     comp = cmp(elm, tmp);         \
 645     if (comp < 0) {           \
 646       res = tmp;          \
 647       tmp = RB_LEFT(tmp, field);      \
 648     }             \
 649     else if (comp > 0)          \
 650       tmp = RB_RIGHT(tmp, field);     \
 651     else              \
 652       return (tmp);         \
 653   }               \
 654   return (res);             \
 655 }                 \
 656                   \
 657 /* ARGSUSED */                \
 658 attr struct type *              \
 659 name##_RB_NEXT(struct type *elm)          \
 660 {                 \
 661   if (RB_RIGHT(elm, field)) {         \
 662     elm = RB_RIGHT(elm, field);       \
 663     while (RB_LEFT(elm, field))       \
 664       elm = RB_LEFT(elm, field);      \
 665   } else {              \
 666     if (RB_PARENT(elm, field) &&        \
 667         (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
 668       elm = RB_PARENT(elm, field);      \
 669     else {              \
 670       while (RB_PARENT(elm, field) &&     \
 671           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
 672         elm = RB_PARENT(elm, field);    \
 673       elm = RB_PARENT(elm, field);      \
 674     }             \
 675   }               \
 676   return (elm);             \
 677 }                 \
 678                   \
 679 /* ARGSUSED */                \
 680 attr struct type *              \
 681 name##_RB_PREV(struct type *elm)          \
 682 {                 \
 683   if (RB_LEFT(elm, field)) {          \
 684     elm = RB_LEFT(elm, field);        \
 685     while (RB_RIGHT(elm, field))        \
 686       elm = RB_RIGHT(elm, field);     \
 687   } else {              \
 688     if (RB_PARENT(elm, field) &&        \
 689         (elm == RB_RIGHT(RB_PARENT(elm, field), field)))  \
 690       elm = RB_PARENT(elm, field);      \
 691     else {              \
 692       while (RB_PARENT(elm, field) &&     \
 693           (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
 694         elm = RB_PARENT(elm, field);    \
 695       elm = RB_PARENT(elm, field);      \
 696     }             \
 697   }               \
 698   return (elm);             \
 699 }                 \
 700                   \
 701 attr struct type *              \
 702 name##_RB_MINMAX(struct name *head, int val)        \
 703 {                 \
 704   struct type *tmp = RB_ROOT(head);       \
 705   struct type *parent = NULL;         \
 706   while (tmp) {             \
 707     parent = tmp;           \
 708     if (val < 0)            \
 709       tmp = RB_LEFT(tmp, field);      \
 710     else              \
 711       tmp = RB_RIGHT(tmp, field);     \
 712   }               \
 713   return (parent);            \
 714 }
 715
 716 #define RB_NEGINF -1
 717 #define RB_INF  1
 718
 719 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
 720 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
 721 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
 722 #define RB_NFIND(name, x, y)  name##_RB_NFIND(x, y)
 723 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
 724 #define RB_PREV(name, x, y) name##_RB_PREV(y)
 725 #define RB_MIN(name, x)   name##_RB_MINMAX(x, RB_NEGINF)
 726 #define RB_MAX(name, x)   name##_RB_MINMAX(x, RB_INF)
 727
 728 #define RB_FOREACH(x, name, head)         \
 729   for ((x) = RB_MIN(name, head);          \
 730        (x) != NULL;           \
 731        (x) = name##_RB_NEXT(x))
 732
 733 #define RB_FOREACH_SAFE(x, name, head, y)       \
 734   for ((x) = RB_MIN(name, head);          \
 735       ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);    \
 736        (x) = (y))
 737
 738 #define RB_FOREACH_REVERSE(x, name, head)       \
 739   for ((x) = RB_MAX(name, head);          \
 740        (x) != NULL;           \
 741        (x) = name##_RB_PREV(x))
 742
 743 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)     \
 744   for ((x) = RB_MAX(name, head);          \
 745       ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);    \
 746        (x) = (y))
 747
 748 #endif  /* _SYS_TREE_H_ */