Lines Matching full:head
79 #define SPLAY_ROOT(head) (head)->sph_root
80 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
83 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
84 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
85 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
86 (head)->sph_root = tmp; \
89 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
90 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
91 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
92 (head)->sph_root = tmp; \
95 #define SPLAY_LINKLEFT(head, tmp, field) do { \
96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97 tmp = (head)->sph_root; \
98 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
101 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
102 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
103 tmp = (head)->sph_root; \
104 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
107 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
108 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
109 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
110 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
111 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
124 name##_SPLAY_FIND(struct name *head, struct type *elm) \
126 if (SPLAY_EMPTY(head)) \
128 name##_SPLAY(head, elm); \
129 if ((cmp)(elm, (head)->sph_root) == 0) \
130 return (head->sph_root); \
135 name##_SPLAY_NEXT(struct name *head, struct type *elm) \
137 name##_SPLAY(head, elm); \
149 name##_SPLAY_MIN_MAX(struct name *head, int val) \
151 name##_SPLAY_MINMAX(head, val); \
152 return (SPLAY_ROOT(head)); \
160 name##_SPLAY_INSERT(struct name *head, struct type *elm) \
162 if (SPLAY_EMPTY(head)) { \
166 name##_SPLAY(head, elm); \
167 __comp = (cmp)(elm, (head)->sph_root); \
169 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
170 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
171 SPLAY_LEFT((head)->sph_root, field) = NULL; \
173 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
174 SPLAY_LEFT(elm, field) = (head)->sph_root; \
175 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
177 return ((head)->sph_root); \
179 (head)->sph_root = (elm); \
184 name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
187 if (SPLAY_EMPTY(head)) \
189 name##_SPLAY(head, elm); \
190 if ((cmp)(elm, (head)->sph_root) == 0) { \
191 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
192 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
194 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
195 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
196 name##_SPLAY(head, elm); \
197 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
205 name##_SPLAY(struct name *head, struct type *elm) \
213 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
215 __tmp = SPLAY_LEFT((head)->sph_root, field); \
219 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
220 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
223 SPLAY_LINKLEFT(head, __right, field); \
225 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
229 SPLAY_ROTATE_LEFT(head, __tmp, field); \
230 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
233 SPLAY_LINKRIGHT(head, __left, field); \
236 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
242 void name##_SPLAY_MINMAX(struct name *head, int __comp) \
251 __tmp = SPLAY_LEFT((head)->sph_root, field); \
255 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
256 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
259 SPLAY_LINKLEFT(head, __right, field); \
261 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
265 SPLAY_ROTATE_LEFT(head, __tmp, field); \
266 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
269 SPLAY_LINKRIGHT(head, __left, field); \
272 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
287 #define SPLAY_FOREACH(x, name, head) \
288 for ((x) = SPLAY_MIN(name, head); \
290 (x) = SPLAY_NEXT(name, head, x))
319 #define RB_ROOT(head) (head)->rbh_root
320 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
337 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
349 (head)->rbh_root = (tmp); \
357 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
369 (head)->rbh_root = (tmp); \
393 name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
408 RB_ROTATE_LEFT(head, parent, tmp, field);\
414 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
424 RB_ROTATE_RIGHT(head, parent, tmp, field);\
430 RB_ROTATE_LEFT(head, gparent, tmp, field); \
433 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
437 name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
441 elm != RB_ROOT(head)) { \
446 RB_ROTATE_LEFT(head, parent, tmp, field);\
463 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
470 RB_ROTATE_LEFT(head, parent, tmp, field);\
471 elm = RB_ROOT(head); \
478 RB_ROTATE_RIGHT(head, parent, tmp, field);\
495 RB_ROTATE_LEFT(head, tmp, oright, field);\
502 RB_ROTATE_RIGHT(head, parent, tmp, field);\
503 elm = RB_ROOT(head); \
513 name##_RB_REMOVE(struct name *head, struct type *elm) \
538 RB_ROOT(head) = child; \
549 RB_ROOT(head) = elm; \
572 RB_ROOT(head) = child; \
575 name##_RB_REMOVE_COLOR(head, parent, child); \
581 name##_RB_INSERT(struct name *head, struct type *elm) \
586 tmp = RB_ROOT(head); \
605 RB_ROOT(head) = elm; \
606 name##_RB_INSERT_COLOR(head, elm); \
612 name##_RB_FIND(struct name *head, struct type *elm) \
614 struct type *tmp = RB_ROOT(head); \
650 name##_RB_MINMAX(struct name *head, int val) \
652 struct type *tmp = RB_ROOT(head); \
674 #define RB_FOREACH(x, name, head) \
675 for ((x) = RB_MIN(name, head); \
