Lines Matching refs:elm
75 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
76 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
120 /* Finds the node with the same key as elm */ \
122 name##_SPLAY_FIND(struct name *head, struct type *elm) \
126 name##_SPLAY(head, elm); \
127 if ((cmp)(elm, (head)->sph_root) == 0) \
133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
135 name##_SPLAY(head, elm); \
136 if (SPLAY_RIGHT(elm, field) != NULL) { \
137 elm = SPLAY_RIGHT(elm, field); \
138 while (SPLAY_LEFT(elm, field) != NULL) { \
139 elm = SPLAY_LEFT(elm, field); \
142 elm = NULL; \
143 return (elm); \
154 * Moves node close to the key of elm to top
158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
161 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
164 name##_SPLAY(head, elm); \
165 __comp = (cmp)(elm, (head)->sph_root); \
167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172 SPLAY_LEFT(elm, field) = (head)->sph_root; \
177 (head)->sph_root = (elm); \
182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
187 name##_SPLAY(head, elm); \
188 if ((cmp)(elm, (head)->sph_root) == 0) { \
194 name##_SPLAY(head, elm); \
197 return (elm); \
203 name##_SPLAY(struct name *head, struct type *elm) \
211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
216 if ((cmp)(elm, __tmp) < 0){ \
226 if ((cmp)(elm, __tmp) > 0){ \
313 #define RB_LEFT(elm, field) (elm)->field.rbe_left
314 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
315 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
316 #define RB_COLOR(elm, field) (elm)->field.rbe_color
320 #define RB_SET(elm, parent, field) do { \
321 RB_PARENT(elm, field) = parent; \
322 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
323 RB_COLOR(elm, field) = RB_RED; \
335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
336 (tmp) = RB_RIGHT(elm, field); \
337 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
338 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
340 RB_AUGMENT(elm); \
341 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
342 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
343 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
345 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
348 RB_LEFT(tmp, field) = (elm); \
349 RB_PARENT(elm, field) = (tmp); \
355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
356 (tmp) = RB_LEFT(elm, field); \
357 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
358 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
360 RB_AUGMENT(elm); \
361 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
362 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
363 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
365 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
368 RB_RIGHT(tmp, field) = (elm); \
369 RB_PARENT(elm, field) = (tmp); \
387 * Moves node close to the key of elm to top
391 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
394 while ((parent = RB_PARENT(elm, field)) && \
402 elm = gparent; \
405 if (RB_RIGHT(parent, field) == elm) { \
408 parent = elm; \
409 elm = tmp; \
418 elm = gparent; \
421 if (RB_LEFT(parent, field) == elm) { \
424 parent = elm; \
425 elm = tmp; \
435 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
438 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
439 elm != RB_ROOT(head)) { \
440 if (RB_LEFT(parent, field) == elm) { \
452 elm = parent; \
453 parent = RB_PARENT(elm, field); \
469 elm = RB_ROOT(head); \
484 elm = parent; \
485 parent = RB_PARENT(elm, field); \
501 elm = RB_ROOT(head); \
506 if (elm) \
507 RB_COLOR(elm, field) = RB_BLACK; \
511 name##_RB_REMOVE(struct name *head, struct type *elm) \
513 struct type *child, *parent, *old = elm; \
515 if (RB_LEFT(elm, field) == NULL) \
516 child = RB_RIGHT(elm, field); \
517 else if (RB_RIGHT(elm, field) == NULL) \
518 child = RB_LEFT(elm, field); \
521 elm = RB_RIGHT(elm, field); \
522 while ((left = RB_LEFT(elm, field))) \
523 elm = left; \
524 child = RB_RIGHT(elm, field); \
525 parent = RB_PARENT(elm, field); \
526 color = RB_COLOR(elm, field); \
530 if (RB_LEFT(parent, field) == elm) \
537 if (RB_PARENT(elm, field) == old) \
538 parent = elm; \
539 (elm)->field = (old)->field; \
542 RB_LEFT(RB_PARENT(old, field), field) = elm;\
544 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
547 RB_ROOT(head) = elm; \
548 RB_PARENT(RB_LEFT(old, field), field) = elm; \
550 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
559 parent = RB_PARENT(elm, field); \
560 color = RB_COLOR(elm, field); \
564 if (RB_LEFT(parent, field) == elm) \
579 name##_RB_INSERT(struct name *head, struct type *elm) \
587 comp = (cmp)(elm, parent); \
595 RB_SET(elm, parent, field); \
598 RB_LEFT(parent, field) = elm; \
600 RB_RIGHT(parent, field) = elm; \
603 RB_ROOT(head) = elm; \
604 name##_RB_INSERT_COLOR(head, elm); \
608 /* Finds the node with the same key as elm */ \
610 name##_RB_FIND(struct name *head, struct type *elm) \
615 comp = cmp(elm, tmp); \
627 name##_RB_NEXT(struct type *elm) \
629 if (RB_RIGHT(elm, field)) { \
630 elm = RB_RIGHT(elm, field); \
631 while (RB_LEFT(elm, field)) \
632 elm = RB_LEFT(elm, field); \
634 if (RB_PARENT(elm, field) && \
635 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
636 elm = RB_PARENT(elm, field); \
638 while (RB_PARENT(elm, field) && \
639 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
640 elm = RB_PARENT(elm, field); \
641 elm = RB_PARENT(elm, field); \
644 return (elm); \