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