Lines Matching refs:field
78 #define SPLAY_LEFT(elm, field) ((elm)->field.spe_left) argument
79 #define SPLAY_RIGHT(elm, field) ((elm)->field.spe_right) argument
84 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
85 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
86 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
90 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
91 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
92 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
96 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
97 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
99 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
102 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
103 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
105 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
108 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
109 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
110 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
111 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
112 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
117 #define SPLAY_PROTOTYPE(name, type, field, cmp) \ argument
139 if (SPLAY_RIGHT(elm, field) != NULL) { \
140 elm = SPLAY_RIGHT(elm, field); \
141 while (SPLAY_LEFT(elm, field) != NULL) { \
142 elm = SPLAY_LEFT(elm, field); \
159 #define SPLAY_GENERATE(name, type, field, cmp) \ argument
164 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;\
170 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root,\
171 field) \
172 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
173 SPLAY_LEFT((head)->sph_root, field) = NULL; \
175 SPLAY_RIGHT(elm, field) = \
176 SPLAY_RIGHT((head)->sph_root, field); \
177 SPLAY_LEFT(elm, field) = (head)->sph_root; \
178 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
194 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
196 field); \
198 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
199 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
201 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
214 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
219 __tmp = SPLAY_LEFT((head)->sph_root, field); \
223 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
224 if (SPLAY_LEFT((head)->sph_root, field) \
228 SPLAY_LINKLEFT(head, __right, field); \
230 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
234 SPLAY_ROTATE_LEFT(head, __tmp, field); \
235 if (SPLAY_RIGHT((head)->sph_root, field)\
239 SPLAY_LINKRIGHT(head, __left, field); \
242 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
252 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
257 __tmp = SPLAY_LEFT((head)->sph_root, field); \
261 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
262 if (SPLAY_LEFT((head)->sph_root, field) \
266 SPLAY_LINKLEFT(head, __right, field); \
268 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
272 SPLAY_ROTATE_LEFT(head, __tmp, field); \
273 if (SPLAY_RIGHT((head)->sph_root, field)\
277 SPLAY_LINKRIGHT(head, __left, field); \
280 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
320 #define RB_LEFT(elm, field) ((elm)->field.rbe_left) argument
321 #define RB_RIGHT(elm, field) ((elm)->field.rbe_right) argument
322 #define RB_PARENT(elm, field) ((elm)->field.rbe_parent) argument
323 #define RB_COLOR(elm, field) ((elm)->field.rbe_color) argument
327 #define RB_SET(elm, parent, field) do { \ argument
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 { \ argument
334 RB_COLOR(black, field) = RB_BLACK; \
335 RB_COLOR(red, field) = RB_RED; \
342 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
343 (tmp) = RB_RIGHT(elm, field); \
344 RB_RIGHT(elm, field) = RB_LEFT(tmp, field); \
345 if (RB_RIGHT(elm, field) != NULL) \
346 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
348 RB_PARENT(tmp, field) = RB_PARENT(elm, field); \
349 if (RB_PARENT(tmp, field) != NULL) { \
350 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
351 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
353 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
356 RB_LEFT(tmp, field) = (elm); \
357 RB_PARENT(elm, field) = (tmp); \
359 if ((RB_PARENT(tmp, field))) \
360 RB_AUGMENT(RB_PARENT(tmp, field)); \
363 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
364 (tmp) = RB_LEFT(elm, field); \
365 RB_LEFT(elm, field) = RB_RIGHT(tmp, field); \
366 if (RB_LEFT(elm, field) != NULL) \
367 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
369 RB_PARENT(tmp, field) = RB_PARENT(elm, field); \
370 if (RB_PARENT(tmp, field) != NULL) { \
371 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
372 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
374 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
377 RB_RIGHT(tmp, field) = (elm); \
378 RB_PARENT(elm, field) = (tmp); \
380 if ((RB_PARENT(tmp, field))) \
381 RB_AUGMENT(RB_PARENT(tmp, field)); \
385 #define RB_PROTOTYPE(name, type, field, cmp) \ argument
386 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
387 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ argument
388 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, static)
389 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ argument
422 #define RB_GENERATE(name, type, field, cmp) \ argument
423 RB_GENERATE_INTERNAL(name, type, field, cmp,)
424 #define RB_GENERATE_STATIC(name, type, field, cmp) \ argument
425 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((unused)) static)
426 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ argument
427 RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
428 RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
429 RB_GENERATE_INSERT(name, type, field, cmp, attr) \
430 RB_GENERATE_REMOVE(name, type, field, attr) \
431 RB_GENERATE_FIND(name, type, field, cmp, attr) \
432 RB_GENERATE_NFIND(name, type, field, cmp, attr) \
433 RB_GENERATE_NEXT(name, type, field, attr) \
434 RB_GENERATE_PREV(name, type, field, attr) \
435 RB_GENERATE_MINMAX(name, type, field, attr)
437 #define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \ argument
442 while ((parent = RB_PARENT(elm, field)) != NULL && \
443 RB_COLOR(parent, field) == RB_RED) { \
444 gparent = RB_PARENT(parent, field); \
445 if (parent == RB_LEFT(gparent, field)) { \
446 tmp = RB_RIGHT(gparent, field); \
447 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
448 RB_COLOR(tmp, field) = RB_BLACK; \
449 RB_SET_BLACKRED(parent, gparent, field);\
453 if (RB_RIGHT(parent, field) == elm) { \
454 RB_ROTATE_LEFT(head, parent, tmp, field);\
459 RB_SET_BLACKRED(parent, gparent, field); \
460 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
462 tmp = RB_LEFT(gparent, field); \
463 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
464 RB_COLOR(tmp, field) = RB_BLACK; \
465 RB_SET_BLACKRED(parent, gparent, field);\
469 if (RB_LEFT(parent, field) == elm) { \
470 RB_ROTATE_RIGHT(head, parent, tmp, field);\
475 RB_SET_BLACKRED(parent, gparent, field); \
476 RB_ROTATE_LEFT(head, gparent, tmp, field); \
479 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
482 #define RB_GENERATE_REMOVE_COLOR(name, type, field, attr) \ argument
488 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
490 if (RB_LEFT(parent, field) == elm) { \
491 tmp = RB_RIGHT(parent, field); \
492 if (RB_COLOR(tmp, field) == RB_RED) { \
493 RB_SET_BLACKRED(tmp, parent, field); \
494 RB_ROTATE_LEFT(head, parent, tmp, field);\
495 tmp = RB_RIGHT(parent, field); \
497 if ((RB_LEFT(tmp, field) == NULL || \
498 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) \
499 && (RB_RIGHT(tmp, field) == NULL || \
500 RB_COLOR(RB_RIGHT(tmp, field), field) \
502 RB_COLOR(tmp, field) = RB_RED; \
504 parent = RB_PARENT(elm, field); \
506 if (RB_RIGHT(tmp, field) == NULL || \
507 RB_COLOR(RB_RIGHT(tmp, field), field) \
510 oleft = RB_LEFT(tmp, field); \
512 RB_COLOR(oleft, field) = \
514 RB_COLOR(tmp, field) = RB_RED; \
516 field); \
517 tmp = RB_RIGHT(parent, field); \
519 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
520 RB_COLOR(parent, field) = RB_BLACK; \
521 if (RB_RIGHT(tmp, field)) \
522 RB_COLOR(RB_RIGHT(tmp, field), field) \
524 RB_ROTATE_LEFT(head, parent, tmp, field);\
529 tmp = RB_LEFT(parent, field); \
530 if (RB_COLOR(tmp, field) == RB_RED) { \
531 RB_SET_BLACKRED(tmp, parent, field); \
532 RB_ROTATE_RIGHT(head, parent, tmp, field);\
533 tmp = RB_LEFT(parent, field); \
535 if ((RB_LEFT(tmp, field) == NULL || \
536 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) \
537 && (RB_RIGHT(tmp, field) == NULL || \
538 RB_COLOR(RB_RIGHT(tmp, field), field) == \
540 RB_COLOR(tmp, field) = RB_RED; \
542 parent = RB_PARENT(elm, field); \
544 if (RB_LEFT(tmp, field) == NULL || \
545 RB_COLOR(RB_LEFT(tmp, field), field) \
548 oright = RB_RIGHT(tmp, field); \
550 RB_COLOR(oright, field) \
552 RB_COLOR(tmp, field) = RB_RED; \
554 field); \
555 tmp = RB_LEFT(parent, field); \
557 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
558 RB_COLOR(parent, field) = RB_BLACK; \
559 if (RB_LEFT(tmp, field)) \
560 RB_COLOR(RB_LEFT(tmp, field), field) \
562 RB_ROTATE_RIGHT(head, parent, tmp, field);\
569 RB_COLOR(elm, field) = RB_BLACK; \
572 #define RB_GENERATE_REMOVE(name, type, field, attr) \ argument
578 if (RB_LEFT(elm, field) == NULL) \
579 child = RB_RIGHT(elm, field); \
580 else if (RB_RIGHT(elm, field) == NULL) \
581 child = RB_LEFT(elm, field); \
584 elm = RB_RIGHT(elm, field); \
585 while ((left = RB_LEFT(elm, field)) != NULL) \
587 child = RB_RIGHT(elm, field); \
588 parent = RB_PARENT(elm, field); \
589 color = RB_COLOR(elm, field); \
591 RB_PARENT(child, field) = parent; \
593 if (RB_LEFT(parent, field) == elm) \
594 RB_LEFT(parent, field) = child; \
596 RB_RIGHT(parent, field) = child; \
600 if (RB_PARENT(elm, field) == old) \
602 (elm)->field = (old)->field; \
603 if (RB_PARENT(old, field)) { \
604 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
605 RB_LEFT(RB_PARENT(old, field), field) = elm;\
607 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
608 RB_AUGMENT(RB_PARENT(old, field)); \
611 RB_PARENT(RB_LEFT(old, field), field) = elm; \
612 if (RB_RIGHT(old, field)) \
613 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
618 } while ((left = RB_PARENT(left, field)) != NULL); \
622 parent = RB_PARENT(elm, field); \
623 color = RB_COLOR(elm, field); \
625 RB_PARENT(child, field) = parent; \
627 if (RB_LEFT(parent, field) == elm) \
628 RB_LEFT(parent, field) = child; \
630 RB_RIGHT(parent, field) = child; \
640 #define RB_GENERATE_INSERT(name, type, field, cmp, attr) \ argument
653 tmp = RB_LEFT(tmp, field); \
655 tmp = RB_RIGHT(tmp, field); \
659 RB_SET(elm, parent, field); \
662 RB_LEFT(parent, field) = elm; \
664 RB_RIGHT(parent, field) = elm; \
672 #define RB_GENERATE_FIND(name, type, field, cmp, attr) \ argument
682 tmp = RB_LEFT(tmp, field); \
684 tmp = RB_RIGHT(tmp, field); \
691 #define RB_GENERATE_NFIND(name, type, field, cmp, attr) \ argument
703 tmp = RB_LEFT(tmp, field); \
706 tmp = RB_RIGHT(tmp, field); \
713 #define RB_GENERATE_NEXT(name, type, field, attr) \ argument
718 if (RB_RIGHT(elm, field)) { \
719 elm = RB_RIGHT(elm, field); \
720 while (RB_LEFT(elm, field)) \
721 elm = RB_LEFT(elm, field); \
723 if (RB_PARENT(elm, field) && \
724 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
725 elm = RB_PARENT(elm, field); \
727 while (RB_PARENT(elm, field) && \
728 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
729 elm = RB_PARENT(elm, field); \
730 elm = RB_PARENT(elm, field); \
736 #define RB_GENERATE_PREV(name, type, field, attr) \ argument
741 if (RB_LEFT(elm, field)) { \
742 elm = RB_LEFT(elm, field); \
743 while (RB_RIGHT(elm, field)) \
744 elm = RB_RIGHT(elm, field); \
746 if (RB_PARENT(elm, field) && \
747 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
748 elm = RB_PARENT(elm, field); \
750 while (RB_PARENT(elm, field) && \
751 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
752 elm = RB_PARENT(elm, field); \
753 elm = RB_PARENT(elm, field); \
759 #define RB_GENERATE_MINMAX(name, type, field, attr) \ argument
768 tmp = RB_LEFT(tmp, field); \
770 tmp = RB_RIGHT(tmp, field); \