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