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