From 6a7eea5801ca026b1eddc61da720e42331c93f44 Mon Sep 17 00:00:00 2001 From: khizmax Date: Wed, 17 Feb 2016 22:48:43 +0300 Subject: [PATCH] Moved unit test for append-only key/value list to gtest framework --- projects/Win/vc14/gtest-list.vcxproj | 3 + projects/Win/vc14/gtest-list.vcxproj.filters | 9 + test/unit/list/CMakeLists.txt | 2 + test/unit/list/kv_lazy_nogc.cpp | 140 +++++++ test/unit/list/kv_michael_nogc.cpp | 125 +++++++ test/unit/list/test_kv_list_nogc.h | 369 +++++++++++++++++++ 6 files changed, 648 insertions(+) create mode 100644 test/unit/list/kv_lazy_nogc.cpp create mode 100644 test/unit/list/kv_michael_nogc.cpp create mode 100644 test/unit/list/test_kv_list_nogc.h diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index a954d055..823283a2 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -35,6 +35,7 @@ + @@ -89,8 +90,10 @@ + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index dcbca55c..95727c60 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -57,6 +57,9 @@ Header Files + + Header Files + @@ -170,5 +173,11 @@ 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 4acc5459..25a20042 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -20,8 +20,10 @@ set(CDSGTEST_LIST_SOURCES intrusive_michael_rcu_sht.cpp kv_lazy_hp.cpp kv_lazy_dhp.cpp + kv_lazy_nogc.cpp kv_michael_hp.cpp kv_michael_dhp.cpp + kv_michael_nogc.cpp lazy_hp.cpp lazy_dhp.cpp lazy_nogc.cpp diff --git a/test/unit/list/kv_lazy_nogc.cpp b/test/unit/list/kv_lazy_nogc.cpp new file mode 100644 index 00000000..db732cbb --- /dev/null +++ b/test/unit/list/kv_lazy_nogc.cpp @@ -0,0 +1,140 @@ +/* + 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_nogc.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::nogc gc_type; + + class LazyKVList_NOGC : public cds_test::kv_list_nogc + {}; + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/kv_michael_nogc.cpp b/test/unit/list/kv_michael_nogc.cpp new file mode 100644 index 00000000..083aa6d5 --- /dev/null +++ b/test/unit/list/kv_michael_nogc.cpp @@ -0,0 +1,125 @@ +/* + 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_nogc.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::nogc gc_type; + + class MichaelKVList_NOGC : public cds_test::kv_list_nogc + {}; + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelKVList_NOGC, 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( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/test_kv_list_nogc.h b/test/unit/list/test_kv_list_nogc.h new file mode 100644 index 00000000..aff834af --- /dev/null +++ b/test/unit/list/test_kv_list_nogc.h @@ -0,0 +1,369 @@ +/* + 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_NOGC_H +#define CDSUNIT_LIST_TEST_KV_LIST_NOGC_H + +#include +#include + +namespace cds_test { + + class kv_list_nogc : public fixture + { + public: + struct key_type { + int key; + + key_type() = delete; + explicit key_type( int n ) + : key( n ) + {} + + key_type( key_type const& s ) + : key( s.key ) + {} + + key_type( key_type&& s ) + : key( s.key ) + { + s.key = 0; + } + }; + + 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 key; + + other_key() + {} + + other_key( int n ) + : key( n ) + {} + }; + + struct other_less + { + template + bool operator()( T1 const& t1, T2 const& t2 ) const + { + return t1.key < t2.key; + } + }; + + protected: + template + void test( 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_TRUE( l.contains( i.key ) == l.end()); + EXPECT_TRUE( l.contains( key_type( i.key )) == l.end()); + EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) == l.end()); + + switch ( i.key % 5 ) { + case 0: + { + auto it = l.insert( i.key ); + ASSERT_FALSE( it == l.end()); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, 0 ); + it = l.contains( i.key ); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, 0 ); + it = l.insert( i.key ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 1: + { + auto it = l.insert( i.key, i.val ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.val ); + it = l.contains( key_type( i.key )); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.val ); + it = l.insert( key_type( i.key ), i.val ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 2: + { + auto it = l.emplace( i.key, i.key * 100 ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 100 ); + it = l.contains( other_key( i.key ), other_less()); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 100 ); + it = l.emplace( i.key, i.key * 50 ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 3: + { + auto pair = l.update( i.key, false ); + EXPECT_TRUE( pair.first == l.end()); + EXPECT_FALSE( pair.second ); + + pair = l.update( i.key ); + ASSERT_FALSE( pair.first == l.end() ); + EXPECT_TRUE( pair.second ); + pair.first->second.val = i.key * 3; + + auto it = l.contains( other_key( i.key ), other_less() ); + ASSERT_FALSE( it == l.end() ); + EXPECT_TRUE( it == pair.first ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 3 ); + + pair = l.update( i.key, false ); + ASSERT_FALSE( pair.first == l.end() ); + EXPECT_TRUE( pair.first == it ); + EXPECT_FALSE( pair.second ); + EXPECT_EQ( pair.first->first.key, i.key ); + pair.first->second.val = i.key * 5; + + it = l.contains( other_key( i.key ), other_less() ); + ASSERT_FALSE( it == l.end() ); + EXPECT_TRUE( it == pair.first ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 5 ); + break; + } + case 4: + { + auto it = l.insert_with( key_type( i.key ), [&i]( list_value_type& n ) { + EXPECT_EQ( i.key, n.first.key ); + n.second.val = n.first.key * 7; + }); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 7 ); + it = l.contains( i.key ); + ASSERT_FALSE( it == l.end() ); + EXPECT_EQ( it->first.key, i.key ); + EXPECT_EQ( it->second.val, i.key * 7 ); + it = l.insert_with( i.key, []( list_value_type& ) { + EXPECT_TRUE( false ); + }); + EXPECT_TRUE( it == l.end() ); + break; + } + } + + EXPECT_TRUE( l.contains( i.key ) != l.end()); + EXPECT_TRUE( l.contains( key_type( i.key )) != l.end()); + EXPECT_TRUE( l.contains( other_key( i.key ), other_less()) != l.end()); + + EXPECT_FALSE( l.empty() ); + } + + 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; + 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); + 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 ) != l.end()); + + 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( 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.key ); + EXPECT_EQ( it->first.key * 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_NOGC_H -- 2.34.1