These functions provide Red-Black tree management. More...
Data Structures | |
struct | _Eina_Rbtree |
Macros | |
#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) |
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) |
Enumerations | |
enum | Eina_Rbtree_Color { EINA_RBTREE_RED, EINA_RBTREE_BLACK } |
enum | Eina_Rbtree_Direction { EINA_RBTREE_LEFT = 0, EINA_RBTREE_RIGHT = 1 } |
Functions | |
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) |
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. More... | |
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. More... | |
void | eina_rbtree_delete (Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) |
Deletes all nodes from a valid red black tree. More... | |
Eina_Iterator * | eina_rbtree_iterator_prefix (const Eina_Rbtree *root) |
Returns a new prefix iterator associated with a rbtree. More... | |
Eina_Iterator * | eina_rbtree_iterator_infix (const Eina_Rbtree *root) |
Returns a new prefix iterator associated with a rbtree. More... | |
Eina_Iterator * | eina_rbtree_iterator_postfix (const Eina_Rbtree *root) |
Returns a new prefix iterator associated with a rbtree. More... | |
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.
#define EINA_RBTREE Eina_Rbtree __rbtree |
recommended way to declare the inlined Eina_Rbtree in your type.
#define EINA_RBTREE_GET | ( | Rbtree | ) | (&((Rbtree)->__rbtree)) |
access the inlined node if it was created with EINA_RBTREE.
#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_CMP_NODE_CB | ( | Function | ) | ((Eina_Rbtree_Cmp_Node_Cb)Function) |
Cast using Eina_Rbtree_Cmp_Node_Cb
#define EINA_RBTREE_CMP_KEY_CB | ( | Function | ) | ((Eina_Rbtree_Cmp_Key_Cb)Function) |
Cast using Eina_Rbtree_Cmp_Key_Cb
#define EINA_RBTREE_FREE_CB | ( | Function | ) | ((Eina_Rbtree_Free_Cb)Function) |
Cast using Eina_Rbtree_Free_Cb
Type for a Red-Black tree node. It should be inlined into user's type.
Eina_Rbtree_Cmp_Node_Cb |
Function used to compare two nodes and see which direction to navigate.
Eina_Rbtree_Cmp_Key_Cb |
Function used compare node with a given key of specified length.
Eina_Rbtree_Free_Cb |
Function used to free a node.
enum Eina_Rbtree_Color |
node color.
walk direction.
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.
[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. |
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.
References EINA_SAFETY_ON_NULL_RETURN_VAL.
Referenced by edje_box_layout_register().
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.
[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. |
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.
References EINA_SAFETY_ON_NULL_RETURN_VAL.
Referenced by edje_box_layout_register().
void eina_rbtree_delete | ( | Eina_Rbtree * | root, |
Eina_Rbtree_Free_Cb | func, | ||
void * | data | ||
) |
Deletes all nodes from a valid red black tree.
[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. |
References eina_rbtree_delete(), and EINA_SAFETY_ON_NULL_RETURN.
Referenced by eina_hash_free(), eina_hash_free_buckets(), and eina_rbtree_delete().
Eina_Iterator* eina_rbtree_iterator_prefix | ( | const Eina_Rbtree * | root | ) |
Returns a new prefix iterator associated with a rbtree.
[in] | root | The root of rbtree. |
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.
Eina_Iterator* eina_rbtree_iterator_infix | ( | const Eina_Rbtree * | root | ) |
Returns a new prefix iterator associated with a rbtree.
[in] | root | The root of rbtree. |
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.
Eina_Iterator* eina_rbtree_iterator_postfix | ( | const Eina_Rbtree * | root | ) |
Returns a new prefix iterator associated with a rbtree.
[in] | root | The root of rbtree. |
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.