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_ */ 782