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
  60  * trees, including "red-black" and "AVL" trees.  The set of conditions
  61  * applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan:
  62  *      - every rank-difference is 1 or 2.
  63  *      - the rank of any leaf is 1.
  64  *
  65  * For historical reasons, rank differences that are even are associated
  66  * with the color red (Rank-Even-Difference), and the child that a red edge
  67  * points to is called a red child.
  68  *
  69  * Every operation on a rank-balanced tree is bounded as O(lg n).
  70  * The maximum height of a rank-balanced tree is 2lg (n+1).
  71  */
  72
  73 #define SPLAY_HEAD(name, type)                                          \
  74 struct name {                                                           \
  75         struct type *sph_root; /* root of the tree */                   \
  76 }
  77
  78 #define SPLAY_INITIALIZER(root)                                         \
  79         { NULL }
  80
  81 #define SPLAY_INIT(root) do {                                           \
  82         (root)->sph_root = NULL;                                        \
  83 } while (/*CONSTCOND*/ 0)
  84
  85 #define SPLAY_ENTRY(type)                                               \
  86 struct {                                                                \
  87         struct type *spe_left; /* left element */                       \
  88         struct type *spe_right; /* right element */                     \
  89 }
  90
  91 #define SPLAY_LEFT(elm, field)          (elm)->field.spe_left
  92 #define SPLAY_RIGHT(elm, field)         (elm)->field.spe_right
  93 #define SPLAY_ROOT(head)                (head)->sph_root
  94 #define SPLAY_EMPTY(head)               (SPLAY_ROOT(head) == NULL)
  95
  96 /* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
  97 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                       \
  98         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
  99         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 100         (head)->sph_root = tmp;                                         \
 101 } while (/*CONSTCOND*/ 0)
 102
 103 #define SPLAY_ROTATE_LEFT(head, tmp, field) do {                        \
 104         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
 105         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 106         (head)->sph_root = tmp;                                         \
 107 } while (/*CONSTCOND*/ 0)
 108
 109 #define SPLAY_LINKLEFT(head, tmp, field) do {                           \
 110         SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
 111         tmp = (head)->sph_root;                                         \
 112         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
 113 } while (/*CONSTCOND*/ 0)
 114
 115 #define SPLAY_LINKRIGHT(head, tmp, field) do {                          \
 116         SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
 117         tmp = (head)->sph_root;                                         \
 118         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
 119 } while (/*CONSTCOND*/ 0)
 120
 121 #define SPLAY_ASSEMBLE(head, node, left, right, field) do {             \
 122         SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
 123         SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
 124         SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
 125         SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
 126 } while (/*CONSTCOND*/ 0)
 127
 128 /* Generates prototypes and inline functions */
 129
 130 #define SPLAY_PROTOTYPE(name, type, field, cmp)                         \
 131 void name##_SPLAY(struct name *, struct type *);                        \
 132 void name##_SPLAY_MINMAX(struct name *, int);                           \
 133 struct type *name##_SPLAY_INSERT(struct name *, struct type *);         \
 134 struct type *name##_SPLAY_REMOVE(struct name *, struct type *);         \
 135                                                                         \
 136 /* Finds the node with the same key as elm */                           \
 137 static __unused __inline struct type *                                  \
 138 name##_SPLAY_FIND(struct name *head, struct type *elm)                  \
 139 {                                                                       \
 140         if (SPLAY_EMPTY(head))                                          \
 141                 return(NULL);                                           \
 142         name##_SPLAY(head, elm);                                        \
 143         if ((cmp)(elm, (head)->sph_root) == 0)                          \
 144                 return (head->sph_root);                                \
 145         return (NULL);                                                  \
 146 }                                                                       \
 147                                                                         \
 148 static __unused __inline struct type *                                  \
 149 name##_SPLAY_NEXT(struct name *head, struct type *elm)                  \
 150 {                                                                       \
 151         name##_SPLAY(head, elm);                                        \
 152         if (SPLAY_RIGHT(elm, field) != NULL) {                          \
 153                 elm = SPLAY_RIGHT(elm, field);                          \
 154                 while (SPLAY_LEFT(elm, field) != NULL) {                \
 155                         elm = SPLAY_LEFT(elm, field);                   \
 156                 }                                                       \
 157         } else                                                          \
 158                 elm = NULL;                                             \
 159         return (elm);                                                   \
 160 }                                                                       \
 161                                                                         \
 162 static __unused __inline struct type *                                  \
 163 name##_SPLAY_MIN_MAX(struct name *head, int val)                        \
 164 {                                                                       \
 165         name##_SPLAY_MINMAX(head, val);                                 \
 166         return (SPLAY_ROOT(head));                                      \
 167 }
 168
 169 /* Main splay operation.
 170  * Moves node close to the key of elm to top
 171  */
 172 #define SPLAY_GENERATE(name, type, field, cmp)                          \
 173 struct type *                                                           \
 174 name##_SPLAY_INSERT(struct name *head, struct type *elm)                \
 175 {                                                                       \
 176     if (SPLAY_EMPTY(head)) {                                            \
 177             SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
 178     } else {                                                            \
 179             __typeof(cmp(NULL, NULL)) __comp;                           \
 180             name##_SPLAY(head, elm);                                    \
 181             __comp = (cmp)(elm, (head)->sph_root);                      \
 182             if (__comp < 0) {                                           \
 183                     SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
 184                     SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
 185                     SPLAY_LEFT((head)->sph_root, field) = NULL;         \
 186             } else if (__comp > 0) {                                    \
 187                     SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
 188                     SPLAY_LEFT(elm, field) = (head)->sph_root;          \
 189                     SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
 190             } else                                                      \
 191                     return ((head)->sph_root);                          \
 192     }                                                                   \
 193     (head)->sph_root = (elm);                                           \
 194     return (NULL);                                                      \
 195 }                                                                       \
 196                                                                         \
 197 struct type *                                                           \
 198 name##_SPLAY_REMOVE(struct name *head, struct type *elm)                \
 199 {                                                                       \
 200         struct type *__tmp;                                             \
 201         if (SPLAY_EMPTY(head))                                          \
 202                 return (NULL);                                          \
 203         name##_SPLAY(head, elm);                                        \
 204         if ((cmp)(elm, (head)->sph_root) == 0) {                        \
 205                 if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
 206                         (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
 207                 } else {                                                \
 208                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 209                         (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
 210                         name##_SPLAY(head, elm);                        \
 211                         SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
 212                 }                                                       \
 213                 return (elm);                                           \
 214         }                                                               \
 215         return (NULL);                                                  \
 216 }                                                                       \
 217                                                                         \
 218 void                                                                    \
 219 name##_SPLAY(struct name *head, struct type *elm)                       \
 220 {                                                                       \
 221         struct type __node, *__left, *__right, *__tmp;                  \
 222         __typeof(cmp(NULL, NULL)) __comp;                               \
 223 \
 224         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 225         __left = __right = &__node;                                     \
 226 \
 227         while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) {          \
 228                 if (__comp < 0) {                                       \
 229                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 230                         if (__tmp == NULL)                              \
 231                                 break;                                  \
 232                         if ((cmp)(elm, __tmp) < 0){                     \
 233                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 234                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 235                                         break;                          \
 236                         }                                               \
 237                         SPLAY_LINKLEFT(head, __right, field);           \
 238                 } else if (__comp > 0) {                                \
 239                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 240                         if (__tmp == NULL)                              \
 241                                 break;                                  \
 242                         if ((cmp)(elm, __tmp) > 0){                     \
 243                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 244                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 245                                         break;                          \
 246                         }                                               \
 247                         SPLAY_LINKRIGHT(head, __left, field);           \
 248                 }                                                       \
 249         }                                                               \
 250         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 251 }                                                                       \
 252                                                                         \
 253 /* Splay with either the minimum or the maximum element                 \
 254  * Used to find minimum or maximum element in tree.                     \
 255  */                                                                     \
 256 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
 257 {                                                                       \
 258         struct type __node, *__left, *__right, *__tmp;                  \
 259 \
 260         SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
 261         __left = __right = &__node;                                     \
 262 \
 263         while (1) {                                                     \
 264                 if (__comp < 0) {                                       \
 265                         __tmp = SPLAY_LEFT((head)->sph_root, field);    \
 266                         if (__tmp == NULL)                              \
 267                                 break;                                  \
 268                         if (__comp < 0){                                \
 269                                 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
 270                                 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
 271                                         break;                          \
 272                         }                                               \
 273                         SPLAY_LINKLEFT(head, __right, field);           \
 274                 } else if (__comp > 0) {                                \
 275                         __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
 276                         if (__tmp == NULL)                              \
 277                                 break;                                  \
 278                         if (__comp > 0) {                               \
 279                                 SPLAY_ROTATE_LEFT(head, __tmp, field);  \
 280                                 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
 281                                         break;                          \
 282                         }                                               \
 283                         SPLAY_LINKRIGHT(head, __left, field);           \
 284                 }                                                       \
 285         }                                                               \
 286         SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
 287 }
 288
 289 #define SPLAY_NEGINF    -1
 290 #define SPLAY_INF       1
 291
 292 #define SPLAY_INSERT(name, x, y)        name##_SPLAY_INSERT(x, y)
 293 #define SPLAY_REMOVE(name, x, y)        name##_SPLAY_REMOVE(x, y)
 294 #define SPLAY_FIND(name, x, y)          name##_SPLAY_FIND(x, y)
 295 #define SPLAY_NEXT(name, x, y)          name##_SPLAY_NEXT(x, y)
 296 #define SPLAY_MIN(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 297                                         : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
 298 #define SPLAY_MAX(name, x)              (SPLAY_EMPTY(x) ? NULL  \
 299                                         : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
 300
 301 #define SPLAY_FOREACH(x, name, head)                                    \
 302         for ((x) = SPLAY_MIN(name, head);                               \
 303              (x) != NULL;                                               \
 304              (x) = SPLAY_NEXT(name, head, x))
 305
 306 /* Macros that define a rank-balanced tree */
 307 #define RB_HEAD(name, type)                                             \
 308 struct name {                                                           \
 309         struct type *rbh_root; /* root of the tree */                   \
 310 }
 311
 312 #define RB_INITIALIZER(root)                                            \
 313         { NULL }
 314
 315 #define RB_INIT(root) do {                                              \
 316         (root)->rbh_root = NULL;                                        \
 317 } while (/*CONSTCOND*/ 0)
 318
 319 #define RB_ENTRY(type)                                                  \
 320 struct {                                                                \
 321         struct type *rbe_left;          /* left element */              \
 322         struct type *rbe_right;         /* right element */             \
 323         struct type *rbe_parent;        /* parent element */            \
 324 }
 325
 326 #define RB_LEFT(elm, field)             (elm)->field.rbe_left
 327 #define RB_RIGHT(elm, field)            (elm)->field.rbe_right
 328
 329 /*
 330  * With the expectation that any object of struct type has an
 331  * address that is a multiple of 4, and that therefore the
 332  * 2 least significant bits of a pointer to struct type are
 333  * always zero, this implementation sets those bits to indicate
 334  * that the left or right child of the tree node is "red".
 335  */
 336 #define RB_UP(elm, field)               (elm)->field.rbe_parent
 337 #define RB_BITS(elm, field)             (*(__uintptr_t *)&RB_UP(elm, field))
 338 #define RB_RED_L                        ((__uintptr_t)1)
 339 #define RB_RED_R                        ((__uintptr_t)2)
 340 #define RB_RED_MASK                     ((__uintptr_t)3)
 341 #define RB_FLIP_LEFT(elm, field)        (RB_BITS(elm, field) ^= RB_RED_L)
 342 #define RB_FLIP_RIGHT(elm, field)       (RB_BITS(elm, field) ^= RB_RED_R)
 343 #define RB_FLIP_ALL(elm, field)         (RB_BITS(elm, field) ^= RB_RED_MASK)
 344 #define RB_RED_LEFT(elm, field)         ((RB_BITS(elm, field) & RB_RED_L) != 0)
 345 #define RB_RED_RIGHT(elm, field)        ((RB_BITS(elm, field) & RB_RED_R) != 0)
 346 #define RB_PARENT(elm, field)           ((__typeof(RB_UP(elm, field)))  \
 347                                          (RB_BITS(elm, field) & ~RB_RED_MASK))
 348 #define RB_ROOT(head)                   (head)->rbh_root
 349 #define RB_EMPTY(head)                  (RB_ROOT(head) == NULL)
 350
 351 #define RB_SET_PARENT(dst, src, field) do {                             \
 352         RB_BITS(dst, field) = (__uintptr_t)src |                        \
 353             (RB_BITS(dst, field) & RB_RED_MASK);                        \
 354 } while (/*CONSTCOND*/ 0)
 355
 356 #define RB_SET(elm, parent, field) do {                                 \
 357         RB_UP(elm, field) = parent;                                     \
 358         RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
 359 } while (/*CONSTCOND*/ 0)
 360
 361 #define RB_COLOR(elm, field)    (RB_PARENT(elm, field) == NULL ? 0 :    \
 362                                 RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
 363                                 RB_RED_LEFT(RB_PARENT(elm, field), field) : \
 364                                 RB_RED_RIGHT(RB_PARENT(elm, field), field))
 365
 366 /*
 367  * Something to be invoked in a loop at the root of every modified subtree,
 368  * from the bottom up to the root, to update augmented node data.
 369  */
 370 #ifndef RB_AUGMENT
 371 #define RB_AUGMENT(x)   break
 372 #endif
 373
 374 #define RB_SWAP_CHILD(head, out, in, field) do {                        \
 375         if (RB_PARENT(out, field) == NULL)                              \
 376                 RB_ROOT(head) = (in);                                   \
 377         else if ((out) == RB_LEFT(RB_PARENT(out, field), field))        \
 378                 RB_LEFT(RB_PARENT(out, field), field) = (in);           \
 379         else                                                            \
 380                 RB_RIGHT(RB_PARENT(out, field), field) = (in);          \
 381 } while (/*CONSTCOND*/ 0)
 382
 383 #define RB_ROTATE_LEFT(head, elm, tmp, field) do {                      \
 384         if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) {     \
 385                 RB_SET_PARENT(RB_RIGHT(elm, field), elm, field);        \
 386         }                                                               \
 387         RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
 388         RB_SWAP_CHILD(head, elm, tmp, field);                           \
 389         RB_LEFT(tmp, field) = (elm);                                    \
 390         RB_SET_PARENT(elm, tmp, field);                                 \
 391         RB_AUGMENT(elm);                                                \
 392 } while (/*CONSTCOND*/ 0)
 393
 394 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                     \
 395         if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) {     \
 396                 RB_SET_PARENT(RB_LEFT(elm, field), elm, field);         \
 397         }                                                               \
 398         RB_SET_PARENT(tmp, RB_PARENT(elm, field), field);               \
 399         RB_SWAP_CHILD(head, elm, tmp, field);                           \
 400         RB_RIGHT(tmp, field) = (elm);                                   \
 401         RB_SET_PARENT(elm, tmp, field);                                 \
 402         RB_AUGMENT(elm);                                                \
 403 } while (/*CONSTCOND*/ 0)
 404
 405 /* Generates prototypes and inline functions */
 406 #define RB_PROTOTYPE(name, type, field, cmp)                            \
 407         RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
 408 #define RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
 409         RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 410 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)             \
 411         RB_PROTOTYPE_INSERT_COLOR(name, type, attr);                    \
 412         RB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                    \
 413         RB_PROTOTYPE_INSERT(name, type, attr);                          \
 414         RB_PROTOTYPE_REMOVE(name, type, attr);                          \
 415         RB_PROTOTYPE_FIND(name, type, attr);                            \
 416         RB_PROTOTYPE_NFIND(name, type, attr);                           \
 417         RB_PROTOTYPE_NEXT(name, type, attr);                            \
 418         RB_PROTOTYPE_PREV(name, type, attr);                            \
 419         RB_PROTOTYPE_MINMAX(name, type, attr);                          \
 420         RB_PROTOTYPE_REINSERT(name, type, attr);
 421 #define RB_PROTOTYPE_INSERT_COLOR(name, type, attr)                     \
 422         attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
 423 #define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                     \
 424         attr void name##_RB_REMOVE_COLOR(struct name *,                 \
 425             struct type *, struct type *)
 426 #define RB_PROTOTYPE_REMOVE(name, type, attr)                           \
 427         attr struct type *name##_RB_REMOVE(struct name *, struct type *)
 428 #define RB_PROTOTYPE_INSERT(name, type, attr)                           \
 429         attr struct type *name##_RB_INSERT(struct name *, struct type *)
 430 #define RB_PROTOTYPE_FIND(name, type, attr)                             \
 431         attr struct type *name##_RB_FIND(struct name *, struct type *)
 432 #define RB_PROTOTYPE_NFIND(name, type, attr)                            \
 433         attr struct type *name##_RB_NFIND(struct name *, struct type *)
 434 #define RB_PROTOTYPE_NEXT(name, type, attr)                             \
 435         attr struct type *name##_RB_NEXT(struct type *)
 436 #define RB_PROTOTYPE_PREV(name, type, attr)                             \
 437         attr struct type *name##_RB_PREV(struct type *)
 438 #define RB_PROTOTYPE_MINMAX(name, type, attr)                           \
 439         attr struct type *name##_RB_MINMAX(struct name *, int)
 440 #define RB_PROTOTYPE_REINSERT(name, type, attr)                 \
 441         attr struct type *name##_RB_REINSERT(struct name *, struct type *)
 442
 443 /* Main rb operation.
 444  * Moves node close to the key of elm to top
 445  */
 446 #define RB_GENERATE(name, type, field, cmp)                             \
 447         RB_GENERATE_INTERNAL(name, type, field, cmp,)
 448 #define RB_GENERATE_STATIC(name, type, field, cmp)                      \
 449         RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 450 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)              \
 451         RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
 452         RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
 453         RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
 454         RB_GENERATE_REMOVE(name, type, field, attr)                     \
 455         RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
 456         RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
 457         RB_GENERATE_NEXT(name, type, field, attr)                       \
 458         RB_GENERATE_PREV(name, type, field, attr)                       \
 459         RB_GENERATE_MINMAX(name, type, field, attr)                     \
 460         RB_GENERATE_REINSERT(name, type, field, cmp, attr)
 461
 462 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr)               \
 463 attr void                                                               \
 464 name##_RB_INSERT_COLOR(struct name *head, struct type *elm)             \
 465 {                                                                       \
 466         /*                                                              \
 467          * Initially, elm is a leaf.  Either its parent was previously  \
 468          * a leaf, with two black null children, or an interior node    \
 469          * with a black non-null child and a red null child. The        \
 470          * balance criterion "the rank of any leaf is 1" precludes the  \
 471          * possibility of two red null children for the initial parent. \
 472          * So the first loop iteration cannot lead to accessing an      \
 473          * uninitialized 'child', and a later iteration can only happen \
 474          * when a value has been assigned to 'child' in the previous    \
 475          * one.                                                         \
 476          */                                                             \
 477         struct type *child, *parent;                                    \
 478         while ((parent = RB_PARENT(elm, field)) != NULL) {              \
 479                 if (RB_LEFT(parent, field) == elm) {                    \
 480                         if (RB_RED_LEFT(parent, field)) {               \
 481                                 RB_FLIP_LEFT(parent, field);            \
 482                                 return;                                 \
 483                         }                                               \
 484                         RB_FLIP_RIGHT(parent, field);                   \
 485                         if (RB_RED_RIGHT(parent, field)) {              \
 486                                 child = elm;                            \
 487                                 elm = parent;                           \
 488                                 continue;                               \
 489                         }                                               \
 490                         if (!RB_RED_RIGHT(elm, field)) {                \
 491                                 /* coverity[uninit_use] */              \
 492                                 RB_ROTATE_LEFT(head, elm, child, field);\
 493                                 if (RB_RED_RIGHT(child, field))         \
 494                                         RB_FLIP_LEFT(parent, field);    \
 495                                 if (RB_RED_LEFT(child, field))          \
 496                                         RB_FLIP_ALL(elm, field);        \
 497                                 else                                    \
 498                                         RB_FLIP_LEFT(elm, field);       \
 499                                 elm = child;                            \
 500                         }                                               \
 501                         RB_ROTATE_RIGHT(head, parent, elm, field);      \
 502                 } else {                                                \
 503                         if (RB_RED_RIGHT(parent, field)) {              \
 504                                 RB_FLIP_RIGHT(parent, field);           \
 505                                 return;                                 \
 506                         }                                               \
 507                         RB_FLIP_LEFT(parent, field);                    \
 508                         if (RB_RED_LEFT(parent, field)) {               \
 509                                 child = elm;                            \
 510                                 elm = parent;                           \
 511                                 continue;                               \
 512                         }                                               \
 513                         if (!RB_RED_LEFT(elm, field)) {                 \
 514                                 /* coverity[uninit_use] */              \
 515                                 RB_ROTATE_RIGHT(head, elm, child, field);\
 516                                 if (RB_RED_LEFT(child, field))          \
 517                                         RB_FLIP_RIGHT(parent, field);   \
 518                                 if (RB_RED_RIGHT(child, field))         \
 519                                         RB_FLIP_ALL(elm, field);        \
 520                                 else                                    \
 521                                         RB_FLIP_RIGHT(elm, field);      \
 522                                 elm = child;                            \
 523                         }                                               \
 524                         RB_ROTATE_LEFT(head, parent, elm, field);       \
 525                 }                                                       \
 526                 RB_BITS(elm, field) &= ~RB_RED_MASK;                    \
 527                 break;                                                  \
 528         }                                                               \
 529 }
 530
 531 #ifndef RB_STRICT_HST
 532 /*
 533  * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
 534  * 'parent' with one higher rank, and then reduces its rank if 'parent' has
 535  * become a leaf.  This implementation always has the parent in its new position
 536  * with lower rank, to avoid the leaf check.  Define RB_STRICT_HST to 1 to get
 537  * the behavior that HST describes.
 538  */
 539 #define RB_STRICT_HST 0
 540 #endif
 541
 542 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr)               \
 543 attr void                                                               \
 544 name##_RB_REMOVE_COLOR(struct name *head,                               \
 545     struct type *parent, struct type *elm)                              \
 546 {                                                                       \
 547         struct type *sib;                                               \
 548         if (RB_LEFT(parent, field) == elm &&                            \
 549             RB_RIGHT(parent, field) == elm) {                           \
 550                 RB_BITS(parent, field) &= ~RB_RED_MASK;                 \
 551                 elm = parent;                                           \
 552                 parent = RB_PARENT(elm, field);                         \
 553                 if (parent == NULL)                                     \
 554                         return;                                         \
 555         }                                                               \
 556         do {                                                            \
 557                 if (RB_LEFT(parent, field) == elm) {                    \
 558                         if (!RB_RED_LEFT(parent, field)) {              \
 559                                 RB_FLIP_LEFT(parent, field);            \
 560                                 return;                                 \
 561                         }                                               \
 562                         if (RB_RED_RIGHT(parent, field)) {              \
 563                                 RB_FLIP_RIGHT(parent, field);           \
 564                                 elm = parent;                           \
 565                                 continue;                               \
 566                         }                                               \
 567                         sib = RB_RIGHT(parent, field);                  \
 568                         switch (RB_BITS(sib, field) & RB_RED_MASK) {    \
 569                         case RB_RED_MASK:                               \
 570                                 RB_FLIP_ALL(sib, field);                \
 571                                 elm = parent;                           \
 572                                 continue;                               \
 573                         case RB_RED_R:                                  \
 574                                 elm = RB_LEFT(sib, field);              \
 575                                 RB_ROTATE_RIGHT(head, sib, elm, field); \
 576                                 if (RB_RED_LEFT(elm, field))            \
 577                                         RB_FLIP_ALL(parent, field);     \
 578                                 else                                    \
 579                                         RB_FLIP_LEFT(parent, field);    \
 580                                 if (RB_RED_RIGHT(elm, field))           \
 581                                         RB_FLIP_ALL(sib, field);        \
 582                                 else                                    \
 583                                         RB_FLIP_RIGHT(sib, field);      \
 584                                 RB_BITS(elm, field) |= RB_RED_MASK;     \
 585                                 sib = elm;                              \
 586                                 break;                                  \
 587                         case RB_RED_L:                                  \
 588                                 if (RB_STRICT_HST && elm != NULL) {     \
 589                                         RB_FLIP_RIGHT(parent, field);   \
 590                                         RB_FLIP_ALL(sib, field);        \
 591                                         break;                          \
 592                                 }                                       \
 593                                 RB_FLIP_LEFT(parent, field);            \
 594                                 /* FALLTHROUGH */                       \
 595                         default:                                        \
 596                                 RB_FLIP_RIGHT(sib, field);              \
 597                                 break;                                  \
 598                         }                                               \
 599                         RB_ROTATE_LEFT(head, parent, sib, field);       \
 600                 } else {                                                \
 601                         if (!RB_RED_RIGHT(parent, field)) {             \
 602                                 RB_FLIP_RIGHT(parent, field);           \
 603                                 return;                                 \
 604                         }                                               \
 605                         if (RB_RED_LEFT(parent, field)) {               \
 606                                 RB_FLIP_LEFT(parent, field);            \
 607                                 elm = parent;                           \
 608                                 continue;                               \
 609                         }                                               \
 610                         sib = RB_LEFT(parent, field);                   \
 611                         switch (RB_BITS(sib, field) & RB_RED_MASK) {    \
 612                         case RB_RED_MASK:                               \
 613                                 RB_FLIP_ALL(sib, field);                \
 614                                 elm = parent;                           \
 615                                 continue;                               \
 616                         case RB_RED_L:                                  \
 617                                 elm = RB_RIGHT(sib, field);             \
 618                                 RB_ROTATE_LEFT(head, sib, elm, field);  \
 619                                 if (RB_RED_RIGHT(elm, field))           \
 620                                         RB_FLIP_ALL(parent, field);     \
 621                                 else                                    \
 622                                         RB_FLIP_RIGHT(parent, field);   \
 623                                 if (RB_RED_LEFT(elm, field))            \
 624                                         RB_FLIP_ALL(sib, field);        \
 625                                 else                                    \
 626                                         RB_FLIP_LEFT(sib, field);       \
 627                                 RB_BITS(elm, field) |= RB_RED_MASK;     \
 628                                 sib = elm;                              \
 629                                 break;                                  \
 630                         case RB_RED_R:                                  \
 631                                 if (RB_STRICT_HST && elm != NULL) {     \
 632                                         RB_FLIP_LEFT(parent, field);    \
 633                                         RB_FLIP_ALL(sib, field);        \
 634                                         break;                          \
 635                                 }                                       \
 636                                 RB_FLIP_RIGHT(parent, field);           \
 637                                 /* FALLTHROUGH */                       \
 638                         default:                                        \
 639                                 RB_FLIP_LEFT(sib, field);               \
 640                                 break;                                  \
 641                         }                                               \
 642                         RB_ROTATE_RIGHT(head, parent, sib, field);      \
 643                 }                                                       \
 644                 break;                                                  \
 645         } while ((parent = RB_PARENT(elm, field)) != NULL);             \
 646 }
 647
 648 #define RB_GENERATE_REMOVE(name, type, field, attr)                     \
 649 attr struct type *                                                      \
 650 name##_RB_REMOVE(struct name *head, struct type *elm)                   \
 651 {                                                                       \
 652         struct type *child, *old, *parent, *right;                      \
 653                                                                         \
 654         old = elm;                                                      \
 655         parent = RB_PARENT(elm, field);                                 \
 656         right = RB_RIGHT(elm, field);                                   \
 657         if (RB_LEFT(elm, field) == NULL)                                \
 658                 elm = child = right;                                    \
 659         else if (right == NULL)                                         \
 660                 elm = child = RB_LEFT(elm, field);                      \
 661         else {                                                          \
 662                 if ((child = RB_LEFT(right, field)) == NULL) {          \
 663                         child = RB_RIGHT(right, field);                 \
 664                         RB_RIGHT(old, field) = child;                   \
 665                         parent = elm = right;                           \
 666                 } else {                                                \
 667                         do                                              \
 668                                 elm = child;                            \
 669                         while ((child = RB_LEFT(elm, field)) != NULL);  \
 670                         child = RB_RIGHT(elm, field);                   \
 671                         parent = RB_PARENT(elm, field);                 \
 672                         RB_LEFT(parent, field) = child;                 \
 673                         RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\
 674                 }                                                       \
 675                 RB_SET_PARENT(RB_LEFT(old, field), elm, field);         \
 676                 elm->field = old->field;                                \
 677         }                                                               \
 678         RB_SWAP_CHILD(head, old, elm, field);                           \
 679         if (child != NULL)                                              \
 680                 RB_SET_PARENT(child, parent, field);                    \
 681         if (parent != NULL)                                             \
 682                 name##_RB_REMOVE_COLOR(head, parent, child);            \
 683         while (parent != NULL) {                                        \
 684                 RB_AUGMENT(parent);                                     \
 685                 parent = RB_PARENT(parent, field);                      \
 686         }                                                               \
 687         return (old);                                                   \
 688 }
 689
 690 #define RB_GENERATE_INSERT(name, type, field, cmp, attr)                \
 691 /* Inserts a node into the RB tree */                                   \
 692 attr struct type *                                                      \
 693 name##_RB_INSERT(struct name *head, struct type *elm)                   \
 694 {                                                                       \
 695         struct type *tmp;                                               \
 696         struct type *parent = NULL;                                     \
 697         __typeof(cmp(NULL, NULL)) comp = 0;                             \
 698         tmp = RB_ROOT(head);                                            \
 699         while (tmp) {                                                   \
 700                 parent = tmp;                                           \
 701                 comp = (cmp)(elm, parent);                              \
 702                 if (comp < 0)                                           \
 703                         tmp = RB_LEFT(tmp, field);                      \
 704                 else if (comp > 0)                                      \
 705                         tmp = RB_RIGHT(tmp, field);                     \
 706                 else                                                    \
 707                         return (tmp);                                   \
 708         }                                                               \
 709         RB_SET(elm, parent, field);                                     \
 710         if (parent == NULL)                                             \
 711                 RB_ROOT(head) = elm;                                    \
 712         else if (comp < 0)                                              \
 713                 RB_LEFT(parent, field) = elm;                           \
 714         else                                                            \
 715                 RB_RIGHT(parent, field) = elm;                          \
 716         name##_RB_INSERT_COLOR(head, elm);                              \
 717         while (elm != NULL) {                                           \
 718                 RB_AUGMENT(elm);                                        \
 719                 elm = RB_PARENT(elm, field);                            \
 720         }                                                               \
 721         return (NULL);                                                  \
 722 }
 723
 724 #define RB_GENERATE_FIND(name, type, field, cmp, attr)                  \
 725 /* Finds the node with the same key as elm */                           \
 726 attr struct type *                                                      \
 727 name##_RB_FIND(struct name *head, struct type *elm)                     \
 728 {                                                                       \
 729         struct type *tmp = RB_ROOT(head);                               \
 730         __typeof(cmp(NULL, NULL)) comp;                                 \
 731         while (tmp) {                                                   \
 732                 comp = cmp(elm, tmp);                                   \
 733                 if (comp < 0)                                           \
 734                         tmp = RB_LEFT(tmp, field);                      \
 735                 else if (comp > 0)                                      \
 736                         tmp = RB_RIGHT(tmp, field);                     \
 737                 else                                                    \
 738                         return (tmp);                                   \
 739         }                                                               \
 740         return (NULL);                                                  \
 741 }
 742
 743 #define RB_GENERATE_NFIND(name, type, field, cmp, attr)                 \
 744 /* Finds the first node greater than or equal to the search key */      \
 745 attr struct type *                                                      \
 746 name##_RB_NFIND(struct name *head, struct type *elm)                    \
 747 {                                                                       \
 748         struct type *tmp = RB_ROOT(head);                               \
 749         struct type *res = NULL;                                        \
 750         __typeof(cmp(NULL, NULL)) comp;                                 \
 751         while (tmp) {                                                   \
 752                 comp = cmp(elm, tmp);                                   \
 753                 if (comp < 0) {                                         \
 754                         res = tmp;                                      \
 755                         tmp = RB_LEFT(tmp, field);                      \
 756                 }                                                       \
 757                 else if (comp > 0)                                      \
 758                         tmp = RB_RIGHT(tmp, field);                     \
 759                 else                                                    \
 760                         return (tmp);                                   \
 761         }                                                               \
 762         return (res);                                                   \
 763 }
 764
 765 #define RB_GENERATE_NEXT(name, type, field, attr)                       \
 766 /* ARGSUSED */                                                          \
 767 attr struct type *                                                      \
 768 name##_RB_NEXT(struct type *elm)                                        \
 769 {                                                                       \
 770         if (RB_RIGHT(elm, field)) {                                     \
 771                 elm = RB_RIGHT(elm, field);                             \
 772                 while (RB_LEFT(elm, field))                             \
 773                         elm = RB_LEFT(elm, field);                      \
 774         } else {                                                        \
 775                 while (RB_PARENT(elm, field) &&                         \
 776                     (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
 777                         elm = RB_PARENT(elm, field);                    \
 778                 elm = RB_PARENT(elm, field);                            \
 779         }                                                               \
 780         return (elm);                                                   \
 781 }
 782
 783 #define RB_GENERATE_PREV(name, type, field, attr)                       \
 784 /* ARGSUSED */                                                          \
 785 attr struct type *                                                      \
 786 name##_RB_PREV(struct type *elm)                                        \
 787 {                                                                       \
 788         if (RB_LEFT(elm, field)) {                                      \
 789                 elm = RB_LEFT(elm, field);                              \
 790                 while (RB_RIGHT(elm, field))                            \
 791                         elm = RB_RIGHT(elm, field);                     \
 792         } else {                                                        \
 793                 while (RB_PARENT(elm, field) &&                         \
 794                     (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
 795                         elm = RB_PARENT(elm, field);                    \
 796                 elm = RB_PARENT(elm, field);                            \
 797         }                                                               \
 798         return (elm);                                                   \
 799 }
 800
 801 #define RB_GENERATE_MINMAX(name, type, field, attr)                     \
 802 attr struct type *                                                      \
 803 name##_RB_MINMAX(struct name *head, int val)                            \
 804 {                                                                       \
 805         struct type *tmp = RB_ROOT(head);                               \
 806         struct type *parent = NULL;                                     \
 807         while (tmp) {                                                   \
 808                 parent = tmp;                                           \
 809                 if (val < 0)                                            \
 810                         tmp = RB_LEFT(tmp, field);                      \
 811                 else                                                    \
 812                         tmp = RB_RIGHT(tmp, field);                     \
 813         }                                                               \
 814         return (parent);                                                \
 815 }
 816
 817 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr)              \
 818 attr struct type *                                                      \
 819 name##_RB_REINSERT(struct name *head, struct type *elm)                 \
 820 {                                                                       \
 821         struct type *cmpelm;                                            \
 822         if (((cmpelm = RB_PREV(name, head, elm)) != NULL &&             \
 823             cmp(cmpelm, elm) >= 0) ||                                   \
 824             ((cmpelm = RB_NEXT(name, head, elm)) != NULL &&             \
 825             cmp(elm, cmpelm) >= 0)) {                                   \
 826                 /* XXXLAS: Remove/insert is heavy handed. */            \
 827                 RB_REMOVE(name, head, elm);                             \
 828                 return (RB_INSERT(name, head, elm));                    \
 829         }                                                               \
 830         return (NULL);                                                  \
 831 }                                                                       \
 832
 833 #define RB_NEGINF       -1
 834 #define RB_INF  1
 835
 836 #define RB_INSERT(name, x, y)   name##_RB_INSERT(x, y)
 837 #define RB_REMOVE(name, x, y)   name##_RB_REMOVE(x, y)
 838 #define RB_FIND(name, x, y)     name##_RB_FIND(x, y)
 839 #define RB_NFIND(name, x, y)    name##_RB_NFIND(x, y)
 840 #define RB_NEXT(name, x, y)     name##_RB_NEXT(y)
 841 #define RB_PREV(name, x, y)     name##_RB_PREV(y)
 842 #define RB_MIN(name, x)         name##_RB_MINMAX(x, RB_NEGINF)
 843 #define RB_MAX(name, x)         name##_RB_MINMAX(x, RB_INF)
 844 #define RB_REINSERT(name, x, y) name##_RB_REINSERT(x, y)
 845
 846 #define RB_FOREACH(x, name, head)                                       \
 847         for ((x) = RB_MIN(name, head);                                  \
 848              (x) != NULL;                                               \
 849              (x) = name##_RB_NEXT(x))
 850
 851 #define RB_FOREACH_FROM(x, name, y)                                     \
 852         for ((x) = (y);                                                 \
 853             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
 854              (x) = (y))
 855
 856 #define RB_FOREACH_SAFE(x, name, head, y)                               \
 857         for ((x) = RB_MIN(name, head);                                  \
 858             ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL);    \
 859              (x) = (y))
 860
 861 #define RB_FOREACH_REVERSE(x, name, head)                               \
 862         for ((x) = RB_MAX(name, head);                                  \
 863              (x) != NULL;                                               \
 864              (x) = name##_RB_PREV(x))
 865
 866 #define RB_FOREACH_REVERSE_FROM(x, name, y)                             \
 867         for ((x) = (y);                                                 \
 868             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
 869              (x) = (y))
 870
 871 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                       \
 872         for ((x) = RB_MAX(name, head);                                  \
 873             ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL);    \
 874              (x) = (y))
 875
 876 #endif  /* _SYS_TREE_H_ */