Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 10:02:46 

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!