| rev |
line source |
|
nuclear@68
|
1 #ifndef RBTREE_H_
|
|
nuclear@68
|
2 #define RBTREE_H_
|
|
nuclear@68
|
3
|
|
nuclear@86
|
4 #include <stdlib.h> /* for size_t */
|
|
nuclear@86
|
5
|
|
nuclear@68
|
6 struct rbtree;
|
|
nuclear@68
|
7 struct rbnode;
|
|
nuclear@68
|
8
|
|
nuclear@68
|
9
|
|
nuclear@68
|
10 typedef void *(*rb_alloc_func_t)(size_t);
|
|
nuclear@68
|
11 typedef void (*rb_free_func_t)(void*);
|
|
nuclear@68
|
12
|
|
nuclear@68
|
13 typedef int (*rb_cmp_func_t)(void*, void*);
|
|
nuclear@68
|
14 typedef void (*rb_del_func_t)(struct rbnode*, void*);
|
|
nuclear@68
|
15
|
|
nuclear@68
|
16
|
|
nuclear@68
|
17 struct rbtree {
|
|
nuclear@68
|
18 struct rbnode *root;
|
|
nuclear@68
|
19
|
|
nuclear@68
|
20 rb_alloc_func_t alloc;
|
|
nuclear@68
|
21 rb_free_func_t free;
|
|
nuclear@68
|
22
|
|
nuclear@68
|
23 rb_cmp_func_t cmp;
|
|
nuclear@68
|
24 rb_del_func_t del;
|
|
nuclear@68
|
25 void *del_cls;
|
|
nuclear@68
|
26
|
|
nuclear@68
|
27 struct rbnode *rstack, *iter;
|
|
nuclear@68
|
28 };
|
|
nuclear@68
|
29
|
|
nuclear@68
|
30
|
|
nuclear@68
|
31 struct rbnode {
|
|
nuclear@68
|
32 void *key, *data;
|
|
nuclear@68
|
33 int red;
|
|
nuclear@68
|
34 struct rbnode *left, *right;
|
|
nuclear@68
|
35 struct rbnode *next; /* for iterator stack */
|
|
nuclear@68
|
36 };
|
|
nuclear@68
|
37
|
|
nuclear@68
|
38 #define RB_KEY_ADDR (rb_cmp_func_t)(0)
|
|
nuclear@68
|
39 #define RB_KEY_INT (rb_cmp_func_t)(1)
|
|
nuclear@68
|
40 #define RB_KEY_STRING (rb_cmp_func_t)(3)
|
|
nuclear@68
|
41
|
|
nuclear@68
|
42
|
|
nuclear@68
|
43 #ifdef __cplusplus
|
|
nuclear@68
|
44 extern "C" {
|
|
nuclear@68
|
45 #endif
|
|
nuclear@68
|
46
|
|
nuclear@68
|
47 struct rbtree *rb_create(rb_cmp_func_t cmp_func);
|
|
nuclear@68
|
48 void rb_free(struct rbtree *rb);
|
|
nuclear@68
|
49
|
|
nuclear@68
|
50 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
|
|
nuclear@68
|
51 void rb_destroy(struct rbtree *rb);
|
|
nuclear@68
|
52
|
|
nuclear@69
|
53 void rb_clear(struct rbtree *tree);
|
|
nuclear@69
|
54 int rb_copy(struct rbtree *dest, struct rbtree *src);
|
|
nuclear@69
|
55
|
|
nuclear@68
|
56 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
|
|
nuclear@68
|
57 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
|
|
nuclear@68
|
58 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
|
|
nuclear@68
|
59
|
|
nuclear@68
|
60 int rb_size(struct rbtree *rb);
|
|
nuclear@68
|
61
|
|
nuclear@68
|
62 int rb_insert(struct rbtree *rb, void *key, void *data);
|
|
nuclear@68
|
63 int rb_inserti(struct rbtree *rb, int key, void *data);
|
|
nuclear@68
|
64
|
|
nuclear@68
|
65 int rb_delete(struct rbtree *rb, void *key);
|
|
nuclear@68
|
66 int rb_deletei(struct rbtree *rb, int key);
|
|
nuclear@68
|
67
|
|
nuclear@68
|
68 void *rb_find(struct rbtree *rb, void *key);
|
|
nuclear@68
|
69 void *rb_findi(struct rbtree *rb, int key);
|
|
nuclear@68
|
70
|
|
nuclear@68
|
71 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
|
|
nuclear@68
|
72
|
|
nuclear@68
|
73 struct rbnode *rb_root(struct rbtree *rb);
|
|
nuclear@68
|
74
|
|
nuclear@68
|
75 void rb_begin(struct rbtree *rb);
|
|
nuclear@68
|
76 struct rbnode *rb_next(struct rbtree *rb);
|
|
nuclear@68
|
77
|
|
nuclear@68
|
78 void *rb_node_key(struct rbnode *node);
|
|
nuclear@68
|
79 int rb_node_keyi(struct rbnode *node);
|
|
nuclear@68
|
80 void *rb_node_data(struct rbnode *node);
|
|
nuclear@68
|
81
|
|
nuclear@69
|
82
|
|
nuclear@69
|
83 void rb_dbg_print_tree(struct rbtree *tree);
|
|
nuclear@69
|
84
|
|
nuclear@68
|
85 #ifdef __cplusplus
|
|
nuclear@68
|
86 }
|
|
nuclear@68
|
87 #endif
|
|
nuclear@68
|
88
|
|
nuclear@68
|
89
|
|
nuclear@68
|
90 #endif /* RBTREE_H_ */
|
