sptree01/sys/tree.h

0001 /*  $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
0002 /*  $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
0003
0004 /*-
0005  * SPDX-License-Identifier: BSD-2-Clause
0006  *
0007  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
0008  * All rights reserved.
0009  *
0010  * Redistribution and use in source and binary forms, with or without
0011  * modification, are permitted provided that the following conditions
0012  * are met:
0013  * 1. Redistributions of source code must retain the above copyright
0014  *    notice, this list of conditions and the following disclaimer.
0015  * 2. Redistributions in binary form must reproduce the above copyright
0016  *    notice, this list of conditions and the following disclaimer in the
0017  *    documentation and/or other materials provided with the distribution.
0018  *
0019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
0020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
0022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
0023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
0024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
0028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0029  */
0030
0031 #ifndef _SYS_TREE_H_
0032 #define _SYS_TREE_H_
0033
0034 #include <sys/cdefs.h>
0035
0036 /*
0037  * This file defines data structures for different types of trees:
0038  * splay trees and rank-balanced trees.
0039  *
0040  * A splay tree is a self-organizing data structure.  Every operation
0041  * on the tree causes a splay to happen.  The splay moves the requested
0042  * node to the root of the tree and partly rebalances it.
0043  *
0044  * This has the benefit that request locality causes faster lookups as
0045  * the requested nodes move to the top of the tree.  On the other hand,
0046  * every lookup causes memory writes.
0047  *
0048  * The Balance Theorem bounds the total access time for m operations
0049  * and n inserts on an initially empty tree as O((m + n)lg n).  The
0050  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
0051  *
0052  * A rank-balanced tree is a binary search tree with an integer
0053  * rank-difference as an attribute of each pointer from parent to child.
0054  * The sum of the rank-differences on any path from a node down to null is
0055  * the same, and defines the rank of that node. The rank of the null node
0056  * is -1.
0057  *
0058  * Different additional conditions define different sorts of balanced trees,
0059  * including "red-black" and "AVL" trees.  The set of conditions applied here
0060  * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in
0061  * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June
0062  * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper):
0063  *  - every rank-difference is 1 or 2.
0064  *  - the rank of any leaf is 1.
0065  *
0066  * For historical reasons, rank differences that are even are associated
0067  * with the color red (Rank-Even-Difference), and the child that a red edge
0068  * points to is called a red child.
0069  *
0070  * Every operation on a rank-balanced tree is bounded as O(lg n).
0071  * The maximum height of a rank-balanced tree is 2lg (n+1).
0072  */
0073
0074 #define SPLAY_HEAD(name, type)                      \
0075 struct name {                               \
0076     struct type *sph_root; /* root of the tree */           \
0077 }
0078
0079 #define SPLAY_INITIALIZER(root)                     \
0080     { NULL }
0081
0082 #define SPLAY_INIT(root) do {                       \
0083     (root)->sph_root = NULL;                    \
0084 } while (/*CONSTCOND*/ 0)
0085
0086 #define SPLAY_ENTRY(type)                       \
0087 struct {                                \
0088     struct type *spe_left; /* left element */           \
0089     struct type *spe_right; /* right element */         \
0090 }
0091
0092 #define SPLAY_LEFT(elm, field)      (elm)->field.spe_left
0093 #define SPLAY_RIGHT(elm, field)     (elm)->field.spe_right
0094 #define SPLAY_ROOT(head)        (head)->sph_root
0095 #define SPLAY_EMPTY(head)       (SPLAY_ROOT(head) == NULL)
0096
0097 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
0098 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {           \
0099     SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
0100     SPLAY_RIGHT(tmp, field) = (head)->sph_root;         \
0101     (head)->sph_root = tmp;                     \
0102 } while (/*CONSTCOND*/ 0)
0103
0104 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {            \
0105     SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
0106     SPLAY_LEFT(tmp, field) = (head)->sph_root;          \
0107     (head)->sph_root = tmp;                     \
0108 } while (/*CONSTCOND*/ 0)
0109
0110 #define SPLAY_LINKLEFT(head, tmp, field) do {               \
0111     SPLAY_LEFT(tmp, field) = (head)->sph_root;          \
0112     tmp = (head)->sph_root;                     \
0113     (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);     \
0114 } while (/*CONSTCOND*/ 0)
0115
0116 #define SPLAY_LINKRIGHT(head, tmp, field) do {              \
0117     SPLAY_RIGHT(tmp, field) = (head)->sph_root;         \
0118     tmp = (head)->sph_root;                     \
0119     (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);    \
0120 } while (/*CONSTCOND*/ 0)
0121
0122 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {     \
0123     SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
0124     SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
0125     SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
0126     SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
0127 } while (/*CONSTCOND*/ 0)
0128
0129 /* Generates prototypes and inline functions */
0130
0131 #define SPLAY_PROTOTYPE(name, type, field, cmp)             \
0132 void name##_SPLAY(struct name *, struct type *);            \
0133 void name##_SPLAY_MINMAX(struct name *, int);               \
0134 struct type *name##_SPLAY_INSERT(struct name *, struct type *);     \
0135 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);     \
0136                                     \
0137 /* Finds the node with the same key as elm */               \
0138 static __unused __inline struct type *                  \
0139 name##_SPLAY_FIND(struct name *head, struct type *elm)          \
0140 {                                   \
0141     if (SPLAY_EMPTY(head))                      \
0142         return(NULL);                       \
0143     name##_SPLAY(head, elm);                    \
0144     if ((cmp)(elm, (head)->sph_root) == 0)              \
0145         return (head->sph_root);                \
0146     return (NULL);                          \
0147 }                                   \
0148                                     \
0149 static __unused __inline struct type *                  \
0150 name##_SPLAY_NEXT(struct name *head, struct type *elm)          \
0151 {                                   \
0152     name##_SPLAY(head, elm);                    \
0153     if (SPLAY_RIGHT(elm, field) != NULL) {              \
0154         elm = SPLAY_RIGHT(elm, field);              \
0155         while (SPLAY_LEFT(elm, field) != NULL) {        \
0156             elm = SPLAY_LEFT(elm, field);           \
0157         }                           \
0158     } else                              \
0159         elm = NULL;                     \
0160     return (elm);                           \
0161 }                                   \
0162                                     \
0163 static __unused __inline struct type *                  \
0164 name##_SPLAY_MIN_MAX(struct name *head, int val)            \
0165 {                                   \
0166     name##_SPLAY_MINMAX(head, val);                 \
0167     return (SPLAY_ROOT(head));                  \
0168 }
0169
0170 /* Main splay operation.
0171  * Moves node close to the key of elm to top
0172  */
0173 #define SPLAY_GENERATE(name, type, field, cmp)              \
0174 struct type *                               \
0175 name##_SPLAY_INSERT(struct name *head, struct type *elm)        \
0176 {                                   \
0177     if (SPLAY_EMPTY(head)) {                        \
0178         SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
0179     } else {                                \
0180         __typeof(cmp(NULL, NULL)) __comp;               \
0181         name##_SPLAY(head, elm);                    \
0182         __comp = (cmp)(elm, (head)->sph_root);          \
0183         if (__comp < 0) {                       \
0184             SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
0185             SPLAY_RIGHT(elm, field) = (head)->sph_root;     \
0186             SPLAY_LEFT((head)->sph_root, field) = NULL;     \
0187         } else if (__comp > 0) {                    \
0188             SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
0189             SPLAY_LEFT(elm, field) = (head)->sph_root;      \
0190             SPLAY_RIGHT((head)->sph_root, field) = NULL;    \
0191         } else                          \
0192             return ((head)->sph_root);              \
0193     }                                   \
0194     (head)->sph_root = (elm);                       \
0195     return (NULL);                          \
0196 }                                   \
0197                                     \
0198 struct type *                               \
0199 name##_SPLAY_REMOVE(struct name *head, struct type *elm)        \
0200 {                                   \
0201     struct type *__tmp;                     \
0202     if (SPLAY_EMPTY(head))                      \
0203         return (NULL);                      \
0204     name##_SPLAY(head, elm);                    \
0205     if ((cmp)(elm, (head)->sph_root) == 0) {            \
0206         if (SPLAY_LEFT((head)->sph_root, field) == NULL) {  \
0207             (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
0208         } else {                        \
0209             __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
0210             (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
0211             name##_SPLAY(head, elm);            \
0212             SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
0213         }                           \
0214         return (elm);                       \
0215     }                               \
0216     return (NULL);                          \
0217 }                                   \
0218                                     \
0219 void                                    \
0220 name##_SPLAY(struct name *head, struct type *elm)           \
0221 {                                   \
0222     struct type __node, *__left, *__right, *__tmp;          \
0223     __typeof(cmp(NULL, NULL)) __comp;               \
0224 \
0225     SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
0226     __left = __right = &__node;                 \
0227 \
0228     while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {      \
0229         if (__comp < 0) {                   \
0230             __tmp = SPLAY_LEFT((head)->sph_root, field);    \
0231             if (__tmp == NULL)              \
0232                 break;                  \
0233             if ((cmp)(elm, __tmp) < 0){         \
0234                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
0235                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
0236                     break;              \
0237             }                       \
0238             SPLAY_LINKLEFT(head, __right, field);       \
0239         } else if (__comp > 0) {                \
0240             __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
0241             if (__tmp == NULL)              \
0242                 break;                  \
0243             if ((cmp)(elm, __tmp) > 0){         \
0244                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
0245                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
0246                     break;              \
0247             }                       \
0248             SPLAY_LINKRIGHT(head, __left, field);       \
0249         }                           \
0250     }                               \
0251     SPLAY_ASSEMBLE(head, &__node, __left, __right, field);      \
0252 }                                   \
0253                                     \
0254 /* Splay with either the minimum or the maximum element         \
0255  * Used to find minimum or maximum element in tree.         \
0256  */                                 \
0257 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
0258 {                                   \
0259     struct type __node, *__left, *__right, *__tmp;          \
0260 \
0261     SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
0262     __left = __right = &__node;                 \
0263 \
0264     while (1) {                         \
0265         if (__comp < 0) {                   \
0266             __tmp = SPLAY_LEFT((head)->sph_root, field);    \
0267             if (__tmp == NULL)              \
0268                 break;                  \
0269             if (__comp < 0){                \
0270                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
0271                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
0272                     break;              \
0273             }                       \
0274             SPLAY_LINKLEFT(head, __right, field);       \
0275         } else if (__comp > 0) {                \
0276             __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
0277             if (__tmp == NULL)              \
0278                 break;                  \
0279             if (__comp > 0) {               \
0280                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
0281                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
0282                     break;              \
0283             }                       \
0284             SPLAY_LINKRIGHT(head, __left, field);       \
0285         }                           \
0286     }                               \
0287     SPLAY_ASSEMBLE(head, &__node, __left, __right, field);      \
0288 }
0289
0290 #define SPLAY_NEGINF    -1
0291 #define SPLAY_INF   1
0292
0293 #define SPLAY_INSERT(name, x, y)    name##_SPLAY_INSERT(x, y)
0294 #define SPLAY_REMOVE(name, x, y)    name##_SPLAY_REMOVE(x, y)
0295 #define SPLAY_FIND(name, x, y)      name##_SPLAY_FIND(x, y)
0296 #define SPLAY_NEXT(name, x, y)      name##_SPLAY_NEXT(x, y)
0297 #define SPLAY_MIN(name, x)      (SPLAY_EMPTY(x) ? NULL  \
0298                     : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
0299 #define SPLAY_MAX(name, x)      (SPLAY_EMPTY(x) ? NULL  \
0300                     : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
0301
0302 #define SPLAY_FOREACH(x, name, head)                    \
0303     for ((x) = SPLAY_MIN(name, head);               \
0304          (x) != NULL;                       \
0305          (x) = SPLAY_NEXT(name, head, x))
0306
0307 /* Macros that define a rank-balanced tree */
0308 #define RB_HEAD(name, type)                     \
0309 struct name {                               \
0310     struct type *rbh_root; /* root of the tree */           \
0311 }
0312
0313 #define RB_INITIALIZER(root)                        \
0314     { NULL }
0315
0316 #define RB_INIT(root) do {                      \
0317     (root)->rbh_root = NULL;                    \
0318 } while (/*CONSTCOND*/ 0)
0319
0320 #define RB_ENTRY(type)                          \
0321 struct {                                \
0322     struct type *rbe_link[3];                   \
0323 }
0324
0325 /*
0326  * With the expectation that any object of struct type has an
0327  * address that is a multiple of 4, and that therefore the
0328  * 2 least significant bits of a pointer to struct type are
0329  * always zero, this implementation sets those bits to indicate
0330  * that the left or right child of the tree node is "red".
0331  */
0332 #define _RB_LINK(elm, dir, field)   (elm)->field.rbe_link[dir]
0333 #define _RB_UP(elm, field)      _RB_LINK(elm, 0, field)
0334 #define _RB_L               ((__uintptr_t)1)
0335 #define _RB_R               ((__uintptr_t)2)
0336 #define _RB_LR              ((__uintptr_t)3)
0337 #define _RB_BITS(elm)           (*(__uintptr_t *)&elm)
0338 #define _RB_BITSUP(elm, field)      _RB_BITS(_RB_UP(elm, field))
0339 #define _RB_PTR(elm)            (__typeof(elm))         \
0340                     ((__uintptr_t)elm & ~_RB_LR)
0341
0342 #define RB_PARENT(elm, field)       _RB_PTR(_RB_UP(elm, field))
0343 #define RB_LEFT(elm, field)     _RB_LINK(elm, _RB_L, field)
0344 #define RB_RIGHT(elm, field)        _RB_LINK(elm, _RB_R, field)
0345 #define RB_ROOT(head)           (head)->rbh_root
0346 #define RB_EMPTY(head)          (RB_ROOT(head) == NULL)
0347
0348 #define RB_SET_PARENT(dst, src, field) do {             \
0349     _RB_BITSUP(dst, field) = (__uintptr_t)src |         \
0350         (_RB_BITSUP(dst, field) & _RB_LR);              \
0351 } while (/*CONSTCOND*/ 0)
0352
0353 #define RB_SET(elm, parent, field) do {                 \
0354     _RB_UP(elm, field) = parent;                    \
0355     RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;      \
0356 } while (/*CONSTCOND*/ 0)
0357
0358 /*
0359  * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of
0360  * every modified subtree, from the bottom up to the root, to update augmented
0361  * node data.  RB_AUGMENT_CHECK returns true only when the update changes the
0362  * node data, so that updating can be stopped short of the root when it returns
0363  * false.
0364  */
0365 #ifndef RB_AUGMENT_CHECK
0366 #ifndef RB_AUGMENT
0367 #define RB_AUGMENT_CHECK(x) 0
0368 #else
0369 #define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), 1)
0370 #endif
0371 #endif
0372
0373 #define RB_UPDATE_AUGMENT(elm, field) do {              \
0374     __typeof(elm) rb_update_tmp = (elm);                \
0375     while (RB_AUGMENT_CHECK(rb_update_tmp) &&           \
0376         (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL)  \
0377         ;                           \
0378 } while (0)
0379
0380 #define RB_SWAP_CHILD(head, par, out, in, field) do {           \
0381     if (par == NULL)                        \
0382         RB_ROOT(head) = (in);                   \
0383     else if ((out) == RB_LEFT(par, field))              \
0384         RB_LEFT(par, field) = (in);             \
0385     else                                \
0386         RB_RIGHT(par, field) = (in);                \
0387 } while (/*CONSTCOND*/ 0)
0388
0389 /*
0390  * RB_ROTATE macro partially restructures the tree to improve balance. In the
0391  * case when dir is _RB_L, tmp is a right child of elm.  After rotation, elm
0392  * is a left child of tmp, and the subtree that represented the items between
0393  * them, which formerly hung to the left of tmp now hangs to the right of elm.
0394  * The parent-child relationship between elm and its former parent is not
0395  * changed; where this macro once updated those fields, that is now left to the
0396  * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice
0397  * update the same pair of pointer fields with distinct values.
0398  */
0399 #define RB_ROTATE(elm, tmp, dir, field) do {                \
0400     if ((_RB_LINK(elm, dir ^ _RB_LR, field) =           \
0401         _RB_LINK(tmp, dir, field)) != NULL)             \
0402         RB_SET_PARENT(_RB_LINK(tmp, dir, field), elm, field);   \
0403     _RB_LINK(tmp, dir, field) = (elm);              \
0404     RB_SET_PARENT(elm, tmp, field);                 \
0405 } while (/*CONSTCOND*/ 0)
0406
0407 /* Generates prototypes and inline functions */
0408 #define RB_PROTOTYPE(name, type, field, cmp)                \
0409     RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
0410 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)         \
0411     RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
0412 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)     \
0413     RB_PROTOTYPE_RANK(name, type, attr)             \
0414     RB_PROTOTYPE_INSERT_COLOR(name, type, attr);            \
0415     RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);            \
0416     RB_PROTOTYPE_INSERT_FINISH(name, type, attr);           \
0417     RB_PROTOTYPE_INSERT(name, type, attr);              \
0418     RB_PROTOTYPE_REMOVE(name, type, attr);              \
0419     RB_PROTOTYPE_FIND(name, type, attr);                \
0420     RB_PROTOTYPE_NFIND(name, type, attr);               \
0421     RB_PROTOTYPE_NEXT(name, type, attr);                \
0422     RB_PROTOTYPE_INSERT_NEXT(name, type, attr);         \
0423     RB_PROTOTYPE_PREV(name, type, attr);                \
0424     RB_PROTOTYPE_INSERT_PREV(name, type, attr);         \
0425     RB_PROTOTYPE_MINMAX(name, type, attr);              \
0426     RB_PROTOTYPE_REINSERT(name, type, attr);
0427 #ifdef _RB_DIAGNOSTIC
0428 #define RB_PROTOTYPE_RANK(name, type, attr)             \
0429     attr int name##_RB_RANK(struct type *);
0430 #else
0431 #define RB_PROTOTYPE_RANK(name, type, attr)
0432 #endif
0433 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)         \
0434     attr struct type *name##_RB_INSERT_COLOR(struct name *,     \
0435         struct type *, struct type *)
0436 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)         \
0437     attr struct type *name##_RB_REMOVE_COLOR(struct name *,     \
0438         struct type *, struct type *)
0439 #define RB_PROTOTYPE_REMOVE(name, type, attr)               \
0440     attr struct type *name##_RB_REMOVE(struct name *, struct type *)
0441 #define RB_PROTOTYPE_INSERT_FINISH(name, type, attr)            \
0442     attr struct type *name##_RB_INSERT_FINISH(struct name *,    \
0443         struct type *, struct type **, struct type *)
0444 #define RB_PROTOTYPE_INSERT(name, type, attr)               \
0445     attr struct type *name##_RB_INSERT(struct name *, struct type *)
0446 #define RB_PROTOTYPE_FIND(name, type, attr)             \
0447     attr struct type *name##_RB_FIND(struct name *, struct type *)
0448 #define RB_PROTOTYPE_NFIND(name, type, attr)                \
0449     attr struct type *name##_RB_NFIND(struct name *, struct type *)
0450 #define RB_PROTOTYPE_NEXT(name, type, attr)             \
0451     attr struct type *name##_RB_NEXT(struct type *)
0452 #define RB_PROTOTYPE_INSERT_NEXT(name, type, attr)          \
0453     attr struct type *name##_RB_INSERT_NEXT(struct name *,      \
0454         struct type *, struct type *)
0455 #define RB_PROTOTYPE_PREV(name, type, attr)             \
0456     attr struct type *name##_RB_PREV(struct type *)
0457 #define RB_PROTOTYPE_INSERT_PREV(name, type, attr)          \
0458     attr struct type *name##_RB_INSERT_PREV(struct name *,      \
0459         struct type *, struct type *)
0460 #define RB_PROTOTYPE_MINMAX(name, type, attr)               \
0461     attr struct type *name##_RB_MINMAX(struct name *, int)
0462 #define RB_PROTOTYPE_REINSERT(name, type, attr)         \
0463     attr struct type *name##_RB_REINSERT(struct name *, struct type *)
0464
0465 /* Main rb operation.
0466  * Moves node close to the key of elm to top
0467  */
0468 #define RB_GENERATE(name, type, field, cmp)             \
0469     RB_GENERATE_INTERNAL(name, type, field, cmp,)
0470 #define RB_GENERATE_STATIC(name, type, field, cmp)          \
0471     RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
0472 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)      \
0473     RB_GENERATE_RANK(name, type, field, attr)           \
0474     RB_GENERATE_INSERT_COLOR(name, type, field, attr)       \
0475     RB_GENERATE_REMOVE_COLOR(name, type, field, attr)       \
0476     RB_GENERATE_INSERT_FINISH(name, type, field, attr)      \
0477     RB_GENERATE_INSERT(name, type, field, cmp, attr)        \
0478     RB_GENERATE_REMOVE(name, type, field, attr)         \
0479     RB_GENERATE_FIND(name, type, field, cmp, attr)          \
0480     RB_GENERATE_NFIND(name, type, field, cmp, attr)         \
0481     RB_GENERATE_NEXT(name, type, field, attr)           \
0482     RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)       \
0483     RB_GENERATE_PREV(name, type, field, attr)           \
0484     RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)       \
0485     RB_GENERATE_MINMAX(name, type, field, attr)         \
0486     RB_GENERATE_REINSERT(name, type, field, cmp, attr)
0487
0488 #ifdef _RB_DIAGNOSTIC
0489 #ifndef RB_AUGMENT
0490 #define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)
0491 #else
0492 #define _RB_AUGMENT_VERIFY(x) 0
0493 #endif
0494 #define RB_GENERATE_RANK(name, type, field, attr)           \
0495 /*                                  \
0496  * Return the rank of the subtree rooted at elm, or -1 if the subtree   \
0497  * is not rank-balanced, or has inconsistent augmentation data.
0498  */                                 \
0499 attr int                                \
0500 name##_RB_RANK(struct type *elm)                    \
0501 {                                   \
0502     struct type *left, *right, *up;                 \
0503     int left_rank, right_rank;                  \
0504                                     \
0505     if (elm == NULL)                        \
0506         return (0);                     \
0507     up = _RB_UP(elm, field);                    \
0508     left = RB_LEFT(elm, field);                 \
0509     left_rank = ((_RB_BITS(up) & _RB_L) ? 2 : 1) +          \
0510         name##_RB_RANK(left);                   \
0511     right = RB_RIGHT(elm, field);                   \
0512     right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) +         \
0513         name##_RB_RANK(right);                  \
0514     if (left_rank != right_rank ||                  \
0515         (left_rank == 2 && left == NULL && right == NULL) ||    \
0516         _RB_AUGMENT_VERIFY(elm))                    \
0517         return (-1);                        \
0518     return (left_rank);                     \
0519 }
0520 #else
0521 #define RB_GENERATE_RANK(name, type, field, attr)
0522 #endif
0523
0524 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)       \
0525 attr struct type *                          \
0526 name##_RB_INSERT_COLOR(struct name *head,               \
0527     struct type *parent, struct type *elm)              \
0528 {                                   \
0529     /*                              \
0530      * Initially, elm is a leaf.  Either its parent was previously  \
0531      * a leaf, with two black null children, or an interior node    \
0532      * with a black non-null child and a red null child. The        \
0533      * balance criterion "the rank of any leaf is 1" precludes the  \
0534      * possibility of two red null children for the initial parent. \
0535      * So the first loop iteration cannot lead to accessing an      \
0536      * uninitialized 'child', and a later iteration can only happen \
0537      * when a value has been assigned to 'child' in the previous    \
0538      * one.                             \
0539      */                             \
0540     struct type *child, *child_up, *gpar;               \
0541     __uintptr_t elmdir, sibdir;                 \
0542                                     \
0543     do {                                \
0544         /* the rank of the tree rooted at elm grew */       \
0545         gpar = _RB_UP(parent, field);               \
0546         elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
0547         if (_RB_BITS(gpar) & elmdir) {              \
0548             /* shorten the parent-elm edge to rebalance */  \
0549             _RB_BITSUP(parent, field) ^= elmdir;        \
0550             return (NULL);                  \
0551         }                           \
0552         sibdir = elmdir ^ _RB_LR;               \
0553         /* the other edge must change length */         \
0554         _RB_BITSUP(parent, field) ^= sibdir;            \
0555         if ((_RB_BITS(gpar) & _RB_LR) == 0) {           \
0556             /* both edges now short, retry from parent */   \
0557             child = elm;                    \
0558             elm = parent;                   \
0559             continue;                   \
0560         }                           \
0561         _RB_UP(parent, field) = gpar = _RB_PTR(gpar);       \
0562         if (_RB_BITSUP(elm, field) & elmdir) {          \
0563             /*                      \
0564              * Exactly one of the edges descending from elm \
0565              * is long. The long one is in the same     \
0566              * direction as the edge from parent to elm,    \
0567              * so change that by rotation.  The edge from   \
0568              * parent to z was shortened above.  Shorten    \
0569              * the long edge down from elm, and adjust  \
0570              * other edge lengths based on the downward \
0571              * edges from 'child'.              \
0572              *                      \
0573              *       par         par        \
0574              *      /   \       /   \       \
0575              *    elm    z         /     z      \
0576              *   /  \            child      \
0577              *  /  child         /   \      \
0578              *     /   /  \        elm    \     \
0579              *    w   /    \      /   \    y        \
0580              *   x      y    w     \        \
0581              *              x       \
0582              */                     \
0583             RB_ROTATE(elm, child, elmdir, field);       \
0584             child_up = _RB_UP(child, field);        \
0585             if (_RB_BITS(child_up) & sibdir)        \
0586                 _RB_BITSUP(parent, field) ^= elmdir;    \
0587             if (_RB_BITS(child_up) & elmdir)        \
0588                 _RB_BITSUP(elm, field) ^= _RB_LR;   \
0589             else                        \
0590                 _RB_BITSUP(elm, field) ^= elmdir;   \
0591             /* if child is a leaf, don't augment elm,   \
0592              * since it is restored to be a leaf again. */  \
0593             if ((_RB_BITS(child_up) & _RB_LR) == 0)     \
0594                 elm = child;                \
0595         } else                          \
0596             child = elm;                    \
0597                                     \
0598         /*                          \
0599          * The long edge descending from 'child' points back    \
0600          * in the direction of 'parent'. Rotate to make     \
0601          * 'parent' a child of 'child', then make both edges    \
0602          * of 'child' short to rebalance.           \
0603          *                          \
0604          *       par         child          \
0605          *      /   \       /     \         \
0606          *     /     z         x       par      \
0607          *  child                 /   \     \
0608          *   /  \                /     z        \
0609          *  x    \              y           \
0610          *        y                     \
0611          */                         \
0612         RB_ROTATE(parent, child, sibdir, field);        \
0613         _RB_UP(child, field) = gpar;                \
0614         RB_SWAP_CHILD(head, gpar, parent, child, field);    \
0615         /*                          \
0616          * Elements rotated down have new, smaller subtrees,    \
0617          * so update augmentation for them.         \
0618          */                         \
0619         if (elm != child)                   \
0620             (void)RB_AUGMENT_CHECK(elm);            \
0621         (void)RB_AUGMENT_CHECK(parent);             \
0622         return (child);                     \
0623     } while ((parent = gpar) != NULL);              \
0624     return (NULL);                          \
0625 }
0626
0627 #ifndef RB_STRICT_HST
0628 /*
0629  * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
0630  * 'parent' with one higher rank, and then reduces its rank if 'parent' has
0631  * become a leaf.  This implementation always has the parent in its new position
0632  * with lower rank, to avoid the leaf check.  Define RB_STRICT_HST to 1 to get
0633  * the behavior that HST describes.
0634  */
0635 #define RB_STRICT_HST 0
0636 #endif
0637
0638 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)       \
0639 attr struct type *                          \
0640 name##_RB_REMOVE_COLOR(struct name *head,               \
0641     struct type *parent, struct type *elm)              \
0642 {                                   \
0643     struct type *gpar, *sib, *up;                   \
0644     __uintptr_t elmdir, sibdir;                 \
0645                                     \
0646     if (RB_RIGHT(parent, field) == elm &&               \
0647         RB_LEFT(parent, field) == elm) {                \
0648         /* Deleting a leaf that is an only-child creates a  \
0649          * rank-2 leaf. Demote that leaf. */            \
0650         _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \
0651         elm = parent;                       \
0652         if ((parent = _RB_UP(elm, field)) == NULL)      \
0653             return (NULL);                  \
0654     }                               \
0655     do {                                \
0656         /* the rank of the tree rooted at elm shrank */     \
0657         gpar = _RB_UP(parent, field);               \
0658         elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
0659         _RB_BITS(gpar) ^= elmdir;               \
0660         if (_RB_BITS(gpar) & elmdir) {              \
0661             /* lengthen the parent-elm edge to rebalance */ \
0662             _RB_UP(parent, field) = gpar;           \
0663             return (NULL);                  \
0664         }                           \
0665         if (_RB_BITS(gpar) & _RB_LR) {              \
0666             /* shorten other edge, retry from parent */ \
0667             _RB_BITS(gpar) ^= _RB_LR;           \
0668             _RB_UP(parent, field) = gpar;           \
0669             gpar = _RB_PTR(gpar);               \
0670             continue;                   \
0671         }                           \
0672         sibdir = elmdir ^ _RB_LR;               \
0673         sib = _RB_LINK(parent, sibdir, field);          \
0674         up = _RB_UP(sib, field);                \
0675         _RB_BITS(up) ^= _RB_LR;                 \
0676         if ((_RB_BITS(up) & _RB_LR) == 0) {         \
0677             /* shorten edges descending from sib, retry */  \
0678             _RB_UP(sib, field) = up;            \
0679             continue;                   \
0680         }                           \
0681         if ((_RB_BITS(up) & sibdir) == 0) {         \
0682             /*                      \
0683              * The edge descending from 'sib' away from \
0684              * 'parent' is long.  The short edge descending \
0685              * from 'sib' toward 'parent' points to 'elm*'  \
0686              * Rotate to make 'sib' a child of 'elm*'   \
0687              * then adjust the lengths of the edges     \
0688              * descending from 'sib' and 'elm*'.        \
0689              *                      \
0690              *       par         par        \
0691              *      /   \       /   \       \
0692              *     /    sib       elm    \      \
0693              *    / / \             elm*    \
0694              *  elm   elm* \                /  \    \
0695              *        / \   \          /    \   \
0696              *       /   \   z        /      \  \
0697              *      x     y      x      sib \
0698              *                      /  \    \
0699              *                     /    z   \
0700              *                    y     \
0701              */                     \
0702             elm = _RB_LINK(sib, elmdir, field);     \
0703             /* elm is a 1-child.  First rotate at elm. */   \
0704             RB_ROTATE(sib, elm, sibdir, field);     \
0705             up = _RB_UP(elm, field);            \
0706             _RB_BITSUP(parent, field) ^=            \
0707                 (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir;  \
0708             _RB_BITSUP(sib, field) ^=           \
0709                 (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir;  \
0710             _RB_BITSUP(elm, field) |= _RB_LR;       \
0711         } else {                        \
0712             if ((_RB_BITS(up) & elmdir) == 0 &&     \
0713                 RB_STRICT_HST && elm != NULL) {     \
0714                 /* if parent does not become a leaf,    \
0715                    do not demote parent yet. */     \
0716                 _RB_BITSUP(parent, field) ^= sibdir;    \
0717                 _RB_BITSUP(sib, field) ^= _RB_LR;   \
0718             } else if ((_RB_BITS(up) & elmdir) == 0) {  \
0719                 /* demote parent. */            \
0720                 _RB_BITSUP(parent, field) ^= elmdir;    \
0721                 _RB_BITSUP(sib, field) ^= sibdir;   \
0722             } else                      \
0723                 _RB_BITSUP(sib, field) ^= sibdir;   \
0724             elm = sib;                  \
0725         }                           \
0726                                     \
0727         /*                          \
0728          * The edge descending from 'elm' away from 'parent'    \
0729          * is short.  Rotate to make 'parent' a child of 'elm', \
0730          * then lengthen the short edges descending from    \
0731          * 'parent' and 'elm' to rebalance.         \
0732          *                          \
0733          *       par         elm            \
0734          *      /   \       /   \           \
0735          *     e     \         /     \          \
0736          *       elm          /       \         \
0737          *      /  \        par        s        \
0738          *         /    \      /   \            \
0739          *        /      \    e \           \
0740          *       x        s      x          \
0741          */                         \
0742         RB_ROTATE(parent, elm, elmdir, field);          \
0743         RB_SET_PARENT(elm, gpar, field);            \
0744         RB_SWAP_CHILD(head, gpar, parent, elm, field);      \
0745         /*                          \
0746          * An element rotated down, but not into the search \
0747          * path has a new, smaller subtree, so update       \
0748          * augmentation for it.                 \
0749          */                         \
0750         if (sib != elm)                     \
0751             (void)RB_AUGMENT_CHECK(sib);            \
0752         return (parent);                    \
0753     } while (elm = parent, (parent = gpar) != NULL);        \
0754     return (NULL);                          \
0755 }
0756
0757 #define _RB_AUGMENT_WALK(elm, match, field)             \
0758 do {                                    \
0759     if (match == elm)                       \
0760         match = NULL;                       \
0761 } while (RB_AUGMENT_CHECK(elm) &&                   \
0762     (elm = RB_PARENT(elm, field)) != NULL)
0763
0764 #define RB_GENERATE_REMOVE(name, type, field, attr)         \
0765 attr struct type *                          \
0766 name##_RB_REMOVE(struct name *head, struct type *out)           \
0767 {                                   \
0768     struct type *child, *in, *opar, *parent;            \
0769                                     \
0770     child = RB_LEFT(out, field);                    \
0771     in = RB_RIGHT(out, field);                  \
0772     opar = _RB_UP(out, field);                  \
0773     if (in == NULL || child == NULL) {              \
0774         in = child = (in == NULL ? child : in);         \
0775         parent = opar = _RB_PTR(opar);              \
0776     } else {                            \
0777         parent = in;                        \
0778         while (RB_LEFT(in, field))              \
0779             in = RB_LEFT(in, field);            \
0780         RB_SET_PARENT(child, in, field);            \
0781         RB_LEFT(in, field) = child;             \
0782         child = RB_RIGHT(in, field);                \
0783         if (parent != in) {                 \
0784             RB_SET_PARENT(parent, in, field);       \
0785             RB_RIGHT(in, field) = parent;           \
0786             parent = RB_PARENT(in, field);          \
0787             RB_LEFT(parent, field) = child;         \
0788         }                           \
0789         _RB_UP(in, field) = opar;               \
0790         opar = _RB_PTR(opar);                   \
0791     }                               \
0792     RB_SWAP_CHILD(head, opar, out, in, field);          \
0793     if (child != NULL)                      \
0794         _RB_UP(child, field) = parent;              \
0795     if (parent != NULL) {                       \
0796         opar = name##_RB_REMOVE_COLOR(head, parent, child); \
0797         /* if rotation has made 'parent' the root of the same   \
0798          * subtree as before, don't re-augment it. */       \
0799         if (parent == in && RB_LEFT(parent, field) == NULL) {   \
0800             opar = NULL;                    \
0801             parent = RB_PARENT(parent, field);      \
0802         }                           \
0803         _RB_AUGMENT_WALK(parent, opar, field);          \
0804         if (opar != NULL) {                 \
0805             /*                      \
0806              * Elements rotated into the search path have   \
0807              * changed subtrees, so update augmentation for \
0808              * them if AUGMENT_WALK didn't.         \
0809              */                     \
0810             (void)RB_AUGMENT_CHECK(opar);           \
0811             (void)RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \
0812         }                           \
0813     }                               \
0814     return (out);                           \
0815 }
0816
0817 #define RB_GENERATE_INSERT_FINISH(name, type, field, attr)      \
0818 /* Inserts a node into the RB tree */                   \
0819 attr struct type *                          \
0820 name##_RB_INSERT_FINISH(struct name *head, struct type *parent,     \
0821     struct type **pptr, struct type *elm)               \
0822 {                                   \
0823     struct type *tmp = NULL;                    \
0824                                     \
0825     RB_SET(elm, parent, field);                 \
0826     *pptr = elm;                            \
0827     if (parent != NULL)                     \
0828         tmp = name##_RB_INSERT_COLOR(head, parent, elm);    \
0829     _RB_AUGMENT_WALK(elm, tmp, field);              \
0830     if (tmp != NULL)                        \
0831         /*                          \
0832          * An element rotated into the search path has a    \
0833          * changed subtree, so update augmentation for it if    \
0834          * AUGMENT_WALK didn't.                 \
0835          */                         \
0836         (void)RB_AUGMENT_CHECK(tmp);                \
0837     return (NULL);                          \
0838 }
0839
0840 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)        \
0841 /* Inserts a node into the RB tree */                   \
0842 attr struct type *                          \
0843 name##_RB_INSERT(struct name *head, struct type *elm)           \
0844 {                                   \
0845     struct type *tmp;                       \
0846     struct type **tmpp = &RB_ROOT(head);                \
0847     struct type *parent = NULL;                 \
0848                                     \
0849     while ((tmp = *tmpp) != NULL) {                 \
0850         parent = tmp;                       \
0851         __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent);    \
0852         if (comp < 0)                       \
0853             tmpp = &RB_LEFT(parent, field);         \
0854         else if (comp > 0)                  \
0855             tmpp = &RB_RIGHT(parent, field);        \
0856         else                            \
0857             return (parent);                \
0858     }                               \
0859     return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm));  \
0860 }
0861
0862 #define RB_GENERATE_FIND(name, type, field, cmp, attr)          \
0863 /* Finds the node with the same key as elm */               \
0864 attr struct type *                          \
0865 name##_RB_FIND(struct name *head, struct type *elm)         \
0866 {                                   \
0867     struct type *tmp = RB_ROOT(head);               \
0868     __typeof(cmp(NULL, NULL)) comp;                 \
0869     while (tmp) {                           \
0870         comp = cmp(elm, tmp);                   \
0871         if (comp < 0)                       \
0872             tmp = RB_LEFT(tmp, field);          \
0873         else if (comp > 0)                  \
0874             tmp = RB_RIGHT(tmp, field);         \
0875         else                            \
0876             return (tmp);                   \
0877     }                               \
0878     return (NULL);                          \
0879 }
0880
0881 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)         \
0882 /* Finds the first node greater than or equal to the search key */  \
0883 attr struct type *                          \
0884 name##_RB_NFIND(struct name *head, struct type *elm)            \
0885 {                                   \
0886     struct type *tmp = RB_ROOT(head);               \
0887     struct type *res = NULL;                    \
0888     __typeof(cmp(NULL, NULL)) comp;                 \
0889     while (tmp) {                           \
0890         comp = cmp(elm, tmp);                   \
0891         if (comp < 0) {                     \
0892             res = tmp;                  \
0893             tmp = RB_LEFT(tmp, field);          \
0894         }                           \
0895         else if (comp > 0)                  \
0896             tmp = RB_RIGHT(tmp, field);         \
0897         else                            \
0898             return (tmp);                   \
0899     }                               \
0900     return (res);                           \
0901 }
0902
0903 #define RB_GENERATE_NEXT(name, type, field, attr)           \
0904 /* ARGSUSED */                              \
0905 attr struct type *                          \
0906 name##_RB_NEXT(struct type *elm)                    \
0907 {                                   \
0908     if (RB_RIGHT(elm, field)) {                 \
0909         elm = RB_RIGHT(elm, field);             \
0910         while (RB_LEFT(elm, field))             \
0911             elm = RB_LEFT(elm, field);          \
0912     } else {                            \
0913         while (RB_PARENT(elm, field) &&             \
0914             (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
0915             elm = RB_PARENT(elm, field);            \
0916         elm = RB_PARENT(elm, field);                \
0917     }                               \
0918     return (elm);                           \
0919 }
0920
0921 #if defined(_KERNEL) && defined(DIAGNOSTIC)
0922 #define _RB_ORDER_CHECK(cmp, lo, hi) do {               \
0923     KASSERT((cmp)(lo, hi) < 0, ("out of order insertion"));     \
0924 } while (0)
0925 #else
0926 #define _RB_ORDER_CHECK(cmp, lo, hi) do {} while (0)
0927 #endif
0928
0929 #define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)       \
0930 /* Inserts a node into the next position in the RB tree */      \
0931 attr struct type *                          \
0932 name##_RB_INSERT_NEXT(struct name *head,                \
0933     struct type *elm, struct type *next)                \
0934 {                                   \
0935     struct type *tmp;                       \
0936     struct type **tmpp = &RB_RIGHT(elm, field);         \
0937                                     \
0938     _RB_ORDER_CHECK(cmp, elm, next);                \
0939     if (name##_RB_NEXT(elm) != NULL)                \
0940         _RB_ORDER_CHECK(cmp, next, name##_RB_NEXT(elm));    \
0941     while ((tmp = *tmpp) != NULL) {                 \
0942         elm = tmp;                      \
0943         tmpp = &RB_LEFT(elm, field);                \
0944     }                               \
0945     return (name##_RB_INSERT_FINISH(head, elm, tmpp, next));    \
0946 }
0947
0948 #define RB_GENERATE_PREV(name, type, field, attr)           \
0949 /* ARGSUSED */                              \
0950 attr struct type *                          \
0951 name##_RB_PREV(struct type *elm)                    \
0952 {                                   \
0953     if (RB_LEFT(elm, field)) {                  \
0954         elm = RB_LEFT(elm, field);              \
0955         while (RB_RIGHT(elm, field))                \
0956             elm = RB_RIGHT(elm, field);         \
0957     } else {                            \
0958         while (RB_PARENT(elm, field) &&             \
0959             (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
0960             elm = RB_PARENT(elm, field);            \
0961         elm = RB_PARENT(elm, field);                \
0962     }                               \
0963     return (elm);                           \
0964 }
0965
0966 #define RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)       \
0967 /* Inserts a node into the prev position in the RB tree */      \
0968 attr struct type *                          \
0969 name##_RB_INSERT_PREV(struct name *head,                \
0970     struct type *elm, struct type *prev)                \
0971 {                                   \
0972     struct type *tmp;                       \
0973     struct type **tmpp = &RB_LEFT(elm, field);          \
0974                                     \
0975     _RB_ORDER_CHECK(cmp, prev, elm);                \
0976     if (name##_RB_PREV(elm) != NULL)                \
0977         _RB_ORDER_CHECK(cmp, name##_RB_PREV(elm), prev);    \
0978     while ((tmp = *tmpp) != NULL) {                 \
0979         elm = tmp;                      \
0980         tmpp = &RB_RIGHT(elm, field);               \
0981     }                               \
0982     return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev));    \
0983 }
0984
0985 #define RB_GENERATE_MINMAX(name, type, field, attr)         \
0986 attr struct type *                          \
0987 name##_RB_MINMAX(struct name *head, int val)                \
0988 {                                   \
0989     struct type *tmp = RB_ROOT(head);               \
0990     struct type *parent = NULL;                 \
0991     while (tmp) {                           \
0992         parent = tmp;                       \
0993         if (val < 0)                        \
0994             tmp = RB_LEFT(tmp, field);          \
0995         else                            \
0996             tmp = RB_RIGHT(tmp, field);         \
0997     }                               \
0998     return (parent);                        \
0999 }
1000
1001 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr)      \
1002 attr struct type *                          \
1003 name##_RB_REINSERT(struct name *head, struct type *elm)         \
1004 {                                   \
1005     struct type *cmpelm;                        \
1006     if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&     \
1007         cmp(cmpelm, elm) >= 0) ||                   \
1008         ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&     \
1009         cmp(elm, cmpelm) >= 0)) {                   \
1010         /* XXXLAS: Remove/insert is heavy handed. */        \
1011         RB_REMOVE(name, head, elm);             \
1012         return (RB_INSERT(name, head, elm));            \
1013     }                               \
1014     return (NULL);                          \
1015 }                                   \
1016
1017 #define RB_NEGINF   -1
1018 #define RB_INF  1
1019
1020 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
1021 #define RB_INSERT_NEXT(name, x, y, z)   name##_RB_INSERT_NEXT(x, y, z)
1022 #define RB_INSERT_PREV(name, x, y, z)   name##_RB_INSERT_PREV(x, y, z)
1023 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
1024 #define RB_FIND(name, x, y) name##_RB_FIND(x, y)
1025 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
1026 #define RB_NEXT(name, x, y) name##_RB_NEXT(y)
1027 #define RB_PREV(name, x, y) name##_RB_PREV(y)
1028 #define RB_MIN(name, x)     name##_RB_MINMAX(x, RB_NEGINF)
1029 #define RB_MAX(name, x)     name##_RB_MINMAX(x, RB_INF)
1030 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)
1031
1032 #define RB_FOREACH(x, name, head)                   \
1033     for ((x) = RB_MIN(name, head);                  \
1034          (x) != NULL;                       \
1035          (x) = name##_RB_NEXT(x))
1036
1037 #define RB_FOREACH_FROM(x, name, y)                 \
1038     for ((x) = (y);                         \
1039         ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
1040          (x) = (y))
1041
1042 #define RB_FOREACH_SAFE(x, name, head, y)               \
1043     for ((x) = RB_MIN(name, head);                  \
1044         ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
1045          (x) = (y))
1046
1047 #define RB_FOREACH_REVERSE(x, name, head)               \
1048     for ((x) = RB_MAX(name, head);                  \
1049          (x) != NULL;                       \
1050          (x) = name##_RB_PREV(x))
1051
1052 #define RB_FOREACH_REVERSE_FROM(x, name, y)             \
1053     for ((x) = (y);                         \
1054         ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
1055          (x) = (y))
1056
1057 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)           \
1058     for ((x) = RB_MAX(name, head);                  \
1059         ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
1060          (x) = (y))
1061
1062 #endif  /* _SYS_TREE_H_ */