From: khizmax Date: Sat, 12 Nov 2016 09:01:43 +0000 (+0300) Subject: Added hash_size option support to FeldmanHashMap X-Git-Tag: v2.2.0~71 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=9e2f0b2034e923c83895564fcc77241fd34ba717 Added hash_size option support to FeldmanHashMap --- diff --git a/cds/container/details/feldman_hashmap_base.h b/cds/container/details/feldman_hashmap_base.h index ae2f72a3..e69a8241 100644 --- a/cds/container/details/feldman_hashmap_base.h +++ b/cds/container/details/feldman_hashmap_base.h @@ -54,6 +54,14 @@ namespace cds { namespace container { /// \p FeldmanHashMap level statistics typedef cds::intrusive::feldman_hashset::level_statistics level_statistics; + /// Key size option + /** + @copydetails cds::container::feldman_hashmap::traits::hash_size + */ + template + using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >; + + /// \p FeldmanHashMap traits struct traits { @@ -65,7 +73,7 @@ namespace cds { namespace container { CityHash or its successor FarmHash. - If you use a fixed-sized key you may use it directly instead of a hash. + If you use a fixed-sized key you can use it directly instead of a hash. In such case \p %traits::hash should be specified as \p opt::none. However, if you want to use the hash values or if your key type is not fixed-sized you must specify a proper hash functor in your traits. @@ -122,6 +130,30 @@ namespace cds { namespace container { */ typedef opt::none hash; + /// The size of hash value in bytes + /** + By default, the size of hash value is sizeof( hash_type ) + where \p hash_type is type of \p hash() result or sizeof( key ) if you use fixed-sized key. + + Sometimes that size is wrong, for example, for that 6-byte key: + \code + struct key_type { + uint32_t key; + uint16_t subkey; + }; + + static_assert( sizeof( key_type ) == 6, "Key type size mismatch" ); + \endcode + Here sizeof( key_type ) == 8 so \p static_assert will be thrown. + + For that case you can specify \p hash_size explicitly. + + Value \p 0 means auto-calculated sizeof( key_type ). + */ + enum: size_t { + hash_size = 0 + }; + /// Hash comparing functor /** @copydetails cds::intrusive::feldman_hashset::traits::compare @@ -179,6 +211,8 @@ namespace cds { namespace container { Supported \p Options are: - \p opt::hash - a hash functor, default is \p std::hash @copydetails traits::hash + - \p feldman_hashmap::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/impl/feldman_hashmap.h b/cds/container/impl/feldman_hashmap.h index c3934923..453b245c 100644 --- a/cds/container/impl/feldman_hashmap.h +++ b/cds/container/impl/feldman_hashmap.h @@ -155,6 +155,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 \p hash_type in bytes, see \p feldman_hashmap::traits::hash_size for explanation + static CDS_CONSTEXPR size_t const c_hash_size = base_class::c_hash_size; + /// Level statistics typedef feldman_hashmap::level_statistics level_statistics; @@ -358,7 +361,7 @@ namespace cds { namespace container { Equation for \p head_bits and \p array_bits: \code - sizeof( hash_type ) * 8 == head_bits + N * array_bits + c_hash_size * 8 == head_bits + N * array_bits \endcode where \p N is multi-level array depth. */ diff --git a/cds/container/impl/feldman_hashset.h b/cds/container/impl/feldman_hashset.h index 69ef6308..dce01d0c 100644 --- a/cds/container/impl/feldman_hashset.h +++ b/cds/container/impl/feldman_hashset.h @@ -148,7 +148,7 @@ 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 + /// The size of \p 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 diff --git a/test/unit/map/feldman_hashmap_dhp.cpp b/test/unit/map/feldman_hashmap_dhp.cpp index aa58903e..c40613c6 100644 --- a/test/unit/map/feldman_hashmap_dhp.cpp +++ b/test/unit/map/feldman_hashmap_dhp.cpp @@ -129,4 +129,23 @@ namespace { test( m ); } + TEST_F( FeldmanHashMap_DHP, explicit_key_size ) + { + struct map_traits: public cc::feldman_hashmap::traits + { + enum: size_t { + hash_size = sizeof( int ) + sizeof( uint16_t ) + }; + typedef hash2 hash; + typedef less2 less; + typedef cc::feldman_hashmap::stat<> stat; + }; + typedef cc::FeldmanHashMap< gc_type, key_type2, value_type, map_traits > map_type; + + map_type m( 5, 3 ); + EXPECT_EQ( m.head_size(), static_cast(1 << 6) ); + EXPECT_EQ( m.array_node_size(), static_cast(1 << 3) ); + test( m ); + } + } // namespace diff --git a/test/unit/map/feldman_hashmap_hp.cpp b/test/unit/map/feldman_hashmap_hp.cpp index dd25281e..5f5d09a6 100644 --- a/test/unit/map/feldman_hashmap_hp.cpp +++ b/test/unit/map/feldman_hashmap_hp.cpp @@ -139,4 +139,23 @@ namespace { test( m ); } + TEST_F( FeldmanHashMap_HP, explicit_key_size ) + { + struct map_traits: public cc::feldman_hashmap::traits + { + enum: size_t { + hash_size = sizeof(int) + sizeof( uint16_t) + }; + typedef hash2 hash; + typedef less2 less; + typedef cc::feldman_hashmap::stat<> stat; + }; + typedef cc::FeldmanHashMap< gc_type, key_type2, value_type, map_traits > map_type; + + map_type m( 5, 3 ); + EXPECT_EQ( m.head_size(), static_cast(1 << 6) ); + EXPECT_EQ( m.array_node_size(), static_cast(1 << 3) ); + test( m ); + } + } // namespace diff --git a/test/unit/map/test_feldman_hashmap.h b/test/unit/map/test_feldman_hashmap.h index bdde0385..0d458353 100644 --- a/test/unit/map/test_feldman_hashmap.h +++ b/test/unit/map/test_feldman_hashmap.h @@ -45,6 +45,117 @@ namespace cds_test { public: static size_t const kSize = 1000; + struct key_type2 { + int nKey; + uint16_t subkey; + + explicit key_type2( int n ) + : nKey( n ) + , subkey( n ) + {} + + explicit key_type2( size_t n ) + : nKey( static_cast( n )) + , subkey( static_cast( n )) + {} + + explicit key_type2( std::string const& str ) + : nKey( std::stoi( str ) ) + , subkey( nKey ) + {} + + key_type2( key_type2 const& s ) + : nKey( s.nKey ) + , subkey( s.subkey ) + {} + }; + + struct less2 + { + bool operator ()( key_type2 const& v1, key_type2 const& v2 ) const + { + return v1.nKey < v2.nKey; + } + + bool operator ()( key_type2 const& v1, int v2 ) const + { + return v1.nKey < v2; + } + + bool operator ()( int v1, key_type2 const& v2 ) const + { + return v1 < v2.nKey; + } + + bool operator ()( key_type2 const& v1, std::string const& v2 ) const + { + return v1.nKey < std::stoi( v2 ); + } + + bool operator ()( std::string const& v1, key_type2 const& v2 ) const + { + return std::stoi( v1 ) < v2.nKey; + } + }; + + struct cmp2 { + int operator ()( key_type2 const& v1, key_type2 const& v2 ) const + { + if ( v1.nKey < v2.nKey ) + return -1; + return v1.nKey > v2.nKey ? 1 : 0; + } + + int operator ()( key_type2 const& v1, int v2 ) const + { + if ( v1.nKey < v2 ) + return -1; + return v1.nKey > v2 ? 1 : 0; + } + + int operator ()( int v1, key_type2 const& v2 ) const + { + if ( v1 < v2.nKey ) + return -1; + return v1 > v2.nKey ? 1 : 0; + } + + int operator ()( key_type2 const& v1, std::string const& v2 ) const + { + int n2 = std::stoi( v2 ); + if ( v1.nKey < n2 ) + return -1; + return v1.nKey > n2 ? 1 : 0; + } + + int operator ()( std::string const& v1, key_type2 const& v2 ) const + { + int n1 = std::stoi( v1 ); + if ( n1 < v2.nKey ) + return -1; + return n1 > v2.nKey ? 1 : 0; + } + }; + + struct hash2 { + key_type2 operator()( int i ) const + { + return key_type2( cds::opt::v::hash()(i) ); + } + + key_type2 operator()( std::string const& str ) const + { + return key_type2( cds::opt::v::hash()(std::stoi( str ))); + } + + template + key_type2 operator()( T const& i ) const + { + return key_type2( cds::opt::v::hash()(i.nKey)); + } + }; + + protected: template void test( Map& m ) @@ -55,6 +166,8 @@ namespace cds_test { ASSERT_TRUE( m.empty()); ASSERT_CONTAINER_SIZE( m, 0 ); + typedef typename Map::key_type key_type; + typedef typename Map::mapped_type value_type; typedef typename Map::value_type map_pair; size_t const kkSize = kSize; diff --git a/test/unit/map/test_feldman_hashmap_hp.h b/test/unit/map/test_feldman_hashmap_hp.h index 3b22a9fb..f27ef686 100644 --- a/test/unit/map/test_feldman_hashmap_hp.h +++ b/test/unit/map/test_feldman_hashmap_hp.h @@ -54,6 +54,9 @@ namespace cds_test { //typedef typename Map::value_type map_pair; size_t const kkSize = base_class::kSize; + typedef typename Map::key_type key_type; + typedef typename Map::mapped_type value_type; + std::vector arrKeys; for ( int i = 0; i < static_cast(kkSize); ++i ) arrKeys.push_back( key_type( i )); diff --git a/test/unit/map/test_feldman_hashmap_rcu.h b/test/unit/map/test_feldman_hashmap_rcu.h index 65fc5c22..596f9771 100644 --- a/test/unit/map/test_feldman_hashmap_rcu.h +++ b/test/unit/map/test_feldman_hashmap_rcu.h @@ -55,6 +55,8 @@ namespace { ASSERT_TRUE( m.empty()); ASSERT_CONTAINER_SIZE( m, 0 ); + typedef typename Map::key_type key_type; + typedef typename Map::mapped_type value_type; typedef typename Map::value_type map_pair; typedef typename Map::rcu_lock rcu_lock; typedef typename Map::exempt_ptr exempt_ptr; @@ -272,10 +274,33 @@ namespace { this->test( m ); } + TYPED_TEST_P( FeldmanHashMap, explicit_key_size ) + { + typedef typename TestFixture::rcu_type rcu_type; + typedef typename TestFixture::key_type2 key_type2; + typedef typename TestFixture::value_type value_type; + + struct map_traits: public cc::feldman_hashmap::traits + { + enum: size_t { + hash_size = sizeof( int ) + sizeof( uint16_t ) + }; + typedef typename TestFixture::hash2 hash; + typedef typename TestFixture::less2 less; + typedef cc::feldman_hashmap::stat<> stat; + }; + typedef cc::FeldmanHashMap< rcu_type, key_type2, value_type, map_traits > map_type; + + map_type m( 5, 3 ); + EXPECT_EQ( m.head_size(), static_cast(1 << 6) ); + EXPECT_EQ( m.array_node_size(), static_cast(1 << 3) ); + this->test( m ); + } + // 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( FeldmanHashMap, - defaulted, compare, less, cmpmix, backoff, stat + defaulted, compare, less, cmpmix, backoff, stat, explicit_key_size ); } // namespace