Lines Matching refs:head
84 #define SPLAY_ROOT(head) (head)->sph_root argument
85 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) argument
88 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
89 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
90 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
91 (head)->sph_root = tmp; \
94 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
95 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97 (head)->sph_root = tmp; \
100 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
101 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
102 tmp = (head)->sph_root; \
103 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
106 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
107 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
108 tmp = (head)->sph_root; \
109 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
112 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
113 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
114 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field); \
115 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
116 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
129 name##_SPLAY_FIND(struct name *head, struct type *elm) \
131 if (SPLAY_EMPTY(head)) \
133 name##_SPLAY(head, elm); \
134 if ((cmp)(elm, (head)->sph_root) == 0) \
135 return (head->sph_root); \
140 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
142 name##_SPLAY(head, elm); \
154 name##_SPLAY_MIN_MAX(struct name *head, int val) \
156 name##_SPLAY_MINMAX(head, val); \
157 return (SPLAY_ROOT(head)); \
165 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
167 if (SPLAY_EMPTY(head)) { \
171 name##_SPLAY(head, elm); \
172 __comp = (cmp)(elm, (head)->sph_root); \
174 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field); \
175 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
176 SPLAY_LEFT((head)->sph_root, field) = NULL; \
178 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field); \
179 SPLAY_LEFT(elm, field) = (head)->sph_root; \
180 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
182 return ((head)->sph_root); \
184 (head)->sph_root = (elm); \
189 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
192 if (SPLAY_EMPTY(head)) \
194 name##_SPLAY(head, elm); \
195 if ((cmp)(elm, (head)->sph_root) == 0) { \
196 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
197 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
199 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
200 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
201 name##_SPLAY(head, elm); \
202 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
210 name##_SPLAY(struct name *head, struct type *elm) \
218 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
220 __tmp = SPLAY_LEFT((head)->sph_root, field); \
224 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
225 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
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) == NULL) \
238 SPLAY_LINKRIGHT(head, __left, field); \
241 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
247 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
256 __tmp = SPLAY_LEFT((head)->sph_root, field); \
260 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
261 if (SPLAY_LEFT((head)->sph_root, field) == NULL) \
264 SPLAY_LINKLEFT(head, __right, field); \
266 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
270 SPLAY_ROTATE_LEFT(head, __tmp, field); \
271 if (SPLAY_RIGHT((head)->sph_root, field) == NULL) \
274 SPLAY_LINKRIGHT(head, __left, field); \
277 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
292 #define SPLAY_FOREACH(x, name, head) \ argument
293 for ((x) = SPLAY_MIN(name, head); \
295 (x) = SPLAY_NEXT(name, head, x))
324 #define RB_ROOT(head) (head)->rbh_root argument
325 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) argument
342 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
354 (head)->rbh_root = (tmp); \
362 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
374 (head)->rbh_root = (tmp); \
408 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
423 RB_ROTATE_LEFT(head, parent, tmp, field); \
429 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
439 RB_ROTATE_RIGHT(head, parent, tmp, field); \
445 RB_ROTATE_LEFT(head, gparent, tmp, field); \
448 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
452 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, \
457 elm != RB_ROOT(head)) { \
462 RB_ROTATE_LEFT(head, parent, tmp, field); \
480 RB_ROTATE_RIGHT(head, tmp, oleft, field); \
487 RB_ROTATE_LEFT(head, parent, tmp, field); \
488 elm = RB_ROOT(head); \
495 RB_ROTATE_RIGHT(head, parent, tmp, field); \
513 RB_ROTATE_LEFT(head, tmp, oright, field); \
520 RB_ROTATE_RIGHT(head, parent, tmp, field); \
521 elm = RB_ROOT(head); \
531 name##_RB_REMOVE(struct name *head, struct type *elm) \
556 RB_ROOT(head) = child; \
567 RB_ROOT(head) = elm; \
590 RB_ROOT(head) = child; \
593 name##_RB_REMOVE_COLOR(head, parent, child); \
599 name##_RB_INSERT(struct name *head, struct type *elm) \
604 tmp = RB_ROOT(head); \
623 RB_ROOT(head) = elm; \
624 name##_RB_INSERT_COLOR(head, elm); \
630 name##_RB_FIND(struct name *head, struct type *elm) \
632 struct type *tmp = RB_ROOT(head); \
648 name##_RB_NFIND(struct name *head, struct type *elm) \
650 struct type *tmp = RB_ROOT(head); \
712 name##_RB_MINMAX(struct name *head, int val) \
714 struct type *tmp = RB_ROOT(head); \
738 #define RB_FOREACH(x, name, head) \ argument
739 for ((x) = RB_MIN(name, head); \
748 #define RB_FOREACH_SAFE(x, name, head, y) \ argument
749 for ((x) = RB_MIN(name, head); \
753 #define RB_FOREACH_REVERSE(x, name, head) \ argument
754 for ((x) = RB_MAX(name, head); \
763 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ argument
764 for ((x) = RB_MAX(name, head); \