API Reference

consistent_set

Functions

template<typename callable_at>
status_t invoke_safely(callable_at &&callable) noexcept

template<typename keys_at, typename compare_at, typename allocator_at>
void merge_overwrite(std::set<keys_at, compare_at, allocator_at> &target, std::set<keys_at, compare_at, allocator_at> &source) noexcept

Unlike std::set<>::merge, this function overwrites existing values.

https://en.cppreference.com/w/cpp/container/set#Member_types https://en.cppreference.com/w/cpp/container/set/insert

namespace unum

namespace ucset

Functions

template<typename callable_at>
status_t invoke_safely(callable_at &&callable) noexcept

template<typename keys_at, typename compare_at, typename allocator_at>
void merge_overwrite(std::set<keys_at, compare_at, allocator_at> &target, std::set<keys_at, compare_at, allocator_at> &source) noexcept

Unlike std::set<>::merge, this function overwrites existing values.

https://en.cppreference.com/w/cpp/container/set#Member_types https://en.cppreference.com/w/cpp/container/set/insert

template<typename element_at, typename comparator_at = std::less<element_at>, typename allocator_at = std::allocator<std::uint8_t>>
class consistent_set_gt

#include <consistent_set.hpp>

Atomic (in DBMS and Set Theory sense) Transactional Store on top of a Standard Templates Library. It can be used as a Key-Value store, if you store as entries.

Goals

• Atomicity of batch operations.

• Simplicity and familiarity. For performance, consistency, Multi-Version Concurrency control and others, check out the set_avl_gt.

Comparisons

Template Parameters:

• element_at –

• comparator_at –

• allocator_at –

Public Types

using element_t = element_at

using comparator_t = comparator_at

using allocator_t = allocator_at

using versioning_t = element_versioning_gt<element_t, comparator_t>

using identifier_t = typename versioning_t::identifier_t

using generation_t = typename versioning_t::generation_t

using dated_identifier_t = typename versioning_t::dated_identifier_t

using watch_t = typename versioning_t::watch_t

using watched_identifier_t = typename versioning_t::watched_identifier_t

using entry_t = typename versioning_t::entry_t

using entry_comparator_t = typename versioning_t::entry_comparator_t

Public Functions

inline std::size_t size() const noexcept

inline bool empty() const noexcept

inline std::optional<transaction_t> transaction() noexcept

Starts a transaction with a new sequence number. If succeeded, that transaction can later be reset to reuse the memory. If fails, an empty is returned.

inline status_t upsert(element_t &&element) noexcept

Moves a single new.

Parameters:

• element – into the container. This operation is identical to creating and committing a single upsert transaction.

• element – [in] The element to import.

Returns:

status_t Can fail, if out of memory.

template<typename elements_begin_at, typename elements_end_at = elements_begin_at>
inline status_t upsert(elements_begin_at begin, elements_end_at end) noexcept

Atomically updates-or-inserts a batch of entries. Either all entries will be inserted, or all will fail.

The dereferencing operator of the passed

See also

std::make_move_iterator().

Parameters:

• iterator – should return R-Value references of .

• begin –

• end –

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

Finds a member equal to the given comparable.

comparable Object, comparable to and convertible to .

Parameters:

• callback_found – Callback to receive an element_t const &. Ideally, noexcept.

• callback_missing – Callback to be triggered, if nothing was found.

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

Finds the first member greater than the given comparable.

comparable Object, comparable to and convertible to .

Parameters:

• callback_found – Callback to receive an element_t const &. Ideally, noexcept.

• callback_missing – Callback to be triggered, if nothing was found.

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) const noexcept

Implements a heterogeneous lookup for all the entries falling in between the lower and the upper. Degrades to equal_range(), if they are the same.

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

Implements a heterogeneous lookup for all the entries falling in between the lower and the upper. Degrades to equal_range(), if they are the same. Allows in-place modification.

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t erase_range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

Erases all the entries falling in between the lower and the upper.

inline status_t clear() noexcept

Removes all the data from the container.

inline status_t reserve(std::size_t) noexcept

Optimization, that informs container to pre-allocate memory in-advance. Doesn’t guarantee, that the following “upserts” won’t fail with “out of memory”.

template<typename lower_at, typename upper_at, typename generator_at, typename callback_at = no_op_t>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, callback_at &&callback) const noexcept

Uniformly Random-Samples just one entry from the container. Searches within entries that compare equal to the provided comparable.

! This implementation is extremely inefficient and requires a two-pass approach. ! On the first run we estimate the number of entries matching the comparable. ! On the second run we choose a random integer below the number of matched entries ! and loop until we advance the STL iterator enough.

! Depends on the equal_range. Use the Reservoir Sampling overload with ! temporary memory if you want to sample more than one entry.

Parameters:

• generator – [in] Random generator to be invoked on the internal distribution.

• callback – [in] Callback to receive the sampled entry.

template<typename lower_at, typename upper_at, typename generator_at, typename output_iterator_at>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, std::size_t &seen, std::size_t reservoir_capacity, output_iterator_at &&reservoir) const noexcept

Implements Uniform Reservoir Sampling into the provided output buffer. Searches within entries that compare equal to the provided comparable.

Parameters:

• generator – [in] Random generator to be invoked on the internal distribution.

• seen – [inout] The number of previously seen entries. Zero, by default.

• reservoir_capacity – [in] The number of entries that can fit in reservoir.

• reservoir – [in] Iterator to the beginning of the output reservoir.

Public Static Functions

static inline std::optional<store_t> make() noexcept

Creates a new collection of this type without throwing exceptions. If fails, an empty is returned.

Private Types

using entry_allocator_t = typename std::allocator_traits<allocator_t>::template rebind_alloc<entry_t>

using entry_set_t = std::set<entry_t, entry_comparator_t, entry_allocator_t>

using entry_iterator_t = typename entry_set_t::iterator

using watches_allocator_t = typename std::allocator_traits<allocator_t>::template rebind_alloc<watched_identifier_t>

using watches_array_t = std::vector<watched_identifier_t, watches_allocator_t>

using watch_iterator_t = typename watches_array_t::iterator

using store_t = consistent_set_gt

Private Functions

inline consistent_set_gt() noexcept(false)

inline generation_t new_generation() noexcept

template<typename callback_at = no_op_t>
inline void erase_visible(entry_iterator_t begin, entry_iterator_t end, callback_at &&callback = {}) noexcept

inline void unmask_and_compact(entry_iterator_t begin, entry_iterator_t end, generation_t generation_to_unmask) noexcept

inline status_t upsert(entry_set_t &sources) noexcept

Atomically updates-or-inserts a collection of entries. Either all entries will be inserted, or all will fail. This operation is identical to creating and committing a transaction with all the same elements put into it.

not take R-Value?

We want this operation to be consistent, as the rest of the container, so we need a place to return all the objects, if the operation fails. With R-Value, the batch would be lost.

Parameters:

sources – [inout] Collection of entries to import.

Returns:

status_t Can fail, if out of memory.

Private Members

entry_set_t entries_

generation_t generation_ = {0}

std::size_t visible_count_ = {0}

std::size_t visible_deleted_count_ = {0}

Friends

friend class transaction_t

class transaction_t

#include <consistent_set.hpp>

Public Functions

transaction_t(transaction_t&&) noexcept = default

transaction_t &operator=(transaction_t&&) noexcept = default

transaction_t(transaction_t const&) = delete

transaction_t &operator=(transaction_t const&) = delete

inline generation_t generation() const noexcept

inline status_t upsert(element_t &&element) noexcept

inline status_t erase(identifier_t const &id) noexcept

inline status_t reserve(std::size_t size) noexcept

inline status_t watch(identifier_t const &id) noexcept

inline status_t watch(entry_t const &entry) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

Finds a member equal to the given comparable. You may want to watch() the received object, it’s not done by default. Unlike consistent_set_gt::find(), will include the entries added to this transaction.

comparable Object, comparable to and convertible to .

Parameters:

• callback_found – Callback to receive an element_t const &. Ideally, noexcept.

• callback_missing – Callback to be triggered, if nothing was found.

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

Finds the first member greater than the given comparable. You may want to watch() the received object, it’s not done by default. Unlike consistent_set_gt::find(), will include the entries added to this transaction.

comparable Object, comparable to and convertible to .

Parameters:

• callback_found – Callback to receive an element_t const &. Ideally, noexcept.

• callback_missing – Callback to be triggered, if nothing was found.

inline status_t stage() noexcept

inline status_t reset() noexcept

Resets the state of the transaction.

In more detail:

• All the updates staged in DB will be reverted.

• All the updates will in this Transaction will be lost.

• All the watches will be lost.

• New generation will be assigned.

inline status_t rollback() noexcept

Rolls-back a previously “staged” transaction.

In more detail:

• All the updates will be reverted in the DB.

• All the updates will re-emerge in this Transaction.

• All the watches will be lost.

• New generation will be assigned.

inline status_t commit() noexcept

Private Types

enum class stage_t

Values:

enumerator created_k

enumerator staged_k

enumerator commited_k

Private Functions

inline transaction_t(store_t &set) noexcept(false)

inline watch_t missing_watch() const noexcept

inline store_t &store_ref() noexcept

inline store_t const &store_ref() const noexcept

Private Members

friend store_t

store_t *store_ = {nullptr}

entry_set_t changes_ = {}

watches_array_t watches_ = {}

generation_t generation_ = {0}

stage_t stage_ = {stage_t::created_k}

consistent_avl

namespace unum

namespace ucset

template<typename entry_at, typename comparator_at>
class avl_node_gt

#include <consistent_avl.hpp>

AVL-Trees are some of the simplest yet performant Binary Search Trees. This “node” class implements the primary logic, but doesn’t take part in memory management.

Never throws! Even if new node allocation had failed. Implements upper_bound for faster and lighter iterators.

Alternative would be - Binary Threaded Search Tree.

Implements sampling methods.

Template Parameters:

• entry_at – Type of entries to store in this tree.

• comparator_at – A comparator function object, that overload

  bool operator ()(entry_at, entry_at) const
  

Public Types

using entry_t = entry_at

using comparator_t = comparator_at

using height_t = std::int16_t

using node_t = avl_node_gt

Public Members

entry_t entry

node_t *left = nullptr

node_t *right = nullptr

height_t height = 0

Root has the biggest height in the tree. Zero is possible only in the uninitialized detached state. A non-NULL node would have height of one. Allows you to guess the upper bound of branch size, as 1 << height.

Public Static Functions

static inline height_t get_height(node_t *node) noexcept

static inline height_t get_balance(node_t *node) noexcept

template<typename callback_at>
static inline void for_each_top_down(node_t *node, callback_at &&callback) noexcept

template<typename callback_at>
static inline void for_each_bottom_up(node_t *node, callback_at &&callback) noexcept

template<typename callback_at>
static inline void for_each_left_right(node_t *node, callback_at &&callback) noexcept

static inline node_t *find_min(node_t *node) noexcept

static inline node_t *find_max(node_t *node) noexcept

template<typename comparable_at>
static inline node_t *find(node_t *node, comparable_at &&comparable) noexcept

Searches for equal entry in this subtree.

Parameters:

comparable – Any key comparable with stored entries.

Returns:

NULL if nothing was found.

template<typename comparable_at>
static inline node_t *lower_bound(node_t *node, comparable_at &&comparable) noexcept

Find the smallest entry, bigger than or equal to the provided one.

Parameters:

comparable – Any key comparable with stored entries.

Returns:

NULL if nothing was found.

template<typename comparable_at>
static inline node_t *upper_bound(node_t *node, comparable_at &&comparable) noexcept

Find the smallest entry, bigger than the provided one.

Is used for an atomic implementation of iterators. Alternatively one can:

store a stack for path, which is ~O(logN) space. store parents in nodes and have complex logic.

Parameters:

comparable – Any key comparable with stored entries.

Returns:

NULL if nothing was found.

template<typename comparable_a_at, typename comparable_b_at>
static inline node_t *lowest_common_ancestor(node_t *node, comparable_a_at &&a, comparable_b_at &&b) noexcept

Searches for the shortest node, that is ancestor of both provided keys.

Warning

Current recursive implementation is suboptimal.

Returns:

NULL if nothing was found.

template<typename lower_at, typename upper_at, typename callback_at>
static inline node_interval_t range(node_t *node, lower_at &&low, upper_at &&high, callback_at &&callback) noexcept

Complex method, that detects the left-most and right-most nodes containing keys in a provided intervals, as well as their lowest common ancestors.

Warning

Current recursive implementation is suboptimal.

template<typename comparable_at>
static inline node_interval_t equal_range(node_t *node, comparable_at &&comparable) noexcept

template<typename generator_at>
static inline node_t *sample(node_t *node, generator_at &&generator) noexcept

Random samples nodes.

Warning

Resulting distribution is inaccurate, as we only have the upper bound of the branch size.

Parameters:

generator – Any STL-compatible random number generator.

Returns:

NULL if nothing was found.

template<typename generator_at, typename lower_at, typename upper_at, typename predicate_at>
static inline node_t *sample_range(node_t *node, lower_at &&low, upper_at &&high, generator_at &&generator, predicate_at &&predicate) noexcept

Random samples nodes within a given range of keys.

Warning

Without additional stored metadata or dynamic memory, this algorithm performs two passes.

Parameters:

generator – Any STL-compatible random number generator.

Returns:

NULL if nothing was found.

static inline node_t *rotate_right(node_t *y) noexcept

static inline node_t *rotate_left(node_t *x) noexcept

template<typename comparable_at>
static inline node_t *rebalance_after_insert(node_t *node, comparable_at &&comparable) noexcept

template<typename comparable_at, typename callback_found_at, typename callback_make_at>
static inline find_or_make_result_t find_or_make(node_t *node, comparable_at &&comparable, callback_found_at &&callback_found, callback_make_at &&callback_make) noexcept

template<typename node_allocator_at>
static inline find_or_make_result_t insert(node_t *node, entry_t &&entry, node_allocator_at &&node_allocator) noexcept

template<typename node_allocator_at>
static inline find_or_make_result_t upsert(node_t *node, entry_t &&entry, node_allocator_at &&node_allocator) noexcept

static inline find_or_make_result_t insert(node_t *node, node_t *new_child) noexcept

static inline node_t *rebalance_after_extract(node_t *node) noexcept

static inline extract_result_t extract(node_t *node) noexcept

Pops the root replacing it with one of descendants, if present.

Parameters:

comparable – Any key comparable with stored entries.

template<typename comparable_at>
static inline extract_result_t extract(node_t *node, comparable_at &&comparable) noexcept

Searches for a matching ancestor and extracts it out.

Parameters:

comparable – Any key comparable with stored entries.

template<typename predicate_at, typename node_deallocator_at>
static inline remove_if_result_t remove_if(node_t *node, predicate_at &&predicate, node_deallocator_at &&node_deallocator) noexcept

struct extract_result_t

#include <consistent_avl.hpp>

Public Functions

inline node_t *release() noexcept

Public Members

node_t *root = nullptr

std::unique_ptr<node_t> extracted

struct find_or_make_result_t

#include <consistent_avl.hpp>

Public Functions

inline bool failed() const noexcept

Returns:

True if the allocation of the new node has failed.

Public Members

node_t *root = nullptr

node_t *match = nullptr

bool inserted = false

struct node_interval_t

#include <consistent_avl.hpp>

Public Members

node_t *lower_bound = nullptr

node_t *upper_bound = nullptr

node_t *lowest_common_ancestor = nullptr

struct remove_if_result_t

#include <consistent_avl.hpp>

Public Members

node_t *root = nullptr

std::size_t count = 0

template<typename entry_at, typename comparator_at, typename node_allocator_at = std::allocator<avl_node_gt<entry_at, comparator_at>>>
class avl_tree_gt

#include <consistent_avl.hpp>

Public Types

using node_t = avl_node_gt<entry_at, comparator_at>

using node_allocator_t = node_allocator_at

using comparator_t = comparator_at

using entry_t = entry_at

using avl_tree_t = avl_tree_gt

Public Functions

avl_tree_gt() noexcept = default

inline avl_tree_gt(avl_tree_gt &&other) noexcept

inline avl_tree_gt &operator=(avl_tree_gt &&other) noexcept

inline ~avl_tree_gt()

inline std::size_t size() const noexcept

inline std::size_t height() noexcept

inline node_t *root() const noexcept

inline node_t *end() const noexcept

inline node_allocator_t &allocator() noexcept

inline node_allocator_t const &allocator() const noexcept

inline std::size_t total_imbalance() const noexcept

template<typename comparable_at>
inline node_t *find(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline node_t *lower_bound(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline node_t *upper_bound(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline node_t const *find(comparable_at &&comparable) const noexcept

template<typename comparable_at>
inline node_t const *lower_bound(comparable_at &&comparable) const noexcept

template<typename comparable_at>
inline node_t const *upper_bound(comparable_at &&comparable) const noexcept

template<typename comparable_at>
inline upsert_result_t insert(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline upsert_result_t upsert(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline extract_result_t extract(comparable_at &&comparable) noexcept

template<typename comparable_at>
inline bool erase(comparable_at &&comparable) noexcept

inline void clear() noexcept

template<typename callback_at>
inline void for_each(callback_at &&callback) noexcept

inline void merge(avl_tree_t &other) noexcept

inline void merge(extract_result_t other) noexcept

Private Members

node_t *root_ = nullptr

std::size_t size_ = 0

node_allocator_t allocator_

struct extract_result_t

#include <consistent_avl.hpp>

Public Functions

inline ~extract_result_t() noexcept

extract_result_t(extract_result_t const&) = delete

extract_result_t &operator=(extract_result_t const&) = delete

inline explicit operator bool() const noexcept

inline node_t *release() noexcept

Public Members

avl_tree_gt *tree_ = nullptr

node_t *node_ptr_ = nullptr

struct upsert_result_t

#include <consistent_avl.hpp>

Public Functions

inline bool failed() const noexcept

Returns:

True if the allocation of the new node has failed.

inline upsert_result_t &operator=(entry_t &&entry) noexcept

Public Members

node_t *node = nullptr

bool inserted = false

template<typename element_at, typename comparator_at = std::less<element_at>, typename allocator_at = std::allocator<std::uint8_t>>
class consistent_avl_gt

#include <consistent_avl.hpp>

Transactional Concurrent In-Memory Container with Snapshots support.

Consistency

Writing one entry or a batch is logically different. Either all fail or all succeed. Thats why set and set_many are implemented separately. Transactions write only on submit, thus they don’t need set_many.

Consistency

Reading a batch of entries is same as reading one by one. The received items might not be consistent with each other. If such behaviour is needed - you must create snapshot.

with WATCH-ing missing values

If an entry was missing. Then:

1. WATCH-ed in a transaction.

2. added in the second transaction.

3. removed in the third transaction. The first transaction will succeed, if we try to commit it.

Public Types

using element_t = element_at

using comparator_t = comparator_at

using allocator_t = allocator_at

using versioning_t = element_versioning_gt<element_t, comparator_t>

using identifier_t = typename versioning_t::identifier_t

using generation_t = typename versioning_t::generation_t

using dated_identifier_t = typename versioning_t::dated_identifier_t

using watch_t = typename versioning_t::watch_t

using watched_identifier_t = typename versioning_t::watched_identifier_t

using entry_t = typename versioning_t::entry_t

using entry_comparator_t = typename versioning_t::entry_comparator_t

Public Functions

inline consistent_avl_gt() noexcept

inline consistent_avl_gt(consistent_avl_gt &&other) noexcept

inline consistent_avl_gt &operator=(consistent_avl_gt &&other) noexcept

inline std::size_t size() const noexcept

inline std::optional<transaction_t> transaction() noexcept

inline status_t upsert(element_t &&element) noexcept

template<typename elements_begin_at, typename elements_end_at = elements_begin_at>
inline status_t upsert(elements_begin_at begin, elements_end_at end) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t erase_range(lower_at &&lower, upper_at &&upper, callback_at &&callback = {}) noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename callback_at = no_op_t>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, callback_at &&callback) const noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename output_iterator_at>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, std::size_t &seen, std::size_t reservoir_capacity, output_iterator_at &&reservoir) const noexcept

inline status_t clear() noexcept

template<typename dont_instantiate_me_at>
inline void print(dont_instantiate_me_at &cout)

Public Static Functions

static inline std::optional<store_t> make(allocator_t &&allocator = {}) noexcept

Private Types

using entry_node_t = avl_node_gt<entry_t, entry_comparator_t>

using entry_allocator_t = typename allocator_t::template rebind<entry_node_t>::other

using entry_set_t = avl_tree_gt<entry_t, entry_comparator_t, entry_allocator_t>

using entry_iterator_t = entry_node_t*

using watches_allocator_t = typename allocator_t::template rebind<watched_identifier_t>::other

using watches_array_t = std::vector<watched_identifier_t, watches_allocator_t>

using watch_iterator_t = typename watches_array_t::iterator

using store_t = consistent_avl_gt

using extract_result_t = typename entry_set_t::extract_result_t

Private Functions

inline generation_t new_generation() noexcept

inline void unmask_and_compact(identifier_t const &id, generation_t generation_to_unmask) noexcept

Private Members

entry_set_t entries_

generation_t generation_ = {0}

std::size_t visible_count_ = {0}

Friends

friend class transaction_t

class transaction_t

#include <consistent_avl.hpp>

Public Functions

transaction_t(transaction_t&&) noexcept = default

transaction_t &operator=(transaction_t&&) noexcept = default

transaction_t(transaction_t const&) = delete

transaction_t &operator=(transaction_t const&) = delete

inline generation_t generation() const noexcept

inline status_t upsert(element_t &&element) noexcept

inline status_t erase(identifier_t const &id) noexcept

inline status_t reserve(std::size_t size) noexcept

inline status_t watch(identifier_t const &id) noexcept

inline status_t watch(entry_t const &entry) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

inline status_t stage() noexcept

inline status_t reset() noexcept

inline status_t rollback() noexcept

inline status_t commit() noexcept

Private Types

enum class stage_t

Values:

enumerator created_k

enumerator staged_k

enumerator commited_k

Private Functions

inline transaction_t(store_t &set) noexcept

inline watch_t missing_watch() const noexcept

inline store_t &store_ref() noexcept

inline store_t const &store_ref() const noexcept

Private Members

friend store_t

store_t *store_ = {nullptr}

entry_set_t changes_ = {}

watches_array_t watches_ = {}

generation_t generation_ = {0}

stage_t stage_ = {stage_t::created_k}

bool is_snapshot_ = {false}

versioning_avl

namespace unum

namespace ucset

locked

namespace unum

namespace ucset

template<typename collection_at, typename shared_mutex_at = std::shared_mutex>
class locked_gt

#include <locked.hpp>

Wraps and protects any “Consistent Set” under a shared mutex. The collection itself becomes thread-safe, but the transaction don’t! Detects dead-locks and reports operation_would_block_k.

Public Types

using locked_t = locked_gt

using unlocked_t = collection_at

using unlocked_transaction_t = typename unlocked_t::transaction_t

using shared_mutex_t = shared_mutex_at

using element_t = typename unlocked_t::element_t

using comparator_t = typename unlocked_t::comparator_t

using identifier_t = typename unlocked_t::identifier_t

using generation_t = typename unlocked_t::generation_t

Public Functions

inline locked_gt(locked_gt &&other) noexcept

inline std::size_t size() const noexcept

inline bool empty() const noexcept

inline std::optional<transaction_t> transaction() noexcept

inline status_t upsert(element_t &&element) noexcept

template<typename elements_begin_at, typename elements_end_at = elements_begin_at>
inline status_t upsert(elements_begin_at begin, elements_end_at end) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t erase_range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

inline status_t clear() noexcept

inline status_t reserve(std::size_t size) noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename callback_at = no_op_t>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, callback_at &&callback) const noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename output_iterator_at>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, std::size_t &seen, std::size_t reservoir_capacity, output_iterator_at &&reservoir) const noexcept

Public Static Functions

static inline std::optional<locked_gt> make() noexcept

Private Functions

inline locked_gt(unlocked_t &&unlocked) noexcept

inline locked_gt &operator=(locked_gt &&other) noexcept

Private Members

mutable shared_mutex_t mutex_

unlocked_t unlocked_

class transaction_t

#include <locked.hpp>

Public Functions

inline transaction_t(locked_gt &db, unlocked_transaction_t &&unlocked) noexcept

transaction_t(transaction_t&&) noexcept = default

transaction_t &operator=(transaction_t&&) noexcept = default

inline generation_t generation() const noexcept

inline status_t watch(identifier_t const &id) noexcept

inline status_t reserve(std::size_t size) noexcept

inline status_t upsert(element_t &&element) noexcept

inline status_t erase(identifier_t const &id) noexcept

inline status_t stage() noexcept

inline status_t reset() noexcept

inline status_t rollback() noexcept

inline status_t commit() noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

Private Members

locked_gt &store_

unlocked_transaction_t unlocked_

Friends

friend class locked_gt

partitioned

Functions

template<typename at, std::size_t count_ak, std::size_t... sequence_ak>
constexpr std::array<at, count_ak> move_to_array_impl(at (&a)[count_ak], std::index_sequence<sequence_ak...>) noexcept

template<typename at, std::size_t count_ak>
constexpr std::array<at, count_ak> move_to_array(at (&a)[count_ak]) noexcept

This is a slightly tweaked implementation of std::to_array coming in C++20. https://en.cppreference.com/w/cpp/container/array/to_array.

template<typename at, std::size_t count_ak, typename generator_at>
static std::optional<std::array<at, count_ak>> generate_array_safely(generator_at &&generator) noexcept

Takes a generator that produces bool-convertible and dereference-able objects like std::optional, and builds up fixed-size of array of such object, but only if all were successfully built. If at least one generator call fails, the entire resulting std::optional is returned to NULL state.

namespace unum

namespace ucset

Functions

template<typename at, std::size_t count_ak, std::size_t... sequence_ak>
constexpr std::array<at, count_ak> move_to_array_impl(at (&a)[count_ak], std::index_sequence<sequence_ak...>) noexcept

template<typename at, std::size_t count_ak>
constexpr std::array<at, count_ak> move_to_array(at (&a)[count_ak]) noexcept

This is a slightly tweaked implementation of std::to_array coming in C++20. https://en.cppreference.com/w/cpp/container/array/to_array.

template<typename at, std::size_t count_ak, typename generator_at>
static std::optional<std::array<at, count_ak>> generate_array_safely(generator_at &&generator) noexcept

Takes a generator that produces bool-convertible and dereference-able objects like std::optional, and builds up fixed-size of array of such object, but only if all were successfully built. If at least one generator call fails, the entire resulting std::optional is returned to NULL state.

template<typename collection_at, typename hash_at = std::hash<typename collection_at::identifier_t>, typename shared_mutex_at = std::shared_mutex, std::size_t parts_ak = 16>
class partitioned_gt

#include <partitioned.hpp>

Hashes inputs to route them into separate sets, which can be concurrent, or have a separate state-full allocator attached.

Template Parameters:

hash_at – Keys that compare equal must have the same hashes.

Public Types

using partitioned_t = partitioned_gt

using hash_t = hash_at

using part_t = collection_at

using part_transaction_t = typename part_t::transaction_t

using shared_mutex_t = shared_mutex_at

using shared_lock_t = std::shared_lock<shared_mutex_t>

using unique_lock_t = std::unique_lock<shared_mutex_t>

using mutexes_t = std::array<shared_mutex_t, parts_k>

using parts_t = std::array<part_t, parts_k>

using part_transactions_t = std::array<part_transaction_t, parts_k>

using element_t = typename part_t::element_t

using comparator_t = typename part_t::comparator_t

using identifier_t = typename part_t::identifier_t

using generation_t = typename part_t::generation_t

Public Functions

inline partitioned_gt(partitioned_gt &&other) noexcept

inline std::size_t size() const noexcept

inline std::optional<transaction_t> transaction() noexcept

inline status_t upsert(element_t &&element) noexcept

template<typename elements_begin_at, typename elements_end_at = elements_begin_at>
inline status_t upsert(elements_begin_at begin, elements_end_at end) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) const noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

template<typename lower_at = identifier_t, typename upper_at = identifier_t, typename callback_at = no_op_t>
inline status_t erase_range(lower_at &&lower, upper_at &&upper, callback_at &&callback) noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename callback_at = no_op_t>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, callback_at &&callback) const noexcept

template<typename lower_at, typename upper_at, typename generator_at, typename output_iterator_at>
inline status_t sample_range(lower_at &&lower, upper_at &&upper, generator_at &&generator, std::size_t &seen, std::size_t reservoir_capacity, output_iterator_at &&reservoir) const noexcept

inline status_t clear() noexcept

Public Static Functions

static inline std::optional<partitioned_gt> make() noexcept

Public Static Attributes

static constexpr std::size_t parts_k = parts_ak

Private Functions

inline partitioned_gt(parts_t &&unlocked) noexcept

inline partitioned_gt &operator=(partitioned_gt &&other) noexcept

inline generation_t new_generation() noexcept

Private Members

mutable mutexes_t mutexes_

parts_t parts_

std::atomic<generation_t> generation_

Private Static Functions

static inline std::size_t bucket(identifier_t const &id) noexcept

template<typename lock_at, typename mutexes_at>
static inline void lock_out_of_order(mutexes_at &mutexes) noexcept

template<typename lock_at, typename parts_at, typename mutexes_at, typename callable_at>
static inline status_t for_all(parts_at &parts, mutexes_at &mutexes, callable_at &&callable) noexcept

Walks around all the parts, trying to perform operations on them, until all the tasks are exhausted.

template<typename parts_at, typename mutexes_at, typename comparable_at, typename callback_found_at, typename callback_missing_at>
static inline status_t for_all_next_lookups(parts_at &parts, mutexes_at &mutexes, comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing) noexcept

static inline std::optional<parts_t> new_parts() noexcept

Friends

friend class transaction_t

class transaction_t

#include <partitioned.hpp>

Public Functions

inline transaction_t(partitioned_gt &db, part_transactions_t &&unlocked) noexcept

transaction_t(transaction_t&&) noexcept = default

transaction_t &operator=(transaction_t&&) noexcept = default

inline generation_t generation() const noexcept

inline status_t reset() noexcept

inline status_t rollback() noexcept

inline status_t stage() noexcept

inline status_t commit() noexcept

inline status_t watch(identifier_t const &id) noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t find(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

template<typename comparable_at = identifier_t, typename callback_found_at = no_op_t, typename callback_missing_at = no_op_t>
inline status_t upper_bound(comparable_at &&comparable, callback_found_at &&callback_found, callback_missing_at &&callback_missing = {}) const noexcept

inline status_t upsert(element_t &&element) noexcept

inline status_t erase(identifier_t const &id) noexcept

Private Functions

template<typename callable_at>
inline status_t for_parts(callable_at &&callable) noexcept

Private Members

partitioned_gt &store_

part_transactions_t parts_

generation_t generation_

Friends

friend class partitioned_gt

crazy

Typedefs

template<typename collection_at>
using stl_compatible_gt = crazy_gt<collection_at>

namespace unum

namespace ucset

Typedefs

template<typename collection_at>
using stl_compatible_gt = crazy_gt<collection_at>

template<typename collection_at>
class crazy_gt

#include <crazy.hpp>

status

Enums

enum errc_t

Values:

enumerator success_k

enumerator unknown_k

enumerator consistency_k

enumerator transaction_not_recoverable_k

enumerator sequence_number_overflow_k

enumerator out_of_memory_heap_k

enumerator out_of_memory_arena_k

enumerator out_of_memory_disk_k

enumerator invalid_argument_k

enumerator operation_in_progress_k

enumerator operation_not_permitted_k

enumerator operation_not_supported_k

enumerator operation_would_block_k

enumerator operation_canceled_k

enumerator connection_broken_k

enumerator connection_aborted_k

enumerator connection_already_in_progress_k

enumerator connection_refused_k

enumerator connection_reset_k

Functions

template<typename element_at>
copy_to_gt<element_at> copy_to(element_at &element) noexcept

namespace unum

namespace ucset

Enums

enum errc_t

Values:

enumerator success_k

enumerator unknown_k

enumerator consistency_k

enumerator transaction_not_recoverable_k

enumerator sequence_number_overflow_k

enumerator out_of_memory_heap_k

enumerator out_of_memory_arena_k

enumerator out_of_memory_disk_k

enumerator invalid_argument_k

enumerator operation_in_progress_k

enumerator operation_not_permitted_k

enumerator operation_not_supported_k

enumerator operation_would_block_k

enumerator operation_canceled_k

enumerator connection_broken_k

enumerator connection_aborted_k

enumerator connection_already_in_progress_k

enumerator connection_refused_k

enumerator connection_reset_k

Functions

template<typename element_at>
copy_to_gt<element_at> copy_to(element_at &element) noexcept

struct status_t

#include <status.hpp>

Wraps error-codes into bool-convertible conditions.

See also

errc_t.

Public Functions

inline constexpr operator bool() const noexcept

Public Members

errc_t errc = errc_t::success_k

struct no_op_t

#include <status.hpp>

Public Functions

inline constexpr void operator()() const noexcept

template<typename at>
inline constexpr void operator()(at&&) const noexcept

template<typename element_at>
struct copy_to_gt

#include <status.hpp>

Public Functions

template<typename at>
inline void operator()(at &&source) const noexcept

Public Members

element_at &target

template<typename element_at, typename comparator_at>
struct element_versioning_gt

#include <status.hpp>

Public Types

using element_t = element_at

using comparator_t = comparator_at

using identifier_t = typename comparator_t::value_type

using generation_t = std::int64_t

Public Static Functions

template<typename at>
static inline constexpr bool knows_generation()

struct dated_identifier_t

#include <status.hpp>

Public Members

identifier_t id

generation_t generation = {0}

struct entry_comparator_t

#include <status.hpp>

Public Types

using is_transparent = void

Public Functions

template<typename at>
inline decltype(auto) comparable(at const &object) const noexcept

template<typename first_at, typename second_at>
inline bool dated_compare(first_at const &a, second_at const &b) const noexcept

template<typename first_at, typename second_at>
inline bool native_compare(first_at const &a, second_at const &b) const noexcept

template<typename first_at, typename second_at>
inline bool less(first_at const &a, second_at const &b) const noexcept

template<typename first_at, typename second_at>
inline bool operator()(first_at const &a, second_at const &b) const noexcept

template<typename first_at, typename second_at>
inline bool same(first_at const &a, second_at const &b) const noexcept

struct entry_t

#include <status.hpp>

Public Functions

entry_t() = default

entry_t(entry_t&&) noexcept = default

entry_t &operator=(entry_t&&) noexcept = default

entry_t(entry_t const&) noexcept = delete

entry_t &operator=(entry_t const&) noexcept = delete

inline entry_t(element_t &&element) noexcept

inline operator element_t const&() const & noexcept

inline bool operator==(watch_t const &watch) const noexcept

inline bool operator!=(watch_t const &watch) const noexcept

Public Members

mutable element_t element

mutable generation_t generation = {0}

mutable bool deleted = {false}

mutable bool visible = {true}

struct watch_t

#include <status.hpp>

Public Functions

inline bool operator==(watch_t const &watch) const noexcept

inline bool operator!=(watch_t const &watch) const noexcept

Public Members

generation_t generation = {0}

bool deleted = {false}

struct watched_identifier_t

#include <status.hpp>

Public Members

identifier_t id

watch_t watch