Lines Matching +full:comp +full:- +full:config
29 #include "config.h"
39 * splay trees and red-black trees.
41 * A splay tree is a self-organizing data structure. Every operation
53 * A red-black tree is a binary search tree with the node color as an
55 * - every search path from the root to a leaf consists of the
57 * - each red node (except for the root) has a black parent,
58 * - each leaf node is black.
60 * Every operation on a red-black tree is bounded as O(lg n).
61 * The maximum height of a red-black tree is 2lg (n+1).
73 (root)->sph_root = NULL; \
82 #define SPLAY_LEFT(elm, field) (elm)->field.spe_left
83 #define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
84 #define SPLAY_ROOT(head) (head)->sph_root
89 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
90 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
91 (head)->sph_root = tmp; \
95 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97 (head)->sph_root = tmp; \
101 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
102 tmp = (head)->sph_root; \
103 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
107 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
108 tmp = (head)->sph_root; \
109 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
113 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
114 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
115 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
116 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
134 if ((cmp)(elm, (head)->sph_root) == 0) \
135 return (head->sph_root); \
172 __comp = (cmp)(elm, (head)->sph_root); \
174 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
175 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
176 SPLAY_LEFT((head)->sph_root, field) = NULL; \
178 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
179 SPLAY_LEFT(elm, field) = (head)->sph_root; \
180 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
182 return ((head)->sph_root); \
184 (head)->sph_root = (elm); \
195 if ((cmp)(elm, (head)->sph_root) == 0) { \
196 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
197 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
199 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
200 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
202 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
218 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
220 __tmp = SPLAY_LEFT((head)->sph_root, field); \
225 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
230 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
235 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
256 __tmp = SPLAY_LEFT((head)->sph_root, field); \
261 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
266 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
271 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
280 #define SPLAY_NEGINF -1
297 /* Macros that define a red-black tree */
307 (root)->rbh_root = NULL; \
320 #define RB_LEFT(elm, field) (elm)->field.rbe_left
321 #define RB_RIGHT(elm, field) (elm)->field.rbe_right
322 #define RB_PARENT(elm, field) (elm)->field.rbe_parent
323 #define RB_COLOR(elm, field) (elm)->field.rbe_color
324 #define RB_ROOT(head) (head)->rbh_root
354 (head)->rbh_root = (tmp); \
374 (head)->rbh_root = (tmp); \
448 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
556 (elm)->field = (old)->field; \
600 int comp = 0; \
604 comp = (cmp)(elm, parent); \
605 if (comp < 0) \
607 else if (comp > 0) \
614 if (comp < 0) \
630 int comp; \
632 comp = cmp(elm, tmp); \
633 if (comp < 0) \
635 else if (comp > 0) \
649 int comp; \
651 comp = cmp(elm, tmp); \
652 if (comp < 0) { \
656 else if (comp > 0) \
723 #define RB_NEGINF -1