Lines Matching refs:field
86 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
87 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
92 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
93 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
94 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
98 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
99 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
100 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
104 #define SPLAY_LINKLEFT(head, tmp, field) do { \
105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
107 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
110 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
111 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
113 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
116 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
117 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
118 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
119 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
120 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
125 #define SPLAY_PROTOTYPE(name, type, field, cmp) \
147 if (SPLAY_RIGHT(elm, field) != NULL) { \
148 elm = SPLAY_RIGHT(elm, field); \
149 while (SPLAY_LEFT(elm, field) != NULL) { \
150 elm = SPLAY_LEFT(elm, field); \
167 #define SPLAY_GENERATE(name, type, field, cmp) \
172 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
178 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
179 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
180 SPLAY_LEFT((head)->sph_root, field) = NULL; \
182 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
183 SPLAY_LEFT(elm, field) = (head)->sph_root; \
184 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
200 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
201 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
203 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
204 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
206 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
219 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
224 __tmp = SPLAY_LEFT((head)->sph_root, field); \
228 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
229 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
232 SPLAY_LINKLEFT(head, __right, field); \
234 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
238 SPLAY_ROTATE_LEFT(head, __tmp, field); \
239 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
242 SPLAY_LINKRIGHT(head, __left, field); \
245 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
255 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
260 __tmp = SPLAY_LEFT((head)->sph_root, field); \
264 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
265 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
268 SPLAY_LINKLEFT(head, __right, field); \
270 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
274 SPLAY_ROTATE_LEFT(head, __tmp, field); \
275 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
278 SPLAY_LINKRIGHT(head, __left, field); \
281 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
324 #define RB_LEFT(elm, field) (elm)->field.rbe_left
325 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
326 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
327 #define RB_COLOR(elm, field) (elm)->field.rbe_color
331 #define RB_SET(elm, parent, field) do { \
332 RB_PARENT(elm, field) = parent; \
333 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
334 RB_COLOR(elm, field) = RB_RED; \
337 #define RB_SET_BLACKRED(black, red, field) do { \
338 RB_COLOR(black, field) = RB_BLACK; \
339 RB_COLOR(red, field) = RB_RED; \
346 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
347 (tmp) = RB_RIGHT(elm, field); \
348 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
349 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
352 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
353 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
354 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
356 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
359 RB_LEFT(tmp, field) = (elm); \
360 RB_PARENT(elm, field) = (tmp); \
362 if ((RB_PARENT(tmp, field))) \
363 RB_AUGMENT(RB_PARENT(tmp, field)); \
366 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
367 (tmp) = RB_LEFT(elm, field); \
368 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
369 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
372 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
373 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
374 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
376 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
379 RB_RIGHT(tmp, field) = (elm); \
380 RB_PARENT(elm, field) = (tmp); \
382 if ((RB_PARENT(tmp, field))) \
383 RB_AUGMENT(RB_PARENT(tmp, field)); \
387 #define RB_PROTOTYPE(name, type, field, cmp) \
388 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
389 #define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
390 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
391 #define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
406 #define RB_GENERATE(name, type, field, cmp) \
407 RB_GENERATE_INTERNAL(name, type, field, cmp,)
408 #define RB_GENERATE_STATIC(name, type, field, cmp) \
409 RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
410 #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
415 while ((parent = RB_PARENT(elm, field)) != NULL && \
416 RB_COLOR(parent, field) == RB_RED) { \
417 gparent = RB_PARENT(parent, field); \
418 if (parent == RB_LEFT(gparent, field)) { \
419 tmp = RB_RIGHT(gparent, field); \
420 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
421 RB_COLOR(tmp, field) = RB_BLACK; \
422 RB_SET_BLACKRED(parent, gparent, field);\
426 if (RB_RIGHT(parent, field) == elm) { \
427 RB_ROTATE_LEFT(head, parent, tmp, field);\
432 RB_SET_BLACKRED(parent, gparent, field); \
433 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
435 tmp = RB_LEFT(gparent, field); \
436 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
437 RB_COLOR(tmp, field) = RB_BLACK; \
438 RB_SET_BLACKRED(parent, gparent, field);\
442 if (RB_LEFT(parent, field) == elm) { \
443 RB_ROTATE_RIGHT(head, parent, tmp, field);\
448 RB_SET_BLACKRED(parent, gparent, field); \
449 RB_ROTATE_LEFT(head, gparent, tmp, field); \
452 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
459 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
461 if (RB_LEFT(parent, field) == elm) { \
462 tmp = RB_RIGHT(parent, field); \
463 if (RB_COLOR(tmp, field) == RB_RED) { \
464 RB_SET_BLACKRED(tmp, parent, field); \
465 RB_ROTATE_LEFT(head, parent, tmp, field);\
466 tmp = RB_RIGHT(parent, field); \
468 if ((RB_LEFT(tmp, field) == NULL || \
469 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
470 (RB_RIGHT(tmp, field) == NULL || \
471 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
472 RB_COLOR(tmp, field) = RB_RED; \
474 parent = RB_PARENT(elm, field); \
476 if (RB_RIGHT(tmp, field) == NULL || \
477 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
479 if ((oleft = RB_LEFT(tmp, field)) \
481 RB_COLOR(oleft, field) = RB_BLACK;\
482 RB_COLOR(tmp, field) = RB_RED; \
483 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
484 tmp = RB_RIGHT(parent, field); \
486 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
487 RB_COLOR(parent, field) = RB_BLACK; \
488 if (RB_RIGHT(tmp, field)) \
489 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
490 RB_ROTATE_LEFT(head, parent, tmp, field);\
495 tmp = RB_LEFT(parent, field); \
496 if (RB_COLOR(tmp, field) == RB_RED) { \
497 RB_SET_BLACKRED(tmp, parent, field); \
498 RB_ROTATE_RIGHT(head, parent, tmp, field);\
499 tmp = RB_LEFT(parent, field); \
501 if ((RB_LEFT(tmp, field) == NULL || \
502 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
503 (RB_RIGHT(tmp, field) == NULL || \
504 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
505 RB_COLOR(tmp, field) = RB_RED; \
507 parent = RB_PARENT(elm, field); \
509 if (RB_LEFT(tmp, field) == NULL || \
510 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
512 if ((oright = RB_RIGHT(tmp, field)) \
514 RB_COLOR(oright, field) = RB_BLACK;\
515 RB_COLOR(tmp, field) = RB_RED; \
516 RB_ROTATE_LEFT(head, tmp, oright, field);\
517 tmp = RB_LEFT(parent, field); \
519 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
520 RB_COLOR(parent, field) = RB_BLACK; \
521 if (RB_LEFT(tmp, field)) \
522 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
523 RB_ROTATE_RIGHT(head, parent, tmp, field);\
530 RB_COLOR(elm, field) = RB_BLACK; \
538 if (RB_LEFT(elm, field) == NULL) \
539 child = RB_RIGHT(elm, field); \
540 else if (RB_RIGHT(elm, field) == NULL) \
541 child = RB_LEFT(elm, field); \
544 elm = RB_RIGHT(elm, field); \
545 while ((left = RB_LEFT(elm, field)) != NULL) \
547 child = RB_RIGHT(elm, field); \
548 parent = RB_PARENT(elm, field); \
549 color = RB_COLOR(elm, field); \
551 RB_PARENT(child, field) = parent; \
553 if (RB_LEFT(parent, field) == elm) \
554 RB_LEFT(parent, field) = child; \
556 RB_RIGHT(parent, field) = child; \
560 if (RB_PARENT(elm, field) == old) \
562 (elm)->field = (old)->field; \
563 if (RB_PARENT(old, field)) { \
564 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
565 RB_LEFT(RB_PARENT(old, field), field) = elm;\
567 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
568 RB_AUGMENT(RB_PARENT(old, field)); \
571 RB_PARENT(RB_LEFT(old, field), field) = elm; \
572 if (RB_RIGHT(old, field)) \
573 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
578 } while ((left = RB_PARENT(left, field)) != NULL); \
582 parent = RB_PARENT(elm, field); \
583 color = RB_COLOR(elm, field); \
585 RB_PARENT(child, field) = parent; \
587 if (RB_LEFT(parent, field) == elm) \
588 RB_LEFT(parent, field) = child; \
590 RB_RIGHT(parent, field) = child; \
612 tmp = RB_LEFT(tmp, field); \
614 tmp = RB_RIGHT(tmp, field); \
618 RB_SET(elm, parent, field); \
621 RB_LEFT(parent, field) = elm; \
623 RB_RIGHT(parent, field) = elm; \
640 tmp = RB_LEFT(tmp, field); \
642 tmp = RB_RIGHT(tmp, field); \
660 tmp = RB_LEFT(tmp, field); \
663 tmp = RB_RIGHT(tmp, field); \
674 if (RB_RIGHT(elm, field)) { \
675 elm = RB_RIGHT(elm, field); \
676 while (RB_LEFT(elm, field)) \
677 elm = RB_LEFT(elm, field); \
679 if (RB_PARENT(elm, field) && \
680 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
681 elm = RB_PARENT(elm, field); \
683 while (RB_PARENT(elm, field) && \
684 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
685 elm = RB_PARENT(elm, field); \
686 elm = RB_PARENT(elm, field); \
696 if (RB_LEFT(elm, field)) { \
697 elm = RB_LEFT(elm, field); \
698 while (RB_RIGHT(elm, field)) \
699 elm = RB_RIGHT(elm, field); \
701 if (RB_PARENT(elm, field) && \
702 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
703 elm = RB_PARENT(elm, field); \
705 while (RB_PARENT(elm, field) && \
706 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
707 elm = RB_PARENT(elm, field); \
708 elm = RB_PARENT(elm, field); \
722 tmp = RB_LEFT(tmp, field); \
724 tmp = RB_RIGHT(tmp, field); \