The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/sys/tree.h

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*      $OpenBSD: tree.h,v 1.11 2008/05/11 22:19:09 millert Exp $       */
    2 /*
    3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice, this list of conditions and the following disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   25  */
   26 
   27 #ifndef _SYS_TREE_H_
   28 #define _SYS_TREE_H_
   29 
   30 /*
   31  * This file defines data structures for different types of trees:
   32  * splay trees and red-black trees.
   33  *
   34  * A splay tree is a self-organizing data structure.  Every operation
   35  * on the tree causes a splay to happen.  The splay moves the requested
   36  * node to the root of the tree and partly rebalances it.
   37  *
   38  * This has the benefit that request locality causes faster lookups as
   39  * the requested nodes move to the top of the tree.  On the other hand,
   40  * every lookup causes memory writes.
   41  *
   42  * The Balance Theorem bounds the total access time for m operations
   43  * and n inserts on an initially empty tree as O((m + n)lg n).  The
   44  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
   45  *
   46  * A red-black tree is a binary search tree with the node color as an
   47  * extra attribute.  It fulfills a set of conditions:
   48  *      - every search path from the root to a leaf consists of the
   49  *        same number of black nodes,
   50  *      - each red node (except for the root) has a black parent,
   51  *      - each leaf node is black.
   52  *
   53  * Every operation on a red-black tree is bounded as O(lg n).
   54  * The maximum height of a red-black tree is 2lg (n+1).
   55  */
   56 
   57 #define SPLAY_HEAD(name, type)                                          \
   58 struct name {                                                           \
   59         struct type *sph_root; /* root of the tree */                   \
   60 }
   61 
   62 #define SPLAY_INITIALIZER(root)                                         \
   63         { NULL }
   64 
   65 #define SPLAY_INIT(root) do {                                           \
   66         (root)->sph_root = NULL;                                        \
   67 } while (0)
   68 
   69 #define SPLAY_ENTRY(type)                                               \
   70 struct {                                                                \
   71         struct type *spe_left; /* left element */                       \
   72         struct type *spe_right; /* right element */                     \
   73 }
   74 
   75 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
   76 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
   77 #define SPLAY_ROOT(head)                (head)->sph_root
   78 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
   79 
   80 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
   81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
   82         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
   83         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
   84         (head)->sph_root = tmp;                                         \
   85 } while (0)
   86         
   87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
   88         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
   89         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
   90         (head)->sph_root = tmp;                                         \
   91 } while (0)
   92 
   93 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
   94         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
   95         tmp = (head)->sph_root;                                         \
   96         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
   97 } while (0)
   98 
   99 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
  100         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
  101         tmp = (head)->sph_root;                                         \
  102         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
  103 } while (0)
  104 
  105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
  106         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
  107         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
  108         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
  109         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
  110 } while (0)
  111 
  112 /* Generates prototypes and inline functions */
  113 
  114 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
  115 void name##_SPLAY(struct name *, struct type *);                        \
  116 void name##_SPLAY_MINMAX(struct name *, int);                           \
  117 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
  118 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
  119                                                                         \
  120 /* Finds the node with the same key as elm */                           \
  121 static __inline struct type *                                           \
  122 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
  123 {                                                                       \
  124         if (SPLAY_EMPTY(head))                                          \
  125                 return(NULL);                                           \
  126         name##_SPLAY(head, elm);                                        \
  127         if ((cmp)(elm, (head)->sph_root) == 0)                          \
  128                 return (head->sph_root);                                \
  129         return (NULL);                                                  \
  130 }                                                                       \
  131                                                                         \
  132 static __inline struct type *                                           \
  133 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
  134 {                                                                       \
  135         name##_SPLAY(head, elm);                                        \
  136         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
  137                 elm = SPLAY_RIGHT(elm, field);                          \
  138                 while (SPLAY_LEFT(elm, field) != NULL) {                \
  139                         elm = SPLAY_LEFT(elm, field);                   \
  140                 }                                                       \
  141         } else                                                          \
  142                 elm = NULL;                                             \
  143         return (elm);                                                   \
  144 }                                                                       \
  145                                                                         \
  146 static __inline struct type *                                           \
  147 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
  148 {                                                                       \
  149         name##_SPLAY_MINMAX(head, val);                                 \
  150         return (SPLAY_ROOT(head));                                      \
  151 }
  152 
  153 /* Main splay operation.
  154  * Moves node close to the key of elm to top
  155  */
  156 #define SPLAY_GENERATE(name, type, field, cmp)                          \
  157 struct type *                                                           \
  158 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
  159 {                                                                       \
  160     if (SPLAY_EMPTY(head)) {                                            \
  161             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
  162     } else {                                                            \
  163             int __comp;                                                 \
  164             name##_SPLAY(head, elm);                                    \
  165             __comp = (cmp)(elm, (head)->sph_root);                      \
  166             if(__comp < 0) {                                            \
  167                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
  168                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
  169                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
  170             } else if (__comp > 0) {                                    \
  171                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
  172                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
  173                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
  174             } else                                                      \
  175                     return ((head)->sph_root);                          \
  176     }                                                                   \
  177     (head)->sph_root = (elm);                                           \
  178     return (NULL);                                                      \
  179 }                                                                       \
  180                                                                         \
  181 struct type *                                                           \
  182 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
  183 {                                                                       \
  184         struct type *__tmp;                                             \
  185         if (SPLAY_EMPTY(head))                                          \
  186                 return (NULL);                                          \
  187         name##_SPLAY(head, elm);                                        \
  188         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
  189                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
  190                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
  191                 } else {                                                \
  192                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  193                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
  194                         name##_SPLAY(head, elm);                        \
  195                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
  196                 }                                                       \
  197                 return (elm);                                           \
  198         }                                                               \
  199         return (NULL);                                                  \
  200 }                                                                       \
  201                                                                         \
  202 void                                                                    \
  203 name##_SPLAY(struct name *head, struct type *elm)                       \
  204 {                                                                       \
  205         struct type __node, *__left, *__right, *__tmp;                  \
  206         int __comp;                                                     \
  207 \
  208         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  209         __left = __right = &__node;                                     \
  210 \
  211         while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
  212                 if (__comp < 0) {                                       \
  213                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
  214                         if (__tmp == NULL)                              \
  215                                 break;                                  \
  216                         if ((cmp)(elm, __tmp) < 0){                     \
  217                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  218                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  219                                         break;                          \
  220                         }                                               \
  221                         SPLAY_LINKLEFT(head, __right, field);           \
  222                 } else if (__comp > 0) {                                \
  223                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  224                         if (__tmp == NULL)                              \
  225                                 break;                                  \
  226                         if ((cmp)(elm, __tmp) > 0){                     \
  227                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
  228                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  229                                         break;                          \
  230                         }                                               \
  231                         SPLAY_LINKRIGHT(head, __left, field);           \
  232                 }                                                       \
  233         }                                                               \
  234         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
  235 }                                                                       \
  236                                                                         \
  237 /* Splay with either the minimum or the maximum element                 \
  238  * Used to find minimum or maximum element in tree.                     \
  239  */                                                                     \
  240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
  241 {                                                                       \
  242         struct type __node, *__left, *__right, *__tmp;                  \
  243 \
  244         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  245         __left = __right = &__node;                                     \
  246 \
  247         while (1) {                                                     \
  248                 if (__comp < 0) {                                       \
  249                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
  250                         if (__tmp == NULL)                              \
  251                                 break;                                  \
  252                         if (__comp < 0){                                \
  253                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  254                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  255                                         break;                          \
  256                         }                                               \
  257                         SPLAY_LINKLEFT(head, __right, field);           \
  258                 } else if (__comp > 0) {                                \
  259                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  260                         if (__tmp == NULL)                              \
  261                                 break;                                  \
  262                         if (__comp > 0) {                               \
  263                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
  264                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  265                                         break;                          \
  266                         }                                               \
  267                         SPLAY_LINKRIGHT(head, __left, field);           \
  268                 }                                                       \
  269         }                                                               \
  270         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
  271 }
  272 
  273 #define SPLAY_NEGINF    -1
  274 #define SPLAY_INF       1
  275 
  276 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
  277 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
  278 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
  279 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
  280 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
  281                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
  282 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
  283                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
  284 
  285 #define SPLAY_FOREACH(x, name, head)                                    \
  286         for ((x) = SPLAY_MIN(name, head);                               \
  287              (x) != NULL;                                               \
  288              (x) = SPLAY_NEXT(name, head, x))
  289 
  290 /* Macros that define a red-black tree */
  291 #define RB_HEAD(name, type)                                             \
  292 struct name {                                                           \
  293         struct type *rbh_root; /* root of the tree */                   \
  294 }
  295 
  296 #define RB_INITIALIZER(root)                                            \
  297         { NULL }
  298 
  299 #define RB_INIT(root) do {                                              \
  300         (root)->rbh_root = NULL;                                        \
  301 } while (0)
  302 
  303 #define RB_BLACK        0
  304 #define RB_RED          1
  305 #define RB_ENTRY(type)                                                  \
  306 struct {                                                                \
  307         struct type *rbe_left;          /* left element */              \
  308         struct type *rbe_right;         /* right element */             \
  309         struct type *rbe_parent;        /* parent element */            \
  310         int rbe_color;                  /* node color */                \
  311 }
  312 
  313 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
  314 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
  315 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
  316 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
  317 #define RB_ROOT(head)                   (head)->rbh_root
  318 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
  319 
  320 #define RB_SET(elm, parent, field) do {                                 \
  321         RB_PARENT(elm, field) = parent;                                 \
  322         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
  323         RB_COLOR(elm, field) = RB_RED;                                  \
  324 } while (0)
  325 
  326 #define RB_SET_BLACKRED(black, red, field) do {                         \
  327         RB_COLOR(black, field) = RB_BLACK;                              \
  328         RB_COLOR(red, field) = RB_RED;                                  \
  329 } while (0)
  330 
  331 #ifndef RB_AUGMENT
  332 #define RB_AUGMENT(x)
  333 #endif
  334 
  335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
  336         (tmp) = RB_RIGHT(elm, field);                                   \
  337         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
  338                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
  339         }                                                               \
  340         RB_AUGMENT(elm);                                                \
  341         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
  342                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
  343                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
  344                 else                                                    \
  345                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  346         } else                                                          \
  347                 (head)->rbh_root = (tmp);                               \
  348         RB_LEFT(tmp, field) = (elm);                                    \
  349         RB_PARENT(elm, field) = (tmp);                                  \
  350         RB_AUGMENT(tmp);                                                \
  351         if ((RB_PARENT(tmp, field)))                                    \
  352                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
  353 } while (0)
  354 
  355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
  356         (tmp) = RB_LEFT(elm, field);                                    \
  357         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
  358                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
  359         }                                                               \
  360         RB_AUGMENT(elm);                                                \
  361         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
  362                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
  363                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
  364                 else                                                    \
  365                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  366         } else                                                          \
  367                 (head)->rbh_root = (tmp);                               \
  368         RB_RIGHT(tmp, field) = (elm);                                   \
  369         RB_PARENT(elm, field) = (tmp);                                  \
  370         RB_AUGMENT(tmp);                                                \
  371         if ((RB_PARENT(tmp, field)))                                    \
  372                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
  373 } while (0)
  374 
  375 /* Generates prototypes and inline functions */
  376 #define RB_PROTOTYPE(name, type, field, cmp)                            \
  377         RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
  378 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
  379         RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
  380 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
  381 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
  382 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
  383 attr struct type *name##_RB_REMOVE(struct name *, struct type *);       \
  384 attr struct type *name##_RB_INSERT(struct name *, struct type *);       \
  385 attr struct type *name##_RB_FIND(struct name *, struct type *);         \
  386 attr struct type *name##_RB_NFIND(struct name *, struct type *);        \
  387 attr struct type *name##_RB_NEXT(struct type *);                        \
  388 attr struct type *name##_RB_PREV(struct type *);                        \
  389 attr struct type *name##_RB_MINMAX(struct name *, int);                 \
  390                                                                         \
  391 
  392 /* Main rb operation.
  393  * Moves node close to the key of elm to top
  394  */
  395 #define RB_GENERATE(name, type, field, cmp)                             \
  396         RB_GENERATE_INTERNAL(name, type, field, cmp,)
  397 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
  398         RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
  399 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
  400 attr void                                                               \
  401 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
  402 {                                                                       \
  403         struct type *parent, *gparent, *tmp;                            \
  404         while ((parent = RB_PARENT(elm, field)) &&                      \
  405             RB_COLOR(parent, field) == RB_RED) {                        \
  406                 gparent = RB_PARENT(parent, field);                     \
  407                 if (parent == RB_LEFT(gparent, field)) {                \
  408                         tmp = RB_RIGHT(gparent, field);                 \
  409                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  410                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  411                                 RB_SET_BLACKRED(parent, gparent, field);\
  412                                 elm = gparent;                          \
  413                                 continue;                               \
  414                         }                                               \
  415                         if (RB_RIGHT(parent, field) == elm) {           \
  416                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  417                                 tmp = parent;                           \
  418                                 parent = elm;                           \
  419                                 elm = tmp;                              \
  420                         }                                               \
  421                         RB_SET_BLACKRED(parent, gparent, field);        \
  422                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
  423                 } else {                                                \
  424                         tmp = RB_LEFT(gparent, field);                  \
  425                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  426                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  427                                 RB_SET_BLACKRED(parent, gparent, field);\
  428                                 elm = gparent;                          \
  429                                 continue;                               \
  430                         }                                               \
  431                         if (RB_LEFT(parent, field) == elm) {            \
  432                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  433                                 tmp = parent;                           \
  434                                 parent = elm;                           \
  435                                 elm = tmp;                              \
  436                         }                                               \
  437                         RB_SET_BLACKRED(parent, gparent, field);        \
  438                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
  439                 }                                                       \
  440         }                                                               \
  441         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
  442 }                                                                       \
  443                                                                         \
  444 attr void                                                               \
  445 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
  446 {                                                                       \
  447         struct type *tmp;                                               \
  448         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
  449             elm != RB_ROOT(head)) {                                     \
  450                 if (RB_LEFT(parent, field) == elm) {                    \
  451                         tmp = RB_RIGHT(parent, field);                  \
  452                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  453                                 RB_SET_BLACKRED(tmp, parent, field);    \
  454                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  455                                 tmp = RB_RIGHT(parent, field);          \
  456                         }                                               \
  457                         if ((RB_LEFT(tmp, field) == NULL ||             \
  458                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  459                             (RB_RIGHT(tmp, field) == NULL ||            \
  460                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  461                                 RB_COLOR(tmp, field) = RB_RED;          \
  462                                 elm = parent;                           \
  463                                 parent = RB_PARENT(elm, field);         \
  464                         } else {                                        \
  465                                 if (RB_RIGHT(tmp, field) == NULL ||     \
  466                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  467                                         struct type *oleft;             \
  468                                         if ((oleft = RB_LEFT(tmp, field)))\
  469                                                 RB_COLOR(oleft, field) = RB_BLACK;\
  470                                         RB_COLOR(tmp, field) = RB_RED;  \
  471                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  472                                         tmp = RB_RIGHT(parent, field);  \
  473                                 }                                       \
  474                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  475                                 RB_COLOR(parent, field) = RB_BLACK;     \
  476                                 if (RB_RIGHT(tmp, field))               \
  477                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  478                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  479                                 elm = RB_ROOT(head);                    \
  480                                 break;                                  \
  481                         }                                               \
  482                 } else {                                                \
  483                         tmp = RB_LEFT(parent, field);                   \
  484                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  485                                 RB_SET_BLACKRED(tmp, parent, field);    \
  486                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  487                                 tmp = RB_LEFT(parent, field);           \
  488                         }                                               \
  489                         if ((RB_LEFT(tmp, field) == NULL ||             \
  490                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  491                             (RB_RIGHT(tmp, field) == NULL ||            \
  492                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  493                                 RB_COLOR(tmp, field) = RB_RED;          \
  494                                 elm = parent;                           \
  495                                 parent = RB_PARENT(elm, field);         \
  496                         } else {                                        \
  497                                 if (RB_LEFT(tmp, field) == NULL ||      \
  498                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  499                                         struct type *oright;            \
  500                                         if ((oright = RB_RIGHT(tmp, field)))\
  501                                                 RB_COLOR(oright, field) = RB_BLACK;\
  502                                         RB_COLOR(tmp, field) = RB_RED;  \
  503                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
  504                                         tmp = RB_LEFT(parent, field);   \
  505                                 }                                       \
  506                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  507                                 RB_COLOR(parent, field) = RB_BLACK;     \
  508                                 if (RB_LEFT(tmp, field))                \
  509                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  510                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  511                                 elm = RB_ROOT(head);                    \
  512                                 break;                                  \
  513                         }                                               \
  514                 }                                                       \
  515         }                                                               \
  516         if (elm)                                                        \
  517                 RB_COLOR(elm, field) = RB_BLACK;                        \
  518 }                                                                       \
  519                                                                         \
  520 attr struct type *                                                      \
  521 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
  522 {                                                                       \
  523         struct type *child, *parent, *old = elm;                        \
  524         int color;                                                      \
  525         if (RB_LEFT(elm, field) == NULL)                                \
  526                 child = RB_RIGHT(elm, field);                           \
  527         else if (RB_RIGHT(elm, field) == NULL)                          \
  528                 child = RB_LEFT(elm, field);                            \
  529         else {                                                          \
  530                 struct type *left;                                      \
  531                 elm = RB_RIGHT(elm, field);                             \
  532                 while ((left = RB_LEFT(elm, field)))                    \
  533                         elm = left;                                     \
  534                 child = RB_RIGHT(elm, field);                           \
  535                 parent = RB_PARENT(elm, field);                         \
  536                 color = RB_COLOR(elm, field);                           \
  537                 if (child)                                              \
  538                         RB_PARENT(child, field) = parent;               \
  539                 if (parent) {                                           \
  540                         if (RB_LEFT(parent, field) == elm)              \
  541                                 RB_LEFT(parent, field) = child;         \
  542                         else                                            \
  543                                 RB_RIGHT(parent, field) = child;        \
  544                         RB_AUGMENT(parent);                             \
  545                 } else                                                  \
  546                         RB_ROOT(head) = child;                          \
  547                 if (RB_PARENT(elm, field) == old)                       \
  548                         parent = elm;                                   \
  549                 (elm)->field = (old)->field;                            \
  550                 if (RB_PARENT(old, field)) {                            \
  551                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  552                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
  553                         else                                            \
  554                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  555                         RB_AUGMENT(RB_PARENT(old, field));              \
  556                 } else                                                  \
  557                         RB_ROOT(head) = elm;                            \
  558                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
  559                 if (RB_RIGHT(old, field))                               \
  560                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
  561                 if (parent) {                                           \
  562                         left = parent;                                  \
  563                         do {                                            \
  564                                 RB_AUGMENT(left);                       \
  565                         } while ((left = RB_PARENT(left, field)));      \
  566                 }                                                       \
  567                 goto color;                                             \
  568         }                                                               \
  569         parent = RB_PARENT(elm, field);                                 \
  570         color = RB_COLOR(elm, field);                                   \
  571         if (child)                                                      \
  572                 RB_PARENT(child, field) = parent;                       \
  573         if (parent) {                                                   \
  574                 if (RB_LEFT(parent, field) == elm)                      \
  575                         RB_LEFT(parent, field) = child;                 \
  576                 else                                                    \
  577                         RB_RIGHT(parent, field) = child;                \
  578                 RB_AUGMENT(parent);                                     \
  579         } else                                                          \
  580                 RB_ROOT(head) = child;                                  \
  581 color:                                                                  \
  582         if (color == RB_BLACK)                                          \
  583                 name##_RB_REMOVE_COLOR(head, parent, child);            \
  584         return (old);                                                   \
  585 }                                                                       \
  586                                                                         \
  587 /* Inserts a node into the RB tree */                                   \
  588 attr struct type *                                                      \
  589 name##_RB_INSERT(struct name *head, struct type *elm)                   \
  590 {                                                                       \
  591         struct type *tmp;                                               \
  592         struct type *parent = NULL;                                     \
  593         int comp = 0;                                                   \
  594         tmp = RB_ROOT(head);                                            \
  595         while (tmp) {                                                   \
  596                 parent = tmp;                                           \
  597                 comp = (cmp)(elm, parent);                              \
  598                 if (comp < 0)                                           \
  599                         tmp = RB_LEFT(tmp, field);                      \
  600                 else if (comp > 0)                                      \
  601                         tmp = RB_RIGHT(tmp, field);                     \
  602                 else                                                    \
  603                         return (tmp);                                   \
  604         }                                                               \
  605         RB_SET(elm, parent, field);                                     \
  606         if (parent != NULL) {                                           \
  607                 if (comp < 0)                                           \
  608                         RB_LEFT(parent, field) = elm;                   \
  609                 else                                                    \
  610                         RB_RIGHT(parent, field) = elm;                  \
  611                 RB_AUGMENT(parent);                                     \
  612         } else                                                          \
  613                 RB_ROOT(head) = elm;                                    \
  614         name##_RB_INSERT_COLOR(head, elm);                              \
  615         return (NULL);                                                  \
  616 }                                                                       \
  617                                                                         \
  618 /* Finds the node with the same key as elm */                           \
  619 attr struct type *                                                      \
  620 name##_RB_FIND(struct name *head, struct type *elm)                     \
  621 {                                                                       \
  622         struct type *tmp = RB_ROOT(head);                               \
  623         int comp;                                                       \
  624         while (tmp) {                                                   \
  625                 comp = cmp(elm, tmp);                                   \
  626                 if (comp < 0)                                           \
  627                         tmp = RB_LEFT(tmp, field);                      \
  628                 else if (comp > 0)                                      \
  629                         tmp = RB_RIGHT(tmp, field);                     \
  630                 else                                                    \
  631                         return (tmp);                                   \
  632         }                                                               \
  633         return (NULL);                                                  \
  634 }                                                                       \
  635                                                                         \
  636 /* Finds the first node greater than or equal to the search key */      \
  637 attr struct type *                                                      \
  638 name##_RB_NFIND(struct name *head, struct type *elm)                    \
  639 {                                                                       \
  640         struct type *tmp = RB_ROOT(head);                               \
  641         struct type *res = NULL;                                        \
  642         int comp;                                                       \
  643         while (tmp) {                                                   \
  644                 comp = cmp(elm, tmp);                                   \
  645                 if (comp < 0) {                                         \
  646                         res = tmp;                                      \
  647                         tmp = RB_LEFT(tmp, field);                      \
  648                 }                                                       \
  649                 else if (comp > 0)                                      \
  650                         tmp = RB_RIGHT(tmp, field);                     \
  651                 else                                                    \
  652                         return (tmp);                                   \
  653         }                                                               \
  654         return (res);                                                   \
  655 }                                                                       \
  656                                                                         \
  657 /* ARGSUSED */                                                          \
  658 attr struct type *                                                      \
  659 name##_RB_NEXT(struct type *elm)                                        \
  660 {                                                                       \
  661         if (RB_RIGHT(elm, field)) {                                     \
  662                 elm = RB_RIGHT(elm, field);                             \
  663                 while (RB_LEFT(elm, field))                             \
  664                         elm = RB_LEFT(elm, field);                      \
  665         } else {                                                        \
  666                 if (RB_PARENT(elm, field) &&                            \
  667                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
  668                         elm = RB_PARENT(elm, field);                    \
  669                 else {                                                  \
  670                         while (RB_PARENT(elm, field) &&                 \
  671                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  672                                 elm = RB_PARENT(elm, field);            \
  673                         elm = RB_PARENT(elm, field);                    \
  674                 }                                                       \
  675         }                                                               \
  676         return (elm);                                                   \
  677 }                                                                       \
  678                                                                         \
  679 /* ARGSUSED */                                                          \
  680 attr struct type *                                                      \
  681 name##_RB_PREV(struct type *elm)                                        \
  682 {                                                                       \
  683         if (RB_LEFT(elm, field)) {                                      \
  684                 elm = RB_LEFT(elm, field);                              \
  685                 while (RB_RIGHT(elm, field))                            \
  686                         elm = RB_RIGHT(elm, field);                     \
  687         } else {                                                        \
  688                 if (RB_PARENT(elm, field) &&                            \
  689                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
  690                         elm = RB_PARENT(elm, field);                    \
  691                 else {                                                  \
  692                         while (RB_PARENT(elm, field) &&                 \
  693                             (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
  694                                 elm = RB_PARENT(elm, field);            \
  695                         elm = RB_PARENT(elm, field);                    \
  696                 }                                                       \
  697         }                                                               \
  698         return (elm);                                                   \
  699 }                                                                       \
  700                                                                         \
  701 attr struct type *                                                      \
  702 name##_RB_MINMAX(struct name *head, int val)                            \
  703 {                                                                       \
  704         struct type *tmp = RB_ROOT(head);                               \
  705         struct type *parent = NULL;                                     \
  706         while (tmp) {                                                   \
  707                 parent = tmp;                                           \
  708                 if (val < 0)                                            \
  709                         tmp = RB_LEFT(tmp, field);                      \
  710                 else                                                    \
  711                         tmp = RB_RIGHT(tmp, field);                     \
  712         }                                                               \
  713         return (parent);                                                \
  714 }
  715 
  716 #define RB_NEGINF       -1
  717 #define RB_INF  1
  718 
  719 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
  720 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
  721 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
  722 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
  723 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
  724 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
  725 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
  726 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
  727 
  728 #define RB_FOREACH(x, name, head)                                       \
  729         for ((x) = RB_MIN(name, head);                                  \
  730              (x) != NULL;                                               \
  731              (x) = name##_RB_NEXT(x))
  732 
  733 #define RB_FOREACH_REVERSE(x, name, head)                               \
  734         for ((x) = RB_MAX(name, head);                                  \
  735              (x) != NULL;                                               \
  736              (x) = name##_RB_PREV(x))
  737 
  738 #endif  /* _SYS_TREE_H_ */

Cache object: 98ff1a01b448967cc49c6034a3fac5f5


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.