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: releng/10.3/sys/sys/tree.h 278344 2015-02-07 08:14:20Z kib $ */
    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         RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
  387         RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
  388         RB_PROTOTYPE_INSERT(name, type, attr);                          \
  389         RB_PROTOTYPE_REMOVE(name, type, attr);                          \
  390         RB_PROTOTYPE_FIND(name, type, attr);                            \
  391         RB_PROTOTYPE_NFIND(name, type, attr);                           \
  392         RB_PROTOTYPE_NEXT(name, type, attr);                            \
  393         RB_PROTOTYPE_PREV(name, type, attr);                            \
  394         RB_PROTOTYPE_MINMAX(name, type, attr);
  395 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                     \
  396         attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
  397 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                     \
  398         attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *)
  399 #define RB_PROTOTYPE_REMOVE(name, type, attr)                           \
  400         attr struct type *name##_RB_REMOVE(struct name *, struct type *)
  401 #define RB_PROTOTYPE_INSERT(name, type, attr)                           \
  402         attr struct type *name##_RB_INSERT(struct name *, struct type *)
  403 #define RB_PROTOTYPE_FIND(name, type, attr)                             \
  404         attr struct type *name##_RB_FIND(struct name *, struct type *)
  405 #define RB_PROTOTYPE_NFIND(name, type, attr)                            \
  406         attr struct type *name##_RB_NFIND(struct name *, struct type *)
  407 #define RB_PROTOTYPE_NEXT(name, type, attr)                             \
  408         attr struct type *name##_RB_NEXT(struct type *)
  409 #define RB_PROTOTYPE_PREV(name, type, attr)                             \
  410         attr struct type *name##_RB_PREV(struct type *)
  411 #define RB_PROTOTYPE_MINMAX(name, type, attr)                           \
  412         attr struct type *name##_RB_MINMAX(struct name *, int)
  413 
  414 /* Main rb operation.
  415  * Moves node close to the key of elm to top
  416  */
  417 #define RB_GENERATE(name, type, field, cmp)                             \
  418         RB_GENERATE_INTERNAL(name, type, field, cmp,)
  419 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
  420         RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
  421 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
  422         RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
  423         RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
  424         RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
  425         RB_GENERATE_REMOVE(name, type, field, attr)                     \
  426         RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
  427         RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
  428         RB_GENERATE_NEXT(name, type, field, attr)                       \
  429         RB_GENERATE_PREV(name, type, field, attr)                       \
  430         RB_GENERATE_MINMAX(name, type, field, attr)
  431 
  432 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
  433 attr void                                                               \
  434 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
  435 {                                                                       \
  436         struct type *parent, *gparent, *tmp;                            \
  437         while ((parent = RB_PARENT(elm, field)) != NULL &&              \
  438             RB_COLOR(parent, field) == RB_RED) {                        \
  439                 gparent = RB_PARENT(parent, field);                     \
  440                 if (parent == RB_LEFT(gparent, field)) {                \
  441                         tmp = RB_RIGHT(gparent, field);                 \
  442                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  443                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  444                                 RB_SET_BLACKRED(parent, gparent, field);\
  445                                 elm = gparent;                          \
  446                                 continue;                               \
  447                         }                                               \
  448                         if (RB_RIGHT(parent, field) == elm) {           \
  449                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  450                                 tmp = parent;                           \
  451                                 parent = elm;                           \
  452                                 elm = tmp;                              \
  453                         }                                               \
  454                         RB_SET_BLACKRED(parent, gparent, field);        \
  455                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
  456                 } else {                                                \
  457                         tmp = RB_LEFT(gparent, field);                  \
  458                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  459                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  460                                 RB_SET_BLACKRED(parent, gparent, field);\
  461                                 elm = gparent;                          \
  462                                 continue;                               \
  463                         }                                               \
  464                         if (RB_LEFT(parent, field) == elm) {            \
  465                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  466                                 tmp = parent;                           \
  467                                 parent = elm;                           \
  468                                 elm = tmp;                              \
  469                         }                                               \
  470                         RB_SET_BLACKRED(parent, gparent, field);        \
  471                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
  472                 }                                                       \
  473         }                                                               \
  474         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
  475 }
  476 
  477 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
  478 attr void                                                               \
  479 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
  480 {                                                                       \
  481         struct type *tmp;                                               \
  482         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
  483             elm != RB_ROOT(head)) {                                     \
  484                 if (RB_LEFT(parent, field) == elm) {                    \
  485                         tmp = RB_RIGHT(parent, field);                  \
  486                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  487                                 RB_SET_BLACKRED(tmp, parent, field);    \
  488                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  489                                 tmp = RB_RIGHT(parent, field);          \
  490                         }                                               \
  491                         if ((RB_LEFT(tmp, field) == NULL ||             \
  492                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  493                             (RB_RIGHT(tmp, field) == NULL ||            \
  494                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  495                                 RB_COLOR(tmp, field) = RB_RED;          \
  496                                 elm = parent;                           \
  497                                 parent = RB_PARENT(elm, field);         \
  498                         } else {                                        \
  499                                 if (RB_RIGHT(tmp, field) == NULL ||     \
  500                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  501                                         struct type *oleft;             \
  502                                         if ((oleft = RB_LEFT(tmp, field)) \
  503                                             != NULL)                    \
  504                                                 RB_COLOR(oleft, field) = RB_BLACK;\
  505                                         RB_COLOR(tmp, field) = RB_RED;  \
  506                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  507                                         tmp = RB_RIGHT(parent, field);  \
  508                                 }                                       \
  509                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  510                                 RB_COLOR(parent, field) = RB_BLACK;     \
  511                                 if (RB_RIGHT(tmp, field))               \
  512                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  513                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  514                                 elm = RB_ROOT(head);                    \
  515                                 break;                                  \
  516                         }                                               \
  517                 } else {                                                \
  518                         tmp = RB_LEFT(parent, field);                   \
  519                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  520                                 RB_SET_BLACKRED(tmp, parent, field);    \
  521                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  522                                 tmp = RB_LEFT(parent, field);           \
  523                         }                                               \
  524                         if ((RB_LEFT(tmp, field) == NULL ||             \
  525                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  526                             (RB_RIGHT(tmp, field) == NULL ||            \
  527                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  528                                 RB_COLOR(tmp, field) = RB_RED;          \
  529                                 elm = parent;                           \
  530                                 parent = RB_PARENT(elm, field);         \
  531                         } else {                                        \
  532                                 if (RB_LEFT(tmp, field) == NULL ||      \
  533                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  534                                         struct type *oright;            \
  535                                         if ((oright = RB_RIGHT(tmp, field)) \
  536                                             != NULL)                    \
  537                                                 RB_COLOR(oright, field) = RB_BLACK;\
  538                                         RB_COLOR(tmp, field) = RB_RED;  \
  539                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
  540                                         tmp = RB_LEFT(parent, field);   \
  541                                 }                                       \
  542                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  543                                 RB_COLOR(parent, field) = RB_BLACK;     \
  544                                 if (RB_LEFT(tmp, field))                \
  545                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  546                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  547                                 elm = RB_ROOT(head);                    \
  548                                 break;                                  \
  549                         }                                               \
  550                 }                                                       \
  551         }                                                               \
  552         if (elm)                                                        \
  553                 RB_COLOR(elm, field) = RB_BLACK;                        \
  554 }
  555 
  556 #define RB_GENERATE_REMOVE(name, type, field, attr)                     \
  557 attr struct type *                                                      \
  558 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
  559 {                                                                       \
  560         struct type *child, *parent, *old = elm;                        \
  561         int color;                                                      \
  562         if (RB_LEFT(elm, field) == NULL)                                \
  563                 child = RB_RIGHT(elm, field);                           \
  564         else if (RB_RIGHT(elm, field) == NULL)                          \
  565                 child = RB_LEFT(elm, field);                            \
  566         else {                                                          \
  567                 struct type *left;                                      \
  568                 elm = RB_RIGHT(elm, field);                             \
  569                 while ((left = RB_LEFT(elm, field)) != NULL)            \
  570                         elm = left;                                     \
  571                 child = RB_RIGHT(elm, field);                           \
  572                 parent = RB_PARENT(elm, field);                         \
  573                 color = RB_COLOR(elm, field);                           \
  574                 if (child)                                              \
  575                         RB_PARENT(child, field) = parent;               \
  576                 if (parent) {                                           \
  577                         if (RB_LEFT(parent, field) == elm)              \
  578                                 RB_LEFT(parent, field) = child;         \
  579                         else                                            \
  580                                 RB_RIGHT(parent, field) = child;        \
  581                         RB_AUGMENT(parent);                             \
  582                 } else                                                  \
  583                         RB_ROOT(head) = child;                          \
  584                 if (RB_PARENT(elm, field) == old)                       \
  585                         parent = elm;                                   \
  586                 (elm)->field = (old)->field;                            \
  587                 if (RB_PARENT(old, field)) {                            \
  588                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  589                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
  590                         else                                            \
  591                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  592                         RB_AUGMENT(RB_PARENT(old, field));              \
  593                 } else                                                  \
  594                         RB_ROOT(head) = elm;                            \
  595                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
  596                 if (RB_RIGHT(old, field))                               \
  597                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
  598                 if (parent) {                                           \
  599                         left = parent;                                  \
  600                         do {                                            \
  601                                 RB_AUGMENT(left);                       \
  602                         } while ((left = RB_PARENT(left, field)) != NULL); \
  603                 }                                                       \
  604                 goto color;                                             \
  605         }                                                               \
  606         parent = RB_PARENT(elm, field);                                 \
  607         color = RB_COLOR(elm, field);                                   \
  608         if (child)                                                      \
  609                 RB_PARENT(child, field) = parent;                       \
  610         if (parent) {                                                   \
  611                 if (RB_LEFT(parent, field) == elm)                      \
  612                         RB_LEFT(parent, field) = child;                 \
  613                 else                                                    \
  614                         RB_RIGHT(parent, field) = child;                \
  615                 RB_AUGMENT(parent);                                     \
  616         } else                                                          \
  617                 RB_ROOT(head) = child;                                  \
  618 color:                                                                  \
  619         if (color == RB_BLACK)                                          \
  620                 name##_RB_REMOVE_COLOR(head, parent, child);            \
  621         return (old);                                                   \
  622 }                                                                       \
  623 
  624 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
  625 /* Inserts a node into the RB tree */                                   \
  626 attr struct type *                                                      \
  627 name##_RB_INSERT(struct name *head, struct type *elm)                   \
  628 {                                                                       \
  629         struct type *tmp;                                               \
  630         struct type *parent = NULL;                                     \
  631         int comp = 0;                                                   \
  632         tmp = RB_ROOT(head);                                            \
  633         while (tmp) {                                                   \
  634                 parent = tmp;                                           \
  635                 comp = (cmp)(elm, parent);                              \
  636                 if (comp < 0)                                           \
  637                         tmp = RB_LEFT(tmp, field);                      \
  638                 else if (comp > 0)                                      \
  639                         tmp = RB_RIGHT(tmp, field);                     \
  640                 else                                                    \
  641                         return (tmp);                                   \
  642         }                                                               \
  643         RB_SET(elm, parent, field);                                     \
  644         if (parent != NULL) {                                           \
  645                 if (comp < 0)                                           \
  646                         RB_LEFT(parent, field) = elm;                   \
  647                 else                                                    \
  648                         RB_RIGHT(parent, field) = elm;                  \
  649                 RB_AUGMENT(parent);                                     \
  650         } else                                                          \
  651                 RB_ROOT(head) = elm;                                    \
  652         name##_RB_INSERT_COLOR(head, elm);                              \
  653         return (NULL);                                                  \
  654 }
  655 
  656 #define RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
  657 /* Finds the node with the same key as elm */                           \
  658 attr struct type *                                                      \
  659 name##_RB_FIND(struct name *head, struct type *elm)                     \
  660 {                                                                       \
  661         struct type *tmp = RB_ROOT(head);                               \
  662         int comp;                                                       \
  663         while (tmp) {                                                   \
  664                 comp = cmp(elm, tmp);                                   \
  665                 if (comp < 0)                                           \
  666                         tmp = RB_LEFT(tmp, field);                      \
  667                 else if (comp > 0)                                      \
  668                         tmp = RB_RIGHT(tmp, field);                     \
  669                 else                                                    \
  670                         return (tmp);                                   \
  671         }                                                               \
  672         return (NULL);                                                  \
  673 }
  674 
  675 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
  676 /* Finds the first node greater than or equal to the search key */      \
  677 attr struct type *                                                      \
  678 name##_RB_NFIND(struct name *head, struct type *elm)                    \
  679 {                                                                       \
  680         struct type *tmp = RB_ROOT(head);                               \
  681         struct type *res = NULL;                                        \
  682         int comp;                                                       \
  683         while (tmp) {                                                   \
  684                 comp = cmp(elm, tmp);                                   \
  685                 if (comp < 0) {                                         \
  686                         res = tmp;                                      \
  687                         tmp = RB_LEFT(tmp, field);                      \
  688                 }                                                       \
  689                 else if (comp > 0)                                      \
  690                         tmp = RB_RIGHT(tmp, field);                     \
  691                 else                                                    \
  692                         return (tmp);                                   \
  693         }                                                               \
  694         return (res);                                                   \
  695 }
  696 
  697 #define RB_GENERATE_NEXT(name, type, field, attr)                       \
  698 /* ARGSUSED */                                                          \
  699 attr struct type *                                                      \
  700 name##_RB_NEXT(struct type *elm)                                        \
  701 {                                                                       \
  702         if (RB_RIGHT(elm, field)) {                                     \
  703                 elm = RB_RIGHT(elm, field);                             \
  704                 while (RB_LEFT(elm, field))                             \
  705                         elm = RB_LEFT(elm, field);                      \
  706         } else {                                                        \
  707                 if (RB_PARENT(elm, field) &&                            \
  708                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
  709                         elm = RB_PARENT(elm, field);                    \
  710                 else {                                                  \
  711                         while (RB_PARENT(elm, field) &&                 \
  712                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  713                                 elm = RB_PARENT(elm, field);            \
  714                         elm = RB_PARENT(elm, field);                    \
  715                 }                                                       \
  716         }                                                               \
  717         return (elm);                                                   \
  718 }
  719 
  720 #define RB_GENERATE_PREV(name, type, field, attr)                       \
  721 /* ARGSUSED */                                                          \
  722 attr struct type *                                                      \
  723 name##_RB_PREV(struct type *elm)                                        \
  724 {                                                                       \
  725         if (RB_LEFT(elm, field)) {                                      \
  726                 elm = RB_LEFT(elm, field);                              \
  727                 while (RB_RIGHT(elm, field))                            \
  728                         elm = RB_RIGHT(elm, field);                     \
  729         } else {                                                        \
  730                 if (RB_PARENT(elm, field) &&                            \
  731                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
  732                         elm = RB_PARENT(elm, field);                    \
  733                 else {                                                  \
  734                         while (RB_PARENT(elm, field) &&                 \
  735                             (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
  736                                 elm = RB_PARENT(elm, field);            \
  737                         elm = RB_PARENT(elm, field);                    \
  738                 }                                                       \
  739         }                                                               \
  740         return (elm);                                                   \
  741 }
  742 
  743 #define RB_GENERATE_MINMAX(name, type, field, attr)                     \
  744 attr struct type *                                                      \
  745 name##_RB_MINMAX(struct name *head, int val)                            \
  746 {                                                                       \
  747         struct type *tmp = RB_ROOT(head);                               \
  748         struct type *parent = NULL;                                     \
  749         while (tmp) {                                                   \
  750                 parent = tmp;                                           \
  751                 if (val < 0)                                            \
  752                         tmp = RB_LEFT(tmp, field);                      \
  753                 else                                                    \
  754                         tmp = RB_RIGHT(tmp, field);                     \
  755         }                                                               \
  756         return (parent);                                                \
  757 }
  758 
  759 #define RB_NEGINF       -1
  760 #define RB_INF  1
  761 
  762 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
  763 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
  764 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
  765 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
  766 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
  767 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
  768 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
  769 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
  770 
  771 #define RB_FOREACH(x, name, head)                                       \
  772         for ((x) = RB_MIN(name, head);                                  \
  773              (x) != NULL;                                               \
  774              (x) = name##_RB_NEXT(x))
  775 
  776 #define RB_FOREACH_FROM(x, name, y)                                     \
  777         for ((x) = (y);                                                 \
  778             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
  779              (x) = (y))
  780 
  781 #define RB_FOREACH_SAFE(x, name, head, y)                               \
  782         for ((x) = RB_MIN(name, head);                                  \
  783             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
  784              (x) = (y))
  785 
  786 #define RB_FOREACH_REVERSE(x, name, head)                               \
  787         for ((x) = RB_MAX(name, head);                                  \
  788              (x) != NULL;                                               \
  789              (x) = name##_RB_PREV(x))
  790 
  791 #define RB_FOREACH_REVERSE_FROM(x, name, y)                             \
  792         for ((x) = (y);                                                 \
  793             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
  794              (x) = (y))
  795 
  796 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                       \
  797         for ((x) = RB_MAX(name, head);                                  \
  798             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
  799              (x) = (y))
  800 
  801 #endif  /* _SYS_TREE_H_ */

Cache object: e64b228256e855605ba812af8f25d952


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