From: khizmax Date: Sat, 16 Apr 2016 14:02:10 +0000 (+0300) Subject: Migrated EllenBinTreeSet unit test to gtest framework X-Git-Tag: v2.2.0~276 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=d2f8014171d5dabf347705380715c4d9ca3b731d Migrated EllenBinTreeSet unit test to gtest framework --- diff --git a/projects/Win/vc14/gtest-tree.vcxproj b/projects/Win/vc14/gtest-tree.vcxproj index 838c00fd..72712306 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj +++ b/projects/Win/vc14/gtest-tree.vcxproj @@ -28,6 +28,35 @@ + + + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + 4503 + 4503 + 4503 + 4503 + 4503 + 4503 + + + + @@ -58,10 +87,15 @@ + + + + + {2ABD6A2E-BEA7-4c8c-982B-A609F83D2DCB} diff --git a/projects/Win/vc14/gtest-tree.vcxproj.filters b/projects/Win/vc14/gtest-tree.vcxproj.filters index 6cda2263..ebec5344 100644 --- a/projects/Win/vc14/gtest-tree.vcxproj.filters +++ b/projects/Win/vc14/gtest-tree.vcxproj.filters @@ -13,32 +13,62 @@ {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms + + {5e28703f-0f92-4c6c-b3a6-3bd837deb8f6} + + + {9fc83943-2620-4528-a704-d3765f52522b} + - - Source Files + + Source Files\intrusive.EllenBinTree - Source Files - - - Source Files + Source Files\intrusive.EllenBinTree - Source Files + Source Files\intrusive.EllenBinTree - Source Files + Source Files\intrusive.EllenBinTree - Source Files + Source Files\intrusive.EllenBinTree - Source Files + Source Files\intrusive.EllenBinTree + Source Files\intrusive.EllenBinTree + + + Source Files\EllenBinTreeSet + + + Source Files + + Source Files + + Source Files\EllenBinTreeSet + + + Source Files\EllenBinTreeSet + + + Source Files\EllenBinTreeSet + + + Source Files\EllenBinTreeSet + + + Source Files\EllenBinTreeSet + + + Source Files\EllenBinTreeSet + @@ -53,5 +83,20 @@ Header Files + + Header Files + + + Header Files + + + Header Files + + + Header Files + + + Header Files + \ No newline at end of file diff --git a/test/unit/set/test_set.h b/test/unit/set/test_set.h index 1f6e142a..d3a7a908 100644 --- a/test/unit/set/test_set.h +++ b/test/unit/set/test_set.h @@ -46,7 +46,7 @@ namespace cds_test { class container_set : public fixture { public: - static size_t const kSize = 100; + static size_t const kSize = 1000; struct stat { diff --git a/test/unit/tree/CMakeLists.txt b/test/unit/tree/CMakeLists.txt index 5cf4ed0c..2406a48b 100644 --- a/test/unit/tree/CMakeLists.txt +++ b/test/unit/tree/CMakeLists.txt @@ -4,6 +4,14 @@ set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-invalid-offsetof") set(CDSGTEST_TREE_SOURCES ../main.cpp + ellen_bintree_update_desc_pool.cpp + ellenbintree_set_dhp.cpp + ellenbintree_set_hp.cpp + ellen_bintree_set_rcu_gpb.cpp + ellen_bintree_set_rcu_gpi.cpp + ellen_bintree_set_rcu_gpt.cpp + ellen_bintree_set_rcu_shb.cpp + ellen_bintree_set_rcu_sht.cpp intrusive_ellenbintree_hp.cpp intrusive_ellenbintree_dhp.cpp intrusive_ellenbintree_rcu_gpb.cpp diff --git a/test/unit/tree/ellen_bintree_set_rcu_gpb.cpp b/test/unit/tree/ellen_bintree_set_rcu_gpb.cpp new file mode 100644 index 00000000..9314c440 --- /dev/null +++ b/test/unit/tree/ellen_bintree_set_rcu_gpb.cpp @@ -0,0 +1,41 @@ +/* + 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 + +#include "test_ellen_bintree_set_rcu.h" + +namespace { + + typedef cds::urcu::general_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPB, EllenBinTreeSet, rcu_implementation ); diff --git a/test/unit/tree/ellen_bintree_set_rcu_gpi.cpp b/test/unit/tree/ellen_bintree_set_rcu_gpi.cpp new file mode 100644 index 00000000..018ffd00 --- /dev/null +++ b/test/unit/tree/ellen_bintree_set_rcu_gpi.cpp @@ -0,0 +1,41 @@ +/* + 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 + +#include "test_ellen_bintree_set_rcu.h" + +namespace { + + typedef cds::urcu::general_instant<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPI, EllenBinTreeSet, rcu_implementation ); diff --git a/test/unit/tree/ellen_bintree_set_rcu_gpt.cpp b/test/unit/tree/ellen_bintree_set_rcu_gpt.cpp new file mode 100644 index 00000000..80329827 --- /dev/null +++ b/test/unit/tree/ellen_bintree_set_rcu_gpt.cpp @@ -0,0 +1,41 @@ +/* + 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 + +#include "test_ellen_bintree_set_rcu.h" + +namespace { + + typedef cds::urcu::general_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_GPT, EllenBinTreeSet, rcu_implementation ); diff --git a/test/unit/tree/ellen_bintree_set_rcu_shb.cpp b/test/unit/tree/ellen_bintree_set_rcu_shb.cpp new file mode 100644 index 00000000..b2a11b0c --- /dev/null +++ b/test/unit/tree/ellen_bintree_set_rcu_shb.cpp @@ -0,0 +1,45 @@ +/* + 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 + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + +#include "test_ellen_bintree_set_rcu.h" + +namespace { + + typedef cds::urcu::signal_buffered<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHB, EllenBinTreeSet, rcu_implementation ); + +#endif // CDS_URCU_SIGNAL_HANDLING_ENABLED diff --git a/test/unit/tree/ellen_bintree_set_rcu_sht.cpp b/test/unit/tree/ellen_bintree_set_rcu_sht.cpp new file mode 100644 index 00000000..89bab953 --- /dev/null +++ b/test/unit/tree/ellen_bintree_set_rcu_sht.cpp @@ -0,0 +1,45 @@ +/* + 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 + +#ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + +#include "test_ellen_bintree_set_rcu.h" + +namespace { + + typedef cds::urcu::signal_threaded<> rcu_implementation; + +} // namespace + +INSTANTIATE_TYPED_TEST_CASE_P( RCU_SHT, EllenBinTreeSet, rcu_implementation ); + +#endif // CDS_URCU_SIGNAL_HANDLING_ENABLED diff --git a/test/unit/tree/ellen_bintree_update_desc_pool.cpp b/test/unit/tree/ellen_bintree_update_desc_pool.cpp new file mode 100644 index 00000000..6a986fff --- /dev/null +++ b/test/unit/tree/ellen_bintree_update_desc_pool.cpp @@ -0,0 +1,37 @@ +/* + 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 +#include "test_ellen_bintree_update_desc_pool.h" + +namespace cds_test { + pool_type s_Pool; + lazy_pool_type s_LazyPool; +} diff --git a/test/unit/tree/ellenbintree_set_dhp.cpp b/test/unit/tree/ellenbintree_set_dhp.cpp new file mode 100644 index 00000000..1e7dc06a --- /dev/null +++ b/test/unit/tree/ellenbintree_set_dhp.cpp @@ -0,0 +1,180 @@ +/* + 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_tree_set_hp.h" + +#include +#include "test_ellen_bintree_update_desc_pool.h" + +namespace { + namespace cc = cds::container; + typedef cds::gc::DHP gc_type; + + class EllenBinTreeSet_DHP : public cds_test::container_tree_set_hp + { + protected: + typedef cds_test::container_tree_set_hp base_class; + typedef int key_type; + + struct generic_traits: public cc::ellen_bintree::traits + { + typedef base_class::key_extractor key_extractor; + }; + + void SetUp() + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item > set_type; + + cds::gc::dhp::GarbageCollector::Construct( 16, set_type::c_nHazardPtrCount ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct(); + } + }; + + + TEST_F( EllenBinTreeSet_DHP, compare ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::compare< cmp > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, less ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::less< base_class::less > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, cmpmix ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::less< base_class::less > + ,cds::opt::compare< cmp > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, update_desc_pool ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, update_desc_lazy_pool ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::lazy_pool_accessor> update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, item_counting ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, backoff ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_DHP, stat ) + { + struct set_traits: public generic_traits + { + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cc::ellen_bintree::stat<> stat; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + +} // namespace diff --git a/test/unit/tree/ellenbintree_set_hp.cpp b/test/unit/tree/ellenbintree_set_hp.cpp new file mode 100644 index 00000000..1152288b --- /dev/null +++ b/test/unit/tree/ellenbintree_set_hp.cpp @@ -0,0 +1,181 @@ +/* + 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_tree_set_hp.h" + +#include +#include "test_ellen_bintree_update_desc_pool.h" + +namespace { + namespace cc = cds::container; + typedef cds::gc::HP gc_type; + + class EllenBinTreeSet_HP : public cds_test::container_tree_set_hp + { + protected: + typedef cds_test::container_tree_set_hp base_class; + typedef int key_type; + + struct generic_traits: public cc::ellen_bintree::traits + { + typedef base_class::key_extractor key_extractor; + }; + + void SetUp() + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item > set_type; + + // +1 - for guarded_ptr + cds::gc::hp::GarbageCollector::Construct( set_type::c_nHazardPtrCount + 1, 1, 16 ); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + cds::gc::hp::GarbageCollector::Destruct( true ); + } + }; + + + TEST_F( EllenBinTreeSet_HP, compare ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::compare< cmp > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, less ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::less< base_class::less > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, cmpmix ) + { + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, + typename cc::ellen_bintree::make_set_traits< + cc::opt::type_traits< generic_traits > + ,cds::opt::less< base_class::less > + ,cds::opt::compare< cmp > + >::type + > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, update_desc_pool ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, update_desc_lazy_pool ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::lazy_pool_accessor> update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, item_counting ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, backoff ) + { + struct set_traits: public generic_traits + { + typedef cmp compare; + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + + TEST_F( EllenBinTreeSet_HP, stat ) + { + struct set_traits: public generic_traits + { + typedef base_class::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cc::ellen_bintree::stat<> stat; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< gc_type, key_type, int_item, set_traits > set_type; + + set_type s; + test( s ); + } + +} // namespace diff --git a/test/unit/tree/intrusive_ellenbintree_dhp.cpp b/test/unit/tree/intrusive_ellenbintree_dhp.cpp index f5b3b1a2..34f54162 100644 --- a/test/unit/tree/intrusive_ellenbintree_dhp.cpp +++ b/test/unit/tree/intrusive_ellenbintree_dhp.cpp @@ -31,8 +31,7 @@ #include "test_intrusive_tree_hp.h" #include -#include -#include +#include "test_ellen_bintree_update_desc_pool.h" namespace { namespace ci = cds::intrusive; @@ -47,62 +46,7 @@ namespace { typedef base_class::key_type key_type; typedef typename base_class::base_int_item< ci::ellen_bintree::node> base_item_type; - typedef ci::ellen_bintree::internal_node< key_type, base_item_type > internal_base_node; - typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node > update_base_desc; - typedef typename base_class::member_int_item< ci::ellen_bintree::node> member_item_type; - typedef ci::ellen_bintree::internal_node< key_type, member_item_type > internal_member_node; - typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc; - - // update_desc pools - struct pool_traits: public cds::memory::vyukov_queue_pool_traits - { - typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer; - }; - typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type; - typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type; - - static pool_type * s_Pool; - static lazy_pool_type * s_LazyPool; - - struct pool_accessor - { - typedef pool_type::value_type value_type; - - pool_type& operator()() const - { - return *s_Pool; - } - }; - - struct lazy_pool_accessor - { - typedef lazy_pool_type::value_type value_type; - - lazy_pool_type& operator()() const - { - return *s_LazyPool; - } - }; - - static void SetUpTestCase() - { - ASSERT_TRUE( s_Pool == nullptr ); - ASSERT_TRUE( s_LazyPool == nullptr ); - s_Pool = new pool_type; - s_LazyPool = new lazy_pool_type; - } - - static void TearDownTestCase() - { - ASSERT_TRUE( s_Pool != nullptr ); - ASSERT_TRUE( s_LazyPool != nullptr ); - delete s_LazyPool; - delete s_Pool; - - s_LazyPool = nullptr; - s_Pool = nullptr; - } void SetUp() { @@ -129,9 +73,6 @@ namespace { }; }; - /*static*/ IntrusiveEllenBinTree_DHP::pool_type * IntrusiveEllenBinTree_DHP::s_Pool = nullptr; - /*static*/ IntrusiveEllenBinTree_DHP::lazy_pool_type * IntrusiveEllenBinTree_DHP::s_LazyPool = nullptr; - TEST_F( IntrusiveEllenBinTree_DHP, base_cmp ) { typedef ci::EllenBinTree< gc_type, key_type, base_item_type, @@ -217,7 +158,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type; @@ -233,7 +174,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type; @@ -328,7 +269,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type; @@ -344,7 +285,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type; diff --git a/test/unit/tree/intrusive_ellenbintree_hp.cpp b/test/unit/tree/intrusive_ellenbintree_hp.cpp index 384cbc57..8674c618 100644 --- a/test/unit/tree/intrusive_ellenbintree_hp.cpp +++ b/test/unit/tree/intrusive_ellenbintree_hp.cpp @@ -31,8 +31,7 @@ #include "test_intrusive_tree_hp.h" #include -#include -#include +#include "test_ellen_bintree_update_desc_pool.h" namespace { namespace ci = cds::intrusive; @@ -47,66 +46,11 @@ namespace { typedef base_class::key_type key_type; typedef typename base_class::base_int_item< ci::ellen_bintree::node> base_item_type; - typedef ci::ellen_bintree::internal_node< key_type, base_item_type > internal_base_node; - typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node > update_base_desc; - typedef typename base_class::member_int_item< ci::ellen_bintree::node> member_item_type; - typedef ci::ellen_bintree::internal_node< key_type, member_item_type > internal_member_node; - typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc; - - // update_desc pools - struct pool_traits: public cds::memory::vyukov_queue_pool_traits - { - typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer; - }; - typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type; - typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type; - - static pool_type * s_Pool; - static lazy_pool_type * s_LazyPool; - - struct pool_accessor - { - typedef pool_type::value_type value_type; - - pool_type& operator()() const - { - return *s_Pool; - } - }; - - struct lazy_pool_accessor - { - typedef lazy_pool_type::value_type value_type; - - lazy_pool_type& operator()() const - { - return *s_LazyPool; - } - }; - - static void SetUpTestCase() - { - ASSERT_TRUE( s_Pool == nullptr ); - ASSERT_TRUE( s_LazyPool == nullptr ); - s_Pool = new pool_type; - s_LazyPool = new lazy_pool_type; - } - - static void TearDownTestCase() - { - ASSERT_TRUE( s_Pool != nullptr ); - ASSERT_TRUE( s_LazyPool != nullptr ); - delete s_LazyPool; - delete s_Pool; - - s_LazyPool = nullptr; - s_Pool = nullptr; - } void SetUp() { - struct list_traits : public ci::ellen_bintree::traits + struct tree_traits : public ci::ellen_bintree::traits { typedef ci::ellen_bintree::base_hook< ci::opt::gc> hook; }; @@ -130,9 +74,6 @@ namespace { }; }; - /*static*/ IntrusiveEllenBinTree_HP::pool_type * IntrusiveEllenBinTree_HP::s_Pool = nullptr; - /*static*/ IntrusiveEllenBinTree_HP::lazy_pool_type * IntrusiveEllenBinTree_HP::s_LazyPool = nullptr; - TEST_F( IntrusiveEllenBinTree_HP, base_cmp ) { @@ -219,7 +160,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::pool_accessor> update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type; @@ -235,7 +176,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, base_item_type, tree_traits > tree_type; @@ -330,7 +271,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type; @@ -346,7 +287,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< gc_type >> hook; typedef base_class::less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::memory::pool_allocator update_desc_allocator; }; typedef ci::EllenBinTree< gc_type, key_type, member_item_type, tree_traits > tree_type; diff --git a/test/unit/tree/test_ellen_bintree_set_rcu.h b/test/unit/tree/test_ellen_bintree_set_rcu.h new file mode 100644 index 00000000..83f68f20 --- /dev/null +++ b/test/unit/tree/test_ellen_bintree_set_rcu.h @@ -0,0 +1,239 @@ +/* + 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_TREE_TEST_ELLEN_BINTREE_SET_RCU_H +#define CDSUNIT_TREE_TEST_ELLEN_BINTREE_SET_RCU_H + +#include "test_tree_set_rcu.h" +#include +#include "test_ellen_bintree_update_desc_pool.h" + + +namespace { + namespace cc = cds::container; + + template + class EllenBinTreeSet: public cds_test::container_tree_set_rcu + { + typedef cds_test::container_tree_set_rcu base_class; + public: + typedef cds::urcu::gc rcu_type; + + protected: + void SetUp() + { + RCU::Construct(); + cds::threading::Manager::attachThread(); + } + + void TearDown() + { + cds::threading::Manager::detachThread(); + RCU::Destruct(); + } + }; + + TYPED_TEST_CASE_P( EllenBinTreeSet ); + + TYPED_TEST_P( EllenBinTreeSet, compare ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + typedef typename TestFixture::key_extractor key_extractor; + + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, + typename cc::ellen_bintree::make_set_traits< + cds::opt::compare< typename TestFixture::cmp > + ,cc::ellen_bintree::key_extractor< key_extractor > + >::type + > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, less ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + typedef typename TestFixture::key_extractor key_extractor; + + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, + typename cc::ellen_bintree::make_set_traits< + cds::opt::less< typename TestFixture::less > + ,cc::ellen_bintree::key_extractor< key_extractor > + >::type + > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, cmpmix ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + typedef typename TestFixture::key_extractor key_extractor; + + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, + typename cc::ellen_bintree::make_set_traits< + cds::opt::less< typename TestFixture::less > + ,cds::opt::compare< typename TestFixture::cmp > + ,cc::ellen_bintree::key_extractor< key_extractor > + >::type + > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, update_desc_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::key_extractor key_extractor; + typedef typename TestFixture::cmp compare; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, update_desc_lazy_pool ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::key_extractor key_extractor; + typedef typename TestFixture::less less; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, item_counting ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::key_extractor key_extractor; + typedef typename TestFixture::cmp compare; + typedef typename TestFixture::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, backoff ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::key_extractor key_extractor; + typedef typename TestFixture::cmp compare; + typedef typename TestFixture::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, stat ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cc::ellen_bintree::stat<> stat; + typedef typename TestFixture::key_extractor key_extractor; + typedef cds::memory::pool_allocator update_desc_allocator; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + TYPED_TEST_P( EllenBinTreeSet, seq_cst ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item int_item; + + struct set_traits: public cc::ellen_bintree::traits + { + typedef typename TestFixture::less less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::backoff::yield back_off; + typedef cc::ellen_bintree::stat<> stat; + typedef typename TestFixture::key_extractor key_extractor; + typedef cds::memory::pool_allocator update_desc_allocator; + typedef cds::opt::v::sequential_consistent memory_model; + }; + typedef cc::EllenBinTreeSet< rcu_type, int, int_item, set_traits > set_type; + + set_type s; + this->test( s ); + } + + + // GCC 5: All this->test names should be written on single line, otherwise a runtime error will be encountered like as + // "No this->test named can be found in this this->test case" + REGISTER_TYPED_TEST_CASE_P( EllenBinTreeSet, + compare, less, cmpmix, update_desc_pool, update_desc_lazy_pool, item_counting, backoff, stat, seq_cst + ); +} // namespace + +#endif // CDSUNIT_TREE_TEST_ELLEN_BINTREE_SET_RCU_H + \ No newline at end of file diff --git a/test/unit/tree/test_ellen_bintree_update_desc_pool.h b/test/unit/tree/test_ellen_bintree_update_desc_pool.h new file mode 100644 index 00000000..89edde7b --- /dev/null +++ b/test/unit/tree/test_ellen_bintree_update_desc_pool.h @@ -0,0 +1,74 @@ +/* + 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_TREE_TEST_ELLEN_BINTREE_UPDATE_DESC_POOL_H +#define CDSUNIT_TREE_TEST_ELLEN_BINTREE_UPDATE_DESC_POOL_H + +#include +#include + +namespace cds_test { + + typedef cds::intrusive::ellen_bintree::update_desc< void, void > update_desc; + + // update_desc pools + struct pool_traits: public cds::memory::vyukov_queue_pool_traits + { + typedef cds::opt::v::static_buffer< update_desc, 256 > buffer; + }; + typedef cds::memory::vyukov_queue_pool< update_desc, pool_traits > pool_type; + typedef cds::memory::lazy_vyukov_queue_pool< update_desc, pool_traits > lazy_pool_type; + + extern pool_type s_Pool; + extern lazy_pool_type s_LazyPool; + + struct pool_accessor + { + typedef pool_type::value_type value_type; + + pool_type& operator()() const + { + return s_Pool; + } + }; + + struct lazy_pool_accessor + { + typedef lazy_pool_type::value_type value_type; + + lazy_pool_type& operator()() const + { + return s_LazyPool; + } + }; + +} // namespace cds_test + +#endif // #ifndef CDSUNIT_TREE_TEST_ELLEN_BINTREE_UPDATE_DESC_POOL_H diff --git a/test/unit/tree/test_intrusive_ellen_bintree_rcu.h b/test/unit/tree/test_intrusive_ellen_bintree_rcu.h index d9038e40..1ccffc78 100644 --- a/test/unit/tree/test_intrusive_ellen_bintree_rcu.h +++ b/test/unit/tree/test_intrusive_ellen_bintree_rcu.h @@ -34,9 +34,7 @@ #include "test_intrusive_tree_rcu.h" #include -#include -#include - +#include "test_ellen_bintree_update_desc_pool.h" // forward declaration namespace cds { namespace intrusive {}} @@ -56,62 +54,7 @@ namespace { typedef base_class::key_type key_type; typedef typename base_class::base_int_item< ci::ellen_bintree::node> base_item_type; - typedef ci::ellen_bintree::internal_node< key_type, base_item_type > internal_base_node; - typedef ci::ellen_bintree::update_desc< base_item_type, internal_base_node > update_base_desc; - typedef typename base_class::member_int_item< ci::ellen_bintree::node> member_item_type; - typedef ci::ellen_bintree::internal_node< key_type, member_item_type > internal_member_node; - typedef ci::ellen_bintree::update_desc< member_item_type, internal_member_node > update_member_desc; - - // update_desc pools - struct pool_traits: public cds::memory::vyukov_queue_pool_traits - { - typedef cds::opt::v::static_buffer< update_base_desc, 256 > buffer; - }; - typedef cds::memory::vyukov_queue_pool< update_base_desc, pool_traits > pool_type; - typedef cds::memory::lazy_vyukov_queue_pool< update_base_desc, pool_traits > lazy_pool_type; - - static pool_type * s_Pool; - static lazy_pool_type * s_LazyPool; - - struct pool_accessor - { - typedef typename pool_type::value_type value_type; - - pool_type& operator()() const - { - return *s_Pool; - } - }; - - struct lazy_pool_accessor - { - typedef typename lazy_pool_type::value_type value_type; - - lazy_pool_type& operator()() const - { - return *s_LazyPool; - } - }; - - static void SetUpTestCase() - { - ASSERT_TRUE( s_Pool == nullptr ); - ASSERT_TRUE( s_LazyPool == nullptr ); - s_Pool = new pool_type; - s_LazyPool = new lazy_pool_type; - } - - static void TearDownTestCase() - { - ASSERT_TRUE( s_Pool != nullptr ); - ASSERT_TRUE( s_LazyPool != nullptr ); - delete s_LazyPool; - delete s_Pool; - - s_LazyPool = nullptr; - s_Pool = nullptr; - } struct generic_traits: public ci::ellen_bintree::traits { @@ -133,9 +76,6 @@ namespace { } }; - /*static*/ template typename IntrusiveEllenBinTree::pool_type * IntrusiveEllenBinTree::s_Pool = nullptr; - /*static*/ template typename IntrusiveEllenBinTree::lazy_pool_type * IntrusiveEllenBinTree::s_LazyPool = nullptr; - TYPED_TEST_CASE_P( IntrusiveEllenBinTree ); @@ -254,7 +194,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; typedef typename TestFixture::template less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::pool_accessor> update_desc_allocator; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::pool_accessor> update_desc_allocator; }; typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; @@ -275,7 +215,7 @@ namespace { typedef ci::ellen_bintree::base_hook< ci::opt::gc< rcu_type >> hook; typedef typename TestFixture::template less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator< typename TestFixture::update_base_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::lazy_pool_accessor> update_desc_allocator; }; typedef ci::EllenBinTree< rcu_type, key_type, base_item_type, tree_traits > tree_type; @@ -400,7 +340,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; typedef typename TestFixture::template less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::pool_accessor> update_desc_allocator; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::pool_accessor> update_desc_allocator; }; typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; @@ -421,7 +361,7 @@ namespace { typedef ci::ellen_bintree::member_hook< offsetof( member_item_type, hMember ), ci::opt::gc< rcu_type >> hook; typedef typename TestFixture::template less less; typedef cds::atomicity::item_counter item_counter; - typedef cds::memory::pool_allocator< typename TestFixture::update_member_desc, typename TestFixture::lazy_pool_accessor> update_desc_allocator; + typedef cds::memory::pool_allocator< cds_test::update_desc, cds_test::lazy_pool_accessor> update_desc_allocator; }; typedef ci::EllenBinTree< rcu_type, key_type, member_item_type, tree_traits > tree_type; diff --git a/test/unit/tree/test_tree_set.h b/test/unit/tree/test_tree_set.h new file mode 100644 index 00000000..bc92bd6e --- /dev/null +++ b/test/unit/tree/test_tree_set.h @@ -0,0 +1,517 @@ +/* + 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_SET_TEST_TREE_SET_H +#define CDSUNIT_SET_TEST_TREE_SET_H + +#include +#include + +// forward declaration +namespace cds { namespace container {}} + +namespace cds_test { + + class container_tree_set : public fixture + { + public: + static size_t const kSize = 1000; + + struct stat + { + unsigned int nFindCount; + unsigned int nUpdateNewCount; + unsigned int nUpdateCount; + mutable unsigned int nEraseCount; + + stat() + { + clear_stat(); + } + + void clear_stat() + { + memset( this, 0, sizeof( *this ) ); + } + }; + + struct other_item { + int nKey; + + explicit other_item( int k ) + : nKey( k ) + {} + + int key() const + { + return nKey; + } + }; + + struct int_item: public stat + { + int nKey; + int nVal; + std::string strVal; + + int_item() + : nKey( 0 ) + , nVal( 0 ) + {} + + explicit int_item( int k ) + : nKey( k ) + , nVal( k * 2 ) + {} + + template + explicit int_item( Q const& src ) + : nKey( src.key() ) + , nVal( 0 ) + {} + + int_item( int_item const& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( src.strVal ) + {} + + int_item( int_item&& src ) + : nKey( src.nKey ) + , nVal( src.nVal ) + , strVal( std::move( src.strVal ) ) + {} + + int_item( int k, std::string&& s ) + : nKey( k ) + , nVal( k * 2 ) + , strVal( std::move( s ) ) + {} + + explicit int_item( other_item const& s ) + : nKey( s.key() ) + , nVal( s.key() * 2 ) + {} + + int key() const + { + return nKey; + } + }; + + struct key_extractor + { + template + void operator()( int& key, T const& val ) const + { + key = val.key(); + } + }; + + struct simple_item_counter { + size_t m_nCount; + + simple_item_counter() + : m_nCount( 0 ) + {} + + size_t operator ++() + { + return ++m_nCount; + } + + size_t operator --() + { + return --m_nCount; + } + + void reset() + { + m_nCount = 0; + } + + operator size_t() const + { + return m_nCount; + } + + }; + + struct less + { + bool operator ()( int_item const& v1, int_item const& v2 ) const + { + return v1.key() < v2.key(); + } + + bool operator()( int lhs, int rhs ) const + { + return lhs < rhs; + } + + template + bool operator ()( int_item const& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()( const Q& v1, int_item const& v2 ) const + { + return v1 < v2.key(); + } + }; + + struct cmp { + int operator ()( int_item const& v1, int_item const& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + + int operator()( int lhs, int rhs ) const + { + return lhs - rhs; + } + + template + int operator ()( T const& v1, int v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + int operator ()( int v1, T const& v2 ) const + { + if ( v1 < v2.key() ) + return -1; + return v1 > v2.key() ? 1 : 0; + } + }; + + struct other_less { + template + bool operator()( Q const& lhs, T const& rhs ) const + { + return lhs.key() < rhs.key(); + } + + bool operator()( int lhs, other_item const& rhs ) const + { + return lhs < rhs.key(); + } + + bool operator()( other_item const& lhs, int rhs ) const + { + return lhs.key() < rhs; + } + }; + + protected: + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + size_t const nSetSize = kSize; + + typedef typename Set::value_type value_type; + + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + // insert/find + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_FALSE( s.contains( i.nKey ) ); + ASSERT_FALSE( s.contains( i ) ); + ASSERT_FALSE( s.contains( other_item( i.key() ), other_less())); + ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} )); + + std::pair updResult; + + std::string str; + updResult = s.update( i.key(), []( bool bNew, value_type&, int ) + { + ASSERT_TRUE( false ); + }, false ); + EXPECT_FALSE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + switch ( idx % 8 ) { + case 0: + ASSERT_TRUE( s.insert( i )); + ASSERT_FALSE( s.insert( i )); + updResult = s.update( i, []( bool bNew, value_type& val, value_type const& arg) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( val.key(), arg.key() ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 1: + ASSERT_TRUE( s.insert( i.key() )); + ASSERT_FALSE( s.insert( i.key() )); + updResult = s.update( i.key(), []( bool bNew, value_type& val, int arg) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( val.key(), arg ); + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + break; + case 2: + ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 3: + ASSERT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } )); + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nFindCount, 1 ); + })); + break; + case 4: + updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg ) + { + EXPECT_TRUE( bNew ); + EXPECT_EQ( v.key(), arg.key() ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i, []( bool bNew, value_type& v, value_type const& arg ) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( v.key(), arg.key() ); + ++v.nUpdateNewCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + ASSERT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) + { + EXPECT_EQ( v.key(), key ); + EXPECT_EQ( v.nUpdateNewCount, 2 ); + })); + break; + case 5: + updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg ) + { + EXPECT_TRUE( bNew ); + EXPECT_EQ( v.key(), arg ); + ++v.nUpdateNewCount; + }); + EXPECT_TRUE( updResult.first ); + EXPECT_TRUE( updResult.second ); + + updResult = s.update( i.key(), []( bool bNew, value_type& v, int arg ) + { + EXPECT_FALSE( bNew ); + EXPECT_EQ( v.key(), arg ); + ++v.nUpdateNewCount; + }, false ); + EXPECT_TRUE( updResult.first ); + EXPECT_FALSE( updResult.second ); + + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nUpdateNewCount, 2 ); + })); + break; + case 6: + ASSERT_TRUE( s.emplace( i.key())); + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + })); + break; + case 7: + str = "Hello!"; + ASSERT_TRUE( s.emplace( i.key(), std::move( str ))); + EXPECT_TRUE( str.empty()); + ASSERT_TRUE( s.find( i, []( value_type const& v, value_type const& arg ) + { + EXPECT_EQ( v.key(), arg.key() ); + EXPECT_EQ( v.nVal, arg.nVal ); + EXPECT_EQ( v.strVal, std::string( "Hello!" )); + } ) ); + break; + default: + // forgot anything?.. + ASSERT_TRUE( false ); + } + + ASSERT_TRUE( s.contains( i.nKey ) ); + ASSERT_TRUE( s.contains( i ) ); + ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) ); + ASSERT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) ); + ASSERT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) ); + ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) ); + } + + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + // erase + shuffle( indices.begin(), indices.end() ); + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_TRUE( s.contains( i.nKey ) ); + ASSERT_TRUE( s.contains( i ) ); + ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) ); + ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) + { + v.nFindCount = 1; + })); + ASSERT_TRUE( s.find( i, []( value_type& v, value_type const& ) + { + EXPECT_EQ( ++v.nFindCount, 2 ); + })); + ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) + { + EXPECT_EQ( ++v.nFindCount, 3 ); + })); + + int nKey = i.key() - 1; + switch ( idx % 6 ) { + case 0: + ASSERT_TRUE( s.erase( i.key())); + ASSERT_FALSE( s.erase( i.key())); + break; + case 1: + ASSERT_TRUE( s.erase( i )); + ASSERT_FALSE( s.erase( i )); + break; + case 2: + ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less())); + ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) ); + break; + case 3: + ASSERT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 4: + ASSERT_TRUE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase( i, [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + case 5: + ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey ); + + nKey = i.key() - 1; + ASSERT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v ) + { + nKey = v.key(); + } )); + EXPECT_EQ( i.key(), nKey + 1 ); + break; + } + + ASSERT_FALSE( s.contains( i.nKey ) ); + ASSERT_FALSE( s.contains( i ) ); + ASSERT_FALSE( s.contains( other_item( i.key() ), other_less())); + ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} )); + ASSERT_FALSE( s.find( i, []( value_type&, value_type const& ) {} )); + ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} )); + } + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + + // clear + for ( auto& i : data ) { + ASSERT_TRUE( s.insert( i ) ); + } + + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + s.clear(); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + } + }; + +} // namespace cds_test + +#endif // CDSUNIT_SET_TEST_TREE_SET_H diff --git a/test/unit/tree/test_tree_set_hp.h b/test/unit/tree/test_tree_set_hp.h new file mode 100644 index 00000000..b0bed2f5 --- /dev/null +++ b/test/unit/tree/test_tree_set_hp.h @@ -0,0 +1,188 @@ +/* + 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_SET_TEST_TREE_SET_HP_H +#define CDSUNIT_SET_TEST_TREE_SET_HP_H + +#include "test_tree_set.h" + +namespace cds_test { + + class container_tree_set_hp: public container_tree_set + { + typedef container_tree_set base_class; + + protected: + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + base_class::test( s ); + + typedef typename Set::value_type value_type; + + size_t const nSetSize = kSize; + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] ) ); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + typedef typename Set::guarded_ptr guarded_ptr; + guarded_ptr gp; + + // get() + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_TRUE( !gp ); + switch ( idx % 3 ) { + case 0: + gp = s.get( i.key() ); + ASSERT_FALSE( !gp ); + break; + case 1: + gp = s.get( i ); + ASSERT_FALSE( !gp ); + break; + case 2: + gp = s.get_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !gp ); + } + EXPECT_EQ( gp->key(), i.key() ); + gp->nFindCount = gp->key() * 3; + + gp.release(); + } + + // extract() + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_TRUE( !gp ); + switch ( idx % 3 ) { + case 0: + gp = s.extract( i.key() ); + ASSERT_FALSE( !gp ); + break; + case 1: + gp = s.extract( i ); + ASSERT_FALSE( !gp ); + break; + case 2: + gp = s.extract_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !gp ); + break; + } + EXPECT_EQ( gp->key(), i.key() ); + EXPECT_EQ( gp->nFindCount, i.key() * 3 ); + + switch ( idx % 3 ) { + case 0: + gp = s.extract( i.key() ); + break; + case 1: + gp = s.extract( i ); + break; + case 2: + gp = s.extract_with( other_item( i.key() ), other_less() ); + break; + } + ASSERT_TRUE( !gp ); + } + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] ) ); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + // extract_min + size_t nCount = 0; + int nKey = -1; + while ( !s.empty() ) { + gp = s.extract_min(); + ASSERT_FALSE( !gp ); + EXPECT_EQ( nKey + 1, gp->key() ); + ++nCount; + nKey = gp->key(); + } + gp.release(); + EXPECT_EQ( nCount, nSetSize ); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + // extract_max + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] )); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + nCount = 0; + nKey = nSetSize; + while ( !s.empty() ) { + gp = s.extract_max(); + ASSERT_FALSE( !gp ); + EXPECT_EQ( nKey - 1, gp->key() ); + ++nCount; + nKey = gp->key(); + } + gp.release(); + EXPECT_EQ( nCount, nSetSize ); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + } + + }; +} // namespace cds_test + +#endif // CDSUNIT_SET_TEST_TREE_SET_HP_H diff --git a/test/unit/tree/test_tree_set_rcu.h b/test/unit/tree/test_tree_set_rcu.h new file mode 100644 index 00000000..e6f9ddaf --- /dev/null +++ b/test/unit/tree/test_tree_set_rcu.h @@ -0,0 +1,233 @@ +/* + 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_TREE_TEST_TREE_SET_RCU_H +#define CDSUNIT_TREE_TEST_TREE_SET_RCU_H + +#include "test_tree_set.h" + +namespace cds_test { + + class container_tree_set_rcu: public container_tree_set + { + typedef container_tree_set base_class; + + protected: + template + void test( Set& s ) + { + // Precondition: set is empty + // Postcondition: set is empty + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + base_class::test( s ); + + typedef typename Set::value_type value_type; + + size_t const nSetSize = kSize; + std::vector< value_type > data; + std::vector< size_t> indices; + data.reserve( kSize ); + indices.reserve( kSize ); + for ( size_t key = 0; key < kSize; ++key ) { + data.push_back( value_type( static_cast(key) ) ); + indices.push_back( key ); + } + shuffle( indices.begin(), indices.end() ); + + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] )); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + typedef typename Set::exempt_ptr exempt_ptr; + typedef value_type * raw_ptr; + typedef typename Set::rcu_lock rcu_lock; + + // get() + for ( auto idx : indices ) { + auto& i = data[idx]; + + { + rcu_lock l; + raw_ptr rp{}; + ASSERT_TRUE( !rp ); + switch ( idx % 3 ) { + case 0: + rp = s.get( i.key() ); + ASSERT_FALSE( !rp ); + break; + case 1: + rp = s.get( i ); + ASSERT_FALSE( !rp ); + break; + case 2: + rp = s.get_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !rp ); + } + EXPECT_EQ( rp->key(), i.key() ); + rp->nFindCount = rp->key() * 3; + } + } + + // extract() + exempt_ptr xp; + for ( auto idx : indices ) { + auto& i = data[idx]; + + ASSERT_TRUE( !xp ); + if ( Set::c_bExtractLockExternal ) { + { + rcu_lock l; + + switch ( idx % 3 ) { + case 0: + xp = s.extract( i.key() ); + ASSERT_FALSE( !xp ); + break; + case 1: + xp = s.extract( i ); + ASSERT_FALSE( !xp ); + break; + case 2: + xp = s.extract_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !xp ); + break; + } + EXPECT_EQ( xp->key(), i.key() ); + EXPECT_EQ( xp->nFindCount, i.key() * 3 ); + } + xp.release(); + + { + rcu_lock l; + + switch ( idx % 3 ) { + case 0: + xp = s.extract( i.key() ); + break; + case 1: + xp = s.extract( i ); + break; + case 2: + xp = s.extract_with( other_item( i.key() ), other_less() ); + break; + } + ASSERT_TRUE( !xp ); + } + } + else { + switch ( idx % 3 ) { + case 0: + xp = s.extract( i.key() ); + ASSERT_FALSE( !xp ); + break; + case 1: + xp = s.extract( i ); + ASSERT_FALSE( !xp ); + break; + case 2: + xp = s.extract_with( other_item( i.key() ), other_less() ); + ASSERT_FALSE( !xp ); + break; + } + EXPECT_EQ( xp->key(), i.key() ); + EXPECT_EQ( xp->nFindCount, i.key() * 3 ); + + switch ( idx % 3 ) { + case 0: + xp = s.extract( i.key() ); + break; + case 1: + xp = s.extract( i ); + break; + case 2: + xp = s.extract_with( other_item( i.key() ), other_less() ); + break; + } + ASSERT_TRUE( !xp ); + } + } + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] ) ); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + // extract_min + size_t nCount = 0; + int nKey = -1; + while ( !s.empty() ) { + xp = s.extract_min(); + ASSERT_FALSE( !xp ); + EXPECT_EQ( nKey + 1, xp->key() ); + ++nCount; + nKey = xp->key(); + } + xp.release(); + EXPECT_EQ( nCount, nSetSize ); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + + // extract_max + for ( auto i : indices ) { + ASSERT_TRUE( s.insert( data[i] ) ); + } + ASSERT_FALSE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, nSetSize ); + + nCount = 0; + nKey = nSetSize; + while ( !s.empty() ) { + xp = s.extract_max(); + ASSERT_FALSE( !xp ); + EXPECT_EQ( nKey - 1, xp->key() ); + ++nCount; + nKey = xp->key(); + } + xp.release(); + EXPECT_EQ( nCount, nSetSize ); + + ASSERT_TRUE( s.empty() ); + ASSERT_CONTAINER_SIZE( s, 0 ); + } + + }; +} // namespace cds_test + +#endif // CDSUNIT_TREE_TEST_TREE_SET_RCU_H