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-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 67a194b7e668de1fa483e1f7858b57b6


[ 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.