Added SplitListMap<HP> based on IterableList
authorkhizmax <libcds.dev@gmail.com>
Thu, 27 Oct 2016 20:32:00 +0000 (23:32 +0300)
committerkhizmax <libcds.dev@gmail.com>
Thu, 27 Oct 2016 20:32:00 +0000 (23:32 +0300)
cds/container/michael_map.h
cds/container/split_list_map.h
cds/container/split_list_set.h
projects/Win/vc14/gtest-map.vcxproj
projects/Win/vc14/gtest-map.vcxproj.filters
test/unit/map/split_iterable_dhp.cpp [new file with mode: 0644]
test/unit/map/split_iterable_hp.cpp [new file with mode: 0644]
test/unit/map/test_michael_iterable.h

index 6c67eb3..51e2ad6 100644 (file)
@@ -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.
 
-            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
@@ -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.
 
-            @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.
@@ -565,7 +565,7 @@ namespace cds { namespace container {
         /**
             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,
@@ -752,6 +752,28 @@ namespace cds { namespace container {
             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)"
@@ -765,6 +787,31 @@ namespace cds { namespace container {
             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
@@ -775,14 +822,6 @@ namespace cds { namespace container {
         {
             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
         /**
@@ -795,14 +834,6 @@ namespace cds { namespace container {
         {
             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
index 29cd7fc..4d2fdaa 100644 (file)
@@ -5,7 +5,7 @@
 
     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:
 
@@ -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.
-        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>
@@ -303,9 +303,9 @@ namespace cds { namespace container {
             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
@@ -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>
-        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
@@ -357,10 +357,10 @@ namespace cds { namespace container {
             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)
-            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
@@ -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.
 
-            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
-
             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.
 
-            @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>
-        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*/ ) {
@@ -415,6 +434,21 @@ namespace cds { namespace container {
         }
         //@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 )
         {
@@ -422,6 +456,32 @@ namespace cds { namespace container {
         }
         //@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
 
@@ -555,6 +615,23 @@ namespace cds { namespace container {
             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)"
@@ -571,6 +648,28 @@ namespace cds { namespace container {
                 [&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
@@ -585,14 +684,6 @@ namespace cds { namespace container {
         {
             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
         /**
@@ -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>());
         }
-        //@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
@@ -690,8 +773,13 @@ namespace cds { namespace container {
         {
             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
 
index 5f301ed..febcf44 100644 (file)
@@ -889,6 +889,12 @@ namespace cds { namespace container {
             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_;
index 7a23a39..d46ebca 100644 (file)
@@ -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 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
index 5b66b74..8079ed3 100644 (file)
     <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
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
@@ -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
@@ -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
index 0bc7b52..0e671bd 100644 (file)
@@ -86,6 +86,10 @@ namespace cds_test {
                     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 ) {
@@ -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 );
                 } ));
+
+                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 );