sys/sys/arb.h

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