|
Electroneum
|

Go to the source code of this file.
Classes | |
| struct | rbnode_type |
| struct | rbtree_type |
Macros | |
| #define | RBTREE_NULL &rbtree_null_node |
| #define | RBTREE_FOR(node, type, rbtree) |
Typedefs | |
| typedef struct rbnode_type | rbnode_type |
| typedef struct rbtree_type | rbtree_type |
Functions | |
| rbtree_type * | rbtree_create (int(*cmpf)(const void *, const void *)) |
| void | rbtree_init (rbtree_type *rbtree, int(*cmpf)(const void *, const void *)) |
| rbnode_type * | rbtree_insert (rbtree_type *rbtree, rbnode_type *data) |
| rbnode_type * | rbtree_delete (rbtree_type *rbtree, const void *key) |
| rbnode_type * | rbtree_search (rbtree_type *rbtree, const void *key) |
| int | rbtree_find_less_equal (rbtree_type *rbtree, const void *key, rbnode_type **result) |
| rbnode_type * | rbtree_first (rbtree_type *rbtree) |
| rbnode_type * | rbtree_last (rbtree_type *rbtree) |
| rbnode_type * | rbtree_next (rbnode_type *rbtree) |
| rbnode_type * | rbtree_previous (rbnode_type *rbtree) |
| void | traverse_postorder (rbtree_type *tree, void(*func)(rbnode_type *, void *), void *arg) |
Variables | |
| rbnode_type | rbtree_null_node |
Red black tree. Implementation taken from NSD 3.0.5, adjusted for use in unbound (memory allocation, logging and so on).
Definition in file rbtree.h.
| #define RBTREE_FOR | ( | node, | |
| type, | |||
| rbtree | |||
| ) |
Call with node=variable of struct* with rbnode_type as first element. with type is the type of a pointer to that struct.
| #define RBTREE_NULL &rbtree_null_node |
| typedef struct rbnode_type rbnode_type |
This structure must be the first member of the data structure in the rbtree. This allows easy casting between an rbnode_type and the user data (poor man's inheritance).
| typedef struct rbtree_type rbtree_type |
| rbtree_type* rbtree_create | ( | int(*)(const void *, const void *) | cmpf | ) |
Create new tree (malloced) with given key compare function.
| cmpf | compare function (like strcmp) takes pointers to two keys. |
| rbnode_type* rbtree_delete | ( | rbtree_type * | rbtree, |
| const void * | key | ||
| ) |
Delete element from tree.
| rbtree | tree to delete from. |
| key | key of item to delete. |
| int rbtree_find_less_equal | ( | rbtree_type * | rbtree, |
| const void * | key, | ||
| rbnode_type ** | result | ||
| ) |
Find, but match does not have to be exact.
| rbtree | tree to find in. |
| key | key to find position of. |
| result | set to the exact node if present, otherwise to element that precedes the position of key in the tree. NULL if no smaller element. |
| rbnode_type* rbtree_first | ( | rbtree_type * | rbtree | ) |
Returns first (smallest) node in the tree
| rbtree | tree |
| void rbtree_init | ( | rbtree_type * | rbtree, |
| int(*)(const void *, const void *) | cmpf | ||
| ) |
Init a new tree (malloced by caller) with given key compare function.
| rbtree | uninitialised memory for new tree, returned empty. |
| cmpf | compare function (like strcmp) takes pointers to two keys. |
| rbnode_type* rbtree_insert | ( | rbtree_type * | rbtree, |
| rbnode_type * | data | ||
| ) |
Insert data into the tree.
| rbtree | tree to insert to. |
| data | element to insert. |
| rbnode_type* rbtree_last | ( | rbtree_type * | rbtree | ) |
Returns last (largest) node in the tree
| rbtree | tree |
| rbnode_type* rbtree_next | ( | rbnode_type * | rbtree | ) |
Returns next larger node in the tree
| rbtree | tree |
| rbnode_type* rbtree_previous | ( | rbnode_type * | rbtree | ) |
Returns previous smaller node in the tree
| rbtree | tree |
| rbnode_type* rbtree_search | ( | rbtree_type * | rbtree, |
| const void * | key | ||
| ) |
Find key in tree. Returns NULL if not found.
| rbtree | tree to find in. |
| key | key that must match. |
| void traverse_postorder | ( | rbtree_type * | tree, |
| void(*)(rbnode_type *, void *) | func, | ||
| void * | arg | ||
| ) |
Call function for all elements in the redblack tree, such that leaf elements are called before parent elements. So that all elements can be safely free()d. Note that your function must not remove the nodes from the tree. Since that may trigger rebalances of the rbtree.
| tree | the tree |
| func | function called with element and user arg. The function must not alter the rbtree. |
| arg | user argument. |
| rbnode_type rbtree_null_node |
the global empty node