From d9905d3b97515b456b4a765d34bf5f57d12e5acb Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 14 Feb 2016 12:18:37 +0300 Subject: [PATCH] Moved gc::nogc-based list tests 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/lazy_nogc.cpp | 140 ++++++++ test/unit/list/michael_nogc.cpp | 125 +++++++ test/unit/list/test_list_nogc.h | 335 +++++++++++++++++++ 6 files changed, 614 insertions(+) create mode 100644 test/unit/list/lazy_nogc.cpp create mode 100644 test/unit/list/michael_nogc.cpp create mode 100644 test/unit/list/test_list_nogc.h diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index 20ef3853..4cabb611 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -35,6 +35,7 @@ + @@ -83,8 +84,10 @@ + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index 59ab214e..8396e454 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -39,6 +39,9 @@ Header Files + + Header Files + @@ -104,5 +107,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 96f7f65f..2014cf46 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 lazy_hp.cpp lazy_dhp.cpp + lazy_nogc.cpp michael_hp.cpp michael_dhp.cpp + michael_nogc.cpp ) include_directories( diff --git a/test/unit/list/lazy_nogc.cpp b/test/unit/list/lazy_nogc.cpp new file mode 100644 index 00000000..c1507445 --- /dev/null +++ b/test/unit/list/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_list_nogc.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::nogc gc_type; + + class LazyList_NOGC : public cds_test::list_nogc + {}; + + TEST_F( LazyList_NOGC, less_ordered ) + { + typedef cc::LazyList< gc_type, item, + typename cc::lazy_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyList_NOGC, compare_ordered ) + { + typedef cc::LazyList< gc_type, item, + typename cc::lazy_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyList_NOGC, mix_ordered ) + { + typedef cc::LazyList< gc_type, item, + 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( LazyList_NOGC, item_counting ) + { + struct traits : public cc::lazy_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::LazyList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyList_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::LazyList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyList_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::LazyList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( LazyList_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::LazyList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/michael_nogc.cpp b/test/unit/list/michael_nogc.cpp new file mode 100644 index 00000000..88331cb9 --- /dev/null +++ b/test/unit/list/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_list_nogc.h" +#include + +namespace { + namespace cc = cds::container; + typedef cds::gc::nogc gc_type; + + class MichaelList_NOGC : public cds_test::list_nogc + {}; + + TEST_F( MichaelList_NOGC, less_ordered ) + { + typedef cc::MichaelList< gc_type, item, + typename cc::michael_list::make_traits< + cds::opt::less< lt > + >::type + > list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelList_NOGC, compare_ordered ) + { + typedef cc::MichaelList< gc_type, item, + typename cc::michael_list::make_traits< + cds::opt::compare< cmp > + >::type + > list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelList_NOGC, mix_ordered ) + { + typedef cc::MichaelList< gc_type, item, + 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( MichaelList_NOGC, item_counting ) + { + struct traits : public cc::michael_list::traits + { + typedef lt less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef cc::MichaelList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelList_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::MichaelList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + + TEST_F( MichaelList_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::MichaelList list_type; + + list_type l; + test( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/test_list_nogc.h b/test/unit/list/test_list_nogc.h new file mode 100644 index 00000000..b3812121 --- /dev/null +++ b/test/unit/list/test_list_nogc.h @@ -0,0 +1,335 @@ +/* + 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_LIST_NOGC_H +#define CDSUNIT_LIST_TEST_LIST_NOGC_H + +#include +#include + +namespace cds_test { + + class list_nogc : public fixture + { + public: + struct item { + int nKey; + int nVal; + + item() + {} + + item( int key ) + : nKey( key ) + , nVal( key * 2 ) + {} + + item( int key, int val ) + : nKey( key ) + , nVal( val ) + {} + + item( const item& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + {} + + int key() const + { + return nKey; + } + }; + + template + struct lt + { + bool operator ()( const T& v1, const T& v2 ) const + { + return v1.key() < v2.key(); + } + + template + bool operator ()( const T& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()( const Q& v1, const T& v2 ) const + { + return v1 < v2.key(); + } + }; + + template + struct cmp { + int operator ()( const T& v1, const T& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + + template + int operator ()( const T& v1, const Q& v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + int operator ()( const Q& v1, const T& v2 ) const + { + if ( v1 < v2.key() ) + return -1; + return v1 > v2.key() ? 1 : 0; + } + }; + + struct other_item + { + int nKey; + + other_item() + {} + + other_item( int n ) + : nKey( n ) + {} + }; + + struct other_less + { + template + bool operator()( T1 const& t1, T2 const& t2 ) const + { + return t1.nKey < t2.nKey; + } + }; + + protected: + template + void test( List& l ) + { + // Precondition: list is empty + // Postcondition: list is empty + + static const size_t nSize = 20; + typedef typename List::value_type value_type; + value_type arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].nKey = static_cast(i); + arr[i].nVal = arr[i].nKey * 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 ) == l.end()); + EXPECT_TRUE( l.contains( i.nKey ) == l.end()); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less()) == l.end()); + + switch ( i.nKey & 3 ) { + case 0: + { + auto it = l.insert( i.nKey ); + EXPECT_FALSE( it == l.end()); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, it->nKey * 2 ); + it = l.contains( i.nKey ); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, it->nKey * 2 ); + it = l.insert( i.nKey ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 1: + { + auto it = l.insert( i ); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nVal ); + it = l.contains( i ); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nVal ); + it = l.insert( i ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 2: + { + auto it = l.emplace( i.nKey, i.nKey * 100 ); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nKey * 100 ); + it = l.contains( other_item( i.nKey ), other_less()); + EXPECT_FALSE( it == l.end() ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nKey * 100 ); + it = l.emplace( i.nKey, i.nKey * 50 ); + EXPECT_TRUE( it == l.end() ); + break; + } + case 3: + { + auto pair = l.update( i.nKey, false ); + EXPECT_TRUE( pair.first == l.end()); + EXPECT_FALSE( pair.second ); + + pair = l.update( i.nKey ); + EXPECT_FALSE( pair.first == l.end() ); + EXPECT_TRUE( pair.second ); + pair.first->nVal = i.nKey * 3; + EXPECT_EQ( pair.first->nKey, i.nKey ); + + auto it = l.contains( other_item( i.nKey ), other_less() ); + EXPECT_FALSE( it == l.end() ); + EXPECT_TRUE( it == pair.first ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nKey * 3 ); + + pair = l.update( i.nKey, false ); + EXPECT_FALSE( pair.first == l.end() ); + EXPECT_TRUE( pair.first == it ); + EXPECT_FALSE( pair.second ); + EXPECT_EQ( pair.first->nKey, i.nKey ); + pair.first->nVal = i.nKey * 5; + + it = l.contains( other_item( i.nKey ), other_less() ); + EXPECT_FALSE( it == l.end() ); + EXPECT_TRUE( it == pair.first ); + EXPECT_EQ( it->nKey, i.nKey ); + EXPECT_EQ( it->nVal, i.nKey * 5 ); + } + break; + } + + EXPECT_TRUE( l.contains( i ) != l.end()); + EXPECT_TRUE( l.contains( i.nKey ) != l.end()); + EXPECT_TRUE( l.contains( other_item( i.nKey ), 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::value_type value_type; + value_type arr[nSize]; + + for ( size_t i = 0; i < nSize; ++i ) { + arr[i].nKey = static_cast(i); + arr[i].nVal = arr[i].nKey; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i ) != l.end()); + + int key = 0; + for ( auto& it : l ) { + EXPECT_EQ( key, it.nKey ); + EXPECT_EQ( it.nVal, it.nKey ); + it.nVal = it.nKey * 10; + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( key, it->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 10, it->nVal ); + ++key; + } + EXPECT_EQ( static_cast(key), nSize ); + + key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( key, it->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 10, it->nVal ); + it->nVal = it->nKey * 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->nKey ); + EXPECT_EQ( key, (*it).nKey ); + EXPECT_EQ( it->nKey * 2, it->nVal ); + ++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_LIST_NOGC_H -- 2.34.1