sys/sys/tree.h

   1 /*      $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
   2 /*      $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
   3 /* $FreeBSD$ */
   4
   5 /*-
   6  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   7  *
   8  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
   9  * All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  21  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  22  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  23  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  24  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  25  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifndef _SYS_TREE_H_
  33 #define _SYS_TREE_H_
  34
  35 #include <sys/cdefs.h>
  36
  37 /*
  38  * This file defines data structures for different types of trees:
  39  * splay trees and rank-balanced trees.
  40  *
  41  * A splay tree is a self-organizing data structure.  Every operation
  42  * on the tree causes a splay to happen.  The splay moves the requested
  43  * node to the root of the tree and partly rebalances it.
  44  *
  45  * This has the benefit that request locality causes faster lookups as
  46  * the requested nodes move to the top of the tree.  On the other hand,
  47  * every lookup causes memory writes.
  48  *
  49  * The Balance Theorem bounds the total access time for m operations
  50  * and n inserts on an initially empty tree as O((m + n)lg n).  The
  51  * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
  52  *
  53  * A rank-balanced tree is a binary search tree with an integer
  54  * rank-difference as an attribute of each pointer from parent to child.
  55  * The sum of the rank-differences on any path from a node down to null is
  56  * the same, and defines the rank of that node. The rank of the null node
  57  * is -1.
  58  *
  59  * Different additional conditions define different sorts of balanced trees,
  60  * including "red-black" and "AVL" trees.  The set of conditions applied here
  61  * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in
  62  * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June
  63  * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper):
  64  *      - every rank-difference is 1 or 2.
  65  *      - the rank of any leaf is 1.
  66  *
  67  * For historical reasons, rank differences that are even are associated
  68  * with the color red (Rank-Even-Difference), and the child that a red edge
  69  * points to is called a red child.
  70  *
  71  * Every operation on a rank-balanced tree is bounded as O(lg n).
  72  * The maximum height of a rank-balanced tree is 2lg (n+1).
  73  */
  74
  75 #define SPLAY_HEAD(name, type)                                          \
  76 struct name {                                                           \
  77         struct type *sph_root; /* root of the tree */                   \
  78 }
  79
  80 #define SPLAY_INITIALIZER(root)                                         \
  81         { NULL }
  82
  83 #define SPLAY_INIT(root) do {                                           \
  84         (root)->sph_root = NULL;                                        \
  85 } while (/*CONSTCOND*/ 0)
  86
  87 #define SPLAY_ENTRY(type)                                               \
  88 struct {                                                                \
  89         struct type *spe_left; /* left element */                       \
  90         struct type *spe_right; /* right element */                     \
  91 }
  92
  93 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
  94 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
  95 #define SPLAY_ROOT(head)                (head)->sph_root
  96 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
  97
  98 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  99 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
 100         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
 101         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 102         (head)->sph_root = tmp;                                         \
 103 } while (/*CONSTCOND*/ 0)
 104
 105 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
 106         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
 107         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 108         (head)->sph_root = tmp;                                         \
 109 } while (/*CONSTCOND*/ 0)
 110
 111 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
 112         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 113         tmp = (head)->sph_root;                                         \
 114         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
 115 } while (/*CONSTCOND*/ 0)
 116
 117 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
 118         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 119         tmp = (head)->sph_root;                                         \
 120         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
 121 } while (/*CONSTCOND*/ 0)
 122
 123 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
 124         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
 125         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
 126         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
 127         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
 128 } while (/*CONSTCOND*/ 0)
 129
 130 /* Generates prototypes and inline functions */
 131
 132 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
 133 void name##_SPLAY(struct name *, struct type *);                        \
 134 void name##_SPLAY_MINMAX(struct name *, int);                           \
 135 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
 136 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
 137                                                                         \
 138 /* Finds the node with the same key as elm */                           \
 139 static __unused __inline struct type *                                  \
 140 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
 141 {                                                                       \
 142         if (SPLAY_EMPTY(head))                                          \
 143                 return(NULL);                                           \
 144         name##_SPLAY(head, elm);                                        \
 145         if ((cmp)(elm, (head)->sph_root) == 0)                          \
 146                 return (head->sph_root);                                \
 147         return (NULL);                                                  \
 148 }                                                                       \
 149                                                                         \
 150 static __unused __inline struct type *                                  \
 151 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
 152 {                                                                       \
 153         name##_SPLAY(head, elm);                                        \
 154         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
 155                 elm = SPLAY_RIGHT(elm, field);                          \
 156                 while (SPLAY_LEFT(elm, field) != NULL) {                \
 157                         elm = SPLAY_LEFT(elm, field);                   \
 158                 }                                                       \
 159         } else                                                          \
 160                 elm = NULL;                                             \
 161         return (elm);                                                   \
 162 }                                                                       \
 163                                                                         \
 164 static __unused __inline struct type *                                  \
 165 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
 166 {                                                                       \
 167         name##_SPLAY_MINMAX(head, val);                                 \
 168         return (SPLAY_ROOT(head));                                      \
 169 }
 170
 171 /* Main splay operation.
 172  * Moves node close to the key of elm to top
 173  */
 174 #define SPLAY_GENERATE(name, type, field, cmp)                          \
 175 struct type *                                                           \
 176 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
 177 {                                                                       \
 178     if (SPLAY_EMPTY(head)) {                                            \
 179             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
 180     } else {                                                            \
 181             __typeof(cmp(NULL, NULL)) __comp;                           \
 182             name##_SPLAY(head, elm);                                    \
 183             __comp = (cmp)(elm, (head)->sph_root);                      \
 184             if(__comp < 0) {                                            \
 185                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
 186                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
 187                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
 188             } else if (__comp > 0) {                                    \
 189                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
 190                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
 191                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
 192             } else                                                      \
 193                     return ((head)->sph_root);                          \
 194     }                                                                   \
 195     (head)->sph_root = (elm);                                           \
 196     return (NULL);                                                      \
 197 }                                                                       \
 198                                                                         \
 199 struct type *                                                           \
 200 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
 201 {                                                                       \
 202         struct type *__tmp;                                             \
 203         if (SPLAY_EMPTY(head))                                          \
 204                 return (NULL);                                          \
 205         name##_SPLAY(head, elm);                                        \
 206         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
 207                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
 208                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
 209                 } else {                                                \
 210                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 211                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
 212                         name##_SPLAY(head, elm);                        \
 213                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
 214                 }                                                       \
 215                 return (elm);                                           \
 216         }                                                               \
 217         return (NULL);                                                  \
 218 }                                                                       \
 219                                                                         \
 220 void                                                                    \
 221 name##_SPLAY(struct name *head, struct type *elm)                       \
 222 {                                                                       \
 223         struct type __node, *__left, *__right, *__tmp;                  \
 224         __typeof(cmp(NULL, NULL)) __comp;                               \
 225 \
 226         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 227         __left = __right = &__node;                                     \
 228 \
 229         while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
 230                 if (__comp < 0) {                                       \
 231                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 232                         if (__tmp == NULL)                              \
 233                                 break;                                  \
 234                         if ((cmp)(elm, __tmp) < 0){                     \
 235                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 236                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 237                                         break;                          \
 238                         }                                               \
 239                         SPLAY_LINKLEFT(head, __right, field);           \
 240                 } else if (__comp > 0) {                                \
 241                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 242                         if (__tmp == NULL)                              \
 243                                 break;                                  \
 244                         if ((cmp)(elm, __tmp) > 0){                     \
 245                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 246                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 247                                         break;                          \
 248                         }                                               \
 249                         SPLAY_LINKRIGHT(head, __left, field);           \
 250                 }                                                       \
 251         }                                                               \
 252         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 253 }                                                                       \
 254                                                                         \
 255 /* Splay with either the minimum or the maximum element                 \
 256  * Used to find minimum or maximum element in tree.                     \
 257  */                                                                     \
 258 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 259 {                                                                       \
 260         struct type __node, *__left, *__right, *__tmp;                  \
 261 \
 262         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 263         __left = __right = &__node;                                     \
 264 \
 265         while (1) {                                                     \
 266                 if (__comp < 0) {                                       \
 267                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 268                         if (__tmp == NULL)                              \
 269                                 break;                                  \
 270                         if (__comp < 0){                                \
 271                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 272                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 273                                         break;                          \
 274                         }                                               \
 275                         SPLAY_LINKLEFT(head, __right, field);           \
 276                 } else if (__comp > 0) {                                \
 277                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 278                         if (__tmp == NULL)                              \
 279                                 break;                                  \
 280                         if (__comp > 0) {                               \
 281                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 282                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 283                                         break;                          \
 284                         }                                               \
 285                         SPLAY_LINKRIGHT(head, __left, field);           \
 286                 }                                                       \
 287         }                                                               \
 288         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 289 }
 290
 291 #define SPLAY_NEGINF    -1
 292 #define SPLAY_INF       1
 293
 294 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 295 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 296 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 297 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 298 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 299                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 300 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 301                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 302
 303 #define SPLAY_FOREACH(x, name, head)                                    \
 304         for ((x) = SPLAY_MIN(name, head);                               \
 305              (x) != NULL;                                               \
 306              (x) = SPLAY_NEXT(name, head, x))
 307
 308 /* Macros that define a rank-balanced tree */
 309 #define RB_HEAD(name, type)                                             \
 310 struct name {                                                           \
 311         struct type *rbh_root; /* root of the tree */                   \
 312 }
 313
 314 #define RB_INITIALIZER(root)                                            \
 315         { NULL }
 316
 317 #define RB_INIT(root) do {                                              \
 318         (root)->rbh_root = NULL;                                        \
 319 } while (/*CONSTCOND*/ 0)
 320
 321 #define RB_ENTRY(type)                                                  \
 322 struct {                                                                \
 323         struct type *rbe_link[3];                                       \
 324 }
 325
 326 /*
 327  * With the expectation that any object of struct type has an
 328  * address that is a multiple of 4, and that therefore the
 329  * 2 least significant bits of a pointer to struct type are
 330  * always zero, this implementation sets those bits to indicate
 331  * that the left or right child of the tree node is "red".
 332  */
 333 #define _RB_LINK(elm, dir, field)       (elm)->field.rbe_link[dir]
 334 #define _RB_UP(elm, field)              _RB_LINK(elm, 2, field)
 335 #define _RB_L                           ((__uintptr_t)1)
 336 #define _RB_R                           ((__uintptr_t)2)
 337 #define _RB_LR                          ((__uintptr_t)3)
 338 #define _RB_BITS(elm)                   (*(__uintptr_t *)&elm)
 339 #define _RB_BITSUP(elm, field)          _RB_BITS(_RB_UP(elm, field))
 340 #define _RB_PTR(elm)                    (__typeof(elm))                 \
 341                                         ((__uintptr_t)elm & ~_RB_LR)
 342
 343 #define RB_PARENT(elm, field)           _RB_PTR(_RB_UP(elm, field))
 344 #define RB_LEFT(elm, field)             _RB_LINK(elm, _RB_L-1, field)
 345 #define RB_RIGHT(elm, field)            _RB_LINK(elm, _RB_R-1, field)
 346 #define RB_ROOT(head)                   (head)->rbh_root
 347 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 348
 349 #define RB_SET_PARENT(dst, src, field) do {                             \
 350         _RB_BITSUP(dst, field) = (__uintptr_t)src |                     \
 351             (_RB_BITSUP(dst, field) & _RB_LR);                          \
 352 } while (/*CONSTCOND*/ 0)
 353
 354 #define RB_SET(elm, parent, field) do {                                 \
 355         _RB_UP(elm, field) = parent;                                    \
 356         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
 357 } while (/*CONSTCOND*/ 0)
 358
 359 /*
 360  * Either RB_AUGMENT or RB_AUGMENT_CHECK is invoked in a loop at the root of
 361  * every modified subtree, from the bottom up to the root, to update augmented
 362  * node data.  RB_AUGMENT_CHECK returns true only when the update changes the
 363  * node data, so that updating can be stopped short of the root when it returns
 364  * false.
 365  */
 366 #ifndef RB_AUGMENT_CHECK
 367 #ifndef RB_AUGMENT
 368 #define RB_AUGMENT_CHECK(x) 0
 369 #else
 370 #define RB_AUGMENT_CHECK(x) (RB_AUGMENT(x), 1)
 371 #endif
 372 #endif
 373
 374 #define RB_UPDATE_AUGMENT(elm, field) do {                              \
 375         __typeof(elm) rb_update_tmp = (elm);                            \
 376         while (RB_AUGMENT_CHECK(rb_update_tmp) &&                       \
 377             (rb_update_tmp = RB_PARENT(rb_update_tmp, field)) != NULL)  \
 378                 ;                                                       \
 379 } while (0)
 380
 381 #define RB_SWAP_CHILD(head, par, out, in, field) do {                   \
 382         if (par == NULL)                                                \
 383                 RB_ROOT(head) = (in);                                   \
 384         else if ((out) == RB_LEFT(par, field))                          \
 385                 RB_LEFT(par, field) = (in);                             \
 386         else                                                            \
 387                 RB_RIGHT(par, field) = (in);                            \
 388 } while (/*CONSTCOND*/ 0)
 389
 390 /*
 391  * RB_ROTATE macro partially restructures the tree to improve balance. In the
 392  * case when dir is _RB_L, tmp is a right child of elm.  After rotation, elm
 393  * is a left child of tmp, and the subtree that represented the items between
 394  * them, which formerly hung to the left of tmp now hangs to the right of elm.
 395  * The parent-child relationship between elm and its former parent is not
 396  * changed; where this macro once updated those fields, that is now left to the
 397  * caller of RB_ROTATE to clean up, so that a pair of rotations does not twice
 398  * update the same pair of pointer fields with distinct values.
 399  */
 400 #define RB_ROTATE(elm, tmp, dir, field) do {                            \
 401         if ((_RB_LINK(elm, (dir ^ _RB_LR)-1, field) =                   \
 402             _RB_LINK(tmp, dir-1, field)) != NULL)                       \
 403                 RB_SET_PARENT(_RB_LINK(tmp, dir-1, field), elm, field); \
 404         _RB_LINK(tmp, dir-1, field) = (elm);                            \
 405         RB_SET_PARENT(elm, tmp, field);                                 \
 406 } while (/*CONSTCOND*/ 0)
 407
 408 /* Generates prototypes and inline functions */
 409 #define RB_PROTOTYPE(name, type, field, cmp)                            \
 410         RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
 411 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
 412         RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 413 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
 414         RB_PROTOTYPE_RANK(name, type, attr)                             \
 415         RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr);                 \
 416         RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
 417         RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
 418         RB_PROTOTYPE_INSERT_FINISH(name, type, attr);                   \
 419         RB_PROTOTYPE_INSERT(name, type, attr);                          \
 420         RB_PROTOTYPE_REMOVE(name, type, attr);                          \
 421         RB_PROTOTYPE_FIND(name, type, attr);                            \
 422         RB_PROTOTYPE_NFIND(name, type, attr);                           \
 423         RB_PROTOTYPE_NEXT(name, type, attr);                            \
 424         RB_PROTOTYPE_INSERT_NEXT(name, type, attr);                     \
 425         RB_PROTOTYPE_PREV(name, type, attr);                            \
 426         RB_PROTOTYPE_INSERT_PREV(name, type, attr);                     \
 427         RB_PROTOTYPE_MINMAX(name, type, attr);                          \
 428         RB_PROTOTYPE_REINSERT(name, type, attr);
 429 #ifdef _RB_DIAGNOSTIC
 430 #define RB_PROTOTYPE_RANK(name, type, attr)                             \
 431         attr int name##_RB_RANK(struct type *);
 432 #else
 433 #define RB_PROTOTYPE_RANK(name, type, attr)
 434 #endif
 435 #define RB_PROTOTYPE_DO_INSERT_COLOR(name, type, attr)                  \
 436         attr struct type *name##_RB_DO_INSERT_COLOR(struct name *,      \
 437             struct type *, struct type *)
 438 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                     \
 439         attr struct type *name##_RB_INSERT_COLOR(struct name *, struct type *)
 440 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                     \
 441         attr struct type *name##_RB_REMOVE_COLOR(struct name *,         \
 442             struct type *, struct type *)
 443 #define RB_PROTOTYPE_REMOVE(name, type, attr)                           \
 444         attr struct type *name##_RB_REMOVE(struct name *, struct type *)
 445 #define RB_PROTOTYPE_INSERT_FINISH(name, type, attr)                    \
 446         attr struct type *name##_RB_INSERT_FINISH(struct name *,        \
 447             struct type *, struct type **, struct type *)
 448 #define RB_PROTOTYPE_INSERT(name, type, attr)                           \
 449         attr struct type *name##_RB_INSERT(struct name *, struct type *)
 450 #define RB_PROTOTYPE_FIND(name, type, attr)                             \
 451         attr struct type *name##_RB_FIND(struct name *, struct type *)
 452 #define RB_PROTOTYPE_NFIND(name, type, attr)                            \
 453         attr struct type *name##_RB_NFIND(struct name *, struct type *)
 454 #define RB_PROTOTYPE_NEXT(name, type, attr)                             \
 455         attr struct type *name##_RB_NEXT(struct type *)
 456 #define RB_PROTOTYPE_INSERT_NEXT(name, type, attr)                      \
 457         attr struct type *name##_RB_INSERT_NEXT(struct name *,          \
 458             struct type *, struct type *)
 459 #define RB_PROTOTYPE_PREV(name, type, attr)                             \
 460         attr struct type *name##_RB_PREV(struct type *)
 461 #define RB_PROTOTYPE_INSERT_PREV(name, type, attr)                      \
 462         attr struct type *name##_RB_INSERT_PREV(struct name *,          \
 463             struct type *, struct type *)
 464 #define RB_PROTOTYPE_MINMAX(name, type, attr)                           \
 465         attr struct type *name##_RB_MINMAX(struct name *, int)
 466 #define RB_PROTOTYPE_REINSERT(name, type, attr)                 \
 467         attr struct type *name##_RB_REINSERT(struct name *, struct type *)
 468
 469 /* Main rb operation.
 470  * Moves node close to the key of elm to top
 471  */
 472 #define RB_GENERATE(name, type, field, cmp)                             \
 473         RB_GENERATE_INTERNAL(name, type, field, cmp,)
 474 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
 475         RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 476 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
 477         RB_GENERATE_RANK(name, type, field, attr)                       \
 478         RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr)            \
 479         RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
 480         RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
 481         RB_GENERATE_INSERT_FINISH(name, type, field, attr)              \
 482         RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
 483         RB_GENERATE_REMOVE(name, type, field, attr)                     \
 484         RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
 485         RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
 486         RB_GENERATE_NEXT(name, type, field, attr)                       \
 487         RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)           \
 488         RB_GENERATE_PREV(name, type, field, attr)                       \
 489         RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)           \
 490         RB_GENERATE_MINMAX(name, type, field, attr)                     \
 491         RB_GENERATE_REINSERT(name, type, field, cmp, attr)
 492
 493 #ifdef _RB_DIAGNOSTIC
 494 #ifndef RB_AUGMENT
 495 #define _RB_AUGMENT_VERIFY(x) RB_AUGMENT_CHECK(x)
 496 #else
 497 #define _RB_AUGMENT_VERIFY(x) 0
 498 #endif
 499 #define RB_GENERATE_RANK(name, type, field, attr)                       \
 500 /*                                                                      \
 501  * Return the rank of the subtree rooted at elm, or -1 if the subtree   \
 502  * is not rank-balanced, or has inconsistent augmentation data.
 503  */                                                                     \
 504 attr int                                                                \
 505 name##_RB_RANK(struct type *elm)                                        \
 506 {                                                                       \
 507         struct type *left, *right, *up;                                 \
 508         int left_rank, right_rank;                                      \
 509                                                                         \
 510         if (elm == NULL)                                                \
 511                 return (0);                                             \
 512         up = _RB_UP(elm, field);                                        \
 513         left = RB_LEFT(elm, field);                                     \
 514         left_rank = ((_RB_BITS(up) & _RB_L) ? 2 : 1) +                  \
 515             name##_RB_RANK(left);                                       \
 516         right = RB_RIGHT(elm, field);                                   \
 517         right_rank = ((_RB_BITS(up) & _RB_R) ? 2 : 1) +                 \
 518             name##_RB_RANK(right);                                      \
 519         if (left_rank != right_rank ||                                  \
 520             (left_rank == 2 && left == NULL && right == NULL) ||        \
 521             _RB_AUGMENT_VERIFY(elm))                                    \
 522                 return (-1);                                            \
 523         return (left_rank);                                             \
 524 }
 525 #else
 526 #define RB_GENERATE_RANK(name, type, field, attr)
 527 #endif
 528
 529 #define RB_GENERATE_DO_INSERT_COLOR(name, type, field, attr)            \
 530 attr struct type *                                                      \
 531 name##_RB_DO_INSERT_COLOR(struct name *head,                            \
 532     struct type *parent, struct type *elm)                              \
 533 {                                                                       \
 534         /*                                                              \
 535          * Initially, elm is a leaf.  Either its parent was previously  \
 536          * a leaf, with two black null children, or an interior node    \
 537          * with a black non-null child and a red null child. The        \
 538          * balance criterion "the rank of any leaf is 1" precludes the  \
 539          * possibility of two red null children for the initial parent. \
 540          * So the first loop iteration cannot lead to accessing an      \
 541          * uninitialized 'child', and a later iteration can only happen \
 542          * when a value has been assigned to 'child' in the previous    \
 543          * one.                                                         \
 544          */                                                             \
 545         struct type *child, *child_up, *gpar;                           \
 546         __uintptr_t elmdir, sibdir;                                     \
 547                                                                         \
 548         do {                                                            \
 549                 /* the rank of the tree rooted at elm grew */           \
 550                 gpar = _RB_UP(parent, field);                           \
 551                 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
 552                 if (_RB_BITS(gpar) & elmdir) {                          \
 553                         /* shorten the parent-elm edge to rebalance */  \
 554                         _RB_BITSUP(parent, field) ^= elmdir;            \
 555                         return (NULL);                                  \
 556                 }                                                       \
 557                 sibdir = elmdir ^ _RB_LR;                               \
 558                 /* the other edge must change length */                 \
 559                 _RB_BITSUP(parent, field) ^= sibdir;                    \
 560                 if ((_RB_BITS(gpar) & _RB_LR) == 0) {                   \
 561                         /* both edges now short, retry from parent */   \
 562                         child = elm;                                    \
 563                         elm = parent;                                   \
 564                         continue;                                       \
 565                 }                                                       \
 566                 _RB_UP(parent, field) = gpar = _RB_PTR(gpar);           \
 567                 if (_RB_BITSUP(elm, field) & elmdir) {                  \
 568                         /*                                              \
 569                          * Exactly one of the edges descending from elm \
 570                          * is long. The long one is in the same         \
 571                          * direction as the edge from parent to elm,    \
 572                          * so change that by rotation.  The edge from   \
 573                          * parent to z was shortened above.  Shorten    \
 574                          * the long edge down from elm, and adjust      \
 575                          * other edge lengths based on the downward     \
 576                          * edges from 'child'.                          \
 577                          *                                              \
 578                          *           par                 par            \
 579                          *          /   \               /   \           \
 580                          *        elm    z             /     z          \
 581                          *       /  \                child              \
 582                          *      /  child             /   \              \
 583                          *     /   /  \            elm    \             \
 584                          *    w   /    \          /   \    y            \
 585                          *       x      y        w     \                \
 586                          *                              x               \
 587                          */                                             \
 588                         RB_ROTATE(elm, child, elmdir, field);           \
 589                         child_up = _RB_UP(child, field);                \
 590                         if (_RB_BITS(child_up) & sibdir)                \
 591                                 _RB_BITSUP(parent, field) ^= elmdir;    \
 592                         if (_RB_BITS(child_up) & elmdir)                \
 593                                 _RB_BITSUP(elm, field) ^= _RB_LR;       \
 594                         else                                            \
 595                                 _RB_BITSUP(elm, field) ^= elmdir;       \
 596                         /* if child is a leaf, don't augment elm,       \
 597                          * since it is restored to be a leaf again. */  \
 598                         if ((_RB_BITS(child_up) & _RB_LR) == 0)         \
 599                                 elm = child;                            \
 600                 } else                                                  \
 601                         child = elm;                                    \
 602                                                                         \
 603                 /*                                                      \
 604                  * The long edge descending from 'child' points back    \
 605                  * in the direction of 'parent'. Rotate to make         \
 606                  * 'parent' a child of 'child', then make both edges    \
 607                  * of 'child' short to rebalance.                       \
 608                  *                                                      \
 609                  *           par                 child                  \
 610                  *          /   \               /     \                 \
 611                  *         /     z             x       par              \
 612                  *      child                         /   \             \
 613                  *       /  \                        /     z            \
 614                  *      x    \                      y                   \
 615                  *            y                                         \
 616                  */                                                     \
 617                 RB_ROTATE(parent, child, sibdir, field);                \
 618                 _RB_UP(child, field) = gpar;                            \
 619                 RB_SWAP_CHILD(head, gpar, parent, child, field);        \
 620                 /*                                                      \
 621                  * Elements rotated down have new, smaller subtrees,    \
 622                  * so update augmentation for them.                     \
 623                  */                                                     \
 624                 if (elm != child)                                       \
 625                         (void)RB_AUGMENT_CHECK(elm);                    \
 626                 (void)RB_AUGMENT_CHECK(parent);                         \
 627                 return (child);                                         \
 628         } while ((parent = gpar) != NULL);                              \
 629         return (NULL);                                                  \
 630 }
 631
 632 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
 633 attr struct type *                                                      \
 634 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
 635 {                                                                       \
 636         struct type *parent, *tmp;                                      \
 637                                                                         \
 638         parent = RB_PARENT(elm, field);                                 \
 639         if (parent != NULL)                                             \
 640                 tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm);     \
 641         else                                                            \
 642                 tmp = NULL;                                             \
 643         return (tmp);                                                   \
 644 }
 645
 646 #ifndef RB_STRICT_HST
 647 /*
 648  * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
 649  * 'parent' with one higher rank, and then reduces its rank if 'parent' has
 650  * become a leaf.  This implementation always has the parent in its new position
 651  * with lower rank, to avoid the leaf check.  Define RB_STRICT_HST to 1 to get
 652  * the behavior that HST describes.
 653  */
 654 #define RB_STRICT_HST 0
 655 #endif
 656
 657 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
 658 attr struct type *                                                      \
 659 name##_RB_REMOVE_COLOR(struct name *head,                               \
 660     struct type *parent, struct type *elm)                              \
 661 {                                                                       \
 662         struct type *gpar, *sib, *up;                                   \
 663         __uintptr_t elmdir, sibdir;                                     \
 664                                                                         \
 665         if (RB_RIGHT(parent, field) == elm &&                           \
 666             RB_LEFT(parent, field) == elm) {                            \
 667                 /* Deleting a leaf that is an only-child creates a      \
 668                  * rank-2 leaf. Demote that leaf. */                    \
 669                 _RB_UP(parent, field) = _RB_PTR(_RB_UP(parent, field)); \
 670                 elm = parent;                                           \
 671                 if ((parent = _RB_UP(elm, field)) == NULL)              \
 672                         return (NULL);                                  \
 673         }                                                               \
 674         do {                                                            \
 675                 /* the rank of the tree rooted at elm shrank */         \
 676                 gpar = _RB_UP(parent, field);                           \
 677                 elmdir = RB_RIGHT(parent, field) == elm ? _RB_R : _RB_L; \
 678                 _RB_BITS(gpar) ^= elmdir;                               \
 679                 if (_RB_BITS(gpar) & elmdir) {                          \
 680                         /* lengthen the parent-elm edge to rebalance */ \
 681                         _RB_UP(parent, field) = gpar;                   \
 682                         return (NULL);                                  \
 683                 }                                                       \
 684                 if (_RB_BITS(gpar) & _RB_LR) {                          \
 685                         /* shorten other edge, retry from parent */     \
 686                         _RB_BITS(gpar) ^= _RB_LR;                       \
 687                         _RB_UP(parent, field) = gpar;                   \
 688                         gpar = _RB_PTR(gpar);                           \
 689                         continue;                                       \
 690                 }                                                       \
 691                 sibdir = elmdir ^ _RB_LR;                               \
 692                 sib = _RB_LINK(parent, sibdir-1, field);                \
 693                 up = _RB_UP(sib, field);                                \
 694                 _RB_BITS(up) ^= _RB_LR;                                 \
 695                 if ((_RB_BITS(up) & _RB_LR) == 0) {                     \
 696                         /* shorten edges descending from sib, retry */  \
 697                         _RB_UP(sib, field) = up;                        \
 698                         continue;                                       \
 699                 }                                                       \
 700                 if ((_RB_BITS(up) & sibdir) == 0) {                     \
 701                         /*                                              \
 702                          * The edge descending from 'sib' away from     \
 703                          * 'parent' is long.  The short edge descending \
 704                          * from 'sib' toward 'parent' points to 'elm*'  \
 705                          * Rotate to make 'sib' a child of 'elm*'       \
 706                          * then adjust the lengths of the edges         \
 707                          * descending from 'sib' and 'elm*'.            \
 708                          *                                              \
 709                          *           par                 par            \
 710                          *          /   \               /   \           \
 711                          *         /    sib           elm    \          \
 712                          *        /     / \                 elm*        \
 713                          *      elm   elm* \                /  \        \
 714                          *            / \   \              /    \       \
 715                          *           /   \   z            /      \      \
 716                          *          x     y              x      sib     \
 717                          *                                      /  \    \
 718                          *                                     /    z   \
 719                          *                                    y         \
 720                          */                                             \
 721                         elm = _RB_LINK(sib, elmdir-1, field);           \
 722                         /* elm is a 1-child.  First rotate at elm. */   \
 723                         RB_ROTATE(sib, elm, sibdir, field);             \
 724                         up = _RB_UP(elm, field);                        \
 725                         _RB_BITSUP(parent, field) ^=                    \
 726                             (_RB_BITS(up) & elmdir) ? _RB_LR : elmdir;  \
 727                         _RB_BITSUP(sib, field) ^=                       \
 728                             (_RB_BITS(up) & sibdir) ? _RB_LR : sibdir;  \
 729                         _RB_BITSUP(elm, field) |= _RB_LR;               \
 730                 } else {                                                \
 731                         if ((_RB_BITS(up) & elmdir) == 0 &&             \
 732                             RB_STRICT_HST && elm != NULL) {             \
 733                                 /* if parent does not become a leaf,    \
 734                                    do not demote parent yet. */         \
 735                                 _RB_BITSUP(parent, field) ^= sibdir;    \
 736                                 _RB_BITSUP(sib, field) ^= _RB_LR;       \
 737                         } else if ((_RB_BITS(up) & elmdir) == 0) {      \
 738                                 /* demote parent. */                    \
 739                                 _RB_BITSUP(parent, field) ^= elmdir;    \
 740                                 _RB_BITSUP(sib, field) ^= sibdir;       \
 741                         } else                                          \
 742                                 _RB_BITSUP(sib, field) ^= sibdir;       \
 743                         elm = sib;                                      \
 744                 }                                                       \
 745                                                                         \
 746                 /*                                                      \
 747                  * The edge descending from 'elm' away from 'parent'    \
 748                  * is short.  Rotate to make 'parent' a child of 'elm', \
 749                  * then lengthen the short edges descending from        \
 750                  * 'parent' and 'elm' to rebalance.                     \
 751                  *                                                      \
 752                  *           par                 elm                    \
 753                  *          /   \               /   \                   \
 754                  *         e     \             /     \                  \
 755                  *               elm          /       \                 \
 756                  *              /  \        par        s                \
 757                  *             /    \      /   \                        \
 758                  *            /      \    e     \                       \
 759                  *           x        s          x                      \
 760                  */                                                     \
 761                 RB_ROTATE(parent, elm, elmdir, field);                  \
 762                 RB_SET_PARENT(elm, gpar, field);                        \
 763                 RB_SWAP_CHILD(head, gpar, parent, elm, field);          \
 764                 /*                                                      \
 765                  * An element rotated down, but not into the search     \
 766                  * path has a new, smaller subtree, so update           \
 767                  * augmentation for it.                                 \
 768                  */                                                     \
 769                 if (sib != elm)                                         \
 770                         (void)RB_AUGMENT_CHECK(sib);                    \
 771                 return (parent);                                        \
 772         } while (elm = parent, (parent = gpar) != NULL);                \
 773         return (NULL);                                                  \
 774 }
 775
 776 #define _RB_AUGMENT_WALK(elm, match, field)                             \
 777 do {                                                                    \
 778         if (match == elm)                                               \
 779                 match = NULL;                                           \
 780 } while (RB_AUGMENT_CHECK(elm) &&                                       \
 781     (elm = RB_PARENT(elm, field)) != NULL)
 782
 783 #define RB_GENERATE_REMOVE(name, type, field, attr)                     \
 784 attr struct type *                                                      \
 785 name##_RB_REMOVE(struct name *head, struct type *out)                   \
 786 {                                                                       \
 787         struct type *child, *in, *opar, *parent;                        \
 788                                                                         \
 789         child = RB_LEFT(out, field);                                    \
 790         in = RB_RIGHT(out, field);                                      \
 791         opar = _RB_UP(out, field);                                      \
 792         if (in == NULL || child == NULL) {                              \
 793                 in = child = in == NULL ? child : in;                   \
 794                 parent = opar = _RB_PTR(opar);                          \
 795         } else {                                                        \
 796                 parent = in;                                            \
 797                 while (RB_LEFT(in, field))                              \
 798                         in = RB_LEFT(in, field);                        \
 799                 RB_SET_PARENT(child, in, field);                        \
 800                 RB_LEFT(in, field) = child;                             \
 801                 child = RB_RIGHT(in, field);                            \
 802                 if (parent != in) {                                     \
 803                         RB_SET_PARENT(parent, in, field);               \
 804                         RB_RIGHT(in, field) = parent;                   \
 805                         parent = RB_PARENT(in, field);                  \
 806                         RB_LEFT(parent, field) = child;                 \
 807                 }                                                       \
 808                 _RB_UP(in, field) = opar;                               \
 809                 opar = _RB_PTR(opar);                                   \
 810         }                                                               \
 811         RB_SWAP_CHILD(head, opar, out, in, field);                      \
 812         if (child != NULL)                                              \
 813                 _RB_UP(child, field) = parent;                          \
 814         if (parent != NULL) {                                           \
 815                 opar = name##_RB_REMOVE_COLOR(head, parent, child);     \
 816                 /* if rotation has made 'parent' the root of the same   \
 817                  * subtree as before, don't re-augment it. */           \
 818                 if (parent == in && RB_LEFT(parent, field) == NULL) {   \
 819                         opar = NULL;                                    \
 820                         parent = RB_PARENT(parent, field);              \
 821                 }                                                       \
 822                 _RB_AUGMENT_WALK(parent, opar, field);                  \
 823                 if (opar != NULL) {                                     \
 824                         /*                                              \
 825                          * Elements rotated into the search path have   \
 826                          * changed subtrees, so update augmentation for \
 827                          * them if AUGMENT_WALK didn't.                 \
 828                          */                                             \
 829                         (void)RB_AUGMENT_CHECK(opar);                   \
 830                         (void)RB_AUGMENT_CHECK(RB_PARENT(opar, field)); \
 831                 }                                                       \
 832         }                                                               \
 833         return (out);                                                   \
 834 }
 835
 836 #define RB_GENERATE_INSERT_FINISH(name, type, field, attr)              \
 837 /* Inserts a node into the RB tree */                                   \
 838 attr struct type *                                                      \
 839 name##_RB_INSERT_FINISH(struct name *head, struct type *parent,         \
 840     struct type **pptr, struct type *elm)                               \
 841 {                                                                       \
 842         struct type *tmp = NULL;                                        \
 843                                                                         \
 844         RB_SET(elm, parent, field);                                     \
 845         *pptr = elm;                                                    \
 846         if (parent != NULL)                                             \
 847                 tmp = name##_RB_DO_INSERT_COLOR(head, parent, elm);     \
 848         _RB_AUGMENT_WALK(elm, tmp, field);                              \
 849         if (tmp != NULL)                                                \
 850                 /*                                                      \
 851                  * An element rotated into the search path has a        \
 852                  * changed subtree, so update augmentation for it if    \
 853                  * AUGMENT_WALK didn't.                                 \
 854                  */                                                     \
 855                 (void)RB_AUGMENT_CHECK(tmp);                            \
 856         return (NULL);                                                  \
 857 }
 858
 859 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
 860 /* Inserts a node into the RB tree */                                   \
 861 attr struct type *                                                      \
 862 name##_RB_INSERT(struct name *head, struct type *elm)                   \
 863 {                                                                       \
 864         struct type *tmp;                                               \
 865         struct type **tmpp = &RB_ROOT(head);                            \
 866         struct type *parent = NULL;                                     \
 867                                                                         \
 868         while ((tmp = *tmpp) != NULL) {                                 \
 869                 parent = tmp;                                           \
 870                 __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent);    \
 871                 if (comp < 0)                                           \
 872                         tmpp = &RB_LEFT(parent, field);                 \
 873                 else if (comp > 0)                                      \
 874                         tmpp = &RB_RIGHT(parent, field);                \
 875                 else                                                    \
 876                         return (parent);                                \
 877         }                                                               \
 878         return (name##_RB_INSERT_FINISH(head, parent, tmpp, elm));      \
 879 }
 880
 881 #define RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
 882 /* Finds the node with the same key as elm */                           \
 883 attr struct type *                                                      \
 884 name##_RB_FIND(struct name *head, struct type *elm)                     \
 885 {                                                                       \
 886         struct type *tmp = RB_ROOT(head);                               \
 887         __typeof(cmp(NULL, NULL)) comp;                                 \
 888         while (tmp) {                                                   \
 889                 comp = cmp(elm, tmp);                                   \
 890                 if (comp < 0)                                           \
 891                         tmp = RB_LEFT(tmp, field);                      \
 892                 else if (comp > 0)                                      \
 893                         tmp = RB_RIGHT(tmp, field);                     \
 894                 else                                                    \
 895                         return (tmp);                                   \
 896         }                                                               \
 897         return (NULL);                                                  \
 898 }
 899
 900 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
 901 /* Finds the first node greater than or equal to the search key */      \
 902 attr struct type *                                                      \
 903 name##_RB_NFIND(struct name *head, struct type *elm)                    \
 904 {                                                                       \
 905         struct type *tmp = RB_ROOT(head);                               \
 906         struct type *res = NULL;                                        \
 907         __typeof(cmp(NULL, NULL)) comp;                                 \
 908         while (tmp) {                                                   \
 909                 comp = cmp(elm, tmp);                                   \
 910                 if (comp < 0) {                                         \
 911                         res = tmp;                                      \
 912                         tmp = RB_LEFT(tmp, field);                      \
 913                 }                                                       \
 914                 else if (comp > 0)                                      \
 915                         tmp = RB_RIGHT(tmp, field);                     \
 916                 else                                                    \
 917                         return (tmp);                                   \
 918         }                                                               \
 919         return (res);                                                   \
 920 }
 921
 922 #define RB_GENERATE_NEXT(name, type, field, attr)                       \
 923 /* ARGSUSED */                                                          \
 924 attr struct type *                                                      \
 925 name##_RB_NEXT(struct type *elm)                                        \
 926 {                                                                       \
 927         if (RB_RIGHT(elm, field)) {                                     \
 928                 elm = RB_RIGHT(elm, field);                             \
 929                 while (RB_LEFT(elm, field))                             \
 930                         elm = RB_LEFT(elm, field);                      \
 931         } else {                                                        \
 932                 while (RB_PARENT(elm, field) &&                         \
 933                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
 934                         elm = RB_PARENT(elm, field);                    \
 935                 elm = RB_PARENT(elm, field);                            \
 936         }                                                               \
 937         return (elm);                                                   \
 938 }
 939
 940 #if defined(_KERNEL) && defined(DIAGNOSTIC)
 941 #define _RB_ORDER_CHECK(cmp, lo, hi) do {                               \
 942         KASSERT((cmp)(lo, hi) < 0, ("out of order insertion"));         \
 943 } while (0)
 944 #else
 945 #define _RB_ORDER_CHECK(cmp, lo, hi) do {} while (0)
 946 #endif
 947
 948 #define RB_GENERATE_INSERT_NEXT(name, type, field, cmp, attr)           \
 949 /* Inserts a node into the next position in the RB tree */              \
 950 attr struct type *                                                      \
 951 name##_RB_INSERT_NEXT(struct name *head,                                \
 952     struct type *elm, struct type *next)                                \
 953 {                                                                       \
 954         struct type *tmp;                                               \
 955         struct type **tmpp = &RB_RIGHT(elm, field);                     \
 956                                                                         \
 957         _RB_ORDER_CHECK(cmp, elm, next);                                \
 958         if (name##_RB_NEXT(elm) != NULL)                                \
 959                 _RB_ORDER_CHECK(cmp, next, name##_RB_NEXT(elm));        \
 960         while ((tmp = *tmpp) != NULL) {                                 \
 961                 elm = tmp;                                              \
 962                 tmpp = &RB_LEFT(elm, field);                            \
 963         }                                                               \
 964         return (name##_RB_INSERT_FINISH(head, elm, tmpp, next));        \
 965 }
 966
 967 #define RB_GENERATE_PREV(name, type, field, attr)                       \
 968 /* ARGSUSED */                                                          \
 969 attr struct type *                                                      \
 970 name##_RB_PREV(struct type *elm)                                        \
 971 {                                                                       \
 972         if (RB_LEFT(elm, field)) {                                      \
 973                 elm = RB_LEFT(elm, field);                              \
 974                 while (RB_RIGHT(elm, field))                            \
 975                         elm = RB_RIGHT(elm, field);                     \
 976         } else {                                                        \
 977                 while (RB_PARENT(elm, field) &&                         \
 978                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
 979                         elm = RB_PARENT(elm, field);                    \
 980                 elm = RB_PARENT(elm, field);                            \
 981         }                                                               \
 982         return (elm);                                                   \
 983 }
 984
 985 #define RB_GENERATE_INSERT_PREV(name, type, field, cmp, attr)           \
 986 /* Inserts a node into the prev position in the RB tree */              \
 987 attr struct type *                                                      \
 988 name##_RB_INSERT_PREV(struct name *head,                                \
 989     struct type *elm, struct type *prev)                                \
 990 {                                                                       \
 991         struct type *tmp;                                               \
 992         struct type **tmpp = &RB_LEFT(elm, field);                      \
 993                                                                         \
 994         _RB_ORDER_CHECK(cmp, prev, elm);                                \
 995         if (name##_RB_PREV(elm) != NULL)                                \
 996                 _RB_ORDER_CHECK(cmp, name##_RB_PREV(elm), prev);        \
 997         while ((tmp = *tmpp) != NULL) {                                 \
 998                 elm = tmp;                                              \
 999                 tmpp = &RB_RIGHT(elm, field);                           \
1000         }                                                               \
1001         return (name##_RB_INSERT_FINISH(head, elm, tmpp, prev));        \
1002 }
1003
1004 #define RB_GENERATE_MINMAX(name, type, field, attr)                     \
1005 attr struct type *                                                      \
1006 name##_RB_MINMAX(struct name *head, int val)                            \
1007 {                                                                       \
1008         struct type *tmp = RB_ROOT(head);                               \
1009         struct type *parent = NULL;                                     \
1010         while (tmp) {                                                   \
1011                 parent = tmp;                                           \
1012                 if (val < 0)                                            \
1013                         tmp = RB_LEFT(tmp, field);                      \
1014                 else                                                    \
1015                         tmp = RB_RIGHT(tmp, field);                     \
1016         }                                                               \
1017         return (parent);                                                \
1018 }
1019
1020 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr)              \
1021 attr struct type *                                                      \
1022 name##_RB_REINSERT(struct name *head, struct type *elm)                 \
1023 {                                                                       \
1024         struct type *cmpelm;                                            \
1025         if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&             \
1026             cmp(cmpelm, elm) >= 0) ||                                   \
1027             ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&             \
1028             cmp(elm, cmpelm) >= 0)) {                                   \
1029                 /* XXXLAS: Remove/insert is heavy handed. */            \
1030                 RB_REMOVE(name, head, elm);                             \
1031                 return (RB_INSERT(name, head, elm));                    \
1032         }                                                               \
1033         return (NULL);                                                  \
1034 }                                                                       \
1035
1036 #define RB_NEGINF       -1
1037 #define RB_INF  1
1038
1039 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
1040 #define RB_INSERT_NEXT(name, x, y, z)   name##_RB_INSERT_NEXT(x, y, z)
1041 #define RB_INSERT_PREV(name, x, y, z)   name##_RB_INSERT_PREV(x, y, z)
1042 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
1043 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
1044 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
1045 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
1046 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
1047 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
1048 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
1049 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)
1050
1051 #define RB_FOREACH(x, name, head)                                       \
1052         for ((x) = RB_MIN(name, head);                                  \
1053              (x) != NULL;                                               \
1054              (x) = name##_RB_NEXT(x))
1055
1056 #define RB_FOREACH_FROM(x, name, y)                                     \
1057         for ((x) = (y);                                                 \
1058             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
1059              (x) = (y))
1060
1061 #define RB_FOREACH_SAFE(x, name, head, y)                               \
1062         for ((x) = RB_MIN(name, head);                                  \
1063             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
1064              (x) = (y))
1065
1066 #define RB_FOREACH_REVERSE(x, name, head)                               \
1067         for ((x) = RB_MAX(name, head);                                  \
1068              (x) != NULL;                                               \
1069              (x) = name##_RB_PREV(x))
1070
1071 #define RB_FOREACH_REVERSE_FROM(x, name, y)                             \
1072         for ((x) = (y);                                                 \
1073             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
1074              (x) = (y))
1075
1076 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                       \
1077         for ((x) = RB_MAX(name, head);                                  \
1078             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
1079              (x) = (y))
1080
1081 #endif  /* _SYS_TREE_H_ */