HP refactoring:

[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 5546546644eade2b9449a28d59e077cfec49d7a7..792dc018aafa508cab67768dca21a6b41df3a2db 100644 (file)
--- a/cds/intrusive/details/feldman_hashset_base.h
+++ b/cds/intrusive/details/feldman_hashset_base.h
@@ -1,4 +1,32 @@
-//$$CDS-header$$
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    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:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
 
 #ifndef CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
 #define CDSLIB_INTRUSIVE_DETAILS_FELDMAN_HASHSET_BASE_H
@@ -272,8 +300,8 @@ namespace cds { namespace intrusive {
 
         //@cond
         namespace details {
-            template <typename HashType, typename UInt = size_t >
-            using hash_splitter = cds::algo::split_bitstring< HashType, UInt >;
+            template <typename HashType >
+            using hash_splitter = cds::algo::split_bitstring< HashType >;
 
             struct metrics {
                 size_t  head_node_size;     // power-of-two
@@ -340,12 +368,13 @@ namespace cds { namespace intrusive {
 
             typedef feldman_hashset::details::hash_splitter< hash_type > hash_splitter;
 
-        protected:
             enum node_flags {
                 flag_array_converting = 1,   ///< the cell is converting from data node to an array node
                 flag_array_node = 2          ///< the cell is a pointer to an array node
             };
 
+        protected:
+
             typedef cds::details::marked_ptr< value_type, 3 > node_ptr;
             typedef atomics::atomic< node_ptr > atomic_node_ptr;
 
@@ -369,17 +398,22 @@ namespace cds { namespace intrusive {
             struct traverse_data {
                 hash_splitter splitter;
                 array_node * pArr;
-                size_t nOffset;
                 size_t nSlot;
                 size_t nHeight;
 
                 traverse_data( hash_type const& hash, multilevel_array& arr )
                     : splitter( hash )
-                    , pArr( arr.head() )
-                    , nOffset( arr.metrics().head_node_size_log )
-                    , nSlot(splitter.cut(arr.metrics().head_node_size_log))
-                    , nHeight( 1 )
-                {}
+                {
+                    reset( arr );
+                }
+
+                void reset( multilevel_array& arr )
+                {
+                    splitter.reset();
+                    pArr = arr.head();
+                    nSlot = splitter.cut( arr.metrics().head_node_size_log );
+                    nHeight = 1;
+                }
             };
 
         protected:
@@ -407,10 +441,10 @@ namespace cds { namespace intrusive {
                     if (slot.bits() == flag_array_node) {
                         // array node, go down the tree
                         assert(slot.ptr() != nullptr);
+                        assert( !pos.splitter.eos());
                         pos.nSlot = pos.splitter.cut( metrics().array_node_size_log );
                         assert( pos.nSlot < metrics().array_node_size );
                         pos.pArr = to_array(slot.ptr());
-                        pos.nOffset += metrics().array_node_size_log;
                         ++pos.nHeight;
                     }
                     else if (slot.bits() == flag_array_converting) {
@@ -545,15 +579,15 @@ namespace cds { namespace intrusive {
 
             bool expand_slot( traverse_data& pos, node_ptr current)
             {
-                return expand_slot( pos.pArr, pos.nSlot, current, pos.nOffset );
+                return expand_slot( pos.pArr, pos.nSlot, current, pos.splitter.bit_offset());
             }
 
+        private:
             bool expand_slot(array_node * pParent, size_t idxParent, node_ptr current, size_t nOffset)
             {
                 assert(current.bits() == 0);
                 assert(current.ptr());
 
-                size_t idx = hash_splitter(hash_accessor()(*current.ptr()), nOffset).cut(m_Metrics.array_node_size_log);
                 array_node * pArr = alloc_array_node(pParent, idxParent);
 
                 node_ptr cur(current.ptr());
@@ -565,6 +599,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
+                size_t idx = hash_splitter( hash_accessor()(*current.ptr()), nOffset ).cut( m_Metrics.array_node_size_log );
                 pArr->nodes[idx].store(current, memory_model::memory_order_release);
 
                 cur = cur | flag_array_converting;
@@ -576,7 +611,6 @@ namespace cds { namespace intrusive {
                 stats().onArrayNodeCreated();
                 return true;
             }
-
         };
         //@endcond
     } // namespace feldman_hashset