Lines Matching refs:head
77 #define SPLAY_ROOT(head) (head)->sph_root argument
78 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) argument
81 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ argument
82 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
83 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
84 (head)->sph_root = tmp; \
87 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ argument
88 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
89 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
90 (head)->sph_root = tmp; \
93 #define SPLAY_LINKLEFT(head, tmp, field) do { \ argument
94 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
95 tmp = (head)->sph_root; \
96 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
99 #define SPLAY_LINKRIGHT(head, tmp, field) do { \ argument
100 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
101 tmp = (head)->sph_root; \
102 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
105 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ argument
106 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
107 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
108 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
109 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
122 name##_SPLAY_FIND(struct name *head, struct type *elm) \
124 if (SPLAY_EMPTY(head)) \
126 name##_SPLAY(head, elm); \
127 if ((cmp)(elm, (head)->sph_root) == 0) \
128 return (head->sph_root); \
133 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
135 name##_SPLAY(head, elm); \
147 name##_SPLAY_MIN_MAX(struct name *head, int val) \
149 name##_SPLAY_MINMAX(head, val); \
150 return (SPLAY_ROOT(head)); \
158 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
160 if (SPLAY_EMPTY(head)) { \
164 name##_SPLAY(head, elm); \
165 __comp = (cmp)(elm, (head)->sph_root); \
167 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
168 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
169 SPLAY_LEFT((head)->sph_root, field) = NULL; \
171 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
172 SPLAY_LEFT(elm, field) = (head)->sph_root; \
173 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
175 return ((head)->sph_root); \
177 (head)->sph_root = (elm); \
182 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
185 if (SPLAY_EMPTY(head)) \
187 name##_SPLAY(head, elm); \
188 if ((cmp)(elm, (head)->sph_root) == 0) { \
189 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
190 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
192 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
193 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
194 name##_SPLAY(head, elm); \
195 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
203 name##_SPLAY(struct name *head, struct type *elm) \
211 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
213 __tmp = SPLAY_LEFT((head)->sph_root, field); \
217 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
218 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
221 SPLAY_LINKLEFT(head, __right, field); \
223 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
227 SPLAY_ROTATE_LEFT(head, __tmp, field); \
228 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
231 SPLAY_LINKRIGHT(head, __left, field); \
234 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
240 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
249 __tmp = SPLAY_LEFT((head)->sph_root, field); \
253 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
254 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
257 SPLAY_LINKLEFT(head, __right, field); \
259 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
263 SPLAY_ROTATE_LEFT(head, __tmp, field); \
264 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
267 SPLAY_LINKRIGHT(head, __left, field); \
270 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
285 #define SPLAY_FOREACH(x, name, head) \ argument
286 for ((x) = SPLAY_MIN(name, head); \
288 (x) = SPLAY_NEXT(name, head, x))
317 #define RB_ROOT(head) (head)->rbh_root argument
318 #define RB_EMPTY(head) (RB_ROOT(head) == NULL) argument
335 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ argument
347 (head)->rbh_root = (tmp); \
355 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ argument
367 (head)->rbh_root = (tmp); \
391 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
406 RB_ROTATE_LEFT(head, parent, tmp, field);\
412 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
422 RB_ROTATE_RIGHT(head, parent, tmp, field);\
428 RB_ROTATE_LEFT(head, gparent, tmp, field); \
431 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
435 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
439 elm != RB_ROOT(head)) { \
444 RB_ROTATE_LEFT(head, parent, tmp, field);\
461 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
468 RB_ROTATE_LEFT(head, parent, tmp, field);\
469 elm = RB_ROOT(head); \
476 RB_ROTATE_RIGHT(head, parent, tmp, field);\
493 RB_ROTATE_LEFT(head, tmp, oright, field);\
500 RB_ROTATE_RIGHT(head, parent, tmp, field);\
501 elm = RB_ROOT(head); \
511 name##_RB_REMOVE(struct name *head, struct type *elm) \
536 RB_ROOT(head) = child; \
547 RB_ROOT(head) = elm; \
570 RB_ROOT(head) = child; \
573 name##_RB_REMOVE_COLOR(head, parent, child); \
579 name##_RB_INSERT(struct name *head, struct type *elm) \
584 tmp = RB_ROOT(head); \
603 RB_ROOT(head) = elm; \
604 name##_RB_INSERT_COLOR(head, elm); \
610 name##_RB_FIND(struct name *head, struct type *elm) \
612 struct type *tmp = RB_ROOT(head); \
648 name##_RB_MINMAX(struct name *head, int val) \
650 struct type *tmp = RB_ROOT(head); \
672 #define RB_FOREACH(x, name, head) \ argument
673 for ((x) = RB_MIN(name, head); \