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_ 69 #define __NODETYPE_ATTRS__ __attribute__ ((packed)) 70 #define __TREETYPE_ATTRS__ __attribute__ ((packed)) 72 typedef uint8_t side_t;
73 typedef uint8_t color_t;
75 #define __MYCONCAT2(a, b) a ## b 76 #define __MYCONCAT3(a, b, c) a ## b ## c 77 #define CONCAT2(a, b) __MYCONCAT2(a, b) 78 #define CONCAT3(a, b, c) __MYCONCAT3(a, b, c) 81 #define TREETYPE(__t_name) struct CONCAT2(__TREETYPE_PREFIX, __t_name) 82 #define NODETYPE(__t_name) struct CONCAT2(__NODETYPE_PREFIX, __t_name) 85 #define DEF_RBN_INITST(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _initst) (TREETYPE(__t_name) *tree) 87 #define RBN_CREATE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _create) 88 #define DEF_RBN_CREATE(__t_name) TREETYPE(__t_name) * RBN_CREATE_NAME(__t_name) (void) 89 #define RB_CREATE RBN_CREATE_NAME 91 #define RBN_NEWNODE_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _newnode) 92 #define DEF_RBN_NEWNODE(__t_name) NODETYPE(__t_name) * RBN_NEWNODE_NAME(__t_name) (void) 93 #define RB_NEWNODE RBN_NEWNODE_NAME 95 #define RBN_INSERT_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _insert) 96 #define DEF_RBN_INSERT(__t_name) int RBN_INSERT_NAME(__t_name) (TREETYPE(__t_name) *tree, NODETYPE(__t_name) *new_node) 97 #define RB_INSERT RBN_INSERT_NAME 99 #define RBN_SEARCH_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _search) 100 #define DEF_RBN_SEARCH(__t_name) NODETYPE(__t_name) * RBN_SEARCH_NAME(__t_name) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 101 #define RB_SEARCH RBN_SEARCH_NAME 103 #define DEF_RBN_DELETE(__t_name) int CONCAT3(__NAME_PREFIX__, __t_name, _delete) (TREETYPE(__t_name) *tree, const NODETYPE(__t_name) *k_node) 105 #define DEF_RBN_REMOVE(__t_name) DEF_RBN_DELETE(__t_name) 107 #define DEF_RBN_NODE_LEFT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getLeftNode) (NODETYPE(__t_name) *node) 108 #define DEF_RBN_NODE_RGHT(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _getRghtNode) (NODETYPE(__t_name) *node) 109 #define DEF_RBN_NODE_RIGHT(__t_name) RBN_NODE_RGHT(__t_name) 111 #define DEF_RBN_NODE_COLOR(__t_name) color_t CONCAT3(__NAME_PREFIX__, __t_name, _getColor) (NODETYPE(__t_name) *node) 112 #define DEF_RBN_NODE_SIDE(__t_name) side_t CONCAT3(__NAME_PREFIX__, __t_name, _getSide) (NODETYPE(__t_name) *node) 114 #define DEF_RBN_ROT_R(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotR) (NODETYPE(__t_name) *r) 115 #define DEF_RBN_ROT_L(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotL) (NODETYPE(__t_name) *r) 116 #define DEF_RBN_ROT_RL(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotRL) (NODETYPE(__t_name) *r) 117 #define DEF_RBN_ROT_LR(__t_name) NODETYPE(__t_name) * CONCAT3(__NAME_PREFIX__, __t_name, _rotLR) (NODETYPE(__t_name) *r) 119 #define ROTATE_ARR_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _rotate) 121 #define RBN_NODECMP_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodecmp) 122 #define DEF_RBN_NODECMP(__t_name) int RBN_NODECMP_NAME(__t_name) (const NODETYPE(__t_name) *a, const NODETYPE(__t_name) *b) 123 #define RBNODECMP DEF_RBN_NODECMP 125 #define RBN_NODEJOIN_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _nodejoin) 126 #define DEF_RBN_NODEJOIN(__t_name) NODETYPE(__t_name) * RBN_NODEJOIN_NAME(__t_name) (NODETYPE(__t_name) *a, NODETYPE(__t_name) *b) 127 #define RBNODEJOIN DEF_RBN_NODEJOIN 129 #define RBN_WALK_NAME(__t_name) CONCAT3(__NAME_PREFIX__, __t_name, _walk) 130 #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) 131 #define RB_WALK RBN_WALK_NAME 133 #define RBN_CALLBACK_NAME(__t_name, myname) CONCAT3(__t_name, _CB_, myname) 134 #define DEF_RBN_CALLBACK(__t_name, myname) void RBN_CALLBACK_NAME(__t_name, myname) (NODETYPE(__t_name) *node, void *cbarg) 135 #define RBCBNAME RBN_CALLBACK_NAME 136 #define RBCALLBACK DEF_RBN_CALLBACK 141 #define DEFRBTREE(__t_name, __u_nitem) \ 142 NODETYPE(__t_name) { \ 144 NODETYPE(__t_name) *___child[2]; \ 149 } __NODETYPE_ATTRS__; \ 151 TREETYPE(__t_name) { \ 152 NODETYPE(__t_name) *root; \ 154 } __TREETYPE_ATTRS__; \ 156 DEF_RBN_NODEJOIN(__t_name); \ 157 DEF_RBN_NODECMP(__t_name); \ 158 DEF_RBN_CREATE(__t_name); \ 159 DEF_RBN_NEWNODE(__t_name); \ 160 DEF_RBN_WALK(__t_name); \ 161 DEF_RBN_INSERT(__t_name); \ 162 DEF_RBN_SEARCH(__t_name) 173 #define __isRED(n) ((n)->___c == COLOR_RED) 174 #define isRED(n) (((n) == NULL) ? 0 : __isRED(n)) 175 #define PTRMOVE(next) { \ 181 #define lch (cur->___child[SIDE_LEFT]) 182 #define rch (cur->___child[SIDE_RGHT]) 187 #define RBN_NEWNODE_CODE(__t_name) \ 188 DEF_RBN_NEWNODE(__t_name) { \ 189 NODETYPE(__t_name) *new; \ 190 new = XMALLOC(sizeof(NODETYPE(__t_name))); \ 193 new->___child[0] = NULL; \ 194 new->___child[1] = NULL; \ 198 #define RBN_ROTATE_CODE(__t_name) \ 199 static DEF_RBN_ROT_L(__t_name) { \ 200 register NODETYPE(__t_name) *nr; \ 202 nr = r->___child[SIDE_RGHT]; \ 203 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 204 nr->___child[SIDE_LEFT] = r; \ 206 nr->___s = r->___s; \ 207 r->___s = SIDE_LEFT; \ 209 if (r->___child[SIDE_RGHT] != NULL) \ 210 r->___child[SIDE_RGHT]->___s = SIDE_RGHT; \ 212 if (nr->___child[SIDE_RGHT] != NULL) \ 213 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 218 static DEF_RBN_ROT_R(__t_name) { \ 219 register NODETYPE(__t_name) *nr; \ 221 nr = r->___child[SIDE_LEFT]; \ 222 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 223 nr->___child[SIDE_RGHT] = r; \ 225 nr->___s = r->___s; \ 226 r->___s = SIDE_RGHT; \ 228 if (r->___child[SIDE_LEFT] != NULL) \ 229 r->___child[SIDE_LEFT]->___s = SIDE_LEFT; \ 231 if (nr->___child[SIDE_LEFT] != NULL) \ 232 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 237 static DEF_RBN_ROT_LR(__t_name) { \ 238 register NODETYPE(__t_name) *nr; \ 240 nr = r->___child[SIDE_RGHT]->___child[SIDE_LEFT]; \ 241 nr->___s = r->___s; \ 242 r->___s = SIDE_LEFT; \ 243 r->___child[SIDE_RGHT]->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 245 if (nr->___child[SIDE_RGHT] != NULL) \ 246 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 248 nr->___child[SIDE_RGHT] = r->___child[SIDE_RGHT]; \ 249 r->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 251 if (nr->___child[SIDE_LEFT] != NULL) \ 252 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 254 nr->___child[SIDE_LEFT] = r; \ 255 nr->___child[SIDE_RGHT]->___c = COLOR_BLK; \ 260 static DEF_RBN_ROT_RL(__t_name) { \ 261 register NODETYPE(__t_name) *nr; \ 263 nr = r->___child[SIDE_LEFT]->___child[SIDE_RGHT]; \ 264 nr->___s = r->___s; \ 265 r->___s = SIDE_RGHT; \ 266 r->___child[SIDE_LEFT]->___child[SIDE_RGHT] = nr->___child[SIDE_LEFT]; \ 268 if (nr->___child[SIDE_LEFT] != NULL) \ 269 nr->___child[SIDE_LEFT]->___s = SIDE_RGHT; \ 271 nr->___child[SIDE_LEFT] = r->___child[SIDE_LEFT]; \ 272 r->___child[SIDE_LEFT] = nr->___child[SIDE_RGHT]; \ 274 if (nr->___child[SIDE_RGHT] != NULL) \ 275 nr->___child[SIDE_RGHT]->___s = SIDE_LEFT; \ 277 nr->___child[SIDE_RGHT] = r; \ 278 nr->___child[SIDE_LEFT]->___c = COLOR_BLK; \ 283 static NODETYPE(__t_name) * (*ROTATE_ARR_NAME(__t_name)[4])(NODETYPE(__t_name) *) = { \ 284 &CONCAT3(__NAME_PREFIX__, __t_name, _rotR), \ 285 &CONCAT3(__NAME_PREFIX__, __t_name, _rotLR), \ 286 &CONCAT3(__NAME_PREFIX__, __t_name, _rotRL), \ 287 &CONCAT3(__NAME_PREFIX__, __t_name, _rotL) \ 290 #define RBN_CREATE_CODE(__t_name) \ 291 DEF_RBN_CREATE(__t_name) { \ 292 TREETYPE(__t_name) *new = XMALLOC (sizeof (TREETYPE(__t_name))); \ 298 #define RBN_INSERT_CODE(__t_name) \ 299 DEF_RBN_INSERT(__t_name) { \ 300 NODETYPE(__t_name) *cur, *par, *grp, *ggp; \ 303 NODETYPE(__t_name) fake; \ 305 fake.___c = COLOR_BLK; \ 306 fake.___child[SIDE_RGHT] = tree->root; \ 307 fake.___child[SIDE_LEFT] = NULL; \ 311 lastdir = SIDE_RGHT; \ 316 par->___child[lastdir] = cur = new_node; \ 317 cur->___s = lastdir; \ 318 cur->___c = COLOR_RED; \ 319 cur->___child[SIDE_LEFT] = cur->___child[SIDE_RGHT]; \ 322 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(lastdir << 1)|(par->___s)](grp); \ 324 tree->root = fake.___child[SIDE_RGHT]; \ 325 tree->root->___c = COLOR_BLK; \ 329 } else if (isRED(lch) && isRED(rch)) { \ 331 cur->___c = COLOR_RED; \ 332 lch->___c = rch->___c = COLOR_BLK; \ 335 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 336 } else if (__isRED(par) && __isRED(cur)) { \ 338 ggp->___child[grp->___s] = ROTATE_ARR_NAME(__t_name)[(cur->___s << 1)|(par->___s)](grp); \ 341 cmp = RBN_NODECMP_NAME(__t_name) (cur, new_node); \ 344 lastdir = cur->___s; \ 345 _E(color_t tmp_c = cur->___c;) \ 346 _E(NODETYPE(__t_name) *tmp_l = cur->___child[SIDE_LEFT];) \ 347 _E(NODETYPE(__t_name) *tmp_r = cur->___child[SIDE_RGHT];) \ 348 tree->root = fake.___child[SIDE_RGHT]; \ 349 tree->root->___c = COLOR_BLK; \ 350 RBN_NODEJOIN_NAME(__t_name) (cur, new_node); \ 352 assert(cur->___s == lastdir); \ 353 assert(cur->___c == tmp_c); \ 354 assert(cur->___child[SIDE_LEFT] == tmp_l); \ 355 assert(cur->___child[SIDE_RGHT] == tmp_r); \ 358 } else if (cmp < 0) { \ 361 lastdir = SIDE_RGHT; \ 365 lastdir = SIDE_LEFT; \ 373 #define RBN_SEARCH_CODE(__t_name) \ 374 DEF_RBN_SEARCH(__t_name) { \ 375 NODETYPE(__t_name) *node; \ 380 while (node != NULL) { \ 381 cmp = RBN_NODECMP_NAME(__t_name) (node, k_node); \ 386 node = node->___child[SIDE_RGHT]; \ 388 node = node->___child[SIDE_LEFT]; \ 394 #define __WALK_STACK_SIZE 32 395 #define __WALK_STACK_GROW 16 397 #define PUSH(n) node_stack[node_stack_count] = (n), ++node_stack_count 398 #define POP(n) (n) = node_stack[--node_stack_count] 399 #define TOP (node_stack[node_stack_count-1]) 400 #define CNT node_stack_count 402 #define RBN_WALK_CODE(__t_name) \ 403 DEF_RBN_WALK(__t_name) { \ 404 NODETYPE(__t_name) **node_stack; \ 405 register uint16_t node_stack_size; \ 406 register uint16_t node_stack_count; \ 408 node_stack_count = 0; \ 409 node_stack_size = __WALK_STACK_SIZE; \ 410 node_stack = XCALLOC(sizeof (NODETYPE(__t_name) *), node_stack_size); \ 417 callback (TOP, cbarg); \ 418 if (TOP->___child[SIDE_LEFT] != NULL) { \ 419 PUSH(TOP->___child[SIDE_LEFT]); \ 422 if (TOP->___child[SIDE_RGHT] != NULL) { \ 423 TOP = TOP->___child[SIDE_RGHT]; \ 435 if (TOP->___child[SIDE_LEFT] != NULL) { \ 436 PUSH(TOP->___child[SIDE_LEFT]); \ 439 callback (TOP, cbarg); \ 440 if (TOP->___child[SIDE_RGHT] != NULL) { \ 441 TOP = TOP->___child[SIDE_RGHT]; \ 480 #define RBTREECODE(__t_name) \ 481 RBN_CREATE_CODE(__t_name) \ 482 RBN_ROTATE_CODE(__t_name); \ 483 RBN_NEWNODE_CODE(__t_name) \ 484 RBN_SEARCH_CODE(__t_name) \ 485 RBN_INSERT_CODE(__t_name) \ 486 RBN_WALK_CODE(__t_name) \ 487 static const char CONCAT2(__t_name, dummy) = 0