30 #include "../../../../common/util.h"
36 # define _E(exp) while(0)
39 #define XMALLOC malloc
40 #define XREALLOC realloc
41 #define XCALLOC calloc
44 #define SIDE_LEFT ((side_t)0)
45 #define SIDE_RGHT ((side_t)1)
66 #define __NAME_PREFIX__ ___rb_
67 #define __TREETYPE_PREFIX rbtree_
68 #define __NODETYPE_PREFIX rbnode_
69 #define __NODETYPE_ATTRS__ __attribute__ ((packed))
70 #define __TREETYPE_ATTRS__ __attribute__ ((packed))
72 typedef uint8_t side_t;
73 typedef uint8_t color_t;
75 #define __MYCONCAT2(a, b) a ## b
76 #define __MYCONCAT3(a, b, c) a ## b ## c
77 #define CONCAT2(a, b) __MYCONCAT2(a, b)
78 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c)
81 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name)
82 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name)
85 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree)
87 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create)
88 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void)
89 #define RB_CREATE RBN_CREATE_NAME
91 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode)
92 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void)
93 #define RB_NEWNODE RBN_NEWNODE_NAME
95 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert)
96 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node)
97 #define RB_INSERT RBN_INSERT_NAME
99 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search)
100 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
101 #define RB_SEARCH RBN_SEARCH_NAME
103 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
105 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name)
107 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node)
108 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node)
109 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name)
111 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node)
112 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node)
114 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r)
115 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r)
116 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r)
117 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r)
119 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate)
121 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp)
122 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b)
123 #define RBNODECMP DEF_RBN_NODECMP
125 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin)
126 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b)
127 #define RBNODEJOIN DEF_RBN_NODEJOIN
129 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk)
130 #define DEF_RBN_WALK(__t_name) void RBN_WALK_NAME(__t_name) (TREETYPE(__t_name) *tree, uint8_t order, void (*callback)(NODETYPE(__t_name) *, void *), void *cbarg)
131 #define RB_WALK RBN_WALK_NAME
133 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname)
134 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg)
135 #define RBCBNAME RBN_CALLBACK_NAME
136 #define RBCALLBACK DEF_RBN_CALLBACK
141 #define DEFRBTREE(__t_name, __u_nitem) \
142 NODETYPE(__t_name) { \
144 NODETYPE(__t_name) *___child[2]; \
149 } __NODETYPE_ATTRS__; \
151 TREETYPE(__t_name) { \
152 NODETYPE(__t_name) *root; \
154 } __TREETYPE_ATTRS__; \
156 DEF_RBN_NODEJOIN(__t_name); \
157 DEF_RBN_NODECMP(__t_name); \
158 DEF_RBN_CREATE(__t_name); \
159 DEF_RBN_NEWNODE(__t_name); \
160 DEF_RBN_WALK(__t_name); \
161 DEF_RBN_INSERT(__t_name); \
162 DEF_RBN_SEARCH(__t_name)
173 #define __isRED(n) ((n)->___c == COLOR_RED)
174 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n))
175 #define PTRMOVE(next) { \
181 #define lch (cur->___child[SIDE_LEFT])
182 #define rch (cur->___child[SIDE_RGHT])
187 #define RBN_NEWNODE_CODE(__t_name) \
188 DEF_RBN_NEWNODE(__t_name) { \
189 NODETYPE(__t_name) *new; \
190 new = XMALLOC(sizeof(NODETYPE(__t_name))); \
193 new->___child[0] = NULL; \
194 new->___child[1] = NULL; \
198 #define RBN_ROTATE_CODE(__t_name) \
199 static DEF_RBN_ROT_L(__t_name) { \
200 register NODETYPE(__t_name) *nr; \
202 nr = r->___child[SIDE_RGHT]; \
203 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
204 nr->___child[SIDE_LEFT] = r; \
206 nr->___s = r->___s; \
207 r->___s = SIDE_LEFT; \
209 if (r->___child[SIDE_RGHT] != NULL) \
210 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \
212 if (nr->___child[SIDE_RGHT] != NULL) \
213 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
218 static DEF_RBN_ROT_R(__t_name) { \
219 register NODETYPE(__t_name) *nr; \
221 nr = r->___child[SIDE_LEFT]; \
222 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
223 nr->___child[SIDE_RGHT] = r; \
225 nr->___s = r->___s; \
226 r->___s = SIDE_RGHT; \
228 if (r->___child[SIDE_LEFT] != NULL) \
229 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \
231 if (nr->___child[SIDE_LEFT] != NULL) \
232 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
237 static DEF_RBN_ROT_LR(__t_name) { \
238 register NODETYPE(__t_name) *nr; \
240 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \
241 nr->___s = r->___s; \
242 r->___s = SIDE_LEFT; \
243 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
245 if (nr->___child[SIDE_RGHT] != NULL) \
246 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
248 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \
249 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
251 if (nr->___child[SIDE_LEFT] != NULL) \
252 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
254 nr->___child[SIDE_LEFT] = r; \
255 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
260 static DEF_RBN_ROT_RL(__t_name) { \
261 register NODETYPE(__t_name) *nr; \
263 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \
264 nr->___s = r->___s; \
265 r->___s = SIDE_RGHT; \
266 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
268 if (nr->___child[SIDE_LEFT] != NULL) \
269 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
271 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \
272 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
274 if (nr->___child[SIDE_RGHT] != NULL) \
275 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
277 nr->___child[SIDE_RGHT] = r; \
278 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
283 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \
284 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \
285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \
286 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \
287 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \
290 #define RBN_CREATE_CODE(__t_name) \
291 DEF_RBN_CREATE(__t_name) { \
292 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \
298 #define RBN_INSERT_CODE(__t_name) \
299 DEF_RBN_INSERT(__t_name) { \
300 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \
303 NODETYPE(__t_name) fake; \
305 fake.___c = COLOR_BLK; \
306 fake.___child[SIDE_RGHT] = tree->root; \
307 fake.___child[SIDE_LEFT] = NULL; \
311 lastdir = SIDE_RGHT; \
316 par->___child[lastdir] = cur = new_node; \
317 cur->___s = lastdir; \
318 cur->___c = COLOR_RED; \
319 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \
322 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \
324 tree->root = fake.___child[SIDE_RGHT]; \
325 tree->root->___c = COLOR_BLK; \
329 } else if (isRED(lch) && isRED(rch)) { \
331 cur->___c = COLOR_RED; \
332 lch->___c = rch->___c = COLOR_BLK; \
335 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
336 } else if (__isRED(par) && __isRED(cur)) { \
338 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
341 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \
344 lastdir = cur->___s; \
345 _E(color_t tmp_c = cur->___c;) \
346 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \
347 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \
348 tree->root = fake.___child[SIDE_RGHT]; \
349 tree->root->___c = COLOR_BLK; \
350 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \
352 assert(cur->___s == lastdir); \
353 assert(cur->___c == tmp_c); \
354 assert(cur->___child[SIDE_LEFT] == tmp_l); \
355 assert(cur->___child[SIDE_RGHT] == tmp_r); \
358 } else if (cmp < 0) { \
361 lastdir = SIDE_RGHT; \
365 lastdir = SIDE_LEFT; \
373 #define RBN_SEARCH_CODE(__t_name) \
374 DEF_RBN_SEARCH(__t_name) { \
375 NODETYPE(__t_name) *node; \
380 while (node != NULL) { \
381 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \
386 node = node->___child[SIDE_RGHT]; \
388 node = node->___child[SIDE_LEFT]; \
394 #define __WALK_STACK_SIZE 32
395 #define __WALK_STACK_GROW 16
397 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count
398 #define POP(n) (n) = node_stack[--node_stack_count]
399 #define TOP (node_stack[node_stack_count-1])
400 #define CNT node_stack_count
402 #define RBN_WALK_CODE(__t_name) \
403 DEF_RBN_WALK(__t_name) { \
404 NODETYPE(__t_name) **node_stack; \
405 register uint16_t node_stack_size; \
406 register uint16_t node_stack_count; \
408 node_stack_count = 0; \
409 node_stack_size = __WALK_STACK_SIZE; \
410 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \
417 callback (TOP, cbarg); \
418 if (TOP->___child[SIDE_LEFT] != NULL) { \
419 PUSH(TOP->___child[SIDE_LEFT]); \
422 if (TOP->___child[SIDE_RGHT] != NULL) { \
423 TOP = TOP->___child[SIDE_RGHT]; \
435 if (TOP->___child[SIDE_LEFT] != NULL) { \
436 PUSH(TOP->___child[SIDE_LEFT]); \
439 callback (TOP, cbarg); \
440 if (TOP->___child[SIDE_RGHT] != NULL) { \
441 TOP = TOP->___child[SIDE_RGHT]; \
480 #define RBTREECODE(__t_name) \
481 RBN_CREATE_CODE(__t_name) \
482 RBN_ROTATE_CODE(__t_name); \
483 RBN_NEWNODE_CODE(__t_name) \
484 RBN_SEARCH_CODE(__t_name) \
485 RBN_INSERT_CODE(__t_name) \
486 RBN_WALK_CODE(__t_name) \
487 static const char CONCAT2(__t_name, dummy) = 0