Lines Matching full:head
88 #define SPLAY_ROOT(head) (head)->sph_root
89 #define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
92 #define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
93 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
94 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
95 (head)->sph_root = tmp; \
98 #define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
99 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
100 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
101 (head)->sph_root = tmp; \
104 #define SPLAY_LINKLEFT(head, tmp, field) do { \
105 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
106 tmp = (head)->sph_root; \
107 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
110 #define SPLAY_LINKRIGHT(head, tmp, field) do { \
111 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
112 tmp = (head)->sph_root; \
113 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
116 #define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
117 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
118 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
119 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
120 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
133 name##_SPLAY_FIND(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
135 if (SPLAY_EMPTY(head)) \
137 name##_SPLAY(head, elm); \
138 if ((cmp)(elm, (head)->sph_root) == 0) \
139 return (head->sph_root); \
144 name##_SPLAY_NEXT(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
146 name##_SPLAY(head, elm); \
158 name##_SPLAY_MIN_MAX(SYS_TREE_STRUCT name *head, int val) \
160 name##_SPLAY_MINMAX(head, val); \
161 return (SPLAY_ROOT(head)); \
169 name##_SPLAY_INSERT(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
171 if (SPLAY_EMPTY(head)) { \
175 name##_SPLAY(head, elm); \
176 __comp = (cmp)(elm, (head)->sph_root); \
178 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
179 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
180 SPLAY_LEFT((head)->sph_root, field) = NULL; \
182 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
183 SPLAY_LEFT(elm, field) = (head)->sph_root; \
184 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
186 return ((head)->sph_root); \
188 (head)->sph_root = (elm); \
193 name##_SPLAY_REMOVE(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
196 if (SPLAY_EMPTY(head)) \
198 name##_SPLAY(head, elm); \
199 if ((cmp)(elm, (head)->sph_root) == 0) { \
200 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
201 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
203 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
204 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
205 name##_SPLAY(head, elm); \
206 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
214 name##_SPLAY(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
222 while ((__comp = (cmp)(elm, (head)->sph_root)) != 0) { \
224 __tmp = SPLAY_LEFT((head)->sph_root, field); \
228 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
229 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
232 SPLAY_LINKLEFT(head, __right, field); \
234 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
238 SPLAY_ROTATE_LEFT(head, __tmp, field); \
239 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
242 SPLAY_LINKRIGHT(head, __left, field); \
245 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
251 void name##_SPLAY_MINMAX(SYS_TREE_STRUCT name *head, int __comp) \
260 __tmp = SPLAY_LEFT((head)->sph_root, field); \
264 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
265 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
268 SPLAY_LINKLEFT(head, __right, field); \
270 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
274 SPLAY_ROTATE_LEFT(head, __tmp, field); \
275 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
278 SPLAY_LINKRIGHT(head, __left, field); \
281 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
296 #define SPLAY_FOREACH(x, name, head) \
297 for ((x) = SPLAY_MIN(name, head); \
299 (x) = SPLAY_NEXT(name, head, x))
328 #define RB_ROOT(head) (head)->rbh_root
329 #define RB_EMPTY(head) (RB_ROOT(head) == NULL)
346 #define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
358 (head)->rbh_root = (tmp); \
366 #define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
378 (head)->rbh_root = (tmp); \
412 name##_RB_INSERT_COLOR(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
427 RB_ROTATE_LEFT(head, parent, tmp, field);\
433 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
443 RB_ROTATE_RIGHT(head, parent, tmp, field);\
449 RB_ROTATE_LEFT(head, gparent, tmp, field); \
452 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
456 name##_RB_REMOVE_COLOR(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *parent, SYS_TREE_STRUCT type *elm) \
460 elm != RB_ROOT(head)) { \
465 RB_ROTATE_LEFT(head, parent, tmp, field);\
483 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
490 RB_ROTATE_LEFT(head, parent, tmp, field);\
491 elm = RB_ROOT(head); \
498 RB_ROTATE_RIGHT(head, parent, tmp, field);\
516 RB_ROTATE_LEFT(head, tmp, oright, field);\
523 RB_ROTATE_RIGHT(head, parent, tmp, field);\
524 elm = RB_ROOT(head); \
534 name##_RB_REMOVE(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
559 RB_ROOT(head) = child; \
570 RB_ROOT(head) = elm; \
593 RB_ROOT(head) = child; \
596 name##_RB_REMOVE_COLOR(head, parent, child); \
602 name##_RB_INSERT(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
607 tmp = RB_ROOT(head); \
626 RB_ROOT(head) = elm; \
627 name##_RB_INSERT_COLOR(head, elm); \
633 name##_RB_FIND(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
635 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \
651 name##_RB_NFIND(SYS_TREE_STRUCT name *head, SYS_TREE_STRUCT type *elm) \
653 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \
715 name##_RB_MINMAX(SYS_TREE_STRUCT name *head, int val) \
717 SYS_TREE_STRUCT type *tmp = RB_ROOT(head); \
741 #define RB_FOREACH(x, name, head) \
742 for ((x) = RB_MIN(name, head); \
751 #define RB_FOREACH_SAFE(x, name, head, y) \
752 for ((x) = RB_MIN(name, head); \
756 #define RB_FOREACH_REVERSE(x, name, head) \
757 for ((x) = RB_MAX(name, head); \
766 #define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
767 for ((x) = RB_MAX(name, head); \
