table of contents
| SDS B+Tree(3) | dirsrv | SDS B+Tree(3) |
NAME¶
SDS B+Tree -
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_tchecksumming, 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_tcount)¶
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.
| Tue Jun 4 2024 | Version 1.3.11.12 |