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_ 70 typedef uint8_t side_t;
71 typedef uint8_t color_t;
73 #define __MYCONCAT2(a, b) a ## b 74 #define __MYCONCAT3(a, b, c) a ## b ## c 75 #define CONCAT2(a, b) __MYCONCAT2(a, b) 76 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c) 79 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name) 80 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name) 83 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree) 85 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create) 86 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void) 87 #define RB_CREATE RBN_CREATE_NAME 89 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode) 90 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void) 91 #define RB_NEWNODE RBN_NEWNODE_NAME 93 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert) 94 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node) 95 #define RB_INSERT RBN_INSERT_NAME 97 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search) 98 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 99 #define RB_SEARCH RBN_SEARCH_NAME 101 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 103 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name) 105 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node) 106 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node) 107 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name) 109 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node) 110 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node) 112 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r) 113 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r) 114 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r) 115 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r) 117 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate) 119 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp) 120 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b) 121 #define RBNODECMP DEF_RBN_NODECMP 123 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin) 124 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b) 125 #define RBNODEJOIN DEF_RBN_NODEJOIN 127 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk) 128 #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) 129 #define RB_WALK RBN_WALK_NAME 131 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname) 132 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg) 133 #define RBCBNAME RBN_CALLBACK_NAME 134 #define RBCALLBACK DEF_RBN_CALLBACK 139 #define DEFRBTREE(__t_name, __u_nitem) \ 140 NODETYPE(__t_name) { \ 142 NODETYPE(__t_name) *___child[2]; \ 149 TREETYPE(__t_name) { \ 150 NODETYPE(__t_name) *root; \ 154 DEF_RBN_NODEJOIN(__t_name); \ 155 DEF_RBN_NODECMP(__t_name); \ 156 DEF_RBN_CREATE(__t_name); \ 157 DEF_RBN_NEWNODE(__t_name); \ 158 DEF_RBN_WALK(__t_name); \ 159 DEF_RBN_INSERT(__t_name); \ 160 DEF_RBN_SEARCH(__t_name) 171 #define __isRED(n) ((n)->___c == COLOR_RED) 172 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n)) 173 #define PTRMOVE(next) { \ 179 #define lch (cur->___child[SIDE_LEFT]) 180 #define rch (cur->___child[SIDE_RGHT]) 185 #define RBN_NEWNODE_CODE(__t_name) \ 186 DEF_RBN_NEWNODE(__t_name) { \ 187 NODETYPE(__t_name) *new; \ 188 new = XMALLOC(sizeof(NODETYPE(__t_name))); \ 191 new->___child[0] = NULL; \ 192 new->___child[1] = NULL; \ 196 #define RBN_ROTATE_CODE(__t_name) \ 197 static DEF_RBN_ROT_L(__t_name) { \ 198 register NODETYPE(__t_name) *nr; \ 200 nr = r->___child[SIDE_RGHT]; \ 201 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 202 nr->___child[SIDE_LEFT] = r; \ 204 nr->___s = r->___s; \ 205 r->___s = SIDE_LEFT; \ 207 if (r->___child[SIDE_RGHT] != NULL) \ 208 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \ 210 if (nr->___child[SIDE_RGHT] != NULL) \ 211 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 216 static DEF_RBN_ROT_R(__t_name) { \ 217 register NODETYPE(__t_name) *nr; \ 219 nr = r->___child[SIDE_LEFT]; \ 220 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 221 nr->___child[SIDE_RGHT] = r; \ 223 nr->___s = r->___s; \ 224 r->___s = SIDE_RGHT; \ 226 if (r->___child[SIDE_LEFT] != NULL) \ 227 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \ 229 if (nr->___child[SIDE_LEFT] != NULL) \ 230 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 235 static DEF_RBN_ROT_LR(__t_name) { \ 236 register NODETYPE(__t_name) *nr; \ 238 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \ 239 nr->___s = r->___s; \ 240 r->___s = SIDE_LEFT; \ 241 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 243 if (nr->___child[SIDE_RGHT] != NULL) \ 244 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 246 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \ 247 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 249 if (nr->___child[SIDE_LEFT] != NULL) \ 250 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 252 nr->___child[SIDE_LEFT] = r; \ 253 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 258 static DEF_RBN_ROT_RL(__t_name) { \ 259 register NODETYPE(__t_name) *nr; \ 261 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \ 262 nr->___s = r->___s; \ 263 r->___s = SIDE_RGHT; \ 264 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 266 if (nr->___child[SIDE_LEFT] != NULL) \ 267 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 269 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \ 270 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 272 if (nr->___child[SIDE_RGHT] != NULL) \ 273 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 275 nr->___child[SIDE_RGHT] = r; \ 276 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 281 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \ 282 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \ 283 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \ 284 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \ 285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \ 288 #define RBN_CREATE_CODE(__t_name) \ 289 DEF_RBN_CREATE(__t_name) { \ 290 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \ 296 #define RBN_INSERT_CODE(__t_name) \ 297 DEF_RBN_INSERT(__t_name) { \ 298 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \ 301 NODETYPE(__t_name) fake; \ 303 fake.___c = COLOR_BLK; \ 304 fake.___child[SIDE_RGHT] = tree->root; \ 305 fake.___child[SIDE_LEFT] = NULL; \ 309 lastdir = SIDE_RGHT; \ 314 par->___child[lastdir] = cur = new_node; \ 315 cur->___s = lastdir; \ 316 cur->___c = COLOR_RED; \ 317 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \ 320 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \ 322 tree->root = fake.___child[SIDE_RGHT]; \ 323 tree->root->___c = COLOR_BLK; \ 327 } else if (isRED(lch) && isRED(rch)) { \ 329 cur->___c = COLOR_RED; \ 330 lch->___c = rch->___c = COLOR_BLK; \ 333 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 334 } else if (__isRED(par) && __isRED(cur)) { \ 336 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 339 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \ 342 lastdir = cur->___s; \ 343 _E(color_t tmp_c = cur->___c;) \ 344 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \ 345 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \ 346 tree->root = fake.___child[SIDE_RGHT]; \ 347 tree->root->___c = COLOR_BLK; \ 348 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \ 350 assert(cur->___s == lastdir); \ 351 assert(cur->___c == tmp_c); \ 352 assert(cur->___child[SIDE_LEFT] == tmp_l); \ 353 assert(cur->___child[SIDE_RGHT] == tmp_r); \ 356 } else if (cmp < 0) { \ 359 lastdir = SIDE_RGHT; \ 363 lastdir = SIDE_LEFT; \ 371 #define RBN_SEARCH_CODE(__t_name) \ 372 DEF_RBN_SEARCH(__t_name) { \ 373 NODETYPE(__t_name) *node; \ 378 while (node != NULL) { \ 379 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \ 384 node = node->___child[SIDE_RGHT]; \ 386 node = node->___child[SIDE_LEFT]; \ 392 #define __WALK_STACK_SIZE 32 393 #define __WALK_STACK_GROW 16 395 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count 396 #define POP(n) (n) = node_stack[--node_stack_count] 397 #define TOP (node_stack[node_stack_count-1]) 398 #define CNT node_stack_count 400 #define RBN_WALK_CODE(__t_name) \ 401 DEF_RBN_WALK(__t_name) { \ 402 NODETYPE(__t_name) **node_stack; \ 403 register uint16_t node_stack_size; \ 404 register uint16_t node_stack_count; \ 406 node_stack_count = 0; \ 407 node_stack_size = __WALK_STACK_SIZE; \ 408 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \ 415 callback (TOP, cbarg); \ 416 if (TOP->___child[SIDE_LEFT] != NULL) { \ 417 PUSH(TOP->___child[SIDE_LEFT]); \ 420 if (TOP->___child[SIDE_RGHT] != NULL) { \ 421 TOP = TOP->___child[SIDE_RGHT]; \ 433 if (TOP->___child[SIDE_LEFT] != NULL) { \ 434 PUSH(TOP->___child[SIDE_LEFT]); \ 437 callback (TOP, cbarg); \ 438 if (TOP->___child[SIDE_RGHT] != NULL) { \ 439 TOP = TOP->___child[SIDE_RGHT]; \ 478 #define RBTREECODE(__t_name) \ 479 RBN_CREATE_CODE(__t_name) \ 480 RBN_ROTATE_CODE(__t_name); \ 481 RBN_NEWNODE_CODE(__t_name) \ 482 RBN_SEARCH_CODE(__t_name) \ 483 RBN_INSERT_CODE(__t_name) \ 484 RBN_WALK_CODE(__t_name) \ 485 static const char CONCAT2(__t_name, dummy) = 0