sds_bptree - Man Page

struct sds_bptree_node
struct sds_bptree_instance

#define SDS_BPTREE_DEFAULT_CAPACITY   3
#define SDS_BPTREE_HALF_CAPACITY   2
#define SDS_BPTREE_BRANCH   4

sds_result sds_bptree_init (sds_bptree_instance **binst_ptr, uint16_t checksumming, int64_t(*key_cmp_fn)(void *a, void *b), void(*value_free_fn)(void *value), void(*key_free_fn)(void *key), void *(*key_dup_fn)(void *key))
sds_result sds_bptree_load (sds_bptree_instance *binst, void **keys, void **values, size_t count)
sds_result sds_bptree_destroy (sds_bptree_instance *binst)
sds_result sds_bptree_search (sds_bptree_instance *binst, void *key)
sds_result sds_bptree_retrieve (sds_bptree_instance *binst, void *key, void **target)
sds_result sds_bptree_delete (sds_bptree_instance *binst, void *key)
sds_result sds_bptree_insert (sds_bptree_instance *binst, void *key, void *value)
sds_result sds_bptree_verify (sds_bptree_instance *binst)
sds_result sds_bptree_map (sds_bptree_instance *binst, void(*fn)(void *k, void *v))
sds_result sds_bptree_difference (sds_bptree_instance *binst_a, sds_bptree_instance *binst_b, sds_bptree_instance **binst_difference)
sds_result sds_bptree_union (sds_bptree_instance *binst_a, sds_bptree_instance *binst_b, sds_bptree_instance **binst_union)
sds_result sds_bptree_intersect (sds_bptree_instance *binst_a, sds_bptree_instance *binst_b, sds_bptree_instance **binst_intersect)
sds_result sds_bptree_compliment (sds_bptree_instance *binst_a, sds_bptree_instance *binst_b, sds_bptree_instance **binst_compliment)
sds_result sds_bptree_filter (sds_bptree_instance *binst_a, int64_t(*fn)(void *k, void *v), sds_bptree_instance **binst_subset)

SDS_BPTREE_BRANCH 6 indicates that each node may potentially have up to 6 child nodes. This yields a broad tree, that requires fewer cache misses to travese (despite the higher number of comparisons to search).

SDS_BPTREE_DEFAULT_CAPACITY 5 represements that there are 5 values held per in the B+Tree and COW B+Tree. A signifigant amount of testing went into the tuning of this value for best performance.

SDS_BPTREE_HALF_CAPACITY 3 is pre-calculated as 'ceiling(default capacity / 2)'. This is used to assert when node splits and merges should be taken.

Return the set where elements that exist in A but not B only are returned.

Parameters

binst_a Instance A
binst_b Instance B
binst_compliment Output for a new instance that contains elements unique to A.

Return values

Result of the operation as sds_result.

Delete a key and value from the tree. This implies that the values are freed as part of this process.

Parameters

binst Instance to remove the key and value from.
key Key to delete, along with it's data.

Return values

Result of the operation as sds_result.

Destroy the instance. This frees all remaining values and keys from the structure. After this is called, the bptree may not be accessed.

Parameters

binst Instance to destroy.

Return values

Result of the operation as sds_result.

From instance a, and instance b, create a new insance that contains the keys and values where keys exist in a or b but not both.

Parameters

binst_a Instance A
binst_b Instance B
binst_difference Output for a new instance containing clones of different elements.

Return values

Result of the operation as sds_result.

Filter the set by applying a predicate, and return a new set containing the matching elements.

Parameters

binst_a Instance A
fn Predicate to apply. If this function returns 0 the element is excluded. All other values include the key/value.
binst_subset Output for a new instance containing the matched elements.

Return values

Result of the operation as sds_result.

Initialise an sds b+tree for usage.

Parameters

binst_ptr Pointer to a struct pointer for the instance to initialise.
checksumming Flag to enable online and search checksumming. 0 to disable.
key_cmp_fn Key comparison function.
value_free_fn Function to free values that are assigned to this structure.
key_free_fn Function to free keys that are inside of this structure.
key_dup_fn Function to duplication keys within the structure.

Return values

Result of the operation as sds_result.

Insert the key and value to the tree. If the key already exists, this operation will fail. The key is duplicated on insert, and the duplicated key's life is bound to the tree. This allows you to use stack values as keys, as we duplicate them on insert.

Parameters

binst Instance to insert into.
key Key to insert.
value Value to insert associated with key. May be NULL.

Return values

Result of the operation as sds_result.

Intersect the sets A and B, and return the elements that are present in both sets (but not either).

Parameters

binst_a Instance A
binst_b Instance B
binst_intersect Output for a new instance containing the elements that are intersecting.

Return values

Result of the operation as sds_result.

Bulk load data into a b+tree instance. The existing data in the b+tree instance will be destroyed during the operation. Keys must be sorted prior to calling this function. The index of items in values must match the corresponding key in keys, or be NULL. values may be NULL, which is assumed that all keys have null values associated. Count is the number of elements in keys and values. Key values are owned by the tree from this point, you MUST NOT free them. They must be able to be freed with your key_free_fn.

If you must load a large amount of data to the tree, this operation is signifigantly faster than repeated calls to insert, but relies on you using an appropriate qsort function.

Parameters

binst Instance to purge and load.
keys Array of sorted keys to load.
values Array of sorted values to load.
count Number of values in the arrays.

Return values

Result of the operation as sds_result.

Map a function over the instance. This does not create a new instance, you are expected to use the function to hand the data out to some other function.

WARNING! This function will probably change soon!

Parameters

binst The instance to map over.
fn The function to be applied to each key-value pair.

Return values

Result of the operation as sds_result.

Retrieve the value associated with key from this structure.

Parameters

binst Instance to retrieve the value from.
key Key to search for.
target Destination for the value to end up in. May be NULLed even if the key is not found.

Return values

Result of the operation as sds_result.

Search the instance for a key. Returns a SDS_KEY_PRESENT or SDS_KEY_NOT_PRESENT.

Parameters

binst Instance to search.
key Key to search for.

Return values

Result of the operation as sds_result.

Union the sets A and B, and return a new instance that contains keys and values that are present in either or both.

Parameters

binst_a Instance A
binst_b Instance B
binst_union Output for a new instance containing the elements from both sets.

Return values

Result of the operation as sds_result.

Verify the contents of the tree are correct and sane. If checksumming is enabled, this will validate all checksums. This is generally useful for debugging only or if you think you have some data issue related to your key comparison function.

Parameters

binst Instance to verify.

Return values

Result of the operation as sds_result.