From 2bbe5d3732aac48f0c5bd9eb0efa6fb2fbb76665 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 20 Aug 2015 23:49:58 +0300 Subject: [PATCH] Added container::MultiLevelHashSet unit tests Fixed container::MultiLevelHashSet bugs --- .../details/multilevel_hashset_base.h | 4 +- cds/container/impl/multilevel_hashmap.h | 9 +- cds/container/impl/multilevel_hashset.h | 27 +- cds/intrusive/impl/multilevel_hashset.h | 20 +- projects/Win/vc12/hdr-test-set.vcxproj | 3 + .../Win/vc12/hdr-test-set.vcxproj.filters | 12 + projects/source.test-hdr.mk | 1 + tests/test-hdr/CMakeLists.txt | 1 + .../set/hdr_intrusive_multilevel_hashset.h | 22 +- tests/test-hdr/set/hdr_multilevel_hashset.h | 439 ++++++++++++++++++ .../set/hdr_multilevel_hashset_dhp.cpp | 207 +++++++++ .../set/hdr_multilevel_hashset_hp.cpp | 209 +++++++++ 12 files changed, 933 insertions(+), 21 deletions(-) create mode 100644 tests/test-hdr/set/hdr_multilevel_hashset.h create mode 100644 tests/test-hdr/set/hdr_multilevel_hashset_dhp.cpp create mode 100644 tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp diff --git a/cds/container/details/multilevel_hashset_base.h b/cds/container/details/multilevel_hashset_base.h index 2ecc8ac1..c3b8911b 100644 --- a/cds/container/details/multilevel_hashset_base.h +++ b/cds/container/details/multilevel_hashset_base.h @@ -17,7 +17,7 @@ namespace cds { namespace container { @copydetails cds::intrusive::multilevel_hashset::traits::hash_accessor */ template - using hash_accessor = cds::intrusive::hash_accessor< Accessor >; + using hash_accessor = cds::intrusive::multilevel_hashset::hash_accessor< Accessor >; /// \p MultiLevelHashSet internal statistics, see cds::intrusive::multilevel_hashset::stat template @@ -130,7 +130,7 @@ namespace cds { namespace container { //@cond // Forward declaration - template < class GC, typename T, class Traits = multilevel_hashset::traits > + template < class GC, typename T, class Traits = cds::container::multilevel_hashset::traits > class MultiLevelHashSet; //@endcond diff --git a/cds/container/impl/multilevel_hashmap.h b/cds/container/impl/multilevel_hashmap.h index 7875dea5..2ba9e363 100644 --- a/cds/container/impl/multilevel_hashmap.h +++ b/cds/container/impl/multilevel_hashmap.h @@ -137,6 +137,7 @@ namespace cds { namespace container { { friend class MultiLevelHashMap; typedef Iterator base_class; + public: typedef typename std::conditional< base_class::c_bConstantIterator, value_type const*, value_type*>::type value_ptr; ///< Value pointer typedef typename std::conditional< base_class::c_bConstantIterator, value_type const&, value_type&>::type value_ref; ///< Value reference @@ -436,8 +437,14 @@ namespace cds { namespace container { */ bool erase_at( iterator const& iter ) { - return base_class::erase_at( iter ); + return base_class::erase_at( static_cast( iter )); } + //@cond + bool erase_at( reverse_iterator const& iter ) + { + return base_class::erase_at( static_cast( iter )); + } + //@endcond /// Extracts the item from the map with specified \p key /** diff --git a/cds/container/impl/multilevel_hashset.h b/cds/container/impl/multilevel_hashset.h index e33a0e05..fcc0452c 100644 --- a/cds/container/impl/multilevel_hashset.h +++ b/cds/container/impl/multilevel_hashset.h @@ -155,7 +155,7 @@ namespace cds { namespace container { /** The function creates an element with copy of \p val value and then inserts it into the set. - The type \p Q should contain as minimum the complete key for the element. + The type \p Q should contain as minimum the complete hash for the element. The object of \ref value_type should be constructible from a value of type \p Q. In trivial case, \p Q is equal to \ref value_type. @@ -200,22 +200,23 @@ namespace cds { namespace container { /// Updates the element /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing with lock-free manner. If the \p val key not found in the set, then the new item created from \p val - will be inserted into the set iff \p bInsert is \p true. - Otherwise, if \p val is found, the functor \p func will be called with the item found. + will be inserted into the set iff \p bInsert is \p true. + Otherwise, if \p val is found, it is replaced with new item created from \p val. + In both cases \p func functor is called. The functor \p Func signature: \code struct my_functor { - void operator()( bool bNew, value_type& item, const Q& val ); + void operator()( value_type& cur, value_type * prev ); }; \endcode where: - - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the set - - \p val - argument \p key passed into the \p %update() function + - \p cur - current element + - \p prev - pointer to previous element with such hash. \p prev is \p nullptr + if \p cur was just inserted. The functor may change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. @@ -231,8 +232,8 @@ namespace cds { namespace container { std::pair update( const Q& val, Func func, bool bInsert = true ) { scoped_node_ptr sp( cxx_node_allocator().New( val )); - std::pair bRes = base_class::update( *sp, func, bInsert ); - if ( bRes.first && bRes.second ) + std::pair bRes = base_class::do_update( *sp, func, bInsert ); + if ( bRes.first ) sp.release(); return bRes; } @@ -293,6 +294,12 @@ namespace cds { namespace container { { return base_class::erase_at( iter ); } + //@cond + bool erase_at( reverse_iterator const& iter ) + { + return base_class::erase_at( iter ); + } + //@endcond /// Extracts the item with specified \p hash /** diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h index 46937daf..86ce7439 100644 --- a/cds/intrusive/impl/multilevel_hashset.h +++ b/cds/intrusive/impl/multilevel_hashset.h @@ -129,7 +129,7 @@ namespace cds { namespace intrusive { typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer /// Count of hazard pointers required - static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1; + static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2; /// Node marked poiter typedef cds::details::marked_ptr< value_type, 3 > node_ptr; @@ -625,7 +625,7 @@ namespace cds { namespace intrusive { */ std::pair update( value_type& val, bool bInsert = true ) { - return do_update(val, [](bool, value_type&) {}, bInsert ); + return do_update(val, [](value_type&, value_type *) {}, bInsert ); } /// Unlinks the item \p val from the set @@ -716,6 +716,12 @@ namespace cds { namespace intrusive { return false; } } + //@cond + bool erase_at( reverse_iterator const& iter ) + { + return erase_at(static_cast( iter )); + } + //@endcond /// Extracts the item with specified \p hash /** @@ -1264,7 +1270,7 @@ namespace cds { namespace intrusive { hash_type const& hash = hash_accessor()( val ); hash_splitter splitter( hash ); hash_comparator cmp; - typename gc::Guard guard; + typename gc::GuardArray<2> guards; back_off bkoff; array_node * pArr = m_Head; @@ -1272,6 +1278,8 @@ namespace cds { namespace intrusive { assert( nSlot < m_Metrics.head_node_size ); size_t nOffset = m_Metrics.head_node_size_log; + guards.assign( 1, &val ); + while ( true ) { node_ptr slot = pArr->nodes[nSlot].load( memory_model::memory_order_acquire ); if ( slot.bits() == flag_array_node ) { @@ -1292,7 +1300,7 @@ namespace cds { namespace intrusive { assert(slot.bits() == 0 ); // protect data node by hazard pointer - if ( guard.protect( pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { + if ( guards.protect( 0, pArr->nodes[nSlot], [](node_ptr p) -> value_type * { return p.ptr(); }) != slot ) { // slot value has been changed - retry m_Stat.onSlotChanged(); } @@ -1307,7 +1315,7 @@ namespace cds { namespace intrusive { if ( pArr->nodes[nSlot].compare_exchange_strong( slot, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { // slot can be disposed - f( false, val ); + f( val, slot.ptr() ); gc::template retire( slot.ptr() ); m_Stat.onUpdateExisting(); return std::make_pair( true, false ); @@ -1327,7 +1335,7 @@ namespace cds { namespace intrusive { if ( pArr->nodes[nSlot].compare_exchange_strong( pNull, node_ptr( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { // the new data node has been inserted - f( true, val ); + f( val, nullptr ); ++m_ItemCounter; m_Stat.onUpdateNew(); return std::make_pair( true, true ); diff --git a/projects/Win/vc12/hdr-test-set.vcxproj b/projects/Win/vc12/hdr-test-set.vcxproj index 9615e062..f45220ee 100644 --- a/projects/Win/vc12/hdr-test-set.vcxproj +++ b/projects/Win/vc12/hdr-test-set.vcxproj @@ -545,6 +545,7 @@ + @@ -616,6 +617,8 @@ + + diff --git a/projects/Win/vc12/hdr-test-set.vcxproj.filters b/projects/Win/vc12/hdr-test-set.vcxproj.filters index feb558e8..7e76f8fe 100644 --- a/projects/Win/vc12/hdr-test-set.vcxproj.filters +++ b/projects/Win/vc12/hdr-test-set.vcxproj.filters @@ -22,6 +22,9 @@ intrusive\multilevel_hashset + + container\multilevel_hashset + @@ -51,6 +54,9 @@ {a878aed0-83c9-4ca7-95bb-74f10aad8bde} + + {5268f225-1474-413e-a1cb-5f00b8df5e1e} + @@ -323,5 +329,11 @@ intrusive\multilevel_hashset + + container\multilevel_hashset + + + container\multilevel_hashset + \ No newline at end of file diff --git a/projects/source.test-hdr.mk b/projects/source.test-hdr.mk index a552c28f..efaab042 100644 --- a/projects/source.test-hdr.mk +++ b/projects/source.test-hdr.mk @@ -172,6 +172,7 @@ CDS_TESTHDR_SET := \ tests/test-hdr/set/hdr_michael_set_lazy_rcu_shb.cpp \ tests/test-hdr/set/hdr_michael_set_lazy_rcu_sht.cpp \ tests/test-hdr/set/hdr_michael_set_lazy_nogc.cpp \ + tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp \ tests/test-hdr/set/hdr_refinable_hashset_hashset_std.cpp \ tests/test-hdr/set/hdr_refinable_hashset_boost_flat_set.cpp \ tests/test-hdr/set/hdr_refinable_hashset_boost_list.cpp \ diff --git a/tests/test-hdr/CMakeLists.txt b/tests/test-hdr/CMakeLists.txt index d66292df..f84173f5 100644 --- a/tests/test-hdr/CMakeLists.txt +++ b/tests/test-hdr/CMakeLists.txt @@ -174,6 +174,7 @@ set(CDS_TESTHDR_SET set/hdr_michael_set_lazy_rcu_shb.cpp set/hdr_michael_set_lazy_rcu_sht.cpp set/hdr_michael_set_lazy_nogc.cpp + set/hdr_multilevel_hashset_hp.cpp set/hdr_refinable_hashset_hashset_std.cpp set/hdr_refinable_hashset_boost_flat_set.cpp set/hdr_refinable_hashset_boost_list.cpp diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h index 2b58b0bc..a17823b9 100644 --- a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h +++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h @@ -18,7 +18,7 @@ namespace set { class IntrusiveMultiLevelHashSetHdrTest: public CppUnitMini::TestCase { template - struct Item + struct Item { unsigned int nDisposeCount ; // count of disposer calling Hash hash; @@ -313,7 +313,25 @@ namespace set { el.nIteratorCall = 0; CPPUNIT_ASSERT(s.insert( el )); } - for ( typename Set::iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) { + for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) { + s.erase_at( it ); + it->nIteratorCall = 1; + } + CPPUNIT_ASSERT(s.size() == 0 ); + Set::gc::force_dispose(); + for ( auto& el : arrValue ) { + CPPUNIT_ASSERT( el.nDisposeCount == 1 ); + CPPUNIT_ASSERT( el.nIteratorCall == 1 ); + } + CPPUNIT_ASSERT(s.empty() ); + + // erase with reverse_iterator + for ( auto& el : arrValue ) { + el.nDisposeCount = 0; + el.nIteratorCall = 0; + CPPUNIT_ASSERT(s.insert( el )); + } + for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) { s.erase_at( it ); it->nIteratorCall = 1; } diff --git a/tests/test-hdr/set/hdr_multilevel_hashset.h b/tests/test-hdr/set/hdr_multilevel_hashset.h new file mode 100644 index 00000000..8c7526cd --- /dev/null +++ b/tests/test-hdr/set/hdr_multilevel_hashset.h @@ -0,0 +1,439 @@ +//$$CDS-header$$ + +#ifndef CDSTEST_HDR_MULTILEVEL_HASHSET_H +#define CDSTEST_HDR_MULTILEVEL_HASHSET_H + +#include "cppunit/cppunit_proxy.h" + +// forward declaration +namespace cds { + namespace container {} + namespace opt {} +} + +namespace set { + namespace cc = cds::container; + namespace co = cds::opt; + + class MultiLevelHashSetHdrTest : public CppUnitMini::TestCase + { + template + struct Arg + { + size_t key; + Hash hash; + + Arg( size_t k, Hash const& h ) + : key( k ) + , hash( h ) + {} + }; + + template + struct Item + { + unsigned int nInsertCall; + unsigned int nFindCall; + unsigned int nEraseCall; + mutable unsigned int nIteratorCall; + Hash hash; + size_t key; + + Item( size_t k, Hash const& h ) + : nInsertCall(0) + , nFindCall(0) + , nEraseCall(0) + , nIteratorCall(0) + , hash( h ) + , key( k ) + {} + + explicit Item( Arg const& arg ) + : nInsertCall(0) + , nFindCall(0) + , nEraseCall(0) + , nIteratorCall(0) + , hash( arg.hash ) + , key( arg.key ) + {} + + Item( Item const& i ) + : nInsertCall(0) + , nFindCall(0) + , nEraseCall(0) + , nIteratorCall(0) + , hash( i.hash ) + , key( i.key ) + {} + }; + + template + struct get_hash + { + Hash const& operator()( Item const& i ) const + { + return i.hash; + } + }; + + struct item_disposer { + template + void operator()( Item * p ) + { + ++p->nDisposeCount; + } + }; + + struct hash128 + { + size_t lo; + size_t hi; + + hash128() {} + hash128(size_t l, size_t h) : lo(l), hi(h) {} + hash128( hash128 const& h) : lo(h.lo), hi(h.hi) {} + + struct make { + hash128 operator()( size_t n ) const + { + return hash128( std::hash()( n ), std::hash()( ~n )); + } + hash128 operator()( hash128 const& n ) const + { + return hash128( std::hash()( n.lo ), std::hash()( ~n.hi )); + } + }; + + struct less { + bool operator()( hash128 const& lhs, hash128 const& rhs ) const + { + if ( lhs.hi != rhs.hi ) + return lhs.hi < rhs.hi; + return lhs.lo < rhs.lo; + } + }; + + struct cmp { + int operator()( hash128 const& lhs, hash128 const& rhs ) const + { + if ( lhs.hi != rhs.hi ) + return lhs.hi < rhs.hi ? -1 : 1; + return lhs.lo < rhs.lo ? -1 : lhs.lo == rhs.lo ? 0 : 1; + } + }; + + friend bool operator==( hash128 const& lhs, hash128 const& rhs ) + { + return cmp()( lhs, rhs ) == 0; + } + friend bool operator!=(hash128 const& lhs, hash128 const& rhs) + { + return !( lhs == rhs ); + } + }; + + template + void test_hp( size_t nHeadBits, size_t nArrayBits ) + { + typedef typename Set::hash_type hash_type; + typedef typename Set::value_type value_type; + typedef typename Arg arg_type; + typedef typename Set::guarded_ptr guarded_ptr; + + Hasher hasher; + + size_t const capacity = 1000; + + Set s( nHeadBits, nArrayBits ); + CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size()); + CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits)); + CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits)); + + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT(s.size() == 0); + + // insert test + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( !s.contains( h )); + CPPUNIT_ASSERT( s.insert( value_type( i, h ))); + CPPUNIT_ASSERT(s.contains( h )); + + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == i + 1); + + CPPUNIT_ASSERT( !s.insert( arg_type(i, h) )); + CPPUNIT_ASSERT( s.size() == i + 1); + } + + // update existing test + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( s.contains( h )); + std::pair ret = s.update( arg_type( i, h ), + [](value_type& i, value_type * prev ) { + CPPUNIT_ASSERT_CURRENT( prev != nullptr ); + CPPUNIT_ASSERT_CURRENT( i.key == prev->key ); + CPPUNIT_ASSERT_CURRENT( i.hash == prev->hash ); + i.nInsertCall += 1; + }, false ); + CPPUNIT_ASSERT( ret.first ); + CPPUNIT_ASSERT( !ret.second ); + CPPUNIT_ASSERT( s.contains( h )); + CPPUNIT_ASSERT( s.size() == capacity ); + + guarded_ptr gp(s.get( h )); + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->nInsertCall == 1 ); + CPPUNIT_ASSERT( gp->key == i ); + CPPUNIT_ASSERT( gp->hash == h ); + } + + // erase test + for ( size_t i = 0; i < capacity; ++i ) { + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == capacity - i ); + CPPUNIT_ASSERT(s.find(hasher(i), []( value_type &) {})); + CPPUNIT_ASSERT( s.erase(hasher(i)) ); + CPPUNIT_ASSERT( !s.find(hasher(i), []( value_type &) {})); + CPPUNIT_ASSERT( s.size() == capacity - i - 1); + } + CPPUNIT_ASSERT( s.empty() ); + + // Iterators on empty set + CPPUNIT_ASSERT(s.begin() == s.end()); + CPPUNIT_ASSERT(s.cbegin() == s.cend()); + CPPUNIT_ASSERT(s.rbegin() == s.rend()); + CPPUNIT_ASSERT(s.crbegin() == s.crend()); + + // insert with functor + for ( size_t i = capacity; i > 0; --i ) { + CPPUNIT_ASSERT( s.size() == capacity - i ); + CPPUNIT_ASSERT(s.insert( arg_type( i, hasher(i)), []( value_type& val ) { val.nInsertCall += 1; } )); + CPPUNIT_ASSERT( s.size() == capacity - i + 1 ); + CPPUNIT_ASSERT( !s.empty() ); + + CPPUNIT_ASSERT(s.find( hasher(i), []( value_type& val ) { + CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 ); + val.nFindCall += 1; + } )); + } + CPPUNIT_ASSERT( s.size() == capacity ); + + // for-each iterator test + for ( auto& el : s ) { + CPPUNIT_ASSERT( el.nInsertCall == 1 ); + CPPUNIT_ASSERT( el.nFindCall == 1 ); + el.nFindCall += 1; + } + + // iterator test + for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->nInsertCall == 1 ); + CPPUNIT_ASSERT( it->nFindCall == 2 ); + it->nFindCall += 1; + } + + // reverse iterator test + for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->nInsertCall == 1 ); + CPPUNIT_ASSERT( it->nFindCall == 3 ); + it->nFindCall += 1; + } + + // const iterator test + for ( auto it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->nInsertCall == 1 ); + CPPUNIT_ASSERT( it->nFindCall == 4 ); + it->nIteratorCall += 1; + } + + // const reverse iterator test + for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( it->nInsertCall == 1 ); + CPPUNIT_ASSERT( it->nFindCall == 4 ); + CPPUNIT_ASSERT( it->nIteratorCall == 1 ); + it->nIteratorCall += 1; + } + + // check completeness + for ( size_t i = 1; i <= capacity; ++i ) { + CPPUNIT_ASSERT( s.find( hasher( i ), []( value_type const& el ) { + CPPUNIT_ASSERT_CURRENT( el.nInsertCall == 1 ); + CPPUNIT_ASSERT_CURRENT( el.nFindCall == 4 ); + CPPUNIT_ASSERT_CURRENT( el.nIteratorCall == 2 ); + } )); + } + + // erase with functor test + { + size_t nSum = 0; + for ( size_t i = 1; i <= capacity; ++i ) { + CPPUNIT_ASSERT( s.size() == capacity - i + 1 ); + CPPUNIT_ASSERT(s.erase(hasher(i), [&nSum]( value_type const& val ) { + CPPUNIT_ASSERT_CURRENT( val.nInsertCall == 1 ); + CPPUNIT_ASSERT_CURRENT( val.nFindCall == 4 ); + CPPUNIT_ASSERT_CURRENT( val.nIteratorCall == 2 ); + nSum += val.key; + } )) + CPPUNIT_ASSERT( s.size() == capacity - i ); + CPPUNIT_ASSERT( !s.erase(hasher(i), [&nSum]( value_type const& val ) { nSum += val.key; } )) + } + CPPUNIT_ASSERT(s.empty() ); + CPPUNIT_ASSERT(nSum == (1 + capacity) * capacity / 2 ); + } + + // update test with insert allowing + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( !s.contains( h )); + guarded_ptr gp(s.get( h )); + CPPUNIT_ASSERT( !gp ); + std::pair ret = s.update( arg_type( i, h ), + [](value_type& i, value_type * prev ) { + CPPUNIT_ASSERT_CURRENT( prev == nullptr ); + i.nInsertCall += 1; + }); + CPPUNIT_ASSERT( ret.first ); + CPPUNIT_ASSERT( ret.second ); + CPPUNIT_ASSERT( s.contains( h )); + CPPUNIT_ASSERT( s.size() == i + 1 ); + + gp = s.get( h ); + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->nInsertCall == 1 ); + CPPUNIT_ASSERT( gp->key == i ); + CPPUNIT_ASSERT( gp->hash == h ); + } + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT(s.size() == capacity ); + + // erase_at( iterator ) test + for ( auto it = s.begin(), itEnd = s.end(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( s.erase_at( it )); + } + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT( s.size() == 0 ); + + // emplace test + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( !s.contains( h )); + CPPUNIT_ASSERT( s.emplace( i, hasher(i) )); + CPPUNIT_ASSERT(s.contains( h )); + + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == i + 1); + + CPPUNIT_ASSERT( !s.emplace( arg_type(i, h) )); + CPPUNIT_ASSERT( s.size() == i + 1); + } + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT(s.size() == capacity ); + + // erase_at( reverse_iterator ) test + for ( auto it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it ) { + CPPUNIT_ASSERT( s.erase_at( it )); + } + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT( s.size() == 0 ); + + // extract test + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( !s.contains( h )); + CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) ))); + CPPUNIT_ASSERT(s.contains( h )); + + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == i + 1); + + CPPUNIT_ASSERT( !s.emplace( i, h )); + CPPUNIT_ASSERT( s.size() == i + 1); + } + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT(s.size() == capacity ); + + for ( size_t i = capacity; i != 0; --i ) { + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == i ); + + guarded_ptr gp{ s.extract( hasher(i-1)) }; + CPPUNIT_ASSERT( gp ); + CPPUNIT_ASSERT( gp->key == i - 1); + CPPUNIT_ASSERT(gp->hash == hasher(i-1)); + CPPUNIT_ASSERT( !s.contains(hasher(i-1))); + + gp = s.get(hasher(i-1)); + CPPUNIT_ASSERT( !gp ); + + CPPUNIT_ASSERT( s.size() == i - 1 ); + } + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT(s.size() == 0 ); + + // clear test + for ( size_t i = 0; i < capacity; ++i ) { + hash_type h = hasher(i); + CPPUNIT_ASSERT( !s.contains( h )); + CPPUNIT_ASSERT( s.emplace( arg_type( i, hasher(i) ))); + CPPUNIT_ASSERT(s.contains( h )); + + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT( s.size() == i + 1); + + CPPUNIT_ASSERT( !s.emplace( i, h )); + CPPUNIT_ASSERT( s.size() == i + 1); + } + CPPUNIT_ASSERT( !s.empty() ); + CPPUNIT_ASSERT(s.size() == capacity ); + + s.clear(); + CPPUNIT_ASSERT( s.empty() ); + CPPUNIT_ASSERT(s.size() == 0 ); + + CPPUNIT_MSG( s.statistics() ); + } + + void hp_stdhash(); + void hp_stdhash_stat(); + void hp_stdhash_5_3(); + void hp_stdhash_5_3_stat(); + void hp_hash128(); + void hp_hash128_stat(); + void hp_hash128_4_3(); + void hp_hash128_4_3_stat(); + + void dhp_stdhash(); + void dhp_stdhash_stat(); + void dhp_stdhash_5_3(); + void dhp_stdhash_5_3_stat(); + void dhp_hash128(); + void dhp_hash128_stat(); + void dhp_hash128_4_3(); + void dhp_hash128_4_3_stat(); + + CPPUNIT_TEST_SUITE(MultiLevelHashSetHdrTest) + CPPUNIT_TEST(hp_stdhash) + CPPUNIT_TEST(hp_stdhash_stat) + CPPUNIT_TEST(hp_stdhash_5_3) + CPPUNIT_TEST(hp_stdhash_5_3_stat) + CPPUNIT_TEST(hp_hash128) + CPPUNIT_TEST(hp_hash128_stat) + CPPUNIT_TEST(hp_hash128_4_3) + CPPUNIT_TEST(hp_hash128_4_3_stat) + + CPPUNIT_TEST(dhp_stdhash) + CPPUNIT_TEST(dhp_stdhash_stat) + CPPUNIT_TEST(dhp_stdhash_5_3) + CPPUNIT_TEST(dhp_stdhash_5_3_stat) + CPPUNIT_TEST(dhp_hash128) + CPPUNIT_TEST(dhp_hash128_stat) + CPPUNIT_TEST(dhp_hash128_4_3) + CPPUNIT_TEST(dhp_hash128_4_3_stat) + CPPUNIT_TEST_SUITE_END() + }; + +} // namespace set + +#endif // #ifndef CDSTEST_HDR_MULTILEVEL_HASHSET_H diff --git a/tests/test-hdr/set/hdr_multilevel_hashset_dhp.cpp b/tests/test-hdr/set/hdr_multilevel_hashset_dhp.cpp new file mode 100644 index 00000000..935ff878 --- /dev/null +++ b/tests/test-hdr/set/hdr_multilevel_hashset_dhp.cpp @@ -0,0 +1,207 @@ +//$$CDS-header$$ + +#include "set/hdr_multilevel_hashset.h" +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + namespace { + typedef cds::gc::DHP gc_type; + } // namespace + + void MultiLevelHashSetHdrTest::dhp_stdhash() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + >::type + > set_type2; + test_hp>(4, 2); + } + + void MultiLevelHashSetHdrTest::dhp_hash128() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_hp(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + , co::less< hash_type::less > + >::type + > set_type2; + test_hp(4, 2); + } + + void MultiLevelHashSetHdrTest::dhp_stdhash_stat() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + >::type + > set_type2; + test_hp>(4, 2); + } + + void MultiLevelHashSetHdrTest::dhp_hash128_stat() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef hash128::cmp compare; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_hp(4, 2); + } + + void MultiLevelHashSetHdrTest::dhp_stdhash_5_3() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(5, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + >::type + > set_type2; + test_hp>(5, 3); + } + + void MultiLevelHashSetHdrTest::dhp_hash128_4_3() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_hp(4, 3); + } + + void MultiLevelHashSetHdrTest::dhp_stdhash_5_3_stat() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(5, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + >::type + > set_type2; + test_hp>(5, 3); + } + + void MultiLevelHashSetHdrTest::dhp_hash128_4_3_stat() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + , co::stat< cc::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_hp(4, 3); + } + + +} // namespace set diff --git a/tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp b/tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp new file mode 100644 index 00000000..e96b3c43 --- /dev/null +++ b/tests/test-hdr/set/hdr_multilevel_hashset_hp.cpp @@ -0,0 +1,209 @@ +//$$CDS-header$$ + +#include "set/hdr_multilevel_hashset.h" +#include +#include "unit/print_multilevel_hashset_stat.h" + +namespace set { + namespace { + typedef cds::gc::HP gc_type; + } // namespace + + void MultiLevelHashSetHdrTest::hp_stdhash() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + >::type + > set_type2; + test_hp>(4, 2); + } + + void MultiLevelHashSetHdrTest::hp_hash128() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef hash128::less less; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash128!!!" ); + test_hp(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + , co::less< hash_type::less > + >::type + > set_type2; + test_hp(4, 2); + } + + void MultiLevelHashSetHdrTest::hp_stdhash_stat() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + >::type + > set_type2; + test_hp>(4, 2); + } + + void MultiLevelHashSetHdrTest::hp_hash128_stat() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef hash128::cmp compare; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 2); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + ,co::compare< hash128::cmp > + >::type + > set_type2; + test_hp(4, 2); + } + + void MultiLevelHashSetHdrTest::hp_stdhash_5_3() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(5, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + >::type + > set_type2; + test_hp>(5, 3); + } + + void MultiLevelHashSetHdrTest::hp_hash128_4_3() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef co::v::sequential_consistent memory_model; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::memory_model< co::v::sequential_consistent > + >::type + > set_type2; + test_hp(4, 3); + } + + void MultiLevelHashSetHdrTest::hp_stdhash_5_3_stat() + { + typedef size_t hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" ); + test_hp>(5, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + ,co::stat< cc::multilevel_hashset::stat<>> + >::type + > set_type2; + test_hp>(5, 3); + } + + void MultiLevelHashSetHdrTest::hp_hash128_4_3_stat() + { + typedef hash128 hash_type; + + struct traits: public cc::multilevel_hashset::traits + { + typedef get_hash hash_accessor; + typedef cc::multilevel_hashset::stat<> stat; + typedef hash128::less less; + typedef hash128::cmp compare; + }; + typedef cc::MultiLevelHashSet< gc_type, Item, traits > set_type; + static_assert(std::is_same< typename set_type::hash_type, hash_type>::value, "set::hash_type != hash_type!!!" ); + test_hp(4, 3); + + typedef cc::MultiLevelHashSet< + gc_type, + Item, + typename cc::multilevel_hashset::make_traits< + cc::multilevel_hashset::hash_accessor< get_hash> + , co::stat< cc::multilevel_hashset::stat<>> + , co::less< hash_type::less > + , co::compare< hash128::cmp > + >::type + > set_type2; + test_hp(4, 3); + } + + +} // namespace set + +CPPUNIT_TEST_SUITE_REGISTRATION(set::MultiLevelHashSetHdrTest); -- 2.34.1