cynapses libc red-black tree functions
[cynapses libc API (internal)]

Collaboration diagram for cynapses libc red-black tree functions:

Data Structures

struct c_rbnode_s

Structure that represents a node of a red-black tree. More...

struct c_rbtree_s

Structure that represents a red-black tree. More...

Defines

#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 *obj, void *data)

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)

Variables

xrbcolor_t c_rbnode_s::color

void * c_rbnode_s::data

c_rbtree_compare_func * c_rbtree_s::data_compare

c_rbtree_compare_func * c_rbtree_s::key_compare

c_rbnode_t * c_rbnode_s::left

c_rbnode_t * c_rbnode_s::parent

c_rbnode_t * c_rbnode_s::right

size_t c_rbtree_s::size

Define Documentation

#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);

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:

	T	The tree to destroy.
	DESTRUCTOR	The destructor to call on a node to destroy.

Definition at line 182 of file c_rbtree.h.

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

Get the data of a node.

Parameters:

N

The node to get the data from.

Returns:: The data, NULL if an error occured.

Definition at line 297 of file c_rbtree.h.

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

Get the size of the red-black tree.

Parameters:

T

The tree to get the size from.

Returns:: The size of the red-black tree.

Definition at line 248 of file c_rbtree.h.

Typedef Documentation

typedef struct c_rbnode_s c_rbnode_t

Definition at line 73 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.

Parameters:

	key	key as a generic pointer
	data	data 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 91 of file c_rbtree.h.

typedef struct c_rbtree_s c_rbtree_t

Definition at line 72 of file c_rbtree.h.

typedef int c_rbtree_visit_func(void *obj, void *data)

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:

	obj	The node data that will be passed by c_rbtree_walk().
	data	Generic data pointer.

Returns:: 0 on success, < 0 on error. You should set errno.

Definition at line 106 of file c_rbtree.h.

typedef enum xrbcolor_e xrbcolor_t

Definition at line 78 of file c_rbtree.h.

Enumeration Type Documentation

enum xrbcolor_e

Define the two colors for the red-black tree.

Enumerator:

BLACK
RED

Definition at line 78 of file c_rbtree.h.

Function Documentation

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:

tree

The tree to check.

Returns:: 0 on success, less than 0 if an error occured.

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:

	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.

Returns:: 0 on success, -1 if an error occured with errno set.

c_rbtree_t* c_rbtree_dup ( const c_rbtree_t * tree )

Duplicate a red-black tree.

Parameters:

tree

Tree to duplicate.

Returns:: Pointer to a new allocated duplicated rbtree. NULL if an error occured.

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:

	tree	The tree to search.
	key	The key to search for.

Returns:: If the key was found the node will be returned. On error NULL will be returned.

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:

tree

The tree to free.

Returns:: 0 on success, less than 0 if an error occured.

c_rbnode_t* c_rbtree_head ( c_rbtree_t * tree )

Get the head of the red-black tree.

Parameters:

tree

The tree to get the head for.

Returns:: The head node. NULL if an error occured.

int c_rbtree_insert	(	c_rbtree_t *	tree,
		void *	data
	)

Inserts a node into a red black tree.

Parameters:

	tree	The red black tree to insert the node.
	data	The 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.

int c_rbtree_node_delete ( c_rbnode_t * node )

Delete a node in a red-black tree.

Parameters:

node

Node which should be deleted.

Returns:: 0 on success, -1 if an error occured.

c_rbnode_t* c_rbtree_node_next ( c_rbnode_t * node )

Get the next node.

Parameters:

node

The node of which you want the next node.

Returns:: The next node, NULL if an error occured.

c_rbnode_t* c_rbtree_node_prev ( c_rbnode_t * node )

Get the previous node.

Parameters:

node

The node of which you want the previous node.

Returns:: The previous node, NULL if an error occured.

c_rbnode_t* c_rbtree_tail ( c_rbtree_t * tree )

Get the tail of the red-black tree.

Parameters:

tree

The tree to get the tail for.

Returns:: The tail node. NULL if an error occured.

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:

	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.

Returns:: 0 on sucess, less than 0 if an error occured.

Variable Documentation

xrbcolor_t c_rbnode_s::color [inherited]

Definition at line 127 of file c_rbtree.h.

void* c_rbnode_s::data [inherited]

Definition at line 126 of file c_rbtree.h.

c_rbtree_compare_func* c_rbtree_s::data_compare [inherited]

Definition at line 114 of file c_rbtree.h.

c_rbtree_compare_func* c_rbtree_s::key_compare [inherited]

Definition at line 113 of file c_rbtree.h.

c_rbnode_t* c_rbnode_s::left [inherited]

Definition at line 123 of file c_rbtree.h.

c_rbnode_t* c_rbnode_s::parent [inherited]

Definition at line 125 of file c_rbtree.h.

c_rbnode_t* c_rbnode_s::right [inherited]

Definition at line 124 of file c_rbtree.h.

size_t c_rbtree_s::size [inherited]

Definition at line 115 of file c_rbtree.h.


Data Structures
struct	c_rbnode_s
	Structure that represents a node of a red-black tree. More...
struct	c_rbtree_s
	Structure that represents a red-black tree. More...
Defines
#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 obj, void data)
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)
Variables
xrbcolor_t	c_rbnode_s::color
void *	c_rbnode_s::data
c_rbtree_compare_func *	c_rbtree_s::data_compare
c_rbtree_compare_func *	c_rbtree_s::key_compare
c_rbnode_t *	c_rbnode_s::left
c_rbnode_t *	c_rbnode_s::parent
c_rbnode_t *	c_rbnode_s::right
size_t	c_rbtree_s::size

cynapses libc red-black tree functions [cynapses libc API (internal)]

Data Structures

Defines

Typedefs

Enumerations

Functions

Variables

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation

cynapses libc red-black tree functions
[cynapses libc API (internal)]