jaulib v1.3.0
Jau Support Library (C++, Java, ..)
|
Implementation of a Copy-On-Write (CoW) using std::vector as the underlying storage, exposing lock-free read operations using SC-DRF atomic synchronization. More...
#include <cow_vector.hpp>
Public Types | |
typedef Alloc_type | allocator_type |
typedef cow_ro_iterator< storage_t, storage_ref_t, cow_container_t > | const_iterator |
typedef const value_type * | const_pointer |
typedef const value_type & | const_reference |
typedef cow_vector< value_type, allocator_type > | cow_container_t |
typedef std::make_signed< size_type >::type | difference_type |
typedef bool(* | equal_comparator) (const value_type &a, const value_type &b) |
Generic value_type equal comparator to be user defined for e.g. More... | |
typedef cow_rw_iterator< storage_t, storage_ref_t, cow_container_t > | iterator |
typedef value_type * | pointer |
typedef value_type & | reference |
typedef std::size_t | size_type |
typedef std::shared_ptr< storage_t > | storage_ref_t |
typedef std::vector< value_type, allocator_type > | storage_t |
typedef Value_type | value_type |
Public Member Functions | |
constexpr | cow_vector () noexcept |
constexpr | cow_vector (const allocator_type &a) noexcept |
constexpr_atomic | cow_vector (const cow_vector &x) |
constexpr | cow_vector (const storage_t &x) |
constexpr_atomic | cow_vector (cow_vector &&x) noexcept |
template<class InputIt > | |
constexpr | cow_vector (InputIt first, InputIt last, const allocator_type &alloc=allocator_type()) |
Creates a new instance, copying all elements from the given template input-iterator value_type range [first, last). More... | |
constexpr | cow_vector (size_type n, const allocator_type &a=allocator_type()) |
constexpr | cow_vector (size_type n, const value_type &value, const allocator_type &a=allocator_type()) |
constexpr | cow_vector (std::initializer_list< value_type > initlist, const allocator_type &alloc=allocator_type()) |
Create a new instance from an initializer list. More... | |
~cow_vector () noexcept=default | |
constexpr iterator | begin () |
See description in jau::cow_darray::begin() More... | |
constexpr_atomic size_type | capacity () const noexcept |
constexpr const_iterator | cbegin () const noexcept |
See description in jau::cow_darray::cbegin() More... | |
constexpr_atomic void | clear () noexcept |
Like std::vector::clear(), but ending with zero capacity. More... | |
constexpr_atomic storage_ref_t | copy_store () |
Returns a new shared_ptr copy of the underlying store, i.e. More... | |
template<typename... Args> | |
constexpr_atomic reference | emplace_back (Args &&... args) |
Like std::vector::emplace_back(), construct a new element in place at the end(). More... | |
constexpr_atomic bool | empty () const noexcept |
Like std::vector::empty(). More... | |
constexpr_atomic size_type | erase_matching (const value_type &x, const bool all_matching, equal_comparator comparator) |
Erase either the first matching element or all matching elements. More... | |
allocator_type | get_allocator () const noexcept |
constexpr std::recursive_mutex & | get_write_mutex () noexcept |
Returns this instances' recursive write mutex, allowing user to implement more complex mutable write operations. More... | |
constexpr size_type | max_size () const noexcept |
Returns std::numeric_limits<difference_type>::max() as the maximum array size. More... | |
cow_vector & | operator= (const cow_vector &x) |
Like std::vector::operator=(&), assignment. More... | |
constexpr_atomic cow_vector & | operator= (cow_vector &&x) |
Like std::vector::operator=(&&), move. More... | |
constexpr_atomic void | pop_back () noexcept |
Like std::vector::pop_back(). More... | |
constexpr_atomic void | push_back (const value_type &x) |
Like std::vector::push_back(), copy. More... | |
constexpr_atomic void | push_back (value_type &&x) |
Like std::vector::push_back(), move. More... | |
constexpr_atomic bool | push_back_unique (const value_type &x, equal_comparator comparator) |
Like std::vector::push_back(), but only if the newly added element does not yet exist. More... | |
void | reserve (size_type new_capacity) |
constexpr_atomic void | set_store (storage_ref_t &&new_store_ref) noexcept |
Special case facility allowing the user to replace the current store with the given value, potentially acquired via jau::cow_vector::copy_store() and mutated while holding the jau::cow_vector::get_write_mutex() lock. More... | |
constexpr_atomic size_type | size () const noexcept |
Like std::vector::size(). More... | |
constexpr_atomic storage_ref_t | snapshot () const noexcept |
Returns the current snapshot of the underlying shared std::vector<T> reference. More... | |
constexpr_atomic void | swap (cow_vector &x) noexcept |
Like std::vector::swap(). More... | |
std::string | toString () const noexcept |
Implementation of a Copy-On-Write (CoW) using std::vector as the underlying storage, exposing lock-free read operations using SC-DRF atomic synchronization.
This data structure is also supporting Concurrency.
This class shall be compliant with C++ named requirements for Container.
The vector's store is owned using a shared reference to the data structure, allowing its replacement on Copy-On-Write (CoW).
Writing to the store utilizes a mutex lock to avoid data races on the instances' write operations only, leaving read operations lock-free.
Write operations replace the store reference with a new instance using jau::sc_atomic_critical to synchronize with read operations.
Reading from the store is lock-free and accesses the store reference using jau::sc_atomic_critical to synchronizing with write operations.
Immutable storage const_iterators are supported via jau::cow_ro_iterator, which are constructed lock-free.
jau::cow_ro_iterator hold a snapshot retrieved via jau::cow_vector::snapshot() until its destruction.
Mutable storage iterators are supported via jau::cow_rw_iterator, which holds a copy of this CoW storage and locks its write mutex until jau::cow_rw_iterator::write_back() or its destruction.
After completing all mutable operations but before this iterator's destruction, the user might want to write back this iterators' storage to this CoW using jau::cow_rw_iterator::write_back().
Index operation via ::operator[](size_type) or ::at(size_type) are not supported, since they would be only valid if value_type itself is a std::shared_ptr and hence prohibit the destruction of the object if mutating the storage, e.g. via jau::cow_vector::push_back().
Custom mutable write operations are also supported via jau::cow_vector::get_write_mutex(), jau::cow_vector::copy_store() and jau::cow_vector::set_store().
See example in jau::cow_vector::set_store()
See also:
Definition at line 107 of file cow_vector.hpp.
typedef Value_type jau::cow_vector< Value_type, Alloc_type >::value_type |
Definition at line 112 of file cow_vector.hpp.
typedef value_type* jau::cow_vector< Value_type, Alloc_type >::pointer |
Definition at line 113 of file cow_vector.hpp.
typedef const value_type* jau::cow_vector< Value_type, Alloc_type >::const_pointer |
Definition at line 114 of file cow_vector.hpp.
typedef value_type& jau::cow_vector< Value_type, Alloc_type >::reference |
Definition at line 115 of file cow_vector.hpp.
typedef const value_type& jau::cow_vector< Value_type, Alloc_type >::const_reference |
Definition at line 116 of file cow_vector.hpp.
typedef std::size_t jau::cow_vector< Value_type, Alloc_type >::size_type |
Definition at line 117 of file cow_vector.hpp.
typedef std::make_signed<size_type>::type jau::cow_vector< Value_type, Alloc_type >::difference_type |
Definition at line 118 of file cow_vector.hpp.
typedef Alloc_type jau::cow_vector< Value_type, Alloc_type >::allocator_type |
Definition at line 119 of file cow_vector.hpp.
typedef std::vector<value_type, allocator_type> jau::cow_vector< Value_type, Alloc_type >::storage_t |
Definition at line 121 of file cow_vector.hpp.
typedef std::shared_ptr<storage_t> jau::cow_vector< Value_type, Alloc_type >::storage_ref_t |
Definition at line 122 of file cow_vector.hpp.
typedef cow_vector<value_type, allocator_type> jau::cow_vector< Value_type, Alloc_type >::cow_container_t |
Definition at line 124 of file cow_vector.hpp.
typedef cow_ro_iterator<storage_t, storage_ref_t, cow_container_t> jau::cow_vector< Value_type, Alloc_type >::const_iterator |
Definition at line 130 of file cow_vector.hpp.
typedef cow_rw_iterator<storage_t, storage_ref_t, cow_container_t> jau::cow_vector< Value_type, Alloc_type >::iterator |
Definition at line 136 of file cow_vector.hpp.
typedef bool(* jau::cow_vector< Value_type, Alloc_type >::equal_comparator) (const value_type &a, const value_type &b) |
Generic value_type equal comparator to be user defined for e.g.
jau::cow_vector::push_back_unique().
a | one element of the equality test. |
b | the other element of the equality test. |
Definition at line 550 of file cow_vector.hpp.
|
inlineconstexprnoexcept |
Definition at line 148 of file cow_vector.hpp.
|
inlineexplicitconstexprnoexcept |
Definition at line 151 of file cow_vector.hpp.
|
inlineexplicitconstexpr |
Definition at line 154 of file cow_vector.hpp.
|
inlineconstexpr |
Definition at line 157 of file cow_vector.hpp.
|
inlineexplicitconstexpr |
Definition at line 160 of file cow_vector.hpp.
|
inline |
Definition at line 164 of file cow_vector.hpp.
|
inlinenoexcept |
Definition at line 196 of file cow_vector.hpp.
|
inlineconstexpr |
Creates a new instance, copying all elements from the given template input-iterator value_type range [first, last).
Size will equal the range [first, last), i.e. size_type(last-first)
.
InputIt | template input-iterator custom type |
first | template input-iterator to first element of value_type range [first, last) |
last | template input-iterator to last element of value_type range [first, last) |
alloc | custom allocator_type instance |
Definition at line 249 of file cow_vector.hpp.
|
inlineconstexpr |
Create a new instance from an initializer list.
initlist | initializer_list. |
alloc | allocator |
Definition at line 259 of file cow_vector.hpp.
|
defaultnoexcept |
|
inline |
Like std::vector::operator=(&), assignment.
This write operation uses a mutex lock and is blocking this instances' write operations only.
Definition at line 180 of file cow_vector.hpp.
|
inline |
Like std::vector::operator=(&&), move.
This write operation uses a mutex lock and is blocking both cow_vector instance's write operations.
Definition at line 219 of file cow_vector.hpp.
|
inlineconstexprnoexcept |
Returns std::numeric_limits<difference_type>::max()
as the maximum array size.
We rely on the signed difference_type
for pointer arithmetic, deducing ranges from iterator.
Definition at line 272 of file cow_vector.hpp.
|
inlineconstexprnoexcept |
Returns this instances' recursive write mutex, allowing user to implement more complex mutable write operations.
See example in jau::cow_vector::set_store()
Definition at line 287 of file cow_vector.hpp.
|
inline |
Returns a new shared_ptr copy of the underlying store, i.e.
using a new copy-constructed vectore.
See example in jau::cow_vector::set_store()
This special operation uses a mutex lock and is blocking this instances' write operations only.
Definition at line 303 of file cow_vector.hpp.
|
inlinenoexcept |
Special case facility allowing the user to replace the current store with the given value, potentially acquired via jau::cow_vector::copy_store() and mutated while holding the jau::cow_vector::get_write_mutex() lock.
This is a move operation, i.e. the given new_store_ref is invalid on the caller side after this operation.
User shall pass the store via std::move()
cow_vector<std::shared_ptr<Thing>> list; ... { std::lock_guard<std::recursive_mutex> lock(list.get_write_mutex()); std::shared_ptr<std::vector<std::shared_ptr<Thing>>> snapshot = list.copy_store(); ... some fancy mutation ... list.set_store(std::move(snapshot)); }
new_store_ref | the user store to be moved here, replacing the current store. |
Definition at line 336 of file cow_vector.hpp.
|
inlinenoexcept |
Returns the current snapshot of the underlying shared std::vector<T> reference.
Note that this snapshot will be outdated by the next (concurrent) write operation.
The returned referenced vector is still valid and not mutated, but does not represent the current content of this cow_vector instance.
This read operation is lock-free.
Definition at line 355 of file cow_vector.hpp.
|
inlineconstexprnoexcept |
See description in jau::cow_darray::cbegin()
Definition at line 367 of file cow_vector.hpp.
|
inlineconstexpr |
See description in jau::cow_darray::begin()
Definition at line 376 of file cow_vector.hpp.
|
inlinenoexcept |
Definition at line 382 of file cow_vector.hpp.
|
inlinenoexcept |
Definition at line 388 of file cow_vector.hpp.
|
inlinenoexcept |
Like std::vector::empty().
This read operation is lock-free.
Definition at line 400 of file cow_vector.hpp.
|
inlinenoexcept |
Like std::vector::size().
This read operation is lock-free.
Definition at line 412 of file cow_vector.hpp.
|
inline |
Definition at line 419 of file cow_vector.hpp.
|
inlinenoexcept |
Like std::vector::clear(), but ending with zero capacity.
This write operation uses a mutex lock and is blocking this instances' write operations.
Definition at line 437 of file cow_vector.hpp.
|
inlinenoexcept |
Like std::vector::swap().
This write operation uses a mutex lock and is blocking both cow_vector instance's write operations.
Definition at line 453 of file cow_vector.hpp.
|
inlinenoexcept |
Like std::vector::pop_back().
This write operation uses a mutex lock and is blocking this instances' write operations only.
Definition at line 473 of file cow_vector.hpp.
|
inline |
Like std::vector::push_back(), copy.
This write operation uses a mutex lock and is blocking this instances' write operations only.
x | the value to be added at the tail. |
Definition at line 494 of file cow_vector.hpp.
|
inline |
Like std::vector::push_back(), move.
This write operation uses a mutex lock and is blocking this instances' write operations only.
Definition at line 511 of file cow_vector.hpp.
|
inline |
Like std::vector::emplace_back(), construct a new element in place at the end().
Constructs the element at the end() using placement new.
size will be increased by one.
args | arguments to forward to the constructor of the element |
Definition at line 533 of file cow_vector.hpp.
|
inline |
Like std::vector::push_back(), but only if the newly added element does not yet exist.
This write operation uses a mutex lock and is blocking this instances' write operations only.
Examples
static jau::cow_vector<Thing>::equal_comparator thingEqComparator = [](const Thing &a, const Thing &b) -> bool { return a == b; }; ... jau::cow_vector<Thing> list; bool added = list.push_back_unique(new_element, thingEqComparator); ... cow_vector<std::shared_ptr<Thing>> listOfRefs; bool added = listOfRefs.push_back_unique(new_element, [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; });
x | the value to be added at the tail, if not existing yet. |
comparator | the equal comparator to return true if both given elements are equal |
Definition at line 577 of file cow_vector.hpp.
|
inline |
Erase either the first matching element or all matching elements.
This write operation uses a mutex lock and is blocking this instances' write operations only.
Examples
cow_vector<Thing> list; int count = list.erase_matching(element, true, [](const Thing &a, const Thing &b) -> bool { return a == b; }); ... static jau::cow_vector<Thing>::equal_comparator thingRefEqComparator = [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; }; ... cow_vector<std::shared_ptr<Thing>> listOfRefs; int count = listOfRefs.erase_matching(element, false, thingRefEqComparator);
x | the value to be added at the tail, if not existing yet. |
all_matching | if true, erase all matching elements, otherwise only the first matching element. |
comparator | the equal comparator to return true if both given elements are equal |
Definition at line 615 of file cow_vector.hpp.
|
inlinenoexcept |