rayzor
diff src/rbtree.c @ 16:4d87b0aafbb0
forgot to add the redblack tree
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sun, 13 Apr 2014 09:54:51 +0300 |
| parents | |
| children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/rbtree.c Sun Apr 13 09:54:51 2014 +0300 1.3 @@ -0,0 +1,492 @@ 1.4 +#include <stdio.h> 1.5 +#include <stdlib.h> 1.6 +#include <string.h> 1.7 +#include "inttypes.h" 1.8 +#include "rbtree.h" 1.9 + 1.10 +#define INT2PTR(x) ((void*)(intptr_t)(x)) 1.11 +#define PTR2INT(x) ((int)(intptr_t)(x)) 1.12 + 1.13 +struct rbtree { 1.14 + struct rbnode *root; 1.15 + 1.16 + rb_alloc_func_t alloc; 1.17 + rb_free_func_t free; 1.18 + 1.19 + rb_cmp_func_t cmp; 1.20 + rb_del_func_t del; 1.21 + void *del_cls; 1.22 + 1.23 + struct rbnode *rstack, *iter; 1.24 +}; 1.25 + 1.26 +static int cmpaddr(const void *ap, const void *bp); 1.27 +static int cmpint(const void *ap, const void *bp); 1.28 + 1.29 +static int count_nodes(struct rbnode *node); 1.30 +static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls); 1.31 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data); 1.32 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key); 1.33 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/ 1.34 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls); 1.35 + 1.36 +struct rbtree *rb_create(rb_cmp_func_t cmp_func) 1.37 +{ 1.38 + struct rbtree *rb; 1.39 + 1.40 + if(!(rb = malloc(sizeof *rb))) { 1.41 + return 0; 1.42 + } 1.43 + if(rb_init(rb, cmp_func) == -1) { 1.44 + free(rb); 1.45 + return 0; 1.46 + } 1.47 + return rb; 1.48 +} 1.49 + 1.50 +void rb_free(struct rbtree *rb) 1.51 +{ 1.52 + rb_destroy(rb); 1.53 + free(rb); 1.54 +} 1.55 + 1.56 + 1.57 +int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func) 1.58 +{ 1.59 + memset(rb, 0, sizeof *rb); 1.60 + 1.61 + if(cmp_func == RB_KEY_INT) { 1.62 + rb->cmp = cmpint; 1.63 + } else if(cmp_func == RB_KEY_STRING) { 1.64 + rb->cmp = (rb_cmp_func_t)strcmp; 1.65 + } else { 1.66 + rb->cmp = cmpaddr; 1.67 + } 1.68 + 1.69 + rb->alloc = malloc; 1.70 + rb->free = free; 1.71 + return 0; 1.72 +} 1.73 + 1.74 +void rb_destroy(struct rbtree *rb) 1.75 +{ 1.76 + del_tree(rb->root, rb->del, rb->del_cls); 1.77 +} 1.78 + 1.79 +void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free) 1.80 +{ 1.81 + rb->alloc = alloc; 1.82 + rb->free = free; 1.83 +} 1.84 + 1.85 + 1.86 +void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func) 1.87 +{ 1.88 + rb->cmp = func; 1.89 +} 1.90 + 1.91 +void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls) 1.92 +{ 1.93 + rb->del = func; 1.94 + rb->del_cls = cls; 1.95 +} 1.96 + 1.97 + 1.98 +void rb_clear(struct rbtree *rb) 1.99 +{ 1.100 + del_tree(rb->root, rb->del, rb->del_cls); 1.101 + rb->root = 0; 1.102 +} 1.103 + 1.104 +int rb_copy(struct rbtree *dest, struct rbtree *src) 1.105 +{ 1.106 + struct rbnode *node; 1.107 + 1.108 + rb_clear(dest); 1.109 + rb_begin(src); 1.110 + while((node = rb_next(src))) { 1.111 + if(rb_insert(dest, node->key, node->data) == -1) { 1.112 + return -1; 1.113 + } 1.114 + } 1.115 + return 0; 1.116 +} 1.117 + 1.118 +int rb_size(struct rbtree *rb) 1.119 +{ 1.120 + return count_nodes(rb->root); 1.121 +} 1.122 + 1.123 +int rb_insert(struct rbtree *rb, void *key, void *data) 1.124 +{ 1.125 + rb->root = insert(rb, rb->root, key, data); 1.126 + rb->root->red = 0; 1.127 + return 0; 1.128 +} 1.129 + 1.130 +int rb_inserti(struct rbtree *rb, int key, void *data) 1.131 +{ 1.132 + rb->root = insert(rb, rb->root, INT2PTR(key), data); 1.133 + rb->root->red = 0; 1.134 + return 0; 1.135 +} 1.136 + 1.137 + 1.138 +int rb_delete(struct rbtree *rb, void *key) 1.139 +{ 1.140 + rb->root = delete(rb, rb->root, key); 1.141 + rb->root->red = 0; 1.142 + return 0; 1.143 +} 1.144 + 1.145 +int rb_deletei(struct rbtree *rb, int key) 1.146 +{ 1.147 + rb->root = delete(rb, rb->root, INT2PTR(key)); 1.148 + rb->root->red = 0; 1.149 + return 0; 1.150 +} 1.151 + 1.152 + 1.153 +struct rbnode *rb_find(struct rbtree *rb, void *key) 1.154 +{ 1.155 + struct rbnode *node = rb->root; 1.156 + 1.157 + while(node) { 1.158 + int cmp = rb->cmp(key, node->key); 1.159 + if(cmp == 0) { 1.160 + return node; 1.161 + } 1.162 + node = cmp < 0 ? node->left : node->right; 1.163 + } 1.164 + return 0; 1.165 +} 1.166 + 1.167 +struct rbnode *rb_findi(struct rbtree *rb, int key) 1.168 +{ 1.169 + return rb_find(rb, INT2PTR(key)); 1.170 +} 1.171 + 1.172 + 1.173 +void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls) 1.174 +{ 1.175 + traverse(rb->root, func, cls); 1.176 +} 1.177 + 1.178 + 1.179 +struct rbnode *rb_root(struct rbtree *rb) 1.180 +{ 1.181 + return rb->root; 1.182 +} 1.183 + 1.184 +void rb_begin(struct rbtree *rb) 1.185 +{ 1.186 + rb->rstack = 0; 1.187 + rb->iter = rb->root; 1.188 +} 1.189 + 1.190 +#define push(sp, x) ((x)->next = (sp), (sp) = (x)) 1.191 +#define pop(sp) ((sp) = (sp)->next) 1.192 +#define top(sp) (sp) 1.193 + 1.194 +struct rbnode *rb_next(struct rbtree *rb) 1.195 +{ 1.196 + struct rbnode *res = 0; 1.197 + 1.198 + while(rb->rstack || rb->iter) { 1.199 + if(rb->iter) { 1.200 + push(rb->rstack, rb->iter); 1.201 + rb->iter = rb->iter->left; 1.202 + } else { 1.203 + rb->iter = top(rb->rstack); 1.204 + pop(rb->rstack); 1.205 + res = rb->iter; 1.206 + rb->iter = rb->iter->right; 1.207 + break; 1.208 + } 1.209 + } 1.210 + return res; 1.211 +} 1.212 + 1.213 +void *rb_node_key(struct rbnode *node) 1.214 +{ 1.215 + return node ? node->key : 0; 1.216 +} 1.217 + 1.218 +int rb_node_keyi(struct rbnode *node) 1.219 +{ 1.220 + return node ? PTR2INT(node->key) : 0; 1.221 +} 1.222 + 1.223 +void *rb_node_data(struct rbnode *node) 1.224 +{ 1.225 + return node ? node->data : 0; 1.226 +} 1.227 + 1.228 +static int cmpaddr(const void *ap, const void *bp) 1.229 +{ 1.230 + return ap < bp ? -1 : (ap > bp ? 1 : 0); 1.231 +} 1.232 + 1.233 +static int cmpint(const void *ap, const void *bp) 1.234 +{ 1.235 + return PTR2INT(ap) - PTR2INT(bp); 1.236 +} 1.237 + 1.238 + 1.239 +/* ---- left-leaning 2-3 red-black implementation ---- */ 1.240 + 1.241 +/* helper prototypes */ 1.242 +static int is_red(struct rbnode *tree); 1.243 +static void color_flip(struct rbnode *tree); 1.244 +static struct rbnode *rot_left(struct rbnode *a); 1.245 +static struct rbnode *rot_right(struct rbnode *a); 1.246 +static struct rbnode *find_min(struct rbnode *tree); 1.247 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree); 1.248 +/*static struct rbnode *move_red_right(struct rbnode *tree);*/ 1.249 +static struct rbnode *move_red_left(struct rbnode *tree); 1.250 +static struct rbnode *fix_up(struct rbnode *tree); 1.251 + 1.252 +static int count_nodes(struct rbnode *node) 1.253 +{ 1.254 + if(!node) 1.255 + return 0; 1.256 + 1.257 + return 1 + count_nodes(node->left) + count_nodes(node->right); 1.258 +} 1.259 + 1.260 +static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls) 1.261 +{ 1.262 + if(!node) 1.263 + return; 1.264 + 1.265 + del_tree(node->left, delfunc, cls); 1.266 + del_tree(node->right, delfunc, cls); 1.267 + 1.268 + if(delfunc) { 1.269 + delfunc(node, cls); 1.270 + } 1.271 + free(node); 1.272 +} 1.273 + 1.274 +static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data) 1.275 +{ 1.276 + int cmp; 1.277 + 1.278 + if(!tree) { 1.279 + struct rbnode *node = rb->alloc(sizeof *node); 1.280 + node->red = 1; 1.281 + node->key = key; 1.282 + node->data = data; 1.283 + node->left = node->right = 0; 1.284 + return node; 1.285 + } 1.286 + 1.287 + cmp = rb->cmp(key, tree->key); 1.288 + 1.289 + if(cmp < 0) { 1.290 + tree->left = insert(rb, tree->left, key, data); 1.291 + } else if(cmp > 0) { 1.292 + tree->right = insert(rb, tree->right, key, data); 1.293 + } else { 1.294 + tree->data = data; 1.295 + } 1.296 + 1.297 + /* fix right-leaning reds */ 1.298 + if(is_red(tree->right)) { 1.299 + tree = rot_left(tree); 1.300 + } 1.301 + /* fix two reds in a row */ 1.302 + if(is_red(tree->left) && is_red(tree->left->left)) { 1.303 + tree = rot_right(tree); 1.304 + } 1.305 + 1.306 + /* if 4-node, split it by color inversion */ 1.307 + if(is_red(tree->left) && is_red(tree->right)) { 1.308 + color_flip(tree); 1.309 + } 1.310 + 1.311 + return tree; 1.312 +} 1.313 + 1.314 +static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key) 1.315 +{ 1.316 + int cmp; 1.317 + 1.318 + if(!tree) { 1.319 + return 0; 1.320 + } 1.321 + 1.322 + cmp = rb->cmp(key, tree->key); 1.323 + 1.324 + if(cmp < 0) { 1.325 + if(!is_red(tree->left) && !is_red(tree->left->left)) { 1.326 + tree = move_red_left(tree); 1.327 + } 1.328 + tree->left = delete(rb, tree->left, key); 1.329 + } else { 1.330 + /* need reds on the right */ 1.331 + if(is_red(tree->left)) { 1.332 + tree = rot_right(tree); 1.333 + } 1.334 + 1.335 + /* found it at the bottom (XXX what certifies left is null?) */ 1.336 + if(cmp == 0 && !tree->right) { 1.337 + if(rb->del) { 1.338 + rb->del(tree, rb->del_cls); 1.339 + } 1.340 + rb->free(tree); 1.341 + return 0; 1.342 + } 1.343 + 1.344 + if(!is_red(tree->right) && !is_red(tree->right->left)) { 1.345 + tree = move_red_left(tree); 1.346 + } 1.347 + 1.348 + if(key == tree->key) { 1.349 + struct rbnode *rmin = find_min(tree->right); 1.350 + tree->key = rmin->key; 1.351 + tree->data = rmin->data; 1.352 + tree->right = del_min(rb, tree->right); 1.353 + } else { 1.354 + tree->right = delete(rb, tree->right, key); 1.355 + } 1.356 + } 1.357 + 1.358 + return fix_up(tree); 1.359 +} 1.360 + 1.361 +/*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key) 1.362 +{ 1.363 + int cmp; 1.364 + 1.365 + if(!node) 1.366 + return 0; 1.367 + 1.368 + if((cmp = rb->cmp(key, node->key)) == 0) { 1.369 + return node; 1.370 + } 1.371 + return find(rb, cmp < 0 ? node->left : node->right, key); 1.372 +}*/ 1.373 + 1.374 +static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls) 1.375 +{ 1.376 + if(!node) 1.377 + return; 1.378 + 1.379 + traverse(node->left, func, cls); 1.380 + func(node, cls); 1.381 + traverse(node->right, func, cls); 1.382 +} 1.383 + 1.384 +/* helpers */ 1.385 + 1.386 +static int is_red(struct rbnode *tree) 1.387 +{ 1.388 + return tree && tree->red; 1.389 +} 1.390 + 1.391 +static void color_flip(struct rbnode *tree) 1.392 +{ 1.393 + tree->red = !tree->red; 1.394 + tree->left->red = !tree->left->red; 1.395 + tree->right->red = !tree->right->red; 1.396 +} 1.397 + 1.398 +static struct rbnode *rot_left(struct rbnode *a) 1.399 +{ 1.400 + struct rbnode *b = a->right; 1.401 + a->right = b->left; 1.402 + b->left = a; 1.403 + b->red = a->red; 1.404 + a->red = 1; 1.405 + return b; 1.406 +} 1.407 + 1.408 +static struct rbnode *rot_right(struct rbnode *a) 1.409 +{ 1.410 + struct rbnode *b = a->left; 1.411 + a->left = b->right; 1.412 + b->right = a; 1.413 + b->red = a->red; 1.414 + a->red = 1; 1.415 + return b; 1.416 +} 1.417 + 1.418 +static struct rbnode *find_min(struct rbnode *tree) 1.419 +{ 1.420 + if(!tree) 1.421 + return 0; 1.422 + 1.423 + while(tree->left) { 1.424 + tree = tree->left; 1.425 + } 1.426 + return tree; 1.427 +} 1.428 + 1.429 +static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree) 1.430 +{ 1.431 + if(!tree->left) { 1.432 + if(rb->del) { 1.433 + rb->del(tree->left, rb->del_cls); 1.434 + } 1.435 + rb->free(tree->left); 1.436 + return 0; 1.437 + } 1.438 + 1.439 + /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */ 1.440 + if(!is_red(tree->left) && !is_red(tree->left->left)) { 1.441 + tree = move_red_left(tree); 1.442 + } 1.443 + tree->left = del_min(rb, tree->left); 1.444 + 1.445 + /* fix right-reds, red-reds, and split 4-nodes on the way up */ 1.446 + return fix_up(tree); 1.447 +} 1.448 + 1.449 +#if 0 1.450 +/* push a red link on this node to the right */ 1.451 +static struct rbnode *move_red_right(struct rbnode *tree) 1.452 +{ 1.453 + /* flipping it makes both children go red, so we have a red to the right */ 1.454 + color_flip(tree); 1.455 + 1.456 + /* if after the flip we've got a red-red situation to the left, fix it */ 1.457 + if(is_red(tree->left->left)) { 1.458 + tree = rot_right(tree); 1.459 + color_flip(tree); 1.460 + } 1.461 + return tree; 1.462 +} 1.463 +#endif 1.464 + 1.465 +/* push a red link on this node to the left */ 1.466 +static struct rbnode *move_red_left(struct rbnode *tree) 1.467 +{ 1.468 + /* flipping it makes both children go red, so we have a red to the left */ 1.469 + color_flip(tree); 1.470 + 1.471 + /* if after the flip we've got a red-red on the right-left, fix it */ 1.472 + if(is_red(tree->right->left)) { 1.473 + tree->right = rot_right(tree->right); 1.474 + tree = rot_left(tree); 1.475 + color_flip(tree); 1.476 + } 1.477 + return tree; 1.478 +} 1.479 + 1.480 +static struct rbnode *fix_up(struct rbnode *tree) 1.481 +{ 1.482 + /* fix right-leaning */ 1.483 + if(is_red(tree->right)) { 1.484 + tree = rot_left(tree); 1.485 + } 1.486 + /* change invalid red-red pairs into a proper 4-node */ 1.487 + if(is_red(tree->left) && is_red(tree->left->left)) { 1.488 + tree = rot_right(tree); 1.489 + } 1.490 + /* split 4-nodes */ 1.491 + if(is_red(tree->left) && is_red(tree->right)) { 1.492 + color_flip(tree); 1.493 + } 1.494 + return tree; 1.495 +}