From 65f7355b1eaa63b1a46d2172d10d45e400e6d862 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 13 Mar 2017 23:26:18 +0300 Subject: [PATCH] Added erase_at( iterator ) function to MichaelHashSet/Map and SplitListSet/Map based on IterableList --- cds/container/impl/iterable_kvlist.h | 13 +++++ cds/container/impl/iterable_list.h | 13 +++++ cds/container/michael_map.h | 34 ++++++++++- cds/container/michael_set.h | 28 +++++++++ cds/container/split_list_map.h | 21 +++++++ cds/container/split_list_set.h | 22 +++++++ cds/intrusive/details/michael_set_base.h | 6 +- cds/intrusive/details/split_list_base.h | 6 ++ cds/intrusive/impl/iterable_list.h | 57 ++++++++++++++----- cds/intrusive/michael_set.h | 28 +++++++++ cds/intrusive/split_list.h | 43 +++++++++++++- .../vc141/gtest-iset-michael-iterable.vcxproj | 2 - .../vc141/gtest-iset-split-iterable.vcxproj | 2 - .../Win/vc141/gtest-list-iterable.vcxproj | 2 - .../vc141/gtest-map-split-iterable.vcxproj | 6 +- .../vc141/gtest-set-split-iterable.vcxproj | 5 -- .../map/iter_erase/map_iter_erase_michael.cpp | 6 +- .../map/iter_erase/map_iter_erase_split.cpp | 5 +- test/stress/map/map_type_feldman_hashmap.h | 4 +- test/stress/map/map_type_michael.h | 41 +++++++++---- test/stress/map/map_type_split_list.h | 14 +++++ .../set/iter_erase/set_iter_erase_michael.cpp | 4 +- .../set/iter_erase/set_iter_erase_split.cpp | 5 +- test/stress/set/set_type_michael.h | 14 +++++ test/stress/set/set_type_split_list.h | 14 +++++ .../test_intrusive_iterable_list.h | 18 +++++- .../test_intrusive_michael_iterable_hp.h | 18 ++++++ .../test_intrusive_split_iterable_set.h | 7 ++- test/unit/list/test_iterable_list.h | 7 ++- test/unit/list/test_kv_iterable_list.h | 7 ++- test/unit/map/split_iterable_dhp.cpp | 2 +- test/unit/map/split_iterable_hp.cpp | 2 +- test/unit/map/test_michael_iterable_hp.h | 13 +++++ test/unit/set/test_michael_iterable_hp.h | 15 +++++ test/unit/set/test_split_iterable_hp.h | 15 +++++ 35 files changed, 432 insertions(+), 67 deletions(-) diff --git a/cds/container/impl/iterable_kvlist.h b/cds/container/impl/iterable_kvlist.h index 4a5e44bf..296e0e6c 100644 --- a/cds/container/impl/iterable_kvlist.h +++ b/cds/container/impl/iterable_kvlist.h @@ -445,6 +445,19 @@ namespace cds { namespace container { return base_class::erase_with( key, less_wrapper(), f ); } + /// Deletes the item pointed by iterator \p iter + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + */ + bool erase_at( iterator const& iter ) + { + return base_class::erase_at( iter ); + } + /// Extracts the item from the list with specified \p key /** The function searches an item with key equal to \p key, diff --git a/cds/container/impl/iterable_list.h b/cds/container/impl/iterable_list.h index 64e5de41..061476b3 100644 --- a/cds/container/impl/iterable_list.h +++ b/cds/container/impl/iterable_list.h @@ -524,6 +524,19 @@ namespace cds { namespace container { return erase_at( head(), key, typename maker::template less_wrapper::type(), f ); } + /// Deletes the item pointed by iterator \p iter + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + */ + bool erase_at( iterator const& iter ) + { + return base_class::erase_at( iter ); + } + /// Extracts the item from the list with specified \p key /** The function searches an item with key equal to \p key, diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h index 799407ac..22b2dccf 100644 --- a/cds/container/michael_map.h +++ b/cds/container/michael_map.h @@ -203,7 +203,7 @@ namespace cds { namespace container { //@cond /// Forward iterator template - class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > + class iterator_type: protected cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > { typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst > base_class; friend class MichaelHashMap; @@ -275,13 +275,13 @@ namespace cds { namespace container { /// Equality operator template - bool operator ==(iterator_type const& i ) + bool operator ==(iterator_type const& i ) const { return base_class::operator ==( i ); } /// Equality operator template - bool operator !=(iterator_type const& i ) + bool operator !=(iterator_type const& i ) const { return !( *this == i ); } @@ -674,6 +674,34 @@ namespace cds { namespace container { return bRet; } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based map) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %MichaelHashMap based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + assert( iter != end() ); + assert( iter.bucket() != nullptr ); + + if ( iter.bucket()->erase_at( iter.underlying_iterator())) { + --m_ItemCounter; + return true; + } + return false; + } + /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract The function searches an item with key equal to \p key, diff --git a/cds/container/michael_set.h b/cds/container/michael_set.h index 92bbbe05..cdd383f4 100644 --- a/cds/container/michael_set.h +++ b/cds/container/michael_set.h @@ -570,6 +570,34 @@ namespace cds { namespace container { return bRet; } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %MichaelHashSet based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + assert( iter != end() ); + assert( iter.bucket() != nullptr ); + + if ( iter.bucket()->erase_at( iter.underlying_iterator())) { + --m_ItemCounter; + return true; + } + return false; + } + /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract The function searches an item with key equal to \p key, diff --git a/cds/container/split_list_map.h b/cds/container/split_list_map.h index 56eccfa3..59cc5281 100644 --- a/cds/container/split_list_map.h +++ b/cds/container/split_list_map.h @@ -542,6 +542,27 @@ namespace cds { namespace container { return base_class::erase_with( key, cds::details::predicate_wrapper(), f ); } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based map) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %SplitListMap based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + return base_class::erase_at( iter ); + } + /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_SplitListMap_hp_extract The function searches an item with key equal to \p key, diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index 21d0b353..f6a7831e 100644 --- a/cds/container/split_list_set.h +++ b/cds/container/split_list_set.h @@ -626,6 +626,28 @@ namespace cds { namespace container { [&f](node_type& node) { f( node.m_Value ); } ); } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + return base_class::erase_at( static_cast( iter )); + } + + /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_SplitListSet_hp_extract The function searches an item with key equal to \p key, diff --git a/cds/intrusive/details/michael_set_base.h b/cds/intrusive/details/michael_set_base.h index 070ee0fb..9bf2cd73 100644 --- a/cds/intrusive/details/michael_set_base.h +++ b/cds/intrusive/details/michael_set_base.h @@ -204,6 +204,11 @@ namespace cds { namespace intrusive { return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr; } + list_iterator const& underlying_iterator() const + { + return m_itList; + } + template bool operator ==(iterator const& i) const { @@ -214,7 +219,6 @@ namespace cds { namespace intrusive { { return !( *this == i ); } - }; } //@endcond diff --git a/cds/intrusive/details/split_list_base.h b/cds/intrusive/details/split_list_base.h index 65420bd5..d7f868b8 100644 --- a/cds/intrusive/details/split_list_base.h +++ b/cds/intrusive/details/split_list_base.h @@ -1232,6 +1232,12 @@ namespace cds { namespace intrusive { { return m_itCur != i.m_itCur; } + + protected: + list_iterator const& underlying_iterator() const + { + return m_itCur; + } }; } // namespace details //@endcond diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index d34264be..f9f5b2a3 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -204,7 +204,7 @@ namespace cds { namespace intrusive { friend class IterableList; protected: - node_type const* m_pNode; + node_type* m_pNode; typename gc::Guard m_Guard; // data guard void next() @@ -218,14 +218,14 @@ namespace cds { namespace intrusive { m_Guard.clear(); } - explicit iterator_type( node_type const* pNode ) + explicit iterator_type( node_type* pNode ) : m_pNode( pNode ) { if ( !m_Guard.protect( pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) next(); } - iterator_type( node_type const* pNode, value_type* pVal ) + iterator_type( node_type* pNode, value_type* pVal ) : m_pNode( pNode ) { if ( m_pNode ) { @@ -234,6 +234,11 @@ namespace cds { namespace intrusive { } } + value_type* data() const + { + return m_Guard.template get(); + } + public: typedef typename cds::details::make_const_type::pointer value_ptr; typedef typename cds::details::make_const_type::reference value_ref; @@ -250,13 +255,15 @@ namespace cds { namespace intrusive { value_ptr operator ->() const { - return m_Guard.template get(); + return data(); + //return m_Guard.template get(); } value_ref operator *() const { assert( m_Guard.get_native() != nullptr ); - return *m_Guard.template get(); + return *data(); + //return *m_Guard.template get(); } /// Pre-increment @@ -335,8 +342,8 @@ namespace cds { namespace intrusive { assert( &(*it1) == &(*it2)); \endcode can throw assertion. The point is that the iterator stores the value of element which can be modified later by other thread. - The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after such changing. - Other iterator can observe modified value of the element. + The guard inside the iterator prevents recycling that value so the iterator's value remains valid even after changing. + Other iterator may observe modified value of the element. */ typedef iterator_type iterator; /// Const forward iterator @@ -370,25 +377,25 @@ namespace cds { namespace intrusive { /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { - return const_iterator( &m_Head ); + return const_iterator( const_cast( &m_Head )); } /// Returns a forward const iterator addressing the first element in a list const_iterator begin() const { - return const_iterator( &m_Head ); + return const_iterator( const_cast( &m_Head )); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator end() const { - return const_iterator( &m_Tail ); + return const_iterator( const_cast( &m_Tail )); } /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator cend() const { - return const_iterator( &m_Tail ); + return const_iterator( const_cast( &m_Tail )); } //@} @@ -580,6 +587,28 @@ namespace cds { namespace intrusive { return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less(), f ); } + /// Deletes the item pointed by iterator \p iter + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + */ + bool erase_at( iterator const& iter ) + { + assert( iter != end() ); + + marked_data_ptr val( iter.data() ); + if ( iter.m_pNode->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + --m_ItemCounter; + retire_data( val.ptr() ); + m_Stat.onEraseSuccess(); + return true; + } + return false; + } + /// Extracts the item from the list with specified \p key /** \anchor cds_intrusive_IterableList_hp_extract The function searches an item with key equal to \p key, @@ -981,7 +1010,7 @@ namespace cds { namespace intrusive { } template - bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f, position& pos ) + bool erase_at( node_type* pHead, Q const& val, Compare cmp, Func f, position& pos ) { back_off bkoff; while ( search( pHead, val, pos, cmp )) { @@ -1002,7 +1031,7 @@ namespace cds { namespace intrusive { } template - bool erase_at( node_type* pHead, const Q& val, Compare cmp, Func f ) + bool erase_at( node_type* pHead, Q const& val, Compare cmp, Func f ) { position pos; return erase_at( pHead, val, cmp, f, pos ); @@ -1077,7 +1106,7 @@ namespace cds { namespace intrusive { } m_Stat.onFindFailed(); - return iterator( &m_Tail ); + return iterator( const_cast( &m_Tail )); } template diff --git a/cds/intrusive/michael_set.h b/cds/intrusive/michael_set.h index a2aac0b4..8e21f85f 100644 --- a/cds/intrusive/michael_set.h +++ b/cds/intrusive/michael_set.h @@ -626,6 +626,34 @@ namespace cds { namespace intrusive { return false; } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %MichaelHashSet based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + assert( iter != end() ); + assert( iter.bucket() != nullptr ); + + if ( iter.bucket()->erase_at( iter.underlying_iterator())) { + --m_ItemCounter; + return true; + } + return false; + } + /// Extracts the item with specified \p key /** \anchor cds_intrusive_MichaelHashSet_hp_extract The function searches an item with key equal to \p key, diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index b4e31dfb..d28e2050 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -351,6 +351,16 @@ namespace cds { namespace intrusive { return base_class::unlink_at( h, val ); } + template + typename std::enable_if< + std::is_same< Iterator, typename ordered_list::iterator>::value && is_iterable_list< ordered_list >::value, + bool + >::type + erase_at( Iterator iter ) + { + return base_class::erase_at( iter ); + } + template bool erase_at( aux_node_type * pHead, split_list::details::search_value_type const& val, Compare cmp, Func f ) { @@ -433,10 +443,13 @@ namespace cds { namespace intrusive { //@cond template class iterator_type - :public split_list::details::iterator_type + : public split_list::details::iterator_type { typedef split_list::details::iterator_type iterator_base_class; typedef typename iterator_base_class::list_iterator list_iterator; + + friend class SplitListSet; + public: iterator_type() : iterator_base_class() @@ -830,6 +843,34 @@ namespace cds { namespace intrusive { return erase_( key, typename ordered_list_adapter::template make_compare_from_less(), f ); } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + assert( iter != end() ); + + if ( m_List.erase_at( iter.underlying_iterator())) { + --m_ItemCounter; + m_Stat.onEraseSuccess(); + return true; + } + return false; + } + /// Extracts the item with specified \p key /** \anchor cds_intrusive_SplitListSet_hp_extract The function searches an item with key equal to \p key, diff --git a/projects/Win/vc141/gtest-iset-michael-iterable.vcxproj b/projects/Win/vc141/gtest-iset-michael-iterable.vcxproj index be0c52e6..1d1073ab 100644 --- a/projects/Win/vc141/gtest-iset-michael-iterable.vcxproj +++ b/projects/Win/vc141/gtest-iset-michael-iterable.vcxproj @@ -36,8 +36,6 @@ - - {2A3D25FA-16AB-4105-9585-EF5266979989} diff --git a/projects/Win/vc141/gtest-iset-split-iterable.vcxproj b/projects/Win/vc141/gtest-iset-split-iterable.vcxproj index 4ddbc681..b3236b4b 100644 --- a/projects/Win/vc141/gtest-iset-split-iterable.vcxproj +++ b/projects/Win/vc141/gtest-iset-split-iterable.vcxproj @@ -34,8 +34,6 @@ - - diff --git a/projects/Win/vc141/gtest-list-iterable.vcxproj b/projects/Win/vc141/gtest-list-iterable.vcxproj index 46d0cd17..fbd33a0a 100644 --- a/projects/Win/vc141/gtest-list-iterable.vcxproj +++ b/projects/Win/vc141/gtest-list-iterable.vcxproj @@ -33,10 +33,8 @@ - - diff --git a/projects/Win/vc141/gtest-map-split-iterable.vcxproj b/projects/Win/vc141/gtest-map-split-iterable.vcxproj index 4216fb23..d86db63e 100644 --- a/projects/Win/vc141/gtest-map-split-iterable.vcxproj +++ b/projects/Win/vc141/gtest-map-split-iterable.vcxproj @@ -32,11 +32,9 @@ - - - - + + {B7C62D31-ED28-4D85-AA01-D1071E870080} diff --git a/projects/Win/vc141/gtest-set-split-iterable.vcxproj b/projects/Win/vc141/gtest-set-split-iterable.vcxproj index 3a03aa36..709c92ea 100644 --- a/projects/Win/vc141/gtest-set-split-iterable.vcxproj +++ b/projects/Win/vc141/gtest-set-split-iterable.vcxproj @@ -32,12 +32,7 @@ - - - - - diff --git a/test/stress/map/iter_erase/map_iter_erase_michael.cpp b/test/stress/map/iter_erase/map_iter_erase_michael.cpp index d933d8ea..ee147abb 100644 --- a/test/stress/map/iter_erase/map_iter_erase_michael.cpp +++ b/test/stress/map/iter_erase/map_iter_erase_michael.cpp @@ -32,9 +32,7 @@ #include "map_type_michael.h" namespace map { - //TODO add erase_at() to MichaelHashMap based on IterableList -#if 0 - CDSSTRESS_MichaelMap( Map_Iter_Del3_LF, run_test_extract, key_thread, size_t ) -#endif + + CDSSTRESS_MichaelMap_Iterable( Map_Iter_Del3_LF, run_test_extract, key_thread, size_t ) } // namespace map diff --git a/test/stress/map/iter_erase/map_iter_erase_split.cpp b/test/stress/map/iter_erase/map_iter_erase_split.cpp index 4ffdb6bb..b56d9ce7 100644 --- a/test/stress/map/iter_erase/map_iter_erase_split.cpp +++ b/test/stress/map/iter_erase/map_iter_erase_split.cpp @@ -32,8 +32,7 @@ #include "map_type_split_list.h" namespace map { - //TODO: add erase_at() to SplitList based on IterableList -#if 0 + CDSSTRESS_SplitListIterableMap( Map_Iter_Del3_LF, run_test_extract, key_thread, size_t ) -#endif + } // namespace map diff --git a/test/stress/map/map_type_feldman_hashmap.h b/test/stress/map/map_type_feldman_hashmap.h index 1c5907aa..1b242f54 100644 --- a/test/stress/map/map_type_feldman_hashmap.h +++ b/test/stress/map/map_type_feldman_hashmap.h @@ -60,14 +60,14 @@ namespace map { template typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type - get_begin() + get_begin() { return base_class::begin(); } template typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type - get_end() + get_end() { return base_class::end(); } diff --git a/test/stress/map/map_type_michael.h b/test/stress/map/map_type_michael.h index 98873ea5..7e23eca9 100644 --- a/test/stress/map/map_type_michael.h +++ b/test/stress/map/map_type_michael.h @@ -51,6 +51,20 @@ namespace map { : base_class( cfg.s_nMapSize, cfg.s_nLoadFactor ) {} + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_begin() + { + return base_class::begin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_end() + { + return base_class::end(); + } + // for testing static CDS_CONSTEXPR bool const c_bExtractSupported = true; static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true; @@ -328,7 +342,14 @@ namespace map { #endif #if defined(CDS_STRESS_TEST_LEVEL) && CDS_STRESS_TEST_LEVEL == 1 -# define CDSSTRESS_MichaelMap_HP_1( fixture, test_case, key_type, value_type ) \ + +# define CDSSTRESS_MichaelMap_Iterable_1( fixture, test_case, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_cmp, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_cmp_stat, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_less, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_less_stat, key_type, value_type ) \ + +# define CDSSTRESS_MichaelMap_HP_1( fixture, test_case, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_DHP_cmp, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_HP_cmp_stat, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_HP_less, key_type, value_type ) \ @@ -338,11 +359,6 @@ namespace map { CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Lazy_HP_cmp_stat, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Lazy_HP_less, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Lazy_DHP_less_stat, key_type, value_type ) \ - \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_cmp, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_cmp_stat, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_less, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_less_stat, key_type, value_type ) \ # define CDSSTRESS_MichaelMap_RCU_1( fixture, test_case, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_RCU_GPB_cmp, key_type, value_type ) \ @@ -360,11 +376,18 @@ namespace map { CDSSTRESS_MichaelMap_RCU_1( fixture, test_case, key_type, value_type ) \ #else +# define CDSSTRESS_MichaelMap_Iterable_1( fixture, test_case, key_type, value_type ) # define CDSSTRESS_MichaelMap_HP_1( fixture, test_case, key_type, value_type ) # define CDSSTRESS_MichaelMap_RCU_1( fixture, test_case, key_type, value_type ) # define CDSSTRESS_MichaelMap_1( fixture, test_case, key_type, value_type ) #endif +#define CDSSTRESS_MichaelMap_Iterable( fixture, test_case, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_cmp, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_cmp_stat, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_less, key_type, value_type ) \ + CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_less_stat, key_type, value_type ) \ + CDSSTRESS_MichaelMap_Iterable_1( fixture, test_case, key_type, value_type ) \ #define CDSSTRESS_MichaelMap_HP( fixture, test_case, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_HP_cmp, key_type, value_type ) \ @@ -377,11 +400,7 @@ namespace map { CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Lazy_DHP_less, key_type, value_type ) \ CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Lazy_HP_less_stat, key_type, value_type ) \ \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_cmp, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_cmp_stat, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_DHP_less, key_type, value_type ) \ - CDSSTRESS_MichaelMap_case( fixture, test_case, MichaelMap_Iterable_HP_less_stat, key_type, value_type ) \ - \ + CDSSTRESS_MichaelMap_Iterable( fixture, test_case, key_type, value_type ) \ CDSSTRESS_MichaelMap_HP_1( fixture, test_case, key_type, value_type ) \ CDSSTRESS_MichaelMap_HP_2( fixture, test_case, key_type, value_type ) \ diff --git a/test/stress/map/map_type_split_list.h b/test/stress/map/map_type_split_list.h index c2fe83b7..b26d6748 100644 --- a/test/stress/map/map_type_split_list.h +++ b/test/stress/map/map_type_split_list.h @@ -67,6 +67,20 @@ namespace map { : base_class( cfg.s_nMapSize, cfg.s_nLoadFactor ) {} + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_begin() + { + return base_class::begin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_end() + { + return base_class::end(); + } + // for testing static CDS_CONSTEXPR bool const c_bExtractSupported = true; static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true; diff --git a/test/stress/set/iter_erase/set_iter_erase_michael.cpp b/test/stress/set/iter_erase/set_iter_erase_michael.cpp index e0e88033..2c997bcf 100644 --- a/test/stress/set/iter_erase/set_iter_erase_michael.cpp +++ b/test/stress/set/iter_erase/set_iter_erase_michael.cpp @@ -32,9 +32,7 @@ #include "set_type_michael.h" namespace set { - //TODO: add erase_at() to IterableList and MichaelHashSet -#if 0 + CDSSTRESS_MichaelIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t ) -#endif } // namespace set diff --git a/test/stress/set/iter_erase/set_iter_erase_split.cpp b/test/stress/set/iter_erase/set_iter_erase_split.cpp index d67b7b50..c34f5d42 100644 --- a/test/stress/set/iter_erase/set_iter_erase_split.cpp +++ b/test/stress/set/iter_erase/set_iter_erase_split.cpp @@ -32,8 +32,7 @@ #include "set_type_split_list.h" namespace set { - //TODO: Add erase_at to IterableList and SplitList based on it -#if 0 + CDSSTRESS_SplitListIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t ) -#endif + } // namespace set diff --git a/test/stress/set/set_type_michael.h b/test/stress/set/set_type_michael.h index fafe4b8d..24bf5f0b 100644 --- a/test/stress/set/set_type_michael.h +++ b/test/stress/set/set_type_michael.h @@ -54,6 +54,20 @@ namespace set { : base_class( cfg.s_nSetSize, cfg.s_nLoadFactor ) {} + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_begin() + { + return base_class::begin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_end() + { + return base_class::end(); + } + // for testing static CDS_CONSTEXPR bool const c_bExtractSupported = true; static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true; diff --git a/test/stress/set/set_type_split_list.h b/test/stress/set/set_type_split_list.h index 42f76a4f..aa12be45 100644 --- a/test/stress/set/set_type_split_list.h +++ b/test/stress/set/set_type_split_list.h @@ -62,6 +62,20 @@ namespace set { : base_class( cfg.s_nSetSize, cfg.s_nLoadFactor ) {} + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_begin() + { + return base_class::begin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_end() + { + return base_class::end(); + } + // for testing static CDS_CONSTEXPR bool const c_bExtractSupported = true; static CDS_CONSTEXPR bool const c_bLoadFactorDepended = true; diff --git a/test/unit/intrusive-list/test_intrusive_iterable_list.h b/test/unit/intrusive-list/test_intrusive_iterable_list.h index 2dc23805..4cf8ab76 100644 --- a/test/unit/intrusive-list/test_intrusive_iterable_list.h +++ b/test/unit/intrusive-list/test_intrusive_iterable_list.h @@ -529,7 +529,23 @@ namespace cds_test { ++key; } - l.clear(); + // Erase by iterator + key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( ( *it ).nKey, key ); + + EXPECT_TRUE( l.erase_at( it ) ); + + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( ( *it ).nKey, key ); + + EXPECT_FALSE( l.erase_at( it ) ); + ++key; + } + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + List::gc::force_dispose(); for ( auto const& i : arr ) { EXPECT_EQ( i.s.nDisposeCount, 1 ); diff --git a/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h b/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h index c8b83aae..0a892cb5 100644 --- a/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h +++ b/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h @@ -152,6 +152,24 @@ namespace cds_test { EXPECT_EQ( i.nDisposeCount, 1u ); } + // erase_at() test + for ( auto& i : data ) { + i.nDisposeCount = 0; + ASSERT_TRUE( s.insert( i ) ); + } + + for ( auto it = s.begin(); it != s.end(); ++it ) { + EXPECT_TRUE( s.erase_at( it )); + EXPECT_FALSE( s.erase_at( it )); + } + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + // Force retiring cycle + Set::gc::force_dispose(); + for ( auto& i : data ) { + EXPECT_EQ( i.nDisposeCount, 1u ); + } } }; diff --git a/test/unit/intrusive-set/test_intrusive_split_iterable_set.h b/test/unit/intrusive-set/test_intrusive_split_iterable_set.h index 91bfbb58..4cfcda90 100644 --- a/test/unit/intrusive-set/test_intrusive_split_iterable_set.h +++ b/test/unit/intrusive-set/test_intrusive_split_iterable_set.h @@ -396,8 +396,11 @@ namespace cds_test { EXPECT_EQ( i.nFindCount, 1u ); } - // clear test - s.clear(); + // erase_at() test + for ( auto it = s.begin(); it != s.end(); ++it ) { + EXPECT_TRUE( s.erase_at( it )); + EXPECT_FALSE( s.erase_at( it )); + } ASSERT_TRUE( s.empty()); ASSERT_CONTAINER_SIZE( s, 0u ); diff --git a/test/unit/list/test_iterable_list.h b/test/unit/list/test_iterable_list.h index 9233a842..5dd9ef19 100644 --- a/test/unit/list/test_iterable_list.h +++ b/test/unit/list/test_iterable_list.h @@ -394,7 +394,12 @@ namespace cds_test { } EXPECT_EQ( static_cast(key), nSize ); - l.clear(); + // erase_at() + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_TRUE( l.erase_at( it )); + EXPECT_FALSE( l.erase_at( it )); + } + ASSERT_TRUE( l.empty()); EXPECT_CONTAINER_SIZE( l, 0 ); } diff --git a/test/unit/list/test_kv_iterable_list.h b/test/unit/list/test_kv_iterable_list.h index 9fcefda7..8c6cdc8d 100644 --- a/test/unit/list/test_kv_iterable_list.h +++ b/test/unit/list/test_kv_iterable_list.h @@ -438,7 +438,12 @@ namespace cds_test { } EXPECT_EQ( static_cast(key), nSize ); - l.clear(); + // erase_at() + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_TRUE( l.erase_at( it )); + EXPECT_FALSE( l.erase_at( it )); + } + ASSERT_TRUE( l.empty()); EXPECT_CONTAINER_SIZE( l, 0 ); } diff --git a/test/unit/map/split_iterable_dhp.cpp b/test/unit/map/split_iterable_dhp.cpp index 27f6d5ae..d95c2285 100644 --- a/test/unit/map/split_iterable_dhp.cpp +++ b/test/unit/map/split_iterable_dhp.cpp @@ -38,7 +38,7 @@ namespace { namespace cc = cds::container; typedef cds::gc::DHP gc_type; - class SplitListIterableMap_DHP : public cds_test::michael_iterable_map + class SplitListIterableMap_DHP : public cds_test::michael_iterable_hp { protected: typedef cds_test::michael_iterable_map base_class; diff --git a/test/unit/map/split_iterable_hp.cpp b/test/unit/map/split_iterable_hp.cpp index d93c3843..f2753f68 100644 --- a/test/unit/map/split_iterable_hp.cpp +++ b/test/unit/map/split_iterable_hp.cpp @@ -38,7 +38,7 @@ namespace { namespace cc = cds::container; typedef cds::gc::HP gc_type; - class SplitListIterableMap_HP : public cds_test::michael_iterable_map + class SplitListIterableMap_HP : public cds_test::michael_iterable_hp { protected: typedef cds_test::michael_iterable_map base_class; diff --git a/test/unit/map/test_michael_iterable_hp.h b/test/unit/map/test_michael_iterable_hp.h index 6e940b8f..36b93af0 100644 --- a/test/unit/map/test_michael_iterable_hp.h +++ b/test/unit/map/test_michael_iterable_hp.h @@ -133,6 +133,19 @@ namespace cds_test { } EXPECT_TRUE( m.empty()); EXPECT_CONTAINER_SIZE( m, 0u ); + + // erase_at() + for ( auto const& i : arrKeys ) + EXPECT_TRUE( m.insert( i ) ); + EXPECT_FALSE( m.empty() ); + EXPECT_CONTAINER_SIZE( m, kkSize ); + + for ( auto it = m.begin(); it != m.end(); ++it ) { + EXPECT_TRUE( m.erase_at( it )); + EXPECT_FALSE( m.erase_at( it )); + } + EXPECT_TRUE( m.empty() ); + EXPECT_CONTAINER_SIZE( m, 0u ); } }; diff --git a/test/unit/set/test_michael_iterable_hp.h b/test/unit/set/test_michael_iterable_hp.h index 1ab9a134..08cfbf5b 100644 --- a/test/unit/set/test_michael_iterable_hp.h +++ b/test/unit/set/test_michael_iterable_hp.h @@ -145,6 +145,21 @@ namespace cds_test { EXPECT_TRUE( s.empty()); EXPECT_CONTAINER_SIZE( s, 0 ); + + // erase_at() + for ( auto& i : data ) { + EXPECT_TRUE( s.insert( i ) ); + } + EXPECT_FALSE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, nSetSize ); + + for ( auto it = s.begin(); it != s.end(); ++it ) { + EXPECT_TRUE( s.erase_at( it )); + EXPECT_FALSE( s.erase_at( it )); + } + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); } }; diff --git a/test/unit/set/test_split_iterable_hp.h b/test/unit/set/test_split_iterable_hp.h index 122c8627..2b558fcd 100644 --- a/test/unit/set/test_split_iterable_hp.h +++ b/test/unit/set/test_split_iterable_hp.h @@ -145,6 +145,21 @@ namespace cds_test { EXPECT_TRUE( s.empty()); EXPECT_CONTAINER_SIZE( s, 0 ); + + // erase_at() + for ( auto& i : data ) { + EXPECT_TRUE( s.insert( i ) ); + } + EXPECT_FALSE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, nSetSize ); + + for ( auto it = s.begin(); it != s.end(); ++it ) { + EXPECT_TRUE( s.erase_at( it )); + EXPECT_FALSE( s.erase_at( it )); + } + + EXPECT_TRUE( s.empty() ); + EXPECT_CONTAINER_SIZE( s, 0 ); } }; -- 2.34.1