#include <stddef.h>
#include <stdint.h>
#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