31 # define UV__UNUSED __attribute__((unused)) 64 #define SPLAY_HEAD(name, type) \ 66 struct type *sph_root; \ 69 #define SPLAY_INITIALIZER(root) \ 72 #define SPLAY_INIT(root) do { \ 73 (root)->sph_root = NULL; \ 76 #define SPLAY_ENTRY(type) \ 78 struct type *spe_left; \ 79 struct type *spe_right; \ 82 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left 83 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right 84 #define SPLAY_ROOT(head) (head)->sph_root 85 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) 88 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ 89 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ 90 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 91 (head)->sph_root = tmp; \ 94 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ 95 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ 96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 97 (head)->sph_root = tmp; \ 100 #define SPLAY_LINKLEFT(head, tmp, field) do { \ 101 SPLAY_LEFT(tmp, field) = (head)->sph_root; \ 102 tmp = (head)->sph_root; \ 103 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 106 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ 107 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ 108 tmp = (head)->sph_root; \ 109 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 112 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ 113 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ 114 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \ 115 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ 116 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ 121 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ 122 void name##_SPLAY(struct name *, struct type *); \ 123 void name##_SPLAY_MINMAX(struct name *, int); \ 124 struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ 125 struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ 128 static __inline struct type * \ 129 name##_SPLAY_FIND(struct name *head, struct type *elm) \ 131 if (SPLAY_EMPTY(head)) \ 133 name##_SPLAY(head, elm); \ 134 if ((cmp)(elm, (head)->sph_root) == 0) \ 135 return (head->sph_root); \ 139 static __inline struct type * \ 140 name##_SPLAY_NEXT(struct name *head, struct type *elm) \ 142 name##_SPLAY(head, elm); \ 143 if (SPLAY_RIGHT(elm, field) != NULL) { \ 144 elm = SPLAY_RIGHT(elm, field); \ 145 while (SPLAY_LEFT(elm, field) != NULL) { \ 146 elm = SPLAY_LEFT(elm, field); \ 153 static __inline struct type * \ 154 name##_SPLAY_MIN_MAX(struct name *head, int val) \ 156 name##_SPLAY_MINMAX(head, val); \ 157 return (SPLAY_ROOT(head)); \ 163 #define SPLAY_GENERATE(name, type, field, cmp) \ 165 name##_SPLAY_INSERT(struct name *head, struct type *elm) \ 167 if (SPLAY_EMPTY(head)) { \ 168 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ 171 name##_SPLAY(head, elm); \ 172 __comp = (cmp)(elm, (head)->sph_root); \ 174 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \ 175 SPLAY_RIGHT(elm, field) = (head)->sph_root; \ 176 SPLAY_LEFT((head)->sph_root, field) = NULL; \ 177 } else if (__comp > 0) { \ 178 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \ 179 SPLAY_LEFT(elm, field) = (head)->sph_root; \ 180 SPLAY_RIGHT((head)->sph_root, field) = NULL; \ 182 return ((head)->sph_root); \ 184 (head)->sph_root = (elm); \ 189 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ 191 struct type *__tmp; \ 192 if (SPLAY_EMPTY(head)) \ 194 name##_SPLAY(head, elm); \ 195 if ((cmp)(elm, (head)->sph_root) == 0) { \ 196 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ 197 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ 199 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 200 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ 201 name##_SPLAY(head, elm); \ 202 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ 210 name##_SPLAY(struct name *head, struct type *elm) \ 212 struct type __node, *__left, *__right, *__tmp; \ 215 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 216 __left = __right = &__node; \ 218 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \ 220 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 223 if ((cmp)(elm, __tmp) < 0){ \ 224 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 225 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 228 SPLAY_LINKLEFT(head, __right, field); \ 229 } else if (__comp > 0) { \ 230 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 233 if ((cmp)(elm, __tmp) > 0){ \ 234 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 235 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 238 SPLAY_LINKRIGHT(head, __left, field); \ 241 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 247 void name##_SPLAY_MINMAX(struct name *head, int __comp) \ 249 struct type __node, *__left, *__right, *__tmp; \ 251 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL; \ 252 __left = __right = &__node; \ 256 __tmp = SPLAY_LEFT((head)->sph_root, field); \ 260 SPLAY_ROTATE_RIGHT(head, __tmp, field); \ 261 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \ 264 SPLAY_LINKLEFT(head, __right, field); \ 265 } else if (__comp > 0) { \ 266 __tmp = SPLAY_RIGHT((head)->sph_root, field); \ 270 SPLAY_ROTATE_LEFT(head, __tmp, field); \ 271 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \ 274 SPLAY_LINKRIGHT(head, __left, field); \ 277 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ 280 #define SPLAY_NEGINF -1 283 #define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) 284 #define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) 285 #define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) 286 #define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) 287 #define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ 288 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) 289 #define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ 290 : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) 292 #define SPLAY_FOREACH(x, name, head) \ 293 for ((x) = SPLAY_MIN(name, head); \ 295 (x) = SPLAY_NEXT(name, head, x)) 298 #define RB_HEAD(name, type) \ 300 struct type *rbh_root; \ 303 #define RB_INITIALIZER(root) \ 306 #define RB_INIT(root) do { \ 307 (root)->rbh_root = NULL; \ 312 #define RB_ENTRY(type) \ 314 struct type *rbe_left; \ 315 struct type *rbe_right; \ 316 struct type *rbe_parent; \ 320 #define RB_LEFT(elm, field) (elm)->field.rbe_left 321 #define RB_RIGHT(elm, field) (elm)->field.rbe_right 322 #define RB_PARENT(elm, field) (elm)->field.rbe_parent 323 #define RB_COLOR(elm, field) (elm)->field.rbe_color 324 #define RB_ROOT(head) (head)->rbh_root 325 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) 327 #define RB_SET(elm, parent, field) do { \ 328 RB_PARENT(elm, field) = parent; \ 329 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ 330 RB_COLOR(elm, field) = RB_RED; \ 333 #define RB_SET_BLACKRED(black, red, field) do { \ 334 RB_COLOR(black, field) = RB_BLACK; \ 335 RB_COLOR(red, field) = RB_RED; \ 339 #define RB_AUGMENT(x) do {} while (0) 342 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ 343 (tmp) = RB_RIGHT(elm, field); \ 344 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \ 345 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ 348 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 349 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 350 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 352 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 354 (head)->rbh_root = (tmp); \ 355 RB_LEFT(tmp, field) = (elm); \ 356 RB_PARENT(elm, field) = (tmp); \ 358 if ((RB_PARENT(tmp, field))) \ 359 RB_AUGMENT(RB_PARENT(tmp, field)); \ 362 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ 363 (tmp) = RB_LEFT(elm, field); \ 364 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \ 365 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ 368 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \ 369 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ 370 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ 372 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ 374 (head)->rbh_root = (tmp); \ 375 RB_RIGHT(tmp, field) = (elm); \ 376 RB_PARENT(elm, field) = (tmp); \ 378 if ((RB_PARENT(tmp, field))) \ 379 RB_AUGMENT(RB_PARENT(tmp, field)); \ 383 #define RB_PROTOTYPE(name, type, field, cmp) \ 384 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) 385 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ 386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 387 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ 388 attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ 389 attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ 390 attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ 391 attr struct type *name##_RB_INSERT(struct name *, struct type *); \ 392 attr struct type *name##_RB_FIND(struct name *, struct type *); \ 393 attr struct type *name##_RB_NFIND(struct name *, struct type *); \ 394 attr struct type *name##_RB_NEXT(struct type *); \ 395 attr struct type *name##_RB_PREV(struct type *); \ 396 attr struct type *name##_RB_MINMAX(struct name *, int); \ 402 #define RB_GENERATE(name, type, field, cmp) \ 403 RB_GENERATE_INTERNAL(name, type, field, cmp,) 404 #define RB_GENERATE_STATIC(name, type, field, cmp) \ 405 RB_GENERATE_INTERNAL(name, type, field, cmp, UV__UNUSED static) 406 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ 408 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ 410 struct type *parent, *gparent, *tmp; \ 411 while ((parent = RB_PARENT(elm, field)) != NULL && \ 412 RB_COLOR(parent, field) == RB_RED) { \ 413 gparent = RB_PARENT(parent, field); \ 414 if (parent == RB_LEFT(gparent, field)) { \ 415 tmp = RB_RIGHT(gparent, field); \ 416 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 417 RB_COLOR(tmp, field) = RB_BLACK; \ 418 RB_SET_BLACKRED(parent, gparent, field); \ 422 if (RB_RIGHT(parent, field) == elm) { \ 423 RB_ROTATE_LEFT(head, parent, tmp, field); \ 428 RB_SET_BLACKRED(parent, gparent, field); \ 429 RB_ROTATE_RIGHT(head, gparent, tmp, field); \ 431 tmp = RB_LEFT(gparent, field); \ 432 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ 433 RB_COLOR(tmp, field) = RB_BLACK; \ 434 RB_SET_BLACKRED(parent, gparent, field); \ 438 if (RB_LEFT(parent, field) == elm) { \ 439 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 444 RB_SET_BLACKRED(parent, gparent, field); \ 445 RB_ROTATE_LEFT(head, gparent, tmp, field); \ 448 RB_COLOR(head->rbh_root, field) = RB_BLACK; \ 452 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \ 456 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ 457 elm != RB_ROOT(head)) { \ 458 if (RB_LEFT(parent, field) == elm) { \ 459 tmp = RB_RIGHT(parent, field); \ 460 if (RB_COLOR(tmp, field) == RB_RED) { \ 461 RB_SET_BLACKRED(tmp, parent, field); \ 462 RB_ROTATE_LEFT(head, parent, tmp, field); \ 463 tmp = RB_RIGHT(parent, field); \ 465 if ((RB_LEFT(tmp, field) == NULL || \ 466 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 467 (RB_RIGHT(tmp, field) == NULL || \ 468 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 469 RB_COLOR(tmp, field) = RB_RED; \ 471 parent = RB_PARENT(elm, field); \ 473 if (RB_RIGHT(tmp, field) == NULL || \ 474 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) { \ 475 struct type *oleft; \ 476 if ((oleft = RB_LEFT(tmp, field)) \ 478 RB_COLOR(oleft, field) = RB_BLACK; \ 479 RB_COLOR(tmp, field) = RB_RED; \ 480 RB_ROTATE_RIGHT(head, tmp, oleft, field); \ 481 tmp = RB_RIGHT(parent, field); \ 483 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 484 RB_COLOR(parent, field) = RB_BLACK; \ 485 if (RB_RIGHT(tmp, field)) \ 486 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK; \ 487 RB_ROTATE_LEFT(head, parent, tmp, field); \ 488 elm = RB_ROOT(head); \ 492 tmp = RB_LEFT(parent, field); \ 493 if (RB_COLOR(tmp, field) == RB_RED) { \ 494 RB_SET_BLACKRED(tmp, parent, field); \ 495 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 496 tmp = RB_LEFT(parent, field); \ 498 if ((RB_LEFT(tmp, field) == NULL || \ 499 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) && \ 500 (RB_RIGHT(tmp, field) == NULL || \ 501 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) { \ 502 RB_COLOR(tmp, field) = RB_RED; \ 504 parent = RB_PARENT(elm, field); \ 506 if (RB_LEFT(tmp, field) == NULL || \ 507 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) { \ 508 struct type *oright; \ 509 if ((oright = RB_RIGHT(tmp, field)) \ 511 RB_COLOR(oright, field) = RB_BLACK; \ 512 RB_COLOR(tmp, field) = RB_RED; \ 513 RB_ROTATE_LEFT(head, tmp, oright, field); \ 514 tmp = RB_LEFT(parent, field); \ 516 RB_COLOR(tmp, field) = RB_COLOR(parent, field); \ 517 RB_COLOR(parent, field) = RB_BLACK; \ 518 if (RB_LEFT(tmp, field)) \ 519 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK; \ 520 RB_ROTATE_RIGHT(head, parent, tmp, field); \ 521 elm = RB_ROOT(head); \ 527 RB_COLOR(elm, field) = RB_BLACK; \ 531 name##_RB_REMOVE(struct name *head, struct type *elm) \ 533 struct type *child, *parent, *old = elm; \ 535 if (RB_LEFT(elm, field) == NULL) \ 536 child = RB_RIGHT(elm, field); \ 537 else if (RB_RIGHT(elm, field) == NULL) \ 538 child = RB_LEFT(elm, field); \ 541 elm = RB_RIGHT(elm, field); \ 542 while ((left = RB_LEFT(elm, field)) != NULL) \ 544 child = RB_RIGHT(elm, field); \ 545 parent = RB_PARENT(elm, field); \ 546 color = RB_COLOR(elm, field); \ 548 RB_PARENT(child, field) = parent; \ 550 if (RB_LEFT(parent, field) == elm) \ 551 RB_LEFT(parent, field) = child; \ 553 RB_RIGHT(parent, field) = child; \ 554 RB_AUGMENT(parent); \ 556 RB_ROOT(head) = child; \ 557 if (RB_PARENT(elm, field) == old) \ 559 (elm)->field = (old)->field; \ 560 if (RB_PARENT(old, field)) { \ 561 if (RB_LEFT(RB_PARENT(old, field), field) == old) \ 562 RB_LEFT(RB_PARENT(old, field), field) = elm; \ 564 RB_RIGHT(RB_PARENT(old, field), field) = elm; \ 565 RB_AUGMENT(RB_PARENT(old, field)); \ 567 RB_ROOT(head) = elm; \ 568 RB_PARENT(RB_LEFT(old, field), field) = elm; \ 569 if (RB_RIGHT(old, field)) \ 570 RB_PARENT(RB_RIGHT(old, field), field) = elm; \ 575 } while ((left = RB_PARENT(left, field)) != NULL); \ 579 parent = RB_PARENT(elm, field); \ 580 color = RB_COLOR(elm, field); \ 582 RB_PARENT(child, field) = parent; \ 584 if (RB_LEFT(parent, field) == elm) \ 585 RB_LEFT(parent, field) = child; \ 587 RB_RIGHT(parent, field) = child; \ 588 RB_AUGMENT(parent); \ 590 RB_ROOT(head) = child; \ 592 if (color == RB_BLACK) \ 593 name##_RB_REMOVE_COLOR(head, parent, child); \ 599 name##_RB_INSERT(struct name *head, struct type *elm) \ 602 struct type *parent = NULL; \ 604 tmp = RB_ROOT(head); \ 607 comp = (cmp)(elm, parent); \ 609 tmp = RB_LEFT(tmp, field); \ 611 tmp = RB_RIGHT(tmp, field); \ 615 RB_SET(elm, parent, field); \ 616 if (parent != NULL) { \ 618 RB_LEFT(parent, field) = elm; \ 620 RB_RIGHT(parent, field) = elm; \ 621 RB_AUGMENT(parent); \ 623 RB_ROOT(head) = elm; \ 624 name##_RB_INSERT_COLOR(head, elm); \ 630 name##_RB_FIND(struct name *head, struct type *elm) \ 632 struct type *tmp = RB_ROOT(head); \ 635 comp = cmp(elm, tmp); \ 637 tmp = RB_LEFT(tmp, field); \ 639 tmp = RB_RIGHT(tmp, field); \ 648 name##_RB_NFIND(struct name *head, struct type *elm) \ 650 struct type *tmp = RB_ROOT(head); \ 651 struct type *res = NULL; \ 654 comp = cmp(elm, tmp); \ 657 tmp = RB_LEFT(tmp, field); \ 660 tmp = RB_RIGHT(tmp, field); \ 669 name##_RB_NEXT(struct type *elm) \ 671 if (RB_RIGHT(elm, field)) { \ 672 elm = RB_RIGHT(elm, field); \ 673 while (RB_LEFT(elm, field)) \ 674 elm = RB_LEFT(elm, field); \ 676 if (RB_PARENT(elm, field) && \ 677 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 678 elm = RB_PARENT(elm, field); \ 680 while (RB_PARENT(elm, field) && \ 681 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 682 elm = RB_PARENT(elm, field); \ 683 elm = RB_PARENT(elm, field); \ 691 name##_RB_PREV(struct type *elm) \ 693 if (RB_LEFT(elm, field)) { \ 694 elm = RB_LEFT(elm, field); \ 695 while (RB_RIGHT(elm, field)) \ 696 elm = RB_RIGHT(elm, field); \ 698 if (RB_PARENT(elm, field) && \ 699 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ 700 elm = RB_PARENT(elm, field); \ 702 while (RB_PARENT(elm, field) && \ 703 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ 704 elm = RB_PARENT(elm, field); \ 705 elm = RB_PARENT(elm, field); \ 712 name##_RB_MINMAX(struct name *head, int val) \ 714 struct type *tmp = RB_ROOT(head); \ 715 struct type *parent = NULL; \ 719 tmp = RB_LEFT(tmp, field); \ 721 tmp = RB_RIGHT(tmp, field); \ 729 #define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) 730 #define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) 731 #define RB_FIND(name, x, y) name##_RB_FIND(x, y) 732 #define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) 733 #define RB_NEXT(name, x, y) name##_RB_NEXT(y) 734 #define RB_PREV(name, x, y) name##_RB_PREV(y) 735 #define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) 736 #define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) 738 #define RB_FOREACH(x, name, head) \ 739 for ((x) = RB_MIN(name, head); \ 741 (x) = name##_RB_NEXT(x)) 743 #define RB_FOREACH_FROM(x, name, y) \ 745 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 748 #define RB_FOREACH_SAFE(x, name, head, y) \ 749 for ((x) = RB_MIN(name, head); \ 750 ((x) != NULL) && ((y) = name##_RB_NEXT(x), (x) != NULL); \ 753 #define RB_FOREACH_REVERSE(x, name, head) \ 754 for ((x) = RB_MAX(name, head); \ 756 (x) = name##_RB_PREV(x)) 758 #define RB_FOREACH_REVERSE_FROM(x, name, y) \ 760 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \ 763 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ 764 for ((x) = RB_MAX(name, head); \ 765 ((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \