table of contents
| sds_bptree(3) | dirsrv | sds_bptree(3) |
NAME¶
sds_bptree - SDS B+Tree
SYNOPSIS¶
Data Structures¶
struct sds_bptree_node
struct sds_bptree_instance
Macros¶
#define SDS_BPTREE_DEFAULT_CAPACITY 3
#define SDS_BPTREE_HALF_CAPACITY 2
#define SDS_BPTREE_BRANCH 4
Functions¶
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)
Detailed Description¶
Unprotected B+Tree for void types. Supports fast set operations, search, insert, delete and build.
This structure should be considered for all locations where unprotected AVL treels, or array based binary search trees are used.
Macro Definition Documentation¶
#define SDS_BPTREE_BRANCH 4¶
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).
#define SDS_BPTREE_DEFAULT_CAPACITY 3¶
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.
#define SDS_BPTREE_HALF_CAPACITY 2¶
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.
Function Documentation¶
sds_result sds_bptree_compliment (sds_bptree_instance * binst_a, sds_bptree_instance * binst_b, sds_bptree_instance ** binst_compliment)¶
Return the set where elements that exist in A but not B only are returned.
Parameters
binst_b Instance B
binst_compliment Output for a new instance that contains elements unique to A.
Return values
sds_result sds_bptree_delete (sds_bptree_instance * binst, void * key)¶
Delete a key and value from the tree. This implies that the values are freed as part of this process.
Parameters
key Key to delete, along with it's data.
Return values
sds_result sds_bptree_destroy (sds_bptree_instance * binst)¶
Destroy the instance. This frees all remaining values and keys from the structure. After this is called, the bptree may not be accessed.
Parameters
Return values
sds_result sds_bptree_difference (sds_bptree_instance * binst_a, sds_bptree_instance * binst_b, sds_bptree_instance ** binst_difference)¶
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_b Instance B
binst_difference Output for a new instance containing clones of different elements.
Return values
sds_result sds_bptree_filter (sds_bptree_instance * binst_a, int64_t(*)(void *k, void *v) fn, sds_bptree_instance ** binst_subset)¶
Filter the set by applying a predicate, and return a new set containing the matching elements.
Parameters
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
sds_result sds_bptree_init (sds_bptree_instance ** binst_ptr, uint16_t checksumming, int64_t(*)(void *a, void *b) key_cmp_fn, void(*)(void *value) value_free_fn, void(*)(void *key) key_free_fn, void *(*)(void *key) key_dup_fn)¶
Initialise an sds b+tree for usage.
Parameters
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
sds_result sds_bptree_insert (sds_bptree_instance * binst, void * key, void * value)¶
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
key Key to insert.
value Value to insert associated with key. May be NULL.
Return values
sds_result sds_bptree_intersect (sds_bptree_instance * binst_a, sds_bptree_instance * binst_b, sds_bptree_instance ** binst_intersect)¶
Intersect the sets A and B, and return the elements that are present in both sets (but not either).
Parameters
binst_b Instance B
binst_intersect Output for a new instance containing the elements that are intersecting.
Return values
sds_result sds_bptree_load (sds_bptree_instance * binst, void ** keys, void ** values, size_t count)¶
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
keys Array of sorted keys to load.
values Array of sorted values to load.
count Number of values in the arrays.
Return values
sds_result sds_bptree_map (sds_bptree_instance * binst, void(*)(void *k, void *v) fn)¶
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
fn The function to be applied to each key-value pair.
Return values
sds_result sds_bptree_retrieve (sds_bptree_instance * binst, void * key, void ** target)¶
Retrieve the value associated with key from this structure.
Parameters
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
sds_result sds_bptree_search (sds_bptree_instance * binst, void * key)¶
Search the instance for a key. Returns a SDS_KEY_PRESENT or SDS_KEY_NOT_PRESENT.
Parameters
key Key to search for.
Return values
sds_result sds_bptree_union (sds_bptree_instance * binst_a, sds_bptree_instance * binst_b, sds_bptree_instance ** binst_union)¶
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_b Instance B
binst_union Output for a new instance containing the elements from both sets.
Return values
sds_result sds_bptree_verify (sds_bptree_instance * binst)¶
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
Return values
Author¶
Generated automatically by Doxygen for dirsrv from the source code.
| Fri May 31 2024 | Version 2.4.5 |