aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSven Gothel <[email protected]>2021-01-02 09:34:57 +0100
committerSven Gothel <[email protected]>2021-01-02 09:34:57 +0100
commit4b18e563c90792cba2aadbe047bdf80d174d2dcb (patch)
tree9e545c4dc3c5f2279c89e28755dcf330997d9f13
parent9baec450538c1e85d18dc130af68ea71c17d3306 (diff)
Add: darray, cow_darray, cow_iterator; Adjust cow_vector to cow_darray findings (deprecated); Performance enhancements
cow_darray, cow_vector design changes / notes: - Aligned all typedef's names etc between both implementations for easier review - Removed direct element access, as this would be only valid if Value_type is a std:share_ptr, assuming the underlying shared storage has been pulled. Use iterator! - Introducing immutable const_iterator (a jau::cow_ro_iterator) and mutable iterator (a jau::cow_rw_iterator). Both types hold the underling's iterator and also either the lock-free shared snapshot (const_iterator) or hold the lock and a copy of the storage (iterator). This guarantees an efficient std API aligned operation, keeping alove std::shared_ptr references. - Removed for_each_cow: Use std::for_each with our new const_iterator or iterator etc... Performance changes / notes: - cow_darray: Use fixed golden-ratio for grow-factor in push_back(), reducing too many copies. - cow_darray::push_back(..): No copy on size < capacity, just push_back into underling, dramatically reducing copies. Guaranteed correct using cow_darray + darray, as darray increments end_ iterator after the new element has been added. - Always use pre-increment/decrement, avoiding copy with post-* variant. cow_vector fixes (learned from working with cow_darray) - reserve(): Only is new_capacity > capacity, then need copy_ctor storage - operator=(cow_vector&& x): Hold both cow_vector's write-mutex - pop_back(): Only if not empty - +++ Performance seems to fluctuate on the allocator and we might want resolve this with a custom pooled alloctor. This is obvious when comparing the 'empty' samples with 'reserved', the latter reserve whole memory of the std::vector and jau::darray upfront. Performance on arm64-raspi4 jau::cow_vector vs jau::cow_darray: - sequential fill and list O(1): cow_vector is ~30 times slower (starting empty) (delta due to cow_darray capacity usage, less copies) - unique fill and list O(n*n): cow_vector is 2-3 times slower (starting empty) (most time used for equal time dereferencing) Performance on arm64-raspi4 std::vector vs jau::darray: - sequential fill and list iterator O(1): jau::darray is ~0% - 40% slower (50 .. 1000) (starting empty) (we may call this almost equal, probably allocator related) - unique fill and list iterator O(n*n): std::vector is ~0% - 23% slower (50 .. 1000) (starting empty) (almost equal, most time used for equal time dereferencing) +++ Performance on amd64 jau::cow_vector vs jau::cow_darray: - sequential fill and list O(1): cow_vector is ~38 times slower (starting empty) (delta due to cow_darray capacity usage, less copies) - unique fill and list O(n*n): cow_vector is ~2 times slower (starting empty) (most time used for equal time dereferencing) Performance on amd64 std::vector vs jau::darray: - sequential fill and list iterator O(1): jau::darray is ~0% - 20% slower (50 .. 1000) (starting empty) (we may call this almost equal, probably allocator related) - unique fill and list iterator O(n*n): std::vector is ~0% - 30% slower (50 .. 1000) (starting empty) (almost equal, most time used for equal time dereferencing) +++ Memory ratio allocation/size jau::cow_vector vs jau::cow_darray having size: - 50: 2 vs 1.1 - 100: 2 vs 1.44 - 1000: 2 vs 1.6 - Hence cow_darray golden-ratio growth factor is more efficient on size + perf. Memory ratio allocation/size std::vector vs jau::darray having size: - 50: 1.28 vs 1.10 - 100: 1.28 vs 1.44 - 1000: 1.03 vs 1.60 - Hence cow_darray golden-ratio growth factor is less efficient on big sizes (but configurable)
Diffstat
-rw-r--r--doc/test/test_cow_darray_perf01.amd64.log350
-rw-r--r--doc/test/test_cowvector_perf01.amd64.log153
-rw-r--r--doc/test/test_cowvector_perf01.arm64-raspi4.log153
-rw-r--r--doc/test/test_hashset_perf01.amd64.log117
-rw-r--r--doc/test/test_hashset_perf01.arm64-raspi4.log117
-rw-r--r--include/jau/counting_allocator.hpp7
-rw-r--r--include/jau/cow_darray.hpp817
-rw-r--r--include/jau/cow_iterator.hpp254
-rw-r--r--include/jau/cow_vector.hpp238
-rw-r--r--include/jau/darray.hpp821
-rw-r--r--test/CMakeLists.txt3
-rw-r--r--test/test_cow_darray_01.cpp380
-rw-r--r--test/test_cow_darray_perf01.cpp565
-rw-r--r--test/test_cowvector_perf01.cpp340
14 files changed, 3346 insertions, 969 deletions
diff --git a/doc/test/test_cow_darray_perf01.amd64.log b/doc/test/test_cow_darray_perf01.amd64.log
new file mode 100644
index 0000000..69e64eb
--- /dev/null
+++ b/doc/test/test_cow_darray_perf01.amd64.log
@@ -0,0 +1,350 @@
+COMMANDLINE scripts/test_cow_darray_perf01.sh -v normal
+EXE_WRAPPER nice -20
+logbasename test_cow_darray_perf01.amd64
+logfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.0.log
+valgrindlogfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.valgrind.0.log
+callgrindoutfile /usr/local/projects/zafena/jaulib/doc/test/test_cow_darray_perf01.amd64.callgrind.0.out
+nice -20 /usr/local/projects/zafena/jaulib/build-amd64/test/test_cow_darray_perf01 -v normal
+argc 3, auto_run 0, perf_analysis 0
+Mem: stdvec_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
+Mem: stdvec_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
+Mem: stdvec_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
+Mem: darray_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 880 bytes, alloc[balance 1 = 9 - 8]], 1.100000 ratio
+Mem: darray_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,304 bytes, alloc[balance 1 = 11 - 10]], 1.440000 ratio
+Mem: darray_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 25,552 bytes, alloc[balance 1 = 16 - 15]], 1.597000 ratio
+Mem: cowstdvec_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio
+Mem: cowstdvec_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio
+Mem: cowstdvec_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio
+Mem: cowdarray_empty_ 01 (full_): Elements 50 x 16 bytes; CAlloc[ 880 bytes, alloc[balance 1 = 1 - 0]], 1.100000 ratio
+Mem: cowdarray_empty_ 01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,304 bytes, alloc[balance 1 = 1 - 0]], 1.440000 ratio
+Mem: cowdarray_empty_ 01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 25,552 bytes, alloc[balance 1 = 1 - 0]], 1.597000 ratio
+
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+test_cow_darray_perf01 is a Catch v3.0.0-preview.3 host application.
+Run with -? for options
+
+-------------------------------------------------------------------------------
+Perf Test 01 - Fill Sequential and List, empty and reserve
+-------------------------------------------------------------------------------
+/test/test_cow_darray_perf01.cpp:504
+...............................................................................
+
+benchmark name samples iterations estimated
+ mean low mean high mean
+ std dev low std dev high std dev
+-------------------------------------------------------------------------------
+STD_Vector_empty_idx FillSeq_List
+50 100 36 2.1168 ms
+ 587.887 ns 586.534 ns 592.851 ns
+ 11.6643 ns 2.59561 ns 26.681 ns
+
+STD_Vector_empty_idx FillSeq_List
+100 100 21 2.1273 ms
+ 1.01551 us 1.01076 us 1.02473 us
+ 32.6187 ns 19.7948 ns 53.2098 ns
+
+STD_Vector_empty_idx FillSeq_List
+1000 100 3 2.3295 ms
+ 7.7587 us 7.75414 us 7.77689 us
+ 42.9198 ns 4.0468 ns 101.951 ns
+
+STD_Vector_empty_itr FillSeq_List
+50 100 36 2.1276 ms
+ 586.001 ns 585.784 ns 586.568 ns
+ 1.65525 ns 0.465353 ns 3.27567 ns
+
+STD_Vector_empty_itr FillSeq_List
+100 100 21 2.0895 ms
+ 994.921 ns 988.919 ns 1.00582 us
+ 40.1812 ns 25.3082 ns 57.6708 ns
+
+STD_Vector_empty_itr FillSeq_List
+1000 100 3 2.3886 ms
+ 7.87883 us 7.816 us 7.98781 us
+ 409.816 ns 278.711 ns 740.356 ns
+
+JAU_DArray_empty_idx FillSeq_List
+50 100 35 2.114 ms
+ 598.635 ns 596.777 ns 605.661 ns
+ 16.3576 ns 3.66866 ns 38.0961 ns
+
+JAU_DArray_empty_idx FillSeq_List
+100 100 19 2.1223 ms
+ 1.106 us 1.10402 us 1.1153 us
+ 18.5808 ns 0.490943 ns 44.1982 ns
+
+JAU_DArray_empty_idx FillSeq_List
+1000 100 3 2.8092 ms
+ 9.3225 us 9.29807 us 9.38497 us
+ 184.594 ns 87.6997 ns 341.201 ns
+
+JAU_DArray_empty_itr FillSeq_List
+50 100 36 2.142 ms
+ 596.304 ns 592.709 ns 604.02 ns
+ 25.6078 ns 13.9646 ns 44.649 ns
+
+JAU_DArray_empty_itr FillSeq_List
+100 100 19 2.1546 ms
+ 1.1111 us 1.10853 us 1.11751 us
+ 18.3155 ns 2.03707 ns 34.3155 ns
+
+JAU_DArray_empty_itr FillSeq_List
+1000 100 3 2.8344 ms
+ 9.30593 us 9.30037 us 9.33189 us
+ 52.9018 ns 3.95373 ns 125.894 ns
+
+COW_Vector_empty_itr FillSeq_List
+50 100 4 2.3236 ms
+ 5.74342 us 5.69619 us 5.92492 us
+ 407.638 ns 103.644 ns 933.721 ns
+
+COW_Vector_empty_itr FillSeq_List
+100 100 2 3.8364 ms
+ 19.5381 us 19.4755 us 19.6833 us
+ 470.471 ns 238.193 ns 793.648 ns
+
+COW_Vector_empty_itr FillSeq_List
+1000 100 1 103.138 ms
+ 1.02219 ms 1.02134 ms 1.02303 ms
+ 4.30683 us 3.85196 us 4.88288 us
+
+COW_DArray_empty_itr FillSeq_List
+50 100 12 2.1456 ms
+ 1.76765 us 1.76743 us 1.76851 us
+ 1.98944 ns 0.373864 ns 4.62752 ns
+
+COW_DArray_empty_itr FillSeq_List
+100 100 7 2.2855 ms
+ 3.27837 us 3.26571 us 3.30378 us
+ 88.2901 ns 50.5299 ns 144.154 ns
+
+COW_DArray_empty_itr FillSeq_List
+1000 100 1 2.8288 ms
+ 28.1568 us 28.1023 us 28.2788 us
+ 395.76 ns 197.003 ns 670.658 ns
+
+STD_Vector_rserv_itr FillSeq_List
+50 100 41 2.1279 ms
+ 521.165 ns 519.728 ns 524.924 ns
+ 10.3168 ns 0.266432 ns 20.6426 ns
+
+STD_Vector_rserv_itr FillSeq_List
+100 100 24 2.1096 ms
+ 880.622 ns 877.774 ns 886.438 ns
+ 19.8502 ns 10.6627 ns 31.7561 ns
+
+STD_Vector_rserv_itr FillSeq_List
+1000 100 4 2.6292 ms
+ 6.58481 us 6.56973 us 6.63792 us
+ 124.657 ns 26.2394 ns 278.381 ns
+
+JAU_DArray_rserv_itr FillSeq_List
+50 100 44 2.0944 ms
+ 504.908 ns 503.426 ns 508.953 ns
+ 10.9981 ns 0.347251 ns 23.449 ns
+
+JAU_DArray_rserv_itr FillSeq_List
+100 100 26 2.1476 ms
+ 827.16 ns 825.085 ns 836.084 ns
+ 18.0184 ns 0.377244 ns 42.4347 ns
+
+JAU_DArray_rserv_itr FillSeq_List
+1000 100 4 2.3976 ms
+ 6.00385 us 5.99214 us 6.06161 us
+ 115.24 ns 1.93334 ns 252.482 ns
+
+COW_Vector_rserv_itr FillSeq_List
+50 100 4 2.476 ms
+ 6.12628 us 6.12033 us 6.15452 us
+ 57.0493 ns 3.45555 ns 135.858 ns
+
+COW_Vector_rserv_itr FillSeq_List
+100 100 2 4.073 ms
+ 20.5219 us 20.4073 us 20.9229 us
+ 913.922 ns 52.6484 ns 2.0721 us
+
+COW_Vector_rserv_itr FillSeq_List
+1000 100 1 108.419 ms
+ 1.08169 ms 1.08077 ms 1.08265 ms
+ 4.81349 us 4.35774 us 5.38341 us
+
+COW_Vector_rserv_itr FillSeq_List
+50 100 4 2.4752 ms
+ 6.17815 us 6.1529 us 6.23063 us
+ 177.523 ns 102.004 ns 280.314 ns
+
+COW_Vector_rserv_itr FillSeq_List
+100 100 2 4.0584 ms
+ 20.1429 us 20.0586 us 20.4957 us
+ 744.84 ns 137.805 ns 1.7365 us
+
+COW_Vector_rserv_itr FillSeq_List
+1000 100 1 108.332 ms
+ 1.07729 ms 1.07656 ms 1.078 ms
+ 3.68093 us 3.21951 us 4.23509 us
+
+
+-------------------------------------------------------------------------------
+Perf Test 02 - Fill Unique and List, empty and reserve
+-------------------------------------------------------------------------------
+/test/test_cow_darray_perf01.cpp:530
+...............................................................................
+
+benchmark name samples iterations estimated
+ mean low mean high mean
+ std dev low std dev high std dev
+-------------------------------------------------------------------------------
+STD_Vector_empty_idx FillUni_List
+50 100 11 2.0922 ms
+ 1.78899 us 1.78235 us 1.80339 us
+ 47.5893 ns 26.0812 ns 77.9321 ns
+
+STD_Vector_empty_idx FillUni_List
+100 100 4 2.3412 ms
+ 6.24056 us 6.21462 us 6.30519 us
+ 196.305 ns 97.444 ns 407.914 ns
+
+STD_Vector_empty_idx FillUni_List
+1000 100 1 39.3706 ms
+ 389.91 us 388.749 us 393.46 us
+ 9.43058 us 3.86633 us 20.7428 us
+
+STD_Vector_empty_itr FillUni_List
+50 100 13 2.1619 ms
+ 1.62625 us 1.62237 us 1.636 us
+ 27.9497 ns 4.07125 ns 51.1131 ns
+
+STD_Vector_empty_itr FillUni_List
+100 100 4 2.23 ms
+ 5.54929 us 5.54172 us 5.57753 us
+ 66.2521 ns 17.5609 ns 152.82 ns
+
+STD_Vector_empty_itr FillUni_List
+1000 100 1 38.6387 ms
+ 387.279 us 386.262 us 391.178 us
+ 8.98648 us 2.04055 us 20.9355 us
+
+JAU_DArray_empty_idx FillUni_List
+50 100 12 2.1828 ms
+ 1.88023 us 1.85714 us 1.90417 us
+ 119.67 ns 114.33 ns 135.271 ns
+
+JAU_DArray_empty_idx FillUni_List
+100 100 4 2.7236 ms
+ 6.79534 us 6.77376 us 6.84645 us
+ 159.206 ns 78.086 ns 287.348 ns
+
+JAU_DArray_empty_idx FillUni_List
+1000 100 1 38.8248 ms
+ 394.747 us 394.236 us 395.342 us
+ 2.81011 us 2.40999 us 3.27223 us
+
+JAU_DArray_empty_itr FillUni_List
+50 100 13 2.1112 ms
+ 1.6465 us 1.64008 us 1.66125 us
+ 48.7547 ns 27.7939 ns 77.669 ns
+
+JAU_DArray_empty_itr FillUni_List
+100 100 4 2.5492 ms
+ 6.36098 us 6.34687 us 6.37031 us
+ 57.031 ns 42.8585 ns 112.034 ns
+
+JAU_DArray_empty_itr FillUni_List
+1000 100 1 39.8971 ms
+ 399.012 us 393.175 us 407.601 us
+ 35.6943 us 26.9714 us 44.1455 us
+
+COW_Vector_empty_itr FillUni_List
+50 100 2 2.4302 ms
+ 12.219 us 12.1941 us 12.2724 us
+ 177.965 ns 73.8311 ns 305.141 ns
+
+COW_Vector_empty_itr FillUni_List
+100 100 1 3.6369 ms
+ 36.292 us 36.2068 us 36.5079 us
+ 643.556 ns 285.442 ns 1.27906 us
+
+COW_Vector_empty_itr FillUni_List
+1000 100 1 182.543 ms
+ 1.8947 ms 1.8934 ms 1.89613 ms
+ 6.92523 us 6.21527 us 7.78582 us
+
+COW_DArray_empty_itr FillUni_List
+50 100 3 2.1018 ms
+ 6.99721 us 6.9725 us 7.04634 us
+ 169.177 ns 95.3738 ns 262.178 ns
+
+COW_DArray_empty_itr FillUni_List
+100 100 2 3.3468 ms
+ 16.7829 us 16.714 us 16.9106 us
+ 464.357 ns 281.39 ns 699.268 ns
+
+COW_DArray_empty_itr FillUni_List
+1000 100 1 60.1642 ms
+ 593.482 us 592.789 us 594.21 us
+ 3.64366 us 3.11135 us 4.36028 us
+
+STD_Vector_rserv_itr FillUni_List
+50 100 14 2.1126 ms
+ 1.5431 us 1.53312 us 1.56815 us
+ 70.7362 ns 4.62231 ns 130.265 ns
+
+STD_Vector_rserv_itr FillUni_List
+100 100 4 2.1356 ms
+ 5.42934 us 5.40332 us 5.48336 us
+ 182.126 ns 105.133 ns 322.296 ns
+
+STD_Vector_rserv_itr FillUni_List
+1000 100 1 37.5587 ms
+ 371.987 us 371.528 us 372.643 us
+ 2.76657 us 2.13462 us 4.02853 us
+
+JAU_DArray_rserv_itr FillUni_List
+50 100 13 2.0904 ms
+ 1.6157 us 1.61182 us 1.6312 us
+ 33.6739 ns 3.69632 ns 78.0574 ns
+
+JAU_DArray_rserv_itr FillUni_List
+100 100 4 2.2192 ms
+ 5.33926 us 5.33073 us 5.3557 us
+ 58.2143 ns 30.7842 ns 104.499 ns
+
+JAU_DArray_rserv_itr FillUni_List
+1000 100 1 37.1666 ms
+ 370.967 us 370.349 us 372.018 us
+ 4.03079 us 2.70746 us 6.23372 us
+
+COW_Vector_rserv_itr FillUni_List
+50 100 2 2.4072 ms
+ 11.9813 us 11.89 us 12.2839 us
+ 708.205 ns 35.07 ns 1.58406 us
+
+COW_Vector_rserv_itr FillUni_List
+100 100 1 3.5566 ms
+ 35.4723 us 35.3395 us 35.725 us
+ 905.511 ns 543.264 ns 1.4284 us
+
+COW_Vector_rserv_itr FillUni_List
+1000 100 1 180.037 ms
+ 1.80119 ms 1.79948 ms 1.80266 ms
+ 8.06882 us 6.80229 us 9.89432 us
+
+COW_DArray_rserv_itr FillUni_List
+50 100 4 2.5848 ms
+ 6.46866 us 6.467 us 6.47635 us
+ 15.577 ns 1.36692 ns 37.0103 ns
+
+COW_DArray_rserv_itr FillUni_List
+100 100 2 3.1924 ms
+ 15.8892 us 15.8474 us 16.0002 us
+ 328.232 ns 139.156 ns 660.64 ns
+
+COW_DArray_rserv_itr FillUni_List
+1000 100 1 57.9012 ms
+ 573.339 us 572.701 us 574.159 us
+ 3.65916 us 2.96615 us 4.6329 us
+
+
+===============================================================================
+All tests passed (64672560 assertions in 3 test cases)
+
diff --git a/doc/test/test_cowvector_perf01.amd64.log b/doc/test/test_cowvector_perf01.amd64.log
deleted file mode 100644
index 1c07f45..0000000
--- a/doc/test/test_cowvector_perf01.amd64.log
+++ /dev/null
@@ -1,153 +0,0 @@
-argc 3, auto-run 0
-Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
-
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-test_cowvector_perf01 is a Catch v3.0.0-preview.3 host application.
-Run with -? for options
-
--------------------------------------------------------------------------------
-STD Vector Perf Test 01 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:231
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 60 2.082 ms
- 350.144 ns 349.585 ns 351.737 ns
- 4.42199 ns 2.00301 ns 9.59688 ns
-
-Seq_List 50 100 38 2.0672 ms
- 541.848 ns 541.807 ns 541.982 ns
- 0.345592 ns 0.122757 ns 0.771527 ns
-
-Seq_List 100 100 23 2.116 ms
- 920.523 ns 916.727 ns 927.621 ns
- 25.7041 ns 15.8618 ns 38.9443 ns
-
-Seq_List 200 100 13 2.1879 ms
- 1.72219 us 1.71326 us 1.73803 us
- 58.9475 ns 36.6068 ns 87.466 ns
-
-Seq_List 1000 100 3 2.1756 ms
- 7.32046 us 7.28011 us 7.40319 us
- 283.239 ns 160.691 ns 468.914 ns
-
-
-Mem: cowvec_11 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio
-Mem: cowvec_11 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio
-Mem: cowvec_11 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio
-Mem: cowvec_11 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio
-Mem: cowvec_11 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio
--------------------------------------------------------------------------------
-COW Vector Perf Test 11 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:258
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 10 2.284 ms
- 2.27211 us 2.26364 us 2.28704 us
- 55.6548 ns 36.1072 ns 83.1873 ns
-
-Seq_List 50 100 4 2.4708 ms
- 6.14203 us 6.12294 us 6.19001 us
- 138.624 ns 22.5121 ns 254.346 ns
-
-Seq_List 100 100 1 2.0615 ms
- 20.2991 us 20.2313 us 20.4742 us
- 502.929 ns 120.184 ns 907.942 ns
-
-Seq_List 200 100 1 6.3719 ms
- 63.9441 us 63.7343 us 64.293 us
- 1.34563 us 895.153 ns 2.00555 us
-
-Seq_List 1000 100 1 106.105 ms
- 1.04617 ms 1.04518 ms 1.04712 ms
- 4.92832 us 4.12439 us 6.22148 us
-
-
-Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
--------------------------------------------------------------------------------
-STD Vector Perf Test 02 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:286
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 24 2.0616 ms
- 846.189 ns 843.472 ns 852.225 ns
- 19.5557 ns 9.92097 ns 34.0883 ns
-
-Unique Find 50 100 9 2.0943 ms
- 2.27419 us 2.27358 us 2.2756 us
- 4.66728 ns 2.60139 ns 7.45502 ns
-
-Unique Find 100 100 3 2.2263 ms
- 7.79227 us 7.75814 us 7.84904 us
- 221.114 ns 150.556 ns 325.101 ns
-
-Unique Find 200 100 1 2.9961 ms
- 29.4696 us 29.2017 us 29.7451 us
- 1.3753 us 964.726 ns 2.04338 us
-
-Unique Find 1000 100 1 101.375 ms
- 1.00886 ms 1.00591 ms 1.01206 ms
- 15.7557 us 13.6415 us 20.1276 us
-
-
-Mem: cowvec_12 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio
-Mem: cowvec_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio
-Mem: cowvec_12 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio
-Mem: cowvec_12 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio
-Mem: cowvec_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio
--------------------------------------------------------------------------------
-COW Vector Perf Test 12 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:313
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 5 2.2945 ms
- 4.6223 us 4.61348 us 4.63931 us
- 60.3974 ns 38.3079 ns 116.061 ns
-
-Unique Find 50 100 2 3.169 ms
- 15.8017 us 15.7506 us 15.9111 us
- 365.232 ns 205.942 ns 667.899 ns
-
-Unique Find 100 100 1 5.8658 ms
- 57.5863 us 57.486 us 57.9267 us
- 839.216 ns 279.156 ns 1.87942 us
-
-Unique Find 200 100 1 21.1047 ms
- 210.697 us 210.437 us 211.044 us
- 1.52385 us 1.22872 us 2.03313 us
-
-Unique Find 1000 100 1 467.482 ms
- 4.69308 ms 4.6879 ms 4.69895 ms
- 28.3154 us 25.1022 us 32.3612 us
-
-
-===============================================================================
-All tests passed (17403632 assertions in 4 test cases)
-
diff --git a/doc/test/test_cowvector_perf01.arm64-raspi4.log b/doc/test/test_cowvector_perf01.arm64-raspi4.log
deleted file mode 100644
index 7497ffe..0000000
--- a/doc/test/test_cowvector_perf01.arm64-raspi4.log
+++ /dev/null
@@ -1,153 +0,0 @@
-argc 3, auto-run 0
-Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
-
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-test_cowvector_perf01 is a Catch v3.0.0-preview.3 host application.
-Run with -? for options
-
--------------------------------------------------------------------------------
-STD Vector Perf Test 01 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:231
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 77 9.9099 ms
- 1.27432 us 1.27211 us 1.27914 us
- 15.8552 ns 6.72908 ns 27.0865 ns
-
-Seq_List 50 100 55 9.9 ms
- 1.79602 us 1.78413 us 1.84783 us
- 107.523 ns 14.5073 ns 253.156 ns
-
-Seq_List 100 100 34 9.9518 ms
- 2.9136 us 2.90828 us 2.92575 us
- 39.7364 ns 22.7895 ns 64.0512 ns
-
-Seq_List 200 100 21 10.0926 ms
- 4.77759 us 4.77012 us 4.79622 us
- 54.9702 ns 16.1965 ns 97.5445 ns
-
-Seq_List 1000 100 6 11.5296 ms
- 19.1583 us 19.1215 us 19.2311 us
- 254.646 ns 157.209 ns 395.481 ns
-
-
-Mem: cowvec_11 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio
-Mem: cowvec_11 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio
-Mem: cowvec_11 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio
-Mem: cowvec_11 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio
-Mem: cowvec_11 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio
--------------------------------------------------------------------------------
-COW Vector Perf Test 11 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:258
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 8 10.5888 ms
- 13.4481 us 13.4223 us 13.4991 us
- 178.586 ns 109.07 ns 277.353 ns
-
-Seq_List 50 100 3 10.1469 ms
- 34.5996 us 34.5337 us 34.748 us
- 482.345 ns 282.181 ns 759.841 ns
-
-Seq_List 100 100 2 18.8188 ms
- 94.4849 us 94.3041 us 94.8347 us
- 1.23247 us 752.838 ns 1.9215 us
-
-Seq_List 200 100 1 26.7126 ms
- 266.465 us 266.108 us 267.02 us
- 2.23473 us 1.57151 us 2.96187 us
-
-Seq_List 1000 100 1 445.089 ms
- 4.43661 ms 4.43537 ms 4.43874 ms
- 8.07672 us 5.41298 us 14.4825 us
-
-
-Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
--------------------------------------------------------------------------------
-STD Vector Perf Test 02 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:286
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 26 9.9866 ms
- 3.83536 us 3.82892 us 3.85186 us
- 47.3465 ns 10.36 ns 85.6373 ns
-
-Unique Find 50 100 11 10.219 ms
- 9.31415 us 9.294 us 9.35288 us
- 136.606 ns 76.0691 ns 204.992 ns
-
-Unique Find 100 100 4 11.1196 ms
- 27.9158 us 27.8657 us 28.0241 us
- 361.204 ns 203.807 ns 581.343 ns
-
-Unique Find 200 100 2 18.9416 ms
- 94.8942 us 94.7546 us 95.1397 us
- 923.567 ns 584.085 ns 1.32101 us
-
-Unique Find 1000 100 1 364.572 ms
- 3.64712 ms 3.64621 ms 3.64952 ms
- 7.03117 us 3.22424 us 14.8312 us
-
-
-Mem: cowvec_12 (full_): Elements 25 x 16 bytes; CAlloc[ 768 bytes, alloc[balance 1 = 2 - 1]], 1.920000 ratio
-Mem: cowvec_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,568 bytes, alloc[balance 1 = 2 - 1]], 1.960000 ratio
-Mem: cowvec_12 (full_): Elements 100 x 16 bytes; CAlloc[ 3,168 bytes, alloc[balance 1 = 2 - 1]], 1.980000 ratio
-Mem: cowvec_12 (full_): Elements 200 x 16 bytes; CAlloc[ 6,368 bytes, alloc[balance 1 = 2 - 1]], 1.990000 ratio
-Mem: cowvec_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 31,968 bytes, alloc[balance 1 = 2 - 1]], 1.998000 ratio
--------------------------------------------------------------------------------
-COW Vector Perf Test 12 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_cowvector_perf01.cpp:313
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 3 10.5069 ms
- 34.8512 us 34.7742 us 35.0189 us
- 551.761 ns 294.3 ns 931.225 ns
-
-Unique Find 50 100 1 11.7274 ms
- 116.652 us 116.491 us 117.052 us
- 1.1968 us 348.796 ns 2.12363 us
-
-Unique Find 100 100 1 42.362 ms
- 420.924 us 420.491 us 421.544 us
- 2.60965 us 1.95353 us 3.25359 us
-
-Unique Find 200 100 1 156.78 ms
- 1.5621 ms 1.56129 ms 1.56296 ms
- 4.24603 us 3.94813 us 4.6176 us
-
-Unique Find 1000 100 1 3.48784 s
- 34.8407 ms 34.837 ms 34.8487 ms
- 26.8157 us 15.8642 us 52.1366 us
-
-
-===============================================================================
-All tests passed (4953760 assertions in 4 test cases)
-
diff --git a/doc/test/test_hashset_perf01.amd64.log b/doc/test/test_hashset_perf01.amd64.log
deleted file mode 100644
index ac70875..0000000
--- a/doc/test/test_hashset_perf01.amd64.log
+++ /dev/null
@@ -1,117 +0,0 @@
-argc 3, auto-run 0
-Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
-
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-test_hashset_perf01 is a Catch v3.0.0-preview.3 host application.
-Run with -? for options
-
--------------------------------------------------------------------------------
-STD Vector Perf Test 01 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:269
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 60 2.064 ms
- 343.05 ns 342.936 ns 343.582 ns
- 1.07506 ns 0.0932254 ns 2.55378 ns
-
-Seq_List 50 100 39 2.067 ms
- 550.599 ns 546.832 ns 556.485 ns
- 23.629 ns 16.807 ns 38.1638 ns
-
-Seq_List 100 100 23 2.1344 ms
- 908.328 ns 905.844 ns 915.301 ns
- 18.916 ns 2.60158 ns 39.6416 ns
-
-Seq_List 200 100 13 2.1619 ms
- 1.6673 us 1.66284 us 1.67519 us
- 29.6194 ns 19.2921 ns 47.6946 ns
-
-Seq_List 1000 100 3 2.1549 ms
- 7.34832 us 7.30432 us 7.43755 us
- 306.073 ns 179.633 ns 483.433 ns
-
-
-Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
--------------------------------------------------------------------------------
-STD Vector Perf Test 02 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:297
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 24 2.0472 ms
- 852.497 ns 849.73 ns 858.158 ns
- 19.3529 ns 10.6049 ns 30.5871 ns
-
-Unique Find 50 100 9 2.0709 ms
- 2.24281 us 2.22486 us 2.25011 us
- 53.3331 ns 15.7256 ns 94.6539 ns
-
-Unique Find 100 100 3 2.2842 ms
- 6.75987 us 6.7288 us 6.81588 us
- 206.88 ns 129.222 ns 302.069 ns
-
-Unique Find 200 100 1 2.7023 ms
- 26.4917 us 26.4056 us 26.6488 us
- 572.088 ns 274.826 ns 957.771 ns
-
-Unique Find 1000 100 1 84.9358 ms
- 970.189 us 968.48 us 972.371 us
- 9.84229 us 7.6143 us 14.9796 us
-
-
-Mem: stdset_12 (full_): Elements 25 x 16 bytes; CAlloc[ 600 bytes, alloc[balance 25 = 25 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,200 bytes, alloc[balance 50 = 50 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 100 x 16 bytes; CAlloc[ 2,400 bytes, alloc[balance 100 = 100 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 200 x 16 bytes; CAlloc[ 4,800 bytes, alloc[balance 200 = 200 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 24,000 bytes, alloc[balance 1,000 = 1,000 - 0]], 1.500000 ratio
--------------------------------------------------------------------------------
-STD Unordered-Set Perf Test 12 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:324
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 12 2.1552 ms
- 1.81641 us 1.8122 us 1.83224 us
- 36.556 ns 7.89957 ns 84.0457 ns
-
-Unique Find 50 100 7 2.359 ms
- 3.3691 us 3.36238 us 3.39531 us
- 57.3478 ns 6.25338 ns 131.391 ns
-
-Unique Find 100 100 4 2.6164 ms
- 6.49391 us 6.48824 us 6.51029 us
- 45.1634 ns 19.76 ns 97.6575 ns
-
-Unique Find 200 100 2 2.764 ms
- 13.3148 us 13.2758 us 13.4136 us
- 294.994 ns 142.841 ns 589.103 ns
-
-Unique Find 1000 100 1 8.7068 ms
- 86.4785 us 86.267 us 86.9334 us
- 1.50441 us 802.647 ns 2.52316 us
-
-
-===============================================================================
-All tests passed (17601392 assertions in 3 test cases)
-
diff --git a/doc/test/test_hashset_perf01.arm64-raspi4.log b/doc/test/test_hashset_perf01.arm64-raspi4.log
deleted file mode 100644
index a362fa1..0000000
--- a/doc/test/test_hashset_perf01.arm64-raspi4.log
+++ /dev/null
@@ -1,117 +0,0 @@
-argc 3, auto-run 0
-Mem: stdvec_01 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_01 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
-
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-test_hashset_perf01 is a Catch v3.0.0-preview.3 host application.
-Run with -? for options
-
--------------------------------------------------------------------------------
-STD Vector Perf Test 01 - Fill Sequential and List
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:269
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Seq_List 25 100 78 10.101 ms
- 1.29545 us 1.2927 us 1.3001 us
- 17.8456 ns 12.1376 ns 26.3005 ns
-
-Seq_List 50 100 55 10.197 ms
- 1.84654 us 1.84393 us 1.85299 us
- 19.4339 ns 6.01208 ns 34.476 ns
-
-Seq_List 100 100 35 10.1465 ms
- 2.90007 us 2.89447 us 2.9121 us
- 40.0101 ns 23.2939 ns 62.6749 ns
-
-Seq_List 200 100 21 10.0674 ms
- 4.79983 us 4.78373 us 4.8477 us
- 129.534 ns 47.2952 ns 274.068 ns
-
-Seq_List 1000 100 6 11.4552 ms
- 19.1848 us 19.1531 us 19.261 us
- 246.522 ns 143.048 ns 391.5 ns
-
-
-Mem: stdvec_02 (full_): Elements 25 x 16 bytes; CAlloc[ 512 bytes, alloc[balance 1 = 6 - 5]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 50 x 16 bytes; CAlloc[ 1,024 bytes, alloc[balance 1 = 7 - 6]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 100 x 16 bytes; CAlloc[ 2,048 bytes, alloc[balance 1 = 8 - 7]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 200 x 16 bytes; CAlloc[ 4,096 bytes, alloc[balance 1 = 9 - 8]], 1.280000 ratio
-Mem: stdvec_02 (full_): Elements 1,000 x 16 bytes; CAlloc[ 16,384 bytes, alloc[balance 1 = 11 - 10]], 1.024000 ratio
--------------------------------------------------------------------------------
-STD Vector Perf Test 02 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:297
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 27 10.1493 ms
- 3.79413 us 3.78826 us 3.8091 us
- 43.2259 ns 11.7687 ns 77.1456 ns
-
-Unique Find 50 100 11 10.0749 ms
- 9.21581 us 9.19898 us 9.25444 us
- 125.095 ns 72.4751 ns 198.256 ns
-
-Unique Find 100 100 4 10.9788 ms
- 27.6046 us 27.5425 us 27.7244 us
- 412.409 ns 217.397 ns 623.793 ns
-
-Unique Find 200 100 2 18.8014 ms
- 94.2517 us 94.1176 us 94.4959 us
- 894.732 ns 565.305 ns 1.28047 us
-
-Unique Find 1000 100 1 343.853 ms
- 3.43966 ms 3.43877 ms 3.44153 ms
- 6.31207 us 3.50588 us 12.5288 us
-
-
-Mem: stdset_12 (full_): Elements 25 x 16 bytes; CAlloc[ 600 bytes, alloc[balance 25 = 25 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 50 x 16 bytes; CAlloc[ 1,200 bytes, alloc[balance 50 = 50 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 100 x 16 bytes; CAlloc[ 2,400 bytes, alloc[balance 100 = 100 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 200 x 16 bytes; CAlloc[ 4,800 bytes, alloc[balance 200 = 200 - 0]], 1.500000 ratio
-Mem: stdset_12 (full_): Elements 1,000 x 16 bytes; CAlloc[ 24,000 bytes, alloc[balance 1,000 = 1,000 - 0]], 1.500000 ratio
--------------------------------------------------------------------------------
-STD Unordered-Set Perf Test 12 - Fill Unique and Find-Each
--------------------------------------------------------------------------------
-/test/test_hashset_perf01.cpp:324
-...............................................................................
-
-benchmark name samples iterations estimated
- mean low mean high mean
- std dev low std dev high std dev
--------------------------------------------------------------------------------
-Unique Find 25 100 14 10.4202 ms
- 7.47964 us 7.46322 us 7.51494 us
- 118.007 ns 69.3892 ns 186.392 ns
-
-Unique Find 50 100 8 10.6464 ms
- 13.284 us 13.248 us 13.3487 us
- 239.185 ns 152.993 ns 359.936 ns
-
-Unique Find 100 100 4 10.7904 ms
- 27.1248 us 27.0621 us 27.2544 us
- 441.752 ns 252.981 ns 695.429 ns
-
-Unique Find 200 100 2 11.4072 ms
- 57.1536 us 56.7599 us 58.7903 us
- 3.51188 us 669.03 ns 8.19054 us
-
-Unique Find 1000 100 1 33.7565 ms
- 338.059 us 337.468 us 338.85 us
- 3.47204 us 2.71059 us 4.28299 us
-
-
-===============================================================================
-All tests passed (5198408 assertions in 3 test cases)
-
diff --git a/include/jau/counting_allocator.hpp b/include/jau/counting_allocator.hpp
index 5ec5ced..3cada17 100644
--- a/include/jau/counting_allocator.hpp
+++ b/include/jau/counting_allocator.hpp
@@ -33,6 +33,13 @@
namespace jau {
+/**
+ * Performance counter std::allocator specialization.
+ * <p>
+ * Not overriding deprecated (C++17) and removed (C++20)
+ * methods: address(), max_size(), construct() and destroy().
+ * </p>
+ */
template <class T>
struct counting_allocator : public std::allocator<T>
{
diff --git a/include/jau/cow_darray.hpp b/include/jau/cow_darray.hpp
new file mode 100644
index 0000000..cfcae18
--- /dev/null
+++ b/include/jau/cow_darray.hpp
@@ -0,0 +1,817 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * 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 <cstring>
+#include <string>
+#include <cstdint>
+#include <atomic>
+#include <memory>
+#include <mutex>
+#include <condition_variable>
+#include <algorithm>
+
+#include <jau/debug.hpp>
+#include <jau/darray.hpp>
+#include <jau/basic_types.hpp>
+#include <jau/ordered_atomic.hpp>
+#include <jau/cow_iterator.hpp>
+
+namespace jau {
+
+ /**
+ * Implementation of a Copy-On-Write (CoW) using jau::darray as the underlying storage,
+ * exposing <i>lock-free</i> read operations using SC-DRF atomic synchronization.
+ * <p>
+ * The store is owned using a shared reference to the data structure,
+ * allowing its replacement on Copy-On-Write (CoW).
+ * </p>
+ * <p>
+ * Writing to the store utilizes a mutex lock to avoid data races
+ * on the instances' write operations only, leaving read operations <i>lock-free</i>.<br>
+ * Write operations replace the store reference with a new instance using
+ * jau::sc_atomic_critical to synchronize with read operations.
+ * </p>
+ * <p>
+ * Reading from the store is <i>lock-free</i> and accesses the store reference using
+ * jau::sc_atomic_critical to synchronizing with write operations.
+ * </p>
+ * <p>
+ * Immutable storage const_iterators are supported via jau::cow_ro_iterator,
+ * which are constructed <i>lock-free</i>.<br>
+ * jau::cow_ro_iterator hold a snapshot retrieved via jau::cow_darray::get_snapshot()
+ * until its destruction.
+ * </p>
+ * <p>
+ * Mutable storage iterators are supported via jau::cow_rw_iterator,
+ * which are constructed holding the write-lock.<br>
+ * jau::cow_rw_iterator hold a new store copy via jau::cow_darray::copy_store(),
+ * which replaces the current store via jau::cow_darray::set_store() at destruction.
+ * </p>
+ * <p>
+ * Both, jau::cow_ro_iterator and jau::cor_rw_iterator are harmonized
+ * to work with jau::darray::const_iterator and jau::darray::iterator
+ * for all iterator based operations.
+ * </p>
+ * <p>
+ * Index operation via ::operator[](size_t) or ::at(size_t) are not supported for now,
+ * 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().
+ * </p>
+ * <p>
+ * 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().<br>
+ * See example in jau::cow_darray::set_store()
+ * </p>
+ *
+ * </p>
+ * See also:
+ * <pre>
+ * - Sequentially Consistent (SC) ordering or SC-DRF (data race free) <https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering>
+ * - std::memory_order <https://en.cppreference.com/w/cpp/atomic/memory_order>
+ * </pre>
+ */
+ template <typename Value_type, typename Alloc_type = std::allocator<Value_type>, typename Size_type = jau::nsize_t>
+ class cow_darray
+ {
+ public:
+ typedef darray<Value_type, Alloc_type, Size_type> storage_t;
+ typedef std::shared_ptr<storage_t> storage_ref_t;
+
+ /**
+ * Immutable, read-only const_iterator, lock-free,
+ * holding the current shared store reference until destruction.
+ * <p>
+ * Using jau::cow_darray::get_snapshot() at construction.
+ * </p>
+ */
+ typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator;
+
+ /**
+ * Mutable, read-write iterator, holding the write-lock and a store copy until destruction.
+ * <p>
+ * Using jau::cow_darray::get_write_mutex(), jau::cow_darray::copy_store() at construction<br>
+ * and jau::cow_darray::set_store() at destruction.
+ * </p>
+ */
+ typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_darray> iterator;
+
+ /** Default growth factor using the golden ratio 1.618 */
+ inline static const float DEFAULT_GROWTH_FACTOR = 1.618f;
+
+ private:
+ storage_ref_t store_ref;
+ sc_atomic_bool sync_atomic;
+ 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<storage_t>()), sync_atomic(false) {}
+
+ /**
+ * 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 Alloc_type
+ */
+ constexpr explicit cow_darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type())
+ : store_ref(std::make_shared<storage_t>(capacity, growth_factor, alloc)), sync_atomic(false) {}
+
+ // conversion ctor on storage_t elements
+
+ constexpr cow_darray(const storage_t& x)
+ : store_ref(std::make_shared<storage_t>(x)), sync_atomic(false) {}
+
+ constexpr explicit cow_darray(const storage_t& x, const float growth_factor, const Alloc_type& alloc)
+ : store_ref(std::make_shared<storage_t>(x, growth_factor, alloc)), sync_atomic(false) {}
+
+ constexpr cow_darray(storage_t && x) noexcept
+ : store_ref(std::make_shared<storage_t>(std::move(x))), sync_atomic(false) {}
+
+ constexpr explicit cow_darray(storage_t && x, const float growth_factor, const Alloc_type& alloc) noexcept
+ : store_ref(std::make_shared<storage_t>(std::move(x), growth_factor, alloc)), sync_atomic(false) {}
+
+ // copy_ctor on cow_darray elements
+
+ /**
+ * Creates a new instance, copying all elements from the given array.<br>
+ * 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 cow_darray(const cow_darray& x)
+ : sync_atomic(false) {
+ storage_ref_t x_store_ref;
+ {
+ sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic );
+ x_store_ref = x.store_ref;
+ }
+ store_ref = std::make_shared<storage_t>( *x_store_ref );
+ }
+
+ /**
+ * Creates a new instance, copying all elements from the given array.<br>
+ * 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 Alloc_type instance
+ */
+ constexpr explicit cow_darray(const cow_darray& x, const float growth_factor, const Alloc_type& alloc)
+ : sync_atomic(false) {
+ storage_ref_t x_store_ref;
+ {
+ sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic );
+ x_store_ref = x.store_ref;
+ }
+ store_ref = std::make_shared<storage_t>( *x_store_ref, growth_factor, alloc );
+ }
+
+ /**
+ * Creates a new instance with custom initial storage capacity, copying all elements from the given array.<br>
+ * Size will equal the given array.
+ * <p>
+ * Calculated safe capacity is: <code>std::max<Size_type>(x.size(), _capacity)</code>
+ * </p>
+ * @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 Alloc_type instance
+ */
+ constexpr explicit cow_darray(const cow_darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc)
+ : sync_atomic(false) {
+ storage_ref_t x_store_ref;
+ {
+ sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic );
+ x_store_ref = x.store_ref;
+ }
+ store_ref = std::make_shared<storage_t>( *x_store_ref, _capacity, growth_factor, alloc );
+ }
+
+ // move_ctor on cow_darray elements
+
+ constexpr cow_darray(cow_darray && x) noexcept {
+ // swap store_ref
+ store_ref = std::move(x.store_ref);
+ x.store_ref = nullptr;
+ // not really necessary
+ sync_atomic = std::move(x.sync_atomic);
+ }
+
+ // 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).<br>
+ * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>.
+ * <p>
+ * Calculated safe capacity is: <code>std::max<Size_type>(Size_type(last-first), _capacity)</code>
+ * </p>
+ * @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 Alloc_type instance
+ */
+ constexpr cow_darray(const Size_type _capacity, const_iterator first, const_iterator last,
+ const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type())
+ : store_ref(std::make_shared<storage_t>(_capacity, first.underling(), last.underling(), growth_factor, alloc)), sync_atomic(false)
+ { }
+
+ /**
+ * Creates a new instance with custom initial storage capacity,
+ * copying all elements from the given template input-iterator Value_type range [first, last).<br>
+ * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>.
+ * <p>
+ * Calculated safe capacity is: <code>std::max<Size_type>(Size_type(last-first), _capacity)</code>
+ * </p>
+ * @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 Alloc_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 Alloc_type& alloc = Alloc_type())
+ : store_ref(std::make_shared<storage_t>(_capacity, first, last, growth_factor, alloc)), sync_atomic(false)
+ { }
+
+
+ ~cow_darray() noexcept { }
+
+ // cow_vector features
+
+ /**
+ * Returns this instances' recursive write mutex, allowing user to
+ * implement more complex mutable write operations.
+ * <p>
+ * See example in jau::cow_darray::set_store()
+ * </p>
+ *
+ * @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.
+ * <p>
+ * See example in jau::cow_darray::set_store()
+ * </p>
+ * <p>
+ * This special operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * @see jau::cow_darray::get_write_mutex()
+ * @see jau::cow_darray::copy_store()
+ * @see jau::cow_darray::set_store()
+ */
+ storage_ref_t copy_store() {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ return std::make_shared<storage_t>( *store_ref );
+ }
+
+ /**
+ * Special case facility allowing the user to replace the current store
+ * with the given value, potentially acquired via jau::cow_darray::copy_store()
+ * and mutated while holding the jau::cow_darray::get_write_mutex() lock.
+ * <p>
+ * This is a move operation, i.e. the given new_store_ref is invalid on the caller side
+ * after this operation. <br>
+ * User shall pass the store via std::move()
+ * <pre>
+ * cow_darray<std::shared_ptr<Thing>> list;
+ * ...
+ * {
+ * const std::lock_guard<std::recursive_mutex> lock(list.get_write_mutex());
+ * std::shared_ptr<std::vector<std::shared_ptr<Thing>>> snapshot = list.copy_store();
+ * ...
+ * some fancy mutation
+ * ...
+ * list.set_store(std::move(snapshot));
+ * }
+ * </pre>
+ * </p>
+ * @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()
+ */
+ constexpr void set_store(storage_ref_t && new_store_ref) noexcept {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move( new_store_ref );
+ }
+
+ /**
+ * Returns the current snapshot of the underlying shared std::vector<T> reference.
+ * <p>
+ * Note that this snapshot will be outdated by the next (concurrent) write operation.<br>
+ * The returned referenced vector is still valid and not mutated,
+ * but does not represent the current content of this cow_darray instance.
+ * </p>
+ * <p>
+ * This read operation is <i>lock-free</i>.
+ * </p>
+ * @see jau::for_each_cow
+ */
+ constexpr storage_ref_t get_snapshot() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref;
+ }
+
+ // const_iterator, non mutable, read-only
+
+ constexpr const_iterator begin() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cbegin());
+ }
+
+ constexpr const_iterator cbegin() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cbegin());
+ }
+
+ constexpr const_iterator end() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cend());
+ }
+
+ constexpr const_iterator cend() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cend());
+ }
+
+ // iterator, mutable, read-write
+
+ constexpr iterator begin() noexcept {
+ return iterator(*this, [](storage_ref_t& new_store) -> iterator { return new_store->begin(); } );
+ }
+
+ constexpr iterator end() noexcept {
+ return iterator(*this, [](storage_ref_t& new_store) -> iterator { return new_store->end(); } );
+ }
+
+ // read access
+
+ const Alloc_type& get_allocator_ref() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref->get_allocator_ref();
+ }
+
+ Alloc_type get_allocator() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref->get_allocator();
+ }
+
+ constexpr Size_type capacity() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref->capacity();
+ }
+
+ /**
+ * Like std::vector::empty().
+ * <p>
+ * This read operation is <i>lock-free</i>.
+ * </p>
+ */
+ constexpr bool empty() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref->empty();
+ }
+
+ /**
+ * Like std::vector::size().
+ * <p>
+ * This read operation is <i>lock-free</i>.
+ * </p>
+ */
+ constexpr Size_type size() const noexcept {
+ sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic );
+ return store_ref->size();
+ }
+
+ // write access
+
+ /**
+ * Like std::vector::reserve(), increases this instance's capacity to <code>new_capacity</code>.
+ * <p>
+ * Only creates a new storage and invalidates iterators if <code>new_capacity</code>
+ * is greater than the current jau::darray::capacity().
+ * </p>
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ void reserve(Size_type new_capacity) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ if( new_capacity > old_store_ref->capacity() ) {
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_capacity,
+ old_store_ref->growth_factor(),
+ old_store_ref->get_allocator_ref() );
+ sc_atomic_critical sync( sync_atomic );
+ store_ref = std::move(new_store_ref);
+ }
+ }
+
+ /**
+ * Like std::vector::operator=(&), assignment, but copying from the underling jau::darray
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ cow_darray& operator=(const storage_t& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( x );
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ return *this;
+ }
+
+ /**
+ * Like std::vector::operator=(&&), move, but taking the underling jau::darray
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ cow_darray& operator=(storage_t&& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( std::move(x) );
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ return *this;
+ }
+
+ /**
+ * Like std::vector::operator=(&), assignment
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ cow_darray& operator=(const cow_darray& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t x_store_ref;
+ {
+ sc_atomic_critical sync_x( const_cast<cow_darray *>(&x)->sync_atomic );
+ x_store_ref = x.store_ref;
+ }
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref );
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ return *this;
+ }
+
+ /**
+ * Like std::vector::operator=(&&), move.
+ * <p>
+ * This write operation uses a mutex lock and is blocking both cow_vector instance's write operations.
+ * </p>
+ */
+ cow_darray& operator=(cow_darray&& x) {
+ std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object
+ std::unique_lock<std::recursive_mutex> 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);
+ // swap store_ref
+ store_ref = std::move(x.store_ref);
+ x.store_ref = nullptr;
+ }
+ return *this;
+ }
+
+ /**
+ * Like std::vector::clear(), but ending with zero capacity.
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations.
+ * </p>
+ */
+ void clear() noexcept {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>();
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ }
+
+ /**
+ * Like std::vector::swap().
+ * <p>
+ * This write operation uses a mutex lock and is blocking both cow_darray instance's write operations.
+ * </p>
+ */
+ void swap(cow_darray& x) noexcept {
+ std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object
+ std::unique_lock<std::recursive_mutex> 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().
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ void pop_back() noexcept {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ if( !old_store_ref->empty() ) {
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( old_store_ref->capacity(),
+ old_store_ref->cbegin(),
+ old_store_ref->cend()-1,
+ old_store_ref->growth_factor(),
+ old_store_ref->get_allocator_ref() );
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ }
+ }
+
+ /**
+ * Like std::vector::push_back(), copy
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * @param x the value to be added at the tail.
+ */
+ void push_back(const Value_type& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ if( old_store_ref->capacity_reached() ) {
+ // grow and swap all refs
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->grow_capacity(),
+ old_store_ref->growth_factor(),
+ old_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
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ */
+ void push_back(Value_type&& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ if( old_store_ref->capacity_reached() ) {
+ // grow and swap all refs
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->grow_capacity(),
+ old_store_ref->growth_factor(),
+ old_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::push_back(), but appends the whole Value_type range [first, last).
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * @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 void push_back( InputIt first, InputIt last ) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ const Size_type new_size_ = old_store_ref->size() + Size_type(last - first);
+
+ if( new_size_ > old_store_ref->capacity() ) {
+ // grow and swap all refs
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_size_,
+ old_store_ref->growth_factor(),
+ old_store_ref->get_allocator_ref() );
+ 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 std::vector::push_back(), but appends the whole Value_type range [first, last).
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * @param first first const_iterator to range of Value_type [first, last)
+ * @param last last const_iterator to range of Value_type [first, last)
+ */
+ constexpr void push_back( const_iterator first, const_iterator last ) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t old_store_ref = store_ref;
+ const Size_type new_size_ = old_store_ref->size() + Size_type(last - first);
+
+ if( new_size_ > old_store_ref->capacity() ) {
+ // grow and swap all refs
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, new_size_,
+ old_store_ref->growth_factor(),
+ old_store_ref->get_allocator_ref() );
+ store_ref->push_back( first.underling(), last.underling() );
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ } else {
+ // just append ..
+ store_ref->push_back( first.underling(), last.underling() );
+ }
+ }
+
+ /**
+ * 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.
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * <p>
+ * Examples
+ * <pre>
+ * static jau::cow_darray<Thing>::equal_comparator thingEqComparator =
+ * [](const Thing &a, const Thing &b) -> bool { return a == b; };
+ * ...
+ * jau::cow_darray<Thing> list;
+ *
+ * bool added = list.push_back_unique(new_element, thingEqComparator);
+ * ...
+ * cow_darray<std::shared_ptr<Thing>> listOfRefs;
+ * bool added = listOfRefs.push_back_unique(new_element,
+ * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; });
+ * </pre>
+ * </p>
+ * @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
+ */
+ bool push_back_unique(const Value_type& x, equal_comparator comparator) {
+ const std::lock_guard<std::recursive_mutex> 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.
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * <p>
+ * Examples
+ * <pre>
+ * cow_darray<Thing> list;
+ * int count = list.erase_matching(element, true,
+ * [](const Thing &a, const Thing &b) -> bool { return a == b; });
+ * ...
+ * static jau::cow_darray<Thing>::equal_comparator thingRefEqComparator =
+ * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; };
+ * ...
+ * cow_darray<std::shared_ptr<Thing>> listOfRefs;
+ * int count = listOfRefs.erase_matching(element, false, thingRefEqComparator);
+ * </pre>
+ * </p>
+ * @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
+ */
+ int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) {
+ int count = 0;
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref );
+ for(auto it = new_store_ref->begin(); it != new_store_ref->end(); ) {
+ if( comparator( *it, x ) ) {
+ it = new_store_ref->erase(it);
+ ++count;
+ if( !all_matching ) {
+ break;
+ }
+ } else {
+ ++it;
+ }
+ }
+ if( 0 < count ) { // mutated new_store_ref?
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ } // else throw away new_store_ref
+ return count;
+ }
+
+ /**
+ * Thread safe Value_type copy assignment to Value_type at given position with bounds checking.
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * <p>
+ * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end().
+ * </p>
+ * @param i the position within this store
+ * @param x the value to be assigned to the object at the given position
+ */
+ void put(size_t i, const Value_type& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref );
+ new_store_ref->at(i) = x;
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ }
+
+ /**
+ * Thread safe Value_type move assignment to Value_type at given position with bounds checking.
+ * <p>
+ * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * </p>
+ * <p>
+ * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end().
+ * </p>
+ * @param i the position within this store
+ * @param x the value to be assigned to the object at the given position
+ */
+ void put(size_t i, Value_type&& x) {
+ const std::lock_guard<std::recursive_mutex> lock(mtx_write);
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref );
+ new_store_ref->at(i) = std::move(x);
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
+ }
+ };
+
+} /* namespace jau */
+
+#endif /* JAU_COW_DARRAY_HPP_ */
diff --git a/include/jau/cow_iterator.hpp b/include/jau/cow_iterator.hpp
new file mode 100644
index 0000000..8ebd9c1
--- /dev/null
+++ b/include/jau/cow_iterator.hpp
@@ -0,0 +1,254 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * 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_ITERATOR_HPP_
+#define JAU_COW_ITERATOR_HPP_
+
+#include <cstddef>
+#include <mutex>
+
+namespace jau {
+
+ /**
+ * Implementation of a Copy-On-Write (CoW) read-only iterator for immutable Value_type,
+ * holding the shared Value_type& of the current CoW storage until destruction.
+ */
+ template <typename Value_type, typename Storage_type, typename Storage_ref_type>
+ class cow_ro_iterator {
+
+ private:
+ Storage_ref_type store_holder_;
+ typename Storage_type::const_iterator iterator_;
+
+ public:
+ constexpr cow_ro_iterator(Storage_ref_type store, typename Storage_type::const_iterator iter)
+ : store_holder_(store), iterator_(iter) {}
+
+ constexpr explicit cow_ro_iterator(const cow_ro_iterator& o) noexcept
+ : store_holder_(o.store_holder_), iterator_(o.iterator_) {}
+
+ /**
+ * Returns a copy of the underlying storage const_iterator.
+ */
+ typename Storage_type::const_iterator underling() const noexcept { return iterator_; };
+
+ // Multipass guarantee equality
+
+ constexpr bool operator==(const cow_ro_iterator& rhs) const noexcept {
+ if( this == &rhs ) {
+ return true;
+ }
+ // only testing identity of pointer, OK for Multipass guarantee
+ return store_holder_ == rhs.store_holder_ &&
+ iterator_ == rhs.iterator_;
+ }
+ constexpr bool operator!=(const cow_ro_iterator& rhs) const noexcept
+ { return !(*this == rhs); }
+
+ // Forward iterator requirements
+
+ constexpr const Value_type& operator*() const noexcept
+ { return *iterator_; }
+
+ constexpr const Value_type* operator->() const noexcept
+ { return iterator_; }
+
+ /** Pre-increment; Well performing, return *this. */
+ constexpr cow_ro_iterator& operator++() noexcept {
+ ++iterator_;
+ return *this;
+ }
+
+ /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_ro_iterator& operator++(int) noexcept
+ { return cow_ro_iterator(store_holder_, iterator_++); }
+
+ // Bidirectional iterator requirements
+
+ /** Pre-decrement; Well performing, return *this. */
+ constexpr cow_ro_iterator& operator--() noexcept {
+ --iterator_;
+ return *this;
+ }
+
+ /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_ro_iterator& operator--(int) noexcept
+ { return cow_iterator(store_holder_, iterator_--); }
+
+ // Random access iterator requirements
+
+ /** Subscript of 'element_index', returning immutable Value_type reference. */
+ constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept
+ { return iterator_[i]; }
+
+ /** Addition-assignment of 'element_count'; Well performing, return *this. */
+ constexpr cow_ro_iterator& operator+=(std::ptrdiff_t i) noexcept
+ { iterator_ += i; return *this; }
+
+ /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_ro_iterator operator+(std::ptrdiff_t rhs) const noexcept
+ { return cow_iterator(store_holder_, iterator_ + rhs); }
+
+ /** Subtraction-assignment of 'element_count'; Well performing, return *this. */
+ constexpr cow_ro_iterator& operator-=(std::ptrdiff_t i) noexcept
+ { iterator_ -= i; return *this; }
+
+ /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_ro_iterator operator-(std::ptrdiff_t rhs) const noexcept
+ { return cow_iterator(store_holder_, iterator_ - rhs); }
+
+ // Distance or element count, binary subtraction of two iterator.
+
+ /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */
+ constexpr std::ptrdiff_t operator-(const cow_ro_iterator& rhs) const noexcept
+ { return iterator_ - rhs.iterator_; }
+ };
+
+ /**
+ * Implementation of a Copy-On-Write (CoW) read-write iterator for mutable Value_type,
+ * holding the write lock, a new copy of the CoW storage and a Value_type& of the CoW container itself.
+ * <p>
+ * At destruction, the mutated local storage will replace the
+ * storage in the CoW container and the lock will be released.
+ * </p>
+ */
+ template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename CoW_container>
+ class cow_rw_iterator {
+
+ private:
+ CoW_container& cow_parent_;
+ const std::lock_guard<std::recursive_mutex> lock_;
+ Storage_ref_type new_store_;
+ typename Storage_type::iterator iterator_;
+
+ constexpr explicit cow_rw_iterator(CoW_container& cow_parent, Storage_ref_type& store, typename Storage_type::iterator iter) noexcept
+ : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(store), iterator_(iter) {}
+
+ public:
+ constexpr cow_rw_iterator(CoW_container& cow_parent, typename Storage_type::iterator (*get_iterator)(Storage_ref_type&))
+ : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(cow_parent.copy_store()), iterator_(get_iterator(new_store_)) {}
+
+#if __cplusplus > 201703L
+ constexpr ~cow_rw_iterator() noexcept
+#else
+ ~cow_rw_iterator() noexcept
+#endif
+ {
+ cow_parent_.set_store(std::move(new_store_));
+ }
+
+ /**
+ * Returns a copy of the underlying storage iterator.
+ */
+ typename Storage_type::iterator underling() const noexcept { return iterator_; };
+
+ // Multipass guarantee equality
+
+ constexpr bool operator==(const cow_rw_iterator& rhs) const noexcept {
+ if( this == &rhs ) {
+ return true;
+ }
+ // only testing identity of pointer, OK for Multipass guarantee
+ return &cow_parent_ == &rhs.cow_parent_ &&
+ new_store_ == rhs.new_store_ &&
+ iterator_ == rhs.iterator_;
+ }
+ constexpr bool operator!=(const cow_rw_iterator& rhs) const noexcept
+ { return !(*this == rhs); }
+
+ // Forward iterator requirements
+
+ constexpr const Value_type& operator*() const noexcept
+ { return *iterator_; }
+
+ constexpr const Value_type* operator->() const noexcept
+ { return iterator_; }
+
+ constexpr Value_type& operator*() noexcept
+ { return *iterator_; }
+
+ constexpr Value_type* operator->() noexcept
+ { return iterator_; }
+
+ /** Pre-increment; Well performing, return *this. */
+ constexpr cow_rw_iterator& operator++() noexcept {
+ ++iterator_;
+ return *this;
+ }
+
+ /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_rw_iterator& operator++(int) noexcept
+ { return cow_rw_iterator(cow_parent_, new_store_, iterator_++); }
+
+ // Bidirectional iterator requirements
+
+ /** Pre-decrement; Well performing, return *this. */
+ constexpr cow_rw_iterator& operator--() noexcept {
+ --iterator_;
+ return *this;
+ }
+
+ /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_rw_iterator& operator--(int) noexcept
+ { return cow_rw_iterator(cow_parent_, new_store_, iterator_--); }
+
+ // Random access iterator requirements
+
+ /** Subscript of 'element_index', returning immutable Value_type reference. */
+ constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept
+ { return iterator_[i]; }
+
+ /** Subscript of 'element_index', returning mutable Value_type reference. */
+ constexpr Value_type& operator[](std::ptrdiff_t i) noexcept
+ { return iterator_[i]; }
+
+ /** Addition-assignment of 'element_count'; Well performing, return *this. */
+ constexpr cow_rw_iterator& operator+=(std::ptrdiff_t i) noexcept
+ { iterator_ += i; return *this; }
+
+ /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_rw_iterator operator+(std::ptrdiff_t rhs) const noexcept
+ { return cow_rw_iterator(cow_parent_, new_store_, iterator_ + rhs); }
+
+ /** Subtraction-assignment of 'element_count'; Well performing, return *this. */
+ constexpr cow_rw_iterator& operator-=(std::ptrdiff_t i) noexcept
+ { iterator_ -= i; return *this; }
+
+ /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+ constexpr cow_rw_iterator operator-(std::ptrdiff_t rhs) const noexcept
+ { return cow_rw_iterator(cow_parent_, new_store_, iterator_ - rhs); }
+
+ // constexpr const cow_rw_iterator& base() const noexcept
+ // { return iterator_; }
+
+ // Distance or element count, binary subtraction of two iterator.
+
+ /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */
+ constexpr std::ptrdiff_t operator-(const cow_rw_iterator& rhs) const noexcept
+ { return iterator_ - rhs.iterator_; }
+ };
+
+} /* namespace jau */
+
+#endif /* JAU_COW_ITERATOR_HPP_ */
diff --git a/include/jau/cow_vector.hpp b/include/jau/cow_vector.hpp
index 251e130..cc35ffa 100644
--- a/include/jau/cow_vector.hpp
+++ b/include/jau/cow_vector.hpp
@@ -39,15 +39,15 @@
#include <jau/debug.hpp>
#include <jau/basic_types.hpp>
#include <jau/ordered_atomic.hpp>
-
+#include <jau/cow_iterator.hpp>
namespace jau {
/**
- * Implementation of a Copy-On-Write (CoW) vector,
+ * Implementation of a Copy-On-Write (CoW) using std::vector as the underlying storage,
* exposing <i>lock-free</i> read operations using SC-DRF atomic synchronization.
* <p>
- * The vector's store is owned using a reference to the data structure,
+ * The vector's store is owned using a shared reference to the data structure,
* allowing its replacement on Copy-On-Write (CoW).
* </p>
* <p>
@@ -61,10 +61,22 @@ namespace jau {
* jau::sc_atomic_critical to synchronizing with write operations.
* </p>
* <p>
- * Naturally iterators are not supported directly,
- * otherwise we would need to copy the store to iterate through.<br>
- * However, one can utilize iteration using the shared snapshot
- * of the underlying vector store via jau::cow_vector::get_snapshot() for read operations.
+ * Immutable storage const_iterators are supported via jau::cow_ro_iterator,
+ * which are constructed <i>lock-free</i>.<br>
+ * jau::cow_ro_iterator hold a snapshot retrieved via jau::cow_vector::get_snapshot()
+ * until its destruction.
+ * </p>
+ * <p>
+ * Mutable storage iterators are supported via jau::cow_rw_iterator,
+ * which are constructed holding the write-lock.<br>
+ * jau::cow_rw_iterator hold a new store copy via jau::cow_vector::copy_store(),
+ * which replaces the current store via jau::cow_vector::set_store() at destruction.
+ * </p>
+ * <p>
+ * Index operation via ::operator[](size_t) or ::at(size_t) are not supported for now,
+ * since they would be only valid if Value_type itself is a std::shared_ptr
+ * and hence prohibit the destruction of the object if mutating the storage,
+ * e.g. via jau::cow_vector::push_back().
* </p>
* <p>
* Custom mutable write operations are also supported via
@@ -76,54 +88,78 @@ namespace jau {
* - Sequentially Consistent (SC) ordering or SC-DRF (data race free) <https://en.cppreference.com/w/cpp/atomic/memory_order#Sequentially-consistent_ordering>
* - std::memory_order <https://en.cppreference.com/w/cpp/atomic/memory_order>
* </pre>
+ * \deprecated { jau::cow_vector will be retired, use jau::cow_darray and potentially jau::darray. }
*/
- template <typename Value_type, typename Alloc_type = std::allocator<Value_type>> class cow_vector {
- private:
- typedef std::vector<Value_type, Alloc_type> vector_t;
- typedef std::shared_ptr<vector_t> vector_ref;
+ template <typename Value_type, typename Alloc_type = std::allocator<Value_type>>
+ class cow_vector
+ {
+ public:
+ typedef std::vector<Value_type, Alloc_type> storage_t;
+ typedef std::shared_ptr<storage_t> storage_ref_t;
+
+ /**
+ * Immutable, read-only const_iterator, lock-free,
+ * holding the current shared store reference until destruction.
+ * <p>
+ * Using jau::cow_vector::get_snapshot() at construction.
+ * </p>
+ */
+ typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator;
+
+ /**
+ * Mutable, read-write iterator, holding the write-lock and a store copy until destruction.
+ * <p>
+ * Using jau::cow_vector::get_write_mutex(), jau::cow_vector::copy_store() at construction<br>
+ * and jau::cow_vector::set_store() at destruction.
+ * </p>
+ */
+ typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_vector> iterator;
- vector_ref store_ref;
+ private:
+ storage_ref_t store_ref;
sc_atomic_bool sync_atomic;
std::recursive_mutex mtx_write;
public:
// ctor
- cow_vector() noexcept
- : store_ref( std::make_shared<vector_t>() ), sync_atomic(false) {}
+ constexpr cow_vector() noexcept
+ : store_ref( std::make_shared<storage_t>() ), sync_atomic(false) {}
- explicit cow_vector(const Alloc_type & a) noexcept
- : store_ref( std::make_shared<vector_t>(a) ), sync_atomic(false) { }
+ constexpr explicit cow_vector(const Alloc_type & a) noexcept
+ : store_ref( std::make_shared<storage_t>(a) ), sync_atomic(false) { }
- explicit cow_vector(size_t n, const Alloc_type& a = Alloc_type())
- : store_ref( std::make_shared<vector_t>(n, a) ), sync_atomic(false) { }
+ constexpr explicit cow_vector(size_t n, const Alloc_type& a = Alloc_type())
+ : store_ref( std::make_shared<storage_t>(n, a) ), sync_atomic(false) { }
- cow_vector(size_t n, const Value_type& value, const Alloc_type& a = Alloc_type())
- : store_ref( std::make_shared<vector_t>(n, value, a) ), sync_atomic(false) { }
+ constexpr cow_vector(size_t n, const Value_type& value, const Alloc_type& a = Alloc_type())
+ : store_ref( std::make_shared<storage_t>(n, value, a) ), sync_atomic(false) { }
- cow_vector(const cow_vector& x)
+ constexpr cow_vector(const cow_vector& x)
: sync_atomic(false) {
- vector_ref x_store_ref;
+ storage_ref_t x_store_ref;
{
sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic );
x_store_ref = x.store_ref;
}
- store_ref = std::make_shared<vector_t>( *x_store_ref, x_store_ref->get_allocator() );
+ store_ref = std::make_shared<storage_t>( *x_store_ref, x_store_ref->get_allocator() );
}
- explicit cow_vector(const vector_t& x)
- : store_ref( std::make_shared<vector_t>(x, x->get_allocator()) ), sync_atomic(false) { }
+ constexpr explicit cow_vector(const storage_t& x)
+ : store_ref( std::make_shared<storage_t>(x, x->get_allocator()) ), sync_atomic(false) { }
- cow_vector(cow_vector && x) noexcept {
+ constexpr cow_vector(cow_vector && x) noexcept {
// swap store_ref
- store_ref = x.store_ref;
+ store_ref = std::move(x.store_ref);
x.store_ref = nullptr;
// not really necessary
- sync_atomic = x.sync_atomic;
+ sync_atomic = std::move(x.sync_atomic);
}
~cow_vector() noexcept { }
+ // cow_vector features
+
/**
* Returns this instances' recursive write mutex, allowing user to
* implement more complex mutable write operations.
@@ -135,7 +171,7 @@ namespace jau {
* @see jau::cow_vector::copy_store()
* @see jau::cow_vector::set_store()
*/
- std::recursive_mutex & get_write_mutex() { return mtx_write; }
+ constexpr std::recursive_mutex & get_write_mutex() noexcept { return mtx_write; }
/**
* Returns a new shared_ptr copy of the underlying store,
@@ -150,9 +186,9 @@ namespace jau {
* @see jau::cow_vector::copy_store()
* @see jau::cow_vector::set_store()
*/
- std::shared_ptr<std::vector<Value_type>> copy_store() noexcept {
+ storage_ref_t copy_store() {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- return std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ return std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
}
/**
@@ -182,14 +218,12 @@ namespace jau {
* @see jau::cow_vector::copy_store()
* @see jau::cow_vector::set_store()
*/
- void set_store(std::shared_ptr<std::vector<Value_type>> && new_store_ref) noexcept {
+ constexpr void set_store(storage_ref_t && new_store_ref) noexcept {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
sc_atomic_critical sync(sync_atomic);
- store_ref = new_store_ref;
+ store_ref = std::move( new_store_ref );
}
- // read access
-
/**
* Returns the current snapshot of the underlying shared std::vector<T> reference.
* <p>
@@ -202,17 +236,47 @@ namespace jau {
* </p>
* @see jau::for_each_cow
*/
- std::shared_ptr<std::vector<Value_type>> get_snapshot() const noexcept {
+ constexpr storage_ref_t get_snapshot() const noexcept {
sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
return store_ref;
}
+ // const_iterator, non mutable, read-only
+
+ constexpr const_iterator begin() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cbegin());
+ }
+
+ constexpr const_iterator cbegin() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cbegin());
+ }
+
+ constexpr const_iterator end() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cend());
+ }
+
+ constexpr const_iterator cend() const noexcept {
+ return const_iterator(get_snapshot(), store_ref->cend());
+ }
+
+ // iterator, mutable, read-write
+
+ constexpr iterator begin() noexcept {
+ return iterator(*this, store_ref->begin());
+ }
+
+ constexpr iterator end() noexcept {
+ return iterator(*this, store_ref->end());
+ }
+
+ // read access
+
Alloc_type get_allocator() const noexcept {
sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
return store_ref->get_allocator();
}
- std::size_t capacity() const noexcept {
+ constexpr std::size_t capacity() const noexcept {
sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
return store_ref->capacity();
}
@@ -223,7 +287,7 @@ namespace jau {
* This read operation is <i>lock-free</i>.
* </p>
*/
- bool empty() const noexcept {
+ constexpr bool empty() const noexcept {
sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
return store_ref->empty();
}
@@ -234,11 +298,12 @@ namespace jau {
* This read operation is <i>lock-free</i>.
* </p>
*/
- size_t size() const noexcept {
+ constexpr size_t size() const noexcept {
sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
return store_ref->size();
}
+#if 0
/**
* Like std::vector::operator[](size_t).
* <p>
@@ -292,13 +357,19 @@ namespace jau {
sc_atomic_critical sync(sync_atomic);
return store_ref->at(i);
}
+#endif
// write access
- void reserve(std::size_t n) {
+ void reserve(std::size_t new_capacity) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic );
- store_ref->reserve(n);
+ storage_ref_t old_store_ref = store_ref;
+ if( new_capacity > old_store_ref->capacity() ) {
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->get_allocator() );
+ new_store_ref->reserve(new_capacity);
+ sc_atomic_critical sync( sync_atomic );
+ store_ref = std::move(new_store_ref);
+ }
}
/**
@@ -309,12 +380,12 @@ namespace jau {
*/
cow_vector& operator=(const cow_vector& x) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref x_store_ref;
+ storage_ref_t x_store_ref;
{
sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic );
x_store_ref = x.store_ref;
}
- vector_ref new_store_ref = std::make_shared<vector_t>( *x_store_ref, x_store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *x_store_ref, x_store_ref->get_allocator() );
{
sc_atomic_critical sync(sync_atomic);
store_ref = std::move(new_store_ref);
@@ -325,15 +396,20 @@ namespace jau {
/**
* Like std::vector::operator=(&&), move.
* <p>
- * This write operation uses a mutex lock and is blocking this instances' write operations only.
+ * This write operation uses a mutex lock and is blocking both cow_vector instance's write operations.
* </p>
*/
cow_vector& operator=(cow_vector&& x) {
- const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- sc_atomic_critical sync(sync_atomic);
- // swap store_ref
- store_ref = std::move(x.store_ref);
- x.store_ref = nullptr;
+ std::unique_lock<std::recursive_mutex> lock(mtx_write, std::defer_lock); // utilize std::lock(a, b), allowing mixed order waiting on either object
+ std::unique_lock<std::recursive_mutex> 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);
+ // swap store_ref
+ store_ref = std::move(x.store_ref);
+ x.store_ref = nullptr;
+ }
return *this;
}
@@ -345,7 +421,7 @@ namespace jau {
*/
void clear() noexcept {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>();
+ storage_ref_t new_store_ref = std::make_shared<storage_t>();
{
sc_atomic_critical sync(sync_atomic);
store_ref = std::move(new_store_ref);
@@ -363,9 +439,9 @@ namespace jau {
std::unique_lock<std::recursive_mutex> lock_x(x.mtx_write, std::defer_lock); // otherwise RAII-style relinquish via destructor
std::lock(lock, lock_x);
{
- sc_atomic_critical sync_x( const_cast<cow_vector *>(&x)->sync_atomic );
+ sc_atomic_critical sync_x( x.sync_atomic );
sc_atomic_critical sync(sync_atomic);
- vector_ref x_store_ref = x.store_ref;
+ storage_ref_t x_store_ref = x.store_ref;
x.store_ref = store_ref;
store_ref = x_store_ref;
}
@@ -379,11 +455,14 @@ namespace jau {
*/
void pop_back() noexcept {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
- new_store_ref->pop_back();
- {
- sc_atomic_critical sync(sync_atomic);
- store_ref = std::move(new_store_ref);
+ storage_ref_t old_store_ref = store_ref;
+ if( 0 < old_store_ref->size() ) {
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *old_store_ref, old_store_ref->get_allocator() );
+ new_store_ref->pop_back();
+ {
+ sc_atomic_critical sync(sync_atomic);
+ store_ref = std::move(new_store_ref);
+ }
}
}
@@ -396,7 +475,7 @@ namespace jau {
*/
void push_back(const Value_type& x) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
new_store_ref->push_back(x);
{
sc_atomic_critical sync(sync_atomic);
@@ -412,7 +491,7 @@ namespace jau {
*/
void push_back(Value_type&& x) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
new_store_ref->push_back( std::move(x) );
{
sc_atomic_critical sync(sync_atomic);
@@ -461,7 +540,7 @@ namespace jau {
++it;
}
}
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
new_store_ref->push_back(x);
{
sc_atomic_critical sync(sync_atomic);
@@ -497,11 +576,11 @@ namespace jau {
int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) {
int count = 0;
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
for(auto it = new_store_ref->begin(); it != new_store_ref->end(); ) {
if( comparator( *it, x ) ) {
it = new_store_ref->erase(it);
- count++;
+ ++count;
if( !all_matching ) {
break;
}
@@ -521,12 +600,15 @@ namespace jau {
* <p>
* This write operation uses a mutex lock and is blocking this instances' write operations only.
* </p>
+ * <p>
+ * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end().
+ * </p>
* @param i the position within this store
* @param x the value to be assigned to the object at the given position
*/
void put(size_t i, const Value_type& x) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
new_store_ref->at(i) = x;
{
sc_atomic_critical sync(sync_atomic);
@@ -539,12 +621,15 @@ namespace jau {
* <p>
* This write operation uses a mutex lock and is blocking this instances' write operations only.
* </p>
+ * <p>
+ * To mutate multiple elements, use the more efficient jau::cow_rw_iterator via begin() and end().
+ * </p>
* @param i the position within this store
* @param x the value to be assigned to the object at the given position
*/
void put(size_t i, Value_type&& x) {
const std::lock_guard<std::recursive_mutex> lock(mtx_write);
- vector_ref new_store_ref = std::make_shared<vector_t>( *store_ref, store_ref->get_allocator() );
+ storage_ref_t new_store_ref = std::make_shared<storage_t>( *store_ref, store_ref->get_allocator() );
new_store_ref->at(i) = std::move(x);
{
sc_atomic_critical sync(sync_atomic);
@@ -553,29 +638,6 @@ namespace jau {
}
};
- /**
- * Custom for_each template on a jau::cow_vector snapshot
- * using jau::cow_vector::get_snapshot().
- * <p>
- * jau::for_each_idx() would also be usable, however,
- * iterating through the snapshot preserves consistency over the
- * fetched collection at the time of invocation.
- * </p>
- * <p>
- * Method performs UnaryFunction on all snapshot elements [0..n-1].
- * </p>
- */
- template<typename Value_type, class UnaryFunction>
- constexpr UnaryFunction for_each_cow(cow_vector<Value_type> &cow, UnaryFunction f)
- {
- std::shared_ptr<std::vector<Value_type>> snapshot = cow.get_snapshot();
- const size_t size = snapshot->size();
- for (size_t i = 0; i < size; i++) {
- f( (*snapshot)[i] );
- }
- return f; // implicit move since C++11
- }
-
} /* namespace jau */
#endif /* JAU_COW_VECTOR_HPP_ */
diff --git a/include/jau/darray.hpp b/include/jau/darray.hpp
new file mode 100644
index 0000000..dc81b60
--- /dev/null
+++ b/include/jau/darray.hpp
@@ -0,0 +1,821 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * 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_DYN_ARRAY_HPP_
+#define JAU_DYN_ARRAY_HPP_
+
+#include <cstring>
+#include <string>
+#include <cstdint>
+#include <atomic>
+#include <memory>
+#include <mutex>
+#include <condition_variable>
+#include <vector>
+#include <algorithm>
+
+#include <jau/debug.hpp>
+#include <jau/basic_types.hpp>
+#include <jau/ordered_atomic.hpp>
+
+
+namespace jau {
+
+ /**
+ * Implementation of a dynamic linear array storage, aka vector.<br>
+ * Goals are to support a high-performance CoW dynamic array implementation, jau::cow_darray,<br>
+ * exposing fine grained control over its underlying storage facility.<br>
+ * Further, jau::darray provides high-performance and efficient storage properties on its own.
+ * <p>
+ * API and design differences to std::vector
+ * <ul>
+ * <li>jau::darray adds a parameterized <i>growth factor</i> aspect, default to golden ration jau::darray::DEFAULT_GROWTH_FACTOR</li>
+ * <li><i>capacity</i> control via constructor and operations, related to <i>growth factor</i>.</li>
+ * <li>Iterator jau::darray::const_iterator .. are harmonized with jau::cow_ro_iterator .. used in jau:cow_darray.</li>
+ * <li>...</li>
+ * <li>Custom constructor and operations, supporting a more efficient jau::cow_darray implementation.</li>
+ * <li>Custom template typename Size_type, defaults to jau::nsize_t.</li>
+ * <li>...</li>
+ * <li><b>Removed</b>: Size_type x Value_type fill operations, e.g. assign, constructor, .... for clarity, since supporting <i>capacity</i>.</li>
+ * <li>...</li>
+ * <li><b>TODO</b>: emplace(..), list-initialization operations</li>
+ * </ul>
+ * </p>
+ * <p>
+ * Implementation differences to std::vector and some details
+ * <ul>
+ * <li>Using zero overhead <i>Value_type*</i> as iterator type.</li>
+ * <li>...</li>
+ * <li>Storage is operated on three iterator: <i>begin</i>, <i>end</i> and <i>storage_end</i>.</li>
+ * <li>Constructs and destructs Value_type via <i>placement new</i> within the pre-allocated array capacity. Latter is managed via Alloc_type.</li>
+ * </ul>
+ * </p>
+ */
+ template <typename Value_type, typename Alloc_type = std::allocator<Value_type>, typename Size_type = jau::nsize_t>
+ class darray
+ {
+ public:
+ /** Default growth factor using the golden ratio 1.618 */
+ inline static const float DEFAULT_GROWTH_FACTOR = 1.618f;
+
+ typedef Value_type* iterator;
+ typedef const Value_type* const_iterator;
+
+ private:
+ inline static void freeStore(Alloc_type& alloc, Value_type *ptr, const Size_type size) {
+ if( nullptr != ptr ) {
+ alloc.deallocate(ptr, size);
+ }
+ }
+
+ inline static Value_type * allocStore(Alloc_type& alloc, const Size_type size) {
+ if( 0 < size ) {
+ Value_type * m = alloc.allocate(size);
+ if( nullptr == m ) {
+ throw jau::OutOfMemoryError("allocData "+std::to_string(size)+" elements * "+
+ std::to_string(sizeof(Value_type))+" bytes/element = "+
+ std::to_string(size * sizeof(Value_type))+" bytes -> nullptr", E_FILE_LINE);
+ }
+ return m;
+ }
+ return nullptr;
+ }
+
+ typedef Value_type* array_ref;
+
+ float growth_factor_;
+ Alloc_type alloc_inst;
+ array_ref begin_;
+ array_ref end_;
+ array_ref storage_end_;
+
+ constexpr void set_iterator(array_ref new_storage_, Size_type size_, Size_type capacity_) noexcept {
+ begin_ = new_storage_;
+ end_ = new_storage_+size_;
+ storage_end_ = new_storage_+capacity_;
+ }
+
+ constexpr void set_iterator(Size_type size_, Size_type capacity_) noexcept {
+ end_ = begin_+size_;
+ storage_end_ = begin_+capacity_;
+ }
+
+ Size_type dtor_range(array_ref first, const array_ref last) {
+ Size_type count=0;
+ for(; first < last; ++first, ++count ) {
+ ( first )->~Value_type(); // placement new -> manual destruction!
+ }
+ return count;
+ }
+
+ inline static void ctor_copy_range(array_ref dest, array_ref first, const array_ref last) {
+ for(; first < last; ++dest, ++first) {
+ new (dest) Value_type( *first ); // placement new
+ }
+ }
+ static array_ref clone_range(Alloc_type& alloc, const Size_type dest_capacity, const array_ref first, const array_ref last) {
+ if( dest_capacity < Size_type(last-first) ) {
+ throw jau::IllegalArgumentException("capacity "+std::to_string(dest_capacity)+" < source range "+
+ std::to_string(Size_type(last-first)), E_FILE_LINE);
+ }
+ array_ref dest = allocStore(alloc, dest_capacity);
+ ctor_copy_range(dest, first, last);
+ return dest;
+ }
+ static array_ref clone_range(Alloc_type& alloc, const array_ref first, const array_ref last) {
+ array_ref dest = allocStore(alloc, Size_type(last-first));
+ ctor_copy_range(dest, first, last);
+ return dest;
+ }
+
+ template< class InputIt >
+ inline static void ctor_copy_range_foreign(array_ref dest, InputIt first, InputIt last) {
+ for(; first < last; ++dest, ++first) {
+ new (dest) Value_type( *first ); // placement new
+ }
+ }
+ template< class InputIt >
+ static array_ref clone_range_foreign(Alloc_type& alloc, const Size_type dest_capacity, InputIt first, InputIt last) {
+ if( dest_capacity < Size_type(last-first) ) {
+ throw jau::IllegalArgumentException("capacity "+std::to_string(dest_capacity)+" < source range "+
+ std::to_string(Size_type(last-first)), E_FILE_LINE);
+ }
+ array_ref dest = allocStore(alloc, dest_capacity);
+ ctor_copy_range_foreign(dest, first, last);
+ return dest;
+ }
+
+ inline static void ctor_move_range(array_ref dest, array_ref first, const array_ref last) {
+ for(; first < last; ++dest, ++first) {
+ new (dest) Value_type( std::move( *first ) ); // placement new
+ }
+ }
+ void grow_storage_move(const Size_type new_capacity) {
+ array_ref dest = allocStore(alloc_inst, new_capacity);
+ ctor_move_range(dest, begin_, end_);
+
+ freeStore(alloc_inst, begin_, capacity());
+
+ set_iterator(dest, size(), new_capacity);
+ }
+
+ public:
+
+ // ctor w/o elements
+
+ /**
+ * Default constructor, giving zero capacity and zero memory footprint.
+ */
+ constexpr darray() noexcept
+ : growth_factor_(DEFAULT_GROWTH_FACTOR), alloc_inst(),
+ begin_( nullptr ), end_( nullptr ), storage_end_( nullptr ) {}
+
+ /**
+ * 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 Alloc_type
+ */
+ constexpr explicit darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type())
+ : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( allocStore(alloc_inst, capacity) ),
+ end_( begin_ ), storage_end_( begin_ + capacity ) {}
+
+ // copy_ctor on darray elements
+
+ /**
+ * Creates a new instance, copying all elements from the given darray.<br>
+ * Capacity and size will equal the given array, i.e. the result is a trimmed jau::darray.
+ * @param x the given darray, all elements will be copied into the new instance.
+ */
+ constexpr darray(const darray& x)
+ : growth_factor_( x.growth_factor_ ), alloc_inst( x.alloc_inst ), begin_( clone_range(alloc_inst, x.begin_, x.end_) ),
+ end_( begin_ + x.size() ), storage_end_( begin_ + x.size() )
+ { }
+
+ /**
+ * Creates a new instance, copying all elements from the given darray.<br>
+ * Capacity and size will equal the given array, i.e. the result is a trimmed jau::darray.
+ * @param x the given darray, all elements will be copied into the new instance.
+ * @param growth_factor custom growth factor
+ * @param alloc custom Alloc_type instance
+ */
+ constexpr explicit darray(const darray& x, const float growth_factor, const Alloc_type& alloc)
+ : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, x.begin_, x.end_) ),
+ end_( begin_ + x.size() ), storage_end_( begin_ + x.size() )
+ { }
+
+ /**
+ * Creates a new instance with custom initial storage capacity, copying all elements from the given darray.<br>
+ * Size will equal the given array.
+ * <p>
+ * Throws jau::IllegalArgumentException() if <code>_capacity < x.size()</code>.
+ * </p>
+ * @param x the given 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 Alloc_type instance
+ */
+ constexpr explicit darray(const darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc)
+ : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, _capacity, x.begin_, x.end_) ),
+ end_( begin_ + x.size() ), storage_end_( begin_ + _capacity )
+ { }
+
+ // move_ctor on darray elements
+
+ constexpr darray(darray && x) noexcept
+ : growth_factor_(std::move(x.growth_factor_)), alloc_inst(std::move(x.alloc_inst)),
+ begin_(std::move(x.begin_)), end_(std::move(x.end_)), storage_end_(std::move(x.storage_end_))
+ {
+ // complete swapping store_ref
+ x.begin_ = nullptr;
+ x.end_ = nullptr;
+ x.storage_end_ = nullptr;
+ }
+
+ constexpr explicit darray(darray && x, const float growth_factor, const Alloc_type& alloc) noexcept
+ : growth_factor_(std::move(x.growth_factor_)), alloc_inst(alloc),
+ begin_(std::move(x.begin_)), end_(std::move(x.end_)), storage_end_(std::move(x.storage_end_))
+ {
+ // complete swapping store_ref
+ x.begin_ = nullptr;
+ x.end_ = nullptr;
+ x.storage_end_ = nullptr;
+ }
+
+ // 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).<br>
+ * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>.
+ * <p>
+ * Throws jau::IllegalArgumentException() if <code>_capacity < Size_type(last - first)</code>.
+ * </p>
+ * @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 Alloc_type instance
+ */
+ constexpr darray(const Size_type _capacity, const_iterator first, const_iterator last,
+ const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type())
+ : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range(alloc_inst, _capacity, first, last) ),
+ end_(begin_ + Size_type(last - first) ), storage_end_( begin_ + _capacity )
+ { }
+
+ /**
+ * Creates a new instance with custom initial storage capacity,
+ * copying all elements from the given template input-iterator Value_type range [first, last).<br>
+ * Size will equal the range [first, last), i.e. <code>Size_type(last-first)</code>.
+ * <p>
+ * Throws jau::IllegalArgumentException() if <code>_capacity < Size_type(last - first)</code>.
+ * </p>
+ * @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 Alloc_type instance
+ */
+ template< class InputIt >
+ constexpr explicit darray(const Size_type _capacity, InputIt first, InputIt last,
+ const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type())
+ : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( clone_range_foreign(alloc_inst, _capacity, first, last) ),
+ end_(begin_ + Size_type(last - first) ), storage_end_( begin_ + _capacity )
+ { }
+
+ ~darray() noexcept {
+ clear();
+ }
+
+ // iterator
+
+ constexpr iterator begin() noexcept { return begin_; }
+
+ constexpr const_iterator begin() const noexcept { return begin_; }
+
+ constexpr const_iterator cbegin() const noexcept { return begin_; }
+
+ constexpr iterator end() noexcept { return end_; }
+
+ constexpr const_iterator end() const noexcept { return end_; }
+
+ constexpr const_iterator cend() const noexcept { return end_; }
+
+#if 0
+ constexpr iterator storage_end() noexcept { return storage_end_; }
+
+ constexpr const_iterator storage_end() const noexcept { return storage_end_; }
+
+ constexpr const_iterator cstorage_end() const noexcept { return storage_end_; }
+#endif
+
+ // read access
+
+ const Alloc_type& get_allocator_ref() const noexcept {
+ return alloc_inst;
+ }
+
+ Alloc_type get_allocator() const noexcept {
+ return Alloc_type(alloc_inst);
+ }
+
+ constexpr float growth_factor() const noexcept {
+ return growth_factor_;
+ }
+
+ constexpr Size_type capacity() const noexcept { return Size_type(storage_end_ - begin_); }
+
+ constexpr Size_type grow_number(const Size_type old_number ) const noexcept {
+ const Size_type res = static_cast<Size_type>(old_number * growth_factor_ + 0.5f); // simple round up
+ return std::max<Size_type>(old_number+1, res);
+ }
+ constexpr Size_type grow_capacity() const noexcept {
+ const Size_type old_number = capacity();
+ const Size_type res = static_cast<Size_type>(old_number * growth_factor_ + 0.5f); // simple round up
+ return std::max<Size_type>(old_number+1, res);
+ }
+
+ /**
+ * Like std::vector::empty().
+ */
+ constexpr bool empty() const noexcept { return begin_ == end_; }
+
+ /**
+ * Returns true if capacity has been reached and the next push_back()
+ * will grow the storage and invalidates all iterators and references.
+ */
+ constexpr bool capacity_reached() const noexcept { return end_ >= storage_end_; }
+
+ /**
+ * Like std::vector::size().
+ */
+ constexpr Size_type size() const noexcept { return Size_type(end_ - begin_); }
+
+ // mixed mutable/immutable element access
+
+ /**
+ * Like std::vector::front(), mutable access.
+ */
+ constexpr Value_type & front() { return *begin_; }
+
+ /**
+ * Like std::vector::front(), immutable access.
+ */
+ constexpr const Value_type & front() const { return *begin_; }
+
+ /**
+ * Like std::vector::back(), mutable access.
+ */
+ constexpr Value_type & back() { return *(end_-1); }
+
+ /**
+ * Like std::vector::back(), immutable access.
+ */
+ constexpr const Value_type & back() const { return *(end_-1); }
+
+ /**
+ * Like std::vector::data(), const immutable pointer
+ */
+ constexpr const Value_type* data() const noexcept { return begin_; }
+
+ /**
+ * Like std::vector::data(), mutable pointer
+ */
+ constexpr Value_type* data() noexcept { return begin_; }
+
+ /**
+ * Like std::vector::operator[](Size_type), immutable reference.
+ */
+ const Value_type & operator[](Size_type i) const noexcept {
+ return *(begin_+i);
+ }
+
+ /**
+ * Like std::vector::operator[](Size_type), mutable reference.
+ */
+ Value_type & operator[](Size_type i) noexcept {
+ return *(begin_+i);
+ }
+
+ /**
+ * Like std::vector::at(Size_type), immutable reference.
+ */
+ const Value_type & at(Size_type i) const {
+ if( 0 <= i && i < size() ) {
+ return *(begin_+i);
+ }
+ throw jau::IndexOutOfBoundsException(i, size(), E_FILE_LINE);
+ }
+
+ /**
+ * Like std::vector::at(Size_type), mutable reference.
+ */
+ Value_type & at(Size_type i) {
+ if( 0 <= i && i < size() ) {
+ return *(begin_+i);
+ }
+ throw jau::IndexOutOfBoundsException(i, size(), E_FILE_LINE);
+ }
+
+ // write access, mutable array operations
+
+ /**
+ * Like std::vector::reserve(), increases this instance's capacity to <code>new_capacity</code>.
+ * <p>
+ * Only creates a new storage and invalidates iterators if <code>new_capacity</code>
+ * is greater than the current jau::darray::capacity().
+ * </p>
+ */
+ void reserve(Size_type new_capacity) {
+ const Size_type capacity_ = capacity();
+ if( new_capacity > capacity_ ) {
+ array_ref new_storage = allocStore(alloc_inst, new_capacity);
+ ctor_move_range(new_storage, begin_, end_);
+
+ freeStore(alloc_inst, begin_, capacity_);
+
+ set_iterator(new_storage, size(), new_capacity);
+ }
+ }
+
+ /**
+ * Like std::vector::operator=(&), assignment
+ */
+ darray& operator=(const darray& x) {
+ const Size_type size_ = size();
+ const Size_type capacity_ = capacity();
+ const Size_type x_size_ = x.size();
+ dtor_range(begin_, end_);
+ if( x_size_ > capacity_ ) {
+ freeStore(alloc_inst, begin_, capacity_);
+ begin_ = clone_range(alloc_inst, x_size_, x.begin_, x.end_);
+ set_iterator(x_size_, x_size_);
+ } else {
+ ctor_copy_range(begin_, x.begin_, x.end_);
+ set_iterator(x_size_, capacity_);
+ }
+ return *this;
+ }
+
+ /**
+ * Like std::vector::assign()
+ * @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 void assign( InputIt first, InputIt last ) {
+ const Size_type size_ = size();
+ const Size_type capacity_ = capacity();
+ const Size_type x_size_ = Size_type(last - first);
+ dtor_range(begin_, end_);
+ if( x_size_ > capacity_ ) {
+ freeStore(alloc_inst, begin_, capacity_);
+ begin_ = clone_range_foreign(alloc_inst, x_size_, first, last);
+ set_iterator(x_size_, x_size_);
+ } else {
+ ctor_copy_range_foreign(begin_, first, last);
+ set_iterator(x_size_, capacity_);
+ }
+ }
+ /**
+ * Like std::vector::assign(), but non-template overload using const_iterator.
+ * @param first first const_iterator to range of Value_type [first, last)
+ * @param last last const_iterator to range of Value_type [first, last)
+ */
+ constexpr void assign( const_iterator first, const_iterator last ) {
+ const Size_type size_ = size();
+ const Size_type capacity_ = capacity();
+ const Size_type x_size_ = Size_type(last - first);
+ dtor_range(begin_, end_);
+ if( x_size_ > capacity_ ) {
+ freeStore(alloc_inst, begin_, capacity_);
+ begin_ = clone_range(alloc_inst, x_size_, first, last);
+ set_iterator(x_size_, x_size_);
+ } else {
+ ctor_copy_range(begin_, first, last);
+ set_iterator(x_size_, capacity_);
+ }
+ }
+
+ /**
+ * Like std::vector::operator=(&&), move.
+ */
+ darray& operator=(darray&& x) {
+ clear();
+ alloc_inst = std::move(x.alloc_inst);
+ begin_ = std::move(x.begin_);
+ end_ = std::move(x.end_);
+ storage_end_ = std::move(x.storage_end_);
+
+ // complete swapping store_ref
+ x.begin_ = nullptr;
+ x.end_ = nullptr;
+ x.storage_end_ = nullptr;
+
+ return *this;
+ }
+
+ /**
+ * Like std::vector::clear(), but ending with zero capacity.
+ */
+ void clear() noexcept {
+ dtor_range(begin_, end_);
+ freeStore(alloc_inst, begin_, capacity());
+ begin_ = nullptr;
+ end_ = nullptr;
+ storage_end_ = nullptr;
+ }
+
+ /**
+ * Like std::vector::swap().
+ */
+ void swap(darray& x) noexcept {
+ std::swap(growth_factor_, x.growth_factor_);
+ std::swap(alloc_inst, x.alloc_inst);
+ std::swap(begin_, x.begin_);
+ std::swap(end_, x.end_);
+ std::swap(storage_end_, x.storage_end_);
+ }
+
+ /**
+ * Like std::vector::pop_back().
+ */
+ void pop_back() noexcept {
+ if( begin_ != end_ ) {
+ ( --end_ )->~Value_type(); // placement new -> manual destruction!
+ }
+ }
+
+ /**
+ * Like std::vector::push_back(), copy
+ * @param x the value to be added at the tail.
+ */
+ void push_back(const Value_type& x) {
+ if( end_ == storage_end_ ) {
+ grow_storage_move(grow_capacity());
+ }
+ new (end_) Value_type( x ); // placement new
+ ++end_;
+ }
+
+ /**
+ * Like std::vector::push_back(), move
+ */
+ void push_back(Value_type&& x) {
+ if( end_ == storage_end_ ) {
+ grow_storage_move(grow_capacity());
+ }
+ new (end_) Value_type( std::move(x) ); // placement new
+ ++end_;
+ }
+
+ /**
+ * Like std::vector::push_back(), but appends the whole Value_type range [first, last).
+ * @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 void push_back( InputIt first, InputIt last ) {
+ const Size_type count = Size_type(last - first);
+
+ if( end_ + count >= storage_end_ ) {
+ grow_storage_move(size() + count);
+ }
+ ctor_copy_range_foreign(end_, first, last);
+ end_ += count;
+ }
+
+ /**
+ * Like std::vector::push_back(), but appends the whole Value_type range [first, last).
+ * @param first first const_iterator to range of Value_type [first, last)
+ * @param last last const_iterator to range of Value_type [first, last)
+ */
+ constexpr void push_back( const_iterator first, const_iterator last ) {
+ const Size_type count = Size_type(last - first);
+
+ if( end_ + count >= storage_end_ ) {
+ grow_storage_move(size() + count);
+ }
+ ctor_copy_range(end_, first, last);
+ end_ += count;
+ }
+
+ /**
+ * Like std::vector::erase().
+ * <p>
+ * Removes the element at the given position
+ * and moves all subsequent elements one left.
+ * </p>
+ * <p>
+ * size will be reduced by one.
+ * </p>
+ * @param i the position of the element to be removed
+ */
+ void erase(const Size_type i) {
+ const Size_type size_ = size();
+ if( 0 <= i && i < size_ ) {
+ ( begin_ + i )->~Value_type(); // placement new -> manual destruction!
+
+ const Size_type right_count = size_ - 1 - i;
+ if( 0 < right_count ) {
+ memmove(begin_+i, begin_+i+1, sizeof(Value_type)*right_count); // move right elems one left
+ }
+ --end_;
+ } else {
+ throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE);
+ }
+ }
+
+ /**
+ * Like std::vector::erase(), removes the elements at pos.
+ * @return iterator following the last removed element.
+ */
+ constexpr iterator erase (const_iterator pos) {
+ if( begin_ <= pos && pos < end_ ) {
+ ( pos )->~Value_type(); // placement new -> manual destruction!
+ const Size_type right_count = ( end_ - pos ) - 1;
+ if( 0 < right_count ) {
+ memmove(pos, pos+1, sizeof(Value_type)*right_count); // move right elems one left
+ }
+ --end_;
+ }
+ return begin_ <= pos && pos <= end_ ? pos : nullptr;
+ }
+
+ /**
+ * Like std::vector::erase(), removes the elements in the range [first, last).
+ * @return iterator following the last removed element.
+ */
+ constexpr iterator erase (const_iterator first, const_iterator last) {
+ const Size_type count = dtor_range(first, last);
+ if( count > 0 ) {
+ const Size_type right_count = ( end_ - last ) - 1;
+ if( 0 < right_count ) {
+ memmove(first, last, sizeof(Value_type)*right_count); // move right elems one left
+ }
+ end_ -= count;
+ }
+ return begin_ <= last && last <= end_ ? last : nullptr;
+ }
+
+ /**
+ * Like std::vector::insert(), copy
+ * <p>
+ * Inserts the element at the given position
+ * and moves all elements from there to the right beforehand.
+ * </p>
+ * <p>
+ * size will be increased by one.
+ * </p>
+ * @param i the position of the element to be removed
+ */
+ void insert(Size_type i, const Value_type& x) {
+ const Size_type size_ = size();
+ if( 0 <= i && i <= size_ ) {
+ const Size_type old_capacity_ = capacity();
+ if( size_ + 1 > old_capacity_ ) {
+ grow_storage_move(grow_number(old_capacity_));
+ }
+ const Size_type right_count = size_ - i;
+ if( 0 < right_count ) {
+ memmove(begin_+i+1, begin_+i, sizeof(Value_type)*right_count); // move right elems one right
+ }
+ new (begin_+i) Value_type( x ); // placement new
+ ++end_;
+ } else {
+ throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE);
+ }
+ }
+
+ /**
+ * Like std::vector::insert(), move
+ * <p>
+ * Inserts the element at the given position
+ * and moves all elements from there to the right beforehand.
+ * </p>
+ * <p>
+ * size will be increased by one.
+ * </p>
+ * @param i the position of the element to be removed
+ */
+ void insert(Size_type i, Value_type&& x) {
+ const Size_type size_ = size();
+ if( 0 <= i && i <= size_ ) {
+ const Size_type old_capacity_ = capacity();
+ if( size_ + 1 > old_capacity_ ) {
+ grow_storage_move(grow_number(old_capacity_));
+ }
+ const Size_type right_count = size_ - i;
+ if( 0 < right_count ) {
+ memmove(begin_+i+1, begin_+i, sizeof(Value_type)*right_count); // move right elems one right
+ }
+ new (begin_+i) Value_type( std::move(x) ); // placement new
+ ++end_;
+ } else {
+ throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE);
+ }
+ }
+
+ /**
+ * Generic Value_type equal comparator to be user defined for e.g. jau::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.
+ * <p>
+ * Examples
+ * <pre>
+ * static jau::darray<Thing>::equal_comparator thingEqComparator =
+ * [](const Thing &a, const Thing &b) -> bool { return a == b; };
+ * ...
+ * jau::darray<Thing> list;
+ *
+ * bool added = list.push_back_unique(new_element, thingEqComparator);
+ * ...
+ * darray<std::shared_ptr<Thing>> listOfRefs;
+ * bool added = listOfRefs.push_back_unique(new_element,
+ * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; });
+ * </pre>
+ * </p>
+ * @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
+ */
+ bool push_back_unique(const Value_type& x, equal_comparator comparator) {
+ for(auto it = begin_; it != 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.
+ * <p>
+ * Examples
+ * <pre>
+ * darray<Thing> list;
+ * int count = list.erase_matching(element, true,
+ * [](const Thing &a, const Thing &b) -> bool { return a == b; });
+ * ...
+ * static jau::darray<Thing>::equal_comparator thingRefEqComparator =
+ * [](const std::shared_ptr<Thing> &a, const std::shared_ptr<Thing> &b) -> bool { return *a == *b; };
+ * ...
+ * darray<std::shared_ptr<Thing>> listOfRefs;
+ * int count = listOfRefs.erase_matching(element, false, thingRefEqComparator);
+ * </pre>
+ * </p>
+ * @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
+ */
+ int erase_matching(const Value_type& x, const bool all_matching, equal_comparator comparator) {
+ int count = 0;
+ for(auto it = end_-1; begin_ <= it; --it) {
+ if( comparator( *it, x ) ) {
+ erase(it);
+ ++count;
+ if( !all_matching ) {
+ break;
+ }
+ }
+ }
+ return count;
+ }
+ };
+} /* namespace jau */
+
+#endif /* JAU_DYN_ARRAY_HPP_ */
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 33b448f..7bd76e5 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -21,7 +21,8 @@ set( SOURCES_IDIOMATIC_EXAMPLES
test_lfringbuffer11.cpp
test_mm_sc_drf_00.cpp
test_mm_sc_drf_01.cpp
- test_cowvector_perf01.cpp
+ test_cow_darray_01.cpp
+ test_cow_darray_perf01.cpp
test_hashset_perf01.cpp
)
diff --git a/test/test_cow_darray_01.cpp b/test/test_cow_darray_01.cpp
new file mode 100644
index 0000000..6a1ce85
--- /dev/null
+++ b/test/test_cow_darray_01.cpp
@@ -0,0 +1,380 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * 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.
+ */
+#include <iostream>
+#include <cassert>
+#include <cinttypes>
+#include <cstring>
+#include <random>
+#include <vector>
+
+#define CATCH_CONFIG_RUNNER
+// #define CATCH_CONFIG_MAIN
+#include <catch2/catch_amalgamated.hpp>
+#include <jau/test/catch2_ext.hpp>
+
+#include "test_datatype01.hpp"
+
+#include <jau/basic_types.hpp>
+#include <jau/darray.hpp>
+#include <jau/cow_darray.hpp>
+#include <jau/cow_vector.hpp>
+#include <jau/counting_allocator.hpp>
+
+using namespace jau;
+
+static uint8_t start_addr_b[] = {0x20, 0x26, 0x2A, 0x01, 0x20, 0x10};
+static Addr48Bit start_addr(start_addr_b);
+
+typedef std::vector<DataType01, counting_allocator<DataType01>> DataType01Vector;
+
+template<class T>
+DataType01 * findDataSet01_idx(T& data, DataType01 const & elem) noexcept {
+ const size_t size = data.size();
+ for (size_t i = 0; i < size; i++) {
+ DataType01 & e = data[i];
+ if ( elem == e ) {
+ return &e;
+ }
+ }
+ return nullptr;
+}
+template<class T>
+const DataType01 * findDataSet01_itr(T& data, DataType01 const & elem) noexcept {
+ typename T::const_iterator iter = data.cbegin();
+ typename T::const_iterator end = data.cend();
+ for(; iter != end ; ++iter) {
+ if( elem == *iter ) {
+ return &(*iter);
+ }
+ }
+ return nullptr;
+}
+
+template<class T>
+static void test_00_list_idx(T& data, const bool show) {
+ Addr48Bit a0(start_addr);
+ const std::size_t size = data.size();
+ for (std::size_t i = 0; i < size && a0.next(); ++i) {
+ const DataType01 & e = data[i];
+ e.nop();
+ if( show ) {
+ printf("data[%zu]: %s\n", i, e.toString().c_str());
+ }
+ REQUIRE(e.address == a0);
+ }
+}
+template<class T>
+static void test_00_list_itr(T& data, const bool show) {
+ Addr48Bit a0(start_addr);
+ typename T::const_iterator iter = data.cbegin();
+ typename T::const_iterator end = data.cend();
+ for(std::size_t i = 0; iter != end && a0.next(); ++iter, ++i) {
+ const DataType01 & e = *iter;
+ e.nop();
+ if( show ) {
+ printf("data[%zu]: %s\n", i, e.toString().c_str());
+ }
+ REQUIRE(e.address == a0);
+ }
+}
+
+template<class T>
+static void test_00_seq_find_idx(T& data) {
+ Addr48Bit a0(start_addr);
+ const std::size_t size = data.size();
+ std::size_t fi = 0, i=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ DataType01 *found = findDataSet01_idx(data, elem);
+ if( nullptr != found ) {
+ fi++;
+ found->nop();
+ }
+ }
+ REQUIRE(fi == i);
+}
+template<class T>
+static void test_00_seq_find_itr(T& data) {
+ Addr48Bit a0(start_addr);
+ const std::size_t size = data.size();
+ std::size_t fi = 0, i=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ const DataType01 *found = findDataSet01_itr(data, elem);
+ if( nullptr != found ) {
+ fi++;
+ found->nop();
+ }
+ }
+ REQUIRE(fi == i);
+}
+
+template<class T>
+static void test_00_seq_fill(T& data, const std::size_t size) {
+ Addr48Bit a0(start_addr);
+ std::size_t i=0;
+
+ for(; i<size && a0.next(); i++) {
+ data.push_back( std::move( DataType01(a0, static_cast<uint8_t>(1)) ) );
+ }
+ if( i != data.size() ) {
+ test_00_list_itr(data, true);
+ printf("a0 %s\n", a0.toString().c_str());
+ printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i);
+ }
+ REQUIRE(i == data.size());
+}
+
+template<class T>
+static void test_00_seq_fill_unique_idx(T& data, const std::size_t size) {
+ Addr48Bit a0(start_addr);
+ std::size_t i=0, fi=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ DataType01* exist = findDataSet01_idx(data, elem);
+ if( nullptr == exist ) {
+ data.push_back( std::move(elem) );
+ fi++;
+ } else {
+ printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist));
+ }
+ }
+ if( fi != size ) {
+ test_00_list_idx(data, true);
+ printf("a0 %s\n", a0.toString().c_str());
+ printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i);
+ }
+ REQUIRE(i == data.size());
+ REQUIRE(fi == size);
+}
+template<class T>
+static void test_00_seq_fill_unique_itr(T& data, const std::size_t size) {
+ Addr48Bit a0(start_addr);
+ std::size_t i=0, fi=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ const DataType01* exist = findDataSet01_itr(data, elem);
+ if( nullptr == exist ) {
+ data.push_back( std::move(elem) );
+ fi++;
+ } else {
+ printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist));
+ }
+ }
+ if( fi != size ) {
+ test_00_list_itr(data, true);
+ printf("a0 %s\n", a0.toString().c_str());
+ printf("Size %zu, expected %zu, iter %zu\n", static_cast<std::size_t>(data.size()), size, i);
+ }
+ REQUIRE(i == data.size());
+ REQUIRE(fi == size);
+}
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+template<class T>
+static bool test_01_seq_fill_list_idx(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) {
+ (void)type_id;
+
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_list_idx(data, false);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+template<class T>
+static bool test_01_seq_fill_list_itr(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) {
+ (void)type_id;
+
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_list_itr(data, false);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+template<class T>
+static bool test_02_seq_fillunique_find_idx(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) {
+ (void)type_id;
+
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill_unique_idx(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_seq_find_idx(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+template<class T>
+static bool test_02_seq_fillunique_find_itr(const std::string& type_id, const std::size_t size0, const std::size_t reserve0) {
+ (void)type_id;
+
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill_unique_itr(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_seq_find_itr(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+TEST_CASE( "STD Vector Test 01 - Fill Sequential and List", "[datatype][std][vector]" ) {
+ test_01_seq_fill_list_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_reserve", 100, 100);
+
+ test_01_seq_fill_list_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_fillseq_reserve", 100, 100);
+}
+
+TEST_CASE( "STD Vector Test 02 - Fill Unique and Find-Each", "[datatype][std][vector]" ) {
+ test_02_seq_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_reserve", 100, 100);
+
+ test_02_seq_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>> >("stdvec_filluni_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU COW_Vector Test 11 - Fill Sequential and List", "[datatype][jau][cow_vector]" ) {
+ // test_01_seq_fill_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_empty__", 100, 0);
+ // test_01_seq_fill_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_reserve", 100, 100);
+
+ test_01_seq_fill_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_fillseq_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU COW_Vector Test 12 - Fill Unique and Find-Each", "[datatype][jau][cow_vector]" ) {
+ // test_02_seq_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_empty__", 100, 0);
+ // test_02_seq_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_reserve", 100, 100);
+
+ test_02_seq_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>> >("cowstdvec_filluni_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU DArray Test 21 - Fill Sequential and List", "[datatype][jau][darray]" ) {
+ test_01_seq_fill_list_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_reserve", 100, 100);
+
+ test_01_seq_fill_list_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_fillseq_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU DArray Test 22 - Fill Unique and Find-Each", "[datatype][jau][darray]" ) {
+ test_02_seq_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_reserve", 100, 100);
+
+ test_02_seq_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>> >("darray_filluni_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU COW_DArray Test 31 - Fill Sequential and List", "[datatype][jau][cow_darray]" ) {
+ // test_01_seq_fill_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_empty__", 100, 0);
+ // test_01_seq_fill_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_reserve", 100, 100);
+
+ test_01_seq_fill_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_empty__", 100, 0);
+ test_01_seq_fill_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_fillseq_reserve", 100, 100);
+}
+
+TEST_CASE( "JAU COW_DArray Test 32 - Fill Unique and Find-Each", "[datatype][jau][cow_darray]" ) {
+ // test_02_seq_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_empty__", 100, 0);
+ // test_02_seq_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_reserve", 100, 100);
+
+ test_02_seq_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_empty__", 100, 0);
+ test_02_seq_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>> >("cowdarray_filluni_reserve", 100, 100);
+}
diff --git a/test/test_cow_darray_perf01.cpp b/test/test_cow_darray_perf01.cpp
new file mode 100644
index 0000000..6223395
--- /dev/null
+++ b/test/test_cow_darray_perf01.cpp
@@ -0,0 +1,565 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * 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.
+ */
+#include <iostream>
+#include <cassert>
+#include <cinttypes>
+#include <cstring>
+#include <random>
+#include <vector>
+
+#define CATCH_CONFIG_RUNNER
+// #define CATCH_CONFIG_MAIN
+#include <catch2/catch_amalgamated.hpp>
+#include <jau/test/catch2_ext.hpp>
+
+#include "test_datatype01.hpp"
+
+#include <jau/basic_types.hpp>
+#include <jau/darray.hpp>
+#include <jau/cow_darray.hpp>
+#include <jau/cow_vector.hpp>
+#include <jau/counting_allocator.hpp>
+
+using namespace jau;
+
+static uint8_t start_addr_b[] = {0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
+static Addr48Bit start_addr(start_addr_b);
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+template<class T, typename Size_type>
+DataType01 * findDataSet01_idx(T& data, DataType01 const & elem) noexcept {
+ const Size_type size = data.size();
+ for (Size_type i = 0; i < size; i++) {
+ DataType01 & e = data[i];
+ if ( elem == e ) {
+ return &e;
+ }
+ }
+ return nullptr;
+}
+
+template<class T>
+const DataType01 * findDataSet01_itr(T& data, DataType01 const & elem) noexcept {
+ typename T::const_iterator iter = data.cbegin();
+ typename T::const_iterator end = data.cend();
+ for(; iter != end ; ++iter) {
+ if( elem == *iter ) {
+ return &(*iter);
+ }
+ }
+ return nullptr;
+}
+
+template<class T, typename Size_type>
+static void test_00_list_idx(T& data) {
+ const Size_type size = data.size();
+ for (Size_type i = 0; i < size; i++) {
+ const DataType01 & e = data[i];
+ e.nop();
+ }
+}
+
+template<class T>
+static void test_00_list_itr(T& data) {
+ typename T::const_iterator iter = data.cbegin();
+ typename T::const_iterator end = data.cend();
+ for(; iter != end ; ++iter) {
+ const DataType01 & e = *iter;
+ e.nop();
+ }
+}
+
+template<class T, typename Size_type>
+static void test_00_seq_find_idx(T& data) {
+ Addr48Bit a0(start_addr);
+ const Size_type size = data.size();
+ Size_type fi = 0, i=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ DataType01 *found = findDataSet01_idx<T, Size_type>(data, elem);
+ if( nullptr != found ) {
+ fi++;
+ found->nop();
+ }
+ }
+ REQUIRE(fi == i);
+}
+
+template<class T, typename Size_type>
+static void test_00_seq_find_itr(T& data) {
+ Addr48Bit a0(start_addr);
+ const Size_type size = data.size();
+ Size_type fi = 0, i=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ const DataType01 *found = findDataSet01_itr<T>(data, elem);
+ if( nullptr != found ) {
+ fi++;
+ found->nop();
+ }
+ }
+ REQUIRE(fi == i);
+}
+
+template<class T, typename Size_type>
+static void test_00_seq_fill(T& data, const Size_type size) {
+ Addr48Bit a0(start_addr);
+ Size_type i=0;
+
+ for(; i<size && a0.next(); i++) {
+ data.push_back( std::move( DataType01(a0, static_cast<uint8_t>(1)) ) );
+ }
+ REQUIRE(i == data.size());
+}
+
+template<class T, typename Size_type>
+static void test_00_seq_fill_unique_idx(T& data, const Size_type size) {
+ Addr48Bit a0(start_addr);
+ Size_type i=0, fi=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ DataType01* exist = findDataSet01_idx<T, Size_type>(data, elem);
+ if( nullptr == exist ) {
+ data.push_back( std::move(elem) );
+ fi++;
+ }
+ }
+ REQUIRE(i == data.size());
+ REQUIRE(fi == size);
+}
+template<class T, typename Size_type>
+static void test_00_seq_fill_unique_itr(T& data, const Size_type size) {
+ Addr48Bit a0(start_addr);
+ Size_type i=0, fi=0;
+
+ for(; i<size && a0.next(); i++) {
+ DataType01 elem(a0, static_cast<uint8_t>(1));
+ const DataType01* exist = findDataSet01_itr<T>(data, elem);
+ if( nullptr == exist ) {
+ data.push_back( std::move(elem) );
+ fi++;
+ }
+ }
+ REQUIRE(i == data.size());
+ REQUIRE(fi == size);
+}
+
+template<class T>
+static void print_mem(const std::string& pre, const T& data) {
+ std::size_t bytes_element = sizeof(DataType01);
+ std::size_t elements = data.size();
+ std::size_t bytes_net = elements * bytes_element;
+ std::size_t bytes_total = data.get_allocator().memory_usage;
+ double overhead = 0 == bytes_total ? 0.0 : ( 0 == bytes_net ? 10.0 : (double)bytes_total / (double)bytes_net );
+ printf("Mem: %s: Elements %s x %zu bytes; %s, %lf ratio\n",
+ pre.c_str(), int64DecString(elements, ',', 5).c_str(),
+ bytes_element, data.get_allocator().toString(10, 5).c_str(), overhead);
+ // 5: 1,000
+ // 7: 100,000
+ // 9: 1,000,000
+}
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+template<class T, typename Size_type>
+static bool test_01_seq_fill_list_idx(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) {
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 01 (empty)", data); }
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill<T, Size_type>(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_list_idx<T, Size_type>(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+ if( do_print_mem ) { print_mem(type_id+" 01 (full_)", data); }
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 01 (clear)", data); }
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+template<class T, typename Size_type>
+static bool test_01_seq_fill_list_itr(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) {
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 01 (empty)", data); }
+
+ if( 0 < reserve0 ) {
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+ }
+
+ test_00_seq_fill<T, Size_type>(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_list_itr<T>(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+ if( do_print_mem ) { print_mem(type_id+" 01 (full_)", data); }
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 01 (clear)", data); }
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+template<class T, typename Size_type>
+static bool test_02_seq_fillunique_find_idx(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) {
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); }
+
+ if( 0 < reserve0 ) {
+ data.reserve(reserve0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == reserve0);
+ }
+
+ test_00_seq_fill_unique_idx<T, Size_type>(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_seq_find_idx<T, Size_type>(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+ if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); }
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); }
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+template<class T, typename Size_type>
+static bool test_02_seq_fillunique_find_itr(const std::string& type_id, const Size_type size0, const Size_type reserve0, const bool do_print_mem) {
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); }
+
+ if( 0 < reserve0 ) {
+ data.reserve(reserve0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == reserve0);
+ }
+
+ test_00_seq_fill_unique_itr<T, Size_type>(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_seq_find_itr<T, Size_type>(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+ if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); }
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); }
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+template<class T, typename Size_type>
+static bool test_02b_seq_fillunique_find_itr_rserv(const std::string& type_id, const Size_type size0, const bool do_print_mem) {
+ T data;
+ REQUIRE(0 == data.get_allocator().memory_usage);
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (empty)", data); }
+
+ data.reserve(size0);
+ REQUIRE(data.size() == 0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.capacity() == size0);
+
+ test_00_seq_fill_unique_itr<T, Size_type>(data, size0);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+
+ test_00_seq_find_itr<T, Size_type>(data);
+ REQUIRE(0 != data.get_allocator().memory_usage);
+ REQUIRE(data.size() == size0);
+ if( do_print_mem ) { print_mem(type_id+" 02 (full_)", data); }
+
+ data.clear();
+ REQUIRE(data.size() == 0);
+ // if( do_print_mem ) { print_mem(type_id+" 02 (clear)", data); }
+ // REQUIRE(0 == data.get_allocator().memory_usage);
+ return data.size() == 0;
+}
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+template<class T, typename Size_type>
+static bool footprint_fillseq_list_itr(const std::string& type_id, const bool do_rserv) {
+ // test_01_seq_fill_list_itr<T, Size_type>(type_id, 25, do_rserv? 25 : 0, true);
+ test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, true);
+ if( !catch_auto_run ) {
+ test_01_seq_fill_list_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, true);
+ test_01_seq_fill_list_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, true);
+ }
+ return true;
+}
+
+template<class T, typename Size_type>
+static bool benchmark_fillseq_list_idx(const std::string& title_pre, const std::string& type_id,
+ const bool do_rserv) {
+ if( catch_perf_analysis ) {
+ test_01_seq_fill_list_idx<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false);
+ return true;
+ }
+ if( catch_auto_run ) {
+ test_01_seq_fill_list_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ return true;
+ }
+ // BENCHMARK(title_pre+" FillSeq_List 25") {
+ // return test_01_seq_fill_list_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false);
+ // };
+ BENCHMARK(title_pre+" FillSeq_List 50") {
+ return test_01_seq_fill_list_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillSeq_List 100") {
+ return test_01_seq_fill_list_idx<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillSeq_List 1000") {
+ return test_01_seq_fill_list_idx<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false);
+ };
+ return true;
+}
+template<class T, typename Size_type>
+static bool benchmark_fillseq_list_itr(const std::string& title_pre, const std::string& type_id,
+ const bool do_rserv) {
+ if( catch_perf_analysis ) {
+ test_01_seq_fill_list_itr<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false);
+ return true;
+ }
+ if( catch_auto_run ) {
+ test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ return true;
+ }
+ // BENCHMARK(title_pre+" FillSeq_List 25") {
+ // return test_01_seq_fill_list_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false);
+ // };
+ BENCHMARK(title_pre+" FillSeq_List 50") {
+ return test_01_seq_fill_list_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillSeq_List 100") {
+ return test_01_seq_fill_list_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillSeq_List 1000") {
+ return test_01_seq_fill_list_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false);
+ };
+ return true;
+}
+
+template<class T, typename Size_type>
+static bool benchmark_fillunique_find_idx(const std::string& title_pre, const std::string& type_id,
+ const bool do_rserv) {
+ if( catch_perf_analysis ) {
+ test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false);
+ return true;
+ }
+ if( catch_auto_run ) {
+ test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ return true;
+ }
+ // BENCHMARK(title_pre+" FillUni_List 25") {
+ // return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false);
+ // };
+ BENCHMARK(title_pre+" FillUni_List 50") {
+ return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 100") {
+ return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 1000") {
+ return test_02_seq_fillunique_find_idx<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false);
+ };
+ return true;
+}
+template<class T, typename Size_type>
+static bool benchmark_fillunique_find_itr(const std::string& title_pre, const std::string& type_id,
+ const bool do_rserv) {
+ if( catch_perf_analysis ) {
+ BENCHMARK(title_pre+" FillUni_List 1000") {
+ return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false);
+ };
+ // test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 100000, do_rserv? 100000 : 0, false);
+ return true;
+ }
+ if( catch_auto_run ) {
+ test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ return true;
+ }
+ // BENCHMARK(title_pre+" FillUni_List 25") {
+ // return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 25, do_rserv? 25 : 0, false);
+ // };
+ BENCHMARK(title_pre+" FillUni_List 50") {
+ return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 50, do_rserv? 50 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 100") {
+ return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 100, do_rserv? 100 : 0, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 1000") {
+ return test_02_seq_fillunique_find_itr<T, Size_type>(type_id, 1000, do_rserv? 1000 : 0, false);
+ };
+ return true;
+}
+template<class T, typename Size_type>
+static bool benchmark_fillunique_find_itr_rserv(const std::string& title_pre, const std::string& type_id) {
+ if( catch_perf_analysis ) {
+ BENCHMARK(title_pre+" FillUni_List 1000") {
+ return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 1000, false);
+ };
+ // test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 100000, false);
+ return true;
+ }
+ if( catch_auto_run ) {
+ test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 50, false);
+ return true;
+ }
+ // BENCHMARK(title_pre+" FillUni_List 25") {
+ // return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 25, false);
+ // };
+ BENCHMARK(title_pre+" FillUni_List 50") {
+ return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 50, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 100") {
+ return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 100, false);
+ };
+ BENCHMARK(title_pre+" FillUni_List 1000") {
+ return test_02b_seq_fillunique_find_itr_rserv<T, Size_type>(type_id, 1000, false);
+ };
+ return true;
+}
+
+/****************************************************************************************
+ ****************************************************************************************/
+
+TEST_CASE( "Memory Footprint 01 - Fill Sequential and List", "[datatype][footprint]" ) {
+ if( catch_perf_analysis ) {
+ return;
+ }
+ footprint_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("stdvec_empty_", false);
+ footprint_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("darray_empty_", false);
+ footprint_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("cowstdvec_empty_", false);
+ footprint_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("cowdarray_empty_", false);
+
+#if 0
+ footprint_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("stdvec_rserv", true);
+ footprint_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("darray_rserv", true);
+ footprint_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("cowstdvec_rserv", true);
+ footprint_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("cowdarray_rserv", true);
+#endif
+}
+
+TEST_CASE( "Perf Test 01 - Fill Sequential and List, empty and reserve", "[datatype][sequential]" ) {
+ if( catch_perf_analysis ) {
+#if 0
+ benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false);
+ benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>, jau::nsize_t>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false);
+#endif
+ return;
+ }
+ benchmark_fillseq_list_idx< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_idx", "stdvec_empty_", false);
+ benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false);
+
+ benchmark_fillseq_list_idx< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_idx", "darray_empty_", false);
+ benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>, jau::nsize_t>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false);
+
+ // benchmark_fillseq_list_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_idx", "cowstdvec_empty_", false);
+ benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false);
+
+ // benchmark_fillseq_list_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_idx", "cowdarray_empty_", false);
+ benchmark_fillseq_list_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_itr", "cowdarray_empty_", false);
+
+ benchmark_fillseq_list_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_rserv_itr", "stdvec_rserv", true);
+ benchmark_fillseq_list_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_rserv_itr", "darray_rserv", true);
+ benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv", true);
+ benchmark_fillseq_list_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv", true);
+}
+
+TEST_CASE( "Perf Test 02 - Fill Unique and List, empty and reserve", "[datatype][unique]" ) {
+ if( catch_perf_analysis ) {
+#if 1
+ // benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false);
+ // benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_empty_itr", "cowdarray_empty_", false);
+
+ benchmark_fillunique_find_itr_rserv< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv_");
+ benchmark_fillunique_find_itr_rserv< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_rserv_itr", "cowdarray_rserv_");
+
+ benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false);
+ benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_DArray_empty_itr", "cowdarray_empty_", false);
+
+#endif
+ return;
+ }
+ benchmark_fillunique_find_idx< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_idx", "stdvec_empty_", false);
+
+ benchmark_fillunique_find_itr< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_empty_itr", "stdvec_empty_", false);
+
+ benchmark_fillunique_find_idx< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_idx", "darray_empty_", false);
+ benchmark_fillunique_find_itr< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_empty_itr", "darray_empty_", false);
+
+ // benchmark_fillunique_find_idx< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_idx", "cowstdvec_empty_", false);
+ benchmark_fillunique_find_itr< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_empty_itr", "cowstdvec_empty_", false);
+
+ // benchmark_fillunique_find_idx< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_idx", "cowdarray_empty_", false);
+ benchmark_fillunique_find_itr< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_empty_itr", "cowdarray_empty_", false);
+
+#if 1
+ benchmark_fillunique_find_itr_rserv< std::vector<DataType01, counting_allocator<DataType01>>, std::size_t >("STD_Vector_rserv_itr", "stdvec_rserv");
+ benchmark_fillunique_find_itr_rserv< jau::darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("JAU_DArray_rserv_itr", "darray_rserv");
+ benchmark_fillunique_find_itr_rserv< jau::cow_vector<DataType01, counting_allocator<DataType01>>, std::size_t >("COW_Vector_rserv_itr", "cowstdvec_rserv");
+ benchmark_fillunique_find_itr_rserv< jau::cow_darray<DataType01, counting_allocator<DataType01>>, jau::nsize_t >("COW_DArray_rserv_itr", "cowdarray_rserv");
+#endif
+}
+
diff --git a/test/test_cowvector_perf01.cpp b/test/test_cowvector_perf01.cpp
deleted file mode 100644
index b20520f..0000000
--- a/test/test_cowvector_perf01.cpp
+++ /dev/null
@@ -1,340 +0,0 @@
-/*
- * Author: Sven Gothel <[email protected]>
- * 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.
- */
-#include <iostream>
-#include <cassert>
-#include <cinttypes>
-#include <cstring>
-#include <random>
-#include <vector>
-
-#define CATCH_CONFIG_RUNNER
-// #define CATCH_CONFIG_MAIN
-#include <catch2/catch_amalgamated.hpp>
-#include <jau/test/catch2_ext.hpp>
-
-#include "test_datatype01.hpp"
-
-#include <jau/basic_types.hpp>
-#include <jau/cow_vector.hpp>
-#include <jau/counting_allocator.hpp>
-
-using namespace jau;
-
-static uint8_t start_addr_b[] = {0x20, 0x26, 0x2A, 0x01, 0x20, 0x10};
-static Addr48Bit start_addr(start_addr_b);
-
-typedef std::vector<DataType01, counting_allocator<DataType01>> DataType01Vector;
-
-template<class T>
-DataType01 * findDataSet01(T& data, DataType01 const & elem) noexcept {
- const size_t size = data.size();
- for (size_t i = 0; i < size; i++) {
- DataType01 & e = data[i];
- if ( elem == e ) {
- return &e;
- }
- }
- return nullptr;
-}
-
-template<class T>
-static void test_00_list(T& data, const bool show) {
- const std::size_t size = data.size();
- for (std::size_t i = 0; i < size; i++) {
- DataType01 & e = data[i];
- e.nop();
- if( show ) {
- printf("data[%zu]: %s\n", i, e.toString().c_str());
- }
- }
-}
-
-template<class T>
-static void test_00_seq_find_each(T& data, const bool show) {
- Addr48Bit a0(start_addr);
- const std::size_t size = data.size();
- std::size_t fi = 0, i=0;
-
- for(; i<size && a0.next(); i++) {
- DataType01 elem(a0, static_cast<uint8_t>(1));
- DataType01 *found = findDataSet01(data, elem);
- if( nullptr != found ) {
- fi++;
- found->nop();
- if( show ) {
- printf("data[%zu, %zu]: %s\n", i, fi, found->toString().c_str());
- }
- }
- }
- REQUIRE(fi == i);
-}
-
-template<class T>
-static void test_00_seq_fill(T& data, const std::size_t size) {
- // data.reserve(size);
- Addr48Bit a0(start_addr);
- std::size_t i=0;
-
- for(; i<size && a0.next(); i++) {
- DataType01 elem(a0, static_cast<uint8_t>(1));
- data.push_back( elem );
- }
- if( i != data.size() ) {
- test_00_list(data, true);
- printf("a0 %s\n", a0.toString().c_str());
- printf("Size %zu, expected %zu, iter %zu\n", data.size(), size, i);
- }
- REQUIRE(i == data.size());
-}
-
-template<class T>
-static void test_00_seq_fill_unique(T& data, const std::size_t size) {
- // data.reserve(size);
- Addr48Bit a0(start_addr);
- std::size_t i=0, fi=0;
-
- for(; i<size && a0.next(); i++) {
- DataType01 elem(a0, static_cast<uint8_t>(1));
- DataType01* exist = findDataSet01(data, elem);
- if( nullptr == exist ) {
- data.push_back(elem);
- fi++;
- } else {
- printf("Not unique #%zu: %s == %s (%d)\n", i, elem.toString().c_str(), exist->toString().c_str(), (elem == *exist));
- }
- }
- if( fi != size ) {
- test_00_list(data, true);
- printf("a0 %s\n", a0.toString().c_str());
- printf("Size %zu, expected %zu, iter %zu\n", data.size(), size, i);
- }
- REQUIRE(i == data.size());
- REQUIRE(fi == size);
-}
-
-template<class T>
-static void print_mem(const std::string& pre, const T& data) {
- std::size_t bytes_element = sizeof(DataType01);
- std::size_t elements = data.size();
- std::size_t bytes_net = elements * bytes_element;
- std::size_t bytes_total = data.get_allocator().memory_usage;
- double overhead = 0 == bytes_total ? 0.0 : ( 0 == bytes_net ? 10.0 : (double)bytes_total / (double)bytes_net );
- printf("Mem: %s: Elements %s x %zu bytes; %s, %lf ratio\n",
- pre.c_str(), int64DecString(elements, ',', 5).c_str(),
- bytes_element, data.get_allocator().toString(10, 5).c_str(), overhead);
- // 5: 1,000
- // 7: 100,000
- // 9: 1,000,000
-}
-
-static bool test_stdvec_01_seq_fill_list_clear(const std::size_t size0, const bool do_print_mem) {
- std::vector<DataType01, counting_allocator<DataType01>> data;
- REQUIRE(0 == data.get_allocator().memory_usage);
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("stdvec_01 (empty)", data); }
-
- test_00_seq_fill(data, size0);
- REQUIRE(data.size() == size0);
-
- test_00_list(data, false);
- REQUIRE(data.size() == size0);
- if( do_print_mem ) { print_mem("stdvec_01 (full_)", data); }
-
- data.clear();
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("stdvec_01 (clear)", data); }
- // REQUIRE(0 == data.get_allocator().memory_usage);
- return data.size() == 0;
-}
-
-static bool test_stdvec_02_seq_fillunique_findeach_clear(const std::size_t size0, const bool do_print_mem) {
- std::vector<DataType01, counting_allocator<DataType01>> data;
- REQUIRE(0 == data.get_allocator().memory_usage);
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("stdvec_02 (empty)", data); }
-
- test_00_seq_fill_unique(data, size0);
- REQUIRE(data.size() == size0);
-
- test_00_seq_find_each(data, false);
- REQUIRE(data.size() == size0);
- if( do_print_mem ) { print_mem("stdvec_02 (full_)", data); }
-
- data.clear();
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("stdvec_02 (clear)", data); }
- // REQUIRE(0 == data.get_allocator().memory_usage);
- return data.size() == 0;
-}
-
-static bool test_cowvec_11_seq_fill_list_clear(const std::size_t size0, const bool do_print_mem) {
- jau::cow_vector<DataType01, counting_allocator<DataType01>> data;
- REQUIRE(0 == data.get_allocator().memory_usage);
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("cowvec_11 (empty)", data); }
-
- test_00_seq_fill(data, size0);
- REQUIRE(data.size() == size0);
- if( do_print_mem ) { print_mem("cowvec_11 (full_)", data); }
-
- test_00_list(data, false);
- REQUIRE(data.size() == size0);
-
- data.clear();
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("cowvec_11 (clear)", data); }
- // REQUIRE(0 == data.get_allocator().memory_usage);
- return data.size() == 0;
-}
-
-static bool test_cowvec_12_seq_fillunique_findeach_clear(const std::size_t size0, const bool do_print_mem) {
- jau::cow_vector<DataType01, counting_allocator<DataType01>> data;
- REQUIRE(0 == data.get_allocator().memory_usage);
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("cowvec_12 (empty)", data); }
-
- test_00_seq_fill_unique(data, size0);
- REQUIRE(data.size() == size0);
- if( do_print_mem ) { print_mem("cowvec_12 (full_)", data); }
-
- test_00_seq_find_each(data, false);
- REQUIRE(data.size() == size0);
-
- data.clear();
- REQUIRE(data.size() == 0);
- // if( do_print_mem ) { print_mem("cowvec_12 (clear)", data); }
- // REQUIRE(0 == data.get_allocator().memory_usage);
- return data.size() == 0;
-}
-
-TEST_CASE( "STD Vector Perf Test 01 - Fill Sequential and List", "[datatype][std][vector]" ) {
- test_stdvec_01_seq_fill_list_clear(25, true);
- test_stdvec_01_seq_fill_list_clear(50, true);
- if( !catch_auto_run ) {
- test_stdvec_01_seq_fill_list_clear(100, true);
- test_stdvec_01_seq_fill_list_clear(200, true);
- test_stdvec_01_seq_fill_list_clear(1000, true);
- }
-
- BENCHMARK("Seq_List 25") {
- return test_stdvec_01_seq_fill_list_clear(25, false);
- };
- BENCHMARK("Seq_List 50") {
- return test_stdvec_01_seq_fill_list_clear(50, false);
- };
- if( !catch_auto_run ) {
- BENCHMARK("Seq_List 100") {
- return test_stdvec_01_seq_fill_list_clear(100, false);
- };
- BENCHMARK("Seq_List 200") {
- return test_stdvec_01_seq_fill_list_clear(200, false);
- };
- BENCHMARK("Seq_List 1000") {
- return test_stdvec_01_seq_fill_list_clear(1000, false);
- };
- }
-}
-TEST_CASE( "COW Vector Perf Test 11 - Fill Sequential and List", "[datatype][cow][vector]" ) {
- test_cowvec_11_seq_fill_list_clear(25, true);
- test_cowvec_11_seq_fill_list_clear(50, true);
- if( !catch_auto_run ) {
- test_cowvec_11_seq_fill_list_clear(100, true);
- test_cowvec_11_seq_fill_list_clear(200, true);
- test_cowvec_11_seq_fill_list_clear(1000, true);
- }
-
- BENCHMARK("Seq_List 25") {
- return test_cowvec_11_seq_fill_list_clear(25, false);
- };
- BENCHMARK("Seq_List 50") {
- return test_cowvec_11_seq_fill_list_clear(50, false);
- };
- if( !catch_auto_run ) {
- BENCHMARK("Seq_List 100") {
- return test_cowvec_11_seq_fill_list_clear(100, false);
- };
- BENCHMARK("Seq_List 200") {
- return test_cowvec_11_seq_fill_list_clear(200, false);
- };
- BENCHMARK("Seq_List 1000") {
- return test_cowvec_11_seq_fill_list_clear(1000, false);
- };
- }
-}
-
-TEST_CASE( "STD Vector Perf Test 02 - Fill Unique and Find-Each", "[datatype][std][vector]" ) {
- test_stdvec_02_seq_fillunique_findeach_clear(25, true);
- test_stdvec_02_seq_fillunique_findeach_clear(50, true);
- if( !catch_auto_run ) {
- test_stdvec_02_seq_fillunique_findeach_clear(100, true);
- test_stdvec_02_seq_fillunique_findeach_clear(200, true);
- test_stdvec_02_seq_fillunique_findeach_clear(1000, true);
- }
-
- BENCHMARK("Unique Find 25") {
- return test_stdvec_02_seq_fillunique_findeach_clear(25, false);
- };
- BENCHMARK("Unique Find 50") {
- return test_stdvec_02_seq_fillunique_findeach_clear(50, false);
- };
- if( !catch_auto_run ) {
- BENCHMARK("Unique Find 100") {
- return test_stdvec_02_seq_fillunique_findeach_clear(100, false);
- };
- BENCHMARK("Unique Find 200") {
- return test_stdvec_02_seq_fillunique_findeach_clear(200, false);
- };
- BENCHMARK("Unique Find 1000") {
- return test_stdvec_02_seq_fillunique_findeach_clear(1000, false);
- };
- }
-}
-TEST_CASE( "COW Vector Perf Test 12 - Fill Unique and Find-Each", "[datatype][cow][vector]" ) {
- test_cowvec_12_seq_fillunique_findeach_clear(25, true);
- test_cowvec_12_seq_fillunique_findeach_clear(50, true);
- if( !catch_auto_run ) {
- test_cowvec_12_seq_fillunique_findeach_clear(100, true);
- test_cowvec_12_seq_fillunique_findeach_clear(200, true);
- test_cowvec_12_seq_fillunique_findeach_clear(1000, true);
- }
-
- BENCHMARK("Unique Find 25") {
- return test_cowvec_12_seq_fillunique_findeach_clear(25, false);
- };
- BENCHMARK("Unique Find 50") {
- return test_cowvec_12_seq_fillunique_findeach_clear(50, false);
- };
- if( !catch_auto_run ) {
- BENCHMARK("Unique Find 100") {
- return test_cowvec_12_seq_fillunique_findeach_clear(100, false);
- };
- BENCHMARK("Unique Find 200") {
- return test_cowvec_12_seq_fillunique_findeach_clear(200, false);
- };
- BENCHMARK("Unique Find 1000") {
- return test_cowvec_12_seq_fillunique_findeach_clear(1000, false);
- };
- }
-}
-
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-11 09:42:57 +0000