libuproc  1.2.0
Data Structures | Enumerations | Functions

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_bstuproc_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...
 

Detailed Description

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:

struct { int foo; double bar; } value;
union uproc_bst_key key;
if (!t) {
// handle error
}
key.uint = 23;
value.foo = 42;
value.bar = 3.14;
uproc_bst_update(t, key, &value);
value.foo = 0;
uproc_bst_get(t, key, &value);
assert(value.foo == 42);

Enumeration Type Documentation

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

BST specific return codes.

Enumerator
UPROC_BST_KEY_NOT_FOUND 

BST doesn't contain an item with the given key.

UPROC_BST_KEY_EXISTS 

BST already contains an item with the given key.

Function Documentation

uproc_bst* uproc_bst_create ( enum uproc_bst_keytype  key_type,
size_t  value_size 
)

Initialize an empty binary search tree.

Parameters
key_typekey type
value_sizesize 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.

Parameters
tBST instance
keysearch key
valuepointer to value to be stored
Returns
Returns 0 on success, UPROC_BST_KEY_EXISTS if the key is already present. If memory allocation fails, returns -1 and sets uproc_errno to UPROC_ENOMEM.
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.

Parameters
tBST instance
keysearch key
valuepointer to value to be stored
int uproc_bst_get ( uproc_bst t,
union uproc_bst_key  key,
void *  value 
)

Get item.

Parameters
tBST instance
keysearch key
valueOUT: value associated with the key
Returns
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.
int uproc_bst_remove ( uproc_bst t,
union uproc_bst_key  key,
void *  value 
)

Remove item.

Parameters
tBST instance
keykey of the item to remove
valueOUT: 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.

Parameters
tBST instance
funcfunction to call
opaquesecond argument to function