doc
Data Structures | Macros | Typedefs | Enumerations | Enumerator | Functions | Variables
cynapses libc red-black tree functions

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_tc_rbtree_dup (const c_rbtree_t *tree)
 
c_rbnode_tc_rbtree_find (c_rbtree_t *tree, const void *key)
 
int c_rbtree_free (c_rbtree_t *tree)
 
c_rbnode_tc_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_tc_rbtree_node_next (c_rbnode_t *node)
 
c_rbnode_tc_rbtree_node_prev (c_rbnode_t *node)
 
c_rbnode_tc_rbtree_tail (c_rbtree_t *tree)
 
int c_rbtree_walk (c_rbtree_t *tree, void *data, c_rbtree_visit_func *visitor)
 

Variables

xrbcolor_t c_rbnode_s::color
 
void * c_rbnode_s::data
 
c_rbtree_compare_funcc_rbtree_s::data_compare
 
c_rbtree_compare_funcc_rbtree_s::key_compare
 
c_rbnode_tc_rbnode_s::left
 
c_rbnode_tc_rbnode_s::parent
 
c_rbnode_tc_rbnode_s::right
 
c_rbnode_tc_rbtree_s::root
 
size_t c_rbtree_s::size
 
c_rbtree_tc_rbnode_s::tree
 

Detailed Description

Macro Definition Documentation

◆ c_rbtree_destroy

#define c_rbtree_destroy (   T,
  DESTRUCTOR 
)
Value:
do { \
if (T) { \
c_rbnode_t *_c_rbtree_temp; \
while ((_c_rbtree_temp = c_rbtree_head(T))) { \
(DESTRUCTOR)(_c_rbtree_temp->data); \
if (_c_rbtree_temp == c_rbtree_head(T)) { \
c_rbtree_node_delete(_c_rbtree_temp); \
} \
} \
} \
SAFE_FREE(T); \
} while (0);
c_rbnode_t * c_rbtree_head(c_rbtree_t *tree)
Get the head of the red-black tree.

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.

Parameters
TThe tree to destroy.
DESTRUCTORThe destructor to call on a node to destroy.

Definition at line 180 of file c_rbtree.h.

◆ c_rbtree_node_data

#define c_rbtree_node_data (   N)    ((N) ? ((N)->data) : NULL)

Get the data of a node.

Parameters
NThe node to get the data from.
Returns
The data, NULL if an error occured.

Definition at line 295 of file c_rbtree.h.

◆ c_rbtree_size

#define c_rbtree_size (   T)    (T) == NULL ? 0 : ((T)->size)

Get the size of the red-black tree.

Parameters
TThe tree to get the size from.
Returns
The size of the red-black tree.

Definition at line 246 of file c_rbtree.h.

Typedef Documentation

◆ c_rbnode_t

typedef struct c_rbnode_s c_rbnode_t

Definition at line 71 of file c_rbtree.h.

◆ c_rbtree_compare_func

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.

Parameters
keykey as a generic pointer
datadata as a generic pointer
Returns
It returns an integer less than, equal to, or greater than zero depending on the key or data you use. The function is similar to strcmp().

Definition at line 89 of file c_rbtree.h.

◆ c_rbtree_t

typedef struct c_rbtree_s c_rbtree_t

Definition at line 70 of file c_rbtree.h.

◆ c_rbtree_visit_func

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.

Parameters
objThe node data that will be passed by c_rbtree_walk().
dataGeneric data pointer.
Returns
0 on success, < 0 on error. You should set errno.

Definition at line 104 of file c_rbtree.h.

◆ xrbcolor_t

typedef enum xrbcolor_e xrbcolor_t

Definition at line 76 of file c_rbtree.h.

Enumeration Type Documentation

◆ xrbcolor_e

enum xrbcolor_e

Define the two colors for the red-black tree.

Enumerator
BLACK 
RED 

Definition at line 76 of file c_rbtree.h.

Function Documentation

◆ c_rbtree_check_sanity()

int c_rbtree_check_sanity ( c_rbtree_t tree)

Perform a sanity check for a red-black tree.

This is mostly for testing purposes.

Parameters
treeThe tree to check.
Returns
0 on success, less than 0 if an error occured.

◆ c_rbtree_create()

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.

Parameters
rbtreeThe pointer to assign the allocated memory.
key_compareCallback function to compare a key with the data inside a reb-black tree node.
data_compareCallback function to compare a key as data with thee data inside a red-black tree node.
Returns
0 on success, -1 if an error occured with errno set.

◆ c_rbtree_dup()

c_rbtree_t* c_rbtree_dup ( const c_rbtree_t tree)

Duplicate a red-black tree.

Parameters
treeTree to duplicate.
Returns
Pointer to a new allocated duplicated rbtree. NULL if an error occured.

◆ c_rbtree_find()

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.

Parameters
treeThe tree to search.
keyThe key to search for.
Returns
If the key was found the node will be returned. On error NULL will be returned.

◆ c_rbtree_free()

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.

Parameters
treeThe tree to free.
Returns
0 on success, less than 0 if an error occured.

◆ c_rbtree_head()

c_rbnode_t* c_rbtree_head ( c_rbtree_t tree)

Get the head of the red-black tree.

Parameters
treeThe tree to get the head for.
Returns
The head node. NULL if an error occured.

◆ c_rbtree_insert()

int c_rbtree_insert ( c_rbtree_t tree,
void *  data 
)

Inserts a node into a red black tree.

Parameters
treeThe red black tree to insert the node.
dataThe data to insert into the tree.
Returns
0 on success, 1 if a duplicate has been found and < 0 if an error occured with errno set. EINVAL if a null pointer has been passed as the tree. ENOMEM if there is no memory left.

◆ c_rbtree_node_delete()

int c_rbtree_node_delete ( c_rbnode_t node)

Delete a node in a red-black tree.

Parameters
nodeNode which should be deleted.
Returns
0 on success, -1 if an error occured.

◆ c_rbtree_node_next()

c_rbnode_t* c_rbtree_node_next ( c_rbnode_t node)

Get the next node.

Parameters
nodeThe node of which you want the next node.
Returns
The next node, NULL if an error occured.

◆ c_rbtree_node_prev()

c_rbnode_t* c_rbtree_node_prev ( c_rbnode_t node)

Get the previous node.

Parameters
nodeThe node of which you want the previous node.
Returns
The previous node, NULL if an error occured.

◆ c_rbtree_tail()

c_rbnode_t* c_rbtree_tail ( c_rbtree_t tree)

Get the tail of the red-black tree.

Parameters
treeThe tree to get the tail for.
Returns
The tail node. NULL if an error occured.

◆ c_rbtree_walk()

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.

Parameters
treeTree to walk.
dataData which should be passed to the visitor function.
visitorVisitor function. This will be called for each node passed.
Returns
0 on sucess, less than 0 if an error occured.

Variable Documentation

◆ color

xrbcolor_t c_rbnode_s::color

Definition at line 125 of file c_rbtree.h.

◆ data

void* c_rbnode_s::data

Definition at line 124 of file c_rbtree.h.

◆ data_compare

c_rbtree_compare_func* c_rbtree_s::data_compare

Definition at line 112 of file c_rbtree.h.

◆ key_compare

c_rbtree_compare_func* c_rbtree_s::key_compare

Definition at line 111 of file c_rbtree.h.

◆ left

c_rbnode_t* c_rbnode_s::left

Definition at line 121 of file c_rbtree.h.

◆ parent

c_rbnode_t* c_rbnode_s::parent

Definition at line 123 of file c_rbtree.h.

◆ right

c_rbnode_t* c_rbnode_s::right

Definition at line 122 of file c_rbtree.h.

◆ root

c_rbnode_t* c_rbtree_s::root

Definition at line 110 of file c_rbtree.h.

◆ size

size_t c_rbtree_s::size

Definition at line 113 of file c_rbtree.h.

◆ tree

c_rbtree_t* c_rbnode_s::tree

Definition at line 120 of file c_rbtree.h.