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

Cache object: 422b4728982e9521d82ae190cdae8e64


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