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