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 /*      $OpenBSD: tree.h,v 1.30 2020/10/10 18:03:41 otto Exp $  */
    2 /*
    3  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice, this list of conditions and the following disclaimer.
   11  * 2. Redistributions in binary form must reproduce the above copyright
   12  *    notice, this list of conditions and the following disclaimer in the
   13  *    documentation and/or other materials provided with the distribution.
   14  *
   15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
   16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   17  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
   18  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
   19  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
   20  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
   21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
   22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   24  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   25  */
   26 
   27 #ifndef _SYS_TREE_H_
   28 #define _SYS_TREE_H_
   29 
   30 #include <sys/_null.h>
   31 
   32 /*
   33  * This file defines data structures for different types of trees:
   34  * splay trees and red-black trees.
   35  *
   36  * A splay tree is a self-organizing data structure.  Every operation
   37  * on the tree causes a splay to happen.  The splay moves the requested
   38  * node to the root of the tree and partly rebalances it.
   39  *
   40  * This has the benefit that request locality causes faster lookups as
   41  * the requested nodes move to the top of the tree.  On the other hand,
   42  * every lookup causes memory writes.
   43  *
   44  * The Balance Theorem bounds the total access time for m operations
   45  * and n inserts on an initially empty tree as O((m + n)lg n).  The
   46  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
   47  *
   48  * A red-black tree is a binary search tree with the node color as an
   49  * extra attribute.  It fulfills a set of conditions:
   50  *      - every search path from the root to a leaf consists of the
   51  *        same number of black nodes,
   52  *      - each red node (except for the root) has a black parent,
   53  *      - each leaf node is black.
   54  *
   55  * Every operation on a red-black tree is bounded as O(lg n).
   56  * The maximum height of a red-black tree is 2lg (n+1).
   57  */
   58 
   59 #define SPLAY_HEAD(name, type)                                          \
   60 struct name {                                                           \
   61         struct type *sph_root; /* root of the tree */                   \
   62 }
   63 
   64 #define SPLAY_INITIALIZER(root)                                         \
   65         { NULL }
   66 
   67 #define SPLAY_INIT(root) do {                                           \
   68         (root)->sph_root = NULL;                                        \
   69 } while (0)
   70 
   71 #define SPLAY_ENTRY(type)                                               \
   72 struct {                                                                \
   73         struct type *spe_left; /* left element */                       \
   74         struct type *spe_right; /* right element */                     \
   75 }
   76 
   77 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
   78 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
   79 #define SPLAY_ROOT(head)                (head)->sph_root
   80 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
   81 
   82 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
   83 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
   84         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
   85         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
   86         (head)->sph_root = tmp;                                         \
   87 } while (0)
   88 
   89 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
   90         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
   91         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
   92         (head)->sph_root = tmp;                                         \
   93 } while (0)
   94 
   95 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
   96         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
   97         tmp = (head)->sph_root;                                         \
   98         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
   99 } while (0)
  100 
  101 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
  102         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
  103         tmp = (head)->sph_root;                                         \
  104         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
  105 } while (0)
  106 
  107 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
  108         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
  109         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
  110         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
  111         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
  112 } while (0)
  113 
  114 /* Generates prototypes and inline functions */
  115 
  116 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
  117 void name##_SPLAY(struct name *, struct type *);                        \
  118 void name##_SPLAY_MINMAX(struct name *, int);                           \
  119 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
  120 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
  121                                                                         \
  122 /* Finds the node with the same key as elm */                           \
  123 static __unused __inline struct type *                                  \
  124 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
  125 {                                                                       \
  126         if (SPLAY_EMPTY(head))                                          \
  127                 return(NULL);                                           \
  128         name##_SPLAY(head, elm);                                        \
  129         if ((cmp)(elm, (head)->sph_root) == 0)                          \
  130                 return (head->sph_root);                                \
  131         return (NULL);                                                  \
  132 }                                                                       \
  133                                                                         \
  134 static __unused __inline struct type *                                  \
  135 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
  136 {                                                                       \
  137         name##_SPLAY(head, elm);                                        \
  138         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
  139                 elm = SPLAY_RIGHT(elm, field);                          \
  140                 while (SPLAY_LEFT(elm, field) != NULL) {                \
  141                         elm = SPLAY_LEFT(elm, field);                   \
  142                 }                                                       \
  143         } else                                                          \
  144                 elm = NULL;                                             \
  145         return (elm);                                                   \
  146 }                                                                       \
  147                                                                         \
  148 static __unused __inline struct type *                                  \
  149 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
  150 {                                                                       \
  151         name##_SPLAY_MINMAX(head, val);                                 \
  152         return (SPLAY_ROOT(head));                                      \
  153 }
  154 
  155 /* Main splay operation.
  156  * Moves node close to the key of elm to top
  157  */
  158 #define SPLAY_GENERATE(name, type, field, cmp)                          \
  159 struct type *                                                           \
  160 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
  161 {                                                                       \
  162     if (SPLAY_EMPTY(head)) {                                            \
  163             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
  164     } else {                                                            \
  165             int __comp;                                                 \
  166             name##_SPLAY(head, elm);                                    \
  167             __comp = (cmp)(elm, (head)->sph_root);                      \
  168             if(__comp < 0) {                                            \
  169                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
  170                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
  171                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
  172             } else if (__comp > 0) {                                    \
  173                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
  174                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
  175                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
  176             } else                                                      \
  177                     return ((head)->sph_root);                          \
  178     }                                                                   \
  179     (head)->sph_root = (elm);                                           \
  180     return (NULL);                                                      \
  181 }                                                                       \
  182                                                                         \
  183 struct type *                                                           \
  184 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
  185 {                                                                       \
  186         struct type *__tmp;                                             \
  187         if (SPLAY_EMPTY(head))                                          \
  188                 return (NULL);                                          \
  189         name##_SPLAY(head, elm);                                        \
  190         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
  191                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
  192                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
  193                 } else {                                                \
  194                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  195                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
  196                         name##_SPLAY(head, elm);                        \
  197                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
  198                 }                                                       \
  199                 return (elm);                                           \
  200         }                                                               \
  201         return (NULL);                                                  \
  202 }                                                                       \
  203                                                                         \
  204 void                                                                    \
  205 name##_SPLAY(struct name *head, struct type *elm)                       \
  206 {                                                                       \
  207         struct type __node, *__left, *__right, *__tmp;                  \
  208         int __comp;                                                     \
  209 \
  210         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  211         __left = __right = &__node;                                     \
  212 \
  213         while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
  214                 if (__comp < 0) {                                       \
  215                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
  216                         if (__tmp == NULL)                              \
  217                                 break;                                  \
  218                         if ((cmp)(elm, __tmp) < 0){                     \
  219                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  220                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  221                                         break;                          \
  222                         }                                               \
  223                         SPLAY_LINKLEFT(head, __right, field);           \
  224                 } else if (__comp > 0) {                                \
  225                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  226                         if (__tmp == NULL)                              \
  227                                 break;                                  \
  228                         if ((cmp)(elm, __tmp) > 0){                     \
  229                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
  230                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  231                                         break;                          \
  232                         }                                               \
  233                         SPLAY_LINKRIGHT(head, __left, field);           \
  234                 }                                                       \
  235         }                                                               \
  236         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
  237 }                                                                       \
  238                                                                         \
  239 /* Splay with either the minimum or the maximum element                 \
  240  * Used to find minimum or maximum element in tree.                     \
  241  */                                                                     \
  242 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
  243 {                                                                       \
  244         struct type __node, *__left, *__right, *__tmp;                  \
  245 \
  246         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
  247         __left = __right = &__node;                                     \
  248 \
  249         while (1) {                                                     \
  250                 if (__comp < 0) {                                       \
  251                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
  252                         if (__tmp == NULL)                              \
  253                                 break;                                  \
  254                         if (__comp < 0){                                \
  255                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
  256                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
  257                                         break;                          \
  258                         }                                               \
  259                         SPLAY_LINKLEFT(head, __right, field);           \
  260                 } else if (__comp > 0) {                                \
  261                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
  262                         if (__tmp == NULL)                              \
  263                                 break;                                  \
  264                         if (__comp > 0) {                               \
  265                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
  266                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
  267                                         break;                          \
  268                         }                                               \
  269                         SPLAY_LINKRIGHT(head, __left, field);           \
  270                 }                                                       \
  271         }                                                               \
  272         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
  273 }
  274 
  275 #define SPLAY_NEGINF    -1
  276 #define SPLAY_INF       1
  277 
  278 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
  279 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
  280 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
  281 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
  282 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
  283                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
  284 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
  285                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
  286 
  287 #define SPLAY_FOREACH(x, name, head)                                    \
  288         for ((x) = SPLAY_MIN(name, head);                               \
  289              (x) != NULL;                                               \
  290              (x) = SPLAY_NEXT(name, head, x))
  291 
  292 /* Macros that define a red-black tree */
  293 #define RB_HEAD(name, type)                                             \
  294 struct name {                                                           \
  295         struct type *rbh_root; /* root of the tree */                   \
  296 }
  297 
  298 #define RB_INITIALIZER(root)                                            \
  299         { NULL }
  300 
  301 #define RB_INIT(root) do {                                              \
  302         (root)->rbh_root = NULL;                                        \
  303 } while (0)
  304 
  305 #define RB_BLACK        0
  306 #define RB_RED          1
  307 #define RB_ENTRY(type)                                                  \
  308 struct {                                                                \
  309         struct type *rbe_left;          /* left element */              \
  310         struct type *rbe_right;         /* right element */             \
  311         struct type *rbe_parent;        /* parent element */            \
  312         int rbe_color;                  /* node color */                \
  313 }
  314 
  315 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
  316 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
  317 #define RB_PARENT(elm, field)           (elm)->field.rbe_parent
  318 #define RB_COLOR(elm, field)            (elm)->field.rbe_color
  319 #define RB_ROOT(head)                   (head)->rbh_root
  320 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
  321 
  322 #define RB_SET(elm, parent, field) do {                                 \
  323         RB_PARENT(elm, field) = parent;                                 \
  324         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
  325         RB_COLOR(elm, field) = RB_RED;                                  \
  326 } while (0)
  327 
  328 #define RB_SET_BLACKRED(black, red, field) do {                         \
  329         RB_COLOR(black, field) = RB_BLACK;                              \
  330         RB_COLOR(red, field) = RB_RED;                                  \
  331 } while (0)
  332 
  333 #ifndef RB_AUGMENT
  334 #define RB_AUGMENT(x)   do {} while (0)
  335 #endif
  336 
  337 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
  338         (tmp) = RB_RIGHT(elm, field);                                   \
  339         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
  340                 RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
  341         }                                                               \
  342         RB_AUGMENT(elm);                                                \
  343         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
  344                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
  345                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
  346                 else                                                    \
  347                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  348         } else                                                          \
  349                 (head)->rbh_root = (tmp);                               \
  350         RB_LEFT(tmp, field) = (elm);                                    \
  351         RB_PARENT(elm, field) = (tmp);                                  \
  352         RB_AUGMENT(tmp);                                                \
  353         if ((RB_PARENT(tmp, field)))                                    \
  354                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
  355 } while (0)
  356 
  357 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
  358         (tmp) = RB_LEFT(elm, field);                                    \
  359         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
  360                 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
  361         }                                                               \
  362         RB_AUGMENT(elm);                                                \
  363         if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
  364                 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
  365                         RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
  366                 else                                                    \
  367                         RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
  368         } else                                                          \
  369                 (head)->rbh_root = (tmp);                               \
  370         RB_RIGHT(tmp, field) = (elm);                                   \
  371         RB_PARENT(elm, field) = (tmp);                                  \
  372         RB_AUGMENT(tmp);                                                \
  373         if ((RB_PARENT(tmp, field)))                                    \
  374                 RB_AUGMENT(RB_PARENT(tmp, field));                      \
  375 } while (0)
  376 
  377 /* Generates prototypes and inline functions */
  378 #define RB_PROTOTYPE(name, type, field, cmp)                            \
  379         RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
  380 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
  381         RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
  382 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
  383 attr void name##_RB_INSERT_COLOR(struct name *, struct type *);         \
  384 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
  385 attr struct type *name##_RB_REMOVE(struct name *, struct type *);       \
  386 attr struct type *name##_RB_INSERT(struct name *, struct type *);       \
  387 attr struct type *name##_RB_FIND(struct name *, struct type *);         \
  388 attr struct type *name##_RB_NFIND(struct name *, struct type *);        \
  389 attr struct type *name##_RB_NEXT(struct type *);                        \
  390 attr struct type *name##_RB_PREV(struct type *);                        \
  391 attr struct type *name##_RB_MINMAX(struct name *, int);                 \
  392                                                                         \
  393 
  394 /* Main rb operation.
  395  * Moves node close to the key of elm to top
  396  */
  397 #define RB_GENERATE(name, type, field, cmp)                             \
  398         RB_GENERATE_INTERNAL(name, type, field, cmp,)
  399 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
  400         RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
  401 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
  402 attr void                                                               \
  403 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
  404 {                                                                       \
  405         struct type *parent, *gparent, *tmp;                            \
  406         while ((parent = RB_PARENT(elm, field)) &&                      \
  407             RB_COLOR(parent, field) == RB_RED) {                        \
  408                 gparent = RB_PARENT(parent, field);                     \
  409                 if (parent == RB_LEFT(gparent, field)) {                \
  410                         tmp = RB_RIGHT(gparent, field);                 \
  411                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  412                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  413                                 RB_SET_BLACKRED(parent, gparent, field);\
  414                                 elm = gparent;                          \
  415                                 continue;                               \
  416                         }                                               \
  417                         if (RB_RIGHT(parent, field) == elm) {           \
  418                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  419                                 tmp = parent;                           \
  420                                 parent = elm;                           \
  421                                 elm = tmp;                              \
  422                         }                                               \
  423                         RB_SET_BLACKRED(parent, gparent, field);        \
  424                         RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
  425                 } else {                                                \
  426                         tmp = RB_LEFT(gparent, field);                  \
  427                         if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
  428                                 RB_COLOR(tmp, field) = RB_BLACK;        \
  429                                 RB_SET_BLACKRED(parent, gparent, field);\
  430                                 elm = gparent;                          \
  431                                 continue;                               \
  432                         }                                               \
  433                         if (RB_LEFT(parent, field) == elm) {            \
  434                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  435                                 tmp = parent;                           \
  436                                 parent = elm;                           \
  437                                 elm = tmp;                              \
  438                         }                                               \
  439                         RB_SET_BLACKRED(parent, gparent, field);        \
  440                         RB_ROTATE_LEFT(head, gparent, tmp, field);      \
  441                 }                                                       \
  442         }                                                               \
  443         RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
  444 }                                                                       \
  445                                                                         \
  446 attr void                                                               \
  447 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
  448 {                                                                       \
  449         struct type *tmp;                                               \
  450         while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
  451             elm != RB_ROOT(head)) {                                     \
  452                 if (RB_LEFT(parent, field) == elm) {                    \
  453                         tmp = RB_RIGHT(parent, field);                  \
  454                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  455                                 RB_SET_BLACKRED(tmp, parent, field);    \
  456                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  457                                 tmp = RB_RIGHT(parent, field);          \
  458                         }                                               \
  459                         if ((RB_LEFT(tmp, field) == NULL ||             \
  460                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  461                             (RB_RIGHT(tmp, field) == NULL ||            \
  462                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  463                                 RB_COLOR(tmp, field) = RB_RED;          \
  464                                 elm = parent;                           \
  465                                 parent = RB_PARENT(elm, field);         \
  466                         } else {                                        \
  467                                 if (RB_RIGHT(tmp, field) == NULL ||     \
  468                                     RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
  469                                         struct type *oleft;             \
  470                                         if ((oleft = RB_LEFT(tmp, field)))\
  471                                                 RB_COLOR(oleft, field) = RB_BLACK;\
  472                                         RB_COLOR(tmp, field) = RB_RED;  \
  473                                         RB_ROTATE_RIGHT(head, tmp, oleft, field);\
  474                                         tmp = RB_RIGHT(parent, field);  \
  475                                 }                                       \
  476                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  477                                 RB_COLOR(parent, field) = RB_BLACK;     \
  478                                 if (RB_RIGHT(tmp, field))               \
  479                                         RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
  480                                 RB_ROTATE_LEFT(head, parent, tmp, field);\
  481                                 elm = RB_ROOT(head);                    \
  482                                 break;                                  \
  483                         }                                               \
  484                 } else {                                                \
  485                         tmp = RB_LEFT(parent, field);                   \
  486                         if (RB_COLOR(tmp, field) == RB_RED) {           \
  487                                 RB_SET_BLACKRED(tmp, parent, field);    \
  488                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  489                                 tmp = RB_LEFT(parent, field);           \
  490                         }                                               \
  491                         if ((RB_LEFT(tmp, field) == NULL ||             \
  492                             RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
  493                             (RB_RIGHT(tmp, field) == NULL ||            \
  494                             RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
  495                                 RB_COLOR(tmp, field) = RB_RED;          \
  496                                 elm = parent;                           \
  497                                 parent = RB_PARENT(elm, field);         \
  498                         } else {                                        \
  499                                 if (RB_LEFT(tmp, field) == NULL ||      \
  500                                     RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
  501                                         struct type *oright;            \
  502                                         if ((oright = RB_RIGHT(tmp, field)))\
  503                                                 RB_COLOR(oright, field) = RB_BLACK;\
  504                                         RB_COLOR(tmp, field) = RB_RED;  \
  505                                         RB_ROTATE_LEFT(head, tmp, oright, field);\
  506                                         tmp = RB_LEFT(parent, field);   \
  507                                 }                                       \
  508                                 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
  509                                 RB_COLOR(parent, field) = RB_BLACK;     \
  510                                 if (RB_LEFT(tmp, field))                \
  511                                         RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
  512                                 RB_ROTATE_RIGHT(head, parent, tmp, field);\
  513                                 elm = RB_ROOT(head);                    \
  514                                 break;                                  \
  515                         }                                               \
  516                 }                                                       \
  517         }                                                               \
  518         if (elm)                                                        \
  519                 RB_COLOR(elm, field) = RB_BLACK;                        \
  520 }                                                                       \
  521                                                                         \
  522 attr struct type *                                                      \
  523 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
  524 {                                                                       \
  525         struct type *child, *parent, *old = elm;                        \
  526         int color;                                                      \
  527         if (RB_LEFT(elm, field) == NULL)                                \
  528                 child = RB_RIGHT(elm, field);                           \
  529         else if (RB_RIGHT(elm, field) == NULL)                          \
  530                 child = RB_LEFT(elm, field);                            \
  531         else {                                                          \
  532                 struct type *left;                                      \
  533                 elm = RB_RIGHT(elm, field);                             \
  534                 while ((left = RB_LEFT(elm, field)))                    \
  535                         elm = left;                                     \
  536                 child = RB_RIGHT(elm, field);                           \
  537                 parent = RB_PARENT(elm, field);                         \
  538                 color = RB_COLOR(elm, field);                           \
  539                 if (child)                                              \
  540                         RB_PARENT(child, field) = parent;               \
  541                 if (parent) {                                           \
  542                         if (RB_LEFT(parent, field) == elm)              \
  543                                 RB_LEFT(parent, field) = child;         \
  544                         else                                            \
  545                                 RB_RIGHT(parent, field) = child;        \
  546                         RB_AUGMENT(parent);                             \
  547                 } else                                                  \
  548                         RB_ROOT(head) = child;                          \
  549                 if (RB_PARENT(elm, field) == old)                       \
  550                         parent = elm;                                   \
  551                 (elm)->field = (old)->field;                            \
  552                 if (RB_PARENT(old, field)) {                            \
  553                         if (RB_LEFT(RB_PARENT(old, field), field) == old)\
  554                                 RB_LEFT(RB_PARENT(old, field), field) = elm;\
  555                         else                                            \
  556                                 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
  557                         RB_AUGMENT(RB_PARENT(old, field));              \
  558                 } else                                                  \
  559                         RB_ROOT(head) = elm;                            \
  560                 RB_PARENT(RB_LEFT(old, field), field) = elm;            \
  561                 if (RB_RIGHT(old, field))                               \
  562                         RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
  563                 if (parent) {                                           \
  564                         left = parent;                                  \
  565                         do {                                            \
  566                                 RB_AUGMENT(left);                       \
  567                         } while ((left = RB_PARENT(left, field)));      \
  568                 }                                                       \
  569                 goto color;                                             \
  570         }                                                               \
  571         parent = RB_PARENT(elm, field);                                 \
  572         color = RB_COLOR(elm, field);                                   \
  573         if (child)                                                      \
  574                 RB_PARENT(child, field) = parent;                       \
  575         if (parent) {                                                   \
  576                 if (RB_LEFT(parent, field) == elm)                      \
  577                         RB_LEFT(parent, field) = child;                 \
  578                 else                                                    \
  579                         RB_RIGHT(parent, field) = child;                \
  580                 RB_AUGMENT(parent);                                     \
  581         } else                                                          \
  582                 RB_ROOT(head) = child;                                  \
  583 color:                                                                  \
  584         if (color == RB_BLACK)                                          \
  585                 name##_RB_REMOVE_COLOR(head, parent, child);            \
  586         return (old);                                                   \
  587 }                                                                       \
  588                                                                         \
  589 /* Inserts a node into the RB tree */                                   \
  590 attr struct type *                                                      \
  591 name##_RB_INSERT(struct name *head, struct type *elm)                   \
  592 {                                                                       \
  593         struct type *tmp;                                               \
  594         struct type *parent = NULL;                                     \
  595         int comp = 0;                                                   \
  596         tmp = RB_ROOT(head);                                            \
  597         while (tmp) {                                                   \
  598                 parent = tmp;                                           \
  599                 comp = (cmp)(elm, parent);                              \
  600                 if (comp < 0)                                           \
  601                         tmp = RB_LEFT(tmp, field);                      \
  602                 else if (comp > 0)                                      \
  603                         tmp = RB_RIGHT(tmp, field);                     \
  604                 else                                                    \
  605                         return (tmp);                                   \
  606         }                                                               \
  607         RB_SET(elm, parent, field);                                     \
  608         if (parent != NULL) {                                           \
  609                 if (comp < 0)                                           \
  610                         RB_LEFT(parent, field) = elm;                   \
  611                 else                                                    \
  612                         RB_RIGHT(parent, field) = elm;                  \
  613                 RB_AUGMENT(parent);                                     \
  614         } else                                                          \
  615                 RB_ROOT(head) = elm;                                    \
  616         name##_RB_INSERT_COLOR(head, elm);                              \
  617         return (NULL);                                                  \
  618 }                                                                       \
  619                                                                         \
  620 /* Finds the node with the same key as elm */                           \
  621 attr struct type *                                                      \
  622 name##_RB_FIND(struct name *head, struct type *elm)                     \
  623 {                                                                       \
  624         struct type *tmp = RB_ROOT(head);                               \
  625         int comp;                                                       \
  626         while (tmp) {                                                   \
  627                 comp = cmp(elm, tmp);                                   \
  628                 if (comp < 0)                                           \
  629                         tmp = RB_LEFT(tmp, field);                      \
  630                 else if (comp > 0)                                      \
  631                         tmp = RB_RIGHT(tmp, field);                     \
  632                 else                                                    \
  633                         return (tmp);                                   \
  634         }                                                               \
  635         return (NULL);                                                  \
  636 }                                                                       \
  637                                                                         \
  638 /* Finds the first node greater than or equal to the search key */      \
  639 attr struct type *                                                      \
  640 name##_RB_NFIND(struct name *head, struct type *elm)                    \
  641 {                                                                       \
  642         struct type *tmp = RB_ROOT(head);                               \
  643         struct type *res = NULL;                                        \
  644         int comp;                                                       \
  645         while (tmp) {                                                   \
  646                 comp = cmp(elm, tmp);                                   \
  647                 if (comp < 0) {                                         \
  648                         res = tmp;                                      \
  649                         tmp = RB_LEFT(tmp, field);                      \
  650                 }                                                       \
  651                 else if (comp > 0)                                      \
  652                         tmp = RB_RIGHT(tmp, field);                     \
  653                 else                                                    \
  654                         return (tmp);                                   \
  655         }                                                               \
  656         return (res);                                                   \
  657 }                                                                       \
  658                                                                         \
  659 /* ARGSUSED */                                                          \
  660 attr struct type *                                                      \
  661 name##_RB_NEXT(struct type *elm)                                        \
  662 {                                                                       \
  663         if (RB_RIGHT(elm, field)) {                                     \
  664                 elm = RB_RIGHT(elm, field);                             \
  665                 while (RB_LEFT(elm, field))                             \
  666                         elm = RB_LEFT(elm, field);                      \
  667         } else {                                                        \
  668                 if (RB_PARENT(elm, field) &&                            \
  669                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
  670                         elm = RB_PARENT(elm, field);                    \
  671                 else {                                                  \
  672                         while (RB_PARENT(elm, field) &&                 \
  673                             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
  674                                 elm = RB_PARENT(elm, field);            \
  675                         elm = RB_PARENT(elm, field);                    \
  676                 }                                                       \
  677         }                                                               \
  678         return (elm);                                                   \
  679 }                                                                       \
  680                                                                         \
  681 /* ARGSUSED */                                                          \
  682 attr struct type *                                                      \
  683 name##_RB_PREV(struct type *elm)                                        \
  684 {                                                                       \
  685         if (RB_LEFT(elm, field)) {                                      \
  686                 elm = RB_LEFT(elm, field);                              \
  687                 while (RB_RIGHT(elm, field))                            \
  688                         elm = RB_RIGHT(elm, field);                     \
  689         } else {                                                        \
  690                 if (RB_PARENT(elm, field) &&                            \
  691                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
  692                         elm = RB_PARENT(elm, field);                    \
  693                 else {                                                  \
  694                         while (RB_PARENT(elm, field) &&                 \
  695                             (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
  696                                 elm = RB_PARENT(elm, field);            \
  697                         elm = RB_PARENT(elm, field);                    \
  698                 }                                                       \
  699         }                                                               \
  700         return (elm);                                                   \
  701 }                                                                       \
  702                                                                         \
  703 attr struct type *                                                      \
  704 name##_RB_MINMAX(struct name *head, int val)                            \
  705 {                                                                       \
  706         struct type *tmp = RB_ROOT(head);                               \
  707         struct type *parent = NULL;                                     \
  708         while (tmp) {                                                   \
  709                 parent = tmp;                                           \
  710                 if (val < 0)                                            \
  711                         tmp = RB_LEFT(tmp, field);                      \
  712                 else                                                    \
  713                         tmp = RB_RIGHT(tmp, field);                     \
  714         }                                                               \
  715         return (parent);                                                \
  716 }
  717 
  718 #define RB_NEGINF       -1
  719 #define RB_INF  1
  720 
  721 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
  722 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
  723 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
  724 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
  725 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
  726 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
  727 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
  728 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
  729 
  730 #define RB_FOREACH(x, name, head)                                       \
  731         for ((x) = RB_MIN(name, head);                                  \
  732              (x) != NULL;                                               \
  733              (x) = name##_RB_NEXT(x))
  734 
  735 #define RB_FOREACH_SAFE(x, name, head, y)                               \
  736         for ((x) = RB_MIN(name, head);                                  \
  737             ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);              \
  738              (x) = (y))
  739 
  740 #define RB_FOREACH_REVERSE(x, name, head)                               \
  741         for ((x) = RB_MAX(name, head);                                  \
  742              (x) != NULL;                                               \
  743              (x) = name##_RB_PREV(x))
  744 
  745 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                       \
  746         for ((x) = RB_MAX(name, head);                                  \
  747             ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);              \
  748              (x) = (y))
  749 
  750 
  751 /*
  752  * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
  753  *
  754  * Permission to use, copy, modify, and distribute this software for any
  755  * purpose with or without fee is hereby granted, provided that the above
  756  * copyright notice and this permission notice appear in all copies.
  757  *
  758  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  759  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  760  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  761  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  762  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  763  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  764  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  765  */
  766 
  767 struct rb_type {
  768         int             (*t_compare)(const void *, const void *);
  769         void            (*t_augment)(void *);
  770         unsigned int      t_offset;     /* offset of rb_entry in type */
  771 };
  772 
  773 struct rb_tree {
  774         struct rb_entry *rbt_root;
  775 };
  776 
  777 struct rb_entry {
  778         struct rb_entry  *rbt_parent;
  779         struct rb_entry  *rbt_left;
  780         struct rb_entry  *rbt_right;
  781         unsigned int      rbt_color;
  782 };
  783 
  784 #define RBT_HEAD(_name, _type)                                          \
  785 struct _name {                                                          \
  786         struct rb_tree rbh_root;                                        \
  787 }
  788 
  789 #define RBT_ENTRY(_type)        struct rb_entry
  790 
  791 static inline void
  792 _rb_init(struct rb_tree *rbt)
  793 {
  794         rbt->rbt_root = NULL;
  795 }
  796 
  797 static inline int
  798 _rb_empty(struct rb_tree *rbt)
  799 {
  800         return (rbt->rbt_root == NULL);
  801 }
  802 
  803 void    *_rb_insert(const struct rb_type *, struct rb_tree *, void *);
  804 void    *_rb_remove(const struct rb_type *, struct rb_tree *, void *);
  805 void    *_rb_find(const struct rb_type *, struct rb_tree *, const void *);
  806 void    *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *);
  807 void    *_rb_root(const struct rb_type *, struct rb_tree *);
  808 void    *_rb_min(const struct rb_type *, struct rb_tree *);
  809 void    *_rb_max(const struct rb_type *, struct rb_tree *);
  810 void    *_rb_next(const struct rb_type *, void *);
  811 void    *_rb_prev(const struct rb_type *, void *);
  812 void    *_rb_left(const struct rb_type *, void *);
  813 void    *_rb_right(const struct rb_type *, void *);
  814 void    *_rb_parent(const struct rb_type *, void *);
  815 void     _rb_set_left(const struct rb_type *, void *, void *);
  816 void     _rb_set_right(const struct rb_type *, void *, void *);
  817 void     _rb_set_parent(const struct rb_type *, void *, void *);
  818 void     _rb_poison(const struct rb_type *, void *, unsigned long);
  819 int      _rb_check(const struct rb_type *, void *, unsigned long);
  820 
  821 #define RBT_INITIALIZER(_head)  { { NULL } }
  822 
  823 #define RBT_PROTOTYPE(_name, _type, _field, _cmp)                       \
  824 extern const struct rb_type *const _name##_RBT_TYPE;                    \
  825                                                                         \
  826 __unused static inline void                                             \
  827 _name##_RBT_INIT(struct _name *head)                                    \
  828 {                                                                       \
  829         _rb_init(&head->rbh_root);                                      \
  830 }                                                                       \
  831                                                                         \
  832 __unused static inline struct _type *                                   \
  833 _name##_RBT_INSERT(struct _name *head, struct _type *elm)               \
  834 {                                                                       \
  835         return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm);      \
  836 }                                                                       \
  837                                                                         \
  838 __unused static inline struct _type *                                   \
  839 _name##_RBT_REMOVE(struct _name *head, struct _type *elm)               \
  840 {                                                                       \
  841         return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm);      \
  842 }                                                                       \
  843                                                                         \
  844 __unused static inline struct _type *                                   \
  845 _name##_RBT_FIND(struct _name *head, const struct _type *key)           \
  846 {                                                                       \
  847         return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key);        \
  848 }                                                                       \
  849                                                                         \
  850 __unused static inline struct _type *                                   \
  851 _name##_RBT_NFIND(struct _name *head, const struct _type *key)          \
  852 {                                                                       \
  853         return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key);       \
  854 }                                                                       \
  855                                                                         \
  856 __unused static inline struct _type *                                   \
  857 _name##_RBT_ROOT(struct _name *head)                                    \
  858 {                                                                       \
  859         return _rb_root(_name##_RBT_TYPE, &head->rbh_root);             \
  860 }                                                                       \
  861                                                                         \
  862 __unused static inline int                                              \
  863 _name##_RBT_EMPTY(struct _name *head)                                   \
  864 {                                                                       \
  865         return _rb_empty(&head->rbh_root);                              \
  866 }                                                                       \
  867                                                                         \
  868 __unused static inline struct _type *                                   \
  869 _name##_RBT_MIN(struct _name *head)                                     \
  870 {                                                                       \
  871         return _rb_min(_name##_RBT_TYPE, &head->rbh_root);              \
  872 }                                                                       \
  873                                                                         \
  874 __unused static inline struct _type *                                   \
  875 _name##_RBT_MAX(struct _name *head)                                     \
  876 {                                                                       \
  877         return _rb_max(_name##_RBT_TYPE, &head->rbh_root);              \
  878 }                                                                       \
  879                                                                         \
  880 __unused static inline struct _type *                                   \
  881 _name##_RBT_NEXT(struct _type *elm)                                     \
  882 {                                                                       \
  883         return _rb_next(_name##_RBT_TYPE, elm);                         \
  884 }                                                                       \
  885                                                                         \
  886 __unused static inline struct _type *                                   \
  887 _name##_RBT_PREV(struct _type *elm)                                     \
  888 {                                                                       \
  889         return _rb_prev(_name##_RBT_TYPE, elm);                         \
  890 }                                                                       \
  891                                                                         \
  892 __unused static inline struct _type *                                   \
  893 _name##_RBT_LEFT(struct _type *elm)                                     \
  894 {                                                                       \
  895         return _rb_left(_name##_RBT_TYPE, elm);                         \
  896 }                                                                       \
  897                                                                         \
  898 __unused static inline struct _type *                                   \
  899 _name##_RBT_RIGHT(struct _type *elm)                                    \
  900 {                                                                       \
  901         return _rb_right(_name##_RBT_TYPE, elm);                        \
  902 }                                                                       \
  903                                                                         \
  904 __unused static inline struct _type *                                   \
  905 _name##_RBT_PARENT(struct _type *elm)                                   \
  906 {                                                                       \
  907         return _rb_parent(_name##_RBT_TYPE, elm);                       \
  908 }                                                                       \
  909                                                                         \
  910 __unused static inline void                                             \
  911 _name##_RBT_SET_LEFT(struct _type *elm, struct _type *left)             \
  912 {                                                                       \
  913         _rb_set_left(_name##_RBT_TYPE, elm, left);                      \
  914 }                                                                       \
  915                                                                         \
  916 __unused static inline void                                             \
  917 _name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right)           \
  918 {                                                                       \
  919         _rb_set_right(_name##_RBT_TYPE, elm, right);                    \
  920 }                                                                       \
  921                                                                         \
  922 __unused static inline void                                             \
  923 _name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent)         \
  924 {                                                                       \
  925         _rb_set_parent(_name##_RBT_TYPE, elm, parent);                  \
  926 }                                                                       \
  927                                                                         \
  928 __unused static inline void                                             \
  929 _name##_RBT_POISON(struct _type *elm, unsigned long poison)             \
  930 {                                                                       \
  931         _rb_poison(_name##_RBT_TYPE, elm, poison);                      \
  932 }                                                                       \
  933                                                                         \
  934 __unused static inline int                                              \
  935 _name##_RBT_CHECK(struct _type *elm, unsigned long poison)              \
  936 {                                                                       \
  937         return _rb_check(_name##_RBT_TYPE, elm, poison);                \
  938 }
  939 
  940 #define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug)         \
  941 static int                                                              \
  942 _name##_RBT_COMPARE(const void *lptr, const void *rptr)                 \
  943 {                                                                       \
  944         const struct _type *l = lptr, *r = rptr;                        \
  945         return _cmp(l, r);                                              \
  946 }                                                                       \
  947 static const struct rb_type _name##_RBT_INFO = {                        \
  948         _name##_RBT_COMPARE,                                            \
  949         _aug,                                                           \
  950         offsetof(struct _type, _field),                                 \
  951 };                                                                      \
  952 const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO
  953 
  954 #define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug)          \
  955 static void                                                             \
  956 _name##_RBT_AUGMENT(void *ptr)                                          \
  957 {                                                                       \
  958         struct _type *p = ptr;                                          \
  959         return _aug(p);                                                 \
  960 }                                                                       \
  961 RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT)
  962 
  963 #define RBT_GENERATE(_name, _type, _field, _cmp)                        \
  964     RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
  965 
  966 #define RBT_INIT(_name, _head)          _name##_RBT_INIT(_head)
  967 #define RBT_INSERT(_name, _head, _elm)  _name##_RBT_INSERT(_head, _elm)
  968 #define RBT_REMOVE(_name, _head, _elm)  _name##_RBT_REMOVE(_head, _elm)
  969 #define RBT_FIND(_name, _head, _key)    _name##_RBT_FIND(_head, _key)
  970 #define RBT_NFIND(_name, _head, _key)   _name##_RBT_NFIND(_head, _key)
  971 #define RBT_ROOT(_name, _head)          _name##_RBT_ROOT(_head)
  972 #define RBT_EMPTY(_name, _head)         _name##_RBT_EMPTY(_head)
  973 #define RBT_MIN(_name, _head)           _name##_RBT_MIN(_head)
  974 #define RBT_MAX(_name, _head)           _name##_RBT_MAX(_head)
  975 #define RBT_NEXT(_name, _elm)           _name##_RBT_NEXT(_elm)
  976 #define RBT_PREV(_name, _elm)           _name##_RBT_PREV(_elm)
  977 #define RBT_LEFT(_name, _elm)           _name##_RBT_LEFT(_elm)
  978 #define RBT_RIGHT(_name, _elm)          _name##_RBT_RIGHT(_elm)
  979 #define RBT_PARENT(_name, _elm)         _name##_RBT_PARENT(_elm)
  980 #define RBT_SET_LEFT(_name, _elm, _l)   _name##_RBT_SET_LEFT(_elm, _l)
  981 #define RBT_SET_RIGHT(_name, _elm, _r)  _name##_RBT_SET_RIGHT(_elm, _r)
  982 #define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p)
  983 #define RBT_POISON(_name, _elm, _p)     _name##_RBT_POISON(_elm, _p)
  984 #define RBT_CHECK(_name, _elm, _p)      _name##_RBT_CHECK(_elm, _p)
  985 
  986 #define RBT_FOREACH(_e, _name, _head)                                   \
  987         for ((_e) = RBT_MIN(_name, (_head));                            \
  988              (_e) != NULL;                                              \
  989              (_e) = RBT_NEXT(_name, (_e)))
  990 
  991 #define RBT_FOREACH_SAFE(_e, _name, _head, _n)                          \
  992         for ((_e) = RBT_MIN(_name, (_head));                            \
  993              (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \
  994              (_e) = (_n))
  995 
  996 #define RBT_FOREACH_REVERSE(_e, _name, _head)                           \
  997         for ((_e) = RBT_MAX(_name, (_head));                            \
  998              (_e) != NULL;                                              \
  999              (_e) = RBT_PREV(_name, (_e)))
 1000 
 1001 #define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n)                  \
 1002         for ((_e) = RBT_MAX(_name, (_head));                            \
 1003              (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \
 1004              (_e) = (_n))
 1005 
 1006 #endif  /* _SYS_TREE_H_ */

Cache object: 98ff1a01b448967cc49c6034a3fac5f5


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


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