From d009d7b984cda7b5bfa9d7af83f7c69351b9fa94 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 9 Feb 2016 23:29:50 +0300 Subject: [PATCH] Moved append-only ordered list unit test 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/intrusive_lazy_dhp.cpp | 24 +- test/unit/list/intrusive_lazy_hp.cpp | 24 +- test/unit/list/intrusive_lazy_nogc.cpp | 241 +++++++++ test/unit/list/intrusive_michael_dhp.cpp | 20 +- test/unit/list/intrusive_michael_hp.cpp | 20 +- test/unit/list/intrusive_michael_nogc.cpp | 205 ++++++++ test/unit/list/test_intrusive_list.h | 2 +- test/unit/list/test_intrusive_list_nogc.h | 494 +++++++++++++++++++ 11 files changed, 999 insertions(+), 45 deletions(-) create mode 100644 test/unit/list/intrusive_lazy_nogc.cpp create mode 100644 test/unit/list/intrusive_michael_nogc.cpp create mode 100644 test/unit/list/test_intrusive_list_nogc.h diff --git a/projects/Win/vc14/gtest-list.vcxproj b/projects/Win/vc14/gtest-list.vcxproj index f9d0d92a..c16acb51 100644 --- a/projects/Win/vc14/gtest-list.vcxproj +++ b/projects/Win/vc14/gtest-list.vcxproj @@ -29,12 +29,15 @@ + + + diff --git a/projects/Win/vc14/gtest-list.vcxproj.filters b/projects/Win/vc14/gtest-list.vcxproj.filters index 1315a85a..62ba8453 100644 --- a/projects/Win/vc14/gtest-list.vcxproj.filters +++ b/projects/Win/vc14/gtest-list.vcxproj.filters @@ -21,6 +21,9 @@ Header Files + + Header Files + @@ -38,5 +41,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 da92610d..765e2bd8 100644 --- a/test/unit/list/CMakeLists.txt +++ b/test/unit/list/CMakeLists.txt @@ -4,8 +4,10 @@ set(CDSGTEST_LIST_SOURCES ../main.cpp intrusive_lazy_hp.cpp intrusive_lazy_dhp.cpp + intrusive_lazy_nogc.cpp intrusive_michael_hp.cpp intrusive_michael_dhp.cpp + intrusive_michael_nogc.cpp ) include_directories( diff --git a/test/unit/list/intrusive_lazy_dhp.cpp b/test/unit/list/intrusive_lazy_dhp.cpp index 2822cff2..a443b005 100644 --- a/test/unit/list/intrusive_lazy_dhp.cpp +++ b/test/unit/list/intrusive_lazy_dhp.cpp @@ -76,7 +76,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -92,7 +92,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -109,7 +109,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -126,7 +126,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -144,7 +144,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -162,7 +162,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -178,7 +178,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -194,7 +194,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -211,7 +211,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -229,7 +229,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -247,7 +247,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -265,7 +265,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } diff --git a/test/unit/list/intrusive_lazy_hp.cpp b/test/unit/list/intrusive_lazy_hp.cpp index 9b09536a..bddb5d4c 100644 --- a/test/unit/list/intrusive_lazy_hp.cpp +++ b/test/unit/list/intrusive_lazy_hp.cpp @@ -77,7 +77,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -93,7 +93,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -110,7 +110,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -127,7 +127,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -145,7 +145,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -163,7 +163,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -179,7 +179,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -195,7 +195,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -212,7 +212,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -230,7 +230,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -248,7 +248,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -266,7 +266,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } diff --git a/test/unit/list/intrusive_lazy_nogc.cpp b/test/unit/list/intrusive_lazy_nogc.cpp new file mode 100644 index 00000000..bd97556c --- /dev/null +++ b/test/unit/list/intrusive_lazy_nogc.cpp @@ -0,0 +1,241 @@ +/* + 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_intrusive_list_nogc.h" +#include + +namespace { + namespace ci = cds::intrusive; + typedef cds::gc::nogc gc_type; + + class IntrusiveLazyList_NOGC : public cds_test::intrusive_list_nogc + { + public: + typedef cds_test::intrusive_list_nogc::base_item< ci::lazy_list::node< gc_type>> base_item; + typedef cds_test::intrusive_list_nogc::member_item< ci::lazy_list::node< gc_type>> member_item; + + typedef cds_test::intrusive_list_nogc::base_item< ci::lazy_list::node< gc_type, std::mutex>> base_mutex_item; + typedef cds_test::intrusive_list_nogc::member_item< ci::lazy_list::node< gc_type, std::mutex>> member_mutex_item; + }; + + TEST_F( IntrusiveLazyList_NOGC, base_hook ) + { + typedef ci::LazyList< gc_type, base_item, + typename ci::lazy_list::make_traits< + ci::opt::hook< ci::lazy_list::base_hook< cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< base_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_cmp ) + { + typedef ci::LazyList< gc_type, base_item, + typename ci::lazy_list::make_traits< + ci::opt::hook< ci::lazy_list::base_hook< cds::opt::gc< gc_type >>> + , ci::opt::disposer< mock_disposer > + , cds::opt::compare< cmp< base_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_item_counting ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_mutex ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >, cds::opt::lock_type< std::mutex>> hook; + typedef mock_disposer disposer; + typedef cmp< base_mutex_item > compare; + typedef intrusive_list_nogc::less< base_mutex_item > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::LazyList< gc_type, base_mutex_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_backoff ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, base_hook_seqcst ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::LazyList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook ) + { + typedef ci::LazyList< gc_type, member_item, + typename ci::lazy_list::make_traits< + ci::opt::hook< ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< member_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_cmp ) + { + typedef ci::LazyList< gc_type, member_item, + typename ci::lazy_list::make_traits< + ci::opt::hook< ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::compare< cmp< member_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_item_counting ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_seqcst ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_mutex ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_mutex_item, hMember ), cds::opt::gc< gc_type >, cds::opt::lock_type< std::mutex >> hook; + typedef mock_disposer disposer; + typedef cmp< member_mutex_item > compare; + typedef intrusive_list_nogc::less< member_mutex_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::LazyList< gc_type, member_mutex_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveLazyList_NOGC, member_hook_back_off ) + { + struct traits : public ci::lazy_list::traits { + typedef ci::lazy_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef ci::LazyList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/intrusive_michael_dhp.cpp b/test/unit/list/intrusive_michael_dhp.cpp index 7a33a83b..d6de7f05 100644 --- a/test/unit/list/intrusive_michael_dhp.cpp +++ b/test/unit/list/intrusive_michael_dhp.cpp @@ -73,7 +73,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -89,7 +89,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -106,7 +106,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -124,7 +124,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -142,7 +142,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -158,7 +158,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -174,7 +174,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -191,7 +191,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -209,7 +209,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -227,7 +227,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } diff --git a/test/unit/list/intrusive_michael_hp.cpp b/test/unit/list/intrusive_michael_hp.cpp index 2436f18e..26b0bb53 100644 --- a/test/unit/list/intrusive_michael_hp.cpp +++ b/test/unit/list/intrusive_michael_hp.cpp @@ -74,7 +74,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -90,7 +90,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -107,7 +107,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -125,7 +125,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -143,7 +143,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -159,7 +159,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -175,7 +175,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -192,7 +192,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -210,7 +210,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } @@ -228,7 +228,7 @@ namespace { list_type l; test_common( l ); - test_sorted_iterator( l ); + test_ordered_iterator( l ); test_hp( l ); } diff --git a/test/unit/list/intrusive_michael_nogc.cpp b/test/unit/list/intrusive_michael_nogc.cpp new file mode 100644 index 00000000..21a3ff21 --- /dev/null +++ b/test/unit/list/intrusive_michael_nogc.cpp @@ -0,0 +1,205 @@ +/* + 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_intrusive_list_nogc.h" +#include + +namespace { + namespace ci = cds::intrusive; + typedef cds::gc::nogc gc_type; + + class IntrusiveMichaelList_NOGC : public cds_test::intrusive_list_nogc + { + public: + typedef cds_test::intrusive_list_nogc::base_item< ci::michael_list::node< gc_type>> base_item; + typedef cds_test::intrusive_list_nogc::member_item< ci::michael_list::node< gc_type>> member_item; + }; + + TEST_F( IntrusiveMichaelList_NOGC, base_hook ) + { + typedef ci::MichaelList< gc_type, base_item, + typename ci::michael_list::make_traits< + ci::opt::hook< ci::michael_list::base_hook< cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< base_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, base_hook_cmp ) + { + typedef ci::MichaelList< gc_type, base_item, + typename ci::michael_list::make_traits< + ci::opt::hook< ci::michael_list::base_hook< cds::opt::gc< gc_type >>> + , ci::opt::disposer< mock_disposer > + , cds::opt::compare< cmp< base_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, base_hook_item_counting ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::MichaelList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, base_hook_backoff ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::pause back_off; + }; + typedef ci::MichaelList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, base_hook_seqcst ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< base_item > compare; + typedef intrusive_list_nogc::less< base_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::MichaelList< gc_type, base_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, member_hook ) + { + typedef ci::MichaelList< gc_type, member_item, + typename ci::michael_list::make_traits< + ci::opt::hook< ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::less< less< member_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, member_hook_cmp ) + { + typedef ci::MichaelList< gc_type, member_item, + typename ci::michael_list::make_traits< + ci::opt::hook< ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >>> + ,ci::opt::disposer< mock_disposer > + ,cds::opt::compare< cmp< member_item >> + >::type + > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, member_hook_item_counting ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + }; + typedef ci::MichaelList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, member_hook_seqcst ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef ci::MichaelList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + + TEST_F( IntrusiveMichaelList_NOGC, member_hook_back_off ) + { + struct traits : public ci::michael_list::traits { + typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook; + typedef mock_disposer disposer; + typedef cmp< member_item > compare; + typedef intrusive_list_nogc::less< member_item > less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::empty back_off; + }; + typedef ci::MichaelList< gc_type, member_item, traits > list_type; + + list_type l; + test_common( l ); + test_ordered_iterator( l ); + } + +} // namespace diff --git a/test/unit/list/test_intrusive_list.h b/test/unit/list/test_intrusive_list.h index 65130c59..fc3fe801 100644 --- a/test/unit/list/test_intrusive_list.h +++ b/test/unit/list/test_intrusive_list.h @@ -457,7 +457,7 @@ namespace cds_test { } template - void test_sorted_iterator( List& l ) + void test_ordered_iterator( List& l ) { // Precondition: list is empty // Postcondition: list is empty diff --git a/test/unit/list/test_intrusive_list_nogc.h b/test/unit/list/test_intrusive_list_nogc.h new file mode 100644 index 00000000..1d66c0e8 --- /dev/null +++ b/test/unit/list/test_intrusive_list_nogc.h @@ -0,0 +1,494 @@ +/* + 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_INTRUSIVE_LIST_NOGC_H +#define CDSUNIT_LIST_TEST_INTRUSIVE_LIST_NOGC_H + +#include +#include + +namespace cds_test { + + class intrusive_list_nogc : public fixture + { + public: + struct stat { + int nDisposeCount; + int nUpdateExistsCall; + int nUpdateNewCall; + int nFindCall; + + stat() + : nDisposeCount( 0 ) + , nUpdateExistsCall( 0 ) + , nUpdateNewCall( 0 ) + , nFindCall( 0 ) + {} + + stat( const stat& s ) + { + *this = s; + } + + stat& operator =( const stat& s ) + { + memcpy( this, &s, sizeof( s ) ); + return *this; + } + }; + + template + struct base_item : public Node + { + int nKey; + int nVal; + + mutable stat s; + + base_item() + {} + + base_item( int key, int val ) + : nKey( key ) + , nVal( val ) + , s() + {} + + base_item( const base_item& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + , s() + {} + + const int& key() const + { + return nKey; + } + + base_item& operator=( base_item const& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + + base_item& operator=( base_item&& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + }; + + template + struct member_item + { + int nKey; + int nVal; + Node hMember; + mutable stat s; + + member_item() + {} + + member_item( int key, int val ) + : nKey( key ) + , nVal( val ) + , s() + {} + + member_item( const member_item& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + , s() + {} + + const int& key() const + { + return nKey; + } + + member_item& operator =( member_item const& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + + member_item& operator=( member_item&& src ) + { + nKey = src.nKey; + nVal = src.nVal; + return *this; + } + }; + + template + struct less + { + 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(); + } + }; + + struct other_item { + int nKey; + + other_item( int n ) + : nKey( n ) + {} + }; + + struct other_less { + template + bool operator()( T const& i1, Q const& i2 ) const + { + return i1.nKey < i2.nKey; + } + }; + + 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 mock_disposer + { + template + void operator ()( T * p ) + { + ++p->s.nDisposeCount; + } + }; + + struct mock_disposer2 + { + template + void operator ()( T * p ) + { + p->s.nDisposeCount += 10; + } + }; + + struct update_functor + { + template + void operator ()( bool bNew, T& item, T& /*val*/ ) + { + if ( bNew ) + ++item.s.nUpdateNewCall; + else + ++item.s.nUpdateExistsCall; + } + }; + + struct find_functor + { + template + void operator ()( T& item, Q& /*val*/ ) + { + ++item.s.nFindCall; + } + }; + + struct erase_functor + { + template + void operator()( T const& item ) + { + item.s.nEraseCall++; + } + }; + + protected: + template + void test_common( 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& i : arr ) { + EXPECT_FALSE( l.contains( i.nKey )); + EXPECT_FALSE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_FALSE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 0 ); + EXPECT_FALSE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 0 ); + + EXPECT_TRUE( l.insert( i )); + + EXPECT_TRUE( l.contains( i.nKey )); + EXPECT_TRUE( l.contains( i )); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 1 ); + EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 2 ); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 3 ); + + EXPECT_FALSE( l.insert( i ) ); + ASSERT_FALSE( l.empty() ); + } + ASSERT_CONTAINER_SIZE( l, nSize ); + + // check all items + for ( auto const& i : arr ) { + EXPECT_TRUE( l.contains( i.nKey )); + EXPECT_TRUE( l.contains( i )); + EXPECT_TRUE( l.contains( other_item( i.nKey ), other_less())); + EXPECT_TRUE( l.find( i.nKey, []( value_type& item, int ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 4 ); + EXPECT_TRUE( l.find( i, []( value_type& item, value_type const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 5 ); + EXPECT_TRUE( l.find_with( other_item( i.nKey ), other_less(), []( value_type& item, other_item const& ) { ++item.s.nFindCall; } )); + EXPECT_EQ( i.s.nFindCall, 6 ); + } + ASSERT_FALSE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, nSize ); + + // update existing test + for ( auto& i : arr ) { + EXPECT_EQ( i.s.nUpdateExistsCall, 0 ); + std::pair ret = l.update( i, update_functor() ); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + + ret = l.update( i, []( bool bNew, value_type& i, value_type& arg ) { + EXPECT_FALSE( bNew ); + EXPECT_EQ( i.s.nUpdateExistsCall, 1 ); + EXPECT_TRUE( &i == &arg ); + ++i.s.nUpdateExistsCall; + }); + EXPECT_TRUE( ret.first ); + EXPECT_FALSE( ret.second ); + EXPECT_EQ( i.s.nUpdateExistsCall, 2 ); + } + + // clear() test + l.clear(); + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 1 ); + EXPECT_FALSE( l.contains( i ) ); + } + + + for ( auto& i : arr ) { + std::pair ret = l.update( i, update_functor(), false ); + EXPECT_FALSE( ret.first ); + EXPECT_FALSE( ret.second ); + + ret = l.update( i, update_functor(), true ); + EXPECT_TRUE( ret.first ); + EXPECT_TRUE( ret.second ); + EXPECT_EQ( i.s.nUpdateNewCall, 1 ); + } + + EXPECT_FALSE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, nSize ); + + l.clear( mock_disposer2()); + + EXPECT_TRUE( l.empty() ); + EXPECT_CONTAINER_SIZE( l, 0 ); + + // Apply retired pointer to clean links + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 11 ); + EXPECT_FALSE( l.contains( i )); + } + + // Iterators on empty list + { + auto it = l.begin(); + auto itEnd = l.end(); + auto cit = l.cbegin(); + auto citEnd = l.cend(); + + EXPECT_TRUE( it == itEnd ); + EXPECT_TRUE( it == cit ); + EXPECT_TRUE( cit == citEnd ); + + ++it; + ++cit; + + EXPECT_TRUE( it == itEnd ); + EXPECT_TRUE( it == cit ); + EXPECT_TRUE( cit == citEnd ); + } + } + + 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 * 10; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i ) ); + + int key = 0; + for ( auto it = l.begin(); it != l.end(); ++it ) { + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( (*it).nKey, key ); + ++key; + } + + key = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it ) { + EXPECT_EQ( it->nKey, key ); + EXPECT_EQ( (*it).nKey, key ); + ++key; + } + + l.clear(); + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 1 ); + EXPECT_FALSE( l.contains( i ) ); + } + } + + template + void test_unordered_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 * 10; + } + shuffle( arr, arr + nSize ); + + ASSERT_TRUE( l.empty() ); + ASSERT_CONTAINER_SIZE( l, 0 ); + + for ( auto& i : arr ) + EXPECT_TRUE( l.insert( i ) ); + + size_t idx = 0; + for ( auto it = l.begin(); it != l.end(); ++it, ++idx ) { + ASSERT_LT( idx, nSize ); + EXPECT_EQ( it->nKey, arr[idx].nKey ); + EXPECT_EQ( (*it).nKey, arr[idx].nKey ); + } + + idx = 0; + for ( auto it = l.cbegin(); it != l.cend(); ++it, ++idx ) { + ASSERT_LT( idx, nSize ); + EXPECT_EQ( it->nKey, arr[idx].nKey ); + EXPECT_EQ( (*it).nKey, arr[idx].nKey ); + ++key; + } + + l.clear(); + List::gc::force_dispose(); + for ( auto const& i : arr ) { + EXPECT_EQ( i.s.nDisposeCount, 1 ); + EXPECT_FALSE( l.contains( i ) ); + } + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_LIST_TEST_INTRUSIVE_LIST_NOGC_H -- 2.34.1