From ce8755c5d37c946ae5ed00f8bcaa60e796553a70 Mon Sep 17 00:00:00 2001
From: khizmax <libcds.dev@gmail.com>
Date: Thu, 23 Jul 2015 00:06:53 +0300
Subject: [PATCH] Implemented bit-string splitting for MultiLevelHashSet
---
.../details/multilevel_hashset_base.h | 93 ++++++++++++++++++-
cds/intrusive/impl/multilevel_hashset.h | 2 +
2 files changed, 94 insertions(+), 1 deletion(-)
diff --git a/cds/intrusive/details/multilevel_hashset_base.h b/cds/intrusive/details/multilevel_hashset_base.h
index 2d994782..45fc5102 100644
--- a/cds/intrusive/details/multilevel_hashset_base.h
+++ b/cds/intrusive/details/multilevel_hashset_base.h
@@ -3,7 +3,7 @@
#ifndef CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
#define CDSLIB_INTRUSIVE_DETAILS_MULTILEVEL_HASHSET_BASE_H
-#include <memory.h> // memcmp
+#include <memory.h> // memcmp, memcpy
#include <type_traits>
#include <cds/intrusive/details/base.h>
#include <cds/opt/compare.h>
@@ -216,6 +216,97 @@ namespace cds { namespace intrusive {
}
};
+ //@cond
+ namespace details {
+ template <typename HashType, typename UInt = size_t >
+ class hash_splitter
+ {
+ public:
+ typedef HashType hash_type;
+ typedef UInt uint_type;
+
+ static CDS_CONSTEXPR size_t const c_nHashSize = (sizeof(hash_type) + 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(hash_type) * c_nBitPerByte;
+ static CDS_CONSTEXPR size_t const c_nBitPerInt = sizeof(uint_type) * c_nBitPerByte;
+
+ public:
+ explicit hash_splitter( hash_type const& h )
+ : m_ptr(reinterpret_cast<uint_type const*>( &h ))
+ , m_pos(0)
+# ifdef _DEBUG
+ , m_last( m_ptr + c_nHashSize )
+# endif
+ {}
+
+ explicit operator bool() const
+ {
+ return !eos();
+ }
+
+ // end-of-bitstring
+ bool eos() const
+ {
+ return m_pos >= c_nBitPerHash;
+ }
+
+ uint_type cut( size_t nBits )
+ {
+ assert( !eos() );
+ assert( nBits <= c_nBitPerInt );
+ assert( m_pos + nBits <= c_nBitPerHash );
+# ifdef _DEBUG
+ assert( m_ptr < m_last );
+# endif
+ uint_type result;
+
+ size_t const nRest = c_nBitPerInt - m_pos % c_nBitPerInt;
+ m_pos += nBits;
+ if ( nBits < nRest ) {
+ result = *m_ptr << ( nRest - nBits );
+ result = result >> ( c_nBitPerInt - nBits );
+ }
+ else if ( nBits == nRest ) {
+ result = *m_ptr >> ( c_nBitPerInt - nRest );
+ ++m_ptr;
+ }
+ else {
+ size_t const lsb = *m_ptr >> ( c_nBitPerInt - nRest );
+ nBits -= nRest;
+ ++m_ptr;
+
+ result = *m_ptr << ( c_nBitPerInt - nBits );
+ result = result >> ( c_nBitPerInt - nBits );
+ result = (result << nRest) + lsb;
+ }
+
+ assert( m_pos <= c_nBitPerHash );
+# ifdef _DEBUG
+ assert( m_ptr < m_last );
+# endif
+ return result;
+ }
+
+ uint_type safe_cut( size_t nBits )
+ {
+ assert( !eos() );
+ assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
+
+ if ( m_pos + nBits > c_nBitPerHash )
+ nBits = c_nBitPerHash - m_pos;
+ return nBits ? cut( nBits ) : 0;
+ }
+
+ private:
+ uint_type const* m_ptr; ///< current position in the hash
+ size_t m_pos; ///< current position in bits
+# ifdef _DEBUG
+ uint_type const* m_last;
+# endif
+ };
+ } // namespace details
+ //@endcond
+
} // namespace multilevel_hashset
//@cond
diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h
index 64c41f48..6a11bbe4 100644
--- a/cds/intrusive/impl/multilevel_hashset.h
+++ b/cds/intrusive/impl/multilevel_hashset.h
@@ -130,6 +130,8 @@ namespace cds { namespace intrusive {
typedef cds::details::Allocator< atomic_node_ptr, head_node_allocator > cxx_head_node_allocator;
typedef cds::details::Allocator< atomic_node_ptr, array_node_allocator > cxx_array_node_allocator;
+ typedef multilevel_hashset::details::hash_splitter< hash_type > hash_splitter;
+
struct metrics {
size_t head_node_size; // power-of-two
size_t head_node_size_log; // log2( head_node_size )
--
2.34.1