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