Associative arrays implemented using B-trees. More...

Classes
struct	btree
	An associative array data structure backed by a B-tree. More...

struct	btree_entry
	Refers to a specific location in a B-tree. More...

Functions
static int	btree_contains_key (const btree m, const KeyType k)
	Returns whether the the given key exists in the `btree`. More...

static ValueType *	btree_entry_get (const btree_entry *ent)
	Gets a pointer to the value at an occupied entry. More...

static int	btree_entry_insert (btree_entry entry, const KeyType key, const ValueType *value)
	Inserts an element into the `btree` at a vacant entry. More...

static KeyType *	btree_entry_key (const btree_entry *ent)
	Gets a pointer to the key at an occupied entry. More...

static int	btree_entry_next (btree_entry *ent)
	Modifies an occupied entry to refer to its next element. More...

static int	btree_entry_occupied (const btree_entry *ent)
	Returns whether a entry refers to an existing element. More...

static int	btree_entry_prev (btree_entry *ent)
	Modifies an occupied entry to refer to its previous element. More...

static void	btree_entry_remove (btree_entry *ent)
	Removes the element at an occupied entry. More...

static void	btree_entry_xinsert (btree_entry entry, const KeyType key, const ValueType *value)
	Similar to `btree_entry_insert` but aborts on error. More...

static void	btree_find (btree m, const KeyType key, btree_entry *entry_out)
	Searches for the given `key`. More...

static void	btree_find_first (btree m, btree_entry entry_out)
	Locates the first (least) entry. More...

static void	btree_find_last (btree m, btree_entry entry_out)
	Locates the last (greatest) entry. More...

static ValueType *	btree_get (btree m, const KeyType k)
	Retrieves the value with the given key. More...

static const ValueType *	btree_get_const (const btree m, const KeyType k)
	Retrieves the value with the given key. More...

static void	btree_init (btree *m)
	Initializes an empty `btree`. More...

static int	btree_insert (btree m, const KeyType key, const ValueType value, ValueType value_out)
	Inserts an element into the `btree`. More...

static size_t	btree_len (const btree *m)
	Gets the number of elements. More...

static int	btree_remove (btree m, const KeyType key, KeyType key_out, ValueType value_out)
	Removes the element at the given key and stores the results in `key_out` and `value_out` respectively, returning `1`. More...

static void	btree_reset (btree *m)
	Removes all elements from a `btree` and frees all memory consumed by the B-tree nodes. More...

static int	btree_xinsert (btree m, const KeyType key, const ValueType value, ValueType value_out)
	Similar to `btree_insert` but aborts if an error occurs. More...

Detailed Description

Associative arrays implemented using B-trees.

This is a template header. All identifiers in this are prefixed with an arbitrary prefix provided by the user. Before including this header, <calico/btree_head.h> must be included as well.

The main parameters are:

KeyType: key type
ValueType: value type
CompareFunction: function used to compare keys, with a type that, through implicit conversions, can be called as if its type is int (*)(btree *, const KeyType *, const KeyType *) (default: cal_pcmp).

Some other parameters useful for tuning performance are:

MinArity: number of children per node (default: 8, minimum: 2)
SearchFunction: function used search for a key in a node (default: linear_sorted_search)
ChildIndexType: type used to store indices of child nodes (default: unsigned short)
HeightType: type used to store the height of the tree (default: unsigned char)

Here's an example:

#include <string.h>
#include <calico/btree_head.h>
#define Prefix id
#define KeyType int
#define ValueType double
#include <calico/btree_template.h>
#define Prefix si
#define KeyType const char *
#define ValueType int
#define CompareFunction strcmp
#include <calico/btree_template.h>
int main(void)
{
    int i = 42;
    double d = 1.5;
    id_btree t1;
    si_btree t2;
    id_btree_init(&t1);
    id_btree_insert(&t2, &i, &d);
    id_btree_reset(&t1);
    si_btree_init(&t2);
    si_btree_insert(&t2, &"hello", &i);
    si_btree_reset(&t2);
    return 0;
}

Function Documentation

static int btree_contains_key	(	const btree *	m,
		const KeyType *	k
	)

inlinestatic

Returns whether the the given key exists in the btree.

static ValueType* btree_entry_get ( const btree_entry * ent )

inlinestatic

Gets a pointer to the value at an occupied entry.

If the entry is not occupied, the behavior is undefined.

For sets, this returns a non-null pointer if the entry exists. Otherwise, it returns NULL.

static int btree_entry_insert	(	btree_entry *	entry,
		const KeyType *	key,
		const ValueType *	value
	)

inlinestatic

Inserts an element into the btree at a vacant entry.

If the entry is not vacant, the behavior is undefined.

If the insert is successful, the entry is invalidated and 0 is returned. On error, a positive integer is returned.

Note: The key must match the original key used to obtain the vacant entry, or the behavior is undefined.

static KeyType* btree_entry_key ( const btree_entry * ent )

inlinestatic

Gets a pointer to the key at an occupied entry.

If the entry is not occupied, the behavior is undefined.

Note

The key can be modified as long as it compares equal to its original value. Otherwise, if the key is modified to a value unequal to its original, or invalidated by, e.g., freeing its associated memory, then the behavior of the following operations shall be undefined until the original value is restored:

btree_find
btree_get
btree_get_const
btree_insert
btree_remove
btree_xinsert

static int btree_entry_next ( btree_entry * ent )

inlinestatic

Modifies an occupied entry to refer to its next element.

If there are no more elements, the next entry is vacant. Otherwise, it is occupied. The argument ent must point to an occupied entry, or the behavior is undefined. Returns 1 if the new entry is occupied, 0 if the new entry is vacant.

static int btree_entry_occupied ( const btree_entry * ent )

inlinestatic

Returns whether a entry refers to an existing element.

static int btree_entry_prev ( btree_entry * ent )

inlinestatic

Modifies an occupied entry to refer to its previous element.

If there are no more elements, the previous entry is vacant. Otherwise, it is occupied. The argument ent must point to an occupied entry, or the behavior is undefined.

static void btree_entry_remove ( btree_entry * ent )

inlinestatic

Removes the element at an occupied entry.

The entry is invalidated afterwards. If the entry is not occupied, the behavior is undefined.

static void btree_entry_xinsert	(	btree_entry *	entry,
		const KeyType *	key,
		const ValueType *	value
	)

inlinestatic

Similar to btree_entry_insert but aborts on error.

static void btree_find	(	btree *	m,
		const KeyType *	key,
		btree_entry *	entry_out
	)

inlinestatic

Searches for the given key.

The entry returned can be either occupied or vacant, which indicates whether the key was found.

static void btree_find_first	(	btree *	m,
		btree_entry *	entry_out
	)

inlinestatic

Locates the first (least) entry.

If the B-tree is empty, a vacant entry is returned.

static void btree_find_last	(	btree *	m,
		btree_entry *	entry_out
	)

inlinestatic

Locates the last (greatest) entry.

If the B-tree is empty, a vacant entry is returned.

static ValueType* btree_get	(	btree *	m,
		const KeyType *	k
	)

inlinestatic

Retrieves the value with the given key.

Returns NULL if it is not found.

static const ValueType* btree_get_const	(	const btree *	m,
		const KeyType *	k
	)

inlinestatic

Retrieves the value with the given key.

Returns NULL if it is not found.

static void btree_init ( btree * m )

inlinestatic

Initializes an empty btree.

static int btree_insert	(	btree *	m,
		const KeyType *	key,
		const ValueType *	value,
		ValueType *	value_out
	)

inlinestatic

Inserts an element into the btree.

If an element with the same key already exists, its value is replaced (the key remains unchanged, however) and the old value is stored at value_out.

value and value_out are permitted to alias each other.

If the element was added without replacing an existing element, 0 is returned. If an existing element was replaced, 1 is returned. If an error occurs, a negative value is returned.

Note: If the keys and/or values are associated with resources, they are not automatically released. In this case, to prevent memory leaks it is necessary to free the old value stored in value_out as well as the key if an existing value was replaced. For example,
if (btree_xinsert(m, &key, &value, &old_value)) {
free(key);
free(old_value);
}

static size_t btree_len ( const btree * m )

inlinestatic

Gets the number of elements.

This is an O(1) operation.

static int btree_remove	(	btree *	m,
		const KeyType *	key,
		KeyType *	key_out,
		ValueType *	value_out
	)

inlinestatic

Removes the element at the given key and stores the results in *key_out and *value_out respectively, returning 1.

If the element does not exist, does nothing and returns 0.

If the key and/or value are associated with resources, it may be necessary to release them if btree_remove returns 1, like this:

if (btree_remove(m, key, &old_key, &old_value)) {
    free(old_key);
    free(old_value);
}

key and key_out are permitted to alias.

static void btree_reset ( btree * m )

inlinestatic

Removes all elements from a btree and frees all memory consumed by the B-tree nodes.

This operation does not read any of the keys.

Note: If the keys or values are associated with resources that need to be released, btree_reset does not release them! In this situation, one must manually iterate over each element and release them:
for (btree_find_first(m, &entry);
btree_entry_occupied(&entry);
btree_entry_next(&entry)) {
free(btree_entry_key(&entry));
free(btree_entry_get(&entry));
}
btree_reset(m);

static int btree_xinsert	(	btree *	m,
		const KeyType *	key,
		const ValueType *	value,
		ValueType *	value_out
	)

inlinestatic

Similar to btree_insert but aborts if an error occurs.

Classes

Functions

Detailed Description

Function Documentation