kern

view src/rbtree.h @ 69:b45e2d5f0ae1

find changesets by author, revision, files, or words in the commit message
ok I *think* i've fixed it now
author John Tsiombikas <nuclear@member.fsf.org>
date Wed, 12 Oct 2011 14:39:40 +0300
parents 0a205396e1a0
children 379332fc1667
line source
1 #ifndef RBTREE_H_
2 #define RBTREE_H_
3
4 struct rbtree;
5 struct rbnode;
6
7
8 typedef void *(*rb_alloc_func_t)(size_t);
9 typedef void (*rb_free_func_t)(void*);
10
11 typedef int (*rb_cmp_func_t)(void*, void*);
12 typedef void (*rb_del_func_t)(struct rbnode*, void*);
13
14
15 struct rbtree {
16 struct rbnode *root;
17
18 rb_alloc_func_t alloc;
19 rb_free_func_t free;
20
21 rb_cmp_func_t cmp;
22 rb_del_func_t del;
23 void *del_cls;
24
25 struct rbnode *rstack, *iter;
26 };
27
28
29 struct rbnode {
30 void *key, *data;
31 int red;
32 struct rbnode *left, *right;
33 struct rbnode *next; /* for iterator stack */
34 };
35
36 #define RB_KEY_ADDR (rb_cmp_func_t)(0)
37 #define RB_KEY_INT (rb_cmp_func_t)(1)
38 #define RB_KEY_STRING (rb_cmp_func_t)(3)
39
40
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44
45 struct rbtree *rb_create(rb_cmp_func_t cmp_func);
46 void rb_free(struct rbtree *rb);
47
48 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
49 void rb_destroy(struct rbtree *rb);
50
51 void rb_clear(struct rbtree *tree);
52 int rb_copy(struct rbtree *dest, struct rbtree *src);
53
54 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
55 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
56 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
57
58 int rb_size(struct rbtree *rb);
59
60 int rb_insert(struct rbtree *rb, void *key, void *data);
61 int rb_inserti(struct rbtree *rb, int key, void *data);
62
63 int rb_delete(struct rbtree *rb, void *key);
64 int rb_deletei(struct rbtree *rb, int key);
65
66 void *rb_find(struct rbtree *rb, void *key);
67 void *rb_findi(struct rbtree *rb, int key);
68
69 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
70
71 struct rbnode *rb_root(struct rbtree *rb);
72
73 void rb_begin(struct rbtree *rb);
74 struct rbnode *rb_next(struct rbtree *rb);
75
76 void *rb_node_key(struct rbnode *node);
77 int rb_node_keyi(struct rbnode *node);
78 void *rb_node_data(struct rbnode *node);
79
80
81 void rb_dbg_print_tree(struct rbtree *tree);
82
83 #ifdef __cplusplus
84 }
85 #endif
86
87
88 #endif /* RBTREE_H_ */