sys/sys/arb.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_ARB_H_
  33 #define _SYS_ARB_H_
  34
  35 #include <sys/cdefs.h>
  36
  37 /* Array-based red-black trees. */
  38
  39 #define ARB_NULLIDX     -1
  40 #define ARB_NULLCOL     -1
  41
  42 #define ARB_BLACK       0
  43 #define ARB_RED         1
  44
  45 #define ARB_NEGINF      -1
  46 #define ARB_INF         1
  47
  48 #define ARB_HEAD(name, type, idxbits)                                   \
  49 struct name {                                                           \
  50         int##idxbits##_t        arb_curnodes;                           \
  51         int##idxbits##_t        arb_maxnodes;                           \
  52         int##idxbits##_t        arb_root_idx;                           \
  53         int##idxbits##_t        arb_free_idx;                           \
  54         int##idxbits##_t        arb_min_idx;                            \
  55         int##idxbits##_t        arb_max_idx;                            \
  56         struct type             arb_nodes[];                            \
  57 }
  58 #define ARB8_HEAD(name, type)   ARB_HEAD(name, type, 8)
  59 #define ARB16_HEAD(name, type)  ARB_HEAD(name, type, 16)
  60 #define ARB32_HEAD(name, type)  ARB_HEAD(name, type, 32)
  61
  62 #define ARB_ALLOCSIZE(head, maxn, x)                                    \
  63         (sizeof(*head) + (maxn) * sizeof(*x))
  64
  65 #define ARB_INITIALIZER(name, maxn)                                     \
  66         ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX,              \
  67             ARB_NULLIDX, ARB_NULLIDX })
  68
  69 #define ARB_INIT(x, field, head, maxn)                                  \
  70         (head)->arb_curnodes = 0;                                       \
  71         (head)->arb_maxnodes = (maxn);                                  \
  72         (head)->arb_root_idx = (head)->arb_free_idx =                   \
  73             (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX;    \
  74         /* The ARB_RETURNFREE() puts all entries on the free list. */   \
  75         ARB_ARRFOREACH_REVWCOND(x, field, head,                         \
  76             ARB_RETURNFREE(head, x, field))
  77
  78 #define ARB_ENTRY(idxbits)                                              \
  79 struct {                                                                \
  80         int##idxbits##_t        arbe_parent_idx;                        \
  81         int##idxbits##_t        arbe_left_idx;                          \
  82         int##idxbits##_t        arbe_right_idx;                         \
  83         int8_t                  arbe_color;                             \
  84 }
  85 #define ARB8_ENTRY()            ARB_ENTRY(8)
  86 #define ARB16_ENTRY()           ARB_ENTRY(16)
  87 #define ARB32_ENTRY()           ARB_ENTRY(32)
  88
  89 #define ARB_ENTRYINIT(elm, field) do {                                  \
  90         (elm)->field.arbe_parent_idx =                                  \
  91             (elm)->field.arbe_left_idx =                                \
  92             (elm)->field.arbe_right_idx = ARB_NULLIDX;                  \
  93             (elm)->field.arbe_color = ARB_NULLCOL;                      \
  94 } while (/*CONSTCOND*/ 0)
  95
  96 #define ARB_ELMTYPE(head)               __typeof(&(head)->arb_nodes[0])
  97 #define ARB_NODES(head)                 (head)->arb_nodes
  98 #define ARB_MAXNODES(head)              (head)->arb_maxnodes
  99 #define ARB_CURNODES(head)              (head)->arb_curnodes
 100 #define ARB_EMPTY(head)                 ((head)->arb_curnodes == 0)
 101 #define ARB_FULL(head)                  ((head)->arb_curnodes >= (head)->arb_maxnodes)
 102 #define ARB_CNODE(head, idx) \
 103     ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \
 104     NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx))))
 105 #define ARB_NODE(head, idx) \
 106     (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx)))
 107 #define ARB_ROOT(head)                  ARB_NODE(head, ARB_ROOTIDX(head))
 108 #define ARB_LEFT(head, elm, field)      ARB_NODE(head, ARB_LEFTIDX(elm, field))
 109 #define ARB_RIGHT(head, elm, field)     ARB_NODE(head, ARB_RIGHTIDX(elm, field))
 110 #define ARB_PARENT(head, elm, field)    ARB_NODE(head, ARB_PARENTIDX(elm, field))
 111 #define ARB_FREEIDX(head)               (head)->arb_free_idx
 112 #define ARB_ROOTIDX(head)               (head)->arb_root_idx
 113 #define ARB_MINIDX(head)                (head)->arb_min_idx
 114 #define ARB_MAXIDX(head)                (head)->arb_max_idx
 115 #define ARB_SELFIDX(head, elm)                                          \
 116     ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) -                    \
 117     ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) :            \
 118     (intptr_t)ARB_NULLIDX)
 119 #define ARB_LEFTIDX(elm, field)         (elm)->field.arbe_left_idx
 120 #define ARB_RIGHTIDX(elm, field)        (elm)->field.arbe_right_idx
 121 #define ARB_PARENTIDX(elm, field)       (elm)->field.arbe_parent_idx
 122 #define ARB_COLOR(elm, field)           (elm)->field.arbe_color
 123 #define ARB_PREVFREE(head, elm, field) \
 124     ARB_NODE(head, ARB_PREVFREEIDX(elm, field))
 125 #define ARB_PREVFREEIDX(elm, field)     ARB_LEFTIDX(elm, field)
 126 #define ARB_NEXTFREE(head, elm, field) \
 127     ARB_NODE(head, ARB_NEXTFREEIDX(elm, field))
 128 #define ARB_NEXTFREEIDX(elm, field)     ARB_RIGHTIDX(elm, field)
 129 #define ARB_ISFREE(elm, field)          (ARB_COLOR(elm, field) == ARB_NULLCOL)
 130
 131 #define ARB_SET(head, elm, parent, field) do {                          \
 132         ARB_PARENTIDX(elm, field) =                                     \
 133             parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX;           \
 134         ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \
 135         ARB_COLOR(elm, field) = ARB_RED;                                        \
 136 } while (/*CONSTCOND*/ 0)
 137
 138 #define ARB_SET_BLACKRED(black, red, field) do {                        \
 139         ARB_COLOR(black, field) = ARB_BLACK;                            \
 140         ARB_COLOR(red, field) = ARB_RED;                                        \
 141 } while (/*CONSTCOND*/ 0)
 142
 143 #ifndef ARB_AUGMENT
 144 #define ARB_AUGMENT(x)  do {} while (0)
 145 #endif
 146
 147 #define ARB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
 148         __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx;                     \
 149         (tmp) = ARB_RIGHT(head, elm, field);                            \
 150         _tmpidx = ARB_RIGHTIDX(elm, field);                             \
 151         ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field);             \
 152         if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) {                  \
 153                 ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) =      \
 154                     ARB_SELFIDX(head, elm);                             \
 155         }                                                               \
 156         ARB_AUGMENT(elm);                                               \
 157         ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field);          \
 158         if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) {                 \
 159                 if (ARB_SELFIDX(head, elm) ==                           \
 160                     ARB_LEFTIDX(ARB_PARENT(head, elm, field), field))   \
 161                         ARB_LEFTIDX(ARB_PARENT(head, elm, field),       \
 162                             field) = _tmpidx;                           \
 163                 else                                                    \
 164                         ARB_RIGHTIDX(ARB_PARENT(head, elm, field),      \
 165                             field) = _tmpidx;                           \
 166         } else                                                          \
 167                 ARB_ROOTIDX(head) = _tmpidx;                            \
 168         ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm);               \
 169         ARB_PARENTIDX(elm, field) = _tmpidx;                            \
 170         ARB_AUGMENT(tmp);                                               \
 171         if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX)                   \
 172                 ARB_AUGMENT(ARB_PARENT(head, tmp, field));              \
 173 } while (/*CONSTCOND*/ 0)
 174
 175 #define ARB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
 176         __typeof(ARB_LEFTIDX(elm, field)) _tmpidx;                      \
 177         (tmp) = ARB_LEFT(head, elm, field);                             \
 178         _tmpidx = ARB_LEFTIDX(elm, field);                              \
 179         ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field);             \
 180         if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) {                   \
 181                 ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) =     \
 182                     ARB_SELFIDX(head, elm);                             \
 183         }                                                               \
 184         ARB_AUGMENT(elm);                                               \
 185         ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field);          \
 186         if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) {                 \
 187                 if (ARB_SELFIDX(head, elm) ==                           \
 188                     ARB_LEFTIDX(ARB_PARENT(head, elm, field), field))   \
 189                         ARB_LEFTIDX(ARB_PARENT(head, elm, field),       \
 190                             field) = _tmpidx;                           \
 191                 else                                                    \
 192                         ARB_RIGHTIDX(ARB_PARENT(head, elm, field),      \
 193                             field) = _tmpidx;                           \
 194         } else                                                          \
 195                 ARB_ROOTIDX(head) = _tmpidx;                            \
 196         ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm);              \
 197         ARB_PARENTIDX(elm, field) = _tmpidx;                            \
 198         ARB_AUGMENT(tmp);                                               \
 199         if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX)                   \
 200                 ARB_AUGMENT(ARB_PARENT(head, tmp, field));              \
 201 } while (/*CONSTCOND*/ 0)
 202
 203 #define ARB_RETURNFREE(head, elm, field)                                \
 204 ({                                                                      \
 205         ARB_COLOR(elm, field) = ARB_NULLCOL;                            \
 206         ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head);                \
 207         ARB_FREEIDX(head) = ARB_SELFIDX(head, elm);                     \
 208         elm;                                                            \
 209 })
 210
 211 #define ARB_GETFREEAT(head, field, fidx)                                \
 212 ({                                                                      \
 213         __typeof(ARB_NODE(head, 0)) _elm, _prevelm;                     \
 214         int _idx = fidx;                                                        \
 215         if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) {      \
 216                 /* Populate the free list. */                           \
 217                 ARB_ARRFOREACH_REVERSE(_elm, field, head) {             \
 218                         if (ARB_ISFREE(_elm, field))                    \
 219                                 ARB_RETURNFREE(head, _elm, field);      \
 220                 }                                                       \
 221         }                                                               \
 222         _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head));            \
 223         for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm)       \
 224                 _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field));    \
 225         if (_elm) {                                                     \
 226                 if (fidx == 0)                                          \
 227                         ARB_FREEIDX(head) =                             \
 228                             ARB_NEXTFREEIDX(_elm, field);               \
 229                 else                                                    \
 230                         ARB_NEXTFREEIDX(_prevelm, field) =              \
 231                             ARB_NEXTFREEIDX(_elm, field);               \
 232         }                                                               \
 233         _elm;                                                           \
 234 })
 235 #define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0)
 236
 237 /* Generates prototypes and inline functions */
 238 #define ARB_PROTOTYPE(name, type, field, cmp)                           \
 239         ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
 240 #define ARB_PROTOTYPE_STATIC(name, type, field, cmp)                    \
 241         ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
 242 #define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
 243         ARB_PROTOTYPE_INSERT_COLOR(name, type, attr);                   \
 244         ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr);                   \
 245         ARB_PROTOTYPE_INSERT(name, type, attr);                         \
 246         ARB_PROTOTYPE_REMOVE(name, type, attr);                         \
 247         ARB_PROTOTYPE_CFIND(name, type, attr);                          \
 248         ARB_PROTOTYPE_FIND(name, type, attr);                           \
 249         ARB_PROTOTYPE_NFIND(name, type, attr);                          \
 250         ARB_PROTOTYPE_CNEXT(name, type, attr);                          \
 251         ARB_PROTOTYPE_NEXT(name, type, attr);                           \
 252         ARB_PROTOTYPE_CPREV(name, type, attr);                          \
 253         ARB_PROTOTYPE_PREV(name, type, attr);                           \
 254         ARB_PROTOTYPE_CMINMAX(name, type, attr);                        \
 255         ARB_PROTOTYPE_MINMAX(name, type, attr);                         \
 256         ARB_PROTOTYPE_REBALANCE(name, type, attr);
 257 #define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr)                    \
 258         attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
 259 #define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr)                    \
 260         attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *)
 261 #define ARB_PROTOTYPE_REMOVE(name, type, attr)                          \
 262         attr struct type *name##_ARB_REMOVE(struct name *, struct type *)
 263 #define ARB_PROTOTYPE_INSERT(name, type, attr)                          \
 264         attr struct type *name##_ARB_INSERT(struct name *, struct type *)
 265 #define ARB_PROTOTYPE_CFIND(name, type, attr)                           \
 266         attr const struct type *name##_ARB_CFIND(const struct name *,   \
 267             const struct type *)
 268 #define ARB_PROTOTYPE_FIND(name, type, attr)                            \
 269         attr struct type *name##_ARB_FIND(const struct name *,          \
 270             const struct type *)
 271 #define ARB_PROTOTYPE_NFIND(name, type, attr)                           \
 272         attr struct type *name##_ARB_NFIND(struct name *, struct type *)
 273 #define ARB_PROTOTYPE_CNFIND(name, type, attr)                          \
 274         attr const struct type *name##_ARB_CNFIND(const struct name *,  \
 275             const struct type *)
 276 #define ARB_PROTOTYPE_CNEXT(name, type, attr)                           \
 277         attr const struct type *name##_ARB_CNEXT(const struct name *head,\
 278             const struct type *)
 279 #define ARB_PROTOTYPE_NEXT(name, type, attr)                            \
 280         attr struct type *name##_ARB_NEXT(const struct name *,          \
 281             const struct type *)
 282 #define ARB_PROTOTYPE_CPREV(name, type, attr)                           \
 283         attr const struct type *name##_ARB_CPREV(const struct name *,   \
 284             const struct type *)
 285 #define ARB_PROTOTYPE_PREV(name, type, attr)                            \
 286         attr struct type *name##_ARB_PREV(const struct name *,          \
 287             const struct type *)
 288 #define ARB_PROTOTYPE_CMINMAX(name, type, attr)                         \
 289         attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
 290 #define ARB_PROTOTYPE_MINMAX(name, type, attr)                          \
 291         attr struct type *name##_ARB_MINMAX(const struct name *, int)
 292 #define ARB_PROTOTYPE_REBALANCE(name, type, attr)                       \
 293         attr struct type *name##_ARB_REBALANCE(struct name *, struct type *)
 294
 295 #define ARB_GENERATE(name, type, field, cmp)                            \
 296         ARB_GENERATE_INTERNAL(name, type, field, cmp,)
 297 #define ARB_GENERATE_STATIC(name, type, field, cmp)                     \
 298         ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
 299 #define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
 300         ARB_GENERATE_INSERT_COLOR(name, type, field, attr)              \
 301         ARB_GENERATE_REMOVE_COLOR(name, type, field, attr)              \
 302         ARB_GENERATE_INSERT(name, type, field, cmp, attr)               \
 303         ARB_GENERATE_REMOVE(name, type, field, attr)                    \
 304         ARB_GENERATE_CFIND(name, type, field, cmp, attr)                \
 305         ARB_GENERATE_FIND(name, type, field, cmp, attr)                 \
 306         ARB_GENERATE_CNEXT(name, type, field, attr)                     \
 307         ARB_GENERATE_NEXT(name, type, field, attr)                      \
 308         ARB_GENERATE_CPREV(name, type, field, attr)                     \
 309         ARB_GENERATE_PREV(name, type, field, attr)                      \
 310         ARB_GENERATE_CMINMAX(name, type, field, attr)                   \
 311         ARB_GENERATE_MINMAX(name, type, field, attr)                    \
 312         ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)
 313
 314 #define ARB_GENERATE_INSERT_COLOR(name, type, field, attr)              \
 315 attr void                                                               \
 316 name##_ARB_INSERT_COLOR(struct name *head, struct type *elm)            \
 317 {                                                                       \
 318         struct type *parent, *gparent, *tmp;                            \
 319         while ((parent = ARB_PARENT(head, elm, field)) != NULL &&       \
 320             ARB_COLOR(parent, field) == ARB_RED) {                      \
 321                 gparent = ARB_PARENT(head, parent, field);              \
 322                 if (parent == ARB_LEFT(head, gparent, field)) {         \
 323                         tmp = ARB_RIGHT(head, gparent, field);          \
 324                         if (tmp && ARB_COLOR(tmp, field) == ARB_RED) {  \
 325                                 ARB_COLOR(tmp, field) = ARB_BLACK;      \
 326                                 ARB_SET_BLACKRED(parent, gparent, field); \
 327                                 elm = gparent;                          \
 328                                 continue;                               \
 329                         }                                               \
 330                         if (ARB_RIGHT(head, parent, field) == elm) {    \
 331                                 ARB_ROTATE_LEFT(head, parent, tmp, field); \
 332                                 tmp = parent;                           \
 333                                 parent = elm;                           \
 334                                 elm = tmp;                              \
 335                         }                                               \
 336                         ARB_SET_BLACKRED(parent, gparent, field);       \
 337                         ARB_ROTATE_RIGHT(head, gparent, tmp, field);    \
 338                 } else {                                                \
 339                         tmp = ARB_LEFT(head, gparent, field);           \
 340                         if (tmp && ARB_COLOR(tmp, field) == ARB_RED) {  \
 341                                 ARB_COLOR(tmp, field) = ARB_BLACK;      \
 342                                 ARB_SET_BLACKRED(parent, gparent, field); \
 343                                 elm = gparent;                          \
 344                                 continue;                               \
 345                         }                                               \
 346                         if (ARB_LEFT(head, parent, field) == elm) {     \
 347                                 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
 348                                 tmp = parent;                           \
 349                                 parent = elm;                           \
 350                                 elm = tmp;                              \
 351                         }                                               \
 352                         ARB_SET_BLACKRED(parent, gparent, field);       \
 353                         ARB_ROTATE_LEFT(head, gparent, tmp, field);     \
 354                 }                                                       \
 355         }                                                               \
 356         ARB_COLOR(ARB_ROOT(head), field) = ARB_BLACK;                   \
 357 }
 358
 359 #define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr)              \
 360 attr void                                                               \
 361 name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
 362 {                                                                       \
 363         struct type *tmp;                                               \
 364         while ((elm == NULL || ARB_COLOR(elm, field) == ARB_BLACK) &&   \
 365             elm != ARB_ROOT(head)) {                                    \
 366                 if (ARB_LEFT(head, parent, field) == elm) {             \
 367                         tmp = ARB_RIGHT(head, parent, field);           \
 368                         if (ARB_COLOR(tmp, field) == ARB_RED) {         \
 369                                 ARB_SET_BLACKRED(tmp, parent, field);   \
 370                                 ARB_ROTATE_LEFT(head, parent, tmp, field); \
 371                                 tmp = ARB_RIGHT(head, parent, field);   \
 372                         }                                               \
 373                         if ((ARB_LEFT(head, tmp, field) == NULL ||      \
 374                             ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
 375                             (ARB_RIGHT(head, tmp, field) == NULL ||     \
 376                             ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
 377                                 ARB_COLOR(tmp, field) = ARB_RED;                \
 378                                 elm = parent;                           \
 379                                 parent = ARB_PARENT(head, elm, field);  \
 380                         } else {                                        \
 381                                 if (ARB_RIGHT(head, tmp, field) == NULL || \
 382                                     ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK) { \
 383                                         struct type *oleft;             \
 384                                         if ((oleft = ARB_LEFT(head, tmp, field)) \
 385                                             != NULL)                    \
 386                                                 ARB_COLOR(oleft, field) = ARB_BLACK; \
 387                                         ARB_COLOR(tmp, field) = ARB_RED;        \
 388                                         ARB_ROTATE_RIGHT(head, tmp, oleft, field); \
 389                                         tmp = ARB_RIGHT(head, parent, field); \
 390                                 }                                       \
 391                                 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
 392                                 ARB_COLOR(parent, field) = ARB_BLACK;   \
 393                                 if (ARB_RIGHT(head, tmp, field))        \
 394                                         ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = ARB_BLACK; \
 395                                 ARB_ROTATE_LEFT(head, parent, tmp, field); \
 396                                 elm = ARB_ROOT(head);                   \
 397                                 break;                                  \
 398                         }                                               \
 399                 } else {                                                \
 400                         tmp = ARB_LEFT(head, parent, field);            \
 401                         if (ARB_COLOR(tmp, field) == ARB_RED) {         \
 402                                 ARB_SET_BLACKRED(tmp, parent, field);   \
 403                                 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
 404                                 tmp = ARB_LEFT(head, parent, field);    \
 405                         }                                               \
 406                         if ((ARB_LEFT(head, tmp, field) == NULL ||      \
 407                             ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) && \
 408                             (ARB_RIGHT(head, tmp, field) == NULL ||     \
 409                             ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == ARB_BLACK)) { \
 410                                 ARB_COLOR(tmp, field) = ARB_RED;                \
 411                                 elm = parent;                           \
 412                                 parent = ARB_PARENT(head, elm, field);  \
 413                         } else {                                        \
 414                                 if (ARB_LEFT(head, tmp, field) == NULL || \
 415                                     ARB_COLOR(ARB_LEFT(head, tmp, field), field) == ARB_BLACK) { \
 416                                         struct type *oright;            \
 417                                         if ((oright = ARB_RIGHT(head, tmp, field)) \
 418                                             != NULL)                    \
 419                                                 ARB_COLOR(oright, field) = ARB_BLACK; \
 420                                         ARB_COLOR(tmp, field) = ARB_RED;        \
 421                                         ARB_ROTATE_LEFT(head, tmp, oright, field); \
 422                                         tmp = ARB_LEFT(head, parent, field); \
 423                                 }                                       \
 424                                 ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
 425                                 ARB_COLOR(parent, field) = ARB_BLACK;   \
 426                                 if (ARB_LEFT(head, tmp, field))         \
 427                                         ARB_COLOR(ARB_LEFT(head, tmp, field), field) = ARB_BLACK; \
 428                                 ARB_ROTATE_RIGHT(head, parent, tmp, field); \
 429                                 elm = ARB_ROOT(head);                   \
 430                                 break;                                  \
 431                         }                                               \
 432                 }                                                       \
 433         }                                                               \
 434         if (elm)                                                        \
 435                 ARB_COLOR(elm, field) = ARB_BLACK;                      \
 436 }
 437
 438 #define ARB_GENERATE_REMOVE(name, type, field, attr)                    \
 439 attr struct type *                                                      \
 440 name##_ARB_REMOVE(struct name *head, struct type *elm)                  \
 441 {                                                                       \
 442         struct type *child, *parent, *old = elm;                        \
 443         int color;                                                      \
 444         if (ARB_LEFT(head, elm, field) == NULL)                         \
 445                 child = ARB_RIGHT(head, elm, field);                    \
 446         else if (ARB_RIGHT(head, elm, field) == NULL)                   \
 447                 child = ARB_LEFT(head, elm, field);                     \
 448         else {                                                          \
 449                 struct type *left;                                      \
 450                 elm = ARB_RIGHT(head, elm, field);                      \
 451                 while ((left = ARB_LEFT(head, elm, field)) != NULL)     \
 452                         elm = left;                                     \
 453                 child = ARB_RIGHT(head, elm, field);                    \
 454                 parent = ARB_PARENT(head, elm, field);                  \
 455                 color = ARB_COLOR(elm, field);                          \
 456                 if (child)                                              \
 457                         ARB_PARENTIDX(child, field) =                   \
 458                             ARB_SELFIDX(head, parent);                  \
 459                 if (parent) {                                           \
 460                         if (ARB_LEFT(head, parent, field) == elm)       \
 461                                 ARB_LEFTIDX(parent, field) =            \
 462                                     ARB_SELFIDX(head, child);           \
 463                         else                                            \
 464                                 ARB_RIGHTIDX(parent, field) =           \
 465                                     ARB_SELFIDX(head, child);           \
 466                         ARB_AUGMENT(parent);                            \
 467                 } else                                                  \
 468                         ARB_ROOTIDX(head) = ARB_SELFIDX(head, child);   \
 469                 if (ARB_PARENT(head, elm, field) == old)                \
 470                         parent = elm;                                   \
 471                 (elm)->field = (old)->field;                            \
 472                 if (ARB_PARENT(head, old, field)) {                     \
 473                         if (ARB_LEFT(head, ARB_PARENT(head, old, field), \
 474                             field) == old)                              \
 475                                 ARB_LEFTIDX(ARB_PARENT(head, old, field), \
 476                                     field) = ARB_SELFIDX(head, elm);    \
 477                         else                                            \
 478                                 ARB_RIGHTIDX(ARB_PARENT(head, old, field),\
 479                                     field) = ARB_SELFIDX(head, elm);    \
 480                         ARB_AUGMENT(ARB_PARENT(head, old, field));      \
 481                 } else                                                  \
 482                         ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm);     \
 483                 ARB_PARENTIDX(ARB_LEFT(head, old, field), field) =      \
 484                     ARB_SELFIDX(head, elm);                             \
 485                 if (ARB_RIGHT(head, old, field))                        \
 486                         ARB_PARENTIDX(ARB_RIGHT(head, old, field),      \
 487                             field) = ARB_SELFIDX(head, elm);            \
 488                 if (parent) {                                           \
 489                         left = parent;                                  \
 490                         do {                                            \
 491                                 ARB_AUGMENT(left);                      \
 492                         } while ((left = ARB_PARENT(head, left, field)) \
 493                             != NULL);                                   \
 494                 }                                                       \
 495                 goto color;                                             \
 496         }                                                               \
 497         parent = ARB_PARENT(head, elm, field);                          \
 498         color = ARB_COLOR(elm, field);                                  \
 499         if (child)                                                      \
 500                 ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\
 501         if (parent) {                                                   \
 502                 if (ARB_LEFT(head, parent, field) == elm)               \
 503                         ARB_LEFTIDX(parent, field) =                    \
 504                             ARB_SELFIDX(head, child);                   \
 505                 else                                                    \
 506                         ARB_RIGHTIDX(parent, field) =                   \
 507                             ARB_SELFIDX(head, child);                   \
 508                 ARB_AUGMENT(parent);                                    \
 509         } else                                                          \
 510                 ARB_ROOTIDX(head) = ARB_SELFIDX(head, child);           \
 511 color:                                                                  \
 512         if (color == ARB_BLACK)                                         \
 513                 name##_ARB_REMOVE_COLOR(head, parent, child);           \
 514         ARB_CURNODES(head) -= 1;                                        \
 515         if (ARB_MINIDX(head) == ARB_SELFIDX(head, old))                 \
 516                 ARB_MINIDX(head) = ARB_PARENTIDX(old, field);           \
 517         if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old))                 \
 518                 ARB_MAXIDX(head) = ARB_PARENTIDX(old, field);           \
 519         ARB_RETURNFREE(head, old, field);                               \
 520         return (old);                                                   \
 521 }                                                                       \
 522
 523 #define ARB_GENERATE_INSERT(name, type, field, cmp, attr)               \
 524 /* Inserts a node into the RB tree */                                   \
 525 attr struct type *                                                      \
 526 name##_ARB_INSERT(struct name *head, struct type *elm)                  \
 527 {                                                                       \
 528         struct type *tmp;                                               \
 529         struct type *parent = NULL;                                     \
 530         int comp = 0;                                                   \
 531         tmp = ARB_ROOT(head);                                           \
 532         while (tmp) {                                                   \
 533                 parent = tmp;                                           \
 534                 comp = (cmp)(elm, parent);                              \
 535                 if (comp < 0)                                           \
 536                         tmp = ARB_LEFT(head, tmp, field);               \
 537                 else if (comp > 0)                                      \
 538                         tmp = ARB_RIGHT(head, tmp, field);              \
 539                 else                                                    \
 540                         return (tmp);                                   \
 541         }                                                               \
 542         ARB_SET(head, elm, parent, field);                              \
 543         if (parent != NULL) {                                           \
 544                 if (comp < 0)                                           \
 545                         ARB_LEFTIDX(parent, field) =                    \
 546                             ARB_SELFIDX(head, elm);                     \
 547                 else                                                    \
 548                         ARB_RIGHTIDX(parent, field) =                   \
 549                             ARB_SELFIDX(head, elm);                     \
 550                 ARB_AUGMENT(parent);                                    \
 551         } else                                                          \
 552                 ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm);             \
 553         name##_ARB_INSERT_COLOR(head, elm);                             \
 554         ARB_CURNODES(head) += 1;                                        \
 555         if (ARB_MINIDX(head) == ARB_NULLIDX ||                          \
 556             (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) &&           \
 557             ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm)))      \
 558                 ARB_MINIDX(head) = ARB_SELFIDX(head, elm);              \
 559         if (ARB_MAXIDX(head) == ARB_NULLIDX ||                          \
 560             (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) &&           \
 561             ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm)))     \
 562                 ARB_MAXIDX(head) = ARB_SELFIDX(head, elm);      \
 563         return (NULL);                                                  \
 564 }
 565
 566 #define ARB_GENERATE_CFIND(name, type, field, cmp, attr)                \
 567 /* Finds the node with the same key as elm */                           \
 568 attr const struct type *                                                \
 569 name##_ARB_CFIND(const struct name *head, const struct type *elm)       \
 570 {                                                                       \
 571         const struct type *tmp = ARB_ROOT(head);                        \
 572         int comp;                                                       \
 573         while (tmp) {                                                   \
 574                 comp = cmp(elm, tmp);                                   \
 575                 if (comp < 0)                                           \
 576                         tmp = ARB_LEFT(head, tmp, field);               \
 577                 else if (comp > 0)                                      \
 578                         tmp = ARB_RIGHT(head, tmp, field);              \
 579                 else                                                    \
 580                         return (tmp);                                   \
 581         }                                                               \
 582         return (NULL);                                                  \
 583 }
 584
 585 #define ARB_GENERATE_FIND(name, type, field, cmp, attr)                 \
 586 attr struct type *                                                      \
 587 name##_ARB_FIND(const struct name *head, const struct type *elm)        \
 588 { return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); }
 589
 590 #define ARB_GENERATE_CNFIND(name, type, field, cmp, attr)               \
 591 /* Finds the first node greater than or equal to the search key */      \
 592 attr const struct type *                                                \
 593 name##_ARB_CNFIND(const struct name *head, const struct type *elm)      \
 594 {                                                                       \
 595         const struct type *tmp = ARB_ROOT(head);                        \
 596         const struct type *res = NULL;                                  \
 597         int comp;                                                       \
 598         while (tmp) {                                                   \
 599                 comp = cmp(elm, tmp);                                   \
 600                 if (comp < 0) {                                         \
 601                         res = tmp;                                      \
 602                         tmp = ARB_LEFT(head, tmp, field);               \
 603                 }                                                       \
 604                 else if (comp > 0)                                      \
 605                         tmp = ARB_RIGHT(head, tmp, field);              \
 606                 else                                                    \
 607                         return (tmp);                                   \
 608         }                                                               \
 609         return (res);                                                   \
 610 }
 611
 612 #define ARB_GENERATE_NFIND(name, type, field, cmp, attr)                \
 613 attr struct type *                                                      \
 614 name##_ARB_NFIND(const struct name *head, const struct type *elm)       \
 615 { return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); }
 616
 617 #define ARB_GENERATE_CNEXT(name, type, field, attr)                     \
 618 /* ARGSUSED */                                                          \
 619 attr const struct type *                                                \
 620 name##_ARB_CNEXT(const struct name *head, const struct type *elm)       \
 621 {                                                                       \
 622         if (ARB_RIGHT(head, elm, field)) {                              \
 623                 elm = ARB_RIGHT(head, elm, field);                      \
 624                 while (ARB_LEFT(head, elm, field))                      \
 625                         elm = ARB_LEFT(head, elm, field);               \
 626         } else {                                                        \
 627                 if (ARB_PARENT(head, elm, field) &&                     \
 628                     (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\
 629                     field)))                                            \
 630                         elm = ARB_PARENT(head, elm, field);             \
 631                 else {                                                  \
 632                         while (ARB_PARENT(head, elm, field) &&          \
 633                             (elm == ARB_RIGHT(head, ARB_PARENT(head,    \
 634                             elm, field), field)))                       \
 635                                 elm = ARB_PARENT(head, elm, field);     \
 636                         elm = ARB_PARENT(head, elm, field);             \
 637                 }                                                       \
 638         }                                                               \
 639         return (elm);                                                   \
 640 }
 641
 642 #define ARB_GENERATE_NEXT(name, type, field, attr)                      \
 643 attr struct type *                                                      \
 644 name##_ARB_NEXT(const struct name *head, const struct type *elm)        \
 645 { return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); }
 646
 647 #define ARB_GENERATE_CPREV(name, type, field, attr)                     \
 648 /* ARGSUSED */                                                          \
 649 attr const struct type *                                                \
 650 name##_ARB_CPREV(const struct name *head, const struct type *elm)       \
 651 {                                                                       \
 652         if (ARB_LEFT(head, elm, field)) {                               \
 653                 elm = ARB_LEFT(head, elm, field);                       \
 654                 while (ARB_RIGHT(head, elm, field))                     \
 655                         elm = ARB_RIGHT(head, elm, field);              \
 656         } else {                                                        \
 657                 if (ARB_PARENT(head, elm, field) &&                     \
 658                     (elm == ARB_RIGHT(head, ARB_PARENT(head, elm,       \
 659                     field), field)))                                    \
 660                         elm = ARB_PARENT(head, elm, field);             \
 661                 else {                                                  \
 662                         while (ARB_PARENT(head, elm, field) &&          \
 663                             (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\
 664                             field), field)))                            \
 665                                 elm = ARB_PARENT(head, elm, field);     \
 666                         elm = ARB_PARENT(head, elm, field);             \
 667                 }                                                       \
 668         }                                                               \
 669         return (elm);                                                   \
 670 }
 671
 672 #define ARB_GENERATE_PREV(name, type, field, attr)                      \
 673 attr struct type *                                                      \
 674 name##_ARB_PREV(const struct name *head, const struct type *elm)        \
 675 { return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); }
 676
 677 #define ARB_GENERATE_CMINMAX(name, type, field, attr)                   \
 678 attr const struct type *                                                \
 679 name##_ARB_CMINMAX(const struct name *head, int val)                    \
 680 {                                                                       \
 681         const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\
 682         const struct type *parent = NULL;                               \
 683         while (tmp) {                                                   \
 684                 parent = tmp;                                           \
 685                 if (val < 0)                                            \
 686                         tmp = ARB_LEFT(head, tmp, field);               \
 687                 else                                                    \
 688                         tmp = ARB_RIGHT(head, tmp, field);              \
 689         }                                                               \
 690         return (__DECONST(struct type *, parent));                      \
 691 }
 692
 693 #define ARB_GENERATE_MINMAX(name, type, field, attr)                    \
 694 attr struct type *                                                      \
 695 name##_ARB_MINMAX(const struct name *head, int val)                     \
 696 { return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
 697
 698 #define ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)            \
 699 attr struct type *                                                      \
 700 name##_ARB_REBALANCE(struct name *head, struct type *elm)               \
 701 {                                                                       \
 702         struct type *cmpelm;                                            \
 703         if (((cmpelm = ARB_PREV(name, head, elm)) != NULL &&            \
 704             (cmp)(cmpelm, elm) >= 0) ||                                 \
 705             ((cmpelm = ARB_NEXT(name, head, elm)) != NULL &&            \
 706             (cmp)(elm, cmpelm) >= 0)) {                                 \
 707                 /* XXXLAS: Remove/insert is heavy handed. */            \
 708                 ARB_REMOVE(name, head, elm);                            \
 709                 /* Remove puts elm on the free list. */                 \
 710                 elm = ARB_GETFREE(head, field);                         \
 711                 return (ARB_INSERT(name, head, elm));                   \
 712         }                                                               \
 713         return (NULL);                                                  \
 714 }                                                                       \
 715
 716 #define ARB_INSERT(name, x, y)  name##_ARB_INSERT(x, y)
 717 #define ARB_REMOVE(name, x, y)  name##_ARB_REMOVE(x, y)
 718 #define ARB_CFIND(name, x, y)   name##_ARB_CFIND(x, y)
 719 #define ARB_FIND(name, x, y)    name##_ARB_FIND(x, y)
 720 #define ARB_CNFIND(name, x, y)  name##_ARB_CNFIND(x, y)
 721 #define ARB_NFIND(name, x, y)   name##_ARB_NFIND(x, y)
 722 #define ARB_CNEXT(name, x, y)   name##_ARB_CNEXT(x, y)
 723 #define ARB_NEXT(name, x, y)    name##_ARB_NEXT(x, y)
 724 #define ARB_CPREV(name, x, y)   name##_ARB_CPREV(x, y)
 725 #define ARB_PREV(name, x, y)    name##_ARB_PREV(x, y)
 726 #define ARB_CMIN(name, x)       (ARB_MINIDX(x) == ARB_NULLIDX ? \
 727         name##_ARB_CMINMAX(x, ARB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x)))
 728 #define ARB_MIN(name, x)        (ARB_MINIDX(x) == ARB_NULLIDX ? \
 729         name##_ARB_MINMAX(x, ARB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x)))
 730 #define ARB_CMAX(name, x)       (ARB_MAXIDX(x) == ARB_NULLIDX ? \
 731         name##_ARB_CMINMAX(x, ARB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
 732 #define ARB_MAX(name, x)        (ARB_MAXIDX(x) == ARB_NULLIDX ? \
 733         name##_ARB_MINMAX(x, ARB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
 734 #define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y)
 735
 736 #define ARB_FOREACH(x, name, head)                                      \
 737         for ((x) = ARB_MIN(name, head);                                 \
 738              (x) != NULL;                                               \
 739              (x) = name##_ARB_NEXT(head, x))
 740
 741 #define ARB_FOREACH_FROM(x, name, y)                                    \
 742         for ((x) = (y);                                                 \
 743             ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL);   \
 744              (x) = (y))
 745
 746 #define ARB_FOREACH_SAFE(x, name, head, y)                              \
 747         for ((x) = ARB_MIN(name, head);                                 \
 748             ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL);   \
 749              (x) = (y))
 750
 751 #define ARB_FOREACH_REVERSE(x, name, head)                              \
 752         for ((x) = ARB_MAX(name, head);                                 \
 753              (x) != NULL;                                               \
 754              (x) = name##_ARB_PREV(x))
 755
 756 #define ARB_FOREACH_REVERSE_FROM(x, name, y)                            \
 757         for ((x) = (y);                                                 \
 758             ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL);   \
 759              (x) = (y))
 760
 761 #define ARB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
 762         for ((x) = ARB_MAX(name, head);                                 \
 763             ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL);   \
 764              (x) = (y))
 765
 766 #define ARB_ARRFOREACH(x, field, head)                                  \
 767         for ((x) = ARB_NODES(head);                                     \
 768             ARB_SELFIDX(head, x) < ARB_MAXNODES(head);                  \
 769             (x)++)
 770
 771 #define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond)              \
 772         for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1);          \
 773             (x) >= ARB_NODES(head) && (extracond);                      \
 774             (x)--)
 775
 776 #define ARB_ARRFOREACH_REVERSE(x, field, head) \
 777         ARB_ARRFOREACH_REVWCOND(x, field, head, 1)
 778
 779 #endif  /* _SYS_ARB_H_ */