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-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 6cd8d40b5a0f75aaaf0114c18fb3264e


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