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 ae2f72a3df25274a862b63131d1ae0560730eb92..e69a82415ee540ccd7fe548181fa1f3be9c224b6 100644 (file)
--- 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;
 
         /// \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 <size_t Size>
+        using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >;
+
+

         /// \p FeldmanHashMap traits
         struct traits
         {
         /// \p FeldmanHashMap traits
         struct traits
         {


@@ -65,7 +73,7 @@ namespace cds { namespace container {
                 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
                 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
 
                 <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
                 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a>.
 

-                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.
                 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;
 
             */
             typedef opt::none hash;
 

+            /// The size of hash value in bytes
+            /**
+                By default, the size of hash value is <tt>sizeof( hash_type )</tt>
+                where \p hash_type is type of \p hash() result or <tt>sizeof( key )</tt> 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 <tt>sizeof( key_type ) == 8</tt> so \p static_assert will be thrown.
+
+                For that case you can specify \p hash_size explicitly.
+
+                Value \p 0 means auto-calculated <tt>sizeof( key_type )</tt>.
+            */
+            enum: size_t {
+                hash_size = 0
+            };
+

             /// Hash comparing functor
             /**
                 @copydetails cds::intrusive::feldman_hashset::traits::compare
             /// 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
             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.
             - \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 c393492336d44a069f2d41c09ea3594646a13e2a..453b245cad2b294749b3b83803f9b3fba16cf31e 100644 (file)
--- 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;
 
         /// 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;
 
         /// 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
 
             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.
         */
             \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 69ef63081d04dc5c8cd0d14e24cfcca8d41d3510..dce01d0c814398191d21591d2b9ffb6dd2f944d0 100644 (file)
--- 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;
 
         /// 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
         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 aa58903e3e2e8b834e3c49a3695ca46de9927912..c40613c611464e6e2cc2bfca1655e84eeb8101c4 100644 (file)
--- a/test/unit/map/feldman_hashmap_dhp.cpp
+++ b/test/unit/map/feldman_hashmap_dhp.cpp
@@ -129,4 +129,23 @@ namespace {
         test( m );
     }
 
         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<size_t>(1 << 6) );
+        EXPECT_EQ( m.array_node_size(), static_cast<size_t>(1 << 3) );
+        test( m );
+    }
+

 } // namespace
 } // namespace

diff --git a/test/unit/map/feldman_hashmap_hp.cpp b/test/unit/map/feldman_hashmap_hp.cpp
index dd25281e0e2db34d89ae1f818889e543d9ce89df..5f5d09a651900e6952581c869564ca5995f04e92 100644 (file)
--- a/test/unit/map/feldman_hashmap_hp.cpp
+++ b/test/unit/map/feldman_hashmap_hp.cpp
@@ -139,4 +139,23 @@ namespace {
         test( m );
     }
 
         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<size_t>(1 << 6) );
+        EXPECT_EQ( m.array_node_size(), static_cast<size_t>(1 << 3) );
+        test( m );
+    }
+

 } // namespace
 } // namespace

diff --git a/test/unit/map/test_feldman_hashmap.h b/test/unit/map/test_feldman_hashmap.h
index bdde0385a11a23f9c3257fdcd396195da8497803..0d458353d54a6a2218e725eb3824971ca471b8cc 100644 (file)
--- 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;
 
     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<int>( n ))
+                , subkey( static_cast<uint16_t>( 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<int>()(i) );
+            }
+
+            key_type2 operator()( std::string const& str ) const
+            {
+                return key_type2( cds::opt::v::hash<int>()(std::stoi( str )));
+            }
+
+            template <typename T>
+            key_type2 operator()( T const& i ) const
+            {
+                return key_type2( cds::opt::v::hash<int>()(i.nKey));
+            }
+        };
+
+

     protected:
         template <typename Map>
         void test( Map& m )
     protected:
         template <typename Map>
         void test( Map& m )


@@ -55,6 +166,8 @@ namespace cds_test {
             ASSERT_TRUE( m.empty());
             ASSERT_CONTAINER_SIZE( m, 0 );
 
             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;
 
             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 3b22a9fba7711f4ca6e88ccbacd529744d3154b3..f27ef686b0994263a1bf6542386c933b0457872a 100644 (file)
--- 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::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<key_type> arrKeys;
             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
                 arrKeys.push_back( key_type( i ));
             std::vector<key_type> arrKeys;
             for ( int i = 0; i < static_cast<int>(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 65fc5c222c542c7fcee6eaeefb2d7718c5f61ac4..596f977160387d898af8ffceef8e54ce5894c5d4 100644 (file)
--- 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 );
 
             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;
             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 );
     }
 
         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<size_t>(1 << 6) );
+        EXPECT_EQ( m.array_node_size(), static_cast<size_t>(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 <test_name> can be found in this test case"
     REGISTER_TYPED_TEST_CASE_P( FeldmanHashMap,
     // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
     // "No test named <test_name> 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
 
         );
 } // namespace