diff options
| -rw-r--r-- | include/jau/cow_darray.hpp | 4 | ||||
| -rw-r--r-- | include/jau/cow_iterator.hpp | 269 | ||||
| -rw-r--r-- | include/jau/cow_vector.hpp | 4 |
3 files changed, 237 insertions, 40 deletions
diff --git a/include/jau/cow_darray.hpp b/include/jau/cow_darray.hpp index 05d925d..64c1e89 100644 --- a/include/jau/cow_darray.hpp +++ b/include/jau/cow_darray.hpp @@ -128,7 +128,7 @@ namespace jau { * Using jau::cow_darray::get_snapshot() at construction. * </p> */ - typedef cow_ro_iterator<value_type, storage_t, storage_ref_t, size_type> const_iterator; + typedef cow_ro_iterator<storage_t, storage_ref_t> const_iterator; /** * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. @@ -137,7 +137,7 @@ namespace jau { * and jau::cow_darray::set_store() at destruction. * </p> */ - typedef cow_rw_iterator<value_type, storage_t, storage_ref_t, cow_darray, size_type> iterator; + typedef cow_rw_iterator<storage_t, storage_ref_t, cow_darray> iterator; // typedef std::reverse_iterator<iterator> reverse_iterator; // typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/include/jau/cow_iterator.hpp b/include/jau/cow_iterator.hpp index 5775a24..938edcc 100644 --- a/include/jau/cow_iterator.hpp +++ b/include/jau/cow_iterator.hpp @@ -29,33 +29,92 @@ #include <limits> #include <mutex> +#include <type_traits> + 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. + * Implementation of a Copy-On-Write (CoW) read-only iterator for immutable value_type.<br> + * Instance holds the 'shared value_type reference', Storage_ref_type, + * of the current CoW storage until destruction. + * <p> + * This iterator simply wraps the native iterator of type 'iterator_type' + * and manages the CoW related resource lifecycle. + * </p> + * <p> + * Implementation complies with iterator_category 'random_access_iterator_tag' + * </p> */ - template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename Size_type> + template <typename Storage_type, typename Storage_ref_type> class cow_ro_iterator { + public: + /** Actual const iterator type of the contained native iterator, probably a simple pointer. */ + typedef typename Storage_type::const_iterator iterator_type; private: + typedef std::iterator_traits<iterator_type> sub_traits_t; + Storage_ref_type store_holder_; - typename Storage_type::const_iterator iterator_; + iterator_type iterator_; public: - typedef Size_type size_type; - typedef typename std::make_signed<Size_type>::type difference_type; + typedef typename sub_traits_t::iterator_category iterator_category; // random_access_iterator_tag + + typedef typename Storage_type::size_type size_type; // using our template overload Size_type + typedef typename Storage_type::difference_type difference_type; // derived from our Size_type + // typedef typename Storage_type::value_type value_type; // OK + // typedef typename Storage_type::reference reference; // for some reason, the 'const' is lost + // typedef typename Storage_type::pointer pointer; // for some reason, the 'const' is lost + typedef typename sub_traits_t::value_type value_type; // OK + typedef typename sub_traits_t::reference reference; // 'const value_type &' + typedef typename sub_traits_t::pointer pointer; // 'const value_type *' + +#if 0 +// TODO ??? +#if __cplusplus > 201703L && __cpp_lib_concepts + using iterator_concept = std::__detail::__iter_concept<_Iterator>; +#endif +#endif - constexpr cow_ro_iterator(Storage_ref_type store, typename Storage_type::const_iterator iter) - : store_holder_(store), iterator_(iter) {} + public: + constexpr cow_ro_iterator(Storage_ref_type store, iterator_type iter) + : store_holder_(store), iterator_(iter) { } - constexpr explicit cow_ro_iterator(const cow_ro_iterator& o) noexcept + // C++ named requirements: LegacyIterator: CopyConstructible + constexpr cow_ro_iterator(const cow_ro_iterator& o) noexcept : store_holder_(o.store_holder_), iterator_(o.iterator_) {} + // C++ named requirements: LegacyIterator: CopyAssignable + constexpr cow_ro_iterator& operator=(const cow_ro_iterator& o) noexcept { + store_holder_ = o.store_holder_; + iterator_ = o.iterator_; + } + + // C++ named requirements: LegacyIterator: MoveConstructable + constexpr cow_ro_iterator(cow_ro_iterator && o) noexcept + : store_holder_(std::move(o.store_holder_)), iterator_(std::move(o.iterator_)) { + o.store_holder_ = nullptr; + // o.iterator_ = nullptr; + } + + // C++ named requirements: LegacyIterator: MoveAssignable + constexpr cow_ro_iterator& operator=(cow_ro_iterator&& o) noexcept { + store_holder_ = std::move(o.store_holder_); + iterator_ = std::move(o.iterator_); + o.store_holder_ = nullptr; + // o.iterator_ = nullptr; + } + + // C++ named requirements: LegacyIterator: Swappable + void swap(cow_ro_iterator& o) noexcept { + std::swap( store_holder_, o.store_holder_); + std::swap( iterator_, o.iterator_); + } + /** * Returns a copy of the underlying storage const_iterator. */ - typename Storage_type::const_iterator underling() const noexcept { return iterator_; }; + iterator_type underling() const noexcept { return iterator_; }; // Multipass guarantee equality @@ -70,12 +129,43 @@ namespace jau { constexpr bool operator!=(const cow_ro_iterator& rhs) const noexcept { return !(*this == rhs); } + // Relation + + constexpr bool operator<=(const cow_ro_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + return store_holder_ == rhs.store_holder_ && + iterator_ <= rhs.iterator_; + } + constexpr bool operator<(const cow_ro_iterator& rhs) const noexcept { + if( this == &rhs ) { + return false; + } + return store_holder_ == rhs.store_holder_ && + iterator_ < rhs.iterator_; + } + constexpr bool operator>=(const cow_ro_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + return store_holder_ == rhs.store_holder_ && + iterator_ >= rhs.iterator_; + } + constexpr bool operator>(const cow_ro_iterator& rhs) const noexcept { + if( this == &rhs ) { + return false; + } + return store_holder_ == rhs.store_holder_ && + iterator_ > rhs.iterator_; + } + // Forward iterator requirements - constexpr const Value_type& operator*() const noexcept + constexpr const reference operator*() const noexcept { return *iterator_; } - constexpr const Value_type* operator->() const noexcept + constexpr const pointer operator->() const noexcept { return iterator_; } /** Pre-increment; Well performing, return *this. */ @@ -85,7 +175,7 @@ namespace jau { } /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */ - constexpr cow_ro_iterator& operator++(int) noexcept + constexpr cow_ro_iterator operator++(int) noexcept { return cow_ro_iterator(store_holder_, iterator_++); } // Bidirectional iterator requirements @@ -97,13 +187,13 @@ namespace jau { } /** 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_--); } + constexpr cow_ro_iterator operator--(int) noexcept + { return cow_ro_iterator(store_holder_, iterator_--); } // Random access iterator requirements /** Subscript of 'element_index', returning immutable Value_type reference. */ - constexpr const Value_type& operator[](difference_type i) const noexcept + constexpr const reference operator[](difference_type i) const noexcept { return iterator_[i]; } /** Addition-assignment of 'element_count'; Well performing, return *this. */ @@ -112,7 +202,7 @@ namespace jau { /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */ constexpr cow_ro_iterator operator+(difference_type rhs) const noexcept - { return cow_iterator(store_holder_, iterator_ + rhs); } + { return cow_ro_iterator(store_holder_, iterator_ + rhs); } /** Subtraction-assignment of 'element_count'; Well performing, return *this. */ constexpr cow_ro_iterator& operator-=(difference_type i) noexcept @@ -120,7 +210,7 @@ namespace jau { /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */ constexpr cow_ro_iterator operator-(difference_type rhs) const noexcept - { return cow_iterator(store_holder_, iterator_ - rhs); } + { return cow_ro_iterator(store_holder_, iterator_ - rhs); } // Distance or element count, binary subtraction of two iterator. @@ -130,31 +220,63 @@ namespace jau { }; /** - * 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. + * Implementation of a Copy-On-Write (CoW) read-write iterator for mutable value_type.<br> + * Instance holds the 'shared value_type reference', Storage_ref_type, + * of the current CoW storage until destruction. + * <p> + * This iterator simply wraps the native iterator of type 'iterator_type' + * and manages the CoW related resource lifecycle. + * </p> * <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, typename Size_type> + template <typename Storage_type, typename Storage_ref_type, typename CoW_container> class cow_rw_iterator { + public: + /** Actual iterator type of the contained native iterator, probably a simple pointer. */ + typedef typename Storage_type::iterator iterator_type; private: + typedef std::iterator_traits<iterator_type> sub_traits_t; + CoW_container& cow_parent_; - const std::lock_guard<std::recursive_mutex> lock_; + std::lock_guard<std::recursive_mutex> lock_; Storage_ref_type new_store_; - typename Storage_type::iterator iterator_; + iterator_type iterator_; - constexpr explicit cow_rw_iterator(CoW_container& cow_parent, Storage_ref_type& store, typename Storage_type::iterator iter) noexcept + constexpr explicit cow_rw_iterator(CoW_container& cow_parent, Storage_ref_type& store, iterator_type iter) noexcept : 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; + typedef typename sub_traits_t::iterator_category iterator_category; // random_access_iterator_tag + + typedef typename Storage_type::size_type size_type; // using our template overload Size_type + typedef typename Storage_type::difference_type difference_type; // derived from our Size_type + // typedef typename Storage_type::value_type value_type; // OK + // typedef typename Storage_type::reference reference; // + // typedef typename Storage_type::pointer pointer; // + typedef typename sub_traits_t::value_type value_type; // OK + typedef typename sub_traits_t::reference reference; // 'value_type &' + typedef typename sub_traits_t::pointer pointer; // 'value_type *' + + #if 0 + // TODO ??? + #if __cplusplus > 201703L && __cpp_lib_concepts + using iterator_concept = std::__detail::__iter_concept<_Iterator>; + #endif + #endif + + 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_)) {} + constexpr cow_rw_iterator(CoW_container& cow_parent, iterator_type (*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_)) {} + + constexpr cow_rw_iterator(CoW_container& cow_parent, iterator_type iter) + : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), + new_store_(cow_parent.copy_store()), iterator_(iter) {} #if __cplusplus > 201703L constexpr ~cow_rw_iterator() noexcept @@ -165,6 +287,46 @@ namespace jau { cow_parent_.set_store(std::move(new_store_)); } + // C++ named requirements: LegacyIterator: CopyConstructible + constexpr cow_rw_iterator(const cow_rw_iterator& o) noexcept + : cow_parent_(o.cow_parent_), lock_(cow_parent_.get_write_mutex()), + new_store_(o.new_store_), iterator_(o.iterator_) {} + + // C++ named requirements: LegacyIterator: CopyAssignable + constexpr cow_rw_iterator& operator=(const cow_rw_iterator& o) noexcept { + cow_parent_ = o.cow_parent_; + lock_ = cow_parent_.get_write_mutex(); + new_store_ = o.new_store_; + iterator_ = o.iterator_; + } + + // C++ named requirements: LegacyIterator: MoveConstructable + constexpr cow_rw_iterator(cow_rw_iterator && o) noexcept + : cow_parent_(std::move(o.cow_parent_)), lock_(cow_parent_.get_write_mutex()), + new_store_(std::move(o.new_store_)), iterator_(std::move(o.iterator_)) { + o.lock_ = nullptr; // ??? + o.new_store_ = nullptr; + // o.iterator_ = nullptr; + } + + // C++ named requirements: LegacyIterator: MoveAssignable + constexpr cow_rw_iterator& operator=(cow_rw_iterator&& o) noexcept { + cow_parent_ = std::move(o.cow_parent_); + lock_ = cow_parent_.get_write_mutex(); + new_store_ = std::move(o.new_store_); + iterator_ = std::move(o.iterator_); + o.new_store_ = nullptr; + // o.iterator_ = nullptr; + } + + // C++ named requirements: LegacyIterator: Swappable + void swap(cow_rw_iterator& o) noexcept { + std::swap( cow_parent_, o.cow_parent_); + // std::swap( lock_, o.lock_); // lock stays in each + std::swap( new_store_, o.new_store_); + std::swap( iterator_, o.iterator_); + } + /** * Returns a copy of the underlying storage iterator. */ @@ -184,18 +346,53 @@ namespace jau { constexpr bool operator!=(const cow_rw_iterator& rhs) const noexcept { return !(*this == rhs); } + // Relation + + constexpr bool operator<=(const cow_rw_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + return &cow_parent_ == &rhs.cow_parent_ && + new_store_ == rhs.new_store_ && + iterator_ <= rhs.iterator_; + } + constexpr bool operator<(const cow_rw_iterator& rhs) const noexcept { + if( this == &rhs ) { + return false; + } + return &cow_parent_ == &rhs.cow_parent_ && + new_store_ == rhs.new_store_ && + iterator_ < rhs.iterator_; + } + constexpr bool operator>=(const cow_rw_iterator& rhs) const noexcept { + if( this == &rhs ) { + return true; + } + return &cow_parent_ == &rhs.cow_parent_ && + new_store_ == rhs.new_store_ && + iterator_ >= rhs.iterator_; + } + constexpr bool operator>(const cow_rw_iterator& rhs) const noexcept { + if( this == &rhs ) { + return false; + } + return &cow_parent_ == &rhs.cow_parent_ && + new_store_ == rhs.new_store_ && + iterator_ > rhs.iterator_; + } + // Forward iterator requirements - constexpr const Value_type& operator*() const noexcept + constexpr const reference operator*() const noexcept { return *iterator_; } - constexpr const Value_type* operator->() const noexcept + constexpr const pointer operator->() const noexcept { return iterator_; } - constexpr Value_type& operator*() noexcept + constexpr reference operator*() noexcept { return *iterator_; } - constexpr Value_type* operator->() noexcept + constexpr pointer operator->() noexcept { return iterator_; } /** Pre-increment; Well performing, return *this. */ @@ -205,7 +402,7 @@ namespace jau { } /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */ - constexpr cow_rw_iterator& operator++(int) noexcept + constexpr cow_rw_iterator operator++(int) noexcept { return cow_rw_iterator(cow_parent_, new_store_, iterator_++); } // Bidirectional iterator requirements @@ -217,17 +414,17 @@ namespace jau { } /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */ - constexpr cow_rw_iterator& operator--(int) noexcept + 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[](difference_type i) const noexcept + constexpr const reference operator[](difference_type i) const noexcept { return iterator_[i]; } /** Subscript of 'element_index', returning mutable Value_type reference. */ - constexpr Value_type& operator[](difference_type i) noexcept + constexpr reference operator[](difference_type i) noexcept { return iterator_[i]; } /** Addition-assignment of 'element_count'; Well performing, return *this. */ diff --git a/include/jau/cow_vector.hpp b/include/jau/cow_vector.hpp index ded50d0..a30cdd4 100644 --- a/include/jau/cow_vector.hpp +++ b/include/jau/cow_vector.hpp @@ -120,7 +120,7 @@ namespace jau { * Using jau::cow_vector::get_snapshot() at construction. * </p> */ - typedef cow_ro_iterator<value_type, storage_t, storage_ref_t, size_type> const_iterator; + typedef cow_ro_iterator<storage_t, storage_ref_t> const_iterator; /** * Mutable, read-write iterator, holding the write-lock and a store copy until destruction. @@ -129,7 +129,7 @@ namespace jau { * and jau::cow_vector::set_store() at destruction. * </p> */ - typedef cow_rw_iterator<value_type, storage_t, storage_ref_t, cow_vector, size_type> iterator; + typedef cow_rw_iterator<storage_t, storage_ref_t, cow_vector> iterator; private: static constexpr size_type DIFF_MAX = std::numeric_limits<difference_type>::max(); |