From 5321b15564e2cff70c9eabbf604e5ef9aee94dfa Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 27 Oct 2016 23:32:00 +0300 Subject: [PATCH] Added SplitListMap based on IterableList --- cds/container/michael_map.h | 69 ++++-- cds/container/split_list_map.h | 152 +++++++++--- cds/container/split_list_set.h | 6 + projects/Win/vc14/gtest-map.vcxproj | 2 + projects/Win/vc14/gtest-map.vcxproj.filters | 6 + test/unit/map/split_iterable_dhp.cpp | 257 +++++++++++++++++++ test/unit/map/split_iterable_hp.cpp | 258 ++++++++++++++++++++ test/unit/map/test_michael_iterable.h | 13 + 8 files changed, 712 insertions(+), 51 deletions(-) create mode 100644 test/unit/map/split_iterable_dhp.cpp create mode 100644 test/unit/map/split_iterable_hp.cpp diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h index 6c67eb30..51e2ad6b 100644 --- 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. - The functor \p func signature depends of \p OrderedList: + The functor \p func signature depends on \p OrderedList: for \p MichaelKVList, \p LazyKVList \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 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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::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 - 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 - 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 diff --git a/cds/container/split_list_map.h b/cds/container/split_list_map.h index 29cd7fc8..4d2fdaa0 100644 --- 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/ - + 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 #include @@ -303,9 +303,9 @@ namespace cds { namespace container { Returns \p true if inserting successful, \p false otherwise. */ template - 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( 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 - 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( key )), mapped_type( std::forward( val ))); } /// Inserts new node and initialize it by a functor @@ -357,10 +357,10 @@ namespace cds { namespace container { synchronization. */ template - 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( 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: + + for \p MichaelKVList, \p LazyKVList \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. + + for \p IterableKVList + \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 std::pair 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 - std::pair update( K const& key, Func func, bool bAllowInsert = true ) +#ifdef CDS_DOXYGE_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same::value && !is_iterable_list< ordered_list >::value, + std::pair + >::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( 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 +#ifdef CDS_DOXYGE_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same::value && is_iterable_list< ordered_list >::value, + std::pair + >::type +#endif + update( K&& key, Func func, bool bAllowInsert = true ) + { + return base_class::update( std::make_pair( key_type( std::forward( key )), mapped_type()), func, bAllowInsert ); + } + //@endcond + //@cond + template CDS_DEPRECATED("ensure() is deprecated, use update()") std::pair 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 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 +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value, + std::pair + >::type +#endif + upsert( Q&& key, V&& val, bool bAllowInsert = true ) + { + return base_class::upsert( std::make_pair( std::forward( key ), std::forward( 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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::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() ); + } + /// 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 - 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()); } - //@cond - template - 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 diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index 5f301ed5..febcf447 100644 --- 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(); } + /// 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_; diff --git a/projects/Win/vc14/gtest-map.vcxproj b/projects/Win/vc14/gtest-map.vcxproj index 7a23a391..d46ebcaa 100644 --- a/projects/Win/vc14/gtest-map.vcxproj +++ b/projects/Win/vc14/gtest-map.vcxproj @@ -96,6 +96,8 @@ + + 4503 4503 diff --git a/projects/Win/vc14/gtest-map.vcxproj.filters b/projects/Win/vc14/gtest-map.vcxproj.filters index 5b66b743..8079ed34 100644 --- a/projects/Win/vc14/gtest-map.vcxproj.filters +++ b/projects/Win/vc14/gtest-map.vcxproj.filters @@ -173,6 +173,12 @@ Source Files\MichaelMap + + Source Files\SplitListMap + + + Source Files\SplitListMap + diff --git a/test/unit/map/split_iterable_dhp.cpp b/test/unit/map/split_iterable_dhp.cpp new file mode 100644 index 00000000..ee02acde --- /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 +#include +#include + +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 index 00000000..405d3f3f --- /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 +#include +#include + +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 0bc7b527..0e671bdb 100644 --- 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( 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 ); -- 2.34.1