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