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  -  FREEBSD11  -  FREEBSD10  -  FREEBSD9  -  FREEBSD92  -  FREEBSD91  -  FREEBSD90  -  FREEBSD8  -  FREEBSD82  -  FREEBSD81  -  FREEBSD80  -  FREEBSD7  -  FREEBSD74  -  FREEBSD73  -  FREEBSD72  -  FREEBSD71  -  FREEBSD70  -  FREEBSD6  -  FREEBSD64  -  FREEBSD63  -  FREEBSD62  -  FREEBSD61  -  FREEBSD60  -  FREEBSD5  -  FREEBSD55  -  FREEBSD54  -  FREEBSD53  -  FREEBSD52  -  FREEBSD51  -  FREEBSD50  -  FREEBSD4  -  FREEBSD3  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: f7f694ac061ac7c41a0b0ace0c754943


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