#include #include #ifndef RBTREE_H #define RBTREE_H /* NOTE: We only hold pointers to data, it is the user's responsibility to ensure the data pointed by the tree pointers is not invalidated while tree operations are running. */ /* NOTE: We assume data values are unique, i.e., abort insertions with duplicates */ //Comparison function pointer typedef int (*rb_cmp_func)(const void*, const void*); #define BLACK 0 #define RED 1 //Tree node struct struct rb_node { // set to RED or BLACK for red or black uint8_t color; //We don't hold data just pointers so data can be whatever. void *data; //left and right subtrees struct rb_node *left, *right; //parent pointer struct rb_node *parent; }; //Tree struct struct rb_tree { //root node struct rb_node *root; //comparison function rb_cmp_func cmp; size_t size; }; //Exposed functions to manipulate the tree void rb_tree_init(struct rb_tree *tree, rb_cmp_func cmp); //returns 0 on success a negative value on failure int rb_tree_insert(struct rb_tree *tree, void *data); //returns a pointer to the data or NULL if no data with that value was found void* rb_tree_find(struct rb_tree *tree, void *data); //returns 0 on success or a negative value on failure int rb_tree_delete(struct rb_tree *tree, void *data); void rb_tree_destroy(struct rb_tree *tree); #endif