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