30 #include "../../../../common/util.h" 37 # define _E(exp) while(0) 40 #define XMALLOC malloc 41 #define XREALLOC realloc 42 #define XCALLOC calloc 45 #define SIDE_LEFT ((side_t)0) 46 #define SIDE_RGHT ((side_t)1) 67 #define __NAME_PREFIX__ ___rb_ 68 #define __TREETYPE_PREFIX rbtree_ 69 #define __NODETYPE_PREFIX rbnode_ 70 #define __NODETYPE_ATTRS__ __attribute__ ((packed)) 71 #define __TREETYPE_ATTRS__ __attribute__ ((packed)) 73 typedef uint8_t side_t;
74 typedef uint8_t color_t;
76 #define __MYCONCAT2(a, b) a ## b 77 #define __MYCONCAT3(a, b, c) a ## b ## c 78 #define CONCAT2(a, b) __MYCONCAT2(a, b) 79 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c) 82 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name) 83 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name) 86 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree) 88 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create) 89 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void) 90 #define RB_CREATE RBN_CREATE_NAME 92 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode) 93 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void) 94 #define RB_NEWNODE RBN_NEWNODE_NAME 96 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert) 97 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node) 98 #define RB_INSERT RBN_INSERT_NAME 100 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search) 101 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 102 #define RB_SEARCH RBN_SEARCH_NAME 104 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 106 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name) 108 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node) 109 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node) 110 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name) 112 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node) 113 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node) 115 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r) 116 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r) 117 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r) 118 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r) 120 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate) 122 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp) 123 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b) 124 #define RBNODECMP DEF_RBN_NODECMP 126 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin) 127 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b) 128 #define RBNODEJOIN DEF_RBN_NODEJOIN 130 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk) 131 #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) 132 #define RB_WALK RBN_WALK_NAME 134 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname) 135 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg) 136 #define RBCBNAME RBN_CALLBACK_NAME 137 #define RBCALLBACK DEF_RBN_CALLBACK 142 #define DEFRBTREE(__t_name, __u_nitem) \ 143 NODETYPE(__t_name) { \ 145 NODETYPE(__t_name) *___child[2]; \ 150 } __NODETYPE_ATTRS__; \ 152 TREETYPE(__t_name) { \ 153 NODETYPE(__t_name) *root; \ 155 } __TREETYPE_ATTRS__; \ 157 DEF_RBN_NODEJOIN(__t_name); \ 158 DEF_RBN_NODECMP(__t_name); \ 159 DEF_RBN_CREATE(__t_name); \ 160 DEF_RBN_NEWNODE(__t_name); \ 161 DEF_RBN_WALK(__t_name); \ 162 DEF_RBN_INSERT(__t_name); \ 163 DEF_RBN_SEARCH(__t_name) 174 #define __isRED(n) ((n)->___c == COLOR_RED) 175 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n)) 176 #define PTRMOVE(next) { \ 182 #define lch (cur->___child[SIDE_LEFT]) 183 #define rch (cur->___child[SIDE_RGHT]) 188 #define RBN_NEWNODE_CODE(__t_name) \ 189 DEF_RBN_NEWNODE(__t_name) { \ 190 NODETYPE(__t_name) *new; \ 191 new = XMALLOC(sizeof(NODETYPE(__t_name))); \ 194 new->___child[0] = NULL; \ 195 new->___child[1] = NULL; \ 199 #define RBN_ROTATE_CODE(__t_name) \ 200 static DEF_RBN_ROT_L(__t_name) { \ 201 register NODETYPE(__t_name) *nr; \ 203 nr = r->___child[SIDE_RGHT]; \ 204 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 205 nr->___child[SIDE_LEFT] = r; \ 207 nr->___s = r->___s; \ 208 r->___s = SIDE_LEFT; \ 210 if (r->___child[SIDE_RGHT] != NULL) \ 211 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \ 213 if (nr->___child[SIDE_RGHT] != NULL) \ 214 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 219 static DEF_RBN_ROT_R(__t_name) { \ 220 register NODETYPE(__t_name) *nr; \ 222 nr = r->___child[SIDE_LEFT]; \ 223 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 224 nr->___child[SIDE_RGHT] = r; \ 226 nr->___s = r->___s; \ 227 r->___s = SIDE_RGHT; \ 229 if (r->___child[SIDE_LEFT] != NULL) \ 230 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \ 232 if (nr->___child[SIDE_LEFT] != NULL) \ 233 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 238 static DEF_RBN_ROT_LR(__t_name) { \ 239 register NODETYPE(__t_name) *nr; \ 241 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \ 242 nr->___s = r->___s; \ 243 r->___s = SIDE_LEFT; \ 244 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 246 if (nr->___child[SIDE_RGHT] != NULL) \ 247 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 249 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \ 250 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 252 if (nr->___child[SIDE_LEFT] != NULL) \ 253 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 255 nr->___child[SIDE_LEFT] = r; \ 256 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 261 static DEF_RBN_ROT_RL(__t_name) { \ 262 register NODETYPE(__t_name) *nr; \ 264 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \ 265 nr->___s = r->___s; \ 266 r->___s = SIDE_RGHT; \ 267 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 269 if (nr->___child[SIDE_LEFT] != NULL) \ 270 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 272 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \ 273 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 275 if (nr->___child[SIDE_RGHT] != NULL) \ 276 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 278 nr->___child[SIDE_RGHT] = r; \ 279 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 284 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \ 285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \ 286 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \ 287 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \ 288 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \ 291 #define RBN_CREATE_CODE(__t_name) \ 292 DEF_RBN_CREATE(__t_name) { \ 293 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \ 299 #define RBN_INSERT_CODE(__t_name) \ 300 DEF_RBN_INSERT(__t_name) { \ 301 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \ 304 NODETYPE(__t_name) fake; \ 306 fake.___c = COLOR_BLK; \ 307 fake.___child[SIDE_RGHT] = tree->root; \ 308 fake.___child[SIDE_LEFT] = NULL; \ 312 lastdir = SIDE_RGHT; \ 317 par->___child[lastdir] = cur = new_node; \ 318 cur->___s = lastdir; \ 319 cur->___c = COLOR_RED; \ 320 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \ 323 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \ 325 tree->root = fake.___child[SIDE_RGHT]; \ 326 tree->root->___c = COLOR_BLK; \ 330 } else if (isRED(lch) && isRED(rch)) { \ 332 cur->___c = COLOR_RED; \ 333 lch->___c = rch->___c = COLOR_BLK; \ 336 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 337 } else if (__isRED(par) && __isRED(cur)) { \ 339 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 342 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \ 345 lastdir = cur->___s; \ 346 _E(color_t tmp_c = cur->___c;) \ 347 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \ 348 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \ 349 tree->root = fake.___child[SIDE_RGHT]; \ 350 tree->root->___c = COLOR_BLK; \ 351 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \ 353 assert(cur->___s == lastdir); \ 354 assert(cur->___c == tmp_c); \ 355 assert(cur->___child[SIDE_LEFT] == tmp_l); \ 356 assert(cur->___child[SIDE_RGHT] == tmp_r); \ 359 } else if (cmp < 0) { \ 362 lastdir = SIDE_RGHT; \ 366 lastdir = SIDE_LEFT; \ 374 #define RBN_SEARCH_CODE(__t_name) \ 375 DEF_RBN_SEARCH(__t_name) { \ 376 NODETYPE(__t_name) *node; \ 381 while (node != NULL) { \ 382 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \ 387 node = node->___child[SIDE_RGHT]; \ 389 node = node->___child[SIDE_LEFT]; \ 395 #define __WALK_STACK_SIZE 32 396 #define __WALK_STACK_GROW 16 398 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count 399 #define POP(n) (n) = node_stack[--node_stack_count] 400 #define TOP (node_stack[node_stack_count-1]) 401 #define CNT node_stack_count 403 #define RBN_WALK_CODE(__t_name) \ 404 DEF_RBN_WALK(__t_name) { \ 405 NODETYPE(__t_name) **node_stack; \ 406 register uint16_t node_stack_size; \ 407 register uint16_t node_stack_count; \ 409 node_stack_count = 0; \ 410 node_stack_size = __WALK_STACK_SIZE; \ 411 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \ 418 callback (TOP, cbarg); \ 419 if (TOP->___child[SIDE_LEFT] != NULL) { \ 420 PUSH(TOP->___child[SIDE_LEFT]); \ 423 if (TOP->___child[SIDE_RGHT] != NULL) { \ 424 TOP = TOP->___child[SIDE_RGHT]; \ 436 if (TOP->___child[SIDE_LEFT] != NULL) { \ 437 PUSH(TOP->___child[SIDE_LEFT]); \ 440 callback (TOP, cbarg); \ 441 if (TOP->___child[SIDE_RGHT] != NULL) { \ 442 TOP = TOP->___child[SIDE_RGHT]; \ 481 #define RBTREECODE(__t_name) \ 482 RBN_CREATE_CODE(__t_name) \ 483 RBN_ROTATE_CODE(__t_name); \ 484 RBN_NEWNODE_CODE(__t_name) \ 485 RBN_SEARCH_CODE(__t_name) \ 486 RBN_INSERT_CODE(__t_name) \ 487 RBN_WALK_CODE(__t_name) \ 488 static const char CONCAT2(__t_name, dummy) = 0