Tizen Native API
Functions | Typedefs | Defines
Red-Black tree
Containers

This group discusses the functions that provide Red-Black trees 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 the nodes from a valid red black tree.
Eina_Iterator * eina_rbtree_iterator_prefix (const Eina_Rbtree *root)
 Returns a new prefix iterator associated to an rbtree.
Eina_Iterator * eina_rbtree_iterator_infix (const Eina_Rbtree *root)
 Returns a new prefix iterator associated to an rbtree.
Eina_Iterator * eina_rbtree_iterator_postfix (const Eina_Rbtree *root)
 Returns a new prefix iterator associated to an rbtree.

Typedefs

typedef struct _Eina_Rbtree Eina_Rbtree
 The structure type for a Red-Black tree node. It should be inlined into the user type.
typedef Eina_Rbtree_Direction(* Eina_Rbtree_Cmp_Node_Cb )(const Eina_Rbtree *left, const Eina_Rbtree *right, void *data)
 Compares two nodes and decides which direction to navigate.
typedef int(* Eina_Rbtree_Cmp_Key_Cb )(const Eina_Rbtree *node, const void *key, int length, void *data)
 Compares a node with the given key of the specified length.
typedef void(* Eina_Rbtree_Free_Cb )(Eina_Rbtree *node, void *data)
 Called to free a node.

Defines

#define EINA_RBTREE   Eina_Rbtree __rbtree
 Definition of the recommended way to declare the inlined Eina_Rbtree for your type.
#define EINA_RBTREE_GET(Rbtree)   (&((Rbtree)->__rbtree))
 Definition to access the inlined node if it is created with EINA_RBTREE.
#define EINA_RBTREE_CONTAINER_GET(Ptr, Type)   ((Type *)((char *)Ptr - offsetof(Type, __rbtree)))
 Definition to find back the container of a red black tree.
#define EINA_RBTREE_CMP_NODE_CB(Function)   ((Eina_Rbtree_Cmp_Node_Cb)Function)
 Definition of the cast using Eina_Rbtree_Cmp_Node_Cb.
#define EINA_RBTREE_CMP_KEY_CB(Function)   ((Eina_Rbtree_Cmp_Key_Cb)Function)
 Definition of the cast using Eina_Rbtree_Cmp_Key_Cb.
#define EINA_RBTREE_FREE_CB(Function)   ((Eina_Rbtree_Free_Cb)Function)
 Definition of the cast using Eina_Rbtree_Free_Cb.

Define Documentation

#define EINA_RBTREE   Eina_Rbtree __rbtree

Definition of the recommended way to declare the inlined Eina_Rbtree for your type. 

 struct my_type {
    EINA_RBTREE;
    int my_value;
    char *my_name;
 };
See also:
EINA_RBTREE_GET()
#define EINA_RBTREE_CONTAINER_GET (   Ptr,
  Type 
)    ((Type *)((char *)Ptr - offsetof(Type, __rbtree)))

Definition to find back the container of a red black tree.

Since :
2.3.1
#define EINA_RBTREE_GET (   Rbtree)    (&((Rbtree)->__rbtree))

Definition to access the inlined node if it is created with EINA_RBTREE.

Since :
2.3.1

Function Documentation

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

Deletes all the nodes from a valid red black tree.

Since :
2.3.1
Parameters:
[in]rootThe root of a valid red black tree
[in]funcThe callback that frees each node
[in]dataThe private data to help the compare function
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.

This function inserts a new node into 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
Parameters:
[in]rootThe root of an existing valid red black tree
[in]nodeThe new node to insert
[in]cmpThe callback that is able to compare two nodes
[in]dataThe private data to help the compare function
Returns:
The new root of the 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.

This function removes a new node from a valid red black tree that should contain the node that you are removing. This function returns NULL when the red black tree becomes empty. This function doesn't free any data.

Since :
2.3.1
Parameters:
[in]rootThe root of a valid red black tree
[in]nodeThe node to remove from the tree
[in]cmpThe callback that is able to compare two nodes
[in]dataThe private data to help the compare function
Returns:
The new root of the red black tree
Eina_Iterator* eina_rbtree_iterator_infix ( const Eina_Rbtree *  root)

Returns a new prefix iterator associated to an rbtree.

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

Since :
2.3.1
Remarks:
If the memory cannot be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
If the rbtree structure changes then the iterator becomes invalid. That is, if you add or remove nodes this iterator's behavior is undefined and your program may crash.
Parameters:
[in]rootThe root of the rbtree
Returns:
A new iterator
Eina_Iterator* eina_rbtree_iterator_postfix ( const Eina_Rbtree *  root)

Returns a new prefix iterator associated to an rbtree.

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

Since :
2.3.1
Remarks:
If the memory cannot be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
If the rbtree structure changes then the iterator becomes invalid. That is, if you add or remove nodes this iterator's behavior is undefined and your program may crash.
Parameters:
[in]rootThe root of the rbtree
Returns:
A new iterator
Eina_Iterator* eina_rbtree_iterator_prefix ( const Eina_Rbtree *  root)

Returns a new prefix iterator associated to an rbtree.

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

Since :
2.3.1
Remarks:
If the memory cannot be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
If the rbtree structure changes then the iterator becomes invalid. That is, if you add or remove nodes this iterator's behavior is undefined and your program may crash.
Parameters:
[in]rootThe root of the rbtree
Returns:
A new iterator