Lines Matching refs:elm
78 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
79 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
123 /* Finds the node with the same key as elm */ \
125 name##_SPLAY_FIND(struct name *head, struct type *elm) \
129 name##_SPLAY(head, elm); \
130 if ((cmp)(elm, (head)->sph_root) == 0) \
136 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
138 name##_SPLAY(head, elm); \
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); \
145 elm = NULL; \
146 return (elm); \
157 * Moves node close to the key of elm to top
161 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
164 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
167 name##_SPLAY(head, elm); \
168 __comp = (cmp)(elm, (head)->sph_root); \
170 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
171 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
174 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
175 SPLAY_LEFT(elm, field) = (head)->sph_root; \
180 (head)->sph_root = (elm); \
185 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
190 name##_SPLAY(head, elm); \
191 if ((cmp)(elm, (head)->sph_root) == 0) { \
197 name##_SPLAY(head, elm); \
200 return (elm); \
206 name##_SPLAY(struct name *head, struct type *elm) \
214 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
219 if ((cmp)(elm, __tmp) < 0){ \
229 if ((cmp)(elm, __tmp) > 0){ \
323 #define RB_LEFT(elm, field) (elm)->field.rbe_left
324 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
325 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
326 #define RB_COLOR(elm, field) (elm)->field.rbe_color
330 #define RB_SET(elm, parent, field) do { \
331 RB_PARENT(elm, field) = parent; \
332 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
333 RB_COLOR(elm, field) = RB_RED; \
345 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
346 (tmp) = RB_RIGHT(elm, field); \
347 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field)) != NULL) { \
348 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
350 RB_AUGMENT(elm); \
351 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
352 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
353 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
355 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
358 RB_LEFT(tmp, field) = (elm); \
359 RB_PARENT(elm, field) = (tmp); \
365 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
366 (tmp) = RB_LEFT(elm, field); \
367 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field)) != NULL) { \
368 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
370 RB_AUGMENT(elm); \
371 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field)) != NULL) { \
372 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
373 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
375 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
378 RB_RIGHT(tmp, field) = (elm); \
379 RB_PARENT(elm, field) = (tmp); \
403 * Moves node close to the key of elm to top
411 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
414 while ((parent = RB_PARENT(elm, field)) != NULL && \
422 elm = gparent; \
425 if (RB_RIGHT(parent, field) == elm) { \
428 parent = elm; \
429 elm = tmp; \
438 elm = gparent; \
441 if (RB_LEFT(parent, field) == elm) { \
444 parent = elm; \
445 elm = tmp; \
455 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
458 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
459 elm != RB_ROOT(head)) { \
460 if (RB_LEFT(parent, field) == elm) { \
472 elm = parent; \
473 parent = RB_PARENT(elm, field); \
490 elm = RB_ROOT(head); \
505 elm = parent; \
506 parent = RB_PARENT(elm, field); \
523 elm = RB_ROOT(head); \
528 if (elm) \
529 RB_COLOR(elm, field) = RB_BLACK; \
533 name##_RB_REMOVE(struct name *head, struct type *elm) \
535 struct type *child, *parent, *old = elm; \
537 if (RB_LEFT(elm, field) == NULL) \
538 child = RB_RIGHT(elm, field); \
539 else if (RB_RIGHT(elm, field) == NULL) \
540 child = RB_LEFT(elm, field); \
543 elm = RB_RIGHT(elm, field); \
544 while ((left = RB_LEFT(elm, field)) != NULL) \
545 elm = left; \
546 child = RB_RIGHT(elm, field); \
547 parent = RB_PARENT(elm, field); \
548 color = RB_COLOR(elm, field); \
552 if (RB_LEFT(parent, field) == elm) \
559 if (RB_PARENT(elm, field) == old) \
560 parent = elm; \
561 (elm)->field = (old)->field; \
564 RB_LEFT(RB_PARENT(old, field), field) = elm;\
566 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
569 RB_ROOT(head) = elm; \
570 RB_PARENT(RB_LEFT(old, field), field) = elm; \
572 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
581 parent = RB_PARENT(elm, field); \
582 color = RB_COLOR(elm, field); \
586 if (RB_LEFT(parent, field) == elm) \
601 name##_RB_INSERT(struct name *head, struct type *elm) \
609 comp = (cmp)(elm, parent); \
617 RB_SET(elm, parent, field); \
620 RB_LEFT(parent, field) = elm; \
622 RB_RIGHT(parent, field) = elm; \
625 RB_ROOT(head) = elm; \
626 name##_RB_INSERT_COLOR(head, elm); \
630 /* Finds the node with the same key as elm */ \
632 name##_RB_FIND(struct name *head, struct type *elm) \
637 comp = cmp(elm, tmp); \
650 name##_RB_NFIND(struct name *head, struct type *elm) \
656 comp = cmp(elm, tmp); \
671 name##_RB_NEXT(struct type *elm) \
673 if (RB_RIGHT(elm, field)) { \
674 elm = RB_RIGHT(elm, field); \
675 while (RB_LEFT(elm, field)) \
676 elm = RB_LEFT(elm, field); \
678 if (RB_PARENT(elm, field) && \
679 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
680 elm = RB_PARENT(elm, field); \
682 while (RB_PARENT(elm, field) && \
683 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
684 elm = RB_PARENT(elm, field); \
685 elm = RB_PARENT(elm, field); \
688 return (elm); \
693 name##_RB_PREV(struct type *elm) \
695 if (RB_LEFT(elm, field)) { \
696 elm = RB_LEFT(elm, field); \
697 while (RB_RIGHT(elm, field)) \
698 elm = RB_RIGHT(elm, field); \
700 if (RB_PARENT(elm, field) && \
701 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
702 elm = RB_PARENT(elm, field); \
704 while (RB_PARENT(elm, field) && \
705 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
706 elm = RB_PARENT(elm, field); \
707 elm = RB_PARENT(elm, field); \
710 return (elm); \
Indexes created Wed Mar 04 05:31:52 UTC 2026