Lines Matching refs:field
91 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left argument
92 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right argument
97 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
98 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
99 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
103 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
104 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
109 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
115 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
116 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
118 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
121 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
122 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
123 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
124 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
125 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
130 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ argument
152 if (SPLAY_RIGHT(elm, field) != NULL) { \
153 elm = SPLAY_RIGHT(elm, field); \
154 while (SPLAY_LEFT(elm, field) != NULL) { \
155 elm = SPLAY_LEFT(elm, field); \
172 #define SPLAY_GENERATE(name, type, field, cmp) \ argument
177 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
183 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
184 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
185 SPLAY_LEFT((head)->sph_root, field) = NULL; \
187 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
188 SPLAY_LEFT(elm, field) = (head)->sph_root; \
189 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
205 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
206 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
208 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
209 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
211 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
224 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
229 __tmp = SPLAY_LEFT((head)->sph_root, field); \
233 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
234 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
237 SPLAY_LINKLEFT(head, __right, field); \
239 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
243 SPLAY_ROTATE_LEFT(head, __tmp, field); \
244 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
247 SPLAY_LINKRIGHT(head, __left, field); \
250 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
260 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
265 __tmp = SPLAY_LEFT((head)->sph_root, field); \
269 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
270 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
273 SPLAY_LINKLEFT(head, __right, field); \
275 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
279 SPLAY_ROTATE_LEFT(head, __tmp, field); \
280 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
283 SPLAY_LINKRIGHT(head, __left, field); \
286 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
326 #define RB_LEFT(elm, field) (elm)->field.rbe_left argument
327 #define RB_RIGHT(elm, field) (elm)->field.rbe_right argument
336 #define RB_UP(elm, field) (elm)->field.rbe_parent argument
337 #define RB_BITS(elm, field) (*(__uintptr_t *)&RB_UP(elm, field)) argument
341 #define RB_FLIP_LEFT(elm, field) (RB_BITS(elm, field) ^= RB_RED_L) argument
342 #define RB_FLIP_RIGHT(elm, field) (RB_BITS(elm, field) ^= RB_RED_R) argument
343 #define RB_RED_LEFT(elm, field) ((RB_BITS(elm, field) & RB_RED_L) != 0) argument
344 #define RB_RED_RIGHT(elm, field) ((RB_BITS(elm, field) & RB_RED_R) != 0) argument
345 #define RB_PARENT(elm, field) ((__typeof(RB_UP(elm, field))) \ argument
346 (RB_BITS(elm, field) & ~RB_RED_MASK))
350 #define RB_SET_PARENT(dst, src, field) do { \ argument
351 RB_BITS(dst, field) &= RB_RED_MASK; \
352 RB_BITS(dst, field) |= (__uintptr_t)src; \
355 #define RB_SET(elm, parent, field) do { \ argument
356 RB_UP(elm, field) = parent; \
357 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
360 #define RB_COLOR(elm, field) (RB_PARENT(elm, field) == NULL ? 0 : \ argument
361 RB_LEFT(RB_PARENT(elm, field), field) == elm ? \
362 RB_RED_LEFT(RB_PARENT(elm, field), field) : \
363 RB_RED_RIGHT(RB_PARENT(elm, field), field))
373 #define RB_SWAP_CHILD(head, out, in, field) do { \ argument
374 if (RB_PARENT(out, field) == NULL) \
376 else if ((out) == RB_LEFT(RB_PARENT(out, field), field)) \
377 RB_LEFT(RB_PARENT(out, field), field) = (in); \
379 RB_RIGHT(RB_PARENT(out, field), field) = (in); \
382 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
383 (tmp) = RB_RIGHT(elm, field); \
384 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
385 RB_SET_PARENT(RB_RIGHT(elm, field), elm, field); \
387 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \
388 RB_SWAP_CHILD(head, elm, tmp, field); \
389 RB_LEFT(tmp, field) = (elm); \
390 RB_SET_PARENT(elm, tmp, field); \
394 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
395 (tmp) = RB_LEFT(elm, field); \
396 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
397 RB_SET_PARENT(RB_LEFT(elm, field), elm, field); \
399 RB_SET_PARENT(tmp, RB_PARENT(elm, field), field); \
400 RB_SWAP_CHILD(head, elm, tmp, field); \
401 RB_RIGHT(tmp, field) = (elm); \
402 RB_SET_PARENT(elm, tmp, field); \
407 #define RB_PROTOTYPE(name, type, field, cmp) \ argument
408 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
409 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ argument
410 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
411 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ argument
447 #define RB_GENERATE(name, type, field, cmp) \ argument
448 RB_GENERATE_INTERNAL(name, type, field, cmp,)
449 #define RB_GENERATE_STATIC(name, type, field, cmp) \ argument
450 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
451 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ argument
452 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
453 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
454 RB_GENERATE_INSERT(name, type, field, cmp, attr) \
455 RB_GENERATE_REMOVE(name, type, field, attr) \
456 RB_GENERATE_FIND(name, type, field, cmp, attr) \
457 RB_GENERATE_NFIND(name, type, field, cmp, attr) \
458 RB_GENERATE_NEXT(name, type, field, attr) \
459 RB_GENERATE_PREV(name, type, field, attr) \
460 RB_GENERATE_MINMAX(name, type, field, attr) \
461 RB_GENERATE_REINSERT(name, type, field, cmp, attr)
463 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ argument
468 while ((parent = RB_PARENT(elm, field)) != NULL) { \
469 if (RB_LEFT(parent, field) == elm) { \
470 if (RB_RED_LEFT(parent, field)) { \
471 RB_FLIP_LEFT(parent, field); \
474 RB_FLIP_RIGHT(parent, field); \
475 if (RB_RED_RIGHT(parent, field)) { \
479 if (!RB_RED_RIGHT(elm, field)) { \
480 RB_FLIP_LEFT(elm, field); \
481 RB_ROTATE_LEFT(head, elm, child, field);\
482 if (RB_RED_LEFT(child, field)) \
483 RB_FLIP_RIGHT(elm, field); \
484 else if (RB_RED_RIGHT(child, field)) \
485 RB_FLIP_LEFT(parent, field); \
488 RB_ROTATE_RIGHT(head, parent, elm, field); \
490 if (RB_RED_RIGHT(parent, field)) { \
491 RB_FLIP_RIGHT(parent, field); \
494 RB_FLIP_LEFT(parent, field); \
495 if (RB_RED_LEFT(parent, field)) { \
499 if (!RB_RED_LEFT(elm, field)) { \
500 RB_FLIP_RIGHT(elm, field); \
501 RB_ROTATE_RIGHT(head, elm, child, field);\
502 if (RB_RED_RIGHT(child, field)) \
503 RB_FLIP_LEFT(elm, field); \
504 else if (RB_RED_LEFT(child, field)) \
505 RB_FLIP_RIGHT(parent, field); \
508 RB_ROTATE_LEFT(head, parent, elm, field); \
510 RB_BITS(elm, field) &= ~RB_RED_MASK; \
515 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ argument
521 if (RB_LEFT(parent, field) == elm && \
522 RB_RIGHT(parent, field) == elm) { \
523 RB_BITS(parent, field) &= ~RB_RED_MASK; \
525 parent = RB_PARENT(elm, field); \
530 if (RB_LEFT(parent, field) == elm) { \
531 if (!RB_RED_LEFT(parent, field)) { \
532 RB_FLIP_LEFT(parent, field); \
535 if (RB_RED_RIGHT(parent, field)) { \
536 RB_FLIP_RIGHT(parent, field); \
540 sib = RB_RIGHT(parent, field); \
541 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
542 RB_BITS(sib, field) &= ~RB_RED_MASK; \
546 RB_FLIP_RIGHT(sib, field); \
547 if (RB_RED_LEFT(sib, field)) \
548 RB_FLIP_LEFT(parent, field); \
549 else if (!RB_RED_RIGHT(sib, field)) { \
550 RB_FLIP_LEFT(parent, field); \
551 RB_ROTATE_RIGHT(head, sib, elm, field); \
552 if (RB_RED_RIGHT(elm, field)) \
553 RB_FLIP_LEFT(sib, field); \
554 if (RB_RED_LEFT(elm, field)) \
555 RB_FLIP_RIGHT(parent, field); \
556 RB_BITS(elm, field) |= RB_RED_MASK; \
559 RB_ROTATE_LEFT(head, parent, sib, field); \
561 if (!RB_RED_RIGHT(parent, field)) { \
562 RB_FLIP_RIGHT(parent, field); \
565 if (RB_RED_LEFT(parent, field)) { \
566 RB_FLIP_LEFT(parent, field); \
570 sib = RB_LEFT(parent, field); \
571 if ((~RB_BITS(sib, field) & RB_RED_MASK) == 0) {\
572 RB_BITS(sib, field) &= ~RB_RED_MASK; \
576 RB_FLIP_LEFT(sib, field); \
577 if (RB_RED_RIGHT(sib, field)) \
578 RB_FLIP_RIGHT(parent, field); \
579 else if (!RB_RED_LEFT(sib, field)) { \
580 RB_FLIP_RIGHT(parent, field); \
581 RB_ROTATE_LEFT(head, sib, elm, field); \
582 if (RB_RED_LEFT(elm, field)) \
583 RB_FLIP_RIGHT(sib, field); \
584 if (RB_RED_RIGHT(elm, field)) \
585 RB_FLIP_LEFT(parent, field); \
586 RB_BITS(elm, field) |= RB_RED_MASK; \
589 RB_ROTATE_RIGHT(head, parent, sib, field); \
592 } while ((parent = RB_PARENT(elm, field)) != NULL); \
595 #define RB_GENERATE_REMOVE(name, type, field, attr) \ argument
602 parent = RB_PARENT(elm, field); \
603 right = RB_RIGHT(elm, field); \
604 if (RB_LEFT(elm, field) == NULL) \
607 elm = child = RB_LEFT(elm, field); \
609 if ((child = RB_LEFT(right, field)) == NULL) { \
610 child = RB_RIGHT(right, field); \
611 RB_RIGHT(old, field) = child; \
616 while ((child = RB_LEFT(elm, field)) != NULL); \
617 child = RB_RIGHT(elm, field); \
618 parent = RB_PARENT(elm, field); \
619 RB_LEFT(parent, field) = child; \
620 RB_SET_PARENT(RB_RIGHT(old, field), elm, field);\
622 RB_SET_PARENT(RB_LEFT(old, field), elm, field); \
623 elm->field = old->field; \
625 RB_SWAP_CHILD(head, old, elm, field); \
627 RB_SET_PARENT(child, parent, field); \
632 parent = RB_PARENT(parent, field); \
637 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ argument
650 tmp = RB_LEFT(tmp, field); \
652 tmp = RB_RIGHT(tmp, field); \
656 RB_SET(elm, parent, field); \
660 RB_LEFT(parent, field) = elm; \
662 RB_RIGHT(parent, field) = elm; \
666 elm = RB_PARENT(elm, field); \
671 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ argument
681 tmp = RB_LEFT(tmp, field); \
683 tmp = RB_RIGHT(tmp, field); \
690 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ argument
702 tmp = RB_LEFT(tmp, field); \
705 tmp = RB_RIGHT(tmp, field); \
712 #define RB_GENERATE_NEXT(name, type, field, attr) \ argument
717 if (RB_RIGHT(elm, field)) { \
718 elm = RB_RIGHT(elm, field); \
719 while (RB_LEFT(elm, field)) \
720 elm = RB_LEFT(elm, field); \
722 if (RB_PARENT(elm, field) && \
723 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
724 elm = RB_PARENT(elm, field); \
726 while (RB_PARENT(elm, field) && \
727 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
728 elm = RB_PARENT(elm, field); \
729 elm = RB_PARENT(elm, field); \
735 #define RB_GENERATE_PREV(name, type, field, attr) \ argument
740 if (RB_LEFT(elm, field)) { \
741 elm = RB_LEFT(elm, field); \
742 while (RB_RIGHT(elm, field)) \
743 elm = RB_RIGHT(elm, field); \
745 if (RB_PARENT(elm, field) && \
746 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
747 elm = RB_PARENT(elm, field); \
749 while (RB_PARENT(elm, field) && \
750 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
751 elm = RB_PARENT(elm, field); \
752 elm = RB_PARENT(elm, field); \
758 #define RB_GENERATE_MINMAX(name, type, field, attr) \ argument
767 tmp = RB_LEFT(tmp, field); \
769 tmp = RB_RIGHT(tmp, field); \
774 #define RB_GENERATE_REINSERT(name, type, field, cmp, attr) \ argument