node/uv/tree.h

0001 /*-
0002  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
0003  * All rights reserved.
0004  *
0005  * Redistribution and use in source and binary forms, with or without
0006  * modification, are permitted provided that the following conditions
0007  * are met:
0008  * 1. Redistributions of source code must retain the above copyright
0009  *    notice, this list of conditions and the following disclaimer.
0010  * 2. Redistributions in binary form must reproduce the above copyright
0011  *    notice, this list of conditions and the following disclaimer in the
0012  *    documentation and/or other materials provided with the distribution.
0013  *
0014  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
0015  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0016  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
0017  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
0018  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
0019  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0020  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0021  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0022  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
0023  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0024  */
0025
0026 #ifndef  UV_TREE_H_
0027 #define  UV_TREE_H_
0028
0029 #ifndef UV__UNUSED
0030 # if __GNUC__
0031 #  define UV__UNUSED __attribute__((unused))
0032 # else
0033 #  define UV__UNUSED
0034 # endif
0035 #endif
0036
0037 /*
0038  * This file defines data structures for different types of trees:
0039  * splay trees and red-black trees.
0040  *
0041  * A splay tree is a self-organizing data structure.  Every operation
0042  * on the tree causes a splay to happen.  The splay moves the requested
0043  * node to the root of the tree and partly rebalances it.
0044  *
0045  * This has the benefit that request locality causes faster lookups as
0046  * the requested nodes move to the top of the tree.  On the other hand,
0047  * every lookup causes memory writes.
0048  *
0049  * The Balance Theorem bounds the total access time for m operations
0050  * and n inserts on an initially empty tree as O((m + n)lg n).  The
0051  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
0052  *
0053  * A red-black tree is a binary search tree with the node color as an
0054  * extra attribute.  It fulfills a set of conditions:
0055  *  - every search path from the root to a leaf consists of the
0056  *    same number of black nodes,
0057  *  - each red node (except for the root) has a black parent,
0058  *  - each leaf node is black.
0059  *
0060  * Every operation on a red-black tree is bounded as O(lg n).
0061  * The maximum height of a red-black tree is 2lg (n+1).
0062  */
0063
0064 #define SPLAY_HEAD(name, type)                                                \
0065 struct name {                                                                 \
0066   struct type *sph_root; /* root of the tree */                               \
0067 }
0068
0069 #define SPLAY_INITIALIZER(root)                                               \
0070   { NULL }
0071
0072 #define SPLAY_INIT(root) do {                                                 \
0073   (root)->sph_root = NULL;                                                    \
0074 } while (/*CONSTCOND*/ 0)
0075
0076 #define SPLAY_ENTRY(type)                                                     \
0077 struct {                                                                      \
0078   struct type *spe_left;          /* left element */                          \
0079   struct type *spe_right;         /* right element */                         \
0080 }
0081
0082 #define SPLAY_LEFT(elm, field)    (elm)->field.spe_left
0083 #define SPLAY_RIGHT(elm, field)   (elm)->field.spe_right
0084 #define SPLAY_ROOT(head)          (head)->sph_root
0085 #define SPLAY_EMPTY(head)         (SPLAY_ROOT(head) == NULL)
0086
0087 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
0088 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                             \
0089   SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);              \
0090   SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                 \
0091   (head)->sph_root = tmp;                                                     \
0092 } while (/*CONSTCOND*/ 0)
0093
0094 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                              \
0095   SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);              \
0096   SPLAY_LEFT(tmp, field) = (head)->sph_root;                                  \
0097   (head)->sph_root = tmp;                                                     \
0098 } while (/*CONSTCOND*/ 0)
0099
0100 #define SPLAY_LINKLEFT(head, tmp, field) do {                                 \
0101   SPLAY_LEFT(tmp, field) = (head)->sph_root;                                  \
0102   tmp = (head)->sph_root;                                                     \
0103   (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                     \
0104 } while (/*CONSTCOND*/ 0)
0105
0106 #define SPLAY_LINKRIGHT(head, tmp, field) do {                                \
0107   SPLAY_RIGHT(tmp, field) = (head)->sph_root;                                 \
0108   tmp = (head)->sph_root;                                                     \
0109   (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                    \
0110 } while (/*CONSTCOND*/ 0)
0111
0112 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {                   \
0113   SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field);             \
0114   SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);            \
0115   SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field);             \
0116   SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field);             \
0117 } while (/*CONSTCOND*/ 0)
0118
0119 /* Generates prototypes and inline functions */
0120
0121 #define SPLAY_PROTOTYPE(name, type, field, cmp)                               \
0122 void name##_SPLAY(struct name *, struct type *);                              \
0123 void name##_SPLAY_MINMAX(struct name *, int);                                 \
0124 struct type *name##_SPLAY_INSERT(struct name *, struct type *);               \
0125 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);               \
0126                                                                               \
0127 /* Finds the node with the same key as elm */                                 \
0128 static __inline struct type *                                                 \
0129 name##_SPLAY_FIND(struct name *head, struct type *elm)                        \
0130 {                                                                             \
0131   if (SPLAY_EMPTY(head))                                                      \
0132     return(NULL);                                                             \
0133   name##_SPLAY(head, elm);                                                    \
0134   if ((cmp)(elm, (head)->sph_root) == 0)                                      \
0135     return (head->sph_root);                                                  \
0136   return (NULL);                                                              \
0137 }                                                                             \
0138                                                                               \
0139 static __inline struct type *                                                 \
0140 name##_SPLAY_NEXT(struct name *head, struct type *elm)                        \
0141 {                                                                             \
0142   name##_SPLAY(head, elm);                                                    \
0143   if (SPLAY_RIGHT(elm, field) != NULL) {                                      \
0144     elm = SPLAY_RIGHT(elm, field);                                            \
0145     while (SPLAY_LEFT(elm, field) != NULL) {                                  \
0146       elm = SPLAY_LEFT(elm, field);                                           \
0147     }                                                                         \
0148   } else                                                                      \
0149     elm = NULL;                                                               \
0150   return (elm);                                                               \
0151 }                                                                             \
0152                                                                               \
0153 static __inline struct type *                                                 \
0154 name##_SPLAY_MIN_MAX(struct name *head, int val)                              \
0155 {                                                                             \
0156   name##_SPLAY_MINMAX(head, val);                                             \
0157   return (SPLAY_ROOT(head));                                                  \
0158 }
0159
0160 /* Main splay operation.
0161  * Moves node close to the key of elm to top
0162  */
0163 #define SPLAY_GENERATE(name, type, field, cmp)                                \
0164 struct type *                                                                 \
0165 name##_SPLAY_INSERT(struct name *head, struct type *elm)                      \
0166 {                                                                             \
0167     if (SPLAY_EMPTY(head)) {                                                  \
0168       SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;                \
0169     } else {                                                                  \
0170       int __comp;                                                             \
0171       name##_SPLAY(head, elm);                                                \
0172       __comp = (cmp)(elm, (head)->sph_root);                                  \
0173       if(__comp < 0) {                                                        \
0174         SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);         \
0175         SPLAY_RIGHT(elm, field) = (head)->sph_root;                           \
0176         SPLAY_LEFT((head)->sph_root, field) = NULL;                           \
0177       } else if (__comp > 0) {                                                \
0178         SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);       \
0179         SPLAY_LEFT(elm, field) = (head)->sph_root;                            \
0180         SPLAY_RIGHT((head)->sph_root, field) = NULL;                          \
0181       } else                                                                  \
0182         return ((head)->sph_root);                                            \
0183     }                                                                         \
0184     (head)->sph_root = (elm);                                                 \
0185     return (NULL);                                                            \
0186 }                                                                             \
0187                                                                               \
0188 struct type *                                                                 \
0189 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                      \
0190 {                                                                             \
0191   struct type *__tmp;                                                         \
0192   if (SPLAY_EMPTY(head))                                                      \
0193     return (NULL);                                                            \
0194   name##_SPLAY(head, elm);                                                    \
0195   if ((cmp)(elm, (head)->sph_root) == 0) {                                    \
0196     if (SPLAY_LEFT((head)->sph_root, field) == NULL) {                        \
0197       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);                \
0198     } else {                                                                  \
0199       __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
0200       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);                 \
0201       name##_SPLAY(head, elm);                                                \
0202       SPLAY_RIGHT((head)->sph_root, field) = __tmp;                           \
0203     }                                                                         \
0204     return (elm);                                                             \
0205   }                                                                           \
0206   return (NULL);                                                              \
0207 }                                                                             \
0208                                                                               \
0209 void                                                                          \
0210 name##_SPLAY(struct name *head, struct type *elm)                             \
0211 {                                                                             \
0212   struct type __node, *__left, *__right, *__tmp;                              \
0213   int __comp;                                                                 \
0214                                                                               \
0215   SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
0216   __left = __right = &__node;                                                 \
0217                                                                               \
0218   while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {                      \
0219     if (__comp < 0) {                                                         \
0220       __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
0221       if (__tmp == NULL)                                                      \
0222         break;                                                                \
0223       if ((cmp)(elm, __tmp) < 0){                                             \
0224         SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
0225         if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
0226           break;                                                              \
0227       }                                                                       \
0228       SPLAY_LINKLEFT(head, __right, field);                                   \
0229     } else if (__comp > 0) {                                                  \
0230       __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
0231       if (__tmp == NULL)                                                      \
0232         break;                                                                \
0233       if ((cmp)(elm, __tmp) > 0){                                             \
0234         SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
0235         if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
0236           break;                                                              \
0237       }                                                                       \
0238       SPLAY_LINKRIGHT(head, __left, field);                                   \
0239     }                                                                         \
0240   }                                                                           \
0241   SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
0242 }                                                                             \
0243                                                                               \
0244 /* Splay with either the minimum or the maximum element                       \
0245  * Used to find minimum or maximum element in tree.                           \
0246  */                                                                           \
0247 void name##_SPLAY_MINMAX(struct name *head, int __comp)                       \
0248 {                                                                             \
0249   struct type __node, *__left, *__right, *__tmp;                              \
0250                                                                               \
0251   SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;            \
0252   __left = __right = &__node;                                                 \
0253                                                                               \
0254   for (;;) {                                                                  \
0255     if (__comp < 0) {                                                         \
0256       __tmp = SPLAY_LEFT((head)->sph_root, field);                            \
0257       if (__tmp == NULL)                                                      \
0258         break;                                                                \
0259       if (__comp < 0){                                                        \
0260         SPLAY_ROTATE_RIGHT(head, __tmp, field);                               \
0261         if (SPLAY_LEFT((head)->sph_root, field) == NULL)                      \
0262           break;                                                              \
0263       }                                                                       \
0264       SPLAY_LINKLEFT(head, __right, field);                                   \
0265     } else if (__comp > 0) {                                                  \
0266       __tmp = SPLAY_RIGHT((head)->sph_root, field);                           \
0267       if (__tmp == NULL)                                                      \
0268         break;                                                                \
0269       if (__comp > 0) {                                                       \
0270         SPLAY_ROTATE_LEFT(head, __tmp, field);                                \
0271         if (SPLAY_RIGHT((head)->sph_root, field) == NULL)                     \
0272           break;                                                              \
0273       }                                                                       \
0274       SPLAY_LINKRIGHT(head, __left, field);                                   \
0275     }                                                                         \
0276   }                                                                           \
0277   SPLAY_ASSEMBLE(head, &__node, __left, __right, field);                      \
0278 }
0279
0280 #define SPLAY_NEGINF  -1
0281 #define SPLAY_INF     1
0282
0283 #define SPLAY_INSERT(name, x, y)  name##_SPLAY_INSERT(x, y)
0284 #define SPLAY_REMOVE(name, x, y)  name##_SPLAY_REMOVE(x, y)
0285 #define SPLAY_FIND(name, x, y)    name##_SPLAY_FIND(x, y)
0286 #define SPLAY_NEXT(name, x, y)    name##_SPLAY_NEXT(x, y)
0287 #define SPLAY_MIN(name, x)        (SPLAY_EMPTY(x) ? NULL                      \
0288                                   : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
0289 #define SPLAY_MAX(name, x)        (SPLAY_EMPTY(x) ? NULL                      \
0290                                   : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
0291
0292 #define SPLAY_FOREACH(x, name, head)                                          \
0293   for ((x) = SPLAY_MIN(name, head);                                           \
0294        (x) != NULL;                                                           \
0295        (x) = SPLAY_NEXT(name, head, x))
0296
0297 /* Macros that define a red-black tree */
0298 #define RB_HEAD(name, type)                                                   \
0299 struct name {                                                                 \
0300   struct type *rbh_root; /* root of the tree */                               \
0301 }
0302
0303 #define RB_INITIALIZER(root)                                                  \
0304   { NULL }
0305
0306 #define RB_INIT(root) do {                                                    \
0307   (root)->rbh_root = NULL;                                                    \
0308 } while (/*CONSTCOND*/ 0)
0309
0310 #define RB_BLACK  0
0311 #define RB_RED    1
0312 #define RB_ENTRY(type)                                                        \
0313 struct {                                                                      \
0314   struct type *rbe_left;        /* left element */                            \
0315   struct type *rbe_right;       /* right element */                           \
0316   struct type *rbe_parent;      /* parent element */                          \
0317   int rbe_color;                /* node color */                              \
0318 }
0319
0320 #define RB_LEFT(elm, field)     (elm)->field.rbe_left
0321 #define RB_RIGHT(elm, field)    (elm)->field.rbe_right
0322 #define RB_PARENT(elm, field)   (elm)->field.rbe_parent
0323 #define RB_COLOR(elm, field)    (elm)->field.rbe_color
0324 #define RB_ROOT(head)           (head)->rbh_root
0325 #define RB_EMPTY(head)          (RB_ROOT(head) == NULL)
0326
0327 #define RB_SET(elm, parent, field) do {                                       \
0328   RB_PARENT(elm, field) = parent;                                             \
0329   RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;                          \
0330   RB_COLOR(elm, field) = RB_RED;                                              \
0331 } while (/*CONSTCOND*/ 0)
0332
0333 #define RB_SET_BLACKRED(black, red, field) do {                               \
0334   RB_COLOR(black, field) = RB_BLACK;                                          \
0335   RB_COLOR(red, field) = RB_RED;                                              \
0336 } while (/*CONSTCOND*/ 0)
0337
0338 #ifndef RB_AUGMENT
0339 #define RB_AUGMENT(x)  do {} while (0)
0340 #endif
0341
0342 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                            \
0343   (tmp) = RB_RIGHT(elm, field);                                               \
0344   if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {                 \
0345     RB_PARENT(RB_LEFT(tmp, field), field) = (elm);                            \
0346   }                                                                           \
0347   RB_AUGMENT(elm);                                                            \
0348   if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
0349     if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))                       \
0350       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);                          \
0351     else                                                                      \
0352       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);                         \
0353   } else                                                                      \
0354     (head)->rbh_root = (tmp);                                                 \
0355   RB_LEFT(tmp, field) = (elm);                                                \
0356   RB_PARENT(elm, field) = (tmp);                                              \
0357   RB_AUGMENT(tmp);                                                            \
0358   if ((RB_PARENT(tmp, field)))                                                \
0359     RB_AUGMENT(RB_PARENT(tmp, field));                                        \
0360 } while (/*CONSTCOND*/ 0)
0361
0362 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                           \
0363   (tmp) = RB_LEFT(elm, field);                                                \
0364   if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {                 \
0365     RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);                           \
0366   }                                                                           \
0367   RB_AUGMENT(elm);                                                            \
0368   if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
0369     if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))                       \
0370       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);                          \
0371     else                                                                      \
0372       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);                         \
0373   } else                                                                      \
0374     (head)->rbh_root = (tmp);                                                 \
0375   RB_RIGHT(tmp, field) = (elm);                                               \
0376   RB_PARENT(elm, field) = (tmp);                                              \
0377   RB_AUGMENT(tmp);                                                            \
0378   if ((RB_PARENT(tmp, field)))                                                \
0379     RB_AUGMENT(RB_PARENT(tmp, field));                                        \
0380 } while (/*CONSTCOND*/ 0)
0381
0382 /* Generates prototypes and inline functions */
0383 #define  RB_PROTOTYPE(name, type, field, cmp)                                 \
0384   RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
0385 #define  RB_PROTOTYPE_STATIC(name, type, field, cmp)                          \
0386   RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
0387 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)                   \
0388 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);               \
0389 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
0390 attr struct type *name##_RB_REMOVE(struct name *, struct type *);             \
0391 attr struct type *name##_RB_INSERT(struct name *, struct type *);             \
0392 attr struct type *name##_RB_FIND(struct name *, struct type *);               \
0393 attr struct type *name##_RB_NFIND(struct name *, struct type *);              \
0394 attr struct type *name##_RB_NEXT(struct type *);                              \
0395 attr struct type *name##_RB_PREV(struct type *);                              \
0396 attr struct type *name##_RB_MINMAX(struct name *, int);                       \
0397                                                                               \
0398
0399 /* Main rb operation.
0400  * Moves node close to the key of elm to top
0401  */
0402 #define  RB_GENERATE(name, type, field, cmp)                                  \
0403   RB_GENERATE_INTERNAL(name, type, field, cmp,)
0404 #define  RB_GENERATE_STATIC(name, type, field, cmp)                           \
0405   RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
0406 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)                    \
0407 attr void                                                                     \
0408 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)                   \
0409 {                                                                             \
0410   struct type *parent, *gparent, *tmp;                                        \
0411   while ((parent = RB_PARENT(elm, field)) != NULL &&                          \
0412       RB_COLOR(parent, field) == RB_RED) {                                    \
0413     gparent = RB_PARENT(parent, field);                                       \
0414     if (parent == RB_LEFT(gparent, field)) {                                  \
0415       tmp = RB_RIGHT(gparent, field);                                         \
0416       if (tmp && RB_COLOR(tmp, field) == RB_RED) {                            \
0417         RB_COLOR(tmp, field) = RB_BLACK;                                      \
0418         RB_SET_BLACKRED(parent, gparent, field);                              \
0419         elm = gparent;                                                        \
0420         continue;                                                             \
0421       }                                                                       \
0422       if (RB_RIGHT(parent, field) == elm) {                                   \
0423         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0424         tmp = parent;                                                         \
0425         parent = elm;                                                         \
0426         elm = tmp;                                                            \
0427       }                                                                       \
0428       RB_SET_BLACKRED(parent, gparent, field);                                \
0429       RB_ROTATE_RIGHT(head, gparent, tmp, field);                             \
0430     } else {                                                                  \
0431       tmp = RB_LEFT(gparent, field);                                          \
0432       if (tmp && RB_COLOR(tmp, field) == RB_RED) {                            \
0433         RB_COLOR(tmp, field) = RB_BLACK;                                      \
0434         RB_SET_BLACKRED(parent, gparent, field);                              \
0435         elm = gparent;                                                        \
0436         continue;                                                             \
0437       }                                                                       \
0438       if (RB_LEFT(parent, field) == elm) {                                    \
0439         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0440         tmp = parent;                                                         \
0441         parent = elm;                                                         \
0442         elm = tmp;                                                            \
0443       }                                                                       \
0444       RB_SET_BLACKRED(parent, gparent, field);                                \
0445       RB_ROTATE_LEFT(head, gparent, tmp, field);                              \
0446     }                                                                         \
0447   }                                                                           \
0448   RB_COLOR(head->rbh_root, field) = RB_BLACK;                                 \
0449 }                                                                             \
0450                                                                               \
0451 attr void                                                                     \
0452 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent,                \
0453     struct type *elm)                                                         \
0454 {                                                                             \
0455   struct type *tmp;                                                           \
0456   while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&                 \
0457       elm != RB_ROOT(head)) {                                                 \
0458     if (RB_LEFT(parent, field) == elm) {                                      \
0459       tmp = RB_RIGHT(parent, field);                                          \
0460       if (RB_COLOR(tmp, field) == RB_RED) {                                   \
0461         RB_SET_BLACKRED(tmp, parent, field);                                  \
0462         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0463         tmp = RB_RIGHT(parent, field);                                        \
0464       }                                                                       \
0465       if ((RB_LEFT(tmp, field) == NULL ||                                     \
0466           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&                \
0467           (RB_RIGHT(tmp, field) == NULL ||                                    \
0468           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {               \
0469         RB_COLOR(tmp, field) = RB_RED;                                        \
0470         elm = parent;                                                         \
0471         parent = RB_PARENT(elm, field);                                       \
0472       } else {                                                                \
0473         if (RB_RIGHT(tmp, field) == NULL ||                                   \
0474             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {              \
0475           struct type *oleft;                                                 \
0476           if ((oleft = RB_LEFT(tmp, field))                                   \
0477               != NULL)                                                        \
0478             RB_COLOR(oleft, field) = RB_BLACK;                                \
0479           RB_COLOR(tmp, field) = RB_RED;                                      \
0480           RB_ROTATE_RIGHT(head, tmp, oleft, field);                           \
0481           tmp = RB_RIGHT(parent, field);                                      \
0482         }                                                                     \
0483         RB_COLOR(tmp, field) = RB_COLOR(parent, field);                       \
0484         RB_COLOR(parent, field) = RB_BLACK;                                   \
0485         if (RB_RIGHT(tmp, field))                                             \
0486           RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;                   \
0487         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0488         elm = RB_ROOT(head);                                                  \
0489         break;                                                                \
0490       }                                                                       \
0491     } else {                                                                  \
0492       tmp = RB_LEFT(parent, field);                                           \
0493       if (RB_COLOR(tmp, field) == RB_RED) {                                   \
0494         RB_SET_BLACKRED(tmp, parent, field);                                  \
0495         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0496         tmp = RB_LEFT(parent, field);                                         \
0497       }                                                                       \
0498       if ((RB_LEFT(tmp, field) == NULL ||                                     \
0499           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&                \
0500           (RB_RIGHT(tmp, field) == NULL ||                                    \
0501           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {               \
0502         RB_COLOR(tmp, field) = RB_RED;                                        \
0503         elm = parent;                                                         \
0504         parent = RB_PARENT(elm, field);                                       \
0505       } else {                                                                \
0506         if (RB_LEFT(tmp, field) == NULL ||                                    \
0507             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {               \
0508           struct type *oright;                                                \
0509           if ((oright = RB_RIGHT(tmp, field))                                 \
0510               != NULL)                                                        \
0511             RB_COLOR(oright, field) = RB_BLACK;                               \
0512           RB_COLOR(tmp, field) = RB_RED;                                      \
0513           RB_ROTATE_LEFT(head, tmp, oright, field);                           \
0514           tmp = RB_LEFT(parent, field);                                       \
0515         }                                                                     \
0516         RB_COLOR(tmp, field) = RB_COLOR(parent, field);                       \
0517         RB_COLOR(parent, field) = RB_BLACK;                                   \
0518         if (RB_LEFT(tmp, field))                                              \
0519           RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;                    \
0520         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0521         elm = RB_ROOT(head);                                                  \
0522         break;                                                                \
0523       }                                                                       \
0524     }                                                                         \
0525   }                                                                           \
0526   if (elm)                                                                    \
0527     RB_COLOR(elm, field) = RB_BLACK;                                          \
0528 }                                                                             \
0529                                                                               \
0530 attr struct type *                                                            \
0531 name##_RB_REMOVE(struct name *head, struct type *elm)                         \
0532 {                                                                             \
0533   struct type *child, *parent, *old = elm;                                    \
0534   int color;                                                                  \
0535   if (RB_LEFT(elm, field) == NULL)                                            \
0536     child = RB_RIGHT(elm, field);                                             \
0537   else if (RB_RIGHT(elm, field) == NULL)                                      \
0538     child = RB_LEFT(elm, field);                                              \
0539   else {                                                                      \
0540     struct type *left;                                                        \
0541     elm = RB_RIGHT(elm, field);                                               \
0542     while ((left = RB_LEFT(elm, field)) != NULL)                              \
0543       elm = left;                                                             \
0544     child = RB_RIGHT(elm, field);                                             \
0545     parent = RB_PARENT(elm, field);                                           \
0546     color = RB_COLOR(elm, field);                                             \
0547     if (child)                                                                \
0548       RB_PARENT(child, field) = parent;                                       \
0549     if (parent) {                                                             \
0550       if (RB_LEFT(parent, field) == elm)                                      \
0551         RB_LEFT(parent, field) = child;                                       \
0552       else                                                                    \
0553         RB_RIGHT(parent, field) = child;                                      \
0554       RB_AUGMENT(parent);                                                     \
0555     } else                                                                    \
0556       RB_ROOT(head) = child;                                                  \
0557     if (RB_PARENT(elm, field) == old)                                         \
0558       parent = elm;                                                           \
0559     (elm)->field = (old)->field;                                              \
0560     if (RB_PARENT(old, field)) {                                              \
0561       if (RB_LEFT(RB_PARENT(old, field), field) == old)                       \
0562         RB_LEFT(RB_PARENT(old, field), field) = elm;                          \
0563       else                                                                    \
0564         RB_RIGHT(RB_PARENT(old, field), field) = elm;                         \
0565       RB_AUGMENT(RB_PARENT(old, field));                                      \
0566     } else                                                                    \
0567       RB_ROOT(head) = elm;                                                    \
0568     RB_PARENT(RB_LEFT(old, field), field) = elm;                              \
0569     if (RB_RIGHT(old, field))                                                 \
0570       RB_PARENT(RB_RIGHT(old, field), field) = elm;                           \
0571     if (parent) {                                                             \
0572       left = parent;                                                          \
0573       do {                                                                    \
0574         RB_AUGMENT(left);                                                     \
0575       } while ((left = RB_PARENT(left, field)) != NULL);                      \
0576     }                                                                         \
0577     goto color;                                                               \
0578   }                                                                           \
0579   parent = RB_PARENT(elm, field);                                             \
0580   color = RB_COLOR(elm, field);                                               \
0581   if (child)                                                                  \
0582     RB_PARENT(child, field) = parent;                                         \
0583   if (parent) {                                                               \
0584     if (RB_LEFT(parent, field) == elm)                                        \
0585       RB_LEFT(parent, field) = child;                                         \
0586     else                                                                      \
0587       RB_RIGHT(parent, field) = child;                                        \
0588     RB_AUGMENT(parent);                                                       \
0589   } else                                                                      \
0590     RB_ROOT(head) = child;                                                    \
0591 color:                                                                        \
0592   if (color == RB_BLACK)                                                      \
0593     name##_RB_REMOVE_COLOR(head, parent, child);                              \
0594   return (old);                                                               \
0595 }                                                                             \
0596                                                                               \
0597 /* Inserts a node into the RB tree */                                         \
0598 attr struct type *                                                            \
0599 name##_RB_INSERT(struct name *head, struct type *elm)                         \
0600 {                                                                             \
0601   struct type *tmp;                                                           \
0602   struct type *parent = NULL;                                                 \
0603   int comp = 0;                                                               \
0604   tmp = RB_ROOT(head);                                                        \
0605   while (tmp) {                                                               \
0606     parent = tmp;                                                             \
0607     comp = (cmp)(elm, parent);                                                \
0608     if (comp < 0)                                                             \
0609       tmp = RB_LEFT(tmp, field);                                              \
0610     else if (comp > 0)                                                        \
0611       tmp = RB_RIGHT(tmp, field);                                             \
0612     else                                                                      \
0613       return (tmp);                                                           \
0614   }                                                                           \
0615   RB_SET(elm, parent, field);                                                 \
0616   if (parent != NULL) {                                                       \
0617     if (comp < 0)                                                             \
0618       RB_LEFT(parent, field) = elm;                                           \
0619     else                                                                      \
0620       RB_RIGHT(parent, field) = elm;                                          \
0621     RB_AUGMENT(parent);                                                       \
0622   } else                                                                      \
0623     RB_ROOT(head) = elm;                                                      \
0624   name##_RB_INSERT_COLOR(head, elm);                                          \
0625   return (NULL);                                                              \
0626 }                                                                             \
0627                                                                               \
0628 /* Finds the node with the same key as elm */                                 \
0629 attr struct type *                                                            \
0630 name##_RB_FIND(struct name *head, struct type *elm)                           \
0631 {                                                                             \
0632   struct type *tmp = RB_ROOT(head);                                           \
0633   int comp;                                                                   \
0634   while (tmp) {                                                               \
0635     comp = cmp(elm, tmp);                                                     \
0636     if (comp < 0)                                                             \
0637       tmp = RB_LEFT(tmp, field);                                              \
0638     else if (comp > 0)                                                        \
0639       tmp = RB_RIGHT(tmp, field);                                             \
0640     else                                                                      \
0641       return (tmp);                                                           \
0642   }                                                                           \
0643   return (NULL);                                                              \
0644 }                                                                             \
0645                                                                               \
0646 /* Finds the first node greater than or equal to the search key */            \
0647 attr struct type *                                                            \
0648 name##_RB_NFIND(struct name *head, struct type *elm)                          \
0649 {                                                                             \
0650   struct type *tmp = RB_ROOT(head);                                           \
0651   struct type *res = NULL;                                                    \
0652   int comp;                                                                   \
0653   while (tmp) {                                                               \
0654     comp = cmp(elm, tmp);                                                     \
0655     if (comp < 0) {                                                           \
0656       res = tmp;                                                              \
0657       tmp = RB_LEFT(tmp, field);                                              \
0658     }                                                                         \
0659     else if (comp > 0)                                                        \
0660       tmp = RB_RIGHT(tmp, field);                                             \
0661     else                                                                      \
0662       return (tmp);                                                           \
0663   }                                                                           \
0664   return (res);                                                               \
0665 }                                                                             \
0666                                                                               \
0667 /* ARGSUSED */                                                                \
0668 attr struct type *                                                            \
0669 name##_RB_NEXT(struct type *elm)                                              \
0670 {                                                                             \
0671   if (RB_RIGHT(elm, field)) {                                                 \
0672     elm = RB_RIGHT(elm, field);                                               \
0673     while (RB_LEFT(elm, field))                                               \
0674       elm = RB_LEFT(elm, field);                                              \
0675   } else {                                                                    \
0676     if (RB_PARENT(elm, field) &&                                              \
0677         (elm == RB_LEFT(RB_PARENT(elm, field), field)))                       \
0678       elm = RB_PARENT(elm, field);                                            \
0679     else {                                                                    \
0680       while (RB_PARENT(elm, field) &&                                         \
0681           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))                    \
0682         elm = RB_PARENT(elm, field);                                          \
0683       elm = RB_PARENT(elm, field);                                            \
0684     }                                                                         \
0685   }                                                                           \
0686   return (elm);                                                               \
0687 }                                                                             \
0688                                                                               \
0689 /* ARGSUSED */                                                                \
0690 attr struct type *                                                            \
0691 name##_RB_PREV(struct type *elm)                                              \
0692 {                                                                             \
0693   if (RB_LEFT(elm, field)) {                                                  \
0694     elm = RB_LEFT(elm, field);                                                \
0695     while (RB_RIGHT(elm, field))                                              \
0696       elm = RB_RIGHT(elm, field);                                             \
0697   } else {                                                                    \
0698     if (RB_PARENT(elm, field) &&                                              \
0699         (elm == RB_RIGHT(RB_PARENT(elm, field), field)))                      \
0700       elm = RB_PARENT(elm, field);                                            \
0701     else {                                                                    \
0702       while (RB_PARENT(elm, field) &&                                         \
0703           (elm == RB_LEFT(RB_PARENT(elm, field), field)))                     \
0704         elm = RB_PARENT(elm, field);                                          \
0705       elm = RB_PARENT(elm, field);                                            \
0706     }                                                                         \
0707   }                                                                           \
0708   return (elm);                                                               \
0709 }                                                                             \
0710                                                                               \
0711 attr struct type *                                                            \
0712 name##_RB_MINMAX(struct name *head, int val)                                  \
0713 {                                                                             \
0714   struct type *tmp = RB_ROOT(head);                                           \
0715   struct type *parent = NULL;                                                 \
0716   while (tmp) {                                                               \
0717     parent = tmp;                                                             \
0718     if (val < 0)                                                              \
0719       tmp = RB_LEFT(tmp, field);                                              \
0720     else                                                                      \
0721       tmp = RB_RIGHT(tmp, field);                                             \
0722   }                                                                           \
0723   return (parent);                                                            \
0724 }
0725
0726 #define RB_NEGINF   -1
0727 #define RB_INF      1
0728
0729 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
0730 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
0731 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
0732 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
0733 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
0734 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
0735 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
0736 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
0737
0738 #define RB_FOREACH(x, name, head)                                             \
0739   for ((x) = RB_MIN(name, head);                                              \
0740        (x) != NULL;                                                           \
0741        (x) = name##_RB_NEXT(x))
0742
0743 #define RB_FOREACH_FROM(x, name, y)                                           \
0744   for ((x) = (y);                                                             \
0745       ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);                \
0746        (x) = (y))
0747
0748 #define RB_FOREACH_SAFE(x, name, head, y)                                     \
0749   for ((x) = RB_MIN(name, head);                                              \
0750       ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);                \
0751        (x) = (y))
0752
0753 #define RB_FOREACH_REVERSE(x, name, head)                                     \
0754   for ((x) = RB_MAX(name, head);                                              \
0755        (x) != NULL;                                                           \
0756        (x) = name##_RB_PREV(x))
0757
0758 #define RB_FOREACH_REVERSE_FROM(x, name, y)                                   \
0759   for ((x) = (y);                                                             \
0760       ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);                \
0761        (x) = (y))
0762
0763 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                             \
0764   for ((x) = RB_MAX(name, head);                                              \
0765       ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);                \
0766        (x) = (y))
0767
0768 #endif  /* UV_TREE_H_ */