sds_bptree(3)

💖 NAME 💖

okay so bestie, this is the sds_bptree(3) page from the Library Functions Manual, and it's all about sds_bptree — the 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. It 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 traverse (despite the higher number of comparisons to search).

🌈 #define SDS_BPTREE_DEFAULT_CAPACITY 3 🌈

SDS_BPTREE_DEFAULT_CAPACITY 5 represents that there are 5 values held per in the B+Tree and COW B+Tree. A significant 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_bptree_compliment

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

---

💅 sds_bptree_delete

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:

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

---

💅 sds_bptree_destroy

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:

• binst — Instance to destroy.

Return values: Result of the operation as sds_result.

---

💅 sds_bptree_difference

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

---

💅 sds_bptree_filter

sds_result sds_bptree_filter (sds_bptree_instance * binst_a,
    int64_t(* fn )(void *k, void *v), sds_bptree_instance ** binst_subset)

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.

---

💅 sds_bptree_init

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))

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.

---

💅 sds_bptree_insert

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:

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

---

💅 sds_bptree_intersect

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

---

💅 sds_bptree_load

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

---

💅 sds_bptree_map

sds_result sds_bptree_map (sds_bptree_instance * binst, void(* fn )(void *k,
    void *v))

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.

---

💅 sds_bptree_retrieve

sds_result sds_bptree_retrieve (sds_bptree_instance * binst, void * key,
    void ** target)

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.

---

💅 sds_bptree_search

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:

• binst — Instance to search.
• key — Key to search for.

Return values: Result of the operation as sds_result.

---

💅 sds_bptree_union

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

---

💅 sds_bptree_verify

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:

• binst — Instance to verify.

Return values: Result of the operation as sds_result.

---

💜 Author 💜

Generated automatically by Doxygen for dirsrv from the source code.

---

mwah 💋 — this page's source is dirsrv, version Version 3.3.0, and the footer was also giving sds_bptree(3) energy; there was no date in the footer, so bestie I'm not inventing one. 🎀✨