FeldmanHashSet: added checking if a slot can be expanded

[libcds.git] / cds / intrusive / impl / feldman_hashset.h

diff --git a/cds/intrusive/impl/feldman_hashset.h b/cds/intrusive/impl/feldman_hashset.h
index c21646ce2b88c9b230ee5ee59fd28de3adc6db22..68f4c66e205fbd0a44571020df49099d738e860b 100644 (file)
--- a/cds/intrusive/impl/feldman_hashset.h
+++ b/cds/intrusive/impl/feldman_hashset.h
@@ -1,11 +1,11 @@
 /*
     This file is a part of libcds - Concurrent Data Structures library
 
-    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
 
     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:
 
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_INTRUSIVE_IMPL_FELDMAN_HASHSET_H
@@ -145,6 +145,9 @@ namespace cds { namespace intrusive {
         /// Count of hazard pointers required
         static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 2;
 
+        /// The size of 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
         typedef feldman_hashset::level_statistics level_statistics;
 
@@ -562,8 +565,8 @@ namespace cds { namespace intrusive {
     public:
         /// Creates empty set
         /**
-            @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
-            @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
+            @param head_bits - 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
+            @param array_bits - 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
 
             Equation for \p head_bits and \p array_bits:
             \code
@@ -630,16 +633,19 @@ namespace cds { namespace intrusive {
                     // slot value has been changed - retry
                     stats().onSlotChanged();
                 }
-
-                if ( slot.ptr()) {
+                else if ( slot.ptr()) {
                     if ( cmp( hash, hash_accessor()( *slot.ptr())) == 0 ) {
                         // the item with that hash value already exists
                         stats().onInsertFailed();
                         return false;
                     }
 
-                    // the slot must be expanded
-                    base_class::expand_slot( pos, slot );
+                    if ( !pos.splitter.eos() ) {
+                        // the slot must be expanded
+                        base_class::expand_slot( pos, slot );
+                    }
+                    else
+                        return false;
                 }
                 else {
                     // the slot is empty, try to insert data node
@@ -672,7 +678,7 @@ namespace cds { namespace intrusive {
             - If hash value is not found and \p bInsert is \p false then the set is unchanged,
               the function returns <tt> std::pair<false, false> </tt>
 
-            Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull
+            Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful
             (i.e. the item has been inserted or updated),
             \p second is \p true if new item has been added or \p false if the set contains that hash.
         */
@@ -783,16 +789,10 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr extract( hash_type const& hash )
         {
-            guarded_ptr gp;
-            {
-                typename gc::Guard guard;
-                value_type * p = do_erase( hash, guard, []( value_type const&) -> bool {return true;} );
-
-                // p is guarded by HP
-                if ( p )
-                    gp.reset( p );
-            }
-            return gp;
+            typename gc::Guard guard;
+            if ( do_erase( hash, guard, []( value_type const&) -> bool {return true;} ))
+                return guarded_ptr( std::move( guard ));
+            return guarded_ptr();
         }
 
         /// Finds an item by it's \p hash
@@ -862,12 +862,10 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr get( hash_type const& hash )
         {
-            guarded_ptr gp;
-            {
-                typename gc::Guard guard;
-                gp.reset( search( hash, guard ));
-            }
-            return gp;
+            typename gc::Guard guard;
+            if ( search( hash, guard ))
+                return guarded_ptr( std::move( guard ));
+            return guarded_ptr();
         }
 
         /// Clears the set (non-atomic)
@@ -912,7 +910,7 @@ namespace cds { namespace intrusive {
         using base_class::array_node_size;
 
         /// Collects tree level statistics into \p stat
-        /** 
+        /**
             The function traverses the set and collects statistics for each level of the tree
             into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
             represents statistics for level \p i, level 0 is head array.
@@ -1221,8 +1219,12 @@ namespace cds { namespace intrusive {
                     }
 
                     if ( bInsert ) {
-                        // the slot must be expanded
-                        base_class::expand_slot( pos, slot );
+                        if ( !pos.splitter.eos() ) {
+                            // the slot must be expanded
+                            base_class::expand_slot( pos, slot );
+                        }
+                        else
+                            return std::make_pair( false, false );
                     }
                     else {
                         stats().onUpdateFailed();