libuproc
1.2.0
|
Binary search tree. More...
Data Structures | |
union | uproc_bst_key |
The BST key type. More... | |
struct | uproc_bst |
Binary search tree. More... | |
Enumerations | |
enum | uproc_bst_keytype { UPROC_BST_UINT, UPROC_BST_WORD } |
Which member of union uproc_bst_key is used. More... | |
enum | { UPROC_BST_KEY_NOT_FOUND = -404, UPROC_BST_KEY_EXISTS = -403 } |
BST specific return codes. More... | |
Functions | |
uproc_bst * | uproc_bst_create (enum uproc_bst_keytype key_type, size_t value_size) |
Initialize an empty binary search tree. More... | |
void | uproc_bst_destroy (uproc_bst *t) |
Destroy BST and all contained nodes. More... | |
int | uproc_bst_isempty (uproc_bst *t) |
Return non-zero if the tree is empty. More... | |
size_t | uproc_bst_size (const uproc_bst *t) |
Return the number of nodes. More... | |
int | uproc_bst_insert (uproc_bst *t, union uproc_bst_key key, const void *value) |
Insert item. More... | |
int | uproc_bst_update (uproc_bst *t, union uproc_bst_key key, const void *value) |
Insert or update item. More... | |
int | uproc_bst_get (uproc_bst *t, union uproc_bst_key key, void *value) |
Get item. More... | |
int | uproc_bst_remove (uproc_bst *t, union uproc_bst_key key, void *value) |
Remove item. More... | |
void | uproc_bst_map (const uproc_bst *t, void(*func)(union uproc_bst_key, void *, void *), void *opaque) |
Apply function to all items. More... | |
Binary search tree.
The tree is not self-balancing, so don't use it for bigger data sets that might be inserted in order.
The keys are of type union uproc_bst_key, which member the tree instance used is chosen via the first argument to uproc_bst_create(). Values are stored by copying the number of bytes given as the second argument to uproc_bst_create().
Example:
enum uproc_bst_keytype |
Which member of union uproc_bst_key is used.
Enumerator | |
---|---|
UPROC_BST_UINT |
.uint (uintmax_t) |
UPROC_BST_WORD |
.word (struct uproc_word) |
anonymous enum |
uproc_bst* uproc_bst_create | ( | enum uproc_bst_keytype | key_type, |
size_t | value_size | ||
) |
Initialize an empty binary search tree.
key_type | key type |
value_size | size of the stored values |
void uproc_bst_destroy | ( | uproc_bst * | t | ) |
Destroy BST and all contained nodes.
int uproc_bst_isempty | ( | uproc_bst * | t | ) |
Return non-zero if the tree is empty.
size_t uproc_bst_size | ( | const uproc_bst * | t | ) |
Return the number of nodes.
int uproc_bst_insert | ( | uproc_bst * | t, |
union uproc_bst_key | key, | ||
const void * | value | ||
) |
Insert item.
t | BST instance |
key | search key |
value | pointer to value to be stored |
int uproc_bst_update | ( | uproc_bst * | t, |
union uproc_bst_key | key, | ||
const void * | value | ||
) |
Insert or update item.
Like uproc_bst_insert(), but overwrites the value of an already present key.
t | BST instance |
key | search key |
value | pointer to value to be stored |
int uproc_bst_get | ( | uproc_bst * | t, |
union uproc_bst_key | key, | ||
void * | value | ||
) |
Get item.
t | BST instance |
key | search key |
value | OUT: value associated with the key |
int uproc_bst_remove | ( | uproc_bst * | t, |
union uproc_bst_key | key, | ||
void * | value | ||
) |
Remove item.
t | BST instance |
key | key of the item to remove |
value | OUT: removed value |
Returns 0 on success. If the key is not present, returns UPROC_BST_KEY_NOT_FOUND and does not modify the object pointed to by the second parameter.
void uproc_bst_map | ( | const uproc_bst * | t, |
void(*)(union uproc_bst_key, void *, void *) | func, | ||
void * | opaque | ||
) |
Apply function to all items.
The first two arguments passed to func
are the key and a pointer to the value of an item in the tree. The pointed-to value is not a copy, so modifying it will also affect the stored value. The third argument to func
is the user-supplied opaque
pointer.
t | BST instance |
func | function to call |
opaque | second argument to function |