Lines Matching refs:head
81 #define SPLAY_ROOT(head) (head)->sph_root argument
82 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) argument
85 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
86 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
87 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
88 (head)->sph_root = tmp; \
91 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
92 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
93 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
94 (head)->sph_root = tmp; \
97 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
98 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
99 tmp = (head)->sph_root; \
100 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
103 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
104 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
105 tmp = (head)->sph_root; \
106 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
109 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
110 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
111 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
112 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
113 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
126 name##_SPLAY_FIND(struct name *head, struct type *elm) \
128 if (SPLAY_EMPTY(head)) \
130 name##_SPLAY(head, elm); \
131 if ((cmp)(elm, (head)->sph_root) == 0) \
132 return (head->sph_root); \
137 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
139 name##_SPLAY(head, elm); \
151 name##_SPLAY_MIN_MAX(struct name *head, int val) \
153 name##_SPLAY_MINMAX(head, val); \
154 return (SPLAY_ROOT(head)); \
162 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
164 if (SPLAY_EMPTY(head)) { \
168 name##_SPLAY(head, elm); \
169 __comp = (cmp)(elm, (head)->sph_root); \
171 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
172 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
173 SPLAY_LEFT((head)->sph_root, field) = NULL; \
175 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
176 SPLAY_LEFT(elm, field) = (head)->sph_root; \
177 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
179 return ((head)->sph_root); \
181 (head)->sph_root = (elm); \
186 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
189 if (SPLAY_EMPTY(head)) \
191 name##_SPLAY(head, elm); \
192 if ((cmp)(elm, (head)->sph_root) == 0) { \
193 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
194 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
196 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
197 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
198 name##_SPLAY(head, elm); \
199 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
207 name##_SPLAY(struct name *head, struct type *elm) \
215 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
217 __tmp = SPLAY_LEFT((head)->sph_root, field); \
221 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
222 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
225 SPLAY_LINKLEFT(head, __right, field); \
227 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
231 SPLAY_ROTATE_LEFT(head, __tmp, field); \
232 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
235 SPLAY_LINKRIGHT(head, __left, field); \
238 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
244 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
253 __tmp = SPLAY_LEFT((head)->sph_root, field); \
257 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
258 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
261 SPLAY_LINKLEFT(head, __right, field); \
263 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
267 SPLAY_ROTATE_LEFT(head, __tmp, field); \
268 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
271 SPLAY_LINKRIGHT(head, __left, field); \
274 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
289 #define SPLAY_FOREACH(x, name, head) \ argument
290 for ((x) = SPLAY_MIN(name, head); \
292 (x) = SPLAY_NEXT(name, head, x))
321 #define RB_ROOT(head) (head)->rbh_root argument
322 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) argument
339 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
352 (head)->rbh_root = (tmp); \
358 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
371 (head)->rbh_root = (tmp); \
392 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
407 RB_ROTATE_LEFT(head, parent, tmp, field);\
413 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
423 RB_ROTATE_RIGHT(head, parent, tmp, field);\
429 RB_ROTATE_LEFT(head, gparent, tmp, field); \
432 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
436 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
440 elm != RB_ROOT(head)) { \
445 RB_ROTATE_LEFT(head, parent, tmp, field);\
462 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
469 RB_ROTATE_LEFT(head, parent, tmp, field);\
470 elm = RB_ROOT(head); \
477 RB_ROTATE_RIGHT(head, parent, tmp, field);\
494 RB_ROTATE_LEFT(head, tmp, oright, field);\
501 RB_ROTATE_RIGHT(head, parent, tmp, field);\
502 elm = RB_ROOT(head); \
512 name##_RB_REMOVE(struct name *head, struct type *elm) \
537 RB_ROOT(head) = child; \
548 RB_ROOT(head) = elm; \
571 RB_ROOT(head) = child; \
574 name##_RB_REMOVE_COLOR(head, parent, child); \
580 name##_RB_INSERT(struct name *head, struct type *elm) \
585 tmp = RB_ROOT(head); \
604 RB_ROOT(head) = elm; \
605 name##_RB_INSERT_COLOR(head, elm); \
611 name##_RB_FIND(struct name *head, struct type *elm) \
613 struct type *tmp = RB_ROOT(head); \
628 name##_RB_NEXT(struct name *head, struct type *elm) \
649 name##_RB_MINMAX(struct name *head, int val) \
651 struct type *tmp = RB_ROOT(head); \
673 #define RB_FOREACH(x, name, head) \ argument
674 for ((x) = RB_MIN(name, head); \
676 (x) = name##_RB_NEXT(head, x))