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