doc
|
Data Structures | |
struct | c_rbnode_s |
struct | c_rbtree_s |
Macros | |
#define | c_rbtree_destroy(T, DESTRUCTOR) |
#define | c_rbtree_node_data(N) ((N) ? ((N)->data) : NULL) |
#define | c_rbtree_size(T) (T) == NULL ? 0 : ((T)->size) |
Typedefs | |
typedef struct c_rbnode_s | c_rbnode_t |
typedef int | c_rbtree_compare_func(const void *key, const void *data) |
typedef struct c_rbtree_s | c_rbtree_t |
typedef int | c_rbtree_visit_func(void *, void *) |
typedef enum xrbcolor_e | xrbcolor_t |
Enumerations | |
enum | xrbcolor_e { BLACK = 0, RED } |
Functions | |
int | c_rbtree_check_sanity (c_rbtree_t *tree) |
int | c_rbtree_create (c_rbtree_t **rbtree, c_rbtree_compare_func *key_compare, c_rbtree_compare_func *data_compare) |
c_rbtree_t * | c_rbtree_dup (const c_rbtree_t *tree) |
c_rbnode_t * | c_rbtree_find (c_rbtree_t *tree, const void *key) |
int | c_rbtree_free (c_rbtree_t *tree) |
c_rbnode_t * | c_rbtree_head (c_rbtree_t *tree) |
int | c_rbtree_insert (c_rbtree_t *tree, void *data) |
int | c_rbtree_node_delete (c_rbnode_t *node) |
c_rbnode_t * | c_rbtree_node_next (c_rbnode_t *node) |
c_rbnode_t * | c_rbtree_node_prev (c_rbnode_t *node) |
c_rbnode_t * | c_rbtree_tail (c_rbtree_t *tree) |
int | c_rbtree_walk (c_rbtree_t *tree, void *data, c_rbtree_visit_func *visitor) |
#define c_rbtree_destroy | ( | T, | |
DESTRUCTOR | |||
) |
Destroy the content and the nodes of an red-black tree.
This is far from the most efficient way to walk a tree, but it is the safest way to destroy a tree - the destructor can do almost anything (as long as it does not create an infinite loop) to the tree structure without risk.
If for some strange reason you need a faster destructor (think twice - speed and memory deallocation don't mix well) then consider stashing an llist of dataects and destroying that instead, and just using c_rbtree_free() on your tree.
T | The tree to destroy. |
DESTRUCTOR | The destructor to call on a node to destroy. |
Definition at line 180 of file c_rbtree.h.
#define c_rbtree_node_data | ( | N | ) | ((N) ? ((N)->data) : NULL) |
Get the data of a node.
N | The node to get the data from. |
Definition at line 295 of file c_rbtree.h.
#define c_rbtree_size | ( | T | ) | (T) == NULL ? 0 : ((T)->size) |
Get the size of the red-black tree.
T | The tree to get the size from. |
Definition at line 246 of file c_rbtree.h.
typedef struct c_rbnode_s c_rbnode_t |
Definition at line 71 of file c_rbtree.h.
typedef int c_rbtree_compare_func(const void *key, const void *data) |
Callback function to compare a key with the data from a red-black tree node.
key | key as a generic pointer |
data | data as a generic pointer |
Definition at line 89 of file c_rbtree.h.
typedef struct c_rbtree_s c_rbtree_t |
Definition at line 70 of file c_rbtree.h.
typedef int c_rbtree_visit_func(void *, void *) |
Visit function for the c_rbtree_walk() function.
This function will be called by c_rbtree_walk() for every node. It is up to the developer what the function does. The fist parameter is a node object the second can be of any kind.
obj | The node data that will be passed by c_rbtree_walk(). |
data | Generic data pointer. |
Definition at line 104 of file c_rbtree.h.
typedef enum xrbcolor_e xrbcolor_t |
Definition at line 76 of file c_rbtree.h.
enum xrbcolor_e |
Define the two colors for the red-black tree.
Enumerator | |
---|---|
BLACK | |
RED |
Definition at line 76 of file c_rbtree.h.
int c_rbtree_check_sanity | ( | c_rbtree_t * | tree | ) |
Perform a sanity check for a red-black tree.
This is mostly for testing purposes.
tree | The tree to check. |
int c_rbtree_create | ( | c_rbtree_t ** | rbtree, |
c_rbtree_compare_func * | key_compare, | ||
c_rbtree_compare_func * | data_compare | ||
) |
Create the red-black tree.
rbtree | The pointer to assign the allocated memory. |
key_compare | Callback function to compare a key with the data inside a reb-black tree node. |
data_compare | Callback function to compare a key as data with thee data inside a red-black tree node. |
c_rbtree_t* c_rbtree_dup | ( | const c_rbtree_t * | tree | ) |
Duplicate a red-black tree.
tree | Tree to duplicate. |
c_rbnode_t* c_rbtree_find | ( | c_rbtree_t * | tree, |
const void * | key | ||
) |
Find a node in a red-black tree.
c_rbtree_find() is searching for the given key in a red-black tree and returns the node if the key has been found.
tree | The tree to search. |
key | The key to search for. |
int c_rbtree_free | ( | c_rbtree_t * | tree | ) |
Free the structure of a red-black tree.
You should call c_rbtree_destroy() before you call this function.
tree | The tree to free. |
c_rbnode_t* c_rbtree_head | ( | c_rbtree_t * | tree | ) |
Get the head of the red-black tree.
tree | The tree to get the head for. |
int c_rbtree_insert | ( | c_rbtree_t * | tree, |
void * | data | ||
) |
Inserts a node into a red black tree.
tree | The red black tree to insert the node. |
data | The data to insert into the tree. |
int c_rbtree_node_delete | ( | c_rbnode_t * | node | ) |
Delete a node in a red-black tree.
node | Node which should be deleted. |
c_rbnode_t* c_rbtree_node_next | ( | c_rbnode_t * | node | ) |
Get the next node.
node | The node of which you want the next node. |
c_rbnode_t* c_rbtree_node_prev | ( | c_rbnode_t * | node | ) |
Get the previous node.
node | The node of which you want the previous node. |
c_rbnode_t* c_rbtree_tail | ( | c_rbtree_t * | tree | ) |
Get the tail of the red-black tree.
tree | The tree to get the tail for. |
int c_rbtree_walk | ( | c_rbtree_t * | tree, |
void * | data, | ||
c_rbtree_visit_func * | visitor | ||
) |
Walk over a red-black tree.
Walk over a red-black tree calling a visitor function for each node found.
tree | Tree to walk. |
data | Data which should be passed to the visitor function. |
visitor | Visitor function. This will be called for each node passed. |
xrbcolor_t c_rbnode_s::color |
Definition at line 125 of file c_rbtree.h.
void* c_rbnode_s::data |
Definition at line 124 of file c_rbtree.h.
c_rbtree_compare_func* c_rbtree_s::data_compare |
Definition at line 112 of file c_rbtree.h.
c_rbtree_compare_func* c_rbtree_s::key_compare |
Definition at line 111 of file c_rbtree.h.
c_rbnode_t* c_rbnode_s::left |
Definition at line 121 of file c_rbtree.h.
c_rbnode_t* c_rbnode_s::parent |
Definition at line 123 of file c_rbtree.h.
c_rbnode_t* c_rbnode_s::right |
Definition at line 122 of file c_rbtree.h.
c_rbnode_t* c_rbtree_s::root |
Definition at line 110 of file c_rbtree.h.
size_t c_rbtree_s::size |
Definition at line 113 of file c_rbtree.h.
c_rbtree_t* c_rbnode_s::tree |
Definition at line 120 of file c_rbtree.h.