Gnash: jemtree.h Source File

Go to the documentation of this file.
00001 /*      $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
00002 /*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
00003 /* $FreeBSD: src/sys/sys/tree.h,v 1.7 2007/12/28 07:03:26 jasone Exp $ */
00004 
00005 /*-
00006  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
00007  * All rights reserved.
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  * 1. Redistributions of source code must retain the above copyright
00013  *    notice, this list of conditions and the following disclaimer.
00014  * 2. Redistributions in binary form must reproduce the above copyright
00015  *    notice, this list of conditions and the following disclaimer in the
00016  *    documentation and/or other materials provided with the distribution.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00019  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00020  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00021  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00022  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00023  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00024  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00025  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00026  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00027  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00028  */
00029 
00030 #ifndef _SYS_TREE_H_
00031 #define _SYS_TREE_H_
00032 
00033 /*
00034  * This file defines data structures for different types of trees:
00035  * splay trees and red-black trees.
00036  *
00037  * A splay tree is a self-organizing data structure.  Every operation
00038  * on the tree causes a splay to happen.  The splay moves the requested
00039  * node to the root of the tree and partly rebalances it.
00040  *
00041  * This has the benefit that request locality causes faster lookups as
00042  * the requested nodes move to the top of the tree.  On the other hand,
00043  * every lookup causes memory writes.
00044  *
00045  * The Balance Theorem bounds the total access time for m operations
00046  * and n inserts on an initially empty tree as O((m + n)lg n).  The
00047  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
00048  *
00049  * A red-black tree is a binary search tree with the node color as an
00050  * extra attribute.  It fulfills a set of conditions:
00051  *      - every search path from the root to a leaf consists of the
00052  *        same number of black nodes,
00053  *      - each red node (except for the root) has a black parent,
00054  *      - each leaf node is black.
00055  *
00056  * Every operation on a red-black tree is bounded as O(lg n).
00057  * The maximum height of a red-black tree is 2lg (n+1).
00058  */
00059 
00060 #define SPLAY_HEAD(name, type)                                          \
00061 struct name {                                                           \
00062         struct type *sph_root; /* root of the tree */                   \
00063 }
00064 
00065 #define SPLAY_INITIALIZER(root)                                         \
00066         { NULL }
00067 
00068 #define SPLAY_INIT(root) do {                                           \
00069         (root)->sph_root = NULL;                                        \
00070 } while (/*CONSTCOND*/ 0)
00071 
00072 #define SPLAY_ENTRY(type)                                               \
00073 struct {                                                                \
00074         struct type *spe_left; /* left element */                       \
00075         struct type *spe_right; /* right element */                     \
00076 }
00077 
00078 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
00079 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
00080 #define SPLAY_ROOT(head)                (head)->sph_root
00081 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
00082 
00083 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
00084 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
00085         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
00086         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
00087         (head)->sph_root = tmp;                                         \
00088 } while (/*CONSTCOND*/ 0)
00089         
00090 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
00091         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
00092         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
00093         (head)->sph_root = tmp;                                         \
00094 } while (/*CONSTCOND*/ 0)
00095 
00096 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
00097         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
00098         tmp = (head)->sph_root;                                         \
00099         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
00100 } while (/*CONSTCOND*/ 0)
00101 
00102 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
00103         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
00104         tmp = (head)->sph_root;                                         \
00105         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
00106 } while (/*CONSTCOND*/ 0)
00107 
00108 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
00109         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
00110         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
00111         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
00112         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
00113 } while (/*CONSTCOND*/ 0)
00114 
00115 /* Generates prototypes and inline functions */
00116 
00117 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
00118 void name##_SPLAY(struct name *, struct type *);                        \
00119 void name##_SPLAY_MINMAX(struct name *, int);                           \
00120 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
00121 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
00122                                                                         \
00123 /* Finds the node with the same key as elm */                           \
00124 static __inline struct type *                                           \
00125 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
00126 {                                                                       \
00127         if (SPLAY_EMPTY(head))                                          \
00128                 return(NULL);                                           \
00129         name##_SPLAY(head, elm);                                        \
00130         if ((cmp)(elm, (head)->sph_root) == 0)                          \
00131                 return (head->sph_root);                                \
00132         return (NULL);                                                  \
00133 }                                                                       \
00134                                                                         \
00135 static __inline struct type *                                           \
00136 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
00137 {                                                                       \
00138         name##_SPLAY(head, elm);                                        \
00139         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
00140                 elm = SPLAY_RIGHT(elm, field);                          \
00141                 while (SPLAY_LEFT(elm, field) != NULL) {                \
00142                         elm = SPLAY_LEFT(elm, field);                   \
00143                 }                                                       \
00144         } else                                                          \
00145                 elm = NULL;                                             \
00146         return (elm);                                                   \
00147 }                                                                       \
00148                                                                         \
00149 static __inline struct type *                                           \
00150 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
00151 {                                                                       \
00152         name##_SPLAY_MINMAX(head, val);                                 \
00153         return (SPLAY_ROOT(head));                                      \
00154 }
00155 
00156 /* Main splay operation.
00157  * Moves node close to the key of elm to top
00158  */
00159 #define SPLAY_GENERATE(name, type, field, cmp)                          \
00160 struct type *                                                           \
00161 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
00162 {                                                                       \
00163     if (SPLAY_EMPTY(head)) {                                            \
00164             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
00165     } else {                                                            \
00166             int __comp;                                                 \
00167             name##_SPLAY(head, elm);                                    \
00168             __comp = (cmp)(elm, (head)->sph_root);                      \
00169             if(__comp < 0) {                                            \
00170                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
00171                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
00172                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
00173             } else if (__comp > 0) {                                    \
00174                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
00175                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
00176                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
00177             } else                                                      \
00178                     return ((head)->sph_root);                          \
00179     }                                                                   \
00180     (head)->sph_root = (elm);                                           \
00181     return (NULL);                                                      \
00182 }                                                                       \
00183                                                                         \
00184 struct type *                                                           \
00185 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
00186 {                                                                       \
00187         struct type *__tmp;                                             \
00188         if (SPLAY_EMPTY(head))                                          \
00189                 return (NULL);                                          \
00190         name##_SPLAY(head, elm);                                        \
00191         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
00192                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
00193                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
00194                 } else {                                                \
00195                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
00196                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
00197                         name##_SPLAY(head, elm);                        \
00198                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
00199                 }                                                       \
00200                 return (elm);                                           \
00201         }                                                               \
00202         return (NULL);                                                  \
00203 }                                                                       \
00204                                                                         \
00205 void                                                                    \
00206 name##_SPLAY(struct name *head, struct type *elm)                       \
00207 {                                                                       \
00208         struct type __node, *__left, *__right, *__tmp;                  \
00209         int __comp;                                                     \
00210 \
00211         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
00212         __left = __right = &__node;                                     \
00213 \
00214         while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
00215                 if (__comp < 0) {                                       \
00216                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
00217                         if (__tmp == NULL)                              \
00218                                 break;                                  \
00219                         if ((cmp)(elm, __tmp) < 0){                     \
00220                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
00221                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
00222                                         break;                          \
00223                         }                                               \
00224                         SPLAY_LINKLEFT(head, __right, field);           \
00225                 } else if (__comp > 0) {                                \
00226                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
00227                         if (__tmp == NULL)                              \
00228                                 break;                                  \
00229                         if ((cmp)(elm, __tmp) > 0){                     \
00230                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
00231                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
00232                                         break;                          \
00233                         }                                               \
00234                         SPLAY_LINKRIGHT(head, __left, field);           \
00235                 }                                                       \
00236         }                                                               \
00237         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
00238 }                                                                       \
00239                                                                         \
00240 /* Splay with either the minimum or the maximum element                 \
00241  * Used to find minimum or maximum element in tree.                     \
00242  */                                                                     \
00243 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
00244 {                                                                       \
00245         struct type __node, *__left, *__right, *__tmp;                  \
00246 \
00247         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
00248         __left = __right = &__node;                                     \
00249 \
00250         while (1) {                                                     \
00251                 if (__comp < 0) {                                       \
00252                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
00253                         if (__tmp == NULL)                              \
00254                                 break;                                  \
00255                         if (__comp < 0){                                \
00256                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
00257                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
00258                                         break;                          \
00259                         }                                               \
00260                         SPLAY_LINKLEFT(head, __right, field);           \
00261                 } else if (__comp > 0) {                                \
00262                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
00263                         if (__tmp == NULL)                              \
00264                                 break;                                  \
00265                         if (__comp > 0) {                               \
00266                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
00267                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
00268                                         break;                          \
00269                         }                                               \
00270                         SPLAY_LINKRIGHT(head, __left, field);           \
00271                 }                                                       \
00272         }                                                               \
00273         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
00274 }
00275 
00276 #define SPLAY_NEGINF    -1
00277 #define SPLAY_INF       1
00278 
00279 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
00280 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
00281 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
00282 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
00283 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
00284                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
00285 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
00286                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
00287 
00288 #define SPLAY_FOREACH(x, name, head)                                    \
00289         for ((x) = SPLAY_MIN(name, head);                               \
00290              (x) != NULL;                                               \
00291              (x) = SPLAY_NEXT(name, head, x))
00292 
00293 /* Macros that define a red-black tree */
00294 #define RB_HEAD(name, type)                                             \
00295 struct name {                                                           \
00296         struct type *rbh_root; /* root of the tree */                   \
00297 }
00298 
00299 #define RB_INITIALIZER(root)                                            \
00300         { NULL }
00301 
00302 #define RB_INIT(root) do {                                              \
00303         (root)->rbh_root = NULL;                                        \
00304 } while (/*CONSTCOND*/ 0)
00305 
00306 #define RB_BLACK        0
00307 #define RB_RED          1
00308 #define RB_ENTRY(type)                                                  \
00309 struct {                                                                \
00310         struct type *rbe_left;          /* left element */              \
00311         struct type *rbe_right;         /* right element */             \
00312         struct type *rbe_parent;        /* parent element */            \
00313         int rbe_color;                  /* node color */                \
00314 }
00315 
00316 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
00317 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
00318 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
00319 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
00320 #define RB_ROOT(head)                   (head)->rbh_root
00321 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
00322 
00323 #define RB_SET(elm, parent, field) do {                                 \
00324         RB_PARENT(elm, field) = parent;                                 \
00325         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
00326         RB_COLOR(elm, field) = RB_RED;                                  \
00327 } while (/*CONSTCOND*/ 0)
00328 
00329 #define RB_SET_BLACKRED(black, red, field) do {                         \
00330         RB_COLOR(black, field) = RB_BLACK;                              \
00331         RB_COLOR(red, field) = RB_RED;                                  \
00332 } while (/*CONSTCOND*/ 0)
00333 
00334 #ifndef RB_AUGMENT
00335 #define RB_AUGMENT(x)   do {} while (0)
00336 #endif
00337 
00338 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
00339         (tmp) = RB_RIGHT(elm, field);                                   \
00340         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
00341                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
00342         }                                                               \
00343         RB_AUGMENT(elm);                                                \
00344         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
00345                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
00346                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
00347                 else                                                    \
00348                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
00349         } else                                                          \
00350                 (head)->rbh_root = (tmp);                               \
00351         RB_LEFT(tmp, field) = (elm);                                    \
00352         RB_PARENT(elm, field) = (tmp);                                  \
00353         RB_AUGMENT(tmp);                                                \
00354         if ((RB_PARENT(tmp, field)))                                    \
00355                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
00356 } while (/*CONSTCOND*/ 0)
00357 
00358 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
00359         (tmp) = RB_LEFT(elm, field);                                    \
00360         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
00361                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
00362         }                                                               \
00363         RB_AUGMENT(elm);                                                \
00364         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) {  \
00365                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
00366                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
00367                 else                                                    \
00368                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
00369         } else                                                          \
00370                 (head)->rbh_root = (tmp);                               \
00371         RB_RIGHT(tmp, field) = (elm);                                   \
00372         RB_PARENT(elm, field) = (tmp);                                  \
00373         RB_AUGMENT(tmp);                                                \
00374         if ((RB_PARENT(tmp, field)))                                    \
00375                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
00376 } while (/*CONSTCOND*/ 0)
00377 
00378 /* Generates prototypes and inline functions */
00379 #define RB_PROTOTYPE(name, type, field, cmp)                            \
00380         RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
00381 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
00382         RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
00383 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
00384 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
00385 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
00386 attr struct type *name##_RB_REMOVE(struct name *, struct type *);       \
00387 attr struct type *name##_RB_INSERT(struct name *, struct type *);       \
00388 attr struct type *name##_RB_FIND(struct name *, struct type *);         \
00389 attr struct type *name##_RB_NFIND(struct name *, struct type *);        \
00390 attr struct type *name##_RB_NEXT(struct type *);                        \
00391 attr struct type *name##_RB_PREV(struct type *);                        \
00392 attr struct type *name##_RB_MINMAX(struct name *, int);                 \
00393                                                                         \
00394 
00395 /* Main rb operation.
00396  * Moves node close to the key of elm to top
00397  */
00398 #define RB_GENERATE(name, type, field, cmp)                             \
00399         RB_GENERATE_INTERNAL(name, type, field, cmp,)
00400 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
00401         RB_GENERATE_INTERNAL(name, type, field, cmp, static)
00402 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
00403 attr void                                                               \
00404 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
00405 {                                                                       \
00406         struct type *parent, *gparent, *tmp;                            \
00407         while ((parent = RB_PARENT(elm, field)) != NULL &&              \
00408             RB_COLOR(parent, field) == RB_RED) {                        \
00409                 gparent = RB_PARENT(parent, field);                     \
00410                 if (parent == RB_LEFT(gparent, field)) {                \
00411                         tmp = RB_RIGHT(gparent, field);                 \
00412                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
00413                                 RB_COLOR(tmp, field) = RB_BLACK;        \
00414                                 RB_SET_BLACKRED(parent, gparent, field);\
00415                                 elm = gparent;                          \
00416                                 continue;                               \
00417                         }                                               \
00418                         if (RB_RIGHT(parent, field) == elm) {           \
00419                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
00420                                 tmp = parent;                           \
00421                                 parent = elm;                           \
00422                                 elm = tmp;                              \
00423                         }                                               \
00424                         RB_SET_BLACKRED(parent, gparent, field);        \
00425                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
00426                 } else {                                                \
00427                         tmp = RB_LEFT(gparent, field);                  \
00428                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
00429                                 RB_COLOR(tmp, field) = RB_BLACK;        \
00430                                 RB_SET_BLACKRED(parent, gparent, field);\
00431                                 elm = gparent;                          \
00432                                 continue;                               \
00433                         }                                               \
00434                         if (RB_LEFT(parent, field) == elm) {            \
00435                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
00436                                 tmp = parent;                           \
00437                                 parent = elm;                           \
00438                                 elm = tmp;                              \
00439                         }                                               \
00440                         RB_SET_BLACKRED(parent, gparent, field);        \
00441                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
00442                 }                                                       \
00443         }                                                               \
00444         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
00445 }                                                                       \
00446                                                                         \
00447 attr void                                                               \
00448 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
00449 {                                                                       \
00450         struct type *tmp;                                               \
00451         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
00452             elm != RB_ROOT(head)) {                                     \
00453                 if (RB_LEFT(parent, field) == elm) {                    \
00454                         tmp = RB_RIGHT(parent, field);                  \
00455                         if (RB_COLOR(tmp, field) == RB_RED) {           \
00456                                 RB_SET_BLACKRED(tmp, parent, field);    \
00457                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
00458                                 tmp = RB_RIGHT(parent, field);          \
00459                         }                                               \
00460                         if ((RB_LEFT(tmp, field) == NULL ||             \
00461                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
00462                             (RB_RIGHT(tmp, field) == NULL ||            \
00463                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
00464                                 RB_COLOR(tmp, field) = RB_RED;          \
00465                                 elm = parent;                           \
00466                                 parent = RB_PARENT(elm, field);         \
00467                         } else {                                        \
00468                                 if (RB_RIGHT(tmp, field) == NULL ||     \
00469                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
00470                                         struct type *oleft;             \
00471                                         if ((oleft = RB_LEFT(tmp, field)) \
00472                                             != NULL)                    \
00473                                                 RB_COLOR(oleft, field) = RB_BLACK;\
00474                                         RB_COLOR(tmp, field) = RB_RED;  \
00475                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
00476                                         tmp = RB_RIGHT(parent, field);  \
00477                                 }                                       \
00478                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
00479                                 RB_COLOR(parent, field) = RB_BLACK;     \
00480                                 if (RB_RIGHT(tmp, field))               \
00481                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
00482                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
00483                                 elm = RB_ROOT(head);                    \
00484                                 break;                                  \
00485                         }                                               \
00486                 } else {                                                \
00487                         tmp = RB_LEFT(parent, field);                   \
00488                         if (RB_COLOR(tmp, field) == RB_RED) {           \
00489                                 RB_SET_BLACKRED(tmp, parent, field);    \
00490                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
00491                                 tmp = RB_LEFT(parent, field);           \
00492                         }                                               \
00493                         if ((RB_LEFT(tmp, field) == NULL ||             \
00494                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
00495                             (RB_RIGHT(tmp, field) == NULL ||            \
00496                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
00497                                 RB_COLOR(tmp, field) = RB_RED;          \
00498                                 elm = parent;                           \
00499                                 parent = RB_PARENT(elm, field);         \
00500                         } else {                                        \
00501                                 if (RB_LEFT(tmp, field) == NULL ||      \
00502                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
00503                                         struct type *oright;            \
00504                                         if ((oright = RB_RIGHT(tmp, field)) \
00505                                             != NULL)                    \
00506                                                 RB_COLOR(oright, field) = RB_BLACK;\
00507                                         RB_COLOR(tmp, field) = RB_RED;  \
00508                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
00509                                         tmp = RB_LEFT(parent, field);   \
00510                                 }                                       \
00511                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
00512                                 RB_COLOR(parent, field) = RB_BLACK;     \
00513                                 if (RB_LEFT(tmp, field))                \
00514                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
00515                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
00516                                 elm = RB_ROOT(head);                    \
00517                                 break;                                  \
00518                         }                                               \
00519                 }                                                       \
00520         }                                                               \
00521         if (elm)                                                        \
00522                 RB_COLOR(elm, field) = RB_BLACK;                        \
00523 }                                                                       \
00524                                                                         \
00525 attr struct type *                                                      \
00526 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
00527 {                                                                       \
00528         struct type *child, *parent, *old = elm;                        \
00529         int color;                                                      \
00530         if (RB_LEFT(elm, field) == NULL)                                \
00531                 child = RB_RIGHT(elm, field);                           \
00532         else if (RB_RIGHT(elm, field) == NULL)                          \
00533                 child = RB_LEFT(elm, field);                            \
00534         else {                                                          \
00535                 struct type *left;                                      \
00536                 elm = RB_RIGHT(elm, field);                             \
00537                 while ((left = RB_LEFT(elm, field)) != NULL)            \
00538                         elm = left;                                     \
00539                 child = RB_RIGHT(elm, field);                           \
00540                 parent = RB_PARENT(elm, field);                         \
00541                 color = RB_COLOR(elm, field);                           \
00542                 if (child)                                              \
00543                         RB_PARENT(child, field) = parent;               \
00544                 if (parent) {                                           \
00545                         if (RB_LEFT(parent, field) == elm)              \
00546                                 RB_LEFT(parent, field) = child;         \
00547                         else                                            \
00548                                 RB_RIGHT(parent, field) = child;        \
00549                         RB_AUGMENT(parent);                             \
00550                 } else                                                  \
00551                         RB_ROOT(head) = child;                          \
00552                 if (RB_PARENT(elm, field) == old)                       \
00553                         parent = elm;                                   \
00554                 (elm)->field = (old)->field;                            \
00555                 if (RB_PARENT(old, field)) {                            \
00556                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
00557                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
00558                         else                                            \
00559                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
00560                         RB_AUGMENT(RB_PARENT(old, field));              \
00561                 } else                                                  \
00562                         RB_ROOT(head) = elm;                            \
00563                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
00564                 if (RB_RIGHT(old, field))                               \
00565                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
00566                 if (parent) {                                           \
00567                         left = parent;                                  \
00568                         do {                                            \
00569                                 RB_AUGMENT(left);                       \
00570                         } while ((left = RB_PARENT(left, field)) != NULL); \
00571                 }                                                       \
00572                 goto color;                                             \
00573         }                                                               \
00574         parent = RB_PARENT(elm, field);                                 \
00575         color = RB_COLOR(elm, field);                                   \
00576         if (child)                                                      \
00577                 RB_PARENT(child, field) = parent;                       \
00578         if (parent) {                                                   \
00579                 if (RB_LEFT(parent, field) == elm)                      \
00580                         RB_LEFT(parent, field) = child;                 \
00581                 else                                                    \
00582                         RB_RIGHT(parent, field) = child;                \
00583                 RB_AUGMENT(parent);                                     \
00584         } else                                                          \
00585                 RB_ROOT(head) = child;                                  \
00586 color:                                                                  \
00587         if (color == RB_BLACK)                                          \
00588                 name##_RB_REMOVE_COLOR(head, parent, child);            \
00589         return (old);                                                   \
00590 }                                                                       \
00591                                                                         \
00592 /* Inserts a node into the RB tree */                                   \
00593 attr struct type *                                                      \
00594 name##_RB_INSERT(struct name *head, struct type *elm)                   \
00595 {                                                                       \
00596         struct type *tmp;                                               \
00597         struct type *parent = NULL;                                     \
00598         int comp = 0;                                                   \
00599         tmp = RB_ROOT(head);                                            \
00600         while (tmp) {                                                   \
00601                 parent = tmp;                                           \
00602                 comp = (cmp)(elm, parent);                              \
00603                 if (comp < 0)                                           \
00604                         tmp = RB_LEFT(tmp, field);                      \
00605                 else if (comp > 0)                                      \
00606                         tmp = RB_RIGHT(tmp, field);                     \
00607                 else                                                    \
00608                         return (tmp);                                   \
00609         }                                                               \
00610         RB_SET(elm, parent, field);                                     \
00611         if (parent != NULL) {                                           \
00612                 if (comp < 0)                                           \
00613                         RB_LEFT(parent, field) = elm;                   \
00614                 else                                                    \
00615                         RB_RIGHT(parent, field) = elm;                  \
00616                 RB_AUGMENT(parent);                                     \
00617         } else                                                          \
00618                 RB_ROOT(head) = elm;                                    \
00619         name##_RB_INSERT_COLOR(head, elm);                              \
00620         return (NULL);                                                  \
00621 }                                                                       \
00622                                                                         \
00623 /* Finds the node with the same key as elm */                           \
00624 attr struct type *                                                      \
00625 name##_RB_FIND(struct name *head, struct type *elm)                     \
00626 {                                                                       \
00627         struct type *tmp = RB_ROOT(head);                               \
00628         int comp;                                                       \
00629         while (tmp) {                                                   \
00630                 comp = cmp(elm, tmp);                                   \
00631                 if (comp < 0)                                           \
00632                         tmp = RB_LEFT(tmp, field);                      \
00633                 else if (comp > 0)                                      \
00634                         tmp = RB_RIGHT(tmp, field);                     \
00635                 else                                                    \
00636                         return (tmp);                                   \
00637         }                                                               \
00638         return (NULL);                                                  \
00639 }                                                                       \
00640                                                                         \
00641 /* Finds the first node greater than or equal to the search key */      \
00642 attr struct type *                                                      \
00643 name##_RB_NFIND(struct name *head, struct type *elm)                    \
00644 {                                                                       \
00645         struct type *tmp = RB_ROOT(head);                               \
00646         struct type *res = NULL;                                        \
00647         int comp;                                                       \
00648         while (tmp) {                                                   \
00649                 comp = cmp(elm, tmp);                                   \
00650                 if (comp < 0) {                                         \
00651                         res = tmp;                                      \
00652                         tmp = RB_LEFT(tmp, field);                      \
00653                 }                                                       \
00654                 else if (comp > 0)                                      \
00655                         tmp = RB_RIGHT(tmp, field);                     \
00656                 else                                                    \
00657                         return (tmp);                                   \
00658         }                                                               \
00659         return (res);                                                   \
00660 }                                                                       \
00661                                                                         \
00662 /* ARGSUSED */                                                          \
00663 attr struct type *                                                      \
00664 name##_RB_NEXT(struct type *elm)                                        \
00665 {                                                                       \
00666         if (RB_RIGHT(elm, field)) {                                     \
00667                 elm = RB_RIGHT(elm, field);                             \
00668                 while (RB_LEFT(elm, field))                             \
00669                         elm = RB_LEFT(elm, field);                      \
00670         } else {                                                        \
00671                 if (RB_PARENT(elm, field) &&                            \
00672                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
00673                         elm = RB_PARENT(elm, field);                    \
00674                 else {                                                  \
00675                         while (RB_PARENT(elm, field) &&                 \
00676                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
00677                                 elm = RB_PARENT(elm, field);            \
00678                         elm = RB_PARENT(elm, field);                    \
00679                 }                                                       \
00680         }                                                               \
00681         return (elm);                                                   \
00682 }                                                                       \
00683                                                                         \
00684 /* ARGSUSED */                                                          \
00685 attr struct type *                                                      \
00686 name##_RB_PREV(struct type *elm)                                        \
00687 {                                                                       \
00688         if (RB_LEFT(elm, field)) {                                      \
00689                 elm = RB_LEFT(elm, field);                              \
00690                 while (RB_RIGHT(elm, field))                            \
00691                         elm = RB_RIGHT(elm, field);                     \
00692         } else {                                                        \
00693                 if (RB_PARENT(elm, field) &&                            \
00694                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
00695                         elm = RB_PARENT(elm, field);                    \
00696                 else {                                                  \
00697                         while (RB_PARENT(elm, field) &&                 \
00698                             (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
00699                                 elm = RB_PARENT(elm, field);            \
00700                         elm = RB_PARENT(elm, field);                    \
00701                 }                                                       \
00702         }                                                               \
00703         return (elm);                                                   \
00704 }                                                                       \
00705                                                                         \
00706 attr struct type *                                                      \
00707 name##_RB_MINMAX(struct name *head, int val)                            \
00708 {                                                                       \
00709         struct type *tmp = RB_ROOT(head);                               \
00710         struct type *parent = NULL;                                     \
00711         while (tmp) {                                                   \
00712                 parent = tmp;                                           \
00713                 if (val < 0)                                            \
00714                         tmp = RB_LEFT(tmp, field);                      \
00715                 else                                                    \
00716                         tmp = RB_RIGHT(tmp, field);                     \
00717         }                                                               \
00718         return (parent);                                                \
00719 }
00720 
00721 #define RB_NEGINF       -1
00722 #define RB_INF  1
00723 
00724 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
00725 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
00726 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
00727 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
00728 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
00729 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
00730 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
00731 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
00732 
00733 #define RB_FOREACH(x, name, head)                                       \
00734         for ((x) = RB_MIN(name, head);                                  \
00735              (x) != NULL;                                               \
00736              (x) = name##_RB_NEXT(x))
00737 
00738 #define RB_FOREACH_REVERSE(x, name, head)                               \
00739         for ((x) = RB_MAX(name, head);                                  \
00740              (x) != NULL;                                               \
00741              (x) = name##_RB_PREV(x))
00742 
00743 #endif  /* _SYS_TREE_H_ */