Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
cow_darray.hpp
Go to the documentation of this file.
1/*
2 * Author: Sven Gothel <sgothel@jausoft.com>
3 * Copyright (c) 2020 Gothel Software e.K.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
20 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
21 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
22 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 */
24
25#ifndef JAU_COW_DARRAY_HPP_
26#define JAU_COW_DARRAY_HPP_
27
28#include <cstring>
29#include <string>
30#include <cstdint>
31#include <limits>
32#include <atomic>
33#include <memory>
34#include <mutex>
35#include <condition_variable>
36#include <algorithm>
37
38#include <jau/cpp_lang_util.hpp>
39#include <jau/debug.hpp>
40#include <jau/darray.hpp>
41#include <jau/basic_types.hpp>
43#include <jau/cow_iterator.hpp>
44#include <jau/callocator.hpp>
45
46namespace jau {
47
48 /** \addtogroup DataStructs
49 *
50 * @{
51 */
52
53 /**
54 * Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage,
55 * exposing <i>lock-free</i> read operations using SC-DRF atomic synchronization.
56 *
57 * This data structure is also supporting \ref Concurrency.
58 *
59 * This class shall be compliant with <i>C++ named requirements for Container</i>.
60 *
61 * The store is owned using a shared reference to the data structure,
62 * allowing its replacement on Copy-On-Write (CoW).
63 *
64 * Writing to the store utilizes a mutex lock to avoid data races
65 * on the instances' write operations only, leaving read operations <i>lock-free</i>.<br>
66 * Write operations replace the store reference with a new instance using
67 * jau::sc_atomic_critical to synchronize with read operations.
68 *
69 * Reading from the store is <i>lock-free</i> and accesses the store reference using
70 * jau::sc_atomic_critical to synchronizing with write operations.
71 *
72 * Immutable storage const_iterators are supported via jau::cow_ro_iterator,
73 * which are constructed <i>lock-free</i>.<br>
74 * jau::cow_ro_iterator holds a snapshot retrieved via jau::cow_darray::snapshot()
75 * until its destruction.
76 *
77 * Mutable storage iterators are supported via jau::cow_rw_iterator,
78 * which holds a copy of this CoW storage and locks its write mutex until
79 * jau::cow_rw_iterator::write_back() or its destruction.<br>
80 * After completing all mutable operations but before this iterator's destruction,
81 * the user might want to write back this iterators' storage to this CoW
82 * using jau::cow_rw_iterator::write_back().
83 *
84 * Both, jau::cow_ro_iterator and jau::cow_rw_iterator are harmonized
85 * to work with jau::darray::const_iterator and jau::darray::iterator
86 * for all iterator based operations.
87 *
88 * Index operation via ::operator[](size_t) or ::at(size_t) are not supported,
89 * since they would be only valid if value_type itself is a std::shared_ptr
90 * and hence prohibit the destruction of the object if mutating the storage,
91 * e.g. via jau::cow_darray::push_back().
92 *
93 * Custom mutable write operations are also supported via
94 * jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() and jau::cow_darray::set_store().<br>
95 * See example in jau::cow_darray::set_store()
96 *
97 * To allow data-race free operations using iterators from a potentially mutated CoW,
98 * only one cow_darray::begin() const_iterator or iterator should be retrieved from this CoW
99 * and all further operations shall use its
100 * jau::cow_ro_iterator::size(), jau::cow_ro_iterator::begin() and jau::cow_ro_iterator::end()
101 * - or its respective variant from jau::cow_rw_iterator.
102 *
103 * @anchor cow_darray_ntt_params
104 * ### Non-Type Template Parameter controlling Value_type memory
105 * See @ref darray_ntt_params.
106 * #### use_memmove
107 * `use_memmove` see @ref darray_memmove.
108 * #### use_secmem
109 * `use_secmem` see @ref darray_secmem.
110 *
111 * See also:
112 * - Sequentially Consistent (SC) ordering or SC-DRF (data race free) <https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering>
113 * - std::memory_order <https://en.cppreference.com/w/cpp/atomic/memory_order>
114 *
115 * @see jau::darray
116 * @see @ref darray_ntt_params
117 * @see jau::cow_ro_iterator
118 * @see jau::for_each_fidelity
119 * @see jau::cow_rw_iterator
120 * @see jau::cow_rw_iterator::write_back()
121 */
122 template <typename Value_type, typename Size_type = jau::nsize_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>
125 >
127 {
128 public:
129 /** Default growth factor using the golden ratio 1.618 */
130 constexpr static const float DEFAULT_GROWTH_FACTOR = 1.618f;
131
132 constexpr static const bool uses_memmove = use_memmove;
133 constexpr static const bool uses_secmem = use_secmem;
134 constexpr static const bool uses_realloc = use_memmove && std::is_base_of_v<jau::callocator<Value_type>, Alloc_type>;
135
136 // typedefs' for C++ named requirements: Container
137
140 typedef const value_type* const_pointer;
143 typedef Size_type size_type;
144 typedef typename std::make_signed<size_type>::type difference_type;
145 typedef Alloc_type allocator_type;
146
147 typedef darray<value_type, size_type,
149 use_memmove, use_secmem> storage_t;
150 typedef std::shared_ptr<storage_t> storage_ref_t;
151
152 /** Used to determine whether this type is a darray or has a darray, see ::is_darray_type<T> */
153 typedef bool darray_tag;
154
157 use_memmove, use_secmem> cow_container_t;
158
159 /**
160 * Immutable, read-only const_iterator, lock-free,
161 * holding the current shared store reference until destruction.
162 * <p>
163 * Using jau::cow_darray::snapshot() at construction.
164 * </p>
165 * <p>
166 * This iterator is the preferred choice if no mutations are made to the elements state
167 * itself, or all changes can be discarded after the iterator's destruction.<br>
168 * This avoids the costly mutex lock and storage copy of jau::cow_rw_iterator.<br>
169 * Also see jau::for_each_fidelity to iterate through in this good faith fashion.
170 * </p>
171 * @see jau::cow_ro_iterator
172 * @see jau::cow_ro_iterator::size()
173 * @see jau::cow_ro_iterator::begin()
174 * @see jau::cow_ro_iterator::end()
175 * @see jau::for_each_fidelity
176 * @see jau::cow_rw_iterator
177 */
179
180 /**
181 * Mutable, read-write iterator, holding the write-lock and a store copy until destruction.
182 * <p>
183 * Using jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() at construction<br>
184 * and jau::cow_darray::set_store() at destruction.
185 * </p>
186 * <p>
187 * Due to the costly nature of mutable CoW resource management,
188 * consider using jau::cow_ro_iterator if elements won't get mutated
189 * or any changes can be discarded.
190 * </p>
191 * @see jau::cow_rw_iterator
192 * @see jau::cow_rw_iterator::size()
193 * @see jau::cow_rw_iterator::begin()
194 * @see jau::cow_rw_iterator::end()
195 * @see jau::cow_ro_iterator
196 */
198
199 // typedef std::reverse_iterator<iterator> reverse_iterator;
200 // typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
201
202 private:
203 static constexpr size_type DIFF_MAX = std::numeric_limits<difference_type>::max();
204
205 storage_ref_t store_ref;
206 mutable sc_atomic_bool sync_atomic;
207 mutable std::recursive_mutex mtx_write;
208
209 public:
210 // ctor w/o elements
211
212 /**
213 * Default constructor, giving almost zero capacity and zero memory footprint, but the shared empty jau::darray
214 */
215 constexpr cow_darray() noexcept
216 : store_ref(std::make_shared<storage_t>()), sync_atomic(false) {
217 JAU_DARRAY_PRINTF("ctor def: %s\n", get_info().c_str());
218 }
219
220 /**
221 * Creating an empty instance with initial capacity and other (default) properties.
222 * @param capacity initial capacity of the new instance.
223 * @param growth_factor given growth factor
224 * @param alloc given allocator_type
225 */
227 : store_ref(std::make_shared<storage_t>(capacity, growth_factor, alloc)), sync_atomic(false) {
228 JAU_DARRAY_PRINTF("ctor 1: %s\n", get_info().c_str());
229 }
230
231 // conversion ctor on storage_t elements
232
233 constexpr cow_darray(const storage_t& x)
234 : store_ref(std::make_shared<storage_t>(x)), sync_atomic(false) {
235 JAU_DARRAY_PRINTF("ctor copy_0: this %s\n", get_info().c_str());
236 JAU_DARRAY_PRINTF("ctor copy_0: x %s\n", x.get_info().c_str());
237 }
238
239 constexpr explicit cow_darray(const storage_t& x, const float growth_factor, const allocator_type& alloc)
240 : store_ref(std::make_shared<storage_t>(x, growth_factor, alloc)), sync_atomic(false) {
241 JAU_DARRAY_PRINTF("ctor copy_1: this %s\n", get_info().c_str());
242 JAU_DARRAY_PRINTF("ctor copy_1: x %s\n", x.get_info().c_str());
243 }
244
245 /**
246 * Like std::vector::operator=(&), assignment, but copying from the underling jau::darray
247 * <p>
248 * This write operation uses a mutex lock and is blocking this instances' write operations only.
249 * </p>
250 */
252 std::lock_guard<std::recursive_mutex> lock(mtx_write);
253 JAU_DARRAY_PRINTF("assignment copy_0: this %s\n", get_info().c_str());
254 JAU_DARRAY_PRINTF("assignment copy_0: x %s\n", x.get_info().c_str());
255 {
256 sc_atomic_critical sync(sync_atomic);
257 store_ref = std::move( std::make_shared<storage_t>( x ) );
258 }
259 return *this;
260 }
261
262 constexpr cow_darray(storage_t && x) noexcept
263 : store_ref(std::make_shared<storage_t>(std::move(x))), sync_atomic(false) {
264 JAU_DARRAY_PRINTF("ctor move_0: this %s\n", get_info().c_str());
265 JAU_DARRAY_PRINTF("ctor move_0: x %s\n", x.get_info().c_str());
266 // Moved source array has been taken over. darray's move-operator has flushed source
267 }
268
269 constexpr explicit cow_darray(storage_t && x, const float growth_factor, const allocator_type& alloc) noexcept
270 : store_ref(std::make_shared<storage_t>(std::move(x), growth_factor, alloc)), sync_atomic(false) {
271 JAU_DARRAY_PRINTF("ctor move_1: this %s\n", get_info().c_str());
272 JAU_DARRAY_PRINTF("ctor move_1: x %s\n", x.get_info().c_str());
273 // Moved source array has been taken over. darray's move-operator has flushed source
274 }
275
276 /**
277 * Like std::vector::operator=(&&), move, but taking the underling jau::darray
278 * <p>
279 * This write operation uses a mutex lock and is blocking this instances' write operations only.
280 * </p>
281 */
283 std::lock_guard<std::recursive_mutex> lock(mtx_write);
284 JAU_DARRAY_PRINTF("assignment move_0: this %s\n", get_info().c_str());
285 JAU_DARRAY_PRINTF("assignment move_0: x %s\n", x.get_info().c_str());
286 {
287 sc_atomic_critical sync(sync_atomic);
288 store_ref = std::move( std::make_shared<storage_t>( std::move(x) ) );
289 // Moved source array has been taken over. darray's move-operator has flushed source
290 }
291 return *this;
292 }
293
294 // copy_ctor on cow_darray elements
295
296 /**
297 * Creates a new instance, copying all elements from the given array.<br>
298 * Capacity and size will equal the given array, i.e. the result is a trimmed array.
299 * @param x the given cow_darray, all elements will be copied into the new instance.
300 */
303 : sync_atomic(false) {
304 storage_ref_t x_store_ref;
305 {
306 sc_atomic_critical sync_x( x.sync_atomic );
307 JAU_DARRAY_PRINTF("ctor copy.0: this %s\n", get_info().c_str());
308 JAU_DARRAY_PRINTF("ctor copy.0: x %s\n", x.get_info().c_str());
309 x_store_ref = x.store_ref;
310 }
311 store_ref = std::make_shared<storage_t>( *x_store_ref );
312 }
313
314 /**
315 * Creates a new instance, copying all elements from the given array.<br>
316 * Capacity and size will equal the given array, i.e. the result is a trimmed array.
317 * @param x the given cow_darray, all elements will be copied into the new instance.
318 * @param growth_factor custom growth factor
319 * @param alloc custom allocator_type instance
320 */
322 explicit cow_darray(const cow_darray& x, const float growth_factor, const allocator_type& alloc)
323 : sync_atomic(false) {
324 storage_ref_t x_store_ref;
325 {
326 sc_atomic_critical sync_x( x.sync_atomic );
327 JAU_DARRAY_PRINTF("ctor copy.1: this %s\n", get_info().c_str());
328 JAU_DARRAY_PRINTF("ctor copy.1: x %s\n", x.get_info().c_str());
329 x_store_ref = x.store_ref;
330 }
331 store_ref = std::make_shared<storage_t>( *x_store_ref, growth_factor, alloc );
332 }
333
334 /**
335 * Creates a new instance with custom initial storage capacity, copying all elements from the given array.<br>
336 * Size will equal the given array.
337 * <p>
338 * Throws jau::IllegalArgumentException() if <code>_capacity < x.size()</code>.
339 * </p>
340 * @param x the given cow_darray, all elements will be copied into the new instance.
341 * @param _capacity custom initial storage capacity
342 * @param growth_factor custom growth factor
343 * @param alloc custom allocator_type instance
344 */
346 explicit cow_darray(const cow_darray& x, const size_type _capacity, const float growth_factor, const allocator_type& alloc)
347 : sync_atomic(false) {
348 storage_ref_t x_store_ref;
349 {
350 sc_atomic_critical sync_x( x.sync_atomic );
351 JAU_DARRAY_PRINTF("ctor copy.2: this %s\n", get_info().c_str());
352 JAU_DARRAY_PRINTF("ctor copy.2: x %s\n", x.get_info().c_str());
353 x_store_ref = x.store_ref;
354 }
355 store_ref = std::make_shared<storage_t>( *x_store_ref, _capacity, growth_factor, alloc );
356 }
357
358 /**
359 * Like std::vector::operator=(&), assignment
360 * <p>
361 * This write operation uses a mutex lock and is blocking this instances' write operations only.
362 * </p>
363 */
366 std::lock_guard<std::recursive_mutex> lock(mtx_write);
367 storage_ref_t x_store_ref;
368 {
369 sc_atomic_critical sync_x( x.sync_atomic );
370 JAU_DARRAY_PRINTF("assignment copy.0: this %s\n", get_info().c_str());
371 JAU_DARRAY_PRINTF("assignment copy.0: x %s\n", x.get_info().c_str());
372 x_store_ref = x.store_ref;
373 }
374 storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref );
375 {
376 sc_atomic_critical sync(sync_atomic);
377 store_ref = std::move(new_store_ref);
378 }
379 return *this;
380 }
381
382 // move_ctor on cow_darray elements
383
385 cow_darray(cow_darray && x) noexcept {
386 // Strategy-1: Acquire lock, blocking
387 // - If somebody else holds the lock, we wait.
388 // - Then we own the lock
389 // - Post move-op, the source object does not exist anymore
390 std::unique_lock<std::recursive_mutex> lock(x.mtx_write); // *this doesn't exist yet, not locking ourselves
391 {
392 JAU_DARRAY_PRINTF("ctor move.0: this %s\n", get_info().c_str());
393 JAU_DARRAY_PRINTF("ctor move.0: x %s\n", x.get_info().c_str());
394 store_ref = std::move(x.store_ref);
395 // sync_atomic = std::move(x.sync_atomic); // issues w/ g++ 8.3 (move marked as deleted)
396 // mtx_write will be a fresh one, but we hold the source's lock
397
398 // Moved source array has been taken over, null its store_ref
399 x.store_ref = nullptr;
400 }
401 }
402
403 /**
404 * Like std::vector::operator=(&&), move.
405 * <p>
406 * This write operation uses a mutex lock and is blocking both cow_vector instance's write operations.
407 * </p>
408 */
411 // Strategy-2: Acquire locks of both, blocking
412 // - If somebody else holds the lock, we wait.
413 // - Then we own the lock for both instances
414 // - Post move-op, the source object does not exist anymore
415 std::unique_lock<std::recursive_mutex> lock1(x.mtx_write, std::defer_lock); // utilize std::lock(r, w), allowing mixed order waiting on read/write ops
416 std::unique_lock<std::recursive_mutex> lock2( mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor
417 std::lock(lock1, lock2);
418 {
419 sc_atomic_critical sync_x( x.sync_atomic );
420 sc_atomic_critical sync ( sync_atomic );
421 JAU_DARRAY_PRINTF("assignment move.0: this %s\n", get_info().c_str());
422 JAU_DARRAY_PRINTF("assignment move.0: x %s\n", x.get_info().c_str());
423 store_ref = std::move(x.store_ref);
424 // mtx_write and the atomic will be kept as is, but we hold the source's lock
425
426 // Moved source array has been taken over, null its store_ref
427 x.store_ref = nullptr;
428 }
429 return *this;
430 }
431
432 // ctor on const_iterator and foreign template iterator
433
434 /**
435 * Creates a new instance with custom initial storage capacity,
436 * copying all elements from the given const_iterator value_type range [first, last).<br>
437 * Size will equal the range [first, last), i.e. <code>size_type(last-first)</code>.
438 * <p>
439 * Throws jau::IllegalArgumentException() if <code>_capacity < size_type(last - first)</code>.
440 * </p>
441 * @param _capacity custom initial storage capacity
442 * @param first const_iterator to first element of value_type range [first, last)
443 * @param last const_iterator to last element of value_type range [first, last)
444 * @param growth_factor custom growth factor
445 * @param alloc custom allocator_type instance
446 */
447 constexpr cow_darray(const size_type _capacity, const_iterator first, const_iterator last,
449 : store_ref(std::make_shared<storage_t>(_capacity, first.underling(), last.underling(), growth_factor, alloc)), sync_atomic(false)
450 {
451 JAU_DARRAY_PRINTF("ctor iters0: %s\n", get_info().c_str());
452 }
453
454 /**
455 * Creates a new instance with custom initial storage capacity,
456 * copying all elements from the given template input-iterator value_type range [first, last).<br>
457 * Size will equal the range [first, last), i.e. <code>size_type(last-first)</code>.
458 * <p>
459 * Throws jau::IllegalArgumentException() if <code>_capacity < size_type(last - first)</code>.
460 * </p>
461 * @tparam InputIt template input-iterator custom type
462 * @param _capacity custom initial storage capacity
463 * @param first template input-iterator to first element of value_type range [first, last)
464 * @param last template input-iterator to last element of value_type range [first, last)
465 * @param growth_factor custom growth factor
466 * @param alloc custom allocator_type instance
467 */
468 template< class InputIt >
469 constexpr explicit cow_darray(const size_type _capacity, InputIt first, InputIt last,
471 : store_ref(std::make_shared<storage_t>(_capacity, first, last, growth_factor, alloc)), sync_atomic(false)
472 {
473 JAU_DARRAY_PRINTF("ctor iters1: %s\n", get_info().c_str());
474 }
475
476 /**
477 * Creates a new instance,
478 * copying all elements from the given template input-iterator value_type range [first, last).<br>
479 * Size will equal the range [first, last), i.e. <code>size_type(last-first)</code>.
480 * @tparam InputIt template input-iterator custom type
481 * @param first template input-iterator to first element of value_type range [first, last)
482 * @param last template input-iterator to last element of value_type range [first, last)
483 * @param alloc custom allocator_type instance
484 */
485 template< class InputIt >
486 constexpr cow_darray(InputIt first, InputIt last, const allocator_type& alloc = allocator_type())
487 : store_ref(std::make_shared<storage_t>(first, last, alloc)), sync_atomic(false)
488 {
489 JAU_DARRAY_PRINTF("ctor iters2: %s\n", get_info().c_str());
490 }
491
492 /**
493 * Using the `std::initializer_list` requires to *copy* the given value_type objects into this cow_darray.
494 *
495 * To utilize more efficient move semantics, see push_back_list() and jau::make_cow_darray().
496 *
497 * @param initlist initializer_list.
498 * @param alloc allocator
499 * @see push_back_list()
500 * @see jau::make_cow_darray()
501 */
502 constexpr cow_darray(std::initializer_list<value_type> initlist, const allocator_type& alloc = allocator_type())
503 : store_ref(std::make_shared<storage_t>(initlist, alloc)), sync_atomic(false)
504 {
505 JAU_DARRAY_PRINTF("ctor initlist: %s\n", get_info().c_str());
506 }
507
508
509 ~cow_darray() noexcept {
510 JAU_DARRAY_PRINTF("dtor: %s\n", get_info().c_str());
511 }
512
513 /**
514 * Returns <code>std::numeric_limits<difference_type>::max()</code> as the maximum array size.
515 * <p>
516 * We rely on the signed <code>difference_type</code> for pointer arithmetic,
517 * deducing ranges from iterator.
518 * </p>
519 */
520 constexpr size_type max_size() const noexcept { return DIFF_MAX; }
521
522 // cow_vector features
523
524 /**
525 * Returns this instances' recursive write mutex, allowing user to
526 * implement more complex mutable write operations.
527 * <p>
528 * See example in jau::cow_darray::set_store()
529 * </p>
530 *
531 * @see jau::cow_darray::get_write_mutex()
532 * @see jau::cow_darray::copy_store()
533 * @see jau::cow_darray::set_store()
534 */
535 constexpr std::recursive_mutex & get_write_mutex() noexcept { return mtx_write; }
536
537 /**
538 * Returns a new shared_ptr copy of the underlying store,
539 * i.e. using a new copy-constructed vectore.
540 * <p>
541 * See example in jau::cow_darray::set_store()
542 * </p>
543 * <p>
544 * This special operation uses a mutex lock and is blocking this instances' write operations only.
545 * </p>
546 * @see jau::cow_darray::get_write_mutex()
547 * @see jau::cow_darray::copy_store()
548 * @see jau::cow_darray::set_store()
549 */
552 std::lock_guard<std::recursive_mutex> lock(mtx_write);
553 JAU_DARRAY_PRINTF("copy_store: %s\n", get_info().c_str());
554 return std::make_shared<storage_t>( *store_ref );
555 }
556
557 /**
558 * Replace the current store with the given instance,
559 * potentially acquired via jau::cow_darray::copy_store()
560 * and mutated while holding the jau::cow_darray::get_write_mutex() lock.
561 * <p>
562 * This is a move operation, i.e. the given new_store_ref is invalid on the caller side
563 * after this operation. <br>
564 * User shall pass the store via std::move()
565 * <pre>
566 * cow_darray<std::shared_ptr<Thing>> list;
567 * ...
568 * {
569 * std::lock_guard<std::recursive_mutex> lock(list.get_write_mutex());
570 * std::shared_ptr<std::vector<std::shared_ptr<Thing>>> snapshot = list.copy_store();
571 * ...
572 * some fancy mutation
573 * ...
574 * list.set_store(std::move(snapshot));
575 * }
576 * </pre>
577 * Above functionality is covered by jau::cow_rw_iterator, see also jau::cow_rw_iterator::write_back()
578 * </p>
579 * @param new_store_ref the user store to be moved here, replacing the current store.
580 *
581 * @see jau::cow_darray::get_write_mutex()
582 * @see jau::cow_darray::copy_store()
583 * @see jau::cow_darray::set_store()
584 * @see jau::cow_rw_iterator
585 * @see jau::cow_rw_iterator::write_back()
586 */
588 void set_store(storage_ref_t && new_store_ref) noexcept {
589 std::lock_guard<std::recursive_mutex> lock(mtx_write);
590 sc_atomic_critical sync(sync_atomic);
591#if DEBUG_DARRAY
592 JAU_DARRAY_PRINTF("set_store: dest %s\n", get_info().c_str());
593 JAU_DARRAY_PRINTF("set_store: src %s\n", new_store_ref->get_info().c_str());
594 jau::print_backtrace(true, 8);
595#endif
596 store_ref = std::move( new_store_ref );
597 }
598
599 /**
600 * Returns the current snapshot of the underlying shared storage by reference.
601 * <p>
602 * Note that this snapshot will be outdated by the next (concurrent) write operation.<br>
603 * The returned referenced vector is still valid and not mutated,
604 * but does not represent the current content of this cow_darray instance.
605 * </p>
606 * <p>
607 * This read operation is <i>lock-free</i>.
608 * </p>
609 */
611 storage_ref_t snapshot() const noexcept {
612 sc_atomic_critical sync( sync_atomic );
613 return store_ref;
614 }
615
616 // const_iterator, non mutable, read-only
617
618 // Removed for clarity: "constexpr const_iterator begin() const noexcept"
619
620 /**
621 * Returns an jau::cow_ro_iterator to the first element of this CoW storage.
622 * <p>
623 * This method is the preferred choice if the use case allows,
624 * read remarks in jau::cow_ro_iterator.
625 * </p>
626 * <p>
627 * Use jau::cow_ro_iterator::end() on this returned const_iterator
628 * to retrieve the end const_iterator in a data-race free fashion.
629 * </p>
630 * @return jau::cow_darray::const_iterator of type jau::cow_ro_iterator
631 * @see jau::cow_ro_iterator
632 * @see jau::cow_ro_iterator::size()
633 * @see jau::cow_ro_iterator::begin()
634 * @see jau::cow_ro_iterator::end()
635 * @see jau::for_each_fidelity
636 */
637 constexpr const_iterator cbegin() const noexcept {
638 storage_ref_t sr = snapshot();
639 return const_iterator(sr, sr->cbegin());
640 }
641
642 // iterator, mutable, read-write
643
644 /**
645 * Returns an jau::cow_rw_iterator to the first element of this CoW storage.
646 * <p>
647 * Acquiring this mutable iterator has considerable costs attached,
648 * read remarks in jau::cow_rw_iterator.
649 * </p>
650 * <p>
651 * Use jau::cow_rw_iterator::end() on this returned iterator
652 * to retrieve the end iterator in a data-race free fashion.
653 * </p>
654 * @return jau::cow_darray::iterator of type jau::cow_rw_iterator
655 * @see jau::cow_rw_iterator
656 * @see jau::cow_rw_iterator::size()
657 * @see jau::cow_rw_iterator::begin()
658 * @see jau::cow_rw_iterator::end()
659 */
660 constexpr iterator begin() {
661 return iterator(*this);
662 }
663
664 // read access
665
666 const allocator_type& get_allocator_ref() const noexcept {
667 sc_atomic_critical sync( sync_atomic );
668 return store_ref->get_allocator_ref();
669 }
670
671 allocator_type get_allocator() const noexcept {
672 sc_atomic_critical sync( sync_atomic );
673 return store_ref->get_allocator();
674 }
675
676 /**
677 * Returns the growth factor
678 */
680 float growth_factor() const noexcept {
681 sc_atomic_critical sync( sync_atomic );
682 return store_ref->growth_factor();
683 }
684
685 /**
686 * Like std::vector::empty().
687 * <p>
688 * This read operation is <i>lock-free</i>.
689 * </p>
690 * @return
691 */
693 size_type capacity() const noexcept {
694 sc_atomic_critical sync( sync_atomic );
695 return store_ref->capacity();
696 }
697
698 /**
699 * Like std::vector::empty().
700 * <p>
701 * This read operation is <i>lock-free</i>.
702 * </p>
703 */
705 bool empty() const noexcept {
706 sc_atomic_critical sync( sync_atomic );
707 return store_ref->empty();
708 }
709
710 /**
711 * Like std::vector::size().
712 * <p>
713 * This read operation is <i>lock-free</i>.
714 * </p>
715 */
717 size_type size() const noexcept {
718 sc_atomic_critical sync( sync_atomic );
719 return store_ref->size();
720 }
721
722 // write access
723
724 /**
725 * Like std::vector::reserve(), increases this instance's capacity to <code>new_capacity</code>.
726 * <p>
727 * Only creates a new storage and invalidates iterators if <code>new_capacity</code>
728 * is greater than the current jau::darray::capacity().
729 * </p>
730 * <p>
731 * This write operation uses a mutex lock and is blocking this instances' write operations only.
732 * </p>
733 */
734 void reserve(size_type new_capacity) {
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() );
740 sc_atomic_critical sync( sync_atomic );
741 store_ref = std::move(new_store_ref);
742 }
743 }
744
745 /**
746 * Like std::vector::clear(), but ending with zero capacity.
747 * <p>
748 * This write operation uses a mutex lock and is blocking this instances' write operations.
749 * </p>
750 */
752 void clear() noexcept {
753 std::lock_guard<std::recursive_mutex> lock(mtx_write);
754 storage_ref_t new_store_ref = std::make_shared<storage_t>();
755 {
756 sc_atomic_critical sync(sync_atomic);
757 store_ref = std::move(new_store_ref);
758 }
759 }
760
761 /**
762 * Like std::vector::swap().
763 * <p>
764 * This write operation uses a mutex lock and is blocking both cow_darray instance's write operations.
765 * </p>
766 */
768 void swap(cow_darray& x) noexcept {
769 std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object
770 std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor
771 std::lock(lock, lock_x);
772 {
773 sc_atomic_critical sync_x( x.sync_atomic );
774 sc_atomic_critical sync(sync_atomic);
775 storage_ref_t x_store_ref = x.store_ref;
776 x.store_ref = store_ref;
777 store_ref = x_store_ref;
778 }
779 }
780
781 /**
782 * Like std::vector::pop_back().
783 * <p>
784 * This write operation uses a mutex lock and is blocking this instances' write operations only.
785 * </p>
786 */
788 void pop_back() noexcept {
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(),
792 store_ref->cbegin(),
793 store_ref->cend()-1,
794 store_ref->growth_factor(),
795 store_ref->get_allocator_ref() );
796 {
797 sc_atomic_critical sync(sync_atomic);
798 store_ref = std::move(new_store_ref);
799 }
800 }
801 }
802
803 /**
804 * Like std::vector::push_back(), copy
805 * <p>
806 * This write operation uses a mutex lock and is blocking this instances' write operations only.
807 * </p>
808 * @param x the value to be added at the tail.
809 */
811 void push_back(const value_type& x) {
812 std::lock_guard<std::recursive_mutex> lock(mtx_write);
813 if( store_ref->capacity_reached() ) {
814 // grow and swap all refs
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);
819 {
820 sc_atomic_critical sync(sync_atomic);
821 store_ref = std::move(new_store_ref);
822 }
823 } else {
824 // just append ..
825 store_ref->push_back(x);
826 }
827 }
828
829 /**
830 * Like std::vector::push_back(), move
831 * <p>
832 * This write operation uses a mutex lock and is blocking this instances' write operations only.
833 * </p>
834 */
837 std::lock_guard<std::recursive_mutex> lock(mtx_write);
838 if( store_ref->capacity_reached() ) {
839 // grow and swap all refs
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) );
844 {
845 sc_atomic_critical sync(sync_atomic);
846 store_ref = std::move(new_store_ref);
847 }
848 } else {
849 // just append ..
850 store_ref->push_back( std::move(x) );
851 }
852 }
853
854 /**
855 * Like std::vector::emplace_back(), construct a new element in place at the end().
856 * <p>
857 * Constructs the element at the end() using placement new.
858 * </p>
859 * <p>
860 * size will be increased by one.
861 * </p>
862 * @param args arguments to forward to the constructor of the element
863 */
864 template<typename... Args>
866 reference emplace_back(Args&&... args) {
867 std::lock_guard<std::recursive_mutex> lock(mtx_write);
868 if( store_ref->capacity_reached() ) {
869 // grow and swap all refs
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)... );
874 {
875 sc_atomic_critical sync(sync_atomic);
876 store_ref = std::move(new_store_ref);
877 }
878 return res;
879 } else {
880 // just append ..
881 return store_ref->emplace_back( std::forward<Args>(args)... );
882 }
883 }
884
885 /**
886 * Like std::vector::push_back(), but appends the whole value_type range [first, last).
887 * <p>
888 * This write operation uses a mutex lock and is blocking this instances' write operations only.
889 * </p>
890 * @tparam InputIt foreign input-iterator to range of value_type [first, last)
891 * @param first first foreign input-iterator to range of value_type [first, last)
892 * @param last last foreign input-iterator to range of value_type [first, last)
893 */
894 template< class InputIt >
896 void push_back( InputIt first, InputIt last ) {
897 std::lock_guard<std::recursive_mutex> lock(mtx_write);
898 const size_type new_size_ = store_ref->size() + size_type(last - first);
899
900 if( new_size_ > store_ref->capacity() ) {
901 // grow and swap all refs
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 );
906 {
907 sc_atomic_critical sync(sync_atomic);
908 store_ref = std::move(new_store_ref);
909 }
910 } else {
911 // just append ..
912 store_ref->push_back( first, last );
913 }
914 }
915
916 /**
917 * Like push_back(), but for more multiple const r-value to copy.
918 * <p>
919 * This write operation uses a mutex lock and is blocking this instances' write operations only.
920 * </p>
921 *
922 * @tparam Args
923 * @param args r-value references to copy into this storage
924 */
925 template <typename... Args>
926 constexpr_atomic void push_back_list(const Args&... args)
927 {
928 std::lock_guard<std::recursive_mutex> lock(mtx_write);
929 const size_type new_size_ = store_ref->size() + sizeof...(Args);
930
931 if( new_size_ > store_ref->capacity() ) {
932 // grow and swap all refs
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() );
936 // C++17 fold expression on above C++11 template pack args
937 ( new_store_ref->push_back( args ), ... ); // @suppress("Syntax error")
938 {
939 sc_atomic_critical sync(sync_atomic);
940 store_ref = std::move(new_store_ref);
941 }
942 } else {
943 // just append ..
944 // C++17 fold expression on above C++11 template pack args
945 ( store_ref->push_back( args ), ... ); // @suppress("Syntax error")
946 }
947 }
948
949 /**
950 * Like push_back(), but for more multiple r-value references to move.
951 * <p>
952 * This write operation uses a mutex lock and is blocking this instances' write operations only.
953 * </p>
954 *
955 * @tparam Args
956 * @param args r-value references to move into this storage
957 * @see jau::make_cow_darray()
958 */
959 template <typename... Args>
960 constexpr_atomic void push_back_list(Args&&... args)
961 {
962 std::lock_guard<std::recursive_mutex> lock(mtx_write);
963 const size_type new_size_ = store_ref->size() + sizeof...(Args);
964
965 if( new_size_ > store_ref->capacity() ) {
966 // grow and swap all refs
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() );
970 // C++17 fold expression on above C++11 template pack args
971 ( new_store_ref->push_back( std::move(args) ), ... ); // @suppress("Syntax error")
972 {
973 sc_atomic_critical sync(sync_atomic);
974 store_ref = std::move(new_store_ref);
975 }
976 } else {
977 // just append ..
978 // C++17 fold expression on above C++11 template pack args
979 ( store_ref->push_back( std::move(args) ), ... ); // @suppress("Syntax error")
980 }
981 }
982
983 /**
984 * Generic value_type equal comparator to be user defined for e.g. jau::cow_darray::push_back_unique().
985 * @param a one element of the equality test.
986 * @param b the other element of the equality test.
987 * @return true if both are equal
988 */
989 typedef bool(*equal_comparator)(const value_type& a, const value_type& b);
990
991 /**
992 * Like std::vector::push_back(), but only if the newly added element does not yet exist.
993 * <p>
994 * This write operation uses a mutex lock and is blocking this instances' write operations only.
995 * </p>
996 * <p>
997 * Examples
998 * <pre>
999 * static jau::cow_darray<Thing>::equal_comparator thingEqComparator =
1000 * [](const Thing &a, const Thing &b) -> bool { return a == b; };
1001 * ...
1002 * jau::cow_darray<Thing> list;
1003 *
1004 * bool added = list.push_back_unique(new_element, thingEqComparator);
1005 * ...
1006 * cow_darray<std::shared_ptr<Thing>> listOfRefs;
1007 * bool added = listOfRefs.push_back_unique(new_element,
1008 * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; });
1009 * </pre>
1010 * </p>
1011 * @param x the value to be added at the tail, if not existing yet.
1012 * @param comparator the equal comparator to return true if both given elements are equal
1013 * @return true if the element has been uniquely added, otherwise false
1014 */
1016 bool push_back_unique(const value_type& x, equal_comparator comparator) {
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 ) ) {
1020 return false; // already included
1021 } else {
1022 ++it;
1023 }
1024 }
1025 push_back(x);
1026 return true;
1027 }
1028
1029 /**
1030 * Erase either the first matching element or all matching elements.
1031 * <p>
1032 * This write operation uses a mutex lock and is blocking this instances' write operations only.
1033 * </p>
1034 * <p>
1035 * Examples
1036 * <pre>
1037 * cow_darray<Thing> list;
1038 * int count = list.erase_matching(element, true,
1039 * [](const Thing &a, const Thing &b) -> bool { return a == b; });
1040 * ...
1041 * static jau::cow_darray<Thing>::equal_comparator thingRefEqComparator =
1042 * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; };
1043 * ...
1044 * cow_darray<std::shared_ptr<Thing>> listOfRefs;
1045 * int count = listOfRefs.erase_matching(element, false, thingRefEqComparator);
1046 * </pre>
1047 * </p>
1048 * @param x the value to be added at the tail, if not existing yet.
1049 * @param all_matching if true, erase all matching elements, otherwise only the first matching element.
1050 * @param comparator the equal comparator to return true if both given elements are equal
1051 * @return number of erased elements
1052 */
1054 size_type erase_matching(const value_type& x, const bool all_matching, equal_comparator comparator) {
1055 size_type count = 0;
1056
1057 iterator it = begin(); // lock mutex and copy_store
1058 while( !it.is_end() ) {
1059 if( comparator( *it, x ) ) {
1060 it.erase();
1061 ++count;
1062 if( !all_matching ) {
1063 break;
1064 }
1065 } else {
1066 ++it;
1067 }
1068 }
1069 if( 0 < count ) {
1070 it.write_back();
1071 }
1072 return count;
1073 }
1074
1075 std::string toString() const noexcept {
1076 std::string res("{ " + std::to_string( size() ) + ": ");
1077 int i=0;
1078 jau::for_each_const(*this, [&res, &i](const value_type & e) {
1079 if( 1 < ++i ) { res.append(", "); }
1080 res.append( jau::to_string(e) );
1081 } );
1082 res.append(" }");
1083 return res;
1084 }
1085
1086 std::string get_info() const noexcept {
1087 return ("cow_darray[this "+jau::to_hexstring(this)+
1088 ", "+store_ref->get_info()+
1089 "]");
1090 }
1091 };
1092
1093 /**
1094 * Construct a cow_darray<T> instance, initialized by move semantics from the variadic (template pack) argument list.
1095 *
1096 * std::initializer_list<T> enforces to copy the created instances into the container,
1097 * since its iterator references to `const` value_type.
1098 *
1099 * This alternative template passes the r-value argument references to cow_darray::push_back_list(),
1100 * hence using `std::move` without copying semantics.
1101 *
1102 * All argument types must be of same type, i.e. std::is_same.
1103 * The deduced darray<T> instance also uses same type as its Value_type.
1104 *
1105 * @tparam First the first argument type, must be same
1106 * @tparam Next all other argument types, must be same
1107 * @tparam
1108 * @param arg1 the first r-value
1109 * @param argsN the other r-values
1110 * @return the new `cow_darray`
1111 * @see cow_darray::push_back_list()
1112 * @see make_cow_darray()
1113 */
1114 template <typename First, typename... Next,
1115 // std::enable_if_t< ( std::is_same<First, Next>::value && ... ), bool> = true>
1116 std::enable_if_t< std::conjunction_v<std::is_same<First, Next>... >, bool> = true>
1117 constexpr cow_darray< First > make_cow_darray(First&& arg1, Next&&... argsN)
1118 {
1119 cow_darray< First > d(1 + sizeof...(Next));
1120 // C++17 fold expression on above C++11 template pack arg1 and argsN
1121 // d.push_back_list( std::forward<First>(arg1), ( std::forward<Next>(argsN), ... ) ); // @suppress("Syntax error")
1122 d.push_back_list( arg1, argsN... ); // @suppress("Syntax error")
1123 return d;
1124 }
1125
1126 /**
1127 * Complement constructor for cow_darray<T> instance, move semantics initializer for one argument.
1128 * @tparam First
1129 * @tparam Next
1130 * @param arg1
1131 * @return
1132 * @see cow_darray::push_back()
1133 * @see cow_darray::push_back_list()
1134 * @see make_cow_darray()
1135 */
1136 template <typename First, typename... Next>
1137 constexpr cow_darray< First > make_cow_darray(First&& arg1)
1138 {
1140 d.push_back( std::forward<First>(arg1) );
1141 return d;
1142 }
1143
1144 /****************************************************************************************
1145 ****************************************************************************************/
1146
1147 template<typename Value_type, typename Size_type, typename Alloc_type>
1148 std::ostream & operator << (std::ostream &out, const cow_darray<Value_type, Size_type, Alloc_type> &c) {
1149 out << c.toString();
1150 return out;
1151 }
1152
1153 /****************************************************************************************
1154 ****************************************************************************************/
1155
1156 template<typename Value_type, typename Size_type, typename Alloc_type>
1158 if( &rhs == &lhs ) {
1159 return true;
1160 }
1162 rhs_cend += rhs.size();
1163 return (rhs.size() == lhs.size() && std::equal(rhs.cbegin(), rhs_cend, lhs.cbegin()));
1164 }
1165 template<typename Value_type, typename Size_type, typename Alloc_type>
1167 return !(rhs==lhs);
1168 }
1169
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);
1177 }
1178
1179 template<typename Value_type, typename Size_type, typename Alloc_type>
1181 { return lhs < rhs; }
1182
1183 template<typename Value_type, typename Size_type, typename Alloc_type>
1185 { return !(lhs < rhs); }
1186
1187 template<typename Value_type, typename Size_type, typename Alloc_type>
1189 { return !(rhs < lhs); }
1190
1191 template<typename Value_type, typename Size_type, typename Alloc_type>
1193 { rhs.swap(lhs); }
1194
1195 /**@}*/
1196
1197} /* namespace jau */
1198
1199/** \example test_cow_iterator_01.cpp
1200 * This C++ unit test of const jau::cow_ro_iterator and mutable jau::cow_rw_iterator
1201 * in conjunction with jau::cow_darray demonstrates the effect of CoW const and mutable CoW operations
1202 * besides testing them.
1203 */
1204
1205/** \example test_cow_darray_perf01.cpp
1206 * This C++ unit test validates the performance and correctness of the jau::cow_darray implementation.
1207 */
1208
1209/** \example test_cow_darray_01.cpp
1210 * This C++ unit test validates the jau::cow_darray implementation.
1211 */
1212
1213#endif /* JAU_COW_DARRAY_HPP_ */
Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage,...
Definition: cow_darray.hpp:127
static constexpr const bool uses_memmove
Definition: cow_darray.hpp:132
constexpr_atomic cow_darray & operator=(const cow_darray &x)
Like std::vector::operator=(&), assignment.
Definition: cow_darray.hpp:365
constexpr std::recursive_mutex & get_write_mutex() noexcept
Returns this instances' recursive write mutex, allowing user to implement more complex mutable write ...
Definition: cow_darray.hpp:535
constexpr_atomic storage_ref_t copy_store()
Returns a new shared_ptr copy of the underlying store, i.e.
Definition: cow_darray.hpp:551
constexpr_atomic void push_back(value_type &&x)
Like std::vector::push_back(), move.
Definition: cow_darray.hpp:836
value_type * pointer
Definition: cow_darray.hpp:139
constexpr_atomic void push_back(const value_type &x)
Like std::vector::push_back(), copy.
Definition: cow_darray.hpp:811
constexpr_atomic void clear() noexcept
Like std::vector::clear(), but ending with zero capacity.
Definition: cow_darray.hpp:752
constexpr const_iterator cbegin() const noexcept
Returns an jau::cow_ro_iterator to the first element of this CoW storage.
Definition: cow_darray.hpp:637
bool(* equal_comparator)(const value_type &a, const value_type &b)
Generic value_type equal comparator to be user defined for e.g.
Definition: cow_darray.hpp:989
constexpr_atomic size_type size() const noexcept
Like std::vector::size().
Definition: cow_darray.hpp:717
static constexpr const float DEFAULT_GROWTH_FACTOR
Default growth factor using the golden ratio 1.618.
Definition: cow_darray.hpp:130
Value_type value_type
Definition: cow_darray.hpp:138
~cow_darray() noexcept
Definition: cow_darray.hpp:509
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.
Definition: cow_darray.hpp:226
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.
Definition: cow_darray.hpp:322
constexpr cow_darray(const storage_t &x, const float growth_factor, const allocator_type &alloc)
Definition: cow_darray.hpp:239
constexpr_atomic void swap(cow_darray &x) noexcept
Like std::vector::swap().
Definition: cow_darray.hpp:768
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.
Definition: cow_darray.hpp:502
constexpr_atomic cow_darray & operator=(cow_darray &&x) noexcept
Like std::vector::operator=(&&), move.
Definition: cow_darray.hpp:410
constexpr_atomic reference emplace_back(Args &&... args)
Like std::vector::emplace_back(), construct a new element in place at the end().
Definition: cow_darray.hpp:866
std::make_signed< size_type >::type difference_type
Definition: cow_darray.hpp:144
cow_darray & operator=(storage_t &&x)
Like std::vector::operator=(&&), move, but taking the underling jau::darray.
Definition: cow_darray.hpp:282
constexpr size_type max_size() const noexcept
Returns std::numeric_limits<difference_type>::max() as the maximum array size.
Definition: cow_darray.hpp:520
const value_type & const_reference
Definition: cow_darray.hpp:142
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 ...
Definition: cow_darray.hpp:486
bool darray_tag
Used to determine whether this type is a darray or has a darray, see ::is_darray_type<T>
Definition: cow_darray.hpp:153
static constexpr const bool uses_secmem
Definition: cow_darray.hpp:133
const allocator_type & get_allocator_ref() const noexcept
Definition: cow_darray.hpp:666
Size_type size_type
Definition: cow_darray.hpp:143
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...
Definition: cow_darray.hpp:178
constexpr cow_darray(storage_t &&x) noexcept
Definition: cow_darray.hpp:262
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...
Definition: cow_darray.hpp:447
constexpr_atomic void push_back_list(Args &&... args)
Like push_back(), but for more multiple r-value references to move.
Definition: cow_darray.hpp:960
cow_darray< value_type, size_type, allocator_type, use_memmove, use_secmem > cow_container_t
Definition: cow_darray.hpp:157
constexpr cow_darray() noexcept
Default constructor, giving almost zero capacity and zero memory footprint, but the shared empty jau:...
Definition: cow_darray.hpp:215
static constexpr const bool uses_realloc
Definition: cow_darray.hpp:134
constexpr_atomic float growth_factor() const noexcept
Returns the growth factor.
Definition: cow_darray.hpp:680
std::shared_ptr< storage_t > storage_ref_t
Definition: cow_darray.hpp:150
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...
Definition: cow_darray.hpp:469
constexpr_atomic void push_back(InputIt first, InputIt last)
Like std::vector::push_back(), but appends the whole value_type range [first, last).
Definition: cow_darray.hpp:896
allocator_type get_allocator() const noexcept
Definition: cow_darray.hpp:671
constexpr_atomic void push_back_list(const Args &... args)
Like push_back(), but for more multiple const r-value to copy.
Definition: cow_darray.hpp:926
void reserve(size_type new_capacity)
Like std::vector::reserve(), increases this instance's capacity to new_capacity.
Definition: cow_darray.hpp:734
darray< value_type, size_type, allocator_type, use_memmove, use_secmem > storage_t
Definition: cow_darray.hpp:149
constexpr_atomic bool empty() const noexcept
Like std::vector::empty().
Definition: cow_darray.hpp:705
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.
Definition: cow_darray.hpp:251
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().
Definition: cow_darray.hpp:693
Alloc_type allocator_type
Definition: cow_darray.hpp:145
constexpr iterator begin()
Returns an jau::cow_rw_iterator to the first element of this CoW storage.
Definition: cow_darray.hpp:660
constexpr_atomic cow_darray(cow_darray &&x) noexcept
Definition: cow_darray.hpp:385
constexpr cow_darray(storage_t &&x, const float growth_factor, const allocator_type &alloc) noexcept
Definition: cow_darray.hpp:269
constexpr_atomic cow_darray(const cow_darray &x)
Creates a new instance, copying all elements from the given array.
Definition: cow_darray.hpp:302
value_type & reference
Definition: cow_darray.hpp:141
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.
Definition: cow_darray.hpp:197
constexpr_atomic void pop_back() noexcept
Like std::vector::pop_back().
Definition: cow_darray.hpp:788
constexpr_atomic storage_ref_t snapshot() const noexcept
Returns the current snapshot of the underlying shared storage by reference.
Definition: cow_darray.hpp:611
const value_type * const_pointer
Definition: cow_darray.hpp:140
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...
Definition: cow_darray.hpp:346
std::string toString() const noexcept
constexpr cow_darray(const storage_t &x)
Definition: cow_darray.hpp:233
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...
Definition: cow_darray.hpp:588
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.
Definition: darray.hpp:148
std::string get_info() const noexcept
Definition: darray.hpp:1330
This class provides a RAII-style Sequentially Consistent (SC) data race free (DRF) critical block.
#define JAU_DARRAY_PRINTF(...)
Definition: darray.hpp:59
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
Definition: base_codec.hpp:97
#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)
Definition: base_math.hpp:191
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.
Definition: backtrace.hpp:32
bool operator==(const callocator< T1 > &lhs, const callocator< T2 > &rhs) noexcept
Definition: callocator.hpp:150
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,...
Definition: debug.cpp:173
bool operator!=(const callocator< T1 > &lhs, const callocator< T2 > &rhs) noexcept
Definition: callocator.hpp:163
STL namespace.
uint8_t Value_type