25#ifndef JAU_COW_DARRAY_HPP_
26#define JAU_COW_DARRAY_HPP_
35#include <condition_variable>
122 template <
typename Value_type,
typename Size_type = jau::n
size_t,
typename Alloc_type = jau::callocator<Value_type>,
123 bool use_memmove = std::is_trivially_copyable_v<Value_type> || is_container_memmove_compliant_v<Value_type>,
124 bool use_secmem = is_enforcing_secmem_v<Value_type>
134 constexpr static const bool uses_realloc = use_memmove && std::is_base_of_v<jau::callocator<Value_type>, Alloc_type>;
207 mutable std::recursive_mutex mtx_write;
216 : store_ref(
std::make_shared<
storage_t>()), sync_atomic(false) {
234 : store_ref(
std::make_shared<
storage_t>(x)), sync_atomic(false) {
252 std::lock_guard<std::recursive_mutex> lock(mtx_write);
257 store_ref = std::move( std::make_shared<storage_t>( x ) );
263 : store_ref(std::make_shared<storage_t>(std::move(x))), sync_atomic(
false) {
270 : store_ref(std::make_shared<storage_t>(std::move(x),
growth_factor, alloc)), sync_atomic(
false) {
283 std::lock_guard<std::recursive_mutex> lock(mtx_write);
288 store_ref = std::move( std::make_shared<storage_t>( std::move(x) ) );
303 : sync_atomic(false) {
309 x_store_ref = x.store_ref;
311 store_ref = std::make_shared<storage_t>( *x_store_ref );
323 : sync_atomic(false) {
329 x_store_ref = x.store_ref;
331 store_ref = std::make_shared<storage_t>( *x_store_ref,
growth_factor, alloc );
347 : sync_atomic(false) {
353 x_store_ref = x.store_ref;
355 store_ref = std::make_shared<storage_t>( *x_store_ref, _capacity,
growth_factor, alloc );
366 std::lock_guard<std::recursive_mutex> lock(mtx_write);
372 x_store_ref = x.store_ref;
374 storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref );
377 store_ref = std::move(new_store_ref);
390 std::unique_lock<std::recursive_mutex> lock(x.mtx_write);
394 store_ref = std::move(x.store_ref);
399 x.store_ref =
nullptr;
415 std::unique_lock<std::recursive_mutex> lock1(x.mtx_write, std::defer_lock);
416 std::unique_lock<std::recursive_mutex> lock2( mtx_write, std::defer_lock);
417 std::lock(lock1, lock2);
423 store_ref = std::move(x.store_ref);
427 x.store_ref =
nullptr;
449 : store_ref(
std::make_shared<
storage_t>(_capacity, first.underling(), last.underling(),
growth_factor, alloc)), sync_atomic(false)
468 template<
class InputIt >
485 template<
class InputIt >
487 : store_ref(
std::make_shared<
storage_t>(first, last, alloc)), sync_atomic(false)
503 : store_ref(
std::make_shared<
storage_t>(initlist, alloc)), sync_atomic(false)
552 std::lock_guard<std::recursive_mutex> lock(mtx_write);
554 return std::make_shared<storage_t>( *store_ref );
589 std::lock_guard<std::recursive_mutex> lock(mtx_write);
596 store_ref = std::move( new_store_ref );
668 return store_ref->get_allocator_ref();
673 return store_ref->get_allocator();
682 return store_ref->growth_factor();
695 return store_ref->capacity();
707 return store_ref->empty();
719 return store_ref->size();
735 std::lock_guard<std::recursive_mutex> lock(mtx_write);
736 if( new_capacity > store_ref->capacity() ) {
737 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, new_capacity,
738 store_ref->growth_factor(),
739 store_ref->get_allocator_ref() );
741 store_ref = std::move(new_store_ref);
753 std::lock_guard<std::recursive_mutex> lock(mtx_write);
757 store_ref = std::move(new_store_ref);
769 std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock);
770 std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock);
771 std::lock(lock, lock_x);
776 x.store_ref = store_ref;
777 store_ref = x_store_ref;
789 std::lock_guard<std::recursive_mutex> lock(mtx_write);
790 if( !store_ref->empty() ) {
791 storage_ref_t new_store_ref = std::make_shared<storage_t>( store_ref->capacity(),
794 store_ref->growth_factor(),
795 store_ref->get_allocator_ref() );
798 store_ref = std::move(new_store_ref);
812 std::lock_guard<std::recursive_mutex> lock(mtx_write);
813 if( store_ref->capacity_reached() ) {
815 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_grown_capacity(),
816 store_ref->growth_factor(),
817 store_ref->get_allocator_ref() );
818 new_store_ref->push_back(x);
821 store_ref = std::move(new_store_ref);
825 store_ref->push_back(x);
837 std::lock_guard<std::recursive_mutex> lock(mtx_write);
838 if( store_ref->capacity_reached() ) {
840 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_grown_capacity(),
841 store_ref->growth_factor(),
842 store_ref->get_allocator_ref() );
843 new_store_ref->push_back( std::move(x) );
846 store_ref = std::move(new_store_ref);
850 store_ref->push_back( std::move(x) );
864 template<
typename... Args>
867 std::lock_guard<std::recursive_mutex> lock(mtx_write);
868 if( store_ref->capacity_reached() ) {
870 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_grown_capacity(),
871 store_ref->growth_factor(),
872 store_ref->get_allocator_ref() );
873 reference res = new_store_ref->emplace_back( std::forward<Args>(args)... );
876 store_ref = std::move(new_store_ref);
881 return store_ref->emplace_back( std::forward<Args>(args)... );
894 template<
class InputIt >
897 std::lock_guard<std::recursive_mutex> lock(mtx_write);
900 if( new_size_ > store_ref->capacity() ) {
902 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, new_size_,
903 store_ref->growth_factor(),
904 store_ref->get_allocator_ref() );
905 new_store_ref->push_back( first, last );
908 store_ref = std::move(new_store_ref);
912 store_ref->push_back( first, last );
925 template <
typename... Args>
928 std::lock_guard<std::recursive_mutex> lock(mtx_write);
929 const size_type new_size_ = store_ref->size() +
sizeof...(Args);
931 if( new_size_ > store_ref->capacity() ) {
933 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, new_size_,
934 store_ref->growth_factor(),
935 store_ref->get_allocator_ref() );
937 ( new_store_ref->push_back( args ), ... );
940 store_ref = std::move(new_store_ref);
945 ( store_ref->push_back( args ), ... );
959 template <
typename... Args>
962 std::lock_guard<std::recursive_mutex> lock(mtx_write);
963 const size_type new_size_ = store_ref->size() +
sizeof...(Args);
965 if( new_size_ > store_ref->capacity() ) {
967 storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, new_size_,
968 store_ref->growth_factor(),
969 store_ref->get_allocator_ref() );
971 ( new_store_ref->push_back( std::move(args) ), ... );
974 store_ref = std::move(new_store_ref);
979 ( store_ref->push_back( std::move(args) ), ... );
1017 std::lock_guard<std::recursive_mutex> lock(mtx_write);
1018 for(
auto it = store_ref->begin(); it != store_ref->end(); ) {
1019 if( comparator( *it, x ) ) {
1059 if( comparator( *it, x ) ) {
1062 if( !all_matching ) {
1079 if( 1 < ++i ) { res.append(
", "); }
1088 ", "+store_ref->get_info()+
1114 template <
typename First,
typename... Next,
1116 std::enable_if_t< std::conjunction_v<std::is_same<First, Next>... >,
bool> =
true>
1136 template <
typename First,
typename... Next>
1140 d.
push_back( std::forward<First>(arg1) );
1147 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1156 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1158 if( &rhs == &lhs ) {
1162 rhs_cend += rhs.
size();
1165 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1170 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1173 rhs_cend += rhs.
size();
1175 lhs_cend += lhs.
size();
1176 return std::lexicographical_compare(rhs.
cbegin(), rhs_cend, lhs.
begin(), lhs_cend);
1179 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1181 {
return lhs < rhs; }
1183 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1185 {
return !(lhs < rhs); }
1187 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
1189 {
return !(rhs < lhs); }
1191 template<
typename Value_type,
typename Size_type,
typename Alloc_type>
Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage,...
static constexpr const bool uses_memmove
constexpr_atomic cow_darray & operator=(const cow_darray &x)
Like std::vector::operator=(&), assignment.
constexpr std::recursive_mutex & get_write_mutex() noexcept
Returns this instances' recursive write mutex, allowing user to implement more complex mutable write ...
constexpr_atomic storage_ref_t copy_store()
Returns a new shared_ptr copy of the underlying store, i.e.
constexpr_atomic void push_back(value_type &&x)
Like std::vector::push_back(), move.
constexpr_atomic void push_back(const value_type &x)
Like std::vector::push_back(), copy.
constexpr_atomic void clear() noexcept
Like std::vector::clear(), but ending with zero capacity.
constexpr const_iterator cbegin() const noexcept
Returns an jau::cow_ro_iterator to the first element of this CoW storage.
bool(* equal_comparator)(const value_type &a, const value_type &b)
Generic value_type equal comparator to be user defined for e.g.
constexpr_atomic size_type size() const noexcept
Like std::vector::size().
static constexpr const float DEFAULT_GROWTH_FACTOR
Default growth factor using the golden ratio 1.618.
constexpr cow_darray(size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type &alloc=allocator_type())
Creating an empty instance with initial capacity and other (default) properties.
std::string get_info() const noexcept
constexpr_atomic cow_darray(const cow_darray &x, const float growth_factor, const allocator_type &alloc)
Creates a new instance, copying all elements from the given array.
constexpr cow_darray(const storage_t &x, const float growth_factor, const allocator_type &alloc)
constexpr_atomic void swap(cow_darray &x) noexcept
Like std::vector::swap().
constexpr cow_darray(std::initializer_list< value_type > initlist, const allocator_type &alloc=allocator_type())
Using the std::initializer_list requires to copy the given value_type objects into this cow_darray.
constexpr_atomic cow_darray & operator=(cow_darray &&x) noexcept
Like std::vector::operator=(&&), move.
constexpr_atomic reference emplace_back(Args &&... args)
Like std::vector::emplace_back(), construct a new element in place at the end().
std::make_signed< size_type >::type difference_type
cow_darray & operator=(storage_t &&x)
Like std::vector::operator=(&&), move, but taking the underling jau::darray.
constexpr size_type max_size() const noexcept
Returns std::numeric_limits<difference_type>::max() as the maximum array size.
const value_type & const_reference
constexpr cow_darray(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 ...
bool darray_tag
Used to determine whether this type is a darray or has a darray, see ::is_darray_type<T>
static constexpr const bool uses_secmem
const allocator_type & get_allocator_ref() const noexcept
cow_ro_iterator< storage_t, storage_ref_t, cow_container_t > const_iterator
Immutable, read-only const_iterator, lock-free, holding the current shared store reference until dest...
constexpr cow_darray(storage_t &&x) noexcept
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())
Creates a new instance with custom initial storage capacity, copying all elements from the given cons...
constexpr_atomic void push_back_list(Args &&... args)
Like push_back(), but for more multiple r-value references to move.
cow_darray< value_type, size_type, allocator_type, use_memmove, use_secmem > cow_container_t
constexpr cow_darray() noexcept
Default constructor, giving almost zero capacity and zero memory footprint, but the shared empty jau:...
static constexpr const bool uses_realloc
constexpr_atomic float growth_factor() const noexcept
Returns the growth factor.
std::shared_ptr< storage_t > storage_ref_t
constexpr cow_darray(const size_type _capacity, InputIt first, InputIt last, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type &alloc=allocator_type())
Creates a new instance with custom initial storage capacity, copying all elements from the given temp...
constexpr_atomic void push_back(InputIt first, InputIt last)
Like std::vector::push_back(), but appends the whole value_type range [first, last).
allocator_type get_allocator() const noexcept
constexpr_atomic void push_back_list(const Args &... args)
Like push_back(), but for more multiple const r-value to copy.
void reserve(size_type new_capacity)
Like std::vector::reserve(), increases this instance's capacity to new_capacity.
darray< value_type, size_type, allocator_type, use_memmove, use_secmem > storage_t
constexpr_atomic bool empty() const noexcept
Like std::vector::empty().
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.
cow_darray & operator=(const storage_t &x)
Like std::vector::operator=(&), assignment, but copying from the underling jau::darray.
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.
constexpr_atomic size_type capacity() const noexcept
Like std::vector::empty().
Alloc_type allocator_type
constexpr iterator begin()
Returns an jau::cow_rw_iterator to the first element of this CoW storage.
constexpr_atomic cow_darray(cow_darray &&x) noexcept
constexpr cow_darray(storage_t &&x, const float growth_factor, const allocator_type &alloc) noexcept
constexpr_atomic cow_darray(const cow_darray &x)
Creates a new instance, copying all elements from the given array.
cow_rw_iterator< storage_t, storage_ref_t, cow_container_t > iterator
Mutable, read-write iterator, holding the write-lock and a store copy until destruction.
constexpr_atomic void pop_back() noexcept
Like std::vector::pop_back().
constexpr_atomic storage_ref_t snapshot() const noexcept
Returns the current snapshot of the underlying shared storage by reference.
const value_type * const_pointer
constexpr_atomic cow_darray(const cow_darray &x, const size_type _capacity, const float growth_factor, const allocator_type &alloc)
Creates a new instance with custom initial storage capacity, copying all elements from the given arra...
std::string toString() const noexcept
constexpr cow_darray(const storage_t &x)
constexpr_atomic void set_store(storage_ref_t &&new_store_ref) noexcept
Replace the current store with the given instance, potentially acquired via jau::cow_darray::copy_sto...
Implementation of a Copy-On-Write (CoW) read-onlu iterator over immutable value_type storage.
Implementation of a Copy-On-Write (CoW) read-write iterator over mutable value_type storage.
constexpr bool is_end() const noexcept
Returns true, if this iterator points to end().
void write_back() noexcept
Replace the parent's current store with this iterators' instance, unlock the CoW parents' write lock ...
constexpr void erase()
Erases the element at the current position.
Implementation of a dynamic linear array storage, aka vector.
std::string get_info() const noexcept
This class provides a RAII-style Sequentially Consistent (SC) data race free (DRF) critical block.
#define JAU_DARRAY_PRINTF(...)
constexpr UnaryFunction for_each_const(T &data, UnaryFunction f, std::enable_if_t< is_cow_type< T >::value, bool >=true) noexcept
std::string to_string(const endian_t v) noexcept
Return std::string representation of the given endian.
std::string to_string(const alphabet &v) noexcept
#define constexpr_atomic
Used when designed to declare a function constexpr, but prohibited by its specific implementation.
std::ostream & operator<<(std::ostream &out, const cow_darray< Value_type, Size_type, Alloc_type > &c)
constexpr cow_darray< First > make_cow_darray(First &&arg1, Next &&... argsN)
Construct a cow_darray<T> instance, initialized by move semantics from the variadic (template pack) a...
bool operator>=(const cow_darray< Value_type, Size_type, Alloc_type > &rhs, const cow_darray< Value_type, Size_type, Alloc_type > &lhs)
bool operator>(const cow_darray< Value_type, Size_type, Alloc_type > &rhs, const cow_darray< Value_type, Size_type, Alloc_type > &lhs)
bool operator<(const cow_darray< Value_type, Size_type, Alloc_type > &rhs, const cow_darray< Value_type, Size_type, Alloc_type > &lhs)
void swap(cow_darray< Value_type, Size_type, Alloc_type > &rhs, cow_darray< Value_type, Size_type, Alloc_type > &lhs) noexcept
bool operator<=(const cow_darray< Value_type, Size_type, Alloc_type > &rhs, const cow_darray< Value_type, Size_type, Alloc_type > &lhs)
constexpr T max(const T x, const T y) noexcept
Returns the maximum of two integrals (w/ branching) in O(1)
std::string to_hexstring(value_type const &v) noexcept
Produce a lower-case hexadecimal string representation of the given pointer.
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
bool operator==(const callocator< T1 > &lhs, const callocator< T2 > &rhs) noexcept
void print_backtrace(const bool skip_anon_frames, const jau::snsize_t max_frames=-1, const jau::snsize_t skip_frames=2) noexcept
Prints the de-mangled backtrace string separated by newline excluding this function to stderr,...
bool operator!=(const callocator< T1 > &lhs, const callocator< T2 > &rhs) noexcept