/* * Author: Sven Gothel * Copyright (c) 2020 Gothel Software e.K. * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #ifndef JAU_COW_DARRAY_HPP_ #define JAU_COW_DARRAY_HPP_ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace jau { /** \addtogroup DataStructs * * @{ */ /** * Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage, * exposing lock-free read operations using SC-DRF atomic synchronization. * * This data structure is also supporting \ref Concurrency. * * This class shall be compliant with C++ named requirements for Container. * * The 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 holds a snapshot retrieved via jau::cow_darray::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(). * * Both, jau::cow_ro_iterator and jau::cow_rw_iterator are harmonized * to work with jau::darray::const_iterator and jau::darray::iterator * for all iterator based operations. * * Index operation via ::operator[](size_t) or ::at(size_t) 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_darray::push_back(). * * Custom mutable write operations are also supported via * jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() and jau::cow_darray::set_store().
* See example in jau::cow_darray::set_store() * * To allow data-race free operations using iterators from a potentially mutated CoW, * only one cow_darray::begin() const_iterator or iterator should be retrieved from this CoW * and all further operations shall use its * jau::cow_ro_iterator::size(), jau::cow_ro_iterator::begin() and jau::cow_ro_iterator::end() * - or its respective variant from jau::cow_rw_iterator. * * @anchor cow_darray_ntt_params * ### Non-Type Template Parameter controlling Value_type memory * See @ref darray_ntt_params. * #### use_memmove * `use_memmove` see @ref darray_memmove. * #### use_secmem * `use_secmem` see @ref darray_secmem. * * See also: * - Sequentially Consistent (SC) ordering or SC-DRF (data race free) * - std::memory_order * * @see jau::darray * @see @ref darray_ntt_params * @see jau::cow_ro_iterator * @see jau::for_each_fidelity * @see jau::cow_rw_iterator * @see jau::cow_rw_iterator::write_back() */ template , bool use_memmove = std::is_trivially_copyable_v || is_container_memmove_compliant_v, bool use_secmem = is_enforcing_secmem_v > class cow_darray { public: /** Default growth factor using the golden ratio 1.618 */ constexpr static const float DEFAULT_GROWTH_FACTOR = 1.618f; constexpr static const bool uses_memmove = use_memmove; constexpr static const bool uses_secmem = use_secmem; constexpr static const bool uses_realloc = use_memmove && std::is_base_of_v, Alloc_type>; // typedefs' for C++ named requirements: Container typedef Value_type value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef Size_type size_type; typedef typename std::make_signed::type difference_type; typedef Alloc_type allocator_type; typedef darray storage_t; typedef std::shared_ptr storage_ref_t; /** Used to determine whether this type is a darray or has a darray, see ::is_darray_type */ typedef bool darray_tag; typedef cow_darray cow_container_t; /** * Immutable, read-only const_iterator, lock-free, * holding the current shared store reference until destruction. *

* Using jau::cow_darray::snapshot() at construction. *

*

* This iterator is the preferred choice if no mutations are made to the elements state * itself, or all changes can be discarded after the iterator's destruction.
* This avoids the costly mutex lock and storage copy of jau::cow_rw_iterator.
* Also see jau::for_each_fidelity to iterate through in this good faith fashion. *

* @see jau::cow_ro_iterator * @see jau::cow_ro_iterator::size() * @see jau::cow_ro_iterator::begin() * @see jau::cow_ro_iterator::end() * @see jau::for_each_fidelity * @see jau::cow_rw_iterator */ typedef cow_ro_iterator const_iterator; /** * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. *

* Using jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() at construction
* and jau::cow_darray::set_store() at destruction. *

*

* Due to the costly nature of mutable CoW resource management, * consider using jau::cow_ro_iterator if elements won't get mutated * or any changes can be discarded. *

* @see jau::cow_rw_iterator * @see jau::cow_rw_iterator::size() * @see jau::cow_rw_iterator::begin() * @see jau::cow_rw_iterator::end() * @see jau::cow_ro_iterator */ typedef cow_rw_iterator iterator; // typedef std::reverse_iterator reverse_iterator; // typedef std::reverse_iterator const_reverse_iterator; private: static constexpr size_type DIFF_MAX = std::numeric_limits::max(); storage_ref_t store_ref; mutable sc_atomic_bool sync_atomic; mutable std::recursive_mutex mtx_write; public: // ctor w/o elements /** * Default constructor, giving almost zero capacity and zero memory footprint, but the shared empty jau::darray */ constexpr cow_darray() noexcept : store_ref(std::make_shared()), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor def: %s\n", get_info().c_str()); } /** * Creating an empty instance with initial capacity and other (default) properties. * @param capacity initial capacity of the new instance. * @param growth_factor given growth factor * @param alloc given allocator_type */ constexpr explicit cow_darray(size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared(capacity, growth_factor, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor 1: %s\n", get_info().c_str()); } // conversion ctor on storage_t elements constexpr cow_darray(const storage_t& x) : store_ref(std::make_shared(x)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor copy_0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor copy_0: x %s\n", x.get_info().c_str()); } constexpr explicit cow_darray(const storage_t& x, const float growth_factor, const allocator_type& alloc) : store_ref(std::make_shared(x, growth_factor, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor copy_1: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor copy_1: x %s\n", x.get_info().c_str()); } /** * Like std::vector::operator=(&), assignment, but copying from the underling jau::darray *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ cow_darray& operator=(const storage_t& x) { std::lock_guard lock(mtx_write); JAU_DARRAY_PRINTF("assignment copy_0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("assignment copy_0: x %s\n", x.get_info().c_str()); { sc_atomic_critical sync(sync_atomic); store_ref = std::move( std::make_shared( x ) ); } return *this; } constexpr cow_darray(storage_t && x) noexcept : store_ref(std::make_shared(std::move(x))), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor move_0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor move_0: x %s\n", x.get_info().c_str()); // Moved source array has been taken over. darray's move-operator has flushed source } constexpr explicit cow_darray(storage_t && x, const float growth_factor, const allocator_type& alloc) noexcept : store_ref(std::make_shared(std::move(x), growth_factor, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor move_1: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor move_1: x %s\n", x.get_info().c_str()); // Moved source array has been taken over. darray's move-operator has flushed source } /** * Like std::vector::operator=(&&), move, but taking the underling jau::darray *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ cow_darray& operator=(storage_t&& x) { std::lock_guard lock(mtx_write); JAU_DARRAY_PRINTF("assignment move_0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("assignment move_0: x %s\n", x.get_info().c_str()); { sc_atomic_critical sync(sync_atomic); store_ref = std::move( std::make_shared( std::move(x) ) ); // Moved source array has been taken over. darray's move-operator has flushed source } return *this; } // copy_ctor on cow_darray elements /** * Creates a new instance, copying all elements from the given array.
* Capacity and size will equal the given array, i.e. the result is a trimmed array. * @param x the given cow_darray, all elements will be copied into the new instance. */ constexpr_atomic cow_darray(const cow_darray& x) : sync_atomic(false) { storage_ref_t x_store_ref; { sc_atomic_critical sync_x( x.sync_atomic ); JAU_DARRAY_PRINTF("ctor copy.0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor copy.0: x %s\n", x.get_info().c_str()); x_store_ref = x.store_ref; } store_ref = std::make_shared( *x_store_ref ); } /** * Creates a new instance, copying all elements from the given array.
* Capacity and size will equal the given array, i.e. the result is a trimmed array. * @param x the given cow_darray, all elements will be copied into the new instance. * @param growth_factor custom growth factor * @param alloc custom allocator_type instance */ constexpr_atomic explicit cow_darray(const cow_darray& x, const float growth_factor, const allocator_type& alloc) : sync_atomic(false) { storage_ref_t x_store_ref; { sc_atomic_critical sync_x( x.sync_atomic ); JAU_DARRAY_PRINTF("ctor copy.1: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor copy.1: x %s\n", x.get_info().c_str()); x_store_ref = x.store_ref; } store_ref = std::make_shared( *x_store_ref, growth_factor, alloc ); } /** * Creates a new instance with custom initial storage capacity, copying all elements from the given array.
* Size will equal the given array. *

* Throws jau::IllegalArgumentException() if _capacity < x.size(). *

* @param x the given cow_darray, all elements will be copied into the new instance. * @param _capacity custom initial storage capacity * @param growth_factor custom growth factor * @param alloc custom allocator_type instance */ constexpr_atomic explicit cow_darray(const cow_darray& x, const size_type _capacity, const float growth_factor, const allocator_type& alloc) : sync_atomic(false) { storage_ref_t x_store_ref; { sc_atomic_critical sync_x( x.sync_atomic ); JAU_DARRAY_PRINTF("ctor copy.2: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor copy.2: x %s\n", x.get_info().c_str()); x_store_ref = x.store_ref; } store_ref = std::make_shared( *x_store_ref, _capacity, growth_factor, alloc ); } /** * Like std::vector::operator=(&), assignment *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ constexpr_atomic cow_darray& operator=(const cow_darray& x) { std::lock_guard lock(mtx_write); storage_ref_t x_store_ref; { sc_atomic_critical sync_x( x.sync_atomic ); JAU_DARRAY_PRINTF("assignment copy.0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("assignment copy.0: x %s\n", x.get_info().c_str()); x_store_ref = x.store_ref; } storage_ref_t new_store_ref = std::make_shared( *x_store_ref ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } return *this; } // move_ctor on cow_darray elements constexpr_atomic cow_darray(cow_darray && x) noexcept { // Strategy-1: Acquire lock, blocking // - If somebody else holds the lock, we wait. // - Then we own the lock // - Post move-op, the source object does not exist anymore std::unique_lock lock(x.mtx_write); // *this doesn't exist yet, not locking ourselves { JAU_DARRAY_PRINTF("ctor move.0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("ctor move.0: x %s\n", x.get_info().c_str()); store_ref = std::move(x.store_ref); // sync_atomic = std::move(x.sync_atomic); // issues w/ g++ 8.3 (move marked as deleted) // mtx_write will be a fresh one, but we hold the source's lock // Moved source array has been taken over, null its store_ref x.store_ref = nullptr; } } /** * Like std::vector::operator=(&&), move. *

* This write operation uses a mutex lock and is blocking both cow_vector instance's write operations. *

*/ constexpr_atomic cow_darray& operator=(cow_darray&& x) noexcept { // Strategy-2: Acquire locks of both, blocking // - If somebody else holds the lock, we wait. // - Then we own the lock for both instances // - Post move-op, the source object does not exist anymore std::unique_lock lock1(x.mtx_write, std::defer_lock); // utilize std::lock(r, w), allowing mixed order waiting on read/write ops std::unique_lock lock2( mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor std::lock(lock1, lock2); { sc_atomic_critical sync_x( x.sync_atomic ); sc_atomic_critical sync ( sync_atomic ); JAU_DARRAY_PRINTF("assignment move.0: this %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("assignment move.0: x %s\n", x.get_info().c_str()); store_ref = std::move(x.store_ref); // mtx_write and the atomic will be kept as is, but we hold the source's lock // Moved source array has been taken over, null its store_ref x.store_ref = nullptr; } return *this; } // ctor on const_iterator and foreign template iterator /** * Creates a new instance with custom initial storage capacity, * copying all elements from the given const_iterator value_type range [first, last).
* Size will equal the range [first, last), i.e. size_type(last-first). *

* Throws jau::IllegalArgumentException() if _capacity < size_type(last - first). *

* @param _capacity custom initial storage capacity * @param first const_iterator to first element of value_type range [first, last) * @param last const_iterator to last element of value_type range [first, last) * @param growth_factor custom growth factor * @param alloc custom allocator_type instance */ constexpr cow_darray(const size_type _capacity, const_iterator first, const_iterator last, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared(_capacity, first.underling(), last.underling(), growth_factor, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor iters0: %s\n", get_info().c_str()); } /** * Creates a new instance with custom initial storage capacity, * 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). *

* Throws jau::IllegalArgumentException() if _capacity < size_type(last - first). *

* @tparam InputIt template input-iterator custom type * @param _capacity custom initial storage capacity * @param first template input-iterator to first element of value_type range [first, last) * @param last template input-iterator to last element of value_type range [first, last) * @param growth_factor custom growth factor * @param alloc custom allocator_type instance */ template< class InputIt > constexpr explicit cow_darray(const size_type _capacity, InputIt first, InputIt last, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared(_capacity, first, last, growth_factor, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor iters1: %s\n", get_info().c_str()); } /** * 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). * @tparam InputIt template input-iterator custom type * @param first template input-iterator to first element of value_type range [first, last) * @param last template input-iterator to last element of value_type range [first, last) * @param alloc custom allocator_type instance */ template< class InputIt > constexpr cow_darray(InputIt first, InputIt last, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared(first, last, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor iters2: %s\n", get_info().c_str()); } /** * Using the `std::initializer_list` requires to *copy* the given value_type objects into this cow_darray. * * To utilize more efficient move semantics, see push_back_list() and jau::make_cow_darray(). * * @param initlist initializer_list. * @param alloc allocator * @see push_back_list() * @see jau::make_cow_darray() */ constexpr cow_darray(std::initializer_list initlist, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared(initlist, alloc)), sync_atomic(false) { JAU_DARRAY_PRINTF("ctor initlist: %s\n", get_info().c_str()); } ~cow_darray() noexcept { JAU_DARRAY_PRINTF("dtor: %s\n", get_info().c_str()); } /** * Returns std::numeric_limits::max() as the maximum array size. *

* We rely on the signed difference_type for pointer arithmetic, * deducing ranges from iterator. *

*/ constexpr size_type max_size() const noexcept { return DIFF_MAX; } // cow_vector features /** * Returns this instances' recursive write mutex, allowing user to * implement more complex mutable write operations. *

* See example in jau::cow_darray::set_store() *

* * @see jau::cow_darray::get_write_mutex() * @see jau::cow_darray::copy_store() * @see jau::cow_darray::set_store() */ constexpr std::recursive_mutex & get_write_mutex() noexcept { return mtx_write; } /** * Returns a new shared_ptr copy of the underlying store, * i.e. using a new copy-constructed vectore. *

* See example in jau::cow_darray::set_store() *

*

* This special operation uses a mutex lock and is blocking this instances' write operations only. *

* @see jau::cow_darray::get_write_mutex() * @see jau::cow_darray::copy_store() * @see jau::cow_darray::set_store() */ constexpr_atomic storage_ref_t copy_store() { std::lock_guard lock(mtx_write); JAU_DARRAY_PRINTF("copy_store: %s\n", get_info().c_str()); return std::make_shared( *store_ref ); } /** * Replace the current store with the given instance, * potentially acquired via jau::cow_darray::copy_store() * and mutated while holding the jau::cow_darray::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_darray> list;
             *     ...
             *     {
             *         std::lock_guard lock(list.get_write_mutex());
             *         std::shared_ptr>> snapshot = list.copy_store();
             *         ...
             *         some fancy mutation
             *         ...
             *         list.set_store(std::move(snapshot));
             *     }
             *
* Above functionality is covered by jau::cow_rw_iterator, see also jau::cow_rw_iterator::write_back() *

* @param new_store_ref the user store to be moved here, replacing the current store. * * @see jau::cow_darray::get_write_mutex() * @see jau::cow_darray::copy_store() * @see jau::cow_darray::set_store() * @see jau::cow_rw_iterator * @see jau::cow_rw_iterator::write_back() */ constexpr_atomic void set_store(storage_ref_t && new_store_ref) noexcept { std::lock_guard lock(mtx_write); sc_atomic_critical sync(sync_atomic); #if DEBUG_DARRAY JAU_DARRAY_PRINTF("set_store: dest %s\n", get_info().c_str()); JAU_DARRAY_PRINTF("set_store: src %s\n", new_store_ref->get_info().c_str()); jau::print_backtrace(true, 8); #endif store_ref = std::move( new_store_ref ); } /** * Returns the current snapshot of the underlying shared storage by 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_darray instance. *

*

* This read operation is lock-free. *

*/ constexpr_atomic storage_ref_t snapshot() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref; } // const_iterator, non mutable, read-only // Removed for clarity: "constexpr const_iterator begin() const noexcept" /** * Returns an jau::cow_ro_iterator to the first element of this CoW storage. *

* This method is the preferred choice if the use case allows, * read remarks in jau::cow_ro_iterator. *

*

* Use jau::cow_ro_iterator::end() on this returned const_iterator * to retrieve the end const_iterator in a data-race free fashion. *

* @return jau::cow_darray::const_iterator of type jau::cow_ro_iterator * @see jau::cow_ro_iterator * @see jau::cow_ro_iterator::size() * @see jau::cow_ro_iterator::begin() * @see jau::cow_ro_iterator::end() * @see jau::for_each_fidelity */ constexpr const_iterator cbegin() const noexcept { storage_ref_t sr = snapshot(); return const_iterator(sr, sr->cbegin()); } // iterator, mutable, read-write /** * Returns an jau::cow_rw_iterator to the first element of this CoW storage. *

* Acquiring this mutable iterator has considerable costs attached, * read remarks in jau::cow_rw_iterator. *

*

* Use jau::cow_rw_iterator::end() on this returned iterator * to retrieve the end iterator in a data-race free fashion. *

* @return jau::cow_darray::iterator of type jau::cow_rw_iterator * @see jau::cow_rw_iterator * @see jau::cow_rw_iterator::size() * @see jau::cow_rw_iterator::begin() * @see jau::cow_rw_iterator::end() */ constexpr iterator begin() { return iterator(*this); } // read access const allocator_type& get_allocator_ref() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->get_allocator_ref(); } allocator_type get_allocator() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->get_allocator(); } /** * Returns the growth factor */ constexpr_atomic float growth_factor() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->growth_factor(); } /** * Like std::vector::empty(). *

* This read operation is lock-free. *

* @return */ constexpr_atomic size_type capacity() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->capacity(); } /** * Like std::vector::empty(). *

* This read operation is lock-free. *

*/ constexpr_atomic bool empty() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->empty(); } /** * Like std::vector::size(). *

* This read operation is lock-free. *

*/ constexpr_atomic size_type size() const noexcept { sc_atomic_critical sync( sync_atomic ); return store_ref->size(); } // write access /** * Like std::vector::reserve(), increases this instance's capacity to new_capacity. *

* Only creates a new storage and invalidates iterators if new_capacity * is greater than the current jau::darray::capacity(). *

*

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ void reserve(size_type new_capacity) { std::lock_guard lock(mtx_write); if( new_capacity > store_ref->capacity() ) { storage_ref_t new_store_ref = std::make_shared( *store_ref, new_capacity, store_ref->growth_factor(), store_ref->get_allocator_ref() ); sc_atomic_critical sync( sync_atomic ); store_ref = std::move(new_store_ref); } } /** * Like std::vector::clear(), but ending with zero capacity. *

* This write operation uses a mutex lock and is blocking this instances' write operations. *

*/ constexpr_atomic void clear() noexcept { std::lock_guard lock(mtx_write); storage_ref_t new_store_ref = std::make_shared(); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } /** * Like std::vector::swap(). *

* This write operation uses a mutex lock and is blocking both cow_darray instance's write operations. *

*/ constexpr_atomic void swap(cow_darray& x) noexcept { std::unique_lock lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object std::unique_lock lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor std::lock(lock, lock_x); { sc_atomic_critical sync_x( x.sync_atomic ); sc_atomic_critical sync(sync_atomic); storage_ref_t x_store_ref = x.store_ref; x.store_ref = store_ref; store_ref = x_store_ref; } } /** * Like std::vector::pop_back(). *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ constexpr_atomic void pop_back() noexcept { std::lock_guard lock(mtx_write); if( !store_ref->empty() ) { storage_ref_t new_store_ref = std::make_shared( store_ref->capacity(), store_ref->cbegin(), store_ref->cend()-1, store_ref->growth_factor(), store_ref->get_allocator_ref() ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } } /** * Like std::vector::push_back(), copy *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

* @param x the value to be added at the tail. */ constexpr_atomic void push_back(const value_type& x) { std::lock_guard lock(mtx_write); if( store_ref->capacity_reached() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, store_ref->get_grown_capacity(), store_ref->growth_factor(), store_ref->get_allocator_ref() ); new_store_ref->push_back(x); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } else { // just append .. store_ref->push_back(x); } } /** * Like std::vector::push_back(), move *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

*/ constexpr_atomic void push_back(value_type&& x) { std::lock_guard lock(mtx_write); if( store_ref->capacity_reached() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, store_ref->get_grown_capacity(), store_ref->growth_factor(), store_ref->get_allocator_ref() ); new_store_ref->push_back( std::move(x) ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } else { // just append .. store_ref->push_back( std::move(x) ); } } /** * 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. *

* @param args arguments to forward to the constructor of the element */ template constexpr_atomic reference emplace_back(Args&&... args) { std::lock_guard lock(mtx_write); if( store_ref->capacity_reached() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, store_ref->get_grown_capacity(), store_ref->growth_factor(), store_ref->get_allocator_ref() ); reference res = new_store_ref->emplace_back( std::forward(args)... ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } return res; } else { // just append .. return store_ref->emplace_back( std::forward(args)... ); } } /** * Like std::vector::push_back(), but appends the whole value_type range [first, last). *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

* @tparam InputIt foreign input-iterator to range of value_type [first, last) * @param first first foreign input-iterator to range of value_type [first, last) * @param last last foreign input-iterator to range of value_type [first, last) */ template< class InputIt > constexpr_atomic void push_back( InputIt first, InputIt last ) { std::lock_guard lock(mtx_write); const size_type new_size_ = store_ref->size() + size_type(last - first); if( new_size_ > store_ref->capacity() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, new_size_, store_ref->growth_factor(), store_ref->get_allocator_ref() ); new_store_ref->push_back( first, last ); { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } else { // just append .. store_ref->push_back( first, last ); } } /** * Like push_back(), but for more multiple const r-value to copy. *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

* * @tparam Args * @param args r-value references to copy into this storage */ template constexpr_atomic void push_back_list(const Args&... args) { std::lock_guard lock(mtx_write); const size_type new_size_ = store_ref->size() + sizeof...(Args); if( new_size_ > store_ref->capacity() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, new_size_, store_ref->growth_factor(), store_ref->get_allocator_ref() ); // C++17 fold expression on above C++11 template pack args ( new_store_ref->push_back( args ), ... ); // @suppress("Syntax error") { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } else { // just append .. // C++17 fold expression on above C++11 template pack args ( store_ref->push_back( args ), ... ); // @suppress("Syntax error") } } /** * Like push_back(), but for more multiple r-value references to move. *

* This write operation uses a mutex lock and is blocking this instances' write operations only. *

* * @tparam Args * @param args r-value references to move into this storage * @see jau::make_cow_darray() */ template constexpr_atomic void push_back_list(Args&&... args) { std::lock_guard lock(mtx_write); const size_type new_size_ = store_ref->size() + sizeof...(Args); if( new_size_ > store_ref->capacity() ) { // grow and swap all refs storage_ref_t new_store_ref = std::make_shared( *store_ref, new_size_, store_ref->growth_factor(), store_ref->get_allocator_ref() ); // C++17 fold expression on above C++11 template pack args ( new_store_ref->push_back( std::move(args) ), ... ); // @suppress("Syntax error") { sc_atomic_critical sync(sync_atomic); store_ref = std::move(new_store_ref); } } else { // just append .. // C++17 fold expression on above C++11 template pack args ( store_ref->push_back( std::move(args) ), ... ); // @suppress("Syntax error") } } /** * Generic value_type equal comparator to be user defined for e.g. jau::cow_darray::push_back_unique(). * @param a one element of the equality test. * @param b the other element of the equality test. * @return true if both are equal */ typedef bool(*equal_comparator)(const value_type& a, const value_type& b); /** * 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_darray::equal_comparator thingEqComparator =
             *                  [](const Thing &a, const Thing &b) -> bool { return a == b; };
             *     ...
             *     jau::cow_darray list;
             *
             *     bool added = list.push_back_unique(new_element, thingEqComparator);
             *     ...
             *     cow_darray> listOfRefs;
             *     bool added = listOfRefs.push_back_unique(new_element,
             *                    [](const std::shared_ptr &a, const std::shared_ptr &b) -> bool { return *a == *b; });
             *
*

* @param x the value to be added at the tail, if not existing yet. * @param comparator the equal comparator to return true if both given elements are equal * @return true if the element has been uniquely added, otherwise false */ constexpr_atomic bool push_back_unique(const value_type& x, equal_comparator comparator) { std::lock_guard lock(mtx_write); for(auto it = store_ref->begin(); it != store_ref->end(); ) { if( comparator( *it, x ) ) { return false; // already included } else { ++it; } } push_back(x); return true; } /** * 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_darray list;
             *     int count = list.erase_matching(element, true,
             *                    [](const Thing &a, const Thing &b) -> bool { return a == b; });
             *     ...
             *     static jau::cow_darray::equal_comparator thingRefEqComparator =
             *                  [](const std::shared_ptr &a, const std::shared_ptr &b) -> bool { return *a == *b; };
             *     ...
             *     cow_darray> listOfRefs;
             *     int count = listOfRefs.erase_matching(element, false, thingRefEqComparator);
             *
*

* @param x the value to be added at the tail, if not existing yet. * @param all_matching if true, erase all matching elements, otherwise only the first matching element. * @param comparator the equal comparator to return true if both given elements are equal * @return number of erased elements */ constexpr_atomic size_type erase_matching(const value_type& x, const bool all_matching, equal_comparator comparator) { size_type count = 0; iterator it = begin(); // lock mutex and copy_store while( !it.is_end() ) { if( comparator( *it, x ) ) { it.erase(); ++count; if( !all_matching ) { break; } } else { ++it; } } if( 0 < count ) { it.write_back(); } return count; } std::string toString() const noexcept { std::string res("{ " + std::to_string( size() ) + ": "); int i=0; jau::for_each_const(*this, [&res, &i](const value_type & e) { if( 1 < ++i ) { res.append(", "); } res.append( jau::to_string(e) ); } ); res.append(" }"); return res; } std::string get_info() const noexcept { return ("cow_darray[this "+jau::to_hexstring(this)+ ", "+store_ref->get_info()+ "]"); } }; /** * Construct a cow_darray instance, initialized by move semantics from the variadic (template pack) argument list. * * std::initializer_list enforces to copy the created instances into the container, * since its iterator references to `const` value_type. * * This alternative template passes the r-value argument references to cow_darray::push_back_list(), * hence using `std::move` without copying semantics. * * All argument types must be of same type, i.e. std::is_same. * The deduced darray instance also uses same type as its Value_type. * * @tparam First the first argument type, must be same * @tparam Next all other argument types, must be same * @tparam * @param arg1 the first r-value * @param argsN the other r-values * @return the new `cow_darray` * @see cow_darray::push_back_list() * @see make_cow_darray() */ template ::value && ... ), bool> = true> std::enable_if_t< std::conjunction_v... >, bool> = true> constexpr cow_darray< First > make_cow_darray(First&& arg1, Next&&... argsN) { cow_darray< First > d(1 + sizeof...(Next)); // C++17 fold expression on above C++11 template pack arg1 and argsN // d.push_back_list( std::forward(arg1), ( std::forward(argsN), ... ) ); // @suppress("Syntax error") d.push_back_list( arg1, argsN... ); // @suppress("Syntax error") return d; } /** * Complement constructor for cow_darray instance, move semantics initializer for one argument. * @tparam First * @tparam Next * @param arg1 * @return * @see cow_darray::push_back() * @see cow_darray::push_back_list() * @see make_cow_darray() */ template constexpr cow_darray< First > make_cow_darray(First&& arg1) { cow_darray< First > d(1); d.push_back( std::forward(arg1) ); return d; } /**************************************************************************************** ****************************************************************************************/ template std::ostream & operator << (std::ostream &out, const cow_darray &c) { out << c.toString(); return out; } /**************************************************************************************** ****************************************************************************************/ template inline bool operator==(const cow_darray& rhs, const cow_darray& lhs) { if( &rhs == &lhs ) { return true; } typename cow_darray::const_iterator rhs_cend = rhs.cbegin(); rhs_cend += rhs.size(); return (rhs.size() == lhs.size() && std::equal(rhs.cbegin(), rhs_cend, lhs.cbegin())); } template inline bool operator!=(const cow_darray& rhs, const cow_darray& lhs) { return !(rhs==lhs); } template inline bool operator<(const cow_darray& rhs, const cow_darray& lhs) { typename cow_darray::const_iterator rhs_cend = rhs.cbegin(); rhs_cend += rhs.size(); typename cow_darray::const_iterator lhs_cend = lhs.cbegin(); lhs_cend += lhs.size(); return std::lexicographical_compare(rhs.cbegin(), rhs_cend, lhs.begin(), lhs_cend); } template inline bool operator>(const cow_darray& rhs, const cow_darray& lhs) { return lhs < rhs; } template inline bool operator<=(const cow_darray& rhs, const cow_darray& lhs) { return !(lhs < rhs); } template inline bool operator>=(const cow_darray& rhs, const cow_darray& lhs) { return !(rhs < lhs); } template inline void swap(cow_darray& rhs, cow_darray& lhs) noexcept { rhs.swap(lhs); } /**@}*/ } /* namespace jau */ /** \example test_cow_iterator_01.cpp * This C++ unit test of const jau::cow_ro_iterator and mutable jau::cow_rw_iterator * in conjunction with jau::cow_darray demonstrates the effect of CoW const and mutable CoW operations * besides testing them. */ /** \example test_cow_darray_perf01.cpp * This C++ unit test validates the performance and correctness of the jau::cow_darray implementation. */ /** \example test_cow_darray_01.cpp * This C++ unit test validates the jau::cow_darray implementation. */ #endif /* JAU_COW_DARRAY_HPP_ */