These functions provide Red-Black tree management.

For a brief description look at http://en.wikipedia.org/wiki/Red-black_tree . This code is largely inspired from a tutorial written by Julienne Walker at : http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx . The main difference is that this set of functions never allocate any data, making them particularly useful for memory management.

Functions
Eina_Rbtree *	eina_rbtree_inline_insert (Eina_Rbtree root, Eina_Rbtree node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data)
	Inserts a new node inside an existing red black tree.
Eina_Rbtree *	eina_rbtree_inline_remove (Eina_Rbtree root, Eina_Rbtree node, Eina_Rbtree_Cmp_Node_Cb cmp, const void *data)
	Removes a node from an existing red black tree.
void	eina_rbtree_delete (Eina_Rbtree root, Eina_Rbtree_Free_Cb func, void data)
	Deletes all nodes from a valid red black tree.
static Eina_Rbtree *	eina_rbtree_inline_lookup (const Eina_Rbtree root, const void key, int length, Eina_Rbtree_Cmp_Key_Cb cmp, const void *data)
	Searches tree for a key using a comparison function.
Eina_Iterator *	eina_rbtree_iterator_prefix (const Eina_Rbtree *root)
	Returns a new prefix iterator associated with a rbtree.
Eina_Iterator *	eina_rbtree_iterator_infix (const Eina_Rbtree *root)
	Returns a new prefix iterator associated with a rbtree.
Eina_Iterator *	eina_rbtree_iterator_postfix (const Eina_Rbtree *root)
	Returns a new prefix iterator associated with a rbtree.
Typedefs
typedef struct _Eina_Rbtree	Eina_Rbtree
typedef Eina_Rbtree_Direction(*	Eina_Rbtree_Cmp_Node_Cb )(const Eina_Rbtree left, const Eina_Rbtree right, void *data)
typedef int(*	Eina_Rbtree_Cmp_Key_Cb )(const Eina_Rbtree node, const void key, int length, void *data)
typedef void(*	Eina_Rbtree_Free_Cb )(Eina_Rbtree node, void data)
Defines
#define	EINA_RBTREE Eina_Rbtree __rbtree
#define	EINA_RBTREE_GET(Rbtree) (&((Rbtree)->__rbtree))
#define	EINA_RBTREE_CONTAINER_GET(Ptr, Type) ((Type )((char )Ptr - offsetof(Type, __rbtree)))
#define	EINA_RBTREE_CMP_NODE_CB(Function) ((Eina_Rbtree_Cmp_Node_Cb)Function)
#define	EINA_RBTREE_CMP_KEY_CB(Function) ((Eina_Rbtree_Cmp_Key_Cb)Function)
#define	EINA_RBTREE_FREE_CB(Function) ((Eina_Rbtree_Free_Cb)Function)

Define Documentation

#define EINA_RBTREE Eina_Rbtree __rbtree

recommended way to declare the inlined Eina_Rbtree in your type.

 struct my_type {
    EINA_RBTREE;
    int my_value;
    char *my_name;
 };

See also:: EINA_RBTREE_GET()

#define EINA_RBTREE_CMP_KEY_CB ( Function ) ((Eina_Rbtree_Cmp_Key_Cb)Function)

Cast using Eina_Rbtree_Cmp_Key_Cb

#define EINA_RBTREE_CMP_NODE_CB ( Function ) ((Eina_Rbtree_Cmp_Node_Cb)Function)

Cast using Eina_Rbtree_Cmp_Node_Cb

#define EINA_RBTREE_CONTAINER_GET	(	Ptr,
		Type
	)	((Type )((char )Ptr - offsetof(Type, __rbtree)))

find back the container of a red black tree.

#define EINA_RBTREE_FREE_CB ( Function ) ((Eina_Rbtree_Free_Cb)Function)

Cast using Eina_Rbtree_Free_Cb

#define EINA_RBTREE_GET ( Rbtree ) (&((Rbtree)->__rbtree))

access the inlined node if it was created with EINA_RBTREE.

Typedef Documentation

Eina_Rbtree

Type for a Red-Black tree node. It should be inlined into user's type.

Eina_Rbtree_Cmp_Key_Cb

Function used compare node with a given key of specified length.

Eina_Rbtree_Cmp_Node_Cb

Function used to compare two nodes and see which direction to navigate.

Eina_Rbtree_Free_Cb

Function used to free a node.

Enumeration Type Documentation

enum Eina_Rbtree_Color

node color.

enum Eina_Rbtree_Direction

walk direction.

Function Documentation

void eina_rbtree_delete	(	Eina_Rbtree *	root,
		Eina_Rbtree_Free_Cb	func,
		void *	data
	)

Deletes all nodes from a valid red black tree.

Parameters:

[in,out]	root	The root of a valid red black tree.
[in]	func	The callback that will free each node.
[in]	data	Private data to help the compare function.

Since :: 2.3.1

Eina_Rbtree* eina_rbtree_inline_insert	(	Eina_Rbtree *	root,
		Eina_Rbtree *	node,
		Eina_Rbtree_Cmp_Node_Cb	cmp,
		const void *	data
	)

Inserts a new node inside an existing red black tree.

Parameters:

[in,out]	root	The root of an existing valid red black tree.
[in]	node	The new node to insert.
[in]	cmp	The callback that is able to compare two nodes.
[in]	data	Private data to help the compare function.

Returns:: The new root of the red black tree.

This function inserts a new node in a valid red black tree. NULL is an empty valid red black tree. The resulting new tree is a valid red black tree. This function doesn't allocate any data.

Since :: 2.3.1

static Eina_Rbtree* eina_rbtree_inline_lookup	(	const Eina_Rbtree *	root,
		const void *	key,
		int	length,
		Eina_Rbtree_Cmp_Key_Cb	cmp,
		const void *	data
	)		`[static]`

Searches tree for a key using a comparison function.

Parameters:

[in,out]	root	The root of a valid red black tree.
[in]	key	The key value to search for.
[in]	length	The length of the specified key.
[in]	cmp	Callback routine to compare two nodes.
[in]	data	Private data to help the compare function.

Returns:: The first matching node found in the red black tree, or root if nothing was found.

Eina_Rbtree* eina_rbtree_inline_remove	(	Eina_Rbtree *	root,
		Eina_Rbtree *	node,
		Eina_Rbtree_Cmp_Node_Cb	cmp,
		const void *	data
	)

Removes a node from an existing red black tree.

Parameters:

[in,out]	root	The root of a valid red black tree.
[in]	node	The node to remove from the tree.
[in]	cmp	The callback that is able to compare two nodes.
[in]	data	Private data to help the compare function.

Returns:: The new root of the red black tree.

This function removes a new node in a valid red black tree that should contain the node that you are removing. This function will return NULL when the red black tree got empty. This function doesn't free any data.

Since :: 2.3.1

Eina_Iterator* eina_rbtree_iterator_infix ( const Eina_Rbtree * root )

Returns a new prefix iterator associated with a rbtree.

Parameters:

[in] root The root of rbtree.

Returns:: A new iterator.

This function returns a newly allocated iterator associated with root. It will iterate the tree using infix walk. If root is NULL, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.

If the memory cannot be allocated, NULL is returned. Otherwise, a valid iterator is returned.

Warning:: if the rbtree structure changes then the iterator becomes invalid! That is, if you add or remove nodes this iterator behavior is undefined and your program may crash!

Since :: 2.3.1

Eina_Iterator* eina_rbtree_iterator_postfix ( const Eina_Rbtree * root )

Returns a new prefix iterator associated with a rbtree.

Parameters:

[in] root The root of rbtree.

Returns:: A new iterator.

This function returns a newly allocated iterator associated with root. It will iterate the tree using postfix walk. If root is NULL, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.

If the memory cannot be allocated, NULL is returned. Otherwise, a valid iterator is returned.

Warning:: if the rbtree structure changes then the iterator becomes invalid! That is, if you add or remove nodes this iterator behavior is undefined and your program may crash!

Since :: 2.3.1

Eina_Iterator* eina_rbtree_iterator_prefix ( const Eina_Rbtree * root )

Returns a new prefix iterator associated with a rbtree.

Parameters:

[in] root The root of rbtree.

Returns:: A new iterator.

This function returns a newly allocated iterator associated with root. It will iterate the tree using prefix walk. If root is NULL, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.

If the memory cannot be allocated, NULL is returned. Otherwise, a valid iterator is returned.

Warning:: if the rbtree structure changes then the iterator becomes invalid! That is, if you add or remove nodes this iterator behavior is undefined and your program may crash!

Since :: 2.3.1

Functions

Typedefs

Defines

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation