sys/sys/arb.h

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