1 #ifndef RBTREE_H
2 #define RBTREE_H
3 
4 #ifdef __cplusplus
5 extern "C" {
6 #endif
7 
8 enum rb_color { RB_RED, RB_BLACK };
9 
10 struct rb_node
11 {
12 	struct rb_node *left;
13 	struct rb_node *right;
14 	struct rb_node *parent;
15 	enum rb_color color;
16 	void *data;
17 };
18 
19 struct rb_tree
20 {
21 	struct rb_node *root;
22 
23 	/* compare function for two data elements */
24 	int (*cmp_func)(const void *a, const void *b, void *adata);
25 
26 	/* compare function for data element and a key value */
27 	int (*cmp_key_func)(const void *key, const void *data, void *adata);
28 
29 	/* pointer to additional data passed to compare functions */
30 	void *adata;
31 };
32 
33 void rb_clear (struct rb_tree *t);
34 void rb_init_tree (struct rb_tree *t,
35 		int (*cmp_func)(const void *a, const void *b, void *adata),
36 		int (*cmp_key_func)(const void *key, const void *data,
37 			void *adata),
38 		void *adata);
39 void rb_delete (struct rb_tree *t, const void *key);
40 struct rb_node *rb_next (struct rb_node *x);
41 struct rb_node *rb_min (struct rb_tree *t);
42 int rb_is_null (const struct rb_node *n);
43 struct rb_node *rb_search (struct rb_tree *t, const void *key);
44 void rb_insert (struct rb_tree *t, void *data);
45 
46 #ifdef __cplusplus
47 }
48 #endif
49 
50 #endif
51