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 red-black trees.
0039  * A red-black tree is a binary search tree with the node color as an
0040  * extra attribute.  It fulfills a set of conditions:
0041  *  - every search path from the root to a leaf consists of the
0042  *    same number of black nodes,
0043  *  - each red node (except for the root) has a black parent,
0044  *  - each leaf node is black.
0045  *
0046  * Every operation on a red-black tree is bounded as O(lg n).
0047  * The maximum height of a red-black tree is 2lg (n+1).
0048  */
0049
0050 /* Macros that define a red-black tree */
0051 #define RB_HEAD(name, type)                                                   \
0052 struct name {                                                                 \
0053   struct type *rbh_root; /* root of the tree */                               \
0054 }
0055
0056 #define RB_INITIALIZER(root)                                                  \
0057   { NULL }
0058
0059 #define RB_INIT(root) do {                                                    \
0060   (root)->rbh_root = NULL;                                                    \
0061 } while (/*CONSTCOND*/ 0)
0062
0063 #define RB_BLACK  0
0064 #define RB_RED    1
0065 #define RB_ENTRY(type)                                                        \
0066 struct {                                                                      \
0067   struct type *rbe_left;        /* left element */                            \
0068   struct type *rbe_right;       /* right element */                           \
0069   struct type *rbe_parent;      /* parent element */                          \
0070   int rbe_color;                /* node color */                              \
0071 }
0072
0073 #define RB_LEFT(elm, field)     (elm)->field.rbe_left
0074 #define RB_RIGHT(elm, field)    (elm)->field.rbe_right
0075 #define RB_PARENT(elm, field)   (elm)->field.rbe_parent
0076 #define RB_COLOR(elm, field)    (elm)->field.rbe_color
0077 #define RB_ROOT(head)           (head)->rbh_root
0078 #define RB_EMPTY(head)          (RB_ROOT(head) == NULL)
0079
0080 #define RB_SET(elm, parent, field) do {                                       \
0081   RB_PARENT(elm, field) = parent;                                             \
0082   RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;                          \
0083   RB_COLOR(elm, field) = RB_RED;                                              \
0084 } while (/*CONSTCOND*/ 0)
0085
0086 #define RB_SET_BLACKRED(black, red, field) do {                               \
0087   RB_COLOR(black, field) = RB_BLACK;                                          \
0088   RB_COLOR(red, field) = RB_RED;                                              \
0089 } while (/*CONSTCOND*/ 0)
0090
0091 #ifndef RB_AUGMENT
0092 #define RB_AUGMENT(x)  do {} while (0)
0093 #endif
0094
0095 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                            \
0096   (tmp) = RB_RIGHT(elm, field);                                               \
0097   if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {                 \
0098     RB_PARENT(RB_LEFT(tmp, field), field) = (elm);                            \
0099   }                                                                           \
0100   RB_AUGMENT(elm);                                                            \
0101   if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
0102     if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))                       \
0103       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);                          \
0104     else                                                                      \
0105       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);                         \
0106   } else                                                                      \
0107     (head)->rbh_root = (tmp);                                                 \
0108   RB_LEFT(tmp, field) = (elm);                                                \
0109   RB_PARENT(elm, field) = (tmp);                                              \
0110   RB_AUGMENT(tmp);                                                            \
0111   if ((RB_PARENT(tmp, field)))                                                \
0112     RB_AUGMENT(RB_PARENT(tmp, field));                                        \
0113 } while (/*CONSTCOND*/ 0)
0114
0115 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                           \
0116   (tmp) = RB_LEFT(elm, field);                                                \
0117   if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {                 \
0118     RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);                           \
0119   }                                                                           \
0120   RB_AUGMENT(elm);                                                            \
0121   if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {              \
0122     if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))                       \
0123       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);                          \
0124     else                                                                      \
0125       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp);                         \
0126   } else                                                                      \
0127     (head)->rbh_root = (tmp);                                                 \
0128   RB_RIGHT(tmp, field) = (elm);                                               \
0129   RB_PARENT(elm, field) = (tmp);                                              \
0130   RB_AUGMENT(tmp);                                                            \
0131   if ((RB_PARENT(tmp, field)))                                                \
0132     RB_AUGMENT(RB_PARENT(tmp, field));                                        \
0133 } while (/*CONSTCOND*/ 0)
0134
0135 /* Generates prototypes and inline functions */
0136 #define  RB_PROTOTYPE(name, type, field, cmp)                                 \
0137   RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
0138 #define  RB_PROTOTYPE_STATIC(name, type, field, cmp)                          \
0139   RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
0140 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)                   \
0141 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);               \
0142 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
0143 attr struct type *name##_RB_REMOVE(struct name *, struct type *);             \
0144 attr struct type *name##_RB_INSERT(struct name *, struct type *);             \
0145 attr struct type *name##_RB_FIND(struct name *, struct type *);               \
0146 attr struct type *name##_RB_NFIND(struct name *, struct type *);              \
0147 attr struct type *name##_RB_NEXT(struct type *);                              \
0148 attr struct type *name##_RB_PREV(struct type *);                              \
0149 attr struct type *name##_RB_MINMAX(struct name *, int);                       \
0150                                                                               \
0151
0152 /* Main rb operation.
0153  * Moves node close to the key of elm to top
0154  */
0155 #define  RB_GENERATE(name, type, field, cmp)                                  \
0156   RB_GENERATE_INTERNAL(name, type, field, cmp,)
0157 #define  RB_GENERATE_STATIC(name, type, field, cmp)                           \
0158   RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static)
0159 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)                    \
0160 attr void                                                                     \
0161 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)                   \
0162 {                                                                             \
0163   struct type *parent, *gparent, *tmp;                                        \
0164   while ((parent = RB_PARENT(elm, field)) != NULL &&                          \
0165       RB_COLOR(parent, field) == RB_RED) {                                    \
0166     gparent = RB_PARENT(parent, field);                                       \
0167     if (parent == RB_LEFT(gparent, field)) {                                  \
0168       tmp = RB_RIGHT(gparent, field);                                         \
0169       if (tmp && RB_COLOR(tmp, field) == RB_RED) {                            \
0170         RB_COLOR(tmp, field) = RB_BLACK;                                      \
0171         RB_SET_BLACKRED(parent, gparent, field);                              \
0172         elm = gparent;                                                        \
0173         continue;                                                             \
0174       }                                                                       \
0175       if (RB_RIGHT(parent, field) == elm) {                                   \
0176         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0177         tmp = parent;                                                         \
0178         parent = elm;                                                         \
0179         elm = tmp;                                                            \
0180       }                                                                       \
0181       RB_SET_BLACKRED(parent, gparent, field);                                \
0182       RB_ROTATE_RIGHT(head, gparent, tmp, field);                             \
0183     } else {                                                                  \
0184       tmp = RB_LEFT(gparent, field);                                          \
0185       if (tmp && RB_COLOR(tmp, field) == RB_RED) {                            \
0186         RB_COLOR(tmp, field) = RB_BLACK;                                      \
0187         RB_SET_BLACKRED(parent, gparent, field);                              \
0188         elm = gparent;                                                        \
0189         continue;                                                             \
0190       }                                                                       \
0191       if (RB_LEFT(parent, field) == elm) {                                    \
0192         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0193         tmp = parent;                                                         \
0194         parent = elm;                                                         \
0195         elm = tmp;                                                            \
0196       }                                                                       \
0197       RB_SET_BLACKRED(parent, gparent, field);                                \
0198       RB_ROTATE_LEFT(head, gparent, tmp, field);                              \
0199     }                                                                         \
0200   }                                                                           \
0201   RB_COLOR(head->rbh_root, field) = RB_BLACK;                                 \
0202 }                                                                             \
0203                                                                               \
0204 attr void                                                                     \
0205 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent,                \
0206     struct type *elm)                                                         \
0207 {                                                                             \
0208   struct type *tmp;                                                           \
0209   while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&                 \
0210       elm != RB_ROOT(head)) {                                                 \
0211     if (RB_LEFT(parent, field) == elm) {                                      \
0212       tmp = RB_RIGHT(parent, field);                                          \
0213       if (RB_COLOR(tmp, field) == RB_RED) {                                   \
0214         RB_SET_BLACKRED(tmp, parent, field);                                  \
0215         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0216         tmp = RB_RIGHT(parent, field);                                        \
0217       }                                                                       \
0218       if ((RB_LEFT(tmp, field) == NULL ||                                     \
0219           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&                \
0220           (RB_RIGHT(tmp, field) == NULL ||                                    \
0221           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {               \
0222         RB_COLOR(tmp, field) = RB_RED;                                        \
0223         elm = parent;                                                         \
0224         parent = RB_PARENT(elm, field);                                       \
0225       } else {                                                                \
0226         if (RB_RIGHT(tmp, field) == NULL ||                                   \
0227             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {              \
0228           struct type *oleft;                                                 \
0229           if ((oleft = RB_LEFT(tmp, field))                                   \
0230               != NULL)                                                        \
0231             RB_COLOR(oleft, field) = RB_BLACK;                                \
0232           RB_COLOR(tmp, field) = RB_RED;                                      \
0233           RB_ROTATE_RIGHT(head, tmp, oleft, field);                           \
0234           tmp = RB_RIGHT(parent, field);                                      \
0235         }                                                                     \
0236         RB_COLOR(tmp, field) = RB_COLOR(parent, field);                       \
0237         RB_COLOR(parent, field) = RB_BLACK;                                   \
0238         if (RB_RIGHT(tmp, field))                                             \
0239           RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;                   \
0240         RB_ROTATE_LEFT(head, parent, tmp, field);                             \
0241         elm = RB_ROOT(head);                                                  \
0242         break;                                                                \
0243       }                                                                       \
0244     } else {                                                                  \
0245       tmp = RB_LEFT(parent, field);                                           \
0246       if (RB_COLOR(tmp, field) == RB_RED) {                                   \
0247         RB_SET_BLACKRED(tmp, parent, field);                                  \
0248         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0249         tmp = RB_LEFT(parent, field);                                         \
0250       }                                                                       \
0251       if ((RB_LEFT(tmp, field) == NULL ||                                     \
0252           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&                \
0253           (RB_RIGHT(tmp, field) == NULL ||                                    \
0254           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {               \
0255         RB_COLOR(tmp, field) = RB_RED;                                        \
0256         elm = parent;                                                         \
0257         parent = RB_PARENT(elm, field);                                       \
0258       } else {                                                                \
0259         if (RB_LEFT(tmp, field) == NULL ||                                    \
0260             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {               \
0261           struct type *oright;                                                \
0262           if ((oright = RB_RIGHT(tmp, field))                                 \
0263               != NULL)                                                        \
0264             RB_COLOR(oright, field) = RB_BLACK;                               \
0265           RB_COLOR(tmp, field) = RB_RED;                                      \
0266           RB_ROTATE_LEFT(head, tmp, oright, field);                           \
0267           tmp = RB_LEFT(parent, field);                                       \
0268         }                                                                     \
0269         RB_COLOR(tmp, field) = RB_COLOR(parent, field);                       \
0270         RB_COLOR(parent, field) = RB_BLACK;                                   \
0271         if (RB_LEFT(tmp, field))                                              \
0272           RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;                    \
0273         RB_ROTATE_RIGHT(head, parent, tmp, field);                            \
0274         elm = RB_ROOT(head);                                                  \
0275         break;                                                                \
0276       }                                                                       \
0277     }                                                                         \
0278   }                                                                           \
0279   if (elm)                                                                    \
0280     RB_COLOR(elm, field) = RB_BLACK;                                          \
0281 }                                                                             \
0282                                                                               \
0283 attr struct type *                                                            \
0284 name##_RB_REMOVE(struct name *head, struct type *elm)                         \
0285 {                                                                             \
0286   struct type *child, *parent, *old = elm;                                    \
0287   int color;                                                                  \
0288   if (RB_LEFT(elm, field) == NULL)                                            \
0289     child = RB_RIGHT(elm, field);                                             \
0290   else if (RB_RIGHT(elm, field) == NULL)                                      \
0291     child = RB_LEFT(elm, field);                                              \
0292   else {                                                                      \
0293     struct type *left;                                                        \
0294     elm = RB_RIGHT(elm, field);                                               \
0295     while ((left = RB_LEFT(elm, field)) != NULL)                              \
0296       elm = left;                                                             \
0297     child = RB_RIGHT(elm, field);                                             \
0298     parent = RB_PARENT(elm, field);                                           \
0299     color = RB_COLOR(elm, field);                                             \
0300     if (child)                                                                \
0301       RB_PARENT(child, field) = parent;                                       \
0302     if (parent) {                                                             \
0303       if (RB_LEFT(parent, field) == elm)                                      \
0304         RB_LEFT(parent, field) = child;                                       \
0305       else                                                                    \
0306         RB_RIGHT(parent, field) = child;                                      \
0307       RB_AUGMENT(parent);                                                     \
0308     } else                                                                    \
0309       RB_ROOT(head) = child;                                                  \
0310     if (RB_PARENT(elm, field) == old)                                         \
0311       parent = elm;                                                           \
0312     (elm)->field = (old)->field;                                              \
0313     if (RB_PARENT(old, field)) {                                              \
0314       if (RB_LEFT(RB_PARENT(old, field), field) == old)                       \
0315         RB_LEFT(RB_PARENT(old, field), field) = elm;                          \
0316       else                                                                    \
0317         RB_RIGHT(RB_PARENT(old, field), field) = elm;                         \
0318       RB_AUGMENT(RB_PARENT(old, field));                                      \
0319     } else                                                                    \
0320       RB_ROOT(head) = elm;                                                    \
0321     RB_PARENT(RB_LEFT(old, field), field) = elm;                              \
0322     if (RB_RIGHT(old, field))                                                 \
0323       RB_PARENT(RB_RIGHT(old, field), field) = elm;                           \
0324     if (parent) {                                                             \
0325       left = parent;                                                          \
0326       do {                                                                    \
0327         RB_AUGMENT(left);                                                     \
0328       } while ((left = RB_PARENT(left, field)) != NULL);                      \
0329     }                                                                         \
0330     goto color;                                                               \
0331   }                                                                           \
0332   parent = RB_PARENT(elm, field);                                             \
0333   color = RB_COLOR(elm, field);                                               \
0334   if (child)                                                                  \
0335     RB_PARENT(child, field) = parent;                                         \
0336   if (parent) {                                                               \
0337     if (RB_LEFT(parent, field) == elm)                                        \
0338       RB_LEFT(parent, field) = child;                                         \
0339     else                                                                      \
0340       RB_RIGHT(parent, field) = child;                                        \
0341     RB_AUGMENT(parent);                                                       \
0342   } else                                                                      \
0343     RB_ROOT(head) = child;                                                    \
0344 color:                                                                        \
0345   if (color == RB_BLACK)                                                      \
0346     name##_RB_REMOVE_COLOR(head, parent, child);                              \
0347   return (old);                                                               \
0348 }                                                                             \
0349                                                                               \
0350 /* Inserts a node into the RB tree */                                         \
0351 attr struct type *                                                            \
0352 name##_RB_INSERT(struct name *head, struct type *elm)                         \
0353 {                                                                             \
0354   struct type *tmp;                                                           \
0355   struct type *parent = NULL;                                                 \
0356   int comp = 0;                                                               \
0357   tmp = RB_ROOT(head);                                                        \
0358   while (tmp) {                                                               \
0359     parent = tmp;                                                             \
0360     comp = (cmp)(elm, parent);                                                \
0361     if (comp < 0)                                                             \
0362       tmp = RB_LEFT(tmp, field);                                              \
0363     else if (comp > 0)                                                        \
0364       tmp = RB_RIGHT(tmp, field);                                             \
0365     else                                                                      \
0366       return (tmp);                                                           \
0367   }                                                                           \
0368   RB_SET(elm, parent, field);                                                 \
0369   if (parent != NULL) {                                                       \
0370     if (comp < 0)                                                             \
0371       RB_LEFT(parent, field) = elm;                                           \
0372     else                                                                      \
0373       RB_RIGHT(parent, field) = elm;                                          \
0374     RB_AUGMENT(parent);                                                       \
0375   } else                                                                      \
0376     RB_ROOT(head) = elm;                                                      \
0377   name##_RB_INSERT_COLOR(head, elm);                                          \
0378   return (NULL);                                                              \
0379 }                                                                             \
0380                                                                               \
0381 /* Finds the node with the same key as elm */                                 \
0382 attr struct type *                                                            \
0383 name##_RB_FIND(struct name *head, struct type *elm)                           \
0384 {                                                                             \
0385   struct type *tmp = RB_ROOT(head);                                           \
0386   int comp;                                                                   \
0387   while (tmp) {                                                               \
0388     comp = cmp(elm, tmp);                                                     \
0389     if (comp < 0)                                                             \
0390       tmp = RB_LEFT(tmp, field);                                              \
0391     else if (comp > 0)                                                        \
0392       tmp = RB_RIGHT(tmp, field);                                             \
0393     else                                                                      \
0394       return (tmp);                                                           \
0395   }                                                                           \
0396   return (NULL);                                                              \
0397 }                                                                             \
0398                                                                               \
0399 /* Finds the first node greater than or equal to the search key */            \
0400 attr struct type *                                                            \
0401 name##_RB_NFIND(struct name *head, struct type *elm)                          \
0402 {                                                                             \
0403   struct type *tmp = RB_ROOT(head);                                           \
0404   struct type *res = NULL;                                                    \
0405   int comp;                                                                   \
0406   while (tmp) {                                                               \
0407     comp = cmp(elm, tmp);                                                     \
0408     if (comp < 0) {                                                           \
0409       res = tmp;                                                              \
0410       tmp = RB_LEFT(tmp, field);                                              \
0411     }                                                                         \
0412     else if (comp > 0)                                                        \
0413       tmp = RB_RIGHT(tmp, field);                                             \
0414     else                                                                      \
0415       return (tmp);                                                           \
0416   }                                                                           \
0417   return (res);                                                               \
0418 }                                                                             \
0419                                                                               \
0420 /* ARGSUSED */                                                                \
0421 attr struct type *                                                            \
0422 name##_RB_NEXT(struct type *elm)                                              \
0423 {                                                                             \
0424   if (RB_RIGHT(elm, field)) {                                                 \
0425     elm = RB_RIGHT(elm, field);                                               \
0426     while (RB_LEFT(elm, field))                                               \
0427       elm = RB_LEFT(elm, field);                                              \
0428   } else {                                                                    \
0429     if (RB_PARENT(elm, field) &&                                              \
0430         (elm == RB_LEFT(RB_PARENT(elm, field), field)))                       \
0431       elm = RB_PARENT(elm, field);                                            \
0432     else {                                                                    \
0433       while (RB_PARENT(elm, field) &&                                         \
0434           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))                    \
0435         elm = RB_PARENT(elm, field);                                          \
0436       elm = RB_PARENT(elm, field);                                            \
0437     }                                                                         \
0438   }                                                                           \
0439   return (elm);                                                               \
0440 }                                                                             \
0441                                                                               \
0442 /* ARGSUSED */                                                                \
0443 attr struct type *                                                            \
0444 name##_RB_PREV(struct type *elm)                                              \
0445 {                                                                             \
0446   if (RB_LEFT(elm, field)) {                                                  \
0447     elm = RB_LEFT(elm, field);                                                \
0448     while (RB_RIGHT(elm, field))                                              \
0449       elm = RB_RIGHT(elm, field);                                             \
0450   } else {                                                                    \
0451     if (RB_PARENT(elm, field) &&                                              \
0452         (elm == RB_RIGHT(RB_PARENT(elm, field), field)))                      \
0453       elm = RB_PARENT(elm, field);                                            \
0454     else {                                                                    \
0455       while (RB_PARENT(elm, field) &&                                         \
0456           (elm == RB_LEFT(RB_PARENT(elm, field), field)))                     \
0457         elm = RB_PARENT(elm, field);                                          \
0458       elm = RB_PARENT(elm, field);                                            \
0459     }                                                                         \
0460   }                                                                           \
0461   return (elm);                                                               \
0462 }                                                                             \
0463                                                                               \
0464 attr struct type *                                                            \
0465 name##_RB_MINMAX(struct name *head, int val)                                  \
0466 {                                                                             \
0467   struct type *tmp = RB_ROOT(head);                                           \
0468   struct type *parent = NULL;                                                 \
0469   while (tmp) {                                                               \
0470     parent = tmp;                                                             \
0471     if (val < 0)                                                              \
0472       tmp = RB_LEFT(tmp, field);                                              \
0473     else                                                                      \
0474       tmp = RB_RIGHT(tmp, field);                                             \
0475   }                                                                           \
0476   return (parent);                                                            \
0477 }
0478
0479 #define RB_NEGINF   -1
0480 #define RB_INF      1
0481
0482 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
0483 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
0484 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
0485 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
0486 #define RB_NEXT(name, x)        name##_RB_NEXT(x)
0487 #define RB_PREV(name, x)        name##_RB_PREV(x)
0488 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
0489 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
0490
0491 #define RB_FOREACH(x, name, head)                                             \
0492   for ((x) = RB_MIN(name, head);                                              \
0493        (x) != NULL;                                                           \
0494        (x) = name##_RB_NEXT(x))
0495
0496 #define RB_FOREACH_FROM(x, name, y)                                           \
0497   for ((x) = (y);                                                             \
0498       ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);                \
0499        (x) = (y))
0500
0501 #define RB_FOREACH_SAFE(x, name, head, y)                                     \
0502   for ((x) = RB_MIN(name, head);                                              \
0503       ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);                \
0504        (x) = (y))
0505
0506 #define RB_FOREACH_REVERSE(x, name, head)                                     \
0507   for ((x) = RB_MAX(name, head);                                              \
0508        (x) != NULL;                                                           \
0509        (x) = name##_RB_PREV(x))
0510
0511 #define RB_FOREACH_REVERSE_FROM(x, name, y)                                   \
0512   for ((x) = (y);                                                             \
0513       ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);                \
0514        (x) = (y))
0515
0516 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                             \
0517   for ((x) = RB_MAX(name, head);                                              \
0518       ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);                \
0519        (x) = (y))
0520
0521 #endif  /* UV_TREE_H_ */