Fixed FeldmanHashSet/Map: use delete[] operator for array deallocation

[libcds.git] / cds / intrusive / details / feldman_hashset_base.h

diff --git a/cds/intrusive/details/feldman_hashset_base.h b/cds/intrusive/details/feldman_hashset_base.h
index 792dc018aafa508cab67768dca21a6b41df3a2db..3ea4ccd5408579ed372c5f918f856068360240b9 100644 (file)
--- a/cds/intrusive/details/feldman_hashset_base.h
+++ b/cds/intrusive/details/feldman_hashset_base.h
@@ -5,7 +5,7 @@
 
     Source code repo: http://github.com/khizmax/libcds/
     Download: http://sourceforge.net/projects/libcds/files/
-    
+
     Redistribution and use in source and binary forms, with or without
     modification, are permitted provided that the following conditions are met:
 
@@ -61,6 +61,22 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
+        /// Hash size option
+        /**
+            @copydetails traits::hash_size
+        */
+        template <size_t Size>
+        struct hash_size {
+            //@cond
+            template <typename Base> struct pack: public Base
+            {
+                enum: size_t {
+                    hash_size = Size
+                };
+            };
+            //@endcond
+        };
+
         /// \p FeldmanHashSet internal statistics
         template <typename EventCounter = cds::atomicity::event_counter>
         struct stat {
@@ -163,6 +179,24 @@ 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 <tt>sizeof( hash_type )</tt>.
+                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 <tt>sizeof( hash_type )</tt>.
+            */
+            static CDS_CONSTEXPR size_t const hash_size = 0;
+
             /// Disposer for removing data nodes
             typedef cds::intrusive::opt::v::empty_disposer disposer;
 
@@ -192,7 +226,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 +260,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 +336,8 @@ namespace cds { namespace intrusive {
 
         //@cond
         namespace details {
-            template <typename HashType >
-            using hash_splitter = cds::algo::split_bitstring< HashType >;
+            template <typename HashType, size_t HashSize >
+            using hash_splitter = cds::algo::split_bitstring< HashType, HashSize >;
 
             struct metrics {
                 size_t  head_node_size;     // power-of-two
@@ -354,10 +390,9 @@ namespace cds { namespace intrusive {
             /// Hash type deduced from \p hash_accessor return type
             typedef typename std::decay<
                 typename std::remove_reference<
-                decltype(hash_accessor()(std::declval<value_type>()))
+                    decltype(hash_accessor()(std::declval<value_type>()))
                 >::type
             >::type hash_type;
-            //typedef typename std::result_of< hash_accessor( std::declval<value_type>()) >::type hash_type;
             static_assert(!std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value");
 
             typedef typename cds::opt::details::make_comparator_from<
@@ -366,7 +401,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 ) : static_cast<size_t>( 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
@@ -423,14 +461,14 @@ 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())
             {}
 
             ~multilevel_array()
             {
                 destroy_tree();
-                free_array_node(m_Head);
+                free_array_node( m_Head, head_size());
             }
 
             node_ptr traverse(traverse_data& pos)
@@ -504,8 +542,8 @@ namespace cds { namespace intrusive {
                 for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
                     node_ptr slot = p->load(memory_model::memory_order_relaxed);
                     if (slot.bits() == flag_array_node) {
-                        destroy_array_nodes(to_array(slot.ptr()), array_node_size());
-                        free_array_node(to_array(slot.ptr()));
+                        destroy_array_nodes( to_array(slot.ptr()), array_node_size());
+                        free_array_node( to_array( slot.ptr()), array_node_size());
                         p->store(node_ptr(), memory_model::memory_order_relaxed);
                     }
                 }
@@ -528,9 +566,9 @@ namespace cds { namespace intrusive {
                 return alloc_array_node(array_node_size(), pParent, idxParent);
             }
 
-            static void free_array_node(array_node * parr)
+            static void free_array_node( array_node * parr, size_t nSize )
             {
-                cxx_array_node_allocator().Delete(parr);
+                cxx_array_node_allocator().Delete( parr, nSize );
             }
 
             union converter {
@@ -595,7 +633,7 @@ namespace cds { namespace intrusive {
                 if (!slot.compare_exchange_strong(cur, cur | flag_array_converting, memory_model::memory_order_release, atomics::memory_order_relaxed))
                 {
                     stats().onExpandNodeFailed();
-                    free_array_node(pArr);
+                    free_array_node( pArr, array_node_size());
                     return false;
                 }