libresman

annotate src/rbtree.c @ 23:f8e5a1491275

find changesets by author, revision, files, or words in the commit message
win32 file change notification attempt1 (failed)
author John Tsiombikas <nuclear@member.fsf.org>
date Thu, 13 Feb 2014 13:17:07 +0200
parents fe0dbdfbe403
children
rev   line source
nuclear@21 1 #include <stdio.h>
nuclear@21 2 #include <stdlib.h>
nuclear@23 3 #ifndef _MSC_VER
nuclear@21 4 #include <stdint.h>
nuclear@23 5 #endif
nuclear@21 6 #include <string.h>
nuclear@21 7 #include "rbtree.h"
nuclear@21 8
nuclear@21 9 #define INT2PTR(x) ((void*)(intptr_t)(x))
nuclear@21 10 #define PTR2INT(x) ((int)(intptr_t)(x))
nuclear@21 11
nuclear@21 12 struct rbtree {
nuclear@21 13 struct rbnode *root;
nuclear@21 14
nuclear@21 15 rb_alloc_func_t alloc;
nuclear@21 16 rb_free_func_t free;
nuclear@21 17
nuclear@21 18 rb_cmp_func_t cmp;
nuclear@21 19 rb_del_func_t del;
nuclear@21 20 void *del_cls;
nuclear@21 21
nuclear@21 22 struct rbnode *rstack, *iter;
nuclear@21 23 };
nuclear@21 24
nuclear@21 25 static int cmpaddr(const void *ap, const void *bp);
nuclear@21 26 static int cmpint(const void *ap, const void *bp);
nuclear@21 27
nuclear@21 28 static int count_nodes(struct rbnode *node);
nuclear@21 29 static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
nuclear@21 30 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
nuclear@21 31 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
nuclear@21 32 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/
nuclear@21 33 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
nuclear@21 34
nuclear@21 35 struct rbtree *rb_create(rb_cmp_func_t cmp_func)
nuclear@21 36 {
nuclear@21 37 struct rbtree *rb;
nuclear@21 38
nuclear@21 39 if(!(rb = malloc(sizeof *rb))) {
nuclear@21 40 return 0;
nuclear@21 41 }
nuclear@21 42 if(rb_init(rb, cmp_func) == -1) {
nuclear@21 43 free(rb);
nuclear@21 44 return 0;
nuclear@21 45 }
nuclear@21 46 return rb;
nuclear@21 47 }
nuclear@21 48
nuclear@21 49 void rb_free(struct rbtree *rb)
nuclear@21 50 {
nuclear@21 51 rb_destroy(rb);
nuclear@21 52 free(rb);
nuclear@21 53 }
nuclear@21 54
nuclear@21 55
nuclear@21 56 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
nuclear@21 57 {
nuclear@21 58 memset(rb, 0, sizeof *rb);
nuclear@21 59
nuclear@21 60 if(cmp_func == RB_KEY_INT) {
nuclear@21 61 rb->cmp = cmpint;
nuclear@21 62 } else if(cmp_func == RB_KEY_STRING) {
nuclear@21 63 rb->cmp = (rb_cmp_func_t)strcmp;
nuclear@21 64 } else {
nuclear@21 65 rb->cmp = cmpaddr;
nuclear@21 66 }
nuclear@21 67
nuclear@21 68 rb->alloc = malloc;
nuclear@21 69 rb->free = free;
nuclear@21 70 return 0;
nuclear@21 71 }
nuclear@21 72
nuclear@21 73 void rb_destroy(struct rbtree *rb)
nuclear@21 74 {
nuclear@21 75 del_tree(rb->root, rb->del, rb->del_cls);
nuclear@21 76 }
nuclear@21 77
nuclear@21 78 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
nuclear@21 79 {
nuclear@21 80 rb->alloc = alloc;
nuclear@21 81 rb->free = free;
nuclear@21 82 }
nuclear@21 83
nuclear@21 84
nuclear@21 85 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
nuclear@21 86 {
nuclear@21 87 rb->cmp = func;
nuclear@21 88 }
nuclear@21 89
nuclear@21 90 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
nuclear@21 91 {
nuclear@21 92 rb->del = func;
nuclear@21 93 rb->del_cls = cls;
nuclear@21 94 }
nuclear@21 95
nuclear@21 96
nuclear@21 97 void rb_clear(struct rbtree *rb)
nuclear@21 98 {
nuclear@21 99 del_tree(rb->root, rb->del, rb->del_cls);
nuclear@21 100 rb->root = 0;
nuclear@21 101 }
nuclear@21 102
nuclear@21 103 int rb_copy(struct rbtree *dest, struct rbtree *src)
nuclear@21 104 {
nuclear@21 105 struct rbnode *node;
nuclear@21 106
nuclear@21 107 rb_clear(dest);
nuclear@21 108 rb_begin(src);
nuclear@21 109 while((node = rb_next(src))) {
nuclear@21 110 if(rb_insert(dest, node->key, node->data) == -1) {
nuclear@21 111 return -1;
nuclear@21 112 }
nuclear@21 113 }
nuclear@21 114 return 0;
nuclear@21 115 }
nuclear@21 116
nuclear@21 117 int rb_size(struct rbtree *rb)
nuclear@21 118 {
nuclear@21 119 return count_nodes(rb->root);
nuclear@21 120 }
nuclear@21 121
nuclear@21 122 int rb_insert(struct rbtree *rb, void *key, void *data)
nuclear@21 123 {
nuclear@21 124 rb->root = insert(rb, rb->root, key, data);
nuclear@21 125 rb->root->red = 0;
nuclear@21 126 return 0;
nuclear@21 127 }
nuclear@21 128
nuclear@21 129 int rb_inserti(struct rbtree *rb, int key, void *data)
nuclear@21 130 {
nuclear@21 131 rb->root = insert(rb, rb->root, INT2PTR(key), data);
nuclear@21 132 rb->root->red = 0;
nuclear@21 133 return 0;
nuclear@21 134 }
nuclear@21 135
nuclear@21 136
nuclear@21 137 int rb_delete(struct rbtree *rb, void *key)
nuclear@21 138 {
nuclear@21 139 rb->root = delete(rb, rb->root, key);
nuclear@21 140 rb->root->red = 0;
nuclear@21 141 return 0;
nuclear@21 142 }
nuclear@21 143
nuclear@21 144 int rb_deletei(struct rbtree *rb, int key)
nuclear@21 145 {
nuclear@21 146 rb->root = delete(rb, rb->root, INT2PTR(key));
nuclear@21 147 rb->root->red = 0;
nuclear@21 148 return 0;
nuclear@21 149 }
nuclear@21 150
nuclear@21 151
nuclear@21 152 void *rb_find(struct rbtree *rb, void *key)
nuclear@21 153 {
nuclear@21 154 struct rbnode *node = rb->root;
nuclear@21 155
nuclear@21 156 while(node) {
nuclear@21 157 int cmp = rb->cmp(key, node->key);
nuclear@21 158 if(cmp == 0) {
nuclear@21 159 return node->data;
nuclear@21 160 }
nuclear@21 161 node = cmp < 0 ? node->left : node->right;
nuclear@21 162 }
nuclear@21 163 return 0;
nuclear@21 164 }
nuclear@21 165
nuclear@21 166 void *rb_findi(struct rbtree *rb, int key)
nuclear@21 167 {
nuclear@21 168 return rb_find(rb, INT2PTR(key));
nuclear@21 169 }
nuclear@21 170
nuclear@21 171
nuclear@21 172 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
nuclear@21 173 {
nuclear@21 174 traverse(rb->root, func, cls);
nuclear@21 175 }
nuclear@21 176
nuclear@21 177
nuclear@21 178 struct rbnode *rb_root(struct rbtree *rb)
nuclear@21 179 {
nuclear@21 180 return rb->root;
nuclear@21 181 }
nuclear@21 182
nuclear@21 183 void rb_begin(struct rbtree *rb)
nuclear@21 184 {
nuclear@21 185 rb->rstack = 0;
nuclear@21 186 rb->iter = rb->root;
nuclear@21 187 }
nuclear@21 188
nuclear@21 189 #define push(sp, x) ((x)->next = (sp), (sp) = (x))
nuclear@21 190 #define pop(sp) ((sp) = (sp)->next)
nuclear@21 191 #define top(sp) (sp)
nuclear@21 192
nuclear@21 193 struct rbnode *rb_next(struct rbtree *rb)
nuclear@21 194 {
nuclear@21 195 struct rbnode *res = 0;
nuclear@21 196
nuclear@21 197 while(rb->rstack || rb->iter) {
nuclear@21 198 if(rb->iter) {
nuclear@21 199 push(rb->rstack, rb->iter);
nuclear@21 200 rb->iter = rb->iter->left;
nuclear@21 201 } else {
nuclear@21 202 rb->iter = top(rb->rstack);
nuclear@21 203 pop(rb->rstack);
nuclear@21 204 res = rb->iter;
nuclear@21 205 rb->iter = rb->iter->right;
nuclear@21 206 break;
nuclear@21 207 }
nuclear@21 208 }
nuclear@21 209 return res;
nuclear@21 210 }
nuclear@21 211
nuclear@21 212 void *rb_node_key(struct rbnode *node)
nuclear@21 213 {
nuclear@21 214 return node ? node->key : 0;
nuclear@21 215 }
nuclear@21 216
nuclear@21 217 int rb_node_keyi(struct rbnode *node)
nuclear@21 218 {
nuclear@21 219 return node ? PTR2INT(node->key) : 0;
nuclear@21 220 }
nuclear@21 221
nuclear@21 222 void *rb_node_data(struct rbnode *node)
nuclear@21 223 {
nuclear@21 224 return node ? node->data : 0;
nuclear@21 225 }
nuclear@21 226
nuclear@21 227 static int cmpaddr(const void *ap, const void *bp)
nuclear@21 228 {
nuclear@21 229 return ap < bp ? -1 : (ap > bp ? 1 : 0);
nuclear@21 230 }
nuclear@21 231
nuclear@21 232 static int cmpint(const void *ap, const void *bp)
nuclear@21 233 {
nuclear@21 234 return PTR2INT(ap) - PTR2INT(bp);
nuclear@21 235 }
nuclear@21 236
nuclear@21 237
nuclear@21 238 /* ---- left-leaning 2-3 red-black implementation ---- */
nuclear@21 239
nuclear@21 240 /* helper prototypes */
nuclear@21 241 static int is_red(struct rbnode *tree);
nuclear@21 242 static void color_flip(struct rbnode *tree);
nuclear@21 243 static struct rbnode *rot_left(struct rbnode *a);
nuclear@21 244 static struct rbnode *rot_right(struct rbnode *a);
nuclear@21 245 static struct rbnode *find_min(struct rbnode *tree);
nuclear@21 246 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
nuclear@21 247 /*static struct rbnode *move_red_right(struct rbnode *tree);*/
nuclear@21 248 static struct rbnode *move_red_left(struct rbnode *tree);
nuclear@21 249 static struct rbnode *fix_up(struct rbnode *tree);
nuclear@21 250
nuclear@21 251 static int count_nodes(struct rbnode *node)
nuclear@21 252 {
nuclear@21 253 if(!node)
nuclear@21 254 return 0;
nuclear@21 255
nuclear@21 256 return 1 + count_nodes(node->left) + count_nodes(node->right);
nuclear@21 257 }
nuclear@21 258
nuclear@21 259 static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
nuclear@21 260 {
nuclear@21 261 if(!node)
nuclear@21 262 return;
nuclear@21 263
nuclear@21 264 del_tree(node->left, delfunc, cls);
nuclear@21 265 del_tree(node->right, delfunc, cls);
nuclear@21 266
nuclear@21 267 if(delfunc) {
nuclear@21 268 delfunc(node, cls);
nuclear@21 269 }
nuclear@21 270 free(node);
nuclear@21 271 }
nuclear@21 272
nuclear@21 273 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
nuclear@21 274 {
nuclear@21 275 int cmp;
nuclear@21 276
nuclear@21 277 if(!tree) {
nuclear@21 278 struct rbnode *node = rb->alloc(sizeof *node);
nuclear@21 279 node->red = 1;
nuclear@21 280 node->key = key;
nuclear@21 281 node->data = data;
nuclear@21 282 node->left = node->right = 0;
nuclear@21 283 return node;
nuclear@21 284 }
nuclear@21 285
nuclear@21 286 cmp = rb->cmp(key, tree->key);
nuclear@21 287
nuclear@21 288 if(cmp < 0) {
nuclear@21 289 tree->left = insert(rb, tree->left, key, data);
nuclear@21 290 } else if(cmp > 0) {
nuclear@21 291 tree->right = insert(rb, tree->right, key, data);
nuclear@21 292 } else {
nuclear@21 293 tree->data = data;
nuclear@21 294 }
nuclear@21 295
nuclear@21 296 /* fix right-leaning reds */
nuclear@21 297 if(is_red(tree->right)) {
nuclear@21 298 tree = rot_left(tree);
nuclear@21 299 }
nuclear@21 300 /* fix two reds in a row */
nuclear@21 301 if(is_red(tree->left) && is_red(tree->left->left)) {
nuclear@21 302 tree = rot_right(tree);
nuclear@21 303 }
nuclear@21 304
nuclear@21 305 /* if 4-node, split it by color inversion */
nuclear@21 306 if(is_red(tree->left) && is_red(tree->right)) {
nuclear@21 307 color_flip(tree);
nuclear@21 308 }
nuclear@21 309
nuclear@21 310 return tree;
nuclear@21 311 }
nuclear@21 312
nuclear@21 313 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
nuclear@21 314 {
nuclear@21 315 int cmp;
nuclear@21 316
nuclear@21 317 if(!tree) {
nuclear@21 318 return 0;
nuclear@21 319 }
nuclear@21 320
nuclear@21 321 cmp = rb->cmp(key, tree->key);
nuclear@21 322
nuclear@21 323 if(cmp < 0) {
nuclear@21 324 if(!is_red(tree->left) && !is_red(tree->left->left)) {
nuclear@21 325 tree = move_red_left(tree);
nuclear@21 326 }
nuclear@21 327 tree->left = delete(rb, tree->left, key);
nuclear@21 328 } else {
nuclear@21 329 /* need reds on the right */
nuclear@21 330 if(is_red(tree->left)) {
nuclear@21 331 tree = rot_right(tree);
nuclear@21 332 }
nuclear@21 333
nuclear@21 334 /* found it at the bottom (XXX what certifies left is null?) */
nuclear@21 335 if(cmp == 0 && !tree->right) {
nuclear@21 336 if(rb->del) {
nuclear@21 337 rb->del(tree, rb->del_cls);
nuclear@21 338 }
nuclear@21 339 rb->free(tree);
nuclear@21 340 return 0;
nuclear@21 341 }
nuclear@21 342
nuclear@21 343 if(!is_red(tree->right) && !is_red(tree->right->left)) {
nuclear@21 344 tree = move_red_left(tree);
nuclear@21 345 }
nuclear@21 346
nuclear@21 347 if(key == tree->key) {
nuclear@21 348 struct rbnode *rmin = find_min(tree->right);
nuclear@21 349 tree->key = rmin->key;
nuclear@21 350 tree->data = rmin->data;
nuclear@21 351 tree->right = del_min(rb, tree->right);
nuclear@21 352 } else {
nuclear@21 353 tree->right = delete(rb, tree->right, key);
nuclear@21 354 }
nuclear@21 355 }
nuclear@21 356
nuclear@21 357 return fix_up(tree);
nuclear@21 358 }
nuclear@21 359
nuclear@21 360 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
nuclear@21 361 {
nuclear@21 362 int cmp;
nuclear@21 363
nuclear@21 364 if(!node)
nuclear@21 365 return 0;
nuclear@21 366
nuclear@21 367 if((cmp = rb->cmp(key, node->key)) == 0) {
nuclear@21 368 return node;
nuclear@21 369 }
nuclear@21 370 return find(rb, cmp < 0 ? node->left : node->right, key);
nuclear@21 371 }*/
nuclear@21 372
nuclear@21 373 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
nuclear@21 374 {
nuclear@21 375 if(!node)
nuclear@21 376 return;
nuclear@21 377
nuclear@21 378 traverse(node->left, func, cls);
nuclear@21 379 func(node, cls);
nuclear@21 380 traverse(node->right, func, cls);
nuclear@21 381 }
nuclear@21 382
nuclear@21 383 /* helpers */
nuclear@21 384
nuclear@21 385 static int is_red(struct rbnode *tree)
nuclear@21 386 {
nuclear@21 387 return tree && tree->red;
nuclear@21 388 }
nuclear@21 389
nuclear@21 390 static void color_flip(struct rbnode *tree)
nuclear@21 391 {
nuclear@21 392 tree->red = !tree->red;
nuclear@21 393 tree->left->red = !tree->left->red;
nuclear@21 394 tree->right->red = !tree->right->red;
nuclear@21 395 }
nuclear@21 396
nuclear@21 397 static struct rbnode *rot_left(struct rbnode *a)
nuclear@21 398 {
nuclear@21 399 struct rbnode *b = a->right;
nuclear@21 400 a->right = b->left;
nuclear@21 401 b->left = a;
nuclear@21 402 b->red = a->red;
nuclear@21 403 a->red = 1;
nuclear@21 404 return b;
nuclear@21 405 }
nuclear@21 406
nuclear@21 407 static struct rbnode *rot_right(struct rbnode *a)
nuclear@21 408 {
nuclear@21 409 struct rbnode *b = a->left;
nuclear@21 410 a->left = b->right;
nuclear@21 411 b->right = a;
nuclear@21 412 b->red = a->red;
nuclear@21 413 a->red = 1;
nuclear@21 414 return b;
nuclear@21 415 }
nuclear@21 416
nuclear@21 417 static struct rbnode *find_min(struct rbnode *tree)
nuclear@21 418 {
nuclear@23 419 struct rbnode *node = tree;
nuclear@21 420
nuclear@21 421 if(!tree)
nuclear@21 422 return 0;
nuclear@21 423
nuclear@21 424 while(node->left) {
nuclear@21 425 node = node->left;
nuclear@21 426 }
nuclear@21 427 return node;
nuclear@21 428 }
nuclear@21 429
nuclear@21 430 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
nuclear@21 431 {
nuclear@21 432 if(!tree->left) {
nuclear@21 433 if(rb->del) {
nuclear@21 434 rb->del(tree->left, rb->del_cls);
nuclear@21 435 }
nuclear@21 436 rb->free(tree->left);
nuclear@21 437 return 0;
nuclear@21 438 }
nuclear@21 439
nuclear@21 440 /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
nuclear@21 441 if(!is_red(tree->left) && !is_red(tree->left->left)) {
nuclear@21 442 tree = move_red_left(tree);
nuclear@21 443 }
nuclear@21 444 tree->left = del_min(rb, tree->left);
nuclear@21 445
nuclear@21 446 /* fix right-reds, red-reds, and split 4-nodes on the way up */
nuclear@21 447 return fix_up(tree);
nuclear@21 448 }
nuclear@21 449
nuclear@21 450 #if 0
nuclear@21 451 /* push a red link on this node to the right */
nuclear@21 452 static struct rbnode *move_red_right(struct rbnode *tree)
nuclear@21 453 {
nuclear@21 454 /* flipping it makes both children go red, so we have a red to the right */
nuclear@21 455 color_flip(tree);
nuclear@21 456
nuclear@21 457 /* if after the flip we've got a red-red situation to the left, fix it */
nuclear@21 458 if(is_red(tree->left->left)) {
nuclear@21 459 tree = rot_right(tree);
nuclear@21 460 color_flip(tree);
nuclear@21 461 }
nuclear@21 462 return tree;
nuclear@21 463 }
nuclear@21 464 #endif
nuclear@21 465
nuclear@21 466 /* push a red link on this node to the left */
nuclear@21 467 static struct rbnode *move_red_left(struct rbnode *tree)
nuclear@21 468 {
nuclear@21 469 /* flipping it makes both children go red, so we have a red to the left */
nuclear@21 470 color_flip(tree);
nuclear@21 471
nuclear@21 472 /* if after the flip we've got a red-red on the right-left, fix it */
nuclear@21 473 if(is_red(tree->right->left)) {
nuclear@21 474 tree->right = rot_right(tree->right);
nuclear@21 475 tree = rot_left(tree);
nuclear@21 476 color_flip(tree);
nuclear@21 477 }
nuclear@21 478 return tree;
nuclear@21 479 }
nuclear@21 480
nuclear@21 481 static struct rbnode *fix_up(struct rbnode *tree)
nuclear@21 482 {
nuclear@21 483 /* fix right-leaning */
nuclear@21 484 if(is_red(tree->right)) {
nuclear@21 485 tree = rot_left(tree);
nuclear@21 486 }
nuclear@21 487 /* change invalid red-red pairs into a proper 4-node */
nuclear@21 488 if(is_red(tree->left) && is_red(tree->left->left)) {
nuclear@21 489 tree = rot_right(tree);
nuclear@21 490 }
nuclear@21 491 /* split 4-nodes */
nuclear@21 492 if(is_red(tree->left) && is_red(tree->right)) {
nuclear@21 493 color_flip(tree);
nuclear@21 494 }
nuclear@21 495 return tree;
nuclear@21 496 }