Lines Matching refs:head
93 #define SPLAY_ROOT(head) (head)->sph_root argument
94 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) argument
97 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
98 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
99 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
100 (head)->sph_root = tmp; \
103 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
104 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
106 (head)->sph_root = tmp; \
109 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
110 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
111 tmp = (head)->sph_root; \
112 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
115 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
116 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
117 tmp = (head)->sph_root; \
118 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
121 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
122 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
123 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
124 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
125 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
138 name##_SPLAY_FIND(struct name *head, struct type *elm) \
140 if (SPLAY_EMPTY(head)) \
142 name##_SPLAY(head, elm); \
143 if ((cmp)(elm, (head)->sph_root) == 0) \
144 return (head->sph_root); \
149 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
151 name##_SPLAY(head, elm); \
163 name##_SPLAY_MIN_MAX(struct name *head, int val) \
165 name##_SPLAY_MINMAX(head, val); \
166 return (SPLAY_ROOT(head)); \
174 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
176 if (SPLAY_EMPTY(head)) { \
180 name##_SPLAY(head, elm); \
181 __comp = (cmp)(elm, (head)->sph_root); \
183 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
184 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
185 SPLAY_LEFT((head)->sph_root, field) = NULL; \
187 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
188 SPLAY_LEFT(elm, field) = (head)->sph_root; \
189 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
191 return ((head)->sph_root); \
193 (head)->sph_root = (elm); \
198 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
201 if (SPLAY_EMPTY(head)) \
203 name##_SPLAY(head, elm); \
204 if ((cmp)(elm, (head)->sph_root) == 0) { \
205 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
206 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
208 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
209 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
210 name##_SPLAY(head, elm); \
211 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
219 name##_SPLAY(struct name *head, struct type *elm) \
227 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
229 __tmp = SPLAY_LEFT((head)->sph_root, field); \
233 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
234 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
237 SPLAY_LINKLEFT(head, __right, field); \
239 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
243 SPLAY_ROTATE_LEFT(head, __tmp, field); \
244 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
247 SPLAY_LINKRIGHT(head, __left, field); \
250 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
256 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
265 __tmp = SPLAY_LEFT((head)->sph_root, field); \
269 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
270 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
273 SPLAY_LINKLEFT(head, __right, field); \
275 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
279 SPLAY_ROTATE_LEFT(head, __tmp, field); \
280 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
283 SPLAY_LINKRIGHT(head, __left, field); \
286 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
301 #define SPLAY_FOREACH(x, name, head) \ argument
302 for ((x) = SPLAY_MIN(name, head); \
304 (x) = SPLAY_NEXT(name, head, x))
347 #define RB_ROOT(head) (head)->rbh_root argument
348 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) argument
373 #define RB_SWAP_CHILD(head, out, in, field) do { \ argument
375 RB_ROOT(head) = (in); \
382 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
388 RB_SWAP_CHILD(head, elm, tmp, field); \
394 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
400 RB_SWAP_CHILD(head, elm, tmp, field); \
465 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
481 RB_ROTATE_LEFT(head, elm, child, field);\
488 RB_ROTATE_RIGHT(head, parent, elm, field); \
501 RB_ROTATE_RIGHT(head, elm, child, field);\
508 RB_ROTATE_LEFT(head, parent, elm, field); \
517 name##_RB_REMOVE_COLOR(struct name *head, \
551 RB_ROTATE_RIGHT(head, sib, elm, field); \
559 RB_ROTATE_LEFT(head, parent, sib, field); \
581 RB_ROTATE_LEFT(head, sib, elm, field); \
589 RB_ROTATE_RIGHT(head, parent, sib, field); \
597 name##_RB_REMOVE(struct name *head, struct type *elm) \
625 RB_SWAP_CHILD(head, old, elm, field); \
629 name##_RB_REMOVE_COLOR(head, parent, child); \
640 name##_RB_INSERT(struct name *head, struct type *elm) \
645 tmp = RB_ROOT(head); \
658 RB_ROOT(head) = elm; \
663 name##_RB_INSERT_COLOR(head, elm); \
674 name##_RB_FIND(struct name *head, struct type *elm) \
676 struct type *tmp = RB_ROOT(head); \
693 name##_RB_NFIND(struct name *head, struct type *elm) \
695 struct type *tmp = RB_ROOT(head); \
760 name##_RB_MINMAX(struct name *head, int val) \
762 struct type *tmp = RB_ROOT(head); \
776 name##_RB_REINSERT(struct name *head, struct type *elm) \
779 if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \
781 ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \
784 RB_REMOVE(name, head, elm); \
785 return (RB_INSERT(name, head, elm)); \
803 #define RB_FOREACH(x, name, head) \ argument
804 for ((x) = RB_MIN(name, head); \
813 #define RB_FOREACH_SAFE(x, name, head, y) \ argument
814 for ((x) = RB_MIN(name, head); \
818 #define RB_FOREACH_REVERSE(x, name, head) \ argument
819 for ((x) = RB_MAX(name, head); \
828 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ argument
829 for ((x) = RB_MAX(name, head); \