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