Added erase_at( iterator ) function to MichaelHashSet/Map and SplitListSet/Map based...
authorkhizmax <libcds.dev@gmail.com>
Mon, 13 Mar 2017 20:26:18 +0000 (23:26 +0300)
committerkhizmax <libcds.dev@gmail.com>
Mon, 13 Mar 2017 20:26:18 +0000 (23:26 +0300)
35 files changed:
cds/container/impl/iterable_kvlist.h
cds/container/impl/iterable_list.h
cds/container/michael_map.h
cds/container/michael_set.h
cds/container/split_list_map.h
cds/container/split_list_set.h
cds/intrusive/details/michael_set_base.h
cds/intrusive/details/split_list_base.h
cds/intrusive/impl/iterable_list.h
cds/intrusive/michael_set.h
cds/intrusive/split_list.h
projects/Win/vc141/gtest-iset-michael-iterable.vcxproj
projects/Win/vc141/gtest-iset-split-iterable.vcxproj
projects/Win/vc141/gtest-list-iterable.vcxproj
projects/Win/vc141/gtest-map-split-iterable.vcxproj
projects/Win/vc141/gtest-set-split-iterable.vcxproj
test/stress/map/iter_erase/map_iter_erase_michael.cpp
test/stress/map/iter_erase/map_iter_erase_split.cpp
test/stress/map/map_type_feldman_hashmap.h
test/stress/map/map_type_michael.h
test/stress/map/map_type_split_list.h
test/stress/set/iter_erase/set_iter_erase_michael.cpp
test/stress/set/iter_erase/set_iter_erase_split.cpp
test/stress/set/set_type_michael.h
test/stress/set/set_type_split_list.h
test/unit/intrusive-list/test_intrusive_iterable_list.h
test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h
test/unit/intrusive-set/test_intrusive_split_iterable_set.h
test/unit/list/test_iterable_list.h
test/unit/list/test_kv_iterable_list.h
test/unit/map/split_iterable_dhp.cpp
test/unit/map/split_iterable_hp.cpp
test/unit/map/test_michael_iterable_hp.h
test/unit/set/test_michael_iterable_hp.h
test/unit/set/test_split_iterable_hp.h

index 4a5e44b..296e0e6 100644 (file)
@@ -445,6 +445,19 @@ namespace cds { namespace container {
             return base_class::erase_with( key, less_wrapper<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 )
+        {
+            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,
index 64e5de4..061476b 100644 (file)
@@ -524,6 +524,19 @@ namespace cds { namespace container {
             return erase_at( head(), key, typename maker::template less_wrapper<Less>::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,
index 799407a..22b2dcc 100644 (file)
@@ -203,7 +203,7 @@ namespace cds { namespace container {
         //@cond
         /// Forward iterator
         template <bool IsConst>
-        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 C>
-            bool operator ==(iterator_type<C> const& i )
+            bool operator ==(iterator_type<C> const& i ) const
             {
                 return base_class::operator ==( i );
             }
             /// Equality operator
             template <bool C>
-            bool operator !=(iterator_type<C> const& i )
+            bool operator !=(iterator_type<C> 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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::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,
index 92bbbe0..cdd383f 100644 (file)
@@ -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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::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,
index 56eccfa..59cc528 100644 (file)
@@ -542,6 +542,27 @@ namespace cds { namespace container {
             return base_class::erase_with( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>(), 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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::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,
index 21d0b35..f6a7831 100644 (file)
@@ -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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
+        erase_at( Iterator const& iter )
+#endif
+        {
+            return base_class::erase_at( static_cast<iterator::iterator_base_class const&>( 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,
index 070ee0f..9bf2cd7 100644 (file)
@@ -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 C>
                 bool operator ==(iterator<bucket_type, C> const& i) const
                 {
@@ -214,7 +219,6 @@ namespace cds { namespace intrusive {
                 {
                     return !( *this == i );
                 }
-
             };
         }
         //@endcond
index 65420bd..d7f868b 100644 (file)
@@ -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
index d34264b..f9f5b2a 100644 (file)
@@ -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<value_type>();
+            }
+
         public:
             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
@@ -250,13 +255,15 @@ namespace cds { namespace intrusive {
 
             value_ptr operator ->() const
             {
-                return m_Guard.template get<value_type>();
+                return data();
+                //return m_Guard.template get<value_type>();
             }
 
             value_ref operator *() const
             {
                 assert( m_Guard.get_native() != nullptr );
-                return *m_Guard.template get<value_type>();
+                return *data();
+                //return *m_Guard.template get<value_type>();
             }
 
             /// 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<false>    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<node_type*>( &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<node_type*>( &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<node_type*>( &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<node_type*>( &m_Tail ));
         }
     //@}
 
@@ -580,6 +587,28 @@ namespace cds { namespace intrusive {
             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<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 <typename Q, typename Compare, typename Func>
-        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 <typename Q, typename Compare, typename Func>
-        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<node_type*>( &m_Tail ));
         }
 
         template <typename Q, typename Compare>
index a2aac0b..8e21f85 100644 (file)
@@ -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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::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,
index b4e31df..d28e205 100644 (file)
@@ -351,6 +351,16 @@ namespace cds { namespace intrusive {
                 return base_class::unlink_at( h, val );
             }
 
+            template <typename Iterator>
+            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 <typename Q, typename Compare, typename Func>
             bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
             {
@@ -433,10 +443,13 @@ namespace cds { namespace intrusive {
         //@cond
         template <bool IsConst>
         class iterator_type
-            :public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
+            : public split_list::details::iterator_type<node_traits, ordered_list, IsConst>
         {
             typedef split_list::details::iterator_type<node_traits, ordered_list, IsConst> 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<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 Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::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,
index be0c52e..1d1073a 100644 (file)
@@ -36,8 +36,6 @@
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_iterable_hp.h" />
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set.h" />
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_nogc.h" />
-    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_rcu.h" />
   </ItemGroup>
   <PropertyGroup Label="Globals">
     <ProjectGuid>{2A3D25FA-16AB-4105-9585-EF5266979989}</ProjectGuid>
index 4ddbc68..b3236b4 100644 (file)
@@ -34,8 +34,6 @@
   <ItemGroup>
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set.h" />
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_nogc.h" />
-    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set_rcu.h" />
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_split_iterable_set.h" />
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_split_iterable_set_hp.h" />
   </ItemGroup>
index 46d0cd1..fbd33a0 100644 (file)
     <ClInclude Include="..\..\..\test\unit\list\test_kv_iterable_list_hp.h" />
     <ClInclude Include="..\..\..\test\unit\list\test_kv_list.h" />
     <ClInclude Include="..\..\..\test\unit\list\test_kv_list_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\list\test_kv_list_rcu.h" />
     <ClInclude Include="..\..\..\test\unit\list\test_list.h" />
     <ClInclude Include="..\..\..\test\unit\list\test_list_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\list\test_list_rcu.h" />
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="..\..\..\test\unit\list\iterable_dhp.cpp" />
index 4216fb2..d86db63 100644 (file)
     <ClCompile Include="..\..\..\test\unit\map\split_iterable_hp.cpp" />
   </ItemGroup>
   <ItemGroup>
-    <ClInclude Include="..\..\..\test\unit\map\test_map.h" />
     <ClInclude Include="..\..\..\test\unit\map\test_map_data.h" />
-    <ClInclude Include="..\..\..\test\unit\map\test_map_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\map\test_map_nogc.h" />
-    <ClInclude Include="..\..\..\test\unit\map\test_map_rcu.h" />
+    <ClInclude Include="..\..\..\test\unit\map\test_michael_iterable.h" />
+    <ClInclude Include="..\..\..\test\unit\map\test_michael_iterable_hp.h" />
   </ItemGroup>
   <PropertyGroup Label="Globals">
     <ProjectGuid>{B7C62D31-ED28-4D85-AA01-D1071E870080}</ProjectGuid>
index 3a03aa3..709c92e 100644 (file)
     <ClCompile Include="..\..\..\test\unit\set\split_iterable_hp.cpp" />
   </ItemGroup>
   <ItemGroup>
-    <ClInclude Include="..\..\..\test\unit\set\test_ordered_set_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\set\test_set.h" />
     <ClInclude Include="..\..\..\test\unit\set\test_set_data.h" />
-    <ClInclude Include="..\..\..\test\unit\set\test_set_hp.h" />
-    <ClInclude Include="..\..\..\test\unit\set\test_set_nogc.h" />
-    <ClInclude Include="..\..\..\test\unit\set\test_set_rcu.h" />
     <ClInclude Include="..\..\..\test\unit\set\test_split_iterable.h" />
     <ClInclude Include="..\..\..\test\unit\set\test_split_iterable_hp.h" />
   </ItemGroup>
index d933d8e..ee147ab 100644 (file)
@@ -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
index 4ffdb6b..b56d9ce 100644 (file)
@@ -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
index 1c5907a..1b242f5 100644 (file)
@@ -60,14 +60,14 @@ namespace map {
 
         template <typename Iterator>
         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 Iterator>
         typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type
-            get_end()
+        get_end()
         {
             return base_class::end();
         }
index 98873ea..7e23eca 100644 (file)
@@ -51,6 +51,20 @@ namespace map {
             : base_class( cfg.s_nMapSize, cfg.s_nLoadFactor )
         {}
 
+        template <typename Iterator>
+        typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type
+        get_begin()
+        {
+            return base_class::begin();
+        }
+
+        template <typename Iterator>
+        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 ) \
 
index c2fe83b..b26d674 100644 (file)
@@ -67,6 +67,20 @@ namespace map {
             : base_class( cfg.s_nMapSize, cfg.s_nLoadFactor )
         {}
 
+        template <typename Iterator>
+        typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type
+        get_begin()
+        {
+            return base_class::begin();
+        }
+
+        template <typename Iterator>
+        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;
index e0e8803..2c997bc 100644 (file)
@@ -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
index d67b7b5..c34f5d4 100644 (file)
@@ -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
index fafe4b8..24bf5f0 100644 (file)
@@ -54,6 +54,20 @@ namespace set {
             : base_class( cfg.s_nSetSize, cfg.s_nLoadFactor )
         {}
 
+        template <typename Iterator>
+        typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type
+        get_begin()
+        {
+            return base_class::begin();
+        }
+
+        template <typename Iterator>
+        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;
index 42f76a4..aa12be4 100644 (file)
@@ -62,6 +62,20 @@ namespace set {
             : base_class( cfg.s_nSetSize, cfg.s_nLoadFactor )
         {}
 
+        template <typename Iterator>
+        typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type
+        get_begin()
+        {
+            return base_class::begin();
+        }
+
+        template <typename Iterator>
+        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;
index 2dc2380..4cf8ab7 100644 (file)
@@ -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 );
index c8b83aa..0a892cb 100644 (file)
@@ -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 );
+            }
         }
     };
 
index 91bfbb5..4cfcda9 100644 (file)
@@ -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 );
index 9233a84..5dd9ef1 100644 (file)
@@ -394,7 +394,12 @@ namespace cds_test {
             }
             EXPECT_EQ( static_cast<size_t>(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 );
         }
index 9fcefda..8c6cdc8 100644 (file)
@@ -438,7 +438,12 @@ namespace cds_test {
             }
             EXPECT_EQ( static_cast<size_t>(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 );
         }
index 27f6d5a..d95c228 100644 (file)
@@ -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;
index d93c384..f2753f6 100644 (file)
@@ -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;
index 6e940b8..36b93af 100644 (file)
@@ -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 );
         }
     };
 
index 1ab9a13..08cfbf5 100644 (file)
@@ -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 );
         }
 
     };
index 122c862..2b558fc 100644 (file)
@@ -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 );
         }
 
     };