Lines Matching refs:head
82 #define SPLAY_ROOT(head) (head)->sph_root argument
83 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) argument
86 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
87 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
88 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
89 (head)->sph_root = tmp; \
92 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
93 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
95 (head)->sph_root = tmp; \
98 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
99 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
100 tmp = (head)->sph_root; \
101 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
104 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
105 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
106 tmp = (head)->sph_root; \
107 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
110 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
111 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
112 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
113 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
114 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
127 name##_SPLAY_FIND(struct name *head, struct type *elm) \
129 if (SPLAY_EMPTY(head)) \
131 name##_SPLAY(head, elm); \
132 if ((cmp)(elm, (head)->sph_root) == 0) \
133 return (head->sph_root); \
138 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
140 name##_SPLAY(head, elm); \
152 name##_SPLAY_MIN_MAX(struct name *head, int val) \
154 name##_SPLAY_MINMAX(head, val); \
155 return (SPLAY_ROOT(head)); \
163 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
165 if (SPLAY_EMPTY(head)) { \
169 name##_SPLAY(head, elm); \
170 __comp = (cmp)(elm, (head)->sph_root); \
172 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
173 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
174 SPLAY_LEFT((head)->sph_root, field) = NULL; \
176 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
177 SPLAY_LEFT(elm, field) = (head)->sph_root; \
178 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
180 return ((head)->sph_root); \
182 (head)->sph_root = (elm); \
187 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
190 if (SPLAY_EMPTY(head)) \
192 name##_SPLAY(head, elm); \
193 if ((cmp)(elm, (head)->sph_root) == 0) { \
194 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
195 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
197 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
198 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
199 name##_SPLAY(head, elm); \
200 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
208 name##_SPLAY(struct name *head, struct type *elm) \
216 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
218 __tmp = SPLAY_LEFT((head)->sph_root, field); \
222 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
223 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
226 SPLAY_LINKLEFT(head, __right, field); \
228 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
232 SPLAY_ROTATE_LEFT(head, __tmp, field); \
233 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
236 SPLAY_LINKRIGHT(head, __left, field); \
239 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
245 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
254 __tmp = SPLAY_LEFT((head)->sph_root, field); \
258 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
259 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
262 SPLAY_LINKLEFT(head, __right, field); \
264 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
268 SPLAY_ROTATE_LEFT(head, __tmp, field); \
269 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
272 SPLAY_LINKRIGHT(head, __left, field); \
275 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
290 #define SPLAY_FOREACH(x, name, head) \ argument
291 for ((x) = SPLAY_MIN(name, head); \
293 (x) = SPLAY_NEXT(name, head, x))
322 #define RB_ROOT(head) (head)->rbh_root argument
323 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) argument
340 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
352 (head)->rbh_root = (tmp); \
360 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
372 (head)->rbh_root = (tmp); \
406 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
421 RB_ROTATE_LEFT(head, parent, tmp, field);\
427 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
437 RB_ROTATE_RIGHT(head, parent, tmp, field);\
443 RB_ROTATE_LEFT(head, gparent, tmp, field); \
446 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
450 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
454 elm != RB_ROOT(head)) { \
459 RB_ROTATE_LEFT(head, parent, tmp, field);\
477 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
484 RB_ROTATE_LEFT(head, parent, tmp, field);\
485 elm = RB_ROOT(head); \
492 RB_ROTATE_RIGHT(head, parent, tmp, field);\
510 RB_ROTATE_LEFT(head, tmp, oright, field);\
517 RB_ROTATE_RIGHT(head, parent, tmp, field);\
518 elm = RB_ROOT(head); \
528 name##_RB_REMOVE(struct name *head, struct type *elm) \
553 RB_ROOT(head) = child; \
564 RB_ROOT(head) = elm; \
587 RB_ROOT(head) = child; \
590 name##_RB_REMOVE_COLOR(head, parent, child); \
596 name##_RB_INSERT(struct name *head, struct type *elm) \
601 tmp = RB_ROOT(head); \
620 RB_ROOT(head) = elm; \
621 name##_RB_INSERT_COLOR(head, elm); \
627 name##_RB_FIND(struct name *head, struct type *elm) \
629 struct type *tmp = RB_ROOT(head); \
645 name##_RB_NFIND(struct name *head, struct type *elm) \
647 struct type *tmp = RB_ROOT(head); \
709 name##_RB_MINMAX(struct name *head, int val) \
711 struct type *tmp = RB_ROOT(head); \
735 #define RB_FOREACH(x, name, head) \ argument
736 for ((x) = RB_MIN(name, head); \
745 #define RB_FOREACH_SAFE(x, name, head, y) \ argument
746 for ((x) = RB_MIN(name, head); \
750 #define RB_FOREACH_REVERSE(x, name, head) \ argument
751 for ((x) = RB_MAX(name, head); \
760 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ argument
761 for ((x) = RB_MAX(name, head); \