Lines Matching refs:head
80 #define SPLAY_ROOT(head) (head)->sph_root
81 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
84 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
85 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
86 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
87 (head)->sph_root = tmp; \
90 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
91 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
92 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
93 (head)->sph_root = tmp; \
96 #define SPLAY_LINKLEFT(head, tmp, field) do { \
97 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
98 tmp = (head)->sph_root; \
99 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
102 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
103 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
104 tmp = (head)->sph_root; \
105 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
108 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
109 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
110 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
111 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
112 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
125 name##_SPLAY_FIND(struct name *head, struct type *elm) \
127 if (SPLAY_EMPTY(head)) \
129 name##_SPLAY(head, elm); \
130 if ((cmp)(elm, (head)->sph_root) == 0) \
131 return (head->sph_root); \
136 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
138 name##_SPLAY(head, elm); \
150 name##_SPLAY_MIN_MAX(struct name *head, int val) \
152 name##_SPLAY_MINMAX(head, val); \
153 return (SPLAY_ROOT(head)); \
161 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
163 if (SPLAY_EMPTY(head)) { \
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; \
172 SPLAY_LEFT((head)->sph_root, field) = NULL; \
174 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
175 SPLAY_LEFT(elm, field) = (head)->sph_root; \
176 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
178 return ((head)->sph_root); \
180 (head)->sph_root = (elm); \
185 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
188 if (SPLAY_EMPTY(head)) \
190 name##_SPLAY(head, elm); \
191 if ((cmp)(elm, (head)->sph_root) == 0) { \
192 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
193 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
195 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
196 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
197 name##_SPLAY(head, elm); \
198 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
206 name##_SPLAY(struct name *head, struct type *elm) \
214 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
216 __tmp = SPLAY_LEFT((head)->sph_root, field); \
220 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
221 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
224 SPLAY_LINKLEFT(head, __right, field); \
226 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
230 SPLAY_ROTATE_LEFT(head, __tmp, field); \
231 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
234 SPLAY_LINKRIGHT(head, __left, field); \
237 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
243 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
252 __tmp = SPLAY_LEFT((head)->sph_root, field); \
256 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
257 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
260 SPLAY_LINKLEFT(head, __right, field); \
262 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
266 SPLAY_ROTATE_LEFT(head, __tmp, field); \
267 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
270 SPLAY_LINKRIGHT(head, __left, field); \
273 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
288 #define SPLAY_FOREACH(x, name, head) \
289 for ((x) = SPLAY_MIN(name, head); \
291 (x) = SPLAY_NEXT(name, head, x))
327 #define RB_ROOT(head) (head)->rbh_root
328 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
345 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
357 (head)->rbh_root = (tmp); \
365 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
377 (head)->rbh_root = (tmp); \
411 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
426 RB_ROTATE_LEFT(head, parent, tmp, field);\
432 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
442 RB_ROTATE_RIGHT(head, parent, tmp, field);\
448 RB_ROTATE_LEFT(head, gparent, tmp, field); \
451 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
455 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
459 elm != RB_ROOT(head)) { \
464 RB_ROTATE_LEFT(head, parent, tmp, field);\
482 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
489 RB_ROTATE_LEFT(head, parent, tmp, field);\
490 elm = RB_ROOT(head); \
497 RB_ROTATE_RIGHT(head, parent, tmp, field);\
515 RB_ROTATE_LEFT(head, tmp, oright, field);\
522 RB_ROTATE_RIGHT(head, parent, tmp, field);\
523 elm = RB_ROOT(head); \
533 name##_RB_REMOVE(struct name *head, struct type *elm) \
558 RB_ROOT(head) = child; \
569 RB_ROOT(head) = elm; \
592 RB_ROOT(head) = child; \
595 name##_RB_REMOVE_COLOR(head, parent, child); \
601 name##_RB_INSERT(struct name *head, struct type *elm) \
606 tmp = RB_ROOT(head); \
625 RB_ROOT(head) = elm; \
626 name##_RB_INSERT_COLOR(head, elm); \
632 name##_RB_FIND(struct name *head, struct type *elm) \
634 struct type *tmp = RB_ROOT(head); \
650 name##_RB_NFIND(struct name *head, struct type *elm) \
652 struct type *tmp = RB_ROOT(head); \
714 name##_RB_MINMAX(struct name *head, int val) \
716 struct type *tmp = RB_ROOT(head); \
740 #define RB_FOREACH(x, name, head) \
741 for ((x) = RB_MIN(name, head); \
745 #define RB_FOREACH_REVERSE(x, name, head) \
746 for ((x) = RB_MAX(name, head); \