From ba2a5aa1155973b202518c6fb013c0fb84f0d9e6 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 16 Feb 2016 23:08:45 +0300 Subject: [PATCH] Moved HP-based KV-list unit test to gtest framework --- cds/container/details/make_lazy_kvlist.h | 24 +- cds/container/details/make_michael_kvlist.h | 24 +- cds/container/impl/lazy_kvlist.h | 2 + cds/container/impl/michael_kvlist.h | 2 + projects/Win/vc14/gtest-list.vcxproj | 6 + projects/Win/vc14/gtest-list.vcxproj.filters | 18 + test/unit/list/CMakeLists.txt | 4 + test/unit/list/kv_lazy_dhp.cpp | 162 +++++++ test/unit/list/kv_lazy_hp.cpp | 163 +++++++ test/unit/list/kv_michael_dhp.cpp | 146 +++++++ test/unit/list/kv_michael_hp.cpp | 147 +++++++ test/unit/list/test_kv_list.h | 420 +++++++++++++++++++ test/unit/list/test_kv_list_hp.h | 138 ++++++ 13 files changed, 1250 insertions(+), 6 deletions(-) create mode 100644 test/unit/list/kv_lazy_dhp.cpp create mode 100644 test/unit/list/kv_lazy_hp.cpp create mode 100644 test/unit/list/kv_michael_dhp.cpp create mode 100644 test/unit/list/kv_michael_hp.cpp create mode 100644 test/unit/list/test_kv_list.h create mode 100644 test/unit/list/test_kv_list_hp.h diff --git a/cds/container/details/make_lazy_kvlist.h b/cds/container/details/make_lazy_kvlist.h index ae5d0c92..2d3a4692 100644 --- a/cds/container/details/make_lazy_kvlist.h +++ b/cds/container/details/make_lazy_kvlist.h @@ -52,9 +52,13 @@ namespace cds { namespace container { { value_type m_Data; + node_type( key_type const& key ) + : m_Data( key, mapped_type() ) + {} + template node_type( Q const& key ) - : m_Data( key, mapped_type() ) + : m_Data( key_type( key ), mapped_type() ) {} template @@ -62,9 +66,23 @@ namespace cds { namespace container { : m_Data( pair ) {} + node_type( key_type const& key, mapped_type const& value ) + : m_Data( key, value ) + {} + + template + node_type( key_type const& key, R const& value ) + : m_Data( key, mapped_type( value ) ) + {} + + template + node_type( Q const& key, mapped_type const& value ) + : m_Data( key_type( key ), value ) + {} + template node_type( Q const& key, R const& value ) - : m_Data( key, value ) + : m_Data( key_type( key ), mapped_type( value )) {} template @@ -109,7 +127,7 @@ namespace cds { namespace container { struct intrusive_traits: public original_type_traits { - typedef intrusive::lazy_list::base_hook< opt::gc > hook; + typedef intrusive::lazy_list::base_hook< opt::gc, opt::lock_type< typename original_type_traits::lock_type >> hook; typedef node_deallocator disposer; typedef typename std::conditional< std::is_same< typename original_type_traits::equal_to, cds::opt::none >::value, diff --git a/cds/container/details/make_michael_kvlist.h b/cds/container/details/make_michael_kvlist.h index 9419068c..b1513061 100644 --- a/cds/container/details/make_michael_kvlist.h +++ b/cds/container/details/make_michael_kvlist.h @@ -52,9 +52,13 @@ namespace cds { namespace container { { pair_type m_Data; + node_type( key_type const& key ) + : m_Data( key, value_type() ) + {} + template node_type( Q const& key ) - : m_Data( key, value_type() ) + : m_Data( key_type(key), value_type() ) {} template @@ -62,14 +66,28 @@ namespace cds { namespace container { : m_Data( pair ) {} + node_type( key_type const& key, value_type const& value ) + : m_Data( key, value ) + {} + + template + node_type( key_type const& key, R const& value ) + : m_Data( key, value_type( value )) + {} + + template + node_type( Q const& key, value_type const& value ) + : m_Data( key_type( key ), value ) + {} + template node_type( Q const& key, R const& value ) - : m_Data( key, value ) + : m_Data( key_type( key ), value_type( value )) {} template< typename Ky, typename... Args> node_type( Ky&& key, Args&&... args ) - : m_Data( std::forward(key), std::move( value_type( std::forward(args)...))) + : m_Data( key_type( std::forward(key)), std::move( value_type( std::forward(args)...))) {} }; diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index a8a96dab..5db39fc9 100644 --- a/cds/container/impl/lazy_kvlist.h +++ b/cds/container/impl/lazy_kvlist.h @@ -134,6 +134,8 @@ namespace cds { namespace container { typedef typename maker::key_comparator key_comparator; ///< key comparing functor typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + protected: //@cond typedef typename base_class::value_type node_type; diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index dd4fa428..c1053ee7 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -137,6 +137,8 @@ namespace cds { namespace container { typedef typename maker::key_comparator key_comparator; ///< key comparison functor typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + protected: //@cond typedef typename base_class::value_type node_type; diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index 4ab86dde..a954d055 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -33,6 +33,8 @@ + + @@ -85,6 +87,10 @@ + + + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index 16c83276..dcbca55c 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -51,6 +51,12 @@ Header Files + + Header Files + + + Header Files + @@ -152,5 +158,17 @@ Source Files + + Source Files + + + Source Files + + + Source Files + + + Source Files + \ No newline at end of file diff --git a/test/unit/list/CMakeLists.txt b/test/unit/list/CMakeLists.txt index dbe84711..4acc5459 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -18,6 +18,10 @@ set(CDSGTEST_LIST_SOURCES intrusive_michael_rcu_gpt.cpp intrusive_michael_rcu_shb.cpp intrusive_michael_rcu_sht.cpp + kv_lazy_hp.cpp + kv_lazy_dhp.cpp + kv_michael_hp.cpp + kv_michael_dhp.cpp lazy_hp.cpp lazy_dhp.cpp lazy_nogc.cpp diff --git a/test/unit/list/kv_lazy_dhp.cpp b/test/unit/list/kv_lazy_dhp.cpp new file mode 100644 index 00000000..9b242974 --- /dev/null +++ b/test/unit/list/kv_lazy_dhp.cpp @@ -0,0 +1,162 @@ +/* + 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_kv_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::DHP gc_type; + + class LazyKVList_DHP : public cds_test::kv_list_hp + { + protected: + void SetUp() + { + typedef cc::LazyKVList< gc_type, key_type, value_type > list_type; + + cds::gc::dhp::GarbageCollector::Construct( 16, list_type::c_nHazardPtrCount ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct(); + } + }; + + TEST_F( LazyKVList_DHP, less_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, compare_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, mix_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, item_counting ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, backoff ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, seq_cst ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_DHP, mutex ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef std::mutex lock_type; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/kv_lazy_hp.cpp b/test/unit/list/kv_lazy_hp.cpp new file mode 100644 index 00000000..fd5f0c85 --- /dev/null +++ b/test/unit/list/kv_lazy_hp.cpp @@ -0,0 +1,163 @@ +/* + 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_kv_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class LazyKVList_HP : public cds_test::kv_list_hp + { + protected: + void SetUp() + { + typedef cc::LazyKVList< gc_type, key_type, value_type > list_type; + + // +1 - for guarded_ptr + cds::gc::hp::GarbageCollector::Construct( list_type::c_nHazardPtrCount + 1, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + }; + + TEST_F( LazyKVList_HP, less_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, compare_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, mix_ordered ) + { + typedef cc::LazyKVList< gc_type, key_type, value_type, + typename cc::lazy_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, item_counting ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, backoff ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, seq_cst ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( LazyKVList_HP, mutex ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef std::mutex lock_type; + }; + typedef cc::LazyKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/kv_michael_dhp.cpp b/test/unit/list/kv_michael_dhp.cpp new file mode 100644 index 00000000..f942b96c --- /dev/null +++ b/test/unit/list/kv_michael_dhp.cpp @@ -0,0 +1,146 @@ +/* + 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_kv_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::DHP gc_type; + + class MichaelKVList_DHP : public cds_test::kv_list_hp + { + protected: + void SetUp() + { + typedef cc::MichaelKVList< gc_type, key_type, value_type > list_type; + + cds::gc::dhp::GarbageCollector::Construct( 16, list_type::c_nHazardPtrCount ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct(); + } + }; + + TEST_F( MichaelKVList_DHP, less_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_DHP, compare_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_DHP, mix_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_DHP, item_counting ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_DHP, backoff ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_DHP, seq_cst ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/kv_michael_hp.cpp b/test/unit/list/kv_michael_hp.cpp new file mode 100644 index 00000000..baca4a35 --- /dev/null +++ b/test/unit/list/kv_michael_hp.cpp @@ -0,0 +1,147 @@ +/* + 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_kv_list_hp.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class MichaelKVList_HP : public cds_test::kv_list_hp + { + protected: + void SetUp() + { + typedef cc::MichaelKVList< gc_type, key_type, value_type > list_type; + + // +1 - for guarded_ptr + cds::gc::hp::GarbageCollector::Construct( list_type::c_nHazardPtrCount + 1, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + }; + + TEST_F( MichaelKVList_HP, less_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_HP, compare_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_HP, mix_ordered ) + { + typedef cc::MichaelKVList< gc_type, key_type, value_type, + typename cc::michael_list::make_traits< + cds::opt::compare< cmp > + ,cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_HP, item_counting ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_HP, backoff ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + + TEST_F( MichaelKVList_HP, seq_cst ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::MichaelKVList list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + +} // namespace diff --git a/test/unit/list/test_kv_list.h b/test/unit/list/test_kv_list.h new file mode 100644 index 00000000..ee87209e --- /dev/null +++ b/test/unit/list/test_kv_list.h @@ -0,0 +1,420 @@ +/* + 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. +*/ + +#ifndef CDSUNIT_LIST_TEST_KV_LIST_H +#define CDSUNIT_LIST_TEST_KV_LIST_H + +#include +#include + +namespace cds_test { + + class kv_list_common : public fixture + { + public: + struct key_type { + int nKey; + + key_type() = delete; + explicit key_type( int n ) + : nKey( n ) + {} + + key_type( key_type const& s ) + : nKey( s.nKey ) + {} + + key_type( key_type&& s ) + : nKey( s.nKey ) + { + s.nKey = 0; + } + + int key() const + { + return nKey; + } + }; + + struct value_type { + int val; + + value_type() + : val( 0 ) + {} + + explicit value_type( int n ) + : val( n ) + {} + }; + + struct lt + { + bool operator()( key_type const& lhs, key_type const& rhs ) const + { + return lhs.key() < rhs.key(); + } + + bool operator()( key_type const& lhs, int rhs ) const + { + return lhs.key() < rhs; + } + + bool operator()( int lhs, key_type const& rhs ) const + { + return lhs < rhs.key(); + } + + template + bool operator ()( T const& v1, T const& v2 ) const + { + return v1.key() < v2.key(); + } + }; + + struct cmp + { + int operator()( key_type const& lhs, key_type const& rhs ) const + { + return lhs.key() - rhs.key(); + } + + int operator()( key_type const& lhs, int rhs ) const + { + return lhs.key() - rhs; + } + + int operator()( int lhs, key_type const& rhs ) const + { + return lhs - rhs.key(); + } + + template + int operator ()( T const& lhs, T const& rhs ) const + { + return lhs.key() - rhs.key(); + } + }; + + struct other_key + { + int nKey; + + other_key() + {} + + other_key( int n ) + : nKey( n ) + {} + + int key() const + { + return nKey; + } + }; + + struct other_less + { + template + bool operator()( T1 const& t1, T2 const& t2 ) const + { + return t1.key() < t2.key(); + } + }; + + protected: + template + void test_common( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::key_type list_key_type; + typedef typename List::mapped_type list_mapped_type; + typedef typename List::value_type list_value_type; + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i) + 1; + arr[i].val = arr[i].key * 10; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + // insert/find + for ( auto const& i : arr ) { + EXPECT_FALSE( l.contains( i.key )); + EXPECT_FALSE( l.contains( key_type( i.key ))); + EXPECT_FALSE( l.contains( other_key( i.key ), other_less())); + EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} )); + EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} )); + EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} )); + + switch ( i.key % 5 ) { + case 0: + EXPECT_TRUE( l.insert( i.key )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, 0 ); + } )); + EXPECT_FALSE( l.insert( i.key )); + break; + + case 1: + EXPECT_TRUE( l.insert( i.key, i.val )); + EXPECT_TRUE( l.find( key_type(i.key), []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 10 ); + } )); + EXPECT_FALSE( l.insert( key_type( i.key ))); + break; + + case 2: + EXPECT_TRUE( l.insert_with( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey * 2; + })); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 2 ); + } )); + EXPECT_FALSE( l.insert_with( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey * 3; + } )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 2 ); + } )); + break; + + case 3: + { + key_type k( i.key ); + EXPECT_TRUE( l.emplace( std::move(k), i.key * 100 )); + EXPECT_EQ( k.key(), 0 ); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 100 ); + } )); + k.nKey = i.key; + EXPECT_FALSE( l.emplace( std::move( k ), i.key )); + //EXPECT_EQ( k.key(), i.key ); // ??? + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.nKey * 100 ); + } )); + } + break; + case 4: + { + auto pair = l.update( i.key, []( bool bNew, list_value_type& n ) { + ASSERT_TRUE( false ); + }, false ); + EXPECT_FALSE( pair.first ); + EXPECT_FALSE( pair.second ); + + pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) { + EXPECT_TRUE( bNew ); + n.second.val = n.first.nKey * 3; + }); + EXPECT_TRUE( pair.first ); + EXPECT_TRUE( pair.second ); + + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 3 ); + } )); + + pair = l.update( list_key_type(i.key), []( bool bNew, list_value_type& n ) { + EXPECT_FALSE( bNew ); + n.second.val = n.first.nKey * 5; + }); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.second.val, n.first.key() * 5 ); + } )); + } + break; + } + + EXPECT_TRUE( l.contains( i.key )); + EXPECT_TRUE( l.contains( list_key_type(i.key))); + EXPECT_TRUE( l.contains( other_key( i.key ), other_less())); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + n.second.val = n.first.nKey; + } )); + EXPECT_TRUE( l.find( i.key, []( list_value_type& n ) { + EXPECT_EQ( n.first.nKey, n.second.val ); + n.second.val = n.first.nKey * 5; + } )); + EXPECT_TRUE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& n ) { + EXPECT_EQ( n.first.nKey * 5, n.second.val ); + } )); + + auto pair = l.update( i.key, []( bool bNew, list_value_type& n ) { + EXPECT_FALSE( bNew ); + EXPECT_EQ( n.first.nKey * 5, n.second.val ); + n.second.val = n.first.nKey * 3; + }, false ); + EXPECT_TRUE( pair.first ); + EXPECT_FALSE( pair.second ); + + EXPECT_FALSE( l.empty() ); + } + + ASSERT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + // erase + for ( auto const&i : arr ) { + switch ( i.key & 3 ) { + case 0: + EXPECT_TRUE( l.erase( i.key )); + break; + case 1: + EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less())); + break; + case 2: + EXPECT_TRUE( l.erase( i.key, [ &i ]( list_value_type const& n ) { + EXPECT_EQ( n.first.nKey, i.key ); + EXPECT_EQ( n.first.nKey * 3, n.second.val ); + })); + break; + case 3: + EXPECT_TRUE( l.erase_with( other_key( i.key ), other_less(), [ &i ]( list_value_type const& n) { + EXPECT_EQ( n.first.nKey, i.key ); + EXPECT_EQ( n.first.nKey * 3, n.second.val ); + } )); + } + + EXPECT_FALSE( l.contains( i.key )); + EXPECT_FALSE( l.contains( key_type( i.key ))); + EXPECT_FALSE( l.contains( other_key( i.key ), other_less())); + EXPECT_FALSE( l.find( key_type( i.key ), []( list_value_type& ) {} )); + EXPECT_FALSE( l.find( i.key, []( list_value_type& ) {} )); + EXPECT_FALSE( l.find_with( other_key( i.key ), other_less(), []( list_value_type& ) {} )); + } + + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // clear test + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i.key, i.val )); + + ASSERT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + l.clear(); + + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // empty list iterator test + { + List const& cl = l; + EXPECT_TRUE( l.begin() == l.end()); + EXPECT_TRUE( l.cbegin() == l.cend()); + EXPECT_TRUE( cl.begin() == cl.end()); + EXPECT_TRUE( l.begin() == l.cend()); + EXPECT_TRUE( cl.begin() == l.end()); + } + } + + template + void test_ordered_iterator( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i); + arr[i].val = arr[i].key; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i.key, i.val )); + + int key = 0; + for ( auto& it : l ) { + EXPECT_EQ( key, it.first.key() ); + EXPECT_EQ( it.second.val, it.first.key() ); + it.second.val = it.first.key() * 10; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( key, it->first.key() ); + EXPECT_EQ( it->first.key() * 10, it->second.val ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( key, it->first.key() ); + EXPECT_EQ( it->first.key() * 10, it->second.val ); + it->second.val = it->first.key() * 2; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + List const& cl = l; + key = 0; + for ( auto it = cl.begin(); it != cl.end(); ++it ) { + EXPECT_EQ( key, it->first.nKey ); + EXPECT_EQ( it->first.nKey * 2, it->second.val ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + l.clear(); + ASSERT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_LIST_TEST_KV_LIST_H diff --git a/test/unit/list/test_kv_list_hp.h b/test/unit/list/test_kv_list_hp.h new file mode 100644 index 00000000..c401e664 --- /dev/null +++ b/test/unit/list/test_kv_list_hp.h @@ -0,0 +1,138 @@ +/* + 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. +*/ + +#ifndef CDSUNIT_LIST_TEST_KV_LIST_HP_H +#define CDSUNIT_LIST_TEST_KV_LIST_HP_H + +#include "test_kv_list.h" + +namespace cds_test { + + class kv_list_hp : public kv_list_common + { + protected: + template + void test_hp( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::key_type list_key_type; + typedef typename List::mapped_type list_mapped_type; + typedef typename List::value_type list_value_type; + typedef typename List::guarded_ptr guarded_ptr; + + struct key_val { + int key; + int val; + }; + key_val arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].key = static_cast(i); + arr[i].val = arr[i].key * 10; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + guarded_ptr gp; + size_t nCount = 0; + + // get() test + for ( auto& i : arr ) { + gp = l.get( i.key ); + EXPECT_TRUE( !gp ); + gp = l.get_with( other_key( i.key ), other_less()); + EXPECT_TRUE( !gp ); + + EXPECT_TRUE( l.insert( i.key, i.val )); + + gp = l.get( i.key ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 10 ); + gp->second.val = gp->first.nKey * 5; + + gp = l.get_with( other_key( i.key ), other_less()); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 5 ); + gp->second.val = gp->first.nKey * 10; + + ++nCount; + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nCount ); + } + + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nSize ); + + // extract() test + for ( auto const& i : arr ) { + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nCount ); + --nCount; + + gp = l.get( i.key ); + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + + switch ( i.key & 1 ) { + case 0: + gp = l.extract( i.key ); + break; + case 1: + gp = l.extract_with( other_key( i.key ), other_less()); + break; + } + ASSERT_FALSE( !gp ); + EXPECT_EQ( gp->first.nKey, i.key ); + EXPECT_EQ( gp->second.val, gp->first.nKey * 10 ); + + gp = l.get( i.key ); + EXPECT_FALSE( gp ); + + gp = l.extract( i.key ); + EXPECT_FALSE( gp ); + gp = l.extract_with( other_key( i.key ), other_less()); + EXPECT_FALSE( gp ); + } + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + } + }; + +} // namespace cds_list + +#endif // CDSUNIT_LIST_TEST_KV_LIST_HP_H -- 2.34.1