diff options
Diffstat (limited to 'include/jau')
| -rw-r--r-- | include/jau/cow_darray.hpp | 138 | ||||
| -rw-r--r-- | include/jau/cow_iterator.hpp | 41 | ||||
| -rw-r--r-- | include/jau/cow_vector.hpp | 89 | ||||
| -rw-r--r-- | include/jau/darray.hpp | 365 |
4 files changed, 367 insertions, 266 deletions
diff --git a/include/jau/cow_darray.hpp b/include/jau/cow_darray.hpp index cfcae18..da4c33c 100644 --- a/include/jau/cow_darray.hpp +++ b/include/jau/cow_darray.hpp @@ -28,6 +28,7 @@ #include <cstring> #include <string> #include <cstdint> +#include <limits> #include <atomic> #include <memory> #include <mutex> @@ -78,7 +79,7 @@ namespace jau { * </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 + * 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> @@ -99,8 +100,22 @@ namespace jau { class cow_darray { public: - typedef darray<Value_type, Alloc_type, Size_type> storage_t; - typedef std::shared_ptr<storage_t> storage_ref_t; + /** Default growth factor using the golden ratio 1.618 */ + constexpr static const float DEFAULT_GROWTH_FACTOR = 1.618f; + + // std container conform typedefs' + + typedef Value_type value_type; + // typedef value_type* pointer; + // typedef const value_type* const_pointer; + // typedef value_type& reference; + // typedef const value_type& const_reference; + typedef Size_type size_type; + typedef typename std::make_signed<size_type>::type difference_type; + typedef Alloc_type allocator_type; + + typedef darray<value_type, allocator_type, size_type> storage_t; + typedef std::shared_ptr<storage_t> storage_ref_t; /** * Immutable, read-only const_iterator, lock-free, @@ -109,7 +124,7 @@ namespace jau { * Using jau::cow_darray::get_snapshot() at construction. * </p> */ - typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator; + typedef cow_ro_iterator<value_type, storage_t, storage_ref_t, size_type> const_iterator; /** * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. @@ -118,12 +133,14 @@ namespace jau { * and jau::cow_darray::set_store() at destruction. * </p> */ - typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_darray> iterator; + typedef cow_rw_iterator<value_type, storage_t, storage_ref_t, cow_darray, size_type> iterator; - /** Default growth factor using the golden ratio 1.618 */ - inline static const float DEFAULT_GROWTH_FACTOR = 1.618f; + // typedef std::reverse_iterator<iterator> reverse_iterator; + // typedef std::reverse_iterator<const_iterator> const_reverse_iterator; private: + static constexpr size_type DIFF_MAX = std::numeric_limits<difference_type>::max(); + storage_ref_t store_ref; sc_atomic_bool sync_atomic; std::recursive_mutex mtx_write; @@ -141,9 +158,9 @@ namespace jau { * 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 + * @param alloc given allocator_type */ - constexpr explicit cow_darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + constexpr explicit cow_darray(size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared<storage_t>(capacity, growth_factor, alloc)), sync_atomic(false) {} // conversion ctor on storage_t elements @@ -151,13 +168,13 @@ namespace jau { 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) + constexpr explicit cow_darray(const storage_t& x, const float growth_factor, const allocator_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 + constexpr explicit cow_darray(storage_t && x, const float growth_factor, const allocator_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 @@ -182,9 +199,9 @@ namespace jau { * 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 + * @param alloc custom allocator_type instance */ - constexpr explicit cow_darray(const cow_darray& x, const float growth_factor, const Alloc_type& alloc) + constexpr explicit cow_darray(const cow_darray& x, const float growth_factor, const allocator_type& alloc) : sync_atomic(false) { storage_ref_t x_store_ref; { @@ -198,14 +215,14 @@ namespace jau { * 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> + * Throws jau::IllegalArgumentException() if <code>_capacity < x.size()</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 + * @param alloc custom allocator_type instance */ - constexpr explicit cow_darray(const cow_darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc) + constexpr explicit cow_darray(const cow_darray& x, const size_type _capacity, const float growth_factor, const allocator_type& alloc) : sync_atomic(false) { storage_ref_t x_store_ref; { @@ -229,45 +246,54 @@ namespace jau { /** * 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>. + * 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> + * 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 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 + * @param alloc custom allocator_type instance */ - constexpr cow_darray(const Size_type _capacity, const_iterator first, const_iterator last, - const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + constexpr cow_darray(const size_type _capacity, const_iterator first, const_iterator last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared<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>. + * 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> + * 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 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 + * @param alloc custom allocator_type instance */ template< class InputIt > - constexpr explicit cow_darray(const Size_type _capacity, InputIt first, InputIt last, - const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + constexpr explicit cow_darray(const size_type _capacity, InputIt first, InputIt last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : store_ref(std::make_shared<storage_t>(_capacity, first, last, growth_factor, alloc)), sync_atomic(false) { } ~cow_darray() noexcept { } + /** + * Returns <code>std::numeric_limits<difference_type>::max()</code> as the maximum array size. + * <p> + * We rely on the signed <code>difference_type</code> for pointer arithmetic, + * deducing ranges from iterator. + * </p> + */ + constexpr size_type max_size() const noexcept { return DIFF_MAX; } + // cow_vector features /** @@ -381,17 +407,17 @@ namespace jau { // read access - const Alloc_type& get_allocator_ref() const noexcept { + const allocator_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 { + allocator_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 { + constexpr size_type capacity() const noexcept { sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); return store_ref->capacity(); } @@ -413,7 +439,7 @@ namespace jau { * This read operation is <i>lock-free</i>. * </p> */ - constexpr Size_type size() const noexcept { + constexpr size_type size() const noexcept { sc_atomic_critical sync( const_cast<cow_darray *>(this)->sync_atomic ); return store_ref->size(); } @@ -430,7 +456,7 @@ namespace jau { * This write operation uses a mutex lock and is blocking this instances' write operations only. * </p> */ - void reserve(Size_type new_capacity) { + 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() ) { @@ -574,7 +600,7 @@ namespace jau { * </p> * @param x the value to be added at the tail. */ - void push_back(const Value_type& x) { + 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() ) { @@ -599,7 +625,7 @@ namespace jau { * This write operation uses a mutex lock and is blocking this instances' write operations only. * </p> */ - void push_back(Value_type&& x) { + 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() ) { @@ -619,19 +645,19 @@ namespace jau { } /** - * Like std::vector::push_back(), but appends the whole Value_type range [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> - * @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) + * @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); + 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 @@ -650,17 +676,17 @@ namespace jau { } /** - * Like std::vector::push_back(), but appends the whole Value_type range [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) + * @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); + 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 @@ -679,12 +705,12 @@ namespace jau { } /** - * Generic Value_type equal comparator to be user defined for e.g. jau::cow_darray::push_back_unique(). + * 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); + 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. @@ -710,7 +736,7 @@ namespace jau { * @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) { + 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 ) ) { @@ -747,7 +773,7 @@ namespace jau { * @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 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 ); @@ -770,7 +796,7 @@ namespace jau { } /** - * Thread safe Value_type copy assignment to Value_type at given position with bounds checking. + * 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> @@ -780,7 +806,7 @@ namespace jau { * @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) { + void put(size_type 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; @@ -791,7 +817,7 @@ namespace jau { } /** - * Thread safe Value_type move assignment to Value_type at given position with bounds checking. + * 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> @@ -801,7 +827,7 @@ namespace jau { * @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) { + void put(size_type 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); diff --git a/include/jau/cow_iterator.hpp b/include/jau/cow_iterator.hpp index 8ebd9c1..5775a24 100644 --- a/include/jau/cow_iterator.hpp +++ b/include/jau/cow_iterator.hpp @@ -26,6 +26,7 @@ #define JAU_COW_ITERATOR_HPP_ #include <cstddef> +#include <limits> #include <mutex> namespace jau { @@ -34,7 +35,7 @@ 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> + template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename Size_type> class cow_ro_iterator { private: @@ -42,6 +43,9 @@ namespace jau { typename Storage_type::const_iterator iterator_; public: + typedef Size_type size_type; + typedef typename std::make_signed<Size_type>::type difference_type; + constexpr cow_ro_iterator(Storage_ref_type store, typename Storage_type::const_iterator iter) : store_holder_(store), iterator_(iter) {} @@ -99,29 +103,29 @@ namespace jau { // Random access iterator requirements /** Subscript of 'element_index', returning immutable Value_type reference. */ - constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept + constexpr const Value_type& operator[](difference_type 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 + constexpr cow_ro_iterator& operator+=(difference_type 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 + constexpr cow_ro_iterator operator+(difference_type 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 + constexpr cow_ro_iterator& operator-=(difference_type 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 + constexpr cow_ro_iterator operator-(difference_type 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 + /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type difference_type. */ + constexpr difference_type operator-(const cow_ro_iterator& rhs) const noexcept { return iterator_ - rhs.iterator_; } }; @@ -133,7 +137,7 @@ namespace jau { * 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> + template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename CoW_container, typename Size_type> class cow_rw_iterator { private: @@ -146,6 +150,9 @@ namespace jau { : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(store), iterator_(iter) {} public: + typedef Size_type size_type; + typedef typename std::make_signed<Size_type>::type difference_type; + 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_)) {} @@ -216,27 +223,27 @@ namespace jau { // Random access iterator requirements /** Subscript of 'element_index', returning immutable Value_type reference. */ - constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept + constexpr const Value_type& operator[](difference_type i) const noexcept { return iterator_[i]; } /** Subscript of 'element_index', returning mutable Value_type reference. */ - constexpr Value_type& operator[](std::ptrdiff_t i) noexcept + constexpr Value_type& operator[](difference_type i) noexcept { return iterator_[i]; } /** Addition-assignment of 'element_count'; Well performing, return *this. */ - constexpr cow_rw_iterator& operator+=(std::ptrdiff_t i) noexcept + constexpr cow_rw_iterator& operator+=(difference_type 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 + constexpr cow_rw_iterator operator+(difference_type 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 + constexpr cow_rw_iterator& operator-=(difference_type 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 + constexpr cow_rw_iterator operator-(difference_type rhs) const noexcept { return cow_rw_iterator(cow_parent_, new_store_, iterator_ - rhs); } // constexpr const cow_rw_iterator& base() const noexcept @@ -244,8 +251,8 @@ namespace jau { // 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 + /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type difference_type. */ + constexpr difference_type operator-(const cow_rw_iterator& rhs) const noexcept { return iterator_ - rhs.iterator_; } }; diff --git a/include/jau/cow_vector.hpp b/include/jau/cow_vector.hpp index cc35ffa..d1a7881 100644 --- a/include/jau/cow_vector.hpp +++ b/include/jau/cow_vector.hpp @@ -29,6 +29,7 @@ #include <cstring> #include <string> #include <cstdint> +#include <limits> #include <atomic> #include <memory> #include <mutex> @@ -73,8 +74,8 @@ namespace jau { * 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 + * Index operation via ::operator[](size_type) or ::at(size_type) 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> @@ -94,8 +95,19 @@ namespace jau { class cow_vector { public: - typedef std::vector<Value_type, Alloc_type> storage_t; - typedef std::shared_ptr<storage_t> storage_ref_t; + // std container conform typedefs' + + typedef Value_type value_type; + // typedef value_type* pointer; + // typedef const value_type* const_pointer; + // typedef value_type& reference; + // typedef const value_type& const_reference; + typedef std::size_t size_type; + typedef typename std::make_signed<size_type>::type difference_type; + typedef Alloc_type allocator_type; + + typedef std::vector<value_type, allocator_type> storage_t; + typedef std::shared_ptr<storage_t> storage_ref_t; /** * Immutable, read-only const_iterator, lock-free, @@ -104,7 +116,7 @@ namespace jau { * Using jau::cow_vector::get_snapshot() at construction. * </p> */ - typedef cow_ro_iterator<Value_type, storage_t, storage_ref_t> const_iterator; + typedef cow_ro_iterator<value_type, storage_t, storage_ref_t, size_type> const_iterator; /** * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. @@ -113,9 +125,11 @@ namespace jau { * and jau::cow_vector::set_store() at destruction. * </p> */ - typedef cow_rw_iterator<Value_type, storage_t, storage_ref_t, cow_vector> iterator; + typedef cow_rw_iterator<value_type, storage_t, storage_ref_t, cow_vector, size_type> iterator; private: + static constexpr size_type DIFF_MAX = std::numeric_limits<difference_type>::max(); + storage_ref_t store_ref; sc_atomic_bool sync_atomic; std::recursive_mutex mtx_write; @@ -126,13 +140,13 @@ namespace jau { constexpr cow_vector() noexcept : store_ref( std::make_shared<storage_t>() ), sync_atomic(false) {} - constexpr explicit cow_vector(const Alloc_type & a) noexcept + constexpr explicit cow_vector(const allocator_type & a) noexcept : store_ref( std::make_shared<storage_t>(a) ), sync_atomic(false) { } - constexpr explicit cow_vector(size_t n, const Alloc_type& a = Alloc_type()) + constexpr explicit cow_vector(size_type n, const allocator_type& a = allocator_type()) : store_ref( std::make_shared<storage_t>(n, a) ), sync_atomic(false) { } - constexpr cow_vector(size_t n, const Value_type& value, const Alloc_type& a = Alloc_type()) + constexpr cow_vector(size_type n, const value_type& value, const allocator_type& a = allocator_type()) : store_ref( std::make_shared<storage_t>(n, value, a) ), sync_atomic(false) { } constexpr cow_vector(const cow_vector& x) @@ -158,6 +172,15 @@ namespace jau { ~cow_vector() noexcept { } + /** + * Returns <code>std::numeric_limits<difference_type>::max()</code> as the maximum array size. + * <p> + * We rely on the signed <code>difference_type</code> for pointer arithmetic, + * deducing ranges from iterator. + * </p> + */ + constexpr size_type max_size() const noexcept { return DIFF_MAX; } + // cow_vector features /** @@ -271,12 +294,12 @@ namespace jau { // read access - Alloc_type get_allocator() const noexcept { + allocator_type get_allocator() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->get_allocator(); } - constexpr std::size_t capacity() const noexcept { + constexpr size_type capacity() const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->capacity(); } @@ -298,62 +321,62 @@ namespace jau { * This read operation is <i>lock-free</i>. * </p> */ - constexpr size_t size() const noexcept { + constexpr size_type 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). + * Like std::vector::operator[](size_type). * <p> * This read operation is <i>lock-free</i>. * </p> */ - const Value_type & operator[](size_t i) const noexcept { + const value_type & operator[](size_type i) const noexcept { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return (*store_ref)[i]; } /** - * Like std::vector::operator[](size_t). + * Like std::vector::operator[](size_type). * <p> * This read operation is <i>lock-free</i>. * </p> * <p> - * Mutation of the resulting Value_type + * Mutation of the resulting value_type * is not synchronized via this cow_vector instance. * </p> * @see put() */ - Value_type & operator[](size_t i) noexcept { + value_type & operator[](size_type i) noexcept { sc_atomic_critical sync(sync_atomic); return (*store_ref)[i]; } /** - * Like std::vector::at(size_t). + * Like std::vector::at(size_type). * <p> * This read operation is <i>lock-free</i>. * </p> */ - const Value_type & at(size_t i) const { + const value_type & at(size_type i) const { sc_atomic_critical sync( const_cast<cow_vector *>(this)->sync_atomic ); return store_ref->at(i); } /** - * Like std::vector::at(size_t). + * Like std::vector::at(size_type). * <p> * This read operation is <i>lock-free</i>. * </p> * <p> - * Mutation of the resulting Value_type + * Mutation of the resulting value_type * is not synchronized via this cow_vector instance. * </p> * @see put() */ - Value_type & at(size_t i) { + value_type & at(size_type i) { sc_atomic_critical sync(sync_atomic); return store_ref->at(i); } @@ -361,7 +384,7 @@ namespace jau { // write access - void reserve(std::size_t new_capacity) { + 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() ) { @@ -473,7 +496,7 @@ namespace jau { * </p> * @param x the value to be added at the tail. */ - void push_back(const Value_type& x) { + void push_back(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, store_ref->get_allocator() ); new_store_ref->push_back(x); @@ -489,7 +512,7 @@ namespace jau { * This write operation uses a mutex lock and is blocking this instances' write operations only. * </p> */ - void push_back(Value_type&& x) { + void push_back(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, store_ref->get_allocator() ); new_store_ref->push_back( std::move(x) ); @@ -500,12 +523,12 @@ namespace jau { } /** - * Generic Value_type equal comparator to be user defined for e.g. jau::cow_vector::push_back_unique(). + * Generic value_type equal comparator to be user defined for e.g. jau::cow_vector::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); + 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. @@ -531,7 +554,7 @@ namespace jau { * @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) { + 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 ) ) { @@ -573,7 +596,7 @@ namespace jau { * @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 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, store_ref->get_allocator() ); @@ -596,7 +619,7 @@ namespace jau { } /** - * Thread safe Value_type copy assignment to Value_type at given position with bounds checking. + * 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> @@ -606,7 +629,7 @@ namespace jau { * @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) { + void put(size_type 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, store_ref->get_allocator() ); new_store_ref->at(i) = x; @@ -617,7 +640,7 @@ namespace jau { } /** - * Thread safe Value_type move assignment to Value_type at given position with bounds checking. + * 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> @@ -627,7 +650,7 @@ namespace jau { * @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) { + void put(size_type 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, store_ref->get_allocator() ); new_store_ref->at(i) = std::move(x); diff --git a/include/jau/darray.hpp b/include/jau/darray.hpp index dc81b60..835ac6d 100644 --- a/include/jau/darray.hpp +++ b/include/jau/darray.hpp @@ -28,6 +28,7 @@ #include <cstring> #include <string> #include <cstdint> +#include <limits> #include <atomic> #include <memory> #include <mutex> @@ -57,7 +58,7 @@ namespace jau { * <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><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> @@ -65,10 +66,10 @@ namespace jau { * <p> * Implementation differences to std::vector and some details * <ul> - * <li>Using zero overhead <i>Value_type*</i> as iterator type.</li> + * <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> + * <li>Constructs and destructs value_type via <i>placement new</i> within the pre-allocated array capacity. Latter is managed via allocator_type.</li> * </ul> * </p> */ @@ -77,102 +78,137 @@ namespace jau { { 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; + constexpr static const float DEFAULT_GROWTH_FACTOR = 1.618f; + + // std container conform typedefs' + + typedef Value_type value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef value_type* iterator; + typedef const value_type* const_iterator; + typedef Size_type size_type; + typedef typename std::make_signed<size_type>::type difference_type; + // typedef std::reverse_iterator<iterator> reverse_iterator; + // typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef Alloc_type allocator_type; private: - inline static void freeStore(Alloc_type& alloc, Value_type *ptr, const Size_type size) { + static constexpr size_type DIFF_MAX = std::numeric_limits<difference_type>::max(); + + constexpr static void freeStore(allocator_type& alloc, value_type *ptr, const size_type size_) { if( nullptr != ptr ) { - alloc.deallocate(ptr, size); + 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); + /** + * Allocates a new store using allocator_type. + * <p> + * Throws jau::IllegalArgumentException() if size_ > <code>std::numeric_limits<difference_type>::max()</code>, i.e. difference_type maximum. + * </p> + * <p> + * Throws jau::OutOfMemoryError() if allocator_type::allocate() returns nullptr. + * </p> + * @param alloc the allocator_type instance + * @param size_ the element count, must be <= <code>std::numeric_limits<difference_type>::max()</code> + * @return nullptr if given <code>0 == size_</code> or the newly allocated memory + */ + constexpr static value_type * allocStore(allocator_type& alloc, const size_type size_) { + if( 0 != size_ ) { + if( size_ > DIFF_MAX ) { + throw jau::IllegalArgumentException("allocData "+std::to_string(size_)+" > difference_type max "+ + std::to_string(DIFF_MAX), E_FILE_LINE); + } + 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); + throw jau::OutOfMemoryError("alloc "+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_; + allocator_type alloc_inst; + pointer begin_; + pointer end_; + pointer storage_end_; - constexpr void set_iterator(array_ref new_storage_, Size_type size_, Size_type capacity_) noexcept { + constexpr void set_iterator(pointer new_storage_, difference_type size_, difference_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 { + constexpr void set_iterator(difference_type size_, difference_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; + constexpr size_type dtor_range(iterator first, const_iterator last) { + size_type count=0; for(; first < last; ++first, ++count ) { - ( first )->~Value_type(); // placement new -> manual destruction! + ( 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) { + constexpr static void ctor_copy_range(pointer dest, iterator first, const_iterator last) { for(; first < last; ++dest, ++first) { - new (dest) Value_type( *first ); // placement new + 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); + constexpr static pointer clone_range(allocator_type& alloc, const_iterator first, const_iterator last) { + pointer dest = allocStore(alloc, size_type(last-first)); 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)); + constexpr static pointer clone_range(allocator_type& alloc, const size_type dest_capacity, iterator first, const_iterator last) { + if( first > last ) { + throw jau::IllegalArgumentException("first "+aptrHexString(first)+" > last "+aptrHexString(last), E_FILE_LINE); + } + if( dest_capacity < size_type(last-first) ) { + throw jau::IllegalArgumentException("capacity "+std::to_string(dest_capacity)+" < source range "+ + std::to_string(difference_type(last-first)), E_FILE_LINE); + } + pointer dest = allocStore(alloc, dest_capacity); 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) { + constexpr static void ctor_copy_range_foreign(pointer dest, InputIt first, InputIt last) { for(; first < last; ++dest, ++first) { - new (dest) Value_type( *first ); // placement new + 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) ) { + constexpr static pointer clone_range_foreign(allocator_type& alloc, const size_type dest_capacity, InputIt first, InputIt last) { + if( first > last ) { + throw jau::IllegalArgumentException("first "+std::to_string(first)+" > last "+ + std::to_string(last), E_FILE_LINE); + } + 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); + std::to_string(difference_type(last-first)), E_FILE_LINE); } - array_ref dest = allocStore(alloc, dest_capacity); + pointer 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) { + constexpr static void ctor_move_range(pointer dest, iterator first, const_iterator last) { for(; first < last; ++dest, ++first) { - new (dest) Value_type( std::move( *first ) ); // placement new + 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); + constexpr void grow_storage_move(const size_type new_capacity) { + pointer dest = allocStore(alloc_inst, new_capacity); ctor_move_range(dest, begin_, end_); freeStore(alloc_inst, begin_, capacity()); @@ -195,9 +231,9 @@ namespace jau { * 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 + * @param alloc given allocator_type */ - constexpr explicit darray(Size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const Alloc_type& alloc = Alloc_type()) + constexpr explicit darray(size_type capacity, const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_type()) : growth_factor_( growth_factor ), alloc_inst( alloc ), begin_( allocStore(alloc_inst, capacity) ), end_( begin_ ), storage_end_( begin_ + capacity ) {} @@ -218,9 +254,9 @@ namespace jau { * 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 + * @param alloc custom allocator_type instance */ - constexpr explicit darray(const darray& x, const float growth_factor, const Alloc_type& alloc) + constexpr explicit darray(const darray& x, const float growth_factor, const allocator_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() ) { } @@ -234,9 +270,9 @@ namespace jau { * @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 + * @param alloc custom allocator_type instance */ - constexpr explicit darray(const darray& x, const Size_type _capacity, const float growth_factor, const Alloc_type& alloc) + constexpr explicit darray(const darray& x, const size_type _capacity, const float growth_factor, const allocator_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 ) { } @@ -253,7 +289,7 @@ namespace jau { x.storage_end_ = nullptr; } - constexpr explicit darray(darray && x, const float growth_factor, const Alloc_type& alloc) noexcept + constexpr explicit darray(darray && x, const float growth_factor, const allocator_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_)) { @@ -267,48 +303,57 @@ namespace jau { /** * 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>. + * 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>. + * 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 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 + * @param alloc custom allocator_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()) + constexpr darray(const size_type _capacity, const_iterator first, const_iterator last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_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 ) + 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>. + * 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>. + * 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 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 + * @param alloc custom allocator_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()) + constexpr explicit darray(const size_type _capacity, InputIt first, InputIt last, + const float growth_factor=DEFAULT_GROWTH_FACTOR, const allocator_type& alloc = allocator_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 ) + end_(begin_ + size_type(last - first) ), storage_end_( begin_ + _capacity ) { } ~darray() noexcept { clear(); } + /** + * Returns <code>std::numeric_limits<difference_type>::max()</code> as the maximum array size. + * <p> + * We rely on the signed <code>difference_type</code> for pointer arithmetic, + * deducing ranges from iterator. + * </p> + */ + constexpr size_type max_size() const noexcept { return DIFF_MAX; } + // iterator constexpr iterator begin() noexcept { return begin_; } @@ -333,28 +378,28 @@ namespace jau { // read access - const Alloc_type& get_allocator_ref() const noexcept { + const allocator_type& get_allocator_ref() const noexcept { return alloc_inst; } - Alloc_type get_allocator() const noexcept { - return Alloc_type(alloc_inst); + allocator_type get_allocator() const noexcept { + return allocator_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 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_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); + 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); } /** @@ -371,58 +416,58 @@ namespace jau { /** * Like std::vector::size(). */ - constexpr Size_type size() const noexcept { return Size_type(end_ - begin_); } + 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_; } + constexpr reference front() { return *begin_; } /** * Like std::vector::front(), immutable access. */ - constexpr const Value_type & front() const { return *begin_; } + constexpr const_reference front() const { return *begin_; } /** * Like std::vector::back(), mutable access. */ - constexpr Value_type & back() { return *(end_-1); } + constexpr reference back() { return *(end_-1); } /** * Like std::vector::back(), immutable access. */ - constexpr const Value_type & back() const { return *(end_-1); } + constexpr const_reference back() const { return *(end_-1); } /** * Like std::vector::data(), const immutable pointer */ - constexpr const Value_type* data() const noexcept { return begin_; } + constexpr const_pointer data() const noexcept { return begin_; } /** * Like std::vector::data(), mutable pointer */ - constexpr Value_type* data() noexcept { return begin_; } + constexpr pointer data() noexcept { return begin_; } /** - * Like std::vector::operator[](Size_type), immutable reference. + * Like std::vector::operator[](size_type), immutable reference. */ - const Value_type & operator[](Size_type i) const noexcept { + const_reference operator[](size_type i) const noexcept { return *(begin_+i); } /** - * Like std::vector::operator[](Size_type), mutable reference. + * Like std::vector::operator[](size_type), mutable reference. */ - Value_type & operator[](Size_type i) noexcept { + reference operator[](size_type i) noexcept { return *(begin_+i); } /** - * Like std::vector::at(Size_type), immutable reference. + * Like std::vector::at(size_type), immutable reference. */ - const Value_type & at(Size_type i) const { + const_reference at(size_type i) const { if( 0 <= i && i < size() ) { return *(begin_+i); } @@ -430,9 +475,9 @@ namespace jau { } /** - * Like std::vector::at(Size_type), mutable reference. + * Like std::vector::at(size_type), mutable reference. */ - Value_type & at(Size_type i) { + reference at(size_type i) { if( 0 <= i && i < size() ) { return *(begin_+i); } @@ -448,10 +493,10 @@ namespace jau { * is greater than the current jau::darray::capacity(). * </p> */ - void reserve(Size_type new_capacity) { - const Size_type capacity_ = capacity(); + void reserve(size_type new_capacity) { + const size_type capacity_ = capacity(); if( new_capacity > capacity_ ) { - array_ref new_storage = allocStore(alloc_inst, new_capacity); + pointer new_storage = allocStore(alloc_inst, new_capacity); ctor_move_range(new_storage, begin_, end_); freeStore(alloc_inst, begin_, capacity_); @@ -463,10 +508,10 @@ namespace jau { /** * 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(); + constexpr 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_); @@ -481,15 +526,15 @@ namespace jau { /** * 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) + * @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); + 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_); @@ -502,13 +547,13 @@ namespace jau { } /** * 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) + * @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); + 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_); @@ -523,7 +568,7 @@ namespace jau { /** * Like std::vector::operator=(&&), move. */ - darray& operator=(darray&& x) { + constexpr darray& operator=(darray&& x) noexcept { clear(); alloc_inst = std::move(x.alloc_inst); begin_ = std::move(x.begin_); @@ -541,7 +586,7 @@ namespace jau { /** * Like std::vector::clear(), but ending with zero capacity. */ - void clear() noexcept { + constexpr void clear() noexcept { dtor_range(begin_, end_); freeStore(alloc_inst, begin_, capacity()); begin_ = nullptr; @@ -552,7 +597,7 @@ namespace jau { /** * Like std::vector::swap(). */ - void swap(darray& x) noexcept { + constexpr void swap(darray& x) noexcept { std::swap(growth_factor_, x.growth_factor_); std::swap(alloc_inst, x.alloc_inst); std::swap(begin_, x.begin_); @@ -563,9 +608,9 @@ namespace jau { /** * Like std::vector::pop_back(). */ - void pop_back() noexcept { + constexpr void pop_back() noexcept { if( begin_ != end_ ) { - ( --end_ )->~Value_type(); // placement new -> manual destruction! + ( --end_ )->~value_type(); // placement new -> manual destruction! } } @@ -573,34 +618,34 @@ namespace jau { * Like std::vector::push_back(), copy * @param x the value to be added at the tail. */ - void push_back(const Value_type& x) { + constexpr void push_back(const value_type& x) { if( end_ == storage_end_ ) { grow_storage_move(grow_capacity()); } - new (end_) Value_type( x ); // placement new + new (end_) value_type( x ); // placement new ++end_; } /** * Like std::vector::push_back(), move */ - void push_back(Value_type&& x) { + constexpr void push_back(value_type&& x) { if( end_ == storage_end_ ) { grow_storage_move(grow_capacity()); } - new (end_) Value_type( std::move(x) ); // placement new + 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) + * 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); + const size_type count = size_type(last - first); if( end_ + count >= storage_end_ ) { grow_storage_move(size() + count); @@ -610,12 +655,12 @@ namespace jau { } /** - * 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) + * 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); + const size_type count = size_type(last - first); if( end_ + count >= storage_end_ ) { grow_storage_move(size() + count); @@ -635,14 +680,14 @@ namespace jau { * </p> * @param i the position of the element to be removed */ - void erase(const Size_type i) { - const Size_type size_ = size(); + constexpr void erase(const size_type i) { + const size_type size_ = size(); if( 0 <= i && i < size_ ) { - ( begin_ + i )->~Value_type(); // placement new -> manual destruction! + ( begin_ + i )->~value_type(); // placement new -> manual destruction! - const Size_type right_count = size_ - 1 - i; + const difference_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 + memmove(begin_+i, begin_+i+1, sizeof(value_type)*right_count); // move right elems one left } --end_; } else { @@ -656,10 +701,10 @@ namespace jau { */ 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; + ( pos )->~value_type(); // placement new -> manual destruction! + const difference_type right_count = ( end_ - pos ) - 1; if( 0 < right_count ) { - memmove(pos, pos+1, sizeof(Value_type)*right_count); // move right elems one left + memmove(pos, pos+1, sizeof(value_type)*right_count); // move right elems one left } --end_; } @@ -671,11 +716,11 @@ namespace jau { * @return iterator following the last removed element. */ constexpr iterator erase (const_iterator first, const_iterator last) { - const Size_type count = dtor_range(first, last); + const size_type count = dtor_range(first, last); if( count > 0 ) { - const Size_type right_count = ( end_ - last ) - 1; + const difference_type right_count = end_ - last; // last is exclusive if( 0 < right_count ) { - memmove(first, last, sizeof(Value_type)*right_count); // move right elems one left + memmove(first, last, sizeof(value_type)*right_count); // move right elems one left } end_ -= count; } @@ -693,18 +738,18 @@ namespace jau { * </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(); + constexpr 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(); + 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; + const difference_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 + memmove(begin_+i+1, begin_+i, sizeof(value_type)*right_count); // move right elems one right } - new (begin_+i) Value_type( x ); // placement new + new (begin_+i) value_type( x ); // placement new ++end_; } else { throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE); @@ -722,18 +767,18 @@ namespace jau { * </p> * @param i the position of the element to be removed */ - void insert(Size_type i, Value_type&& x) { - const Size_type size_ = size(); + void insert(size_type i, value_type&& x) { + const size_type size_ = size(); if( 0 <= i && i <= size_ ) { - const Size_type old_capacity_ = capacity(); + 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; + const difference_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 + 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 + new (begin_+i) value_type( std::move(x) ); // placement new ++end_; } else { throw jau::IndexOutOfBoundsException(i, size_, E_FILE_LINE); @@ -741,12 +786,12 @@ namespace jau { } /** - * Generic Value_type equal comparator to be user defined for e.g. jau::darray::push_back_unique(). + * 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); + 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. @@ -769,7 +814,7 @@ namespace jau { * @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) { + 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 @@ -802,7 +847,7 @@ namespace jau { * @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 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 ) ) { |