sds_bptree_cow(3)

🌸 okay bestie, welcome to sds_bptree_cow(3) 🌸

This one's from the Library Functions Manual, and it's lowkey the whole reason you'd even show up to this library. It's a whole B+Tree that does copy-on-write, and it's giving main character energy. Let's get into it 💅

---

✨ NAME ✨

sds_bptree_cow — SDS Copy on Write B+Tree 🦋

---

🎀 SYNOPSIS 🎀

💖 Data Structures 💖

• struct sds_bptree_node_list
• struct sds_bptree_transaction
• struct sds_bptree_cow_instance

🦋 Enumerations 🦋

enum sds_txn_state { SDS_TXN_READ = 0, SDS_TXN_WRITE = 1 }

🌟 Functions 🌟

These are the exact signatures, no cap, copy them character for character:

sds_result sds_bptree_cow_init (sds_bptree_cow_instance **binst_ptr, uint16_t checksumming, int64_t(*key_cmp_fn)(void *a, void *b), void(*value_free_fn)(void *value), void *(*value_dup_fn)(void *key), void(*key_free_fn)(void *key), void *(*key_dup_fn)(void *key))
sds_result sds_bptree_cow_destroy (sds_bptree_cow_instance *binst)
sds_result sds_bptree_cow_verify (sds_bptree_cow_instance *binst)
sds_result sds_bptree_cow_rotxn_begin (sds_bptree_cow_instance *binst, sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_rotxn_close (sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_wrtxn_begin (sds_bptree_cow_instance *binst, sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_wrtxn_abort (sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_wrtxn_commit (sds_bptree_transaction **btxn)
sds_result sds_bptree_cow_search (sds_bptree_transaction *btxn, void *key)
sds_result sds_bptree_cow_retrieve (sds_bptree_transaction *btxn, void *key, void **target)
sds_result sds_bptree_cow_delete (sds_bptree_transaction *btxn, void *key)
sds_result sds_bptree_cow_insert (sds_bptree_transaction *btxn, void *key, void *value)
sds_result sds_bptree_cow_update (sds_bptree_transaction *btxn, void *key, void *value)
sds_result sds_bptree_cow_search_atomic (sds_bptree_cow_instance *binst, void *key)
sds_result sds_bptree_cow_retrieve_atomic (sds_bptree_cow_instance *binst, void *key, void **target)
sds_result sds_bptree_cow_delete_atomic (sds_bptree_cow_instance *binst, void *key)
sds_result sds_bptree_cow_insert_atomic (sds_bptree_cow_instance *binst, void *key, void *value)

---

💅 Detailed Description 💅

It's a thread safe Copy on Write B+Tree. It supports parallel read transactions and serialised writes with ref counted members. Periodt.

This is, like, a very important structure — arguably the primary reason to consume this library at all. There are a bunch of important properties this tree provides, and you're gonna hear about all of them 🫶

🔑 keys and values are bound to the tree's life

Okay so the key concept here: all values and keys contained in the tree have their lifetimes bound to the life of the tree and its nodes. Why? Because of the transactional nature of the structure, bestie.

Picture it: a value has been inserted into the tree. We take a read transaction of the tree in thread A. Thread B then deletes the value that was inserted. But because A still refers to the value, it is not freed until thread A closes its read transaction. So all read transactions are always valid, and memory can still be freed correctly. Iconic behavior, honestly.

This has many applications, including the Directory Server plugin subsystem. We can use this property to guarantee a plugin exists for the life of an operation, and we only free it once all consumers have completed their operations with it. Chef's kiss 😭

🦋 writes don't block reads

Another key aspect: write transactions do not block read transactions. Reads can be completed in parallel to writes with complete safety. Write operations are serialised in this structure. That makes it extremely effective for long read operations with many queries, without interrupting other threads. The way that it just... works 🔥

🎀 consistency inside a read transaction

Along with the value and key ownership properties, we can guarantee that the content of the tree within a read transaction will not be removed or added, and will be consistent within the tree.

⚠️ however, we can't guarantee a user doesn't change the value. That part? Not our problem, bestie 💀

🍓 single thread tree vs COW, the comparison

As a comparison: the single thread tree is, on paper, much faster than the COW version due to less memory operations. But in a multi thread use case, the COW version is significantly faster and safer than a mutex protected single thread tree. It's giving glow-up ✨

🌈 what it's actually good for

This tree can be used as a form of object manager for C, and also as a way to allow async operations between threads while maintaining thread safety across an application. This assumes that the operations are largely parallel and batch read oriented over write heavy small transactions. Iykyk.

---

👑 Enumeration Type Documentation 👑

💜 enum sds_txn_state 💜

sds_txt_state lists the possible states of a transaction. (yes, that's spelled exactly like that in here, don't come for me 🙈)

⭐ Enumerators ⭐

• SDS_TXN_READ — 0. This is a read only transaction. No mutable actions may be taken. Look, don't touch 📛
• SDS_TXN_WRITE — 1. This is a read and write transaction. You may perform all read operations, and also all write operations. Go off, you have full permissions 💅

💖 FUNCTION DOCUMENTATION 💖

Ok bestie, this is the main event — every single function in this tree, spelled out. Grab a snack. 🍓

---

✨ sds_bptree_cow_delete

sds_result sds_bptree_cow_delete (sds_bptree_transaction * btxn, void * key)

Deletes key and the data attached to it from the tree. Heads up though — this only works on a valid write transaction, and none of your changes actually show up until a commit happens. Existing readers will literally never see this change until they close their transaction and open a brand new one. No sneaky peeking. 👀

Parameters

• btxn — the write transaction you're operating on.
• key — the key to delete, along with its associated data. And listen: if you already called retrieve on this key, then the key and value must not be accessed after this point within this transaction's lifetime, because the values may get invalidated. Rude but true. 💀

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_delete_atomic

sds_result sds_bptree_cow_delete_atomic (sds_bptree_cow_instance * binst, void * key)

Does the exact same thing as delete, but it implies a single short-lived write transaction plus the commit phase. All handled for you, no cap. 🫶

If you have multiple searches to make, it is better to use a write transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.

Parameters

• binst — the cow b+tree to delete from.
• key — the key to delete. This removes the associated value too.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_destroy

sds_result sds_bptree_cow_destroy (sds_bptree_cow_instance * binst)

Destroys an instance. Like, fully. This nukes all open transactions and frees all the tree elements. It's giving cleanup era. 🧹

Parameters

• binst — the cow b+tree to destroy.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_init

sds_result sds_bptree_cow_init (sds_bptree_cow_instance ** binst_ptr, uint16_t checksumming, int64_t(* key_cmp_fn )(void *a, void *b), void(* value_free_fn )(void *value), void *(* value_dup_fn )(void *key), void(* key_free_fn )(void *key), void *(* key_dup_fn )(void *key))

Initialises an sds cow b+tree so it's ready to go. This allocates space for the tree and bootstraps that very first blank transaction. Baby's first transaction. 👑

Parameters

• binst_ptr — the pointer you want filled with the cow b+tree instance.
• checksumming — during DEBUG, this flag enables tree content checksumming.
• key_cmp_fn — the comparison function for keys in the tree.
• value_free_fn — during operation, the values assigned to this tree are owned by the instance, and this lets us free the values when we need to.
• value_dup_fn — during a copy on write operation, we need to be able to copy the values in the tree.
• key_free_fn — frees the key value.
• key_dup_fn — duplicates a key value.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_insert

sds_result sds_bptree_cow_insert (sds_bptree_transaction * btxn, void * key, void * value)

Inserts a key and its associated value into the tree through a valid write transaction. Big vibe shift here: the keys and values you insert now completely belong to the tree, and may be duplicated or freed at any time. So after you hand a key and value over, you're only allowed to touch them through the retrieve interface, and only in valid scenarios. iykyk. 💅

Parameters

• btxn — the write transaction to operate on.
• key — the key to insert. If a duplicate key is detected, an error is returned.
• value — the value to insert. May be NULL.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_insert_atomic

sds_result sds_bptree_cow_insert_atomic (sds_bptree_cow_instance * binst, void * key, void * value)

Works just like insert, but it implies a single short-lived write transaction and commit phase. One and done. 🔥

If you have multiple searches to make, it is better to use a write transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.

Parameters

• binst — the cow b+tree to insert into.
• key — the key to insert.
• value — the value to insert, associated with key.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_retrieve

sds_result sds_bptree_cow_retrieve (sds_bptree_transaction * btxn, void * key, void ** target)

Searches a tree using a valid transaction reference. This hands you back KEY_PRESENT or KEY_NOT_PRESENT depending on whether the search succeeds or not. Bonus: the value attached to key gets placed into the pointer you passed as target. The search can run on a valid uncommitted write transaction or a read transaction. Versatile icon. 🌈

Parameters

• btxn — the transaction pointer to search.
• key — the key to search for.
• target — the pointer where the value will be placed on a successful search. NULL is a valid value, so be sure to check the result!

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_retrieve_atomic

sds_result sds_bptree_cow_retrieve_atomic (sds_bptree_cow_instance * binst, void * key, void ** target)

Works just like retrieve, but it implies a single short-lived read transaction. Important consequence: calling this means you must free the value returned to you. Not optional, bestie. 😭

If you have multiple searches to make, it is better to use a read transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.

Parameters

• binst — the cow b+tree to search.
• key — the key to search for.
• target — the value retrieved. You must free this after use, with the same free function as the binst holds.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_rotxn_begin

sds_result sds_bptree_cow_rotxn_begin (sds_bptree_cow_instance * binst, sds_bptree_transaction ** btxn)

Starts a read-only transaction on the tree. This guarantees the memory consistency of all the values in the tree for the whole duration of the operation. Immovable object energy. 🗿

Parameters

• binst — the cow b+tree to start a transaction in.
• btxn — the pointer to a transaction to be allocated.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_rotxn_close

sds_result sds_bptree_cow_rotxn_close (sds_bptree_transaction ** btxn)

Wraps up a read-only transaction. Once you've closed it, it may not be used again, and closing may trigger a garbage collection. Also — and this is the big one — after you close the transaction, you may NOT reference any elements you viewed in the tree. Gone, reduced to atoms. 💀

Good news though: there's no penalty for holding this open, so just keep the transaction open until you're sure you don't need the values anymore. Free real estate, basically.

Parameters

• btxn — the transaction to close.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_search

sds_result sds_bptree_cow_search (sds_bptree_transaction * btxn, void * key)

Searches a tree using a valid transaction reference. Returns KEY_PRESENT or KEY_NOT_PRESENT depending on whether the search succeeds or not. The search can run on a valid uncommitted write transaction, or a read transaction. Same energy as retrieve, just without the value handoff. 🦋

Parameters

• btxn — the transaction pointer to search.
• key — the key to search for.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_search_atomic

sds_result sds_bptree_cow_search_atomic (sds_bptree_cow_instance * binst, void * key)

Works just like search, but it implies a single short-lived read transaction. Pure vibes, minimal commitment. ✨

If you have multiple searches to make, it is better to use a read transaction due to the memory design of the transaction. Multiple atomics may cause contention on certain parts of the transaction code.

Parameters

• binst — the cow b+tree to search.
• key — the key to search for.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_update

sds_result sds_bptree_cow_update (sds_bptree_transaction * btxn, void * key, void * value)

Updates a key to have a new associated value, inside a valid write transaction. This is more efficient than doing delete → insert, so for updates it's the preferred route. And here's the moment it's actually needed: when you have previous read transactions but you want to alter a value without affecting the read. The move is — call retrieve, copy the value, then call update on the b+tree. Chef's kiss. 👩‍🍳💋

Parameters

• btxn — the write transaction to operate on.
• key — the key to update. If the key does not exist, fall back to insert.
• value — the value to update. May be NULL.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_verify

sds_result sds_bptree_cow_verify (sds_bptree_cow_instance * binst)

Verifies that an instance holds up under a number of properties. This should only be used when you're debugging issues. And if you do find an issue — add it to the test cases! That's the whole assignment, bestie. 🎀

Parameters

• binst — the cow b+tree to verify.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_wrtxn_abort

sds_result sds_bptree_cow_wrtxn_abort (sds_bptree_transaction ** btxn)

Aborts and rolls back all the changes made during a write transaction. This operation is guaranteed safe to all other transactions, including future writes — so no collateral damage. 🌸

But fr fr: after the abort function is called, you must NOT access this transaction again. Not once.

Parameters

• btxn — the transaction to abort and destroy.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_wrtxn_begin

sds_result sds_bptree_cow_wrtxn_begin (sds_bptree_cow_instance * binst, sds_bptree_transaction ** btxn)

Begins a write transaction, which is what lets you alter the content of the tree. Because this transaction is exclusive, it's best if you can keep it for the "minimal" time possible — it's serialised, so everybody else is waiting on you. ⏳

The good news: changes made in a write transaction are guaranteed to have no impact on any types currently in a read transaction. Safe and sound.

Parameters

• binst — the b+tree to begin a write transaction in.
• btxn — the pointer to a location for the transaction to be created into.

Return values

Result of the operation as sds_result.

---

✨ sds_bptree_cow_wrtxn_commit

sds_result sds_bptree_cow_wrtxn_commit (sds_bptree_transaction ** btxn)

Commits the transaction. After this operation the transaction must not be accessed again, periodt. All changes to the tree become visible right after this call is made, and new read transactions will get this view. 🔥

One important detail: commit does not affect pre-existing read transactions' data. They keep their old view, unbothered.

Parameters

• btxn — the transaction to commit.

Return values

Result of the operation as sds_result.

---

🌷 Author

Generated automatically by Doxygen for dirsrv from the source code.

---

And that's the whole page, bestie! 💜 This is dirsrv Version 3.3.0, page sds_bptree_cow(3) — go forth and commit (responsibly, with minimal transaction time). Mwah! 💅✨