00001 #pragma once
00002 #ifndef REDBLACK_H
00003 #define REDBLACK_H
00004
00005 #include <stdint.h>
00006 #include <stdlib.h>
00007 #include <assert.h>
00008
00009 #ifndef NDEBUG
00010 # define _E(exp) exp
00011 #else
00012 # define _E(exp)
00013 #endif
00014
00015 #define XMALLOC malloc
00016 #define XREALLOC realloc
00017 #define XCALLOC calloc
00018 #define XFREE free
00019
00020 #define SIDE_LEFT ((side_t)0)
00021 #define SIDE_RGHT ((side_t)1)
00022
00023 #define COLOR_BLK 0
00024 #define COLOR_RED 1
00025
00026 #define PREORDER 0
00027 #define INORDER 1
00028 #define POSTORDER 2
00029 #define LRTDLAYER 3
00030 #define RLTDLAYER 4
00031
00032 #if !defined (E_OK)
00033 # define E_OK 0
00034 #endif
00035 #if !defined (E_FAIL)
00036 # define E_FAIL 1
00037 #endif
00038 #if !defined (E_COLL)
00039 # define E_COLL 2
00040 #endif
00041
00042 #define __NAME_PREFIX__ ___rb_
00043 #define __TREETYPE_PREFIX rbtree_
00044 #define __NODETYPE_PREFIX rbnode_
00045 #define __NODETYPE_ATTRS__ __attribute__ ((packed))
00046 #define __TREETYPE_ATTRS__ __attribute__ ((packed))
00047
00048 typedef uint8_t side_t;
00049 typedef uint8_t color_t;
00050
00051 #define __MYCONCAT2(a, b) a ## b
00052 #define __MYCONCAT3(a, b, c) a ## b ## c
00053 #define CONCAT2(a, b) __MYCONCAT2(a, b)
00054 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c)
00055 #define EXPAND(a) a
00056
00057 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name)
00058 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name)
00059
00060
00061 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree)
00062
00063 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create)
00064 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void)
00065 #define RB_CREATE RBN_CREATE_NAME
00066
00067 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode)
00068 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void)
00069 #define RB_NEWNODE RBN_NEWNODE_NAME
00070
00071 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert)
00072 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node)
00073 #define RB_INSERT RBN_INSERT_NAME
00074
00075 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search)
00076 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
00077 #define RB_SEARCH RBN_SEARCH_NAME
00078
00079 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node)
00080
00081 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name)
00082
00083 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node)
00084 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node)
00085 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name)
00086
00087 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node)
00088 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node)
00089
00090 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r)
00091 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r)
00092 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r)
00093 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r)
00094
00095 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate)
00096
00097 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp)
00098 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b)
00099 #define RBNODECMP DEF_RBN_NODECMP
00100
00101 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin)
00102 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b)
00103 #define RBNODEJOIN DEF_RBN_NODEJOIN
00104
00105 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk)
00106 #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)
00107 #define RB_WALK RBN_WALK_NAME
00108
00109 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname)
00110 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg)
00111 #define RBCBNAME RBN_CALLBACK_NAME
00112 #define RBCALLBACK DEF_RBN_CALLBACK
00113
00114 #define NOARG 0
00115
00116
00117 #define DEFRBTREE(__t_name, __u_nitem) \
00118 NODETYPE(__t_name) { \
00119 \
00120 NODETYPE(__t_name) *___child[2]; \
00121 color_t ___c: 1; \
00122 side_t ___s: 1; \
00123 \
00124 __u_nitem; \
00125 } __NODETYPE_ATTRS__; \
00126 \
00127 TREETYPE(__t_name) { \
00128 NODETYPE(__t_name) *root; \
00129 size_t size; \
00130 } __TREETYPE_ATTRS__; \
00131 \
00132 DEF_RBN_NODEJOIN(__t_name); \
00133 DEF_RBN_NODECMP(__t_name); \
00134 DEF_RBN_CREATE(__t_name); \
00135 DEF_RBN_NEWNODE(__t_name); \
00136 DEF_RBN_WALK(__t_name); \
00137 DEF_RBN_INSERT(__t_name); \
00138 DEF_RBN_SEARCH(__t_name)
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149 #define __isRED(n) ((n)->___c == COLOR_RED)
00150 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n))
00151 #define PTRMOVE(next) { \
00152 ggp = grp; \
00153 grp = par; \
00154 par = cur; \
00155 cur = next; }
00156
00157 #define lch (cur->___child[SIDE_LEFT])
00158 #define rch (cur->___child[SIDE_RGHT])
00159
00160
00161
00162
00163 #define RBN_NEWNODE_CODE(__t_name) \
00164 DEF_RBN_NEWNODE(__t_name) { \
00165 NODETYPE(__t_name) *new; \
00166 new = XMALLOC(sizeof(NODETYPE(__t_name))); \
00167 new->___s = 0; \
00168 new->___c = 0; \
00169 new->___child[0] = NULL; \
00170 new->___child[1] = NULL; \
00171 return (new); \
00172 }
00173
00174 #define RBN_ROTATE_CODE(__t_name) \
00175 static DEF_RBN_ROT_L(__t_name) { \
00176 register NODETYPE(__t_name) *nr; \
00177 \
00178 nr = r->___child[SIDE_RGHT]; \
00179 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
00180 nr->___child[SIDE_LEFT] = r; \
00181 \
00182 nr->___s = r->___s; \
00183 r->___s = SIDE_LEFT; \
00184 \
00185 if (r->___child[SIDE_RGHT] != NULL) \
00186 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \
00187 \
00188 if (nr->___child[SIDE_RGHT] != NULL) \
00189 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
00190 \
00191 return (nr); \
00192 } \
00193 \
00194 static DEF_RBN_ROT_R(__t_name) { \
00195 register NODETYPE(__t_name) *nr; \
00196 \
00197 nr = r->___child[SIDE_LEFT]; \
00198 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
00199 nr->___child[SIDE_RGHT] = r; \
00200 \
00201 nr->___s = r->___s; \
00202 r->___s = SIDE_RGHT; \
00203 \
00204 if (r->___child[SIDE_LEFT] != NULL) \
00205 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \
00206 \
00207 if (nr->___child[SIDE_LEFT] != NULL) \
00208 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
00209 \
00210 return (nr); \
00211 } \
00212 \
00213 static DEF_RBN_ROT_LR(__t_name) { \
00214 register NODETYPE(__t_name) *nr; \
00215 \
00216 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \
00217 nr->___s = r->___s; \
00218 r->___s = SIDE_LEFT; \
00219 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
00220 \
00221 if (nr->___child[SIDE_RGHT] != NULL) \
00222 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
00223 \
00224 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \
00225 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
00226 \
00227 if (nr->___child[SIDE_LEFT] != NULL) \
00228 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
00229 \
00230 nr->___child[SIDE_LEFT] = r; \
00231 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \
00232 \
00233 return (nr); \
00234 } \
00235 \
00236 static DEF_RBN_ROT_RL(__t_name) { \
00237 register NODETYPE(__t_name) *nr; \
00238 \
00239 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \
00240 nr->___s = r->___s; \
00241 r->___s = SIDE_RGHT; \
00242 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \
00243 \
00244 if (nr->___child[SIDE_LEFT] != NULL) \
00245 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \
00246 \
00247 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \
00248 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \
00249 \
00250 if (nr->___child[SIDE_RGHT] != NULL) \
00251 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \
00252 \
00253 nr->___child[SIDE_RGHT] = r; \
00254 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \
00255 \
00256 return (nr); \
00257 } \
00258 \
00259 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \
00260 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \
00261 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \
00262 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \
00263 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \
00264 }
00265
00266 #define RBN_CREATE_CODE(__t_name) \
00267 DEF_RBN_CREATE(__t_name) { \
00268 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \
00269 new->root = NULL; \
00270 new->size = 0; \
00271 return (new); \
00272 }
00273
00274 #define RBN_INSERT_CODE(__t_name) \
00275 DEF_RBN_INSERT(__t_name) { \
00276 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \
00277 side_t lastdir; \
00278 int cmp; \
00279 NODETYPE(__t_name) fake; \
00280 \
00281 fake.___c = COLOR_BLK; \
00282 fake.___child[SIDE_RGHT] = tree->root; \
00283 fake.___child[SIDE_LEFT] = NULL; \
00284 ggp = grp = NULL; \
00285 par = &fake; \
00286 cur = tree->root; \
00287 lastdir = SIDE_RGHT; \
00288 \
00289 for (;;) { \
00290 \
00291 if (cur == NULL) { \
00292 par->___child[lastdir] = cur = new_node; \
00293 cur->___s = lastdir; \
00294 cur->___c = COLOR_RED; \
00295 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \
00296 \
00297 if (__isRED(par)) \
00298 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \
00299 \
00300 tree->root = fake.___child[SIDE_RGHT]; \
00301 tree->root->___c = COLOR_BLK; \
00302 ++(tree->size); \
00303 \
00304 return (E_OK); \
00305 } else if (isRED(lch) && isRED(rch)) { \
00306 \
00307 cur->___c = COLOR_RED; \
00308 lch->___c = rch->___c = COLOR_BLK; \
00309 \
00310 if (__isRED(par)) \
00311 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
00312 } else if (__isRED(par) && __isRED(cur)) { \
00313 \
00314 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \
00315 } \
00316 \
00317 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \
00318 \
00319 if (cmp == 0) { \
00320 lastdir = cur->___s; \
00321 _E(color_t tmp_c = cur->___c;) \
00322 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \
00323 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \
00324 tree->root = fake.___child[SIDE_RGHT]; \
00325 tree->root->___c = COLOR_BLK; \
00326 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \
00327 \
00328 assert(cur->___s == lastdir); \
00329 assert(cur->___c == tmp_c); \
00330 assert(cur->___child[SIDE_LEFT] == tmp_l); \
00331 assert(cur->___child[SIDE_RGHT] == tmp_r); \
00332 \
00333 return (E_COLL); \
00334 } else if (cmp < 0) { \
00335 \
00336 PTRMOVE(rch); \
00337 lastdir = SIDE_RGHT; \
00338 } else { \
00339 \
00340 PTRMOVE(lch); \
00341 lastdir = SIDE_LEFT; \
00342 } \
00343 } \
00344 \
00345 abort (); \
00346 return (E_FAIL); \
00347 }
00348
00349 #define RBN_SEARCH_CODE(__t_name) \
00350 DEF_RBN_SEARCH(__t_name) { \
00351 NODETYPE(__t_name) *node; \
00352 int cmp; \
00353 \
00354 node = tree->root; \
00355 \
00356 while (node != NULL) { \
00357 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \
00358 \
00359 if (cmp == 0) \
00360 break; \
00361 else if (cmp < 0) \
00362 node = node->___child[SIDE_RGHT]; \
00363 else \
00364 node = node->___child[SIDE_LEFT]; \
00365 } \
00366 \
00367 return (node); \
00368 }
00369
00370 #define __WALK_STACK_SIZE 32
00371 #define __WALK_STACK_GROW 16
00372
00373 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count
00374 #define POP(n) (n) = node_stack[--node_stack_count]
00375 #define TOP (node_stack[node_stack_count-1])
00376 #define CNT node_stack_count
00377
00378 #define RBN_WALK_CODE(__t_name) \
00379 DEF_RBN_WALK(__t_name) { \
00380 NODETYPE(__t_name) **node_stack; \
00381 register uint16_t node_stack_size; \
00382 register uint16_t node_stack_count; \
00383 \
00384 node_stack_count = 0; \
00385 node_stack_size = __WALK_STACK_SIZE; \
00386 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \
00387 \
00388 PUSH(tree->root); \
00389 \
00390 switch (order) { \
00391 case PREORDER: \
00392 while (CNT > 0) { \
00393 callback (TOP, cbarg); \
00394 if (TOP->___child[SIDE_LEFT] != NULL) { \
00395 PUSH(TOP->___child[SIDE_LEFT]); \
00396 } else { \
00397 __pre: \
00398 if (TOP->___child[SIDE_RGHT] != NULL) { \
00399 TOP = TOP->___child[SIDE_RGHT]; \
00400 } else { \
00401 if (--CNT > 0) \
00402 goto __pre; \
00403 else \
00404 break; \
00405 } \
00406 } \
00407 } \
00408 break; \
00409 case INORDER: \
00410 while (CNT > 0) { \
00411 if (TOP->___child[SIDE_LEFT] != NULL) { \
00412 PUSH(TOP->___child[SIDE_LEFT]); \
00413 } else { \
00414 __in: \
00415 callback (TOP, cbarg); \
00416 if (TOP->___child[SIDE_RGHT] != NULL) { \
00417 TOP = TOP->___child[SIDE_RGHT]; \
00418 } else { \
00419 if (--CNT > 0) \
00420 goto __in; \
00421 else \
00422 break; \
00423 } \
00424 } \
00425 } \
00426 break; \
00427 case POSTORDER: \
00428 break; \
00429 default: \
00430 abort (); \
00431 } \
00432 XFREE(node_stack); \
00433 return; \
00434 }
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453
00454
00455
00456 #define RBTREECODE(__t_name) \
00457 RBN_CREATE_CODE(__t_name) \
00458 RBN_ROTATE_CODE(__t_name); \
00459 RBN_NEWNODE_CODE(__t_name) \
00460 RBN_SEARCH_CODE(__t_name) \
00461 RBN_INSERT_CODE(__t_name) \
00462 RBN_WALK_CODE(__t_name) \
00463 static const char CONCAT2(__t_name, dummy) = 0
00464
00465 #endif