Added hash_size option support to FeldmanHashMap
authorkhizmax <libcds.dev@gmail.com>
Sat, 12 Nov 2016 09:01:43 +0000 (12:01 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sat, 12 Nov 2016 09:01:43 +0000 (12:01 +0300)
cds/container/details/feldman_hashmap_base.h
cds/container/impl/feldman_hashmap.h
cds/container/impl/feldman_hashset.h
test/unit/map/feldman_hashmap_dhp.cpp
test/unit/map/feldman_hashmap_hp.cpp
test/unit/map/test_feldman_hashmap.h
test/unit/map/test_feldman_hashmap_hp.h
test/unit/map/test_feldman_hashmap_rcu.h

index ae2f72a..e69a824 100644 (file)
@@ -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 <size_t Size>
+        using hash_size = cds::intrusive::feldman_hashset::hash_size< Size >;
+
+
         /// \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>.
 
-                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 <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
@@ -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.
index c393492..453b245 100644 (file)
@@ -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.
         */
index 69ef630..dce01d0 100644 (file)
@@ -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
index aa58903..c40613c 100644 (file)
@@ -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<size_t>(1 << 6) );
+        EXPECT_EQ( m.array_node_size(), static_cast<size_t>(1 << 3) );
+        test( m );
+    }
+
 } // namespace
index dd25281..5f5d09a 100644 (file)
@@ -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<size_t>(1 << 6) );
+        EXPECT_EQ( m.array_node_size(), static_cast<size_t>(1 << 3) );
+        test( m );
+    }
+
 } // namespace
index bdde038..0d45835 100644 (file)
@@ -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<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 )
@@ -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;
 
index 3b22a9f..f27ef68 100644 (file)
@@ -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<key_type> arrKeys;
             for ( int i = 0; i < static_cast<int>(kkSize); ++i )
                 arrKeys.push_back( key_type( i ));
index 65fc5c2..596f977 100644 (file)
@@ -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<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,
-        defaulted, compare, less, cmpmix, backoff, stat
+        defaulted, compare, less, cmpmix, backoff, stat, explicit_key_size
         );
 } // namespace