Added SplitListMap<HP> based on IterableList

diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h
index 6c67eb30859ec86cd15cab6420336f459021b531..51e2ad6b063f0efa1c865955c5f20df313eb496b 100644 (file)
--- a/cds/container/michael_map.h
+++ b/cds/container/michael_map.h
@@ -507,7 +507,7 @@ namespace cds { namespace container {
             (note that in this case the \ref key_type should be constructible from type \p K).
             Otherwise, if \p key is found, the functor \p func is called with item found.
 
             (note that in this case the \ref key_type should be constructible from type \p K).
             Otherwise, if \p key is found, the functor \p func is called with item found.
 

-            The functor \p func signature depends of \p OrderedList:
+            The functor \p func signature depends on \p OrderedList:

 
             <b>for \p MichaelKVList, \p LazyKVList</b>
             \code
 
             <b>for \p MichaelKVList, \p LazyKVList</b>
             \code


@@ -536,7 +536,7 @@ namespace cds { namespace container {
             \p second is true if new item has been added or \p false if the item with \p key
             already exists.
 
             \p second is true if new item has been added or \p false if the item with \p key
             already exists.
 

-            @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList" 
+            @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"

             as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
             as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
             synchronization.


@@ -565,7 +565,7 @@ namespace cds { namespace container {
         /**
             The operation performs inserting or changing data with lock-free manner.
 
         /**
             The operation performs inserting or changing data with lock-free manner.
 

-            If the item \p val is not found in the map, then \p val is inserted iff \p bAllowInsert is \p true.
+            If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.

             Otherwise, the current element is changed to \p val, the old element will be retired later.
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
             Otherwise, the current element is changed to \p val, the old element will be retired later.
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,


@@ -752,6 +752,28 @@ namespace cds { namespace container {
             return bucket( key ).find( key, f );
         }
 
             return bucket( key ).find( key, f );
         }
 

+        /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+        /**
+            If \p key is not found the function returns \p end().
+
+            @note This function is supported only for map based on \p IterableList
+        */
+        template <typename K>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<K,K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+        find( K const& key )
+        {
+            auto& b = bucket( key );
+            auto it = b.find( key );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end());
+        }
+
+

         /// Finds the key \p val using \p pred predicate for searching
         /**
             The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"
         /// Finds the key \p val using \p pred predicate for searching
         /**
             The function is an analog of \ref cds_nonintrusive_MichaelMap_find_cfunc "find(K const&, Func)"


@@ -765,6 +787,31 @@ namespace cds { namespace container {
             return bucket( key ).find_with( key, pred, f );
         }
 
             return bucket( key ).find_with( key, pred, f );
         }
 

+        /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
+        /**
+            The function is an analog of \p find(K&) but \p pred is used for key comparing.
+            \p Less functor has the interface like \p std::less.
+            \p pred must imply the same element order as the comparator used for building the set.
+
+            If \p key is not found the function returns \p end().
+
+            @note This function is supported only for map based on \p IterableList
+        */
+        template <typename K, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+        find_with( K const& key, Less pred )
+        {
+            auto& b = bucket( key );
+            auto it = b.find_with( key, pred );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end() );
+        }
+

         /// Checks whether the map contains \p key
         /**
             The function searches the item with key equal to \p key
         /// Checks whether the map contains \p key
         /**
             The function searches the item with key equal to \p key


@@ -775,14 +822,6 @@ namespace cds { namespace container {
         {
             return bucket( key ).contains( key );
         }
         {
             return bucket( key ).contains( key );
         }

-        //@cond
-        template <typename K>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find( K const& key )
-        {
-            return bucket( key ).contains( key );
-        }
-        //@endcond

 
         /// Checks whether the map contains \p key using \p pred predicate for searching
         /**
 
         /// Checks whether the map contains \p key using \p pred predicate for searching
         /**


@@ -795,14 +834,6 @@ namespace cds { namespace container {
         {
             return bucket( key ).contains( key, pred );
         }
         {
             return bucket( key ).contains( key, pred );
         }

-        //@cond
-        template <typename K, typename Less>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find_with( K const& key, Less pred )
-        {
-            return bucket( key ).contains( key, pred );
-        }
-        //@endcond

 
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelHashMap_hp_get
 
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelHashMap_hp_get

diff --git a/cds/container/split_list_map.h b/cds/container/split_list_map.h
index 29cd7fc8c7a7ac840323a924fda0db4125cf7946..4d2fdaa078bfbd3e47d17327b1b6ef3c59f11229 100644 (file)
--- a/cds/container/split_list_map.h
+++ b/cds/container/split_list_map.h
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/

-    
+

     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 


@@ -64,7 +64,7 @@ namespace cds { namespace container {
         You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list
         is original data structure based on an ordered list. Suppose, you want construct split-list map based on \p gc::HP GC
         and \p MichaelList as ordered list implementation. Your map should map \p int key to \p std::string value.
         You should decide what garbage collector you want, and what ordered list you want to use. Split-ordered list
         is original data structure based on an ordered list. Suppose, you want construct split-list map based on \p gc::HP GC
         and \p MichaelList as ordered list implementation. Your map should map \p int key to \p std::string value.

-        So, you beginning your program with following include:
+        So, you beginning your code with the following:

         \code
         #include <cds/container/michael_list_hp.h>
         #include <cds/container/split_list_map.h>
         \code
         #include <cds/container/michael_list_hp.h>
         #include <cds/container/split_list_map.h>


@@ -303,9 +303,9 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K>
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K>

-        bool insert( K const& key )
+        bool insert( K&& key )

         {
         {

-            return base_class::emplace( key_type( key ), mapped_type() );
+            return base_class::emplace( key_type( std::forward<K>( key )), mapped_type() );

         }
 
         /// Inserts new node
         }
 
         /// Inserts new node


@@ -320,9 +320,9 @@ namespace cds { namespace container {
             Returns \p true if \p val is inserted into the map, \p false otherwise.
         */
         template <typename K, typename V>
             Returns \p true if \p val is inserted into the map, \p false otherwise.
         */
         template <typename K, typename V>

-        bool insert( K const& key, V const& val )
+        bool insert( K&& key, V&& val )

         {
         {

-            return base_class::emplace( key_type( key ), mapped_type( val ));
+            return base_class::emplace( key_type( std::forward<K>( key )), mapped_type( std::forward<V>( val )));

         }
 
         /// Inserts new node and initialize it by a functor
         }
 
         /// Inserts new node and initialize it by a functor


@@ -357,10 +357,10 @@ namespace cds { namespace container {
             synchronization.
         */
         template <typename K, typename Func>
             synchronization.
         */
         template <typename K, typename Func>

-        bool insert_with( K const& key, Func func )
+        bool insert_with( K&& key, Func func )

         {
             //TODO: pass arguments by reference (make_pair makes copy)
         {
             //TODO: pass arguments by reference (make_pair makes copy)

-            return base_class::insert( std::make_pair( key_type( key ), mapped_type()), func );
+            return base_class::insert( std::make_pair( key_type( std::forward<K>( key )), mapped_type()), func );

         }
 
         /// For key \p key inserts data of type \p mapped_type created from \p args
         }
 
         /// For key \p key inserts data of type \p mapped_type created from \p args


@@ -382,30 +382,49 @@ namespace cds { namespace container {
             If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
             Otherwise, the functor \p func is called with item found.
 
             If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
             Otherwise, the functor \p func is called with item found.
 

-            The functor signature is:
+            The functor \p func signature depends on ordered list:
+
+            <b>for \p MichaelKVList, \p LazyKVList</b>

             \code
                 struct my_functor {
                     void operator()( bool bNew, value_type& item );
                 };
             \endcode
             \code
                 struct my_functor {
                     void operator()( bool bNew, value_type& item );
                 };
             \endcode

-

             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise

-            - \p item - item of the map
+            - \p item - the item found or inserted
+
+            The functor may change any fields of the \p item.second that is \p mapped_type.
+
+            <b>for \p IterableKVList</b>
+            \code
+                void func( value_type& val, value_type * old );
+            \endcode
+            where
+            - \p val - a new data constructed from \p key
+            - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.

 
             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
             \p second is true if new item has been added or \p false if the item with \p key
             already is in the map.
 
 
             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,
             \p second is true if new item has been added or \p false if the item with \p key
             already is in the map.
 

-            @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" as the ordered list see \ref cds_intrusive_item_creating "insert item troubleshooting".
+            @warning For \ref cds_nonintrusive_MichaelKVList_gc "MichaelKVList" and \ref cds_nonintrusive_IterableKVList_gc "IterableKVList"
+            as the ordered list see \ref cds_intrusive_item_creating "insert item troubleshooting".

             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */
         template <typename K, typename Func>
             \ref cds_nonintrusive_LazyKVList_gc "LazyKVList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */
         template <typename K, typename Func>

-        std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
+#ifdef CDS_DOXYGE_INVOKED
+        std::pair<bool, bool>
+#else
+        typename std::enable_if< 
+            std::is_same<K,K>::value && !is_iterable_list< ordered_list >::value,
+            std::pair<bool, bool>
+        >::type
+#endif
+        update( K&& key, Func func, bool bAllowInsert = true )

         {
         {

-            //TODO: pass arguments by reference (make_pair makes copy)
-            typedef decltype( std::make_pair( key_type( key ), mapped_type() )) arg_pair_type;
+            typedef decltype( std::make_pair( key_type( std::forward<K>( key )), mapped_type() )) arg_pair_type;

 
             return base_class::update( std::make_pair( key_type( key ), mapped_type()),
                 [&func]( bool bNew, value_type& item, arg_pair_type const& /*val*/ ) {
 
             return base_class::update( std::make_pair( key_type( key ), mapped_type()),
                 [&func]( bool bNew, value_type& item, arg_pair_type const& /*val*/ ) {


@@ -415,6 +434,21 @@ namespace cds { namespace container {
         }
         //@cond
         template <typename K, typename Func>
         }
         //@cond
         template <typename K, typename Func>

+#ifdef CDS_DOXYGE_INVOKED
+        std::pair<bool, bool>
+#else
+        typename std::enable_if<
+            std::is_same<K, K>::value && is_iterable_list< ordered_list >::value,
+            std::pair<bool, bool>
+        >::type
+#endif
+        update( K&& key, Func func, bool bAllowInsert = true )
+        {
+            return base_class::update( std::make_pair( key_type( std::forward<K>( key )), mapped_type()), func, bAllowInsert );
+        }
+        //@endcond
+        //@cond
+        template <typename K, typename Func>

         CDS_DEPRECATED("ensure() is deprecated, use update()")
         std::pair<bool, bool> ensure( K const& key, Func func )
         {
         CDS_DEPRECATED("ensure() is deprecated, use update()")
         std::pair<bool, bool> ensure( K const& key, Func func )
         {


@@ -422,6 +456,32 @@ namespace cds { namespace container {
         }
         //@endcond
 
         }
         //@endcond
 

+        /// Inserts or updates the node (only for \p IterableKVList)
+        /**
+            The operation performs inserting or changing data with lock-free manner.
+
+            If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
+            Otherwise, the current element is changed to \p val, the old element will be retired later.
+
+            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+            \p second is \p true if \p val has been added or \p false if the item with that key
+            already in the map.
+            */
+        template <typename Q, typename V>
+#ifdef CDS_DOXYGEN_INVOKED
+        std::pair<bool, bool>
+#else
+        typename std::enable_if< 
+            std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
+            std::pair<bool, bool>
+        >::type
+#endif
+        upsert( Q&& key, V&& val, bool bAllowInsert = true )
+        {
+            return base_class::upsert( std::make_pair( std::forward<Q>( key ), std::forward<V>( val )), bAllowInsert );
+        }
+
+

         /// Deletes \p key from the map
         /** \anchor cds_nonintrusive_SplitListMap_erase_val
 
         /// Deletes \p key from the map
         /** \anchor cds_nonintrusive_SplitListMap_erase_val
 


@@ -555,6 +615,23 @@ namespace cds { namespace container {
             return base_class::find( key, [&f](value_type& pair, K const&){ f( pair ); } );
         }
 
             return base_class::find( key, [&f](value_type& pair, K const&){ f( pair ); } );
         }
 

+        /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+        /**
+            If \p key is not found the function returns \p end().
+
+            @note This function is supported only for map based on \p IterableList
+        */
+        template <typename K>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<K,K>::value && is_iterable_list<ordered_list>::value, iterator >::type
+#endif
+        find( K const& key )
+        {
+            return base_class::find( key );
+        }
+

         /// Finds the key \p val using \p pred predicate for searching
         /**
             The function is an analog of \ref cds_nonintrusive_SplitListMap_find_cfunc "find(K const&, Func)"
         /// Finds the key \p val using \p pred predicate for searching
         /**
             The function is an analog of \ref cds_nonintrusive_SplitListMap_find_cfunc "find(K const&, Func)"


@@ -571,6 +648,28 @@ namespace cds { namespace container {
                 [&f](value_type& pair, K const&){ f( pair ); } );
         }
 
                 [&f](value_type& pair, K const&){ f( pair ); } );
         }
 

+        /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
+        /**
+            The function is an analog of \p find(K&) but \p pred is used for key comparing.
+            \p Less functor has interface like \p std::less.
+            \p pred must imply the same element order as the comparator used for building the map.
+
+            If \p key is not found the function returns \p end().
+
+            @note This function is supported only for map based on \p IterableList
+        */
+        template <typename K, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<K, K>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+        find_with( K const& key, Less pred )
+        {
+            CDS_UNUSED( pred );
+            return base_class::find_with( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>() );
+        }
+

         /// Checks whether the map contains \p key
         /**
             The function searches the item with key equal to \p key
         /// Checks whether the map contains \p key
         /**
             The function searches the item with key equal to \p key


@@ -585,14 +684,6 @@ namespace cds { namespace container {
         {
             return base_class::contains( key );
         }
         {
             return base_class::contains( key );
         }

-        //@cond
-        template <typename K>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find( K const& key )
-        {
-            return contains( key );
-        }
-        //@endcond

 
         /// Checks whether the map contains \p key using \p pred predicate for searching
         /**
 
         /// Checks whether the map contains \p key using \p pred predicate for searching
         /**


@@ -606,14 +697,6 @@ namespace cds { namespace container {
             CDS_UNUSED( pred );
             return base_class::contains( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
         }
             CDS_UNUSED( pred );
             return base_class::contains( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
         }

-        //@cond
-        template <typename K, typename Less>
-        CDS_DEPRECATED("deprecated, use contains()")
-        bool find_with( K const& key, Less pred )
-        {
-            return contains( key, pred );
-        }
-        //@endcond

 
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_SplitListMap_hp_get
 
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_SplitListMap_hp_get


@@ -690,8 +773,13 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
         {
             return base_class::statistics();
         }

-    };

 
 

+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return base_class::list_statistics();
+        }
+    };

 
 }} // namespace cds::container
 
 
 }} // namespace cds::container
 

diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h
index 5f301ed5b6cfe55f3e7f6cbf53b0a0505501cccf..febcf44777aaac6d388fde19451b193c745c6550 100644 (file)
--- a/cds/container/split_list_set.h
+++ b/cds/container/split_list_set.h
@@ -889,6 +889,12 @@ namespace cds { namespace container {
             return base_class::statistics();
         }
 
             return base_class::statistics();
         }
 

+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return m_List.statistics();
+        }
+

     protected:
         //@cond
         using base_class::extract_;
     protected:
         //@cond
         using base_class::extract_;

diff --git a/projects/Win/vc14/gtest-map.vcxproj b/projects/Win/vc14/gtest-map.vcxproj
index 7a23a391d64588a0d4ead644106bec389ced0cc9..d46ebcaacb37bc47a555c21929fa2f399b09904d 100644 (file)
--- a/projects/Win/vc14/gtest-map.vcxproj
+++ b/projects/Win/vc14/gtest-map.vcxproj
@@ -96,6 +96,8 @@
     </ClCompile>\r
     <ClCompile Include="..\..\..\test\unit\map\skiplist_rcu_shb.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\map\skiplist_rcu_sht.cpp" />\r
     </ClCompile>\r
     <ClCompile Include="..\..\..\test\unit\map\skiplist_rcu_shb.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\map\skiplist_rcu_sht.cpp" />\r

+    <ClCompile Include="..\..\..\test\unit\map\split_iterable_dhp.cpp" />\r
+    <ClCompile Include="..\..\..\test\unit\map\split_iterable_hp.cpp" />\r

     <ClCompile Include="..\..\..\test\unit\map\split_lazy_dhp.cpp">\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">4503</DisableSpecificWarnings>\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">4503</DisableSpecificWarnings>\r
     <ClCompile Include="..\..\..\test\unit\map\split_lazy_dhp.cpp">\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">4503</DisableSpecificWarnings>\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">4503</DisableSpecificWarnings>\r

diff --git a/projects/Win/vc14/gtest-map.vcxproj.filters b/projects/Win/vc14/gtest-map.vcxproj.filters
index 5b66b74320e5799a9cf5a2f9fe26c7b529642de1..8079ed34ee8cfceee3d86a121ef1325e358764f8 100644 (file)
--- a/projects/Win/vc14/gtest-map.vcxproj.filters
+++ b/projects/Win/vc14/gtest-map.vcxproj.filters
@@ -173,6 +173,12 @@
     <ClCompile Include="..\..\..\test\unit\map\michael_iterable_dhp.cpp">\r
       <Filter>Source Files\MichaelMap</Filter>\r
     </ClCompile>\r
     <ClCompile Include="..\..\..\test\unit\map\michael_iterable_dhp.cpp">\r
       <Filter>Source Files\MichaelMap</Filter>\r
     </ClCompile>\r

+    <ClCompile Include="..\..\..\test\unit\map\split_iterable_hp.cpp">\r
+      <Filter>Source Files\SplitListMap</Filter>\r
+    </ClCompile>\r
+    <ClCompile Include="..\..\..\test\unit\map\split_iterable_dhp.cpp">\r
+      <Filter>Source Files\SplitListMap</Filter>\r
+    </ClCompile>\r

   </ItemGroup>\r
   <ItemGroup>\r
     <ClInclude Include="..\..\..\test\unit\map\test_map.h">\r
   </ItemGroup>\r
   <ItemGroup>\r
     <ClInclude Include="..\..\..\test\unit\map\test_map.h">\r

diff --git a/test/unit/map/split_iterable_dhp.cpp b/test/unit/map/split_iterable_dhp.cpp
new file mode 100644 (file)
index 0000000..ee02acd
--- /dev/null
+++ b/test/unit/map/split_iterable_dhp.cpp
@@ -0,0 +1,257 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include "test_michael_iterable_hp.h"
+
+#include <cds/container/iterable_list_dhp.h>
+#include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
+
+namespace {
+    namespace cc = cds::container;
+    typedef cds::gc::DHP gc_type;
+
+    class SplitListIterableMap_DHP : public cds_test::michael_iterable_map
+    {
+    protected:
+        typedef cds_test::michael_iterable_map base_class;
+
+        void SetUp()
+        {
+            struct map_traits: public cc::split_list::traits {
+                typedef cc::iterable_list_tag ordered_list;
+                typedef hash1 hash;
+                struct ordered_list_traits: public cc::iterable_list::traits
+                {
+                    typedef cmp compare;
+                };
+            };
+            typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits >   map_type;
+
+            cds::gc::dhp::GarbageCollector::Construct( 16, map_type::c_nHazardPtrCount );
+            cds::threading::Manager::attachThread();
+        }
+
+        void TearDown()
+        {
+            cds::threading::Manager::detachThread();
+            cds::gc::dhp::GarbageCollector::Destruct();
+        }
+    };
+
+    TEST_F( SplitListIterableMap_DHP, compare )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::compare< cmp >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, less )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::less< less >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, cmpmix )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::less< less >
+                        , cds::opt::compare< cmp >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, item_counting )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef base_class::less less;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, stat )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cc::split_list::stat<> stat;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef base_class::less less;
+                typedef cc::iterable_list::stat<> stat;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+        EXPECT_NE( m.statistics().m_nInsertSuccess, 0 );
+        EXPECT_NE( m.list_statistics().m_nInsertSuccess, 0 );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, back_off )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::backoff::yield back_off;
+            typedef cds::opt::v::sequential_consistent memory_model;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
+    struct set_static_traits: public cc::split_list::traits
+    {
+        static bool const dynamic_bucket_table = false;
+    };
+
+    TEST_F( SplitListIterableMap_DHP, static_bucket_table )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_DHP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+} // namespace

diff --git a/test/unit/map/split_iterable_hp.cpp b/test/unit/map/split_iterable_hp.cpp
new file mode 100644 (file)
index 0000000..405d3f3
--- /dev/null
+++ b/test/unit/map/split_iterable_hp.cpp
@@ -0,0 +1,258 @@
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include "test_michael_iterable_hp.h"
+
+#include <cds/container/iterable_list_hp.h>
+#include <cds/container/split_list_map.h>
+#include <cds/intrusive/free_list.h>
+
+namespace {
+    namespace cc = cds::container;
+    typedef cds::gc::HP gc_type;
+
+    class SplitListIterableMap_HP : public cds_test::michael_iterable_map
+    {
+    protected:
+        typedef cds_test::michael_iterable_map base_class;
+
+        void SetUp()
+        {
+            struct map_traits: public cc::split_list::traits {
+                typedef cc::iterable_list_tag ordered_list;
+                typedef hash1 hash;
+                struct ordered_list_traits: public cc::iterable_list::traits
+                {
+                    typedef cmp compare;
+                };
+            };
+            typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits >   map_type;
+
+            // +3 - for guarded_ptr
+            cds::gc::hp::GarbageCollector::Construct( map_type::c_nHazardPtrCount + 3, 1, 16 );
+            cds::threading::Manager::attachThread();
+        }
+
+        void TearDown()
+        {
+            cds::threading::Manager::detachThread();
+            cds::gc::hp::GarbageCollector::Destruct( true );
+        }
+    };
+
+    TEST_F( SplitListIterableMap_HP, compare )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::compare< cmp >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, less )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::less< less >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, cmpmix )
+    {
+        typedef cc::SplitListMap< gc_type, key_type, value_type, 
+            typename cc::split_list::make_traits<
+                cc::split_list::ordered_list< cc::iterable_list_tag >
+                , cds::opt::hash< hash1 >
+                , cc::split_list::ordered_list_traits< 
+                    typename cc::iterable_list::make_traits<
+                        cds::opt::less< less >
+                        , cds::opt::compare< cmp >
+                    >::type
+                >
+            >::type
+        > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, item_counting )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef base_class::less less;
+                typedef cds::backoff::empty back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, stat )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cc::split_list::stat<> stat;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef base_class::less less;
+                typedef cc::iterable_list::stat<> stat;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 2 );
+        test( m );
+        EXPECT_NE( m.statistics().m_nInsertSuccess, 0 );
+        EXPECT_NE( m.list_statistics().m_nInsertSuccess, 0 );
+    }
+
+    TEST_F( SplitListIterableMap_HP, back_off )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::backoff::yield back_off;
+            typedef cds::opt::v::sequential_consistent memory_model;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, free_list )
+    {
+        struct map_traits: public cc::split_list::traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 3 );
+        test( m );
+    }
+
+    struct set_static_traits: public cc::split_list::traits
+    {
+        static bool const dynamic_bucket_table = false;
+    };
+
+    TEST_F( SplitListIterableMap_HP, static_bucket_table )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+    TEST_F( SplitListIterableMap_HP, static_bucket_table_free_list )
+    {
+        struct map_traits: public set_static_traits
+        {
+            typedef cc::iterable_list_tag ordered_list;
+            typedef hash1 hash;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::FreeList free_list;
+
+            struct ordered_list_traits: public cc::iterable_list::traits
+            {
+                typedef cmp compare;
+                typedef cds::backoff::pause back_off;
+            };
+        };
+        typedef cc::SplitListMap< gc_type, key_type, value_type, map_traits > map_type;
+
+        map_type m( kSize, 4 );
+        test( m );
+    }
+
+} // namespace

diff --git a/test/unit/map/test_michael_iterable.h b/test/unit/map/test_michael_iterable.h
index 0bc7b527f3491338ef4155dd35c8661bc7865d7c..0e671bdb48d7278c0694043e463343d758e666ce 100644 (file)
--- a/test/unit/map/test_michael_iterable.h
+++ b/test/unit/map/test_michael_iterable.h
@@ -86,6 +86,10 @@ namespace cds_test {
                     EXPECT_TRUE( false );
                 } ));
 
                     EXPECT_TRUE( false );
                 } ));
 

+                EXPECT_TRUE( m.find( i ) == m.end() );
+                EXPECT_TRUE( m.find( i.nKey ) == m.end() );
+                EXPECT_TRUE( m.find_with( other_item( i.nKey ), other_less() ) == m.end() );
+

                 std::pair< bool, bool > updResult;
 
                 switch ( i.nKey % 17 ) {
                 std::pair< bool, bool > updResult;
 
                 switch ( i.nKey % 17 ) {


@@ -287,6 +291,15 @@ namespace cds_test {
                     EXPECT_EQ( v.first.nKey, v.second.nVal );
                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
                 } ));
                     EXPECT_EQ( v.first.nKey, v.second.nVal );
                     EXPECT_EQ( std::to_string( v.first.nKey ), v.second.strVal );
                 } ));

+
+                ASSERT_TRUE( m.find( i ) != m.end() );
+                ASSERT_TRUE( m.find( i.nKey ) != m.end() );
+                ASSERT_TRUE( m.find_with( other_item( i.nKey ), other_less() ) != m.end() );
+
+                EXPECT_EQ( m.find( i )->first.nKey, i.nKey );
+                EXPECT_EQ( m.find( i.nKey )->first.nKey, i.nKey );
+                EXPECT_EQ( m.find_with( other_item( i.nKey ), other_less() )->first.nKey, i.nKey );
+

             }
             EXPECT_FALSE( m.empty() );
             EXPECT_CONTAINER_SIZE( m, kkSize );
             }
             EXPECT_FALSE( m.empty() );
             EXPECT_CONTAINER_SIZE( m, kkSize );