From: khizmax Date: Fri, 11 Nov 2016 15:14:10 +0000 (+0300) Subject: Added new option hash_size for FeldmanHashSet X-Git-Tag: v2.2.0~73 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=a22c589d97221035acf12552f38ed18b48a29bc9 Added new option hash_size for FeldmanHashSet --- diff --git a/cds/algo/split_bitstring.h b/cds/algo/split_bitstring.h index 738accbb..f74d4ea7 100644 --- a/cds/algo/split_bitstring.h +++ b/cds/algo/split_bitstring.h @@ -43,19 +43,25 @@ namespace cds { namespace algo { The splitter stores a const reference to bit-string, not a copy. The maximum count of bits that can be cut in a single call is sizeof(UInt) * 8 + + Template parameters: + - \p BitString - a fixed-sized type that interprets as bit string + - \p BitStringSize - the siZe of \p BitString in bytes, default is sizeof( BitString ) + - \p UInt - an unsigned integer, return type of \p cut() */ - template ::type > + template ::type > class split_bitstring { public: typedef BitString bitstring; ///< Bit-string type typedef UInt uint_type; ///< Bit-string portion type + static CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize; ///< size of \p BitString in bytes //@cond - static CDS_CONSTEXPR size_t const c_nHashSize = (sizeof(bitstring) + sizeof(uint_type) - 1) / sizeof(uint_type); + static CDS_CONSTEXPR size_t const c_nHashSize = (c_bitstring_size + sizeof(uint_type) - 1) / sizeof(uint_type); static CDS_CONSTEXPR size_t const c_nBitPerByte = 8; - static CDS_CONSTEXPR size_t const c_nBitPerHash = sizeof(bitstring) * c_nBitPerByte; - static CDS_CONSTEXPR size_t const c_nBitPerInt = sizeof(uint_type) * c_nBitPerByte; + static CDS_CONSTEXPR size_t const c_nBitPerHash = c_bitstring_size * c_nBitPerByte; + static CDS_CONSTEXPR size_t const c_nBitPerInt = sizeof( uint_type ) * c_nBitPerByte; //@endcond public: diff --git a/cds/container/details/feldman_hashset_base.h b/cds/container/details/feldman_hashset_base.h index cbdd1431..3f2ab94b 100644 --- a/cds/container/details/feldman_hashset_base.h +++ b/cds/container/details/feldman_hashset_base.h @@ -46,6 +46,13 @@ namespace cds { namespace container { template using hash_accessor = cds::intrusive::feldman_hashset::hash_accessor< Accessor >; + /// Hash size option + /** + @copydetails cds::intrusive::feldman_hashset::traits::hash_size + */ + template + using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >; + /// \p FeldmanHashSet internal statistics, see cds::intrusive::feldman_hashset::stat template using stat = cds::intrusive::feldman_hashset::stat< EventCounter >; @@ -69,6 +76,14 @@ namespace cds { namespace container { */ typedef cds::opt::none hash_accessor; + /// The size of hash value in bytes + /** + @copydetails cds::intrusive::feldman_hashset::traits::hash_size + */ + enum : size_t { + hash_size = 0 + }; + /// Hash comparing functor /** @copydetails cds::intrusive::feldman_hashset::traits::compare @@ -126,6 +141,8 @@ namespace cds { namespace container { Supported \p Options are: - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor. @copydetails traits::hash_accessor + - \p feldman_hashset::hash_size - the size of hash value in bytes. + @copydetails traits::hash_size - \p opt::allocator - item allocator @copydetails traits::allocator - \p opt::node_allocator - array node allocator. diff --git a/cds/container/feldman_hashset_rcu.h b/cds/container/feldman_hashset_rcu.h index 82d3b6dc..dc4e48a1 100644 --- a/cds/container/feldman_hashset_rcu.h +++ b/cds/container/feldman_hashset_rcu.h @@ -112,6 +112,9 @@ namespace cds { namespace container { static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking typedef typename base_class::exempt_ptr exempt_ptr; ///< pointer to extracted node + /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + /// Level statistics typedef feldman_hashset::level_statistics level_statistics; diff --git a/cds/container/impl/feldman_hashset.h b/cds/container/impl/feldman_hashset.h index d0ca0d5a..69ef6308 100644 --- a/cds/container/impl/feldman_hashset.h +++ b/cds/container/impl/feldman_hashset.h @@ -148,6 +148,9 @@ namespace cds { namespace container { /// Count of hazard pointers required static CDS_CONSTEXPR size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; + /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + /// Level statistics typedef feldman_hashset::level_statistics level_statistics; diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h index 94902af2..9d167a5b 100644 --- a/cds/intrusive/details/feldman_hashset_base.h +++ b/cds/intrusive/details/feldman_hashset_base.h @@ -61,6 +61,22 @@ namespace cds { namespace intrusive { //@endcond }; + // Hash size option + /** + @copydetails traits::hash_size + */ + template + struct hash_size { + //@cond + template struct pack: public Base + { + enum: size_t { + hash_size = Size + }; + }; + //@endcond + }; + /// \p FeldmanHashSet internal statistics template struct stat { @@ -163,6 +179,26 @@ namespace cds { namespace intrusive { */ typedef cds::opt::none hash_accessor; + /// The size of hash value in bytes + /** + By default, the size of hash value is sizeof( hash_type ). + Sometimes it is not correct, for example, for that 6-byte struct \p static_assert will be thrown: + \code + struct key_type { + uint32_t key1; + uint16_t subkey; + }; + + static_assert( sizeof( key_type ) == 6, "Key type size mismatch" ); + \endcode + For that case you can specify \p hash_size explicitly. + + Value \p 0 means sizeof( hash_type ). + */ + enum : size_t { + hash_size = 0 + }; + /// Disposer for removing data nodes typedef cds::intrusive::opt::v::empty_disposer disposer; @@ -192,7 +228,7 @@ namespace cds { namespace intrusive { /// Array node allocator /** - Allocator for array nodes. That allocator is used for creating \p headNode and \p arrayNode when the set grows. + Allocator for array nodes. The allocator is used for creating \p headNode and \p arrayNode when the set grows. Default is \ref CDS_DEFAULT_ALLOCATOR */ typedef CDS_DEFAULT_ALLOCATOR node_allocator; @@ -226,6 +262,8 @@ namespace cds { namespace intrusive { Supported \p Options are: - \p feldman_hashset::hash_accessor - mandatory option, hash accessor functor. @copydetails traits::hash_accessor + - \p feldman_hashset::hash_size - the size of hash value in bytes. + @copydetails traits::hash_size - \p opt::node_allocator - array node allocator. @copydetails traits::node_allocator - \p opt::compare - hash comparison functor. No default functor is provided. @@ -300,8 +338,8 @@ namespace cds { namespace intrusive { //@cond namespace details { - template - using hash_splitter = cds::algo::split_bitstring< HashType >; + template + using hash_splitter = cds::algo::split_bitstring< HashType, HashSize >; struct metrics { size_t head_node_size; // power-of-two @@ -365,7 +403,10 @@ namespace cds { namespace intrusive { feldman_hashset::bitwise_compare< hash_type > >::type hash_comparator; - typedef feldman_hashset::details::hash_splitter< hash_type > hash_splitter; + /// The size of hash_type in bytes, see \p traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = traits::hash_size == 0 ? sizeof( hash_type ) : traits::hash_size; + + typedef feldman_hashset::details::hash_splitter< hash_type, c_hash_size > hash_splitter; enum node_flags { flag_array_converting = 1, ///< the cell is converting from data node to an array node @@ -422,7 +463,7 @@ namespace cds { namespace intrusive { public: multilevel_array(size_t head_bits, size_t array_bits ) - : m_Metrics(feldman_hashset::details::metrics::make(head_bits, array_bits, sizeof(hash_type))) + : m_Metrics(feldman_hashset::details::metrics::make( head_bits, array_bits, c_hash_size )) , m_Head( alloc_head_node()) {} diff --git a/cds/intrusive/feldman_hashset_rcu.h b/cds/intrusive/feldman_hashset_rcu.h index b0b5f512..af451990 100644 --- a/cds/intrusive/feldman_hashset_rcu.h +++ b/cds/intrusive/feldman_hashset_rcu.h @@ -113,6 +113,9 @@ namespace cds { namespace intrusive { using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, disposer, void >; ///< pointer to extracted node + /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + //@cond typedef feldman_hashset::level_statistics level_statistics; //@endcond diff --git a/cds/intrusive/impl/feldman_hashset.h b/cds/intrusive/impl/feldman_hashset.h index bcebf4fd..9b6d9b80 100644 --- a/cds/intrusive/impl/feldman_hashset.h +++ b/cds/intrusive/impl/feldman_hashset.h @@ -145,6 +145,9 @@ namespace cds { namespace intrusive { /// Count of hazard pointers required static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2; + /// The size of hash_type in bytes, see \p feldman_hashset::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + /// Level statistics typedef feldman_hashset::level_statistics level_statistics; diff --git a/test/unit/intrusive-set/intrusive_feldman_hashset_dhp.cpp b/test/unit/intrusive-set/intrusive_feldman_hashset_dhp.cpp index 95377f40..fffa02f9 100644 --- a/test/unit/intrusive-set/intrusive_feldman_hashset_dhp.cpp +++ b/test/unit/intrusive-set/intrusive_feldman_hashset_dhp.cpp @@ -143,4 +143,23 @@ namespace { test( s ); } + TEST_F( IntrusiveFeldmanHashSet_DHP, explicit_hash_size ) + { + struct traits: public ci::feldman_hashset::traits + { + typedef base_class::hash_accessor2 hash_accessor; + enum: size_t { + hash_size = sizeof( std::declval().nKey ) + }; + typedef base_class::cmp2 compare; + typedef mock_disposer disposer; + typedef ci::feldman_hashset::stat<> stat; + }; + + typedef ci::FeldmanHashSet< gc_type, int_item2, traits > set_type; + + set_type s( 8, 3 ); + test( s ); + } + } // namespace diff --git a/test/unit/intrusive-set/intrusive_feldman_hashset_hp.cpp b/test/unit/intrusive-set/intrusive_feldman_hashset_hp.cpp index 6e65a08e..c8e9e534 100644 --- a/test/unit/intrusive-set/intrusive_feldman_hashset_hp.cpp +++ b/test/unit/intrusive-set/intrusive_feldman_hashset_hp.cpp @@ -144,4 +144,23 @@ namespace { test( s ); } + TEST_F( IntrusiveFeldmanHashSet_HP, explicit_hash_size ) + { + struct traits: public ci::feldman_hashset::traits + { + typedef base_class::hash_accessor2 hash_accessor; + enum: size_t { + hash_size = sizeof( std::declval().nKey ) + }; + typedef base_class::cmp2 compare; + typedef mock_disposer disposer; + typedef ci::feldman_hashset::stat<> stat; + }; + + typedef ci::FeldmanHashSet< gc_type, int_item2, traits > set_type; + + set_type s( 8, 3 ); + test( s ); + } + } // namespace diff --git a/test/unit/intrusive-set/test_intrusive_feldman_hashset.h b/test/unit/intrusive-set/test_intrusive_feldman_hashset.h index 1409e8a9..da71af1c 100644 --- a/test/unit/intrusive-set/test_intrusive_feldman_hashset.h +++ b/test/unit/intrusive-set/test_intrusive_feldman_hashset.h @@ -47,8 +47,8 @@ namespace cds_test { public: struct stat { - unsigned int nDisposeCount ; // count of disposer calling - unsigned int nFindCount ; // count of find-functor calling + unsigned int nDisposeCount; // count of disposer calling + unsigned int nFindCount; // count of find-functor calling unsigned int nInsertCount; mutable unsigned int nEraseCount; @@ -59,7 +59,7 @@ namespace cds_test { void clear_stat() { - memset( this, 0, sizeof( *this )); + memset( this, 0, sizeof( *this ) ); } }; @@ -76,9 +76,9 @@ namespace cds_test { , nVal( key ) {} - int_item(int key, int val) + int_item( int key, int val ) : nKey( key ) - , nVal(val) + , nVal( val ) {} int_item( int_item const& v ) @@ -93,6 +93,53 @@ namespace cds_test { } }; + struct key_val { + int nKey; + int nVal; + + key_val() + {} + + key_val( int key ) + : nKey( key ) + , nVal( key ) + {} + + key_val( int key, int val ) + : nKey( key ) + , nVal( val ) + {} + + key_val( key_val const& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + {} + + int key() const + { + return nKey; + } + }; + + struct int_item2: public key_val, public stat + { + int_item2() + {} + + explicit int_item2( int key ) + : key_val( key ) + {} + + int_item2( int key, int val ) + : key_val( key, val ) + {} + + int_item2( int_item2 const& v ) + : key_val( v ) + , stat() + {} + }; + struct hash_accessor { int operator()( int_item const& v ) const { @@ -100,6 +147,13 @@ namespace cds_test { } }; + struct hash_accessor2 { + key_val const& operator()( int_item2 const& v ) const + { + return v; + } + }; + struct simple_item_counter { size_t m_nCount; @@ -137,6 +191,15 @@ namespace cds_test { } }; + struct cmp2 { + int operator ()( key_val const& lhs, key_val const& rhs ) const + { + if ( lhs.key() < rhs.key() ) + return -1; + return lhs.key() > rhs.key() ? 1 : 0; + } + }; + struct mock_disposer { template diff --git a/test/unit/intrusive-set/test_intrusive_feldman_hashset_rcu.h b/test/unit/intrusive-set/test_intrusive_feldman_hashset_rcu.h index 6b5c1fc2..3f943632 100644 --- a/test/unit/intrusive-set/test_intrusive_feldman_hashset_rcu.h +++ b/test/unit/intrusive-set/test_intrusive_feldman_hashset_rcu.h @@ -223,10 +223,29 @@ TYPED_TEST_P( IntrusiveFeldmanHashSet, stat ) this->test( s ); } +TYPED_TEST_P( IntrusiveFeldmanHashSet, explicit_hash_size ) +{ + struct traits: public ci::feldman_hashset::traits + { + typedef typename TestFixture::hash_accessor2 hash_accessor; + enum: size_t { + hash_size = sizeof( std::declval().nKey ) + }; + typedef typename TestFixture::cmp2 compare; + typedef typename TestFixture::mock_disposer disposer; + typedef ci::feldman_hashset::stat<> stat; + }; + + typedef ci::FeldmanHashSet< typename TestFixture::rcu_type, typename TestFixture::int_item2, traits > set_type; + + set_type s( 8, 3 ); + this->test( s ); +} + // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as // "No test named can be found in this test case" REGISTER_TYPED_TEST_CASE_P( IntrusiveFeldmanHashSet, - compare, less, cmpmix, backoff, stat + compare, less, cmpmix, backoff, stat, explicit_hash_size ); diff --git a/test/unit/set/feldman_hashset_dhp.cpp b/test/unit/set/feldman_hashset_dhp.cpp index 8d96bf8e..9c4269a8 100644 --- a/test/unit/set/feldman_hashset_dhp.cpp +++ b/test/unit/set/feldman_hashset_dhp.cpp @@ -156,4 +156,21 @@ namespace { test( s ); } + TEST_F( FeldmanHashSet_DHP, explicit_hash_size ) + { + struct set_traits: public cc::feldman_hashset::traits + { + typedef get_hash2 hash_accessor; + enum: size_t { + hash_size = sizeof( std::declval().nKey ) + }; + typedef cmp2 compare; + typedef cc::feldman_hashset::stat<> stat; + }; + typedef cc::FeldmanHashSet< gc_type, int_item2, set_traits > set_type; + + set_type s( 1, 1 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/feldman_hashset_hp.cpp b/test/unit/set/feldman_hashset_hp.cpp index 0c071552..43d888df 100644 --- a/test/unit/set/feldman_hashset_hp.cpp +++ b/test/unit/set/feldman_hashset_hp.cpp @@ -157,4 +157,21 @@ namespace { test( s ); } + TEST_F( FeldmanHashSet_HP, explicit_hash_size ) + { + struct set_traits: public cc::feldman_hashset::traits + { + typedef get_hash2 hash_accessor; + enum: size_t { + hash_size = sizeof( std::declval(). nKey ) + }; + typedef cmp2 compare; + typedef cc::feldman_hashset::stat<> stat; + }; + typedef cc::FeldmanHashSet< gc_type, int_item2, set_traits > set_type; + + set_type s( 1, 1 ); + test( s ); + } + } // namespace diff --git a/test/unit/set/test_feldman_hashset.h b/test/unit/set/test_feldman_hashset.h index 4536455d..a7d88bbd 100644 --- a/test/unit/set/test_feldman_hashset.h +++ b/test/unit/set/test_feldman_hashset.h @@ -129,6 +129,72 @@ namespace cds_test { } }; + struct key_val { + int nKey; + int nVal; + + key_val() + {} + + key_val( int key ) + : nKey( key ) + , nVal( key ) + {} + + key_val( int key, int val ) + : nKey( key ) + , nVal( val ) + {} + + key_val( key_val const& v ) + : nKey( v.nKey ) + , nVal( v.nVal ) + {} + + int key() const + { + return nKey; + } + }; + + struct int_item2: public key_val, public stat + { + std::string strVal; + + int_item2() + {} + + explicit int_item2( int key ) + : key_val( key ) + {} + + int_item2( int key, int val ) + : key_val( key, val ) + {} + + int_item2( int_item2 const& v ) + : key_val( v ) + , stat() + , strVal( v.strVal ) + {} + + int_item2( int_item2&& v ) + : key_val( v ) + , stat() + , strVal( std::move( v.strVal )) + {} + + int_item2( int k, std::string&& s ) + : key_val( k, k * 2 ) + , strVal( std::move( s ) ) + {} + + explicit int_item2( other_item const& s ) + : key_val( s.key(), s.key() * 2 ) + {} + }; + + struct get_hash { int operator()( int_item const& i ) const { @@ -146,6 +212,23 @@ namespace cds_test { } }; + struct get_hash2 { + key_val const& operator()( int_item2 const& i ) const + { + return i; + } + + key_val operator()( other_item const& i ) const + { + return key_val( i.key() ); + } + + key_val operator()( int i ) const + { + return key_val( i ); + } + }; + struct simple_item_counter { size_t m_nCount; @@ -184,6 +267,15 @@ namespace cds_test { } }; + struct cmp2 { + int operator ()( key_val const& v1, key_val const& v2 ) const + { + if ( v1.key() < v2.key() ) + return -1; + return v1.key() > v2.key() ? 1 : 0; + } + }; + struct other_less { template bool operator()( Q const& lhs, T const& rhs ) const diff --git a/test/unit/set/test_feldman_hashset_rcu.h b/test/unit/set/test_feldman_hashset_rcu.h index 2ecc1bfd..e7016fae 100644 --- a/test/unit/set/test_feldman_hashset_rcu.h +++ b/test/unit/set/test_feldman_hashset_rcu.h @@ -280,10 +280,30 @@ namespace { this->test( s ); } + TYPED_TEST_P( FeldmanHashSet, explicit_hash_size ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::int_item2 int_item; + typedef typename TestFixture::get_hash2 get_hash2; + + struct set_traits: public cc::feldman_hashset::traits + { + enum: size_t { + hash_size = sizeof( std::declval().nKey ) + }; + typedef get_hash2 hash_accessor; + typedef cc::feldman_hashset::stat<> stat; + }; + typedef cc::FeldmanHashSet< rcu_type, int_item2, set_traits > set_type; + + set_type s( 8, 4 ); + this->test( s ); + } + // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as // "No test named can be found in this test case" REGISTER_TYPED_TEST_CASE_P( FeldmanHashSet, - defaulted, compare, less, cmpmix, item_counting, backoff, stat + defaulted, compare, less, cmpmix, item_counting, backoff, stat, explicit_hash_size ); } // namespace