HP refactoring:
authorkhizmax <libcds.dev@gmail.com>
Sat, 20 Aug 2016 20:13:56 +0000 (23:13 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sat, 20 Aug 2016 20:13:56 +0000 (23:13 +0300)
- added move semantics support to guards for reducing HP count
- added move semantics for container's method returning guarded_ptr
- fixed some minor bugs

41 files changed:
cds/algo/split_bitstring.h
cds/container/impl/ellen_bintree_map.h
cds/container/impl/ellen_bintree_set.h
cds/container/impl/feldman_hashmap.h
cds/container/impl/feldman_hashset.h
cds/container/impl/iterable_kvlist.h
cds/container/impl/iterable_list.h
cds/container/impl/lazy_kvlist.h
cds/container/impl/lazy_list.h
cds/container/impl/michael_kvlist.h
cds/container/impl/michael_list.h
cds/container/impl/skip_list_map.h
cds/container/impl/skip_list_set.h
cds/container/split_list_map.h
cds/container/split_list_set.h
cds/gc/details/dhp.h
cds/gc/details/hp.h
cds/gc/details/hp_alloc.h
cds/gc/details/hp_type.h
cds/gc/hp.h
cds/gc/impl/dhp_decl.h
cds/gc/impl/dhp_impl.h
cds/gc/impl/hp_decl.h
cds/gc/impl/hp_impl.h
cds/intrusive/details/feldman_hashset_base.h
cds/intrusive/ellen_bintree_dhp.h
cds/intrusive/ellen_bintree_hp.h
cds/intrusive/impl/ellen_bintree.h
cds/intrusive/impl/feldman_hashset.h
cds/intrusive/impl/iterable_list.h
cds/intrusive/impl/lazy_list.h
cds/intrusive/impl/michael_list.h
cds/intrusive/impl/skip_list.h
cds/intrusive/split_list.h
projects/Win/vc14/stress-set-insdelfind.vcxproj
src/dhp_gc.cpp
src/hp_const.h
src/hp_gc.cpp
test/unit/list/test_intrusive_iterable_list.h
test/unit/set/test_feldman_hashset.h
test/unit/set/test_feldman_hashset_hp.h

index 54407c9..2d49968 100644 (file)
@@ -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_ALGO_SPLIT_BITSTRING_H
@@ -44,7 +44,7 @@ namespace cds { namespace algo {
         The splitter stores a const reference to bit-string, not a copy.
         The maximum count of bits that can be cut in a single call is <tt> sizeof(UInt) * 8 </tt>
     */
-    template <typename BitString, typename UInt = size_t >
+    template <typename BitString, typename UInt = typename std::conditional< sizeof(BitString) % sizeof(size_t) == 0, size_t, unsigned >::type >
     class split_bitstring
     {
     public:
index a5b9855..5c2d5b6 100644 (file)
@@ -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_CONTAINER_IMPL_ELLEN_BINTREE_MAP_H
@@ -370,9 +370,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            base_class::extract_min_( gp.guard() );
-            return gp;
+            return guarded_ptr( base_class::extract_min_());
         }
 
         /// Extracts an item with maximal key from the map
@@ -391,9 +389,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            base_class::extract_max_( gp.guard() );
-            return gp;
+            return guarded_ptr( base_class::extract_max_());
         }
 
         /// Extracts an item from the tree
@@ -409,9 +405,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key );
-            return gp;
+            return guarded_ptr( base_class::extract_( key ));
         }
 
         /// Extracts an item from the map using \p pred for searching
@@ -425,10 +419,8 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            base_class::extract_with_( gp.guard(), key,
-                cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
-            return gp;
+            return guarded_ptr( base_class::extract_with_( key,
+                cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >()));
         }
 
         /// Find the key \p key
@@ -520,9 +512,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::get_( gp.guard(), key );
-            return gp;
+            return guarded_ptr( base_class::get_( key ));
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
@@ -536,10 +526,8 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key,
-                cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
-            return gp;
+            return guarded_ptr( base_class::get_with_( key,
+                cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() ));
         }
 
         /// Clears the map (not atomic)
index 2e00f54..a8631e8 100644 (file)
@@ -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_CONTAINER_IMPL_ELLEN_BINTREE_SET_H
@@ -383,9 +383,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            base_class::extract_min_( gp.guard() );
-            return gp;
+            return guarded_ptr( base_class::extract_min_());
         }
 
         /// Extracts an item with maximal key from the set
@@ -404,9 +402,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            base_class::extract_max_( gp.guard() );
-            return gp;
+            return guarded_ptr( base_class::extract_max_());
         }
 
         /// Extracts an item from the tree
@@ -422,9 +418,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key );
-            return gp;
+            return base_class::extract_( key );
         }
 
         /// Extracts an item from the set using \p pred for searching
@@ -438,10 +432,8 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            base_class::extract_with_( gp.guard(), key,
+            return base_class::extract_with_( key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >());
-            return gp;
         }
 
         /// Find the key \p key
@@ -559,9 +551,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::get_( gp.guard(), key );
-            return gp;
+            return base_class::get_( key );
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
@@ -575,10 +565,8 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED(pred);
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key,
+            return base_class::get_with_( key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() );
-            return gp;
         }
 
         /// Clears the set (not atomic)
index 60d73cf..9c90e89 100644 (file)
@@ -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_CONTAINER_IMPL_FELDMAN_HASHMAP_H
@@ -592,14 +592,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
-            guarded_ptr gp;
-            typename gc::Guard guard;
-            node_type * p = base_class::do_erase( m_Hasher( key_type( key )), guard, []( node_type const&) -> bool {return true;} );
-
-            // p is guarded by HP
-            if ( p )
-                gp.reset( p );
-            return gp;
+            return base_class::extract( m_Hasher( key_type( key )));
         }
 
         /// Checks whether the map contains \p key
@@ -665,12 +658,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
-            guarded_ptr gp;
-            {
-                typename gc::Guard guard;
-                gp.reset( base_class::search( m_Hasher( key_type( key )), guard ));
-            }
-            return gp;
+            return base_class::get( m_Hasher( key_type( key )));
         }
 
         /// Clears the map (non-atomic)
index ee48d47..d90a6a3 100644 (file)
@@ -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_CONTAINER_IMPL_FELDMAN_HASHSET_H
index 55cc358..92ec772 100644 (file)
@@ -691,9 +691,9 @@ namespace cds { namespace container {
             return base_class::erase_at( refHead, key, cmp, f );
         }
         template <typename K, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::extract_at( refHead, guard, key, cmp );
+            return base_class::extract_at( refHead, key, cmp );
         }
 
         template <typename K, typename Compare>
@@ -709,9 +709,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::get_at( refHead, guard, key, cmp );
+            return base_class::get_at( refHead, key, cmp );
         }
 
         //@endcond
index 228e96a..e32f894 100644 (file)
@@ -556,9 +556,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, key_comparator() );
-            return gp;
+            return extract_at( head(), key, key_comparator() );
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -573,9 +571,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list contains \p key
@@ -708,9 +704,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key ) const
         {
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, key_comparator() );
-            return gp;
+            return get_at( head(), key, key_comparator() );
         }
 
         /// Finds \p key and return the item found
@@ -726,9 +720,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q const& key, Less pred ) const
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks if the list is empty
@@ -852,9 +844,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::extract_at( refHead, guard, key, cmp );
+            return base_class::extract_at( refHead, key, cmp );
         }
 
         template <typename Q, typename Compare>
@@ -876,9 +868,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( head_type const& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp ) const
+        guarded_ptr get_at( head_type const& refHead, Q const& key, Compare cmp ) const
         {
-            return base_class::get_at( refHead, guard, key, cmp );
+            return base_class::get_at( refHead, key, cmp );
         }
 
         //@endcond
index 59947bb..5b6599c 100644 (file)
@@ -589,9 +589,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return extract_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -607,9 +605,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list contains \p key
@@ -719,9 +715,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return get_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Finds the key \p val and return the item found
@@ -737,9 +731,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks if the list is empty
@@ -831,9 +823,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::extract_at( &refHead, guard, key, cmp );
+            return base_class::extract_at( &refHead, key, cmp );
         }
 
         template <typename K, typename Func>
@@ -863,9 +855,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::get_at( &refHead, guard, key, cmp );
+            return base_class::get_at( &refHead, key, cmp );
         }
 
         //@endcond
index 496f1b5..0a1615e 100644 (file)
@@ -532,9 +532,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return extract_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -550,9 +548,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list contains \p key
@@ -679,9 +675,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return get_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Finds the key \p key and return the item found
@@ -697,9 +691,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list is empty
@@ -831,9 +823,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::extract_at( &refHead, guard, key, cmp );
+            return base_class::extract_at( &refHead, key, cmp );
         }
 
         template <typename Q, typename Func>
@@ -863,9 +855,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::get_at( &refHead, guard, key, cmp );
+            return base_class::get_at( &refHead, key, cmp );
         }
 
         //@endcond
index 4a5ba37..12a2342 100644 (file)
@@ -592,9 +592,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return extract_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -610,9 +608,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list contains \p key
@@ -723,9 +719,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return get_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Finds the \p key and return the item found
@@ -741,9 +735,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks if the list is empty
@@ -846,9 +838,9 @@ namespace cds { namespace container {
             return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
         }
         template <typename K, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::extract_at( refHead, guard, key, cmp );
+            return base_class::extract_at( refHead, key, cmp );
         }
 
         template <typename K, typename Compare>
@@ -864,9 +856,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )
         {
-            return base_class::get_at( refHead, guard, key, cmp );
+            return base_class::get_at( refHead, key, cmp );
         }
 
         //@endcond
index 97e438a..d631e2d 100644 (file)
@@ -525,9 +525,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return extract_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -543,9 +541,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Checks whether the list contains \p key
@@ -670,9 +666,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return get_at( head(), key, intrusive_key_comparator() );
         }
 
         /// Finds \p key and return the item found
@@ -688,9 +682,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         }
 
         /// Check if the list is empty
@@ -810,9 +802,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::extract_at( refHead, guard, key, cmp );
+            return base_class::extract_at( refHead, key, cmp );
         }
 
         template <typename Q, typename Func>
@@ -842,9 +834,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::get_at( refHead, guard, key, cmp );
+            return base_class::get_at( refHead, key, cmp );
         }
 
         //@endcond
index aedf721..74b98e4 100644 (file)
@@ -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_CONTAINER_IMPL_SKIP_LIST_MAP_H
@@ -466,9 +466,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
-            return gp;
+            return base_class::extract_( key, typename base_class::key_comparator() );
         }
 
         /// Extracts the item from the map with comparing functor \p pred
@@ -485,9 +483,7 @@ namespace cds { namespace container {
         {
             CDS_UNUSED( pred );
             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >  wrapped_less;
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
-            return gp;
+            return base_class::extract_( key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
         }
 
         /// Extracts an item with minimal key from the map
@@ -516,9 +512,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            base_class::extract_min_( gp.guard() );
-            return gp;
+            return base_class::extract_min_();
         }
 
         /// Extracts an item with maximal key from the map
@@ -547,9 +541,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            base_class::extract_max_( gp.guard() );
-            return gp;
+            return base_class::extract_max_();
         }
 
         /// Find the key \p key
@@ -662,9 +654,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
-            return gp;
+            return base_class::get_with_( key, typename base_class::key_comparator() );
         }
 
         /// Finds the key \p key and return the item found
@@ -681,9 +671,7 @@ namespace cds { namespace container {
         {
             CDS_UNUSED( pred );
             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor > wrapped_less;
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
-            return gp;
+            return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >());
         }
 
         /// Clears the map
index ae20895..4221124 100644 (file)
@@ -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_CONTAINER_IMPL_SKIP_LIST_SET_H
@@ -483,9 +483,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key, typename base_class::key_comparator() );
-            return gp;
+            return base_class::extract_( key, typename base_class::key_comparator() );
         }
 
         /// Extracts the item from the set with comparing functor \p pred
@@ -502,9 +500,7 @@ namespace cds { namespace container {
         {
             CDS_UNUSED( pred );
             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
-            return gp;
+            return base_class::extract_( key, cds::opt::details::make_comparator_from_less<wrapped_less>() );
         }
 
         /// Extracts an item with minimal key from the set
@@ -533,9 +529,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            base_class::extract_min_( gp.guard() );
-            return gp;
+            return base_class::extract_min_();
         }
 
         /// Extracts an item with maximal key from the set
@@ -564,9 +558,7 @@ namespace cds { namespace container {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            base_class::extract_max_( gp.guard() );
-            return gp;
+            return base_class::extract_max_();
         }
 
         /// Find the \p key
@@ -700,9 +692,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() );
-            return gp;
+            return base_class::get_with_( key, typename base_class::key_comparator() );
         }
 
         /// Finds \p key and return the item found
@@ -719,9 +709,7 @@ namespace cds { namespace container {
         {
             CDS_UNUSED( pred );
             typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >  wrapped_less;
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >());
-            return gp;
+            return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >());
         }
 
         /// Clears the set (not atomic).
index 57c460d..29cd7fc 100644 (file)
@@ -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_CONTAINER_SPLIT_LIST_MAP_H
@@ -511,9 +511,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
-            guarded_ptr gp;
-            base_class::extract_( gp.guard(), key );
-            return gp;
+            return base_class::extract_( key );
         }
 
         /// Extracts the item using compare functor \p pred
@@ -529,9 +527,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            base_class::extract_with_( gp.guard(), key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
-            return gp;
+            return base_class::extract_with_( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
         }
 
         /// Finds the key \p key
@@ -648,9 +644,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
-            guarded_ptr gp;
-            base_class::get_( gp.guard(), key );
-            return gp;
+            return base_class::get_( key );
         }
 
         /// Finds \p key and return the item found
@@ -666,9 +660,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            base_class::get_with_( gp.guard(), key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
-            return gp;
+            return base_class::get_with_( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>());
         }
 
         /// Clears the map (not atomic)
index e9d44e3..4c48a5d 100644 (file)
@@ -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_CONTAINER_SPLIT_LIST_SET_H
@@ -638,9 +638,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_( gp.guard(), key );
-            return gp;
+            return extract_( key );
         }
 
         /// Extracts the item using compare functor \p pred
@@ -655,9 +653,7 @@ namespace cds { namespace container {
         template <typename Q, typename Less>
         guarded_ptr extract_with( Q const& key, Less pred )
         {
-            guarded_ptr gp;
-            extract_with_( gp.guard(), key, pred );
-            return gp;
+            return extract_with_( key, pred );
         }
 
         /// Finds the key \p key
@@ -791,9 +787,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_( gp.guard(), key );
-            return gp;
+            return get_( key );
         }
 
         /// Finds \p key and return the item found
@@ -808,9 +802,7 @@ namespace cds { namespace container {
         template <typename Q, typename Less>
         guarded_ptr get_with( Q const& key, Less pred )
         {
-            guarded_ptr gp;
-            get_with_( gp.guard(), key, pred );
-            return gp;
+            return get_with_( key, pred );
         }
 
         /// Clears the set (not atomic)
@@ -847,17 +839,17 @@ namespace cds { namespace container {
         using base_class::get_;
 
         template <typename Q, typename Less>
-        bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred )
+        guarded_ptr extract_with_( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper<Less>::type());
+            return base_class::extract_with_( key, typename maker::template predicate_wrapper<Less>::type());
         }
 
         template <typename Q, typename Less>
-        bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred )
+        guarded_ptr get_with_( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            return base_class::get_with_( guard, key, typename maker::template predicate_wrapper<Less>::type());
+            return base_class::get_with_( key, typename maker::template predicate_wrapper<Less>::type());
         }
 
         //@endcond
index 68a3659..f459c21 100644 (file)
@@ -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_GC_DETAILS_DHP_H
@@ -117,13 +117,23 @@ namespace cds { namespace gc {
                 {
                     return pPost.load( atomics::memory_order_acquire ) == nullptr;
                 }
+
+                guarded_ptr get( atomics::memory_order order = atomics::memory_order_acquire )
+                {
+                    return pPost.load( order );
+                }
+
+                void set( guarded_ptr p, atomics::memory_order order = atomics::memory_order_release )
+                {
+                    pPost.store( p, order );
+                }
             };
 
             /// Guard allocator
             template <class Alloc = CDS_DEFAULT_ALLOCATOR>
             class guard_allocator
             {
-                cds::details::Allocator<details::guard_data>  m_GuardAllocator    ;   ///< guard allocator
+                cds::details::Allocator<details::guard_data>  m_GuardAllocator;   ///< guard allocator
 
                 atomics::atomic<guard_data *>  m_GuardList;     ///< Head of allocated guard list (linked by guard_data::pGlobalNext field)
                 atomics::atomic<guard_data *>  m_FreeGuardList; ///< Head of free guard list (linked by guard_data::pNextFree field)
@@ -174,7 +184,7 @@ namespace cds { namespace gc {
                 }
 
                 /// Allocates a guard from free list or from heap if free list is empty
-                guard_data * alloc()
+                guard_data* alloc()
                 {
                     // Try to pop a guard from free-list
                     details::guard_data * pGuard;
@@ -196,7 +206,7 @@ namespace cds { namespace gc {
                 /**
                     The function places the guard \p pGuard into free-list
                 */
-                void free( guard_data * pGuard ) CDS_NOEXCEPT
+                void free( guard_data* pGuard ) CDS_NOEXCEPT
                 {
                     pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
 
@@ -329,9 +339,7 @@ namespace cds { namespace gc {
                     // Item counter is needed only as a threshold for \p scan() function
                     // So, we may clear the item counter without synchronization with m_pHead
                     res.second = m_nItemCount.exchange( 0, atomics::memory_order_relaxed );
-
                     res.first = m_pHead.exchange( nullptr, atomics::memory_order_acq_rel );
-
                     return res;
                 }
 
@@ -509,208 +517,8 @@ namespace cds { namespace gc {
                     } while ( !m_pEpochFree[nEpoch].compare_exchange_weak( pCurHead, pHead, atomics::memory_order_release, atomics::memory_order_relaxed ));
                 }
             };
-
-            /// Uninitialized guard
-            class guard
-            {
-                friend class dhp::ThreadGC;
-            protected:
-                details::guard_data * m_pGuard ;    ///< Pointer to guard data
-
-            public:
-                /// Initialize empty guard.
-                CDS_CONSTEXPR guard() CDS_NOEXCEPT
-                    : m_pGuard( nullptr )
-                {}
-
-                /// Copy-ctor is disabled
-                guard( guard const& ) = delete;
-
-                /// Move-ctor is disabled
-                guard( guard&& ) = delete;
-
-                /// Object destructor, does nothing
-                ~guard() CDS_NOEXCEPT
-                {}
-
-                /// Get current guarded pointer
-                void * get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
-                {
-                    assert( m_pGuard != nullptr );
-                    return m_pGuard->pPost.load( order );
-                }
-
-                /// Guards pointer \p p
-                void set( void * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
-                {
-                    assert( m_pGuard != nullptr );
-                    m_pGuard->pPost.store( p, order );
-                }
-
-                /// Clears the guard
-                void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT
-                {
-                    assert( m_pGuard != nullptr );
-                    m_pGuard->pPost.store( nullptr, order );
-                }
-
-                /// Guards pointer \p p
-                template <typename T>
-                T * operator =(T * p) CDS_NOEXCEPT
-                {
-                    set( reinterpret_cast<void *>( const_cast<T *>(p) ));
-                    return p;
-                }
-
-                std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
-                {
-                    clear();
-                    return nullptr;
-                }
-
-            public: // for ThreadGC.
-                /*
-                    GCC cannot compile code for template versions of ThreadGC::allocGuard/freeGuard,
-                    the compiler produces error: 'cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard' is protected
-                    despite the fact that ThreadGC is declared as friend for guard class.
-                    Therefore, we have to add set_guard/get_guard public functions
-                */
-                /// Set guard data
-                void set_guard( details::guard_data * pGuard ) CDS_NOEXCEPT
-                {
-                    assert( m_pGuard == nullptr );
-                    m_pGuard = pGuard;
-                }
-
-                /// Get current guard data
-                details::guard_data * get_guard() CDS_NOEXCEPT
-                {
-                    return m_pGuard;
-                }
-                /// Get current guard data
-                details::guard_data * get_guard() const CDS_NOEXCEPT
-                {
-                    return m_pGuard;
-                }
-
-                details::guard_data * release_guard() CDS_NOEXCEPT
-                {
-                    details::guard_data * p = m_pGuard;
-                    m_pGuard = nullptr;
-                    return p;
-                }
-
-                bool is_initialized() const
-                {
-                    return m_pGuard != nullptr;
-                }
-            };
-
         } // namespace details
 
-        /// Guard
-        /**
-            This class represents auto guard: ctor allocates a guard from guard pool,
-            dtor returns the guard back to the pool of free guard.
-        */
-        class Guard: public details::guard
-        {
-            typedef details::guard    base_class;
-            friend class ThreadGC;
-        public:
-            /// Allocates a guard from \p gc GC. \p gc must be ThreadGC object of current thread
-            Guard(); // inline in dhp_impl.h
-
-            /// Returns guard allocated back to pool of free guards
-            ~Guard();    // inline in dhp_impl.h
-
-            /// Guards pointer \p p
-            template <typename T>
-            T * operator =(T * p) CDS_NOEXCEPT
-            {
-                return base_class::operator =<T>( p );
-            }
-
-            std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
-            {
-                return base_class::operator =(nullptr);
-            }
-        };
-
-        /// Array of guards
-        /**
-            This class represents array of auto guards: ctor allocates \p Count guards from guard pool,
-            dtor returns the guards allocated back to the pool.
-        */
-        template <size_t Count>
-        class GuardArray
-        {
-            details::guard      m_arr[Count]    ;    ///< array of guard
-            const static size_t c_nCapacity = Count ;   ///< Array capacity (equal to \p Count template parameter)
-
-        public:
-            /// Rebind array for other size \p OtherCount
-            template <size_t OtherCount>
-            struct rebind {
-                typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
-            };
-
-        public:
-            /// Allocates array of guards from \p gc which must be the ThreadGC object of current thread
-            GuardArray();    // inline in dhp_impl.h
-
-            /// The object is not copy-constructible
-            GuardArray( GuardArray const& ) = delete;
-
-            /// The object is not move-constructible
-            GuardArray( GuardArray&& ) = delete;
-
-            /// Returns guards allocated back to pool
-            ~GuardArray();    // inline in dh_impl.h
-
-            /// Returns the capacity of array
-            CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
-            {
-                return c_nCapacity;
-            }
-
-            /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count)
-            details::guard& operator []( size_t nIndex ) CDS_NOEXCEPT
-            {
-                assert( nIndex < capacity() );
-                return m_arr[nIndex];
-            }
-
-            /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
-            const details::guard& operator []( size_t nIndex ) const CDS_NOEXCEPT
-            {
-                assert( nIndex < capacity() );
-                return m_arr[nIndex];
-            }
-
-            /// Set the guard \p nIndex. 0 <= \p nIndex < \p Count
-            template <typename T>
-            void set( size_t nIndex, T * p ) CDS_NOEXCEPT
-            {
-                assert( nIndex < capacity() );
-                m_arr[nIndex].set( p );
-            }
-
-            /// Clears (sets to \p nullptr) the guard \p nIndex
-            void clear( size_t nIndex ) CDS_NOEXCEPT
-            {
-                assert( nIndex < capacity() );
-                m_arr[nIndex].clear();
-            }
-
-            /// Clears all guards in the array
-            void clearAll() CDS_NOEXCEPT
-            {
-                for ( size_t i = 0; i < capacity(); ++i )
-                    clear(i);
-            }
-        };
-
         /// Memory manager (Garbage collector)
         class CDS_EXPORT_API GarbageCollector
         {
@@ -845,7 +653,7 @@ namespace cds { namespace gc {
             }
 
             /// Allocates guard list for a thread.
-            details::guard_data * allocGuardList( size_t nCount )
+            details::guard_data* allocGuardList( size_t nCount )
             {
                 return m_GuardPool.allocList( nCount );
             }
@@ -921,9 +729,9 @@ namespace cds { namespace gc {
         */
         class ThreadGC
         {
-            GarbageCollector&   m_gc    ;   ///< reference to GC singleton
-            details::guard_data *    m_pList ;   ///< Local list of guards owned by the thread
-            details::guard_data *    m_pFree ;   ///< The list of free guard from m_pList
+            GarbageCollector&        m_gc;      ///< reference to GC singleton
+            details::guard_data *    m_pList;   ///< Local list of guards owned by the thread
+            details::guard_data *    m_pFree;   ///< The list of free guard from m_pList
 
         public:
             /// Default constructor
@@ -962,72 +770,84 @@ namespace cds { namespace gc {
             }
 
         public:
-            /// Initializes guard \p g
-            void allocGuard( dhp::details::guard& g )
+            /// Allocates new guard
+            dhp::details::guard_data* allocGuard()
             {
                 assert( m_pList != nullptr );
-                if ( !g.m_pGuard ) {
-                    if ( m_pFree ) {
-                        g.m_pGuard = m_pFree;
-                        m_pFree = m_pFree->pNextFree.load( atomics::memory_order_relaxed );
-                    }
-                    else {
-                        g.m_pGuard = m_gc.allocGuard();
-                        g.m_pGuard->pThreadNext = m_pList;
-                        m_pList = g.m_pGuard;
-                    }
+
+                dhp::details::guard_data* ret;
+                if ( cds_likely( m_pFree )) {
+                    ret = m_pFree;
+                    m_pFree = m_pFree->pNextFree.load( atomics::memory_order_relaxed );
+                }
+                else {
+                    ret = m_gc.allocGuard();
+                    ret->pThreadNext = m_pList;
+                    m_pList = ret;
                 }
+                return ret;
             }
 
             /// Frees guard \p g
-            void freeGuard( dhp::details::guard& g )
+            void freeGuard( dhp::details::guard_data* g )
             {
                 assert( m_pList != nullptr );
-                if ( g.m_pGuard ) {
-                    g.m_pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
-                    g.m_pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
-                    m_pFree = g.m_pGuard;
-                    g.m_pGuard = nullptr;
+                if ( cds_likely( g )) {
+                    g->pPost.store( nullptr, atomics::memory_order_relaxed );
+                    g->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
+                    m_pFree = g;
                 }
             }
 
+            /// Guard array
+            template <size_t Count>
+            using guard_array = dhp::details::guard_data* [Count];
+
             /// Initializes guard array \p arr
             template <size_t Count>
-            void allocGuard( GuardArray<Count>& arr )
+            void allocGuard( guard_array<Count>& arr )
             {
                 assert( m_pList != nullptr );
                 size_t nCount = 0;
 
                 while ( m_pFree && nCount < Count ) {
-                    arr[nCount].set_guard( m_pFree );
+                    arr[nCount] = m_pFree;
                     m_pFree = m_pFree->pNextFree.load(atomics::memory_order_relaxed);
                     ++nCount;
                 }
 
                 while ( nCount < Count ) {
-                    details::guard& g = arr[nCount++];
-                    g.set_guard( m_gc.allocGuard() );
-                    g.get_guard()->pThreadNext = m_pList;
-                    m_pList = g.get_guard();
+                    dhp::details::guard_data*& g = arr[nCount];
+                    g = m_gc.allocGuard();
+                    g->pThreadNext = m_pList;
+                    m_pList = g;
+                    ++nCount;
                 }
             }
 
             /// Frees guard array \p arr
             template <size_t Count>
-            void freeGuard( GuardArray<Count>& arr )
+            void freeGuard( guard_array<Count>& arr )
             {
                 assert( m_pList != nullptr );
 
-                details::guard_data * pGuard;
-                for ( size_t i = 0; i < Count - 1; ++i ) {
-                    pGuard = arr[i].get_guard();
-                    pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
-                    pGuard->pNextFree.store( arr[i+1].get_guard(), atomics::memory_order_relaxed );
+                details::guard_data* first = nullptr;
+                details::guard_data* last;
+                for ( size_t i = 0; i < Count; ++i ) {
+                    details::guard_data* guard = arr[i];
+                    if ( cds_likely( guard )) {
+                        guard->pPost.store( nullptr, atomics::memory_order_relaxed );
+                        if ( first )
+                            last->pNextFree.store( guard, atomics::memory_order_relaxed );
+                        else
+                            first = guard;
+                        last = guard;
+                    }
+                }
+                if ( first ) {
+                    last->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
+                    m_pFree = first;
                 }
-                pGuard = arr[Count-1].get_guard();
-                pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
-                pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
-                m_pFree = arr[0].get_guard();
             }
 
             /// Places retired pointer \p and its deleter \p pFunc into list of retired pointer for deferred reclamation
index ffc5744..1bcfd43 100644 (file)
@@ -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_GC_DETAILS_HP_H
@@ -182,9 +182,10 @@ namespace cds {
 
                 char padding[cds::c_nCacheLineSize];
                 atomics::atomic<unsigned int> m_nSync; ///< dummy var to introduce synchronizes-with relationship between threads
+                char padding2[cds::c_nCacheLineSize];
 
                 /// Ctor
-                hp_record( const cds::gc::hp::GarbageCollector& HzpMgr );    // inline
+                hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
                 ~hp_record()
                 {}
 
@@ -261,13 +262,13 @@ namespace cds {
                 //@endcond
             };
 
-            /// Not enough required Hazard Pointer count
+            /// Not enough Hazard Pointer
             class too_many_hazard_ptr : public std::length_error
             {
             public:
                 //@cond
                 too_many_hazard_ptr()
-                    : std::length_error( "Not enough required Hazard Pointer count" )
+                    : std::length_error( "Not enough Hazard Pointer" )
                 {}
                 //@endcond
             };
@@ -461,10 +462,10 @@ namespace cds {
         public:    // Internals for threads
 
             /// Allocates Hazard Pointer GC record. For internal use only
-            details::hp_record * alloc_hp_record();
+            details::hp_record* alloc_hp_record();
 
             /// Free HP record. For internal use only
-            void free_hp_record( details::hp_record * pRec );
+            void free_hp_record( details::hp_record* pRec );
 
             /// The main garbage collecting function
             /**
@@ -546,8 +547,8 @@ namespace cds {
         */
         class ThreadGC
         {
-            GarbageCollector&    m_HzpManager; ///< Hazard Pointer GC singleton
-            details::hp_record * m_pHzpRec;    ///< Pointer to thread's HZP record
+            GarbageCollector&   m_HzpManager; ///< Hazard Pointer GC singleton
+            details::hp_record* m_pHzpRec;    ///< Pointer to thread's HZP record
 
         public:
             /// Default constructor
@@ -565,7 +566,7 @@ namespace cds {
             }
 
             /// Checks if thread GC is initialized
-            bool    isInitialized() const   { return m_pHzpRec != nullptr; }
+            bool isInitialized() const   { return m_pHzpRec != nullptr; }
 
             /// Initialization. Repeat call is available
             void init()
@@ -578,21 +579,21 @@ namespace cds {
             void fini()
             {
                 if ( m_pHzpRec ) {
-                    details::hp_record * pRec = m_pHzpRec;
+                    details::hp_record* pRec = m_pHzpRec;
                     m_pHzpRec = nullptr;
                     m_HzpManager.free_hp_record( pRec );
                 }
             }
 
             /// Initializes HP guard \p guard
-            details::hp_guard& allocGuard()
+            details::hp_guard* allocGuard()
             {
                 assert( m_pHzpRec );
                 return m_pHzpRec->m_hzp.alloc();
             }
 
             /// Frees HP guard \p guard
-            void freeGuard( details::hp_guard& guard )
+            void freeGuard( details::hp_guard* guard )
             {
                 assert( m_pHzpRec );
                 m_pHzpRec->m_hzp.free( guard );
@@ -600,10 +601,10 @@ namespace cds {
 
             /// Initializes HP guard array \p arr
             template <size_t Count>
-            void allocGuard( details::hp_array<Count>& arr )
+            size_t allocGuard( details::hp_array<Count>& arr )
             {
                 assert( m_pHzpRec );
-                m_pHzpRec->m_hzp.alloc( arr );
+                return m_pHzpRec->m_hzp.alloc( arr );
             }
 
             /// Frees HP guard array \p arr
@@ -618,21 +619,6 @@ namespace cds {
             template <typename T>
             void retirePtr( T * p, void (* pFunc)(T *) )
             {
-                /*
-                union {
-                    T * p;
-                    hazard_pointer hp;
-                } cast_ptr;
-                cast_ptr.p = p;
-
-                union{
-                    void( *pFunc )(T *);
-                    free_retired_ptr_func hpFunc;
-                } cast_func;
-                cast_func.pFunc = pFunc;
-
-                retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
-                */
                 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
             }
 
@@ -661,74 +647,6 @@ namespace cds {
             }
         };
 
-        /// Auto hp_guard.
-        /**
-            This class encapsulates Hazard Pointer guard to protect a pointer against deletion.
-            It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated
-            in destructor.
-        */
-        class guard
-        {
-            details::hp_guard&  m_hp    ; ///< Hazard pointer guarded
-
-        public:
-            typedef details::hp_guard::hazard_ptr hazard_ptr ;  ///< Hazard pointer type
-
-        public:
-            /// Allocates HP guard
-            guard(); // inline in hp_impl.h
-
-            /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
-            template <typename T>
-            explicit guard( T * p ); // inline in hp_impl.h
-
-            /// Frees HP guard. The pointer guarded may be deleted after this.
-            ~guard(); // inline in hp_impl.h
-
-            /// Protects the pointer \p p against reclamation (guards the pointer).
-            template <typename T>
-            T * operator =( T * p )
-            {
-                return m_hp = p;
-            }
-
-            //@cond
-            std::nullptr_t operator =(std::nullptr_t)
-            {
-                return m_hp = nullptr;
-            }
-            //@endcond
-
-            /// Get raw guarded pointer
-            hazard_ptr get() const
-            {
-                return m_hp;
-            }
-        };
-
-        /// Auto-managed array of hazard pointers
-        /**
-            This class is wrapper around cds::gc::hp::details::hp_array class.
-            \p Count is the size of HP array
-        */
-        template <size_t Count>
-        class array : public details::hp_array<Count>
-        {
-        public:
-            /// Rebind array for other size \p COUNT2
-            template <size_t Count2>
-            struct rebind {
-                typedef array<Count2>  other;   ///< rebinding result
-            };
-
-        public:
-            /// Allocates array of HP guard
-            array(); // inline in hp_impl.h
-
-            /// Frees array of HP guard
-            ~array(); //inline in hp_impl.h
-        };
-
     }   // namespace hp
 }}  // namespace cds::gc
 //@endcond
index 5da3052..d6d42a5 100644 (file)
@@ -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_GC_DETAILS_HP_ALLOC_H
@@ -52,18 +52,23 @@ namespace cds {
         */
         class hp_guard : protected atomics::atomic < hazard_pointer >
         {
+            template <class Allocator> friend class hp_allocator;
+
         public:
-            typedef hazard_pointer   hazard_ptr;    ///< Hazard pointer type
+            typedef hazard_pointer hazard_ptr;///< Hazard pointer type
+
         private:
-            typedef atomics::atomic<hazard_ptr>  base_class;
+            typedef atomics::atomic<hazard_ptr> atomic_hazard_ptr;
 
-        protected:
-            template <class Allocator> friend class hp_allocator;
+            atomic_hazard_ptr m_hp;
+            hp_guard*         m_next; // next free guard
 
         public:
             hp_guard() CDS_NOEXCEPT
-                : base_class( nullptr )
+                : m_hp( nullptr )
+                , m_next( nullptr )
             {}
+
             ~hp_guard() CDS_NOEXCEPT
             {}
 
@@ -85,28 +90,19 @@ namespace cds {
                 return nullptr;
             }
 
-            /// Returns current value of hazard pointer
-            /**
-                Loading has acquire semantics
-            */
-            operator hazard_ptr() const CDS_NOEXCEPT
-            {
-                return get();
-            }
-
             /// Returns current value of hazard pointer
             /**
                 Loading has acquire semantics
             */
             hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
             {
-                return base_class::load( order );
+                return m_hp.load( order );
             }
 
             template <typename T>
             void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
             {
-                base_class::store( reinterpret_cast<hazard_ptr>(p), order );
+                m_hp.store( reinterpret_cast<hazard_ptr>(p), order );
             }
 
             /// Clears HP
@@ -116,7 +112,7 @@ namespace cds {
             void clear( atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
             {
                 // memory order is not necessary here
-                base_class::store( nullptr, order );
+                m_hp.store( nullptr, order );
             }
         };
 
@@ -137,24 +133,22 @@ namespace cds {
 
             Template parameter:
                 \li Count - capacity of array
-
         */
         template <size_t Count>
         class hp_array
         {
+            template <class Allocator> friend class hp_allocator;
+
         public:
-            typedef hazard_pointer  hazard_ptr_type;   ///< Hazard pointer type
-            typedef hp_guard        atomic_hazard_ptr; ///< Element type of the array
+            typedef hazard_pointer  hazard_ptr;   ///< Hazard pointer type
             static CDS_CONSTEXPR const size_t c_nCapacity = Count ;   ///< Capacity of the array
 
-        private:
-            atomic_hazard_ptr *     m_arr               ;   ///< Hazard pointer array of size = \p Count
-            template <class Allocator> friend class hp_allocator;
-
         public:
             /// Constructs uninitialized array.
             hp_array() CDS_NOEXCEPT
-            {}
+            {
+                memset( m_arr, 0, sizeof( m_arr ));
+            }
 
             /// Destructs object
             ~hp_array() CDS_NOEXCEPT
@@ -167,32 +161,49 @@ namespace cds {
             }
 
             /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
-            void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT
+            void set( size_t nIndex, hazard_ptr hptr ) CDS_NOEXCEPT
             {
-                assert( nIndex < capacity() );
-                m_arr[nIndex] = hzPtr;
+                assert( nIndex < capacity());
+                assert( m_arr[nIndex] != nullptr );
+
+                *m_arr[nIndex] = hptr;
             }
 
-            /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
-            atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT
+            /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
+            hp_guard* operator []( size_t nIndex ) CDS_NOEXCEPT
             {
-                assert( nIndex < capacity() );
+                assert( nIndex < capacity());
                 return m_arr[nIndex];
             }
 
-            /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
-            atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT
+            /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
+            hp_guard* operator []( size_t nIndex ) const CDS_NOEXCEPT
             {
-                assert( nIndex < capacity() );
+                assert( nIndex < capacity());
                 return m_arr[nIndex];
             }
 
             /// Clears (sets to \p nullptr) hazard pointer \p nIndex
             void clear( size_t nIndex ) CDS_NOEXCEPT
+            {
+                assert( nIndex < capacity());
+                assert( m_arr[nIndex] != nullptr );
+
+                m_arr[ nIndex ]->clear();
+            }
+
+            hp_guard* release( size_t nIndex ) CDS_NOEXCEPT
             {
                 assert( nIndex < capacity() );
-                m_arr[ nIndex ].clear();
+
+                hp_guard* p = m_arr[ nIndex ];
+                m_arr[ nIndex ] = nullptr;
+                return p;
             }
+
+
+        private:
+            hp_guard* m_arr[c_nCapacity]; ///< Hazard pointer array of size = \p Count
         };
 
         /// Allocator of hazard pointers for the thread
@@ -212,26 +223,26 @@ namespace cds {
         class hp_allocator
         {
         public:
-            typedef hazard_pointer  hazard_ptr_type;    ///< type of hazard pointer
-            typedef hp_guard        atomic_hazard_ptr;  ///< Atomic hazard pointer type
-            typedef Allocator       allocator_type;     ///< allocator type
+            typedef hazard_pointer  hazard_ptr;     ///< type of hazard pointer
+            typedef Allocator       allocator_type; ///< allocator type
 
         private:
-            typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
+            typedef cds::details::Allocator< hp_guard, allocator_type > allocator_impl;
 
-            atomic_hazard_ptr * m_arrHazardPtr  ;   ///< Array of hazard pointers
-            size_t              m_nTop          ;   ///< The top of stack
-            const size_t        m_nCapacity     ;   ///< Array capacity
+            hp_guard*    m_arrHazardPtr; ///< Array of hazard pointers
+            hp_guard*    m_FreeListHead; ///< List of free hp guards
+            size_t const m_nCapacity;    ///< Array capacity
 
         public:
             /// Default ctor
             explicit hp_allocator(
-                size_t  nCapacity            ///< max count of hazard pointer per thread
-                )
-                : m_arrHazardPtr( alloc_array( nCapacity ) )
-                , m_nCapacity( nCapacity )
+                size_t  nCapacity ///< max count of hazard pointer per thread
+            )
+            : m_arrHazardPtr( alloc_array( nCapacity ))
+            , m_FreeListHead( m_arrHazardPtr )
+            , m_nCapacity( nCapacity )
             {
-                make_free();
+                build_free_list();
             }
 
             /// Dtor
@@ -253,38 +264,52 @@ namespace cds {
             }
 
             /// Checks if all items are allocated
-            bool isFull() const CDS_NOEXCEPT
+            bool full() const CDS_NOEXCEPT
             {
-                return m_nTop == 0;
+                return m_FreeListHead == nullptr;
             }
 
             /// Allocates hazard pointer
-            atomic_hazard_ptr& alloc()
+            hp_guard* alloc()
             {
-                assert( m_nTop > 0 );
-                --m_nTop;
-                return m_arrHazardPtr[m_nTop];
+                assert( !full());
+
+                hp_guard* p = m_FreeListHead;
+                m_FreeListHead = m_FreeListHead->m_next;
+                return p;
             }
 
             /// Frees previously allocated hazard pointer
-            void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
+            void free( hp_guard* hp ) CDS_NOEXCEPT
             {
-                assert( m_nTop < capacity() );
-                hp.clear();
-                ++m_nTop;
+                if ( hp ) {
+                    hp->clear();
+                    hp->m_next = m_FreeListHead;
+                    m_FreeListHead = hp;
+                }
             }
 
             /// Allocates hazard pointers array
             /**
                 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
-                Returns initialized object \p arr
+                Initializes \p arr with hazard pointers.
+
+                @return actual size of allocated array.
             */
             template <size_t Count>
-            void alloc( hp_array<Count>& arr )
+            size_t alloc( hp_array<Count>& arr )
             {
-                assert( m_nTop >= Count );
-                m_nTop -= Count;
-                arr.m_arr = m_arrHazardPtr + m_nTop;
+                size_t i;
+                hp_guard* p = m_FreeListHead;
+                for ( i = 0; i < Count && p; ++i ) {
+                    arr.m_arr[i] = p;
+                    p = p->m_next;
+                }
+                size_t ret = i;
+                for ( ; i < Count; ++i )
+                    arr.m_arr[i] = nullptr;
+                m_FreeListHead = p;
+                return ret;
             }
 
             /// Frees hazard pointer array
@@ -294,38 +319,49 @@ namespace cds {
             template <size_t Count>
             void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
             {
-                CDS_UNUSED( arr );
-
-                assert( m_nTop + Count <= capacity());
-                for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
-                    m_arrHazardPtr[i].clear();
-                m_nTop += Count;
+                hp_guard* pList = m_FreeListHead;
+                for ( size_t i = 0; i < Count; ++i ) {
+                    hp_guard* p = arr[i];
+                    if ( p ) {
+                        p->clear();
+                        p->m_next = pList;
+                        pList = p;
+                    }
+                }
+                m_FreeListHead = pList;
             }
 
             /// Makes all HP free
             void clear() CDS_NOEXCEPT
             {
-                make_free();
+                for ( size_t i = 0; i < capacity(); ++i )
+                    m_arrHazardPtr[i].clear();
             }
 
-            /// Returns to i-th hazard pointer
-            atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
+            /// Returns i-th hazard pointer
+            hp_guard& operator []( size_t i ) CDS_NOEXCEPT
             {
                 assert( i < capacity() );
                 return m_arrHazardPtr[i];
             }
 
         private:
-            void make_free() CDS_NOEXCEPT
+            hp_guard* alloc_array( size_t nCapacity )
             {
-                for ( size_t i = 0; i < capacity(); ++i )
-                    m_arrHazardPtr[i].clear();
-                m_nTop = capacity();
+                return allocator_impl().NewArray( nCapacity );
             }
 
-            atomic_hazard_ptr * alloc_array( size_t nCapacity )
+            void build_free_list()
             {
-                return allocator_impl().NewArray( nCapacity );
+                hp_guard* first = m_arrHazardPtr;
+                hp_guard* last = m_arrHazardPtr + capacity();
+                hp_guard* prev = first;
+                for ( ++first; first < last; ++first ) {
+                    prev->m_next = first;
+                    prev = first;
+                }
+                prev->m_next = nullptr;
+                m_FreeListHead = m_arrHazardPtr;
             }
         };
 
index a3a41dd..21c3115 100644 (file)
@@ -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_GC_DETAILS_HP_TYPE_H
index 901cf22..bcbc3a7 100644 (file)
@@ -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_GC_HP_H
index b2b6e77..128c884 100644 (file)
@@ -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_GC_IMPL_DHP_DECL_H
@@ -119,8 +119,8 @@ namespace cds { namespace gc {
 
         public: // for internal use only!!!
             //@cond
-            static void alloc_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
-            static void free_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
+            static dhp::details::guard_data* alloc_guard(); // inline in dhp_impl.h
+            static void free_guard( dhp::details::guard_data* g ); // inline in dhp_impl.h
             //@endcond
         };
 
@@ -132,31 +132,80 @@ namespace cds { namespace gc {
             A guard is the hazard pointer.
             Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
 
-            A \p %Guard object is not copy- and move-constructible
-            and not copy- and move-assignable.
-        */
-        class Guard: public dhp::Guard
-        {
-            //@cond
-            typedef dhp::Guard base_class;
-            //@endcond
+            \p %Guard object is movable but not copyable.
 
-        public: // for internal use only
-            //@cond
-            typedef cds::gc::dhp::details::guard native_guard;
-            //@endcond
+            The guard object can be in two states:
+            - unlinked - the guard is not linked with any internal hazard pointer.
+              In this state no operation except \p link() and move assignment is supported.
+            - linked (default) - the guard allocates an internal hazard pointer and fully operable.
 
+            Due to performance reason the implementation does not check state of the guard in runtime.
+
+            @warning Move assignment can transfer the guard in unlinked state, use with care.
+        */
+        class Guard
+        {
         public:
-            // Default ctor
-            Guard()
+            /// Default ctor allocates a guard (hazard pointer) from thread-private storage
+            Guard() CDS_NOEXCEPT
+                : m_guard( thread_gc::alloc_guard())
             {}
 
-            //@cond
+            /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
+            explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
+                : m_guard( nullptr )
+            {}
+
+            /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
+            Guard( Guard&& src ) CDS_NOEXCEPT
+                : m_guard( src.m_guard )
+            {
+                src.m_guard = nullptr;
+            }
+
+            /// Move assignment: the internal guards are swapped between \p src and \p this
+            /**
+                @warning \p src will become in unlinked state if \p this was unlinked on entry.
+            */
+            Guard& operator=( Guard&& src ) CDS_NOEXCEPT
+            {
+                std::swap( m_guard, src.m_guard );
+                return *this;
+            }
+
+            /// Copy ctor is prohibited - the guard is not copyable
             Guard( Guard const& ) = delete;
-            Guard( Guard&& s ) = delete;
-            Guard& operator=(Guard const&) = delete;
-            Guard& operator=(Guard&&) = delete;
-            //@endcond
+
+            /// Copy assignment is prohibited
+            Guard& operator=( Guard const& ) = delete;
+
+            ~Guard()
+            {
+                if ( m_guard )
+                    thread_gc::free_guard( m_guard );
+            }
+
+            /// Checks if the guard object linked with any internal hazard pointer
+            bool is_linked() const
+            {
+                return m_guard != nullptr;
+            }
+
+            /// Links the guard with internal hazard pointer if the guard is in unlinked state
+            void link()
+            {
+                if ( !m_guard )
+                    m_guard = thread_gc::alloc_guard();
+            }
+
+            /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
+            void unlink()
+            {
+                if ( m_guard ) {
+                    thread_gc::free_guard( m_guard );
+                    m_guard = nullptr;
+                }
+            }
 
             /// Protects a pointer of type <tt> atomic<T*> </tt>
             /**
@@ -214,15 +263,18 @@ namespace cds { namespace gc {
                 or for already guarded pointer.
             */
             template <typename T>
-            T * assign( T * p )
+            T* assign( T* p )
             {
-                return base_class::operator =(p);
+                assert( m_guard != nullptr );
+                m_guard->pPost.store( p, atomics::memory_order_release );
+                return p;
             }
 
             //@cond
             std::nullptr_t assign( std::nullptr_t )
             {
-                return base_class::operator =(nullptr);
+                clear();
+                return nullptr;
             }
             //@endcond
 
@@ -233,9 +285,9 @@ namespace cds { namespace gc {
                 or for already guarded pointer.
             */
             template <typename T, int BITMASK>
-            T * assign( cds::details::marked_ptr<T, BITMASK> p )
+            T* assign( cds::details::marked_ptr<T, BITMASK> p )
             {
-                return base_class::operator =( p.ptr() );
+                return assign( p.ptr() );
             }
 
             /// Copy from \p src guard to \p this guard
@@ -247,7 +299,8 @@ namespace cds { namespace gc {
             /// Clears value of the guard
             void clear()
             {
-                base_class::clear();
+                assert( m_guard != nullptr );
+                m_guard->pPost.store( nullptr, atomics::memory_order_release );
             }
 
             /// Gets the value currently protected (relaxed read)
@@ -258,10 +311,25 @@ namespace cds { namespace gc {
             }
 
             /// Gets native guarded pointer stored
-            guarded_pointer get_native() const
+            void* get_native() const
             {
-                return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
+                assert( m_guard != nullptr );
+                return m_guard->pPost.load( atomics::memory_order_acquire );
             }
+
+            //@cond
+            dhp::details::guard_data* release()
+            {
+                dhp::details::guard_data* g = m_guard;
+                m_guard = nullptr;
+                return g;
+            }
+            //@endcond
+
+        private:
+            //@cond
+            dhp::details::guard_data* m_guard;
+            //@endcond
         };
 
         /// Array of Dynamic Hazard Pointer guards
@@ -274,11 +342,8 @@ namespace cds { namespace gc {
             and not copy- and move-assignable.
         */
         template <size_t Count>
-        class GuardArray: public dhp::GuardArray<Count>
+        class GuardArray
         {
-            //@cond
-            typedef dhp::GuardArray<Count> base_class;
-            //@endcond
         public:
             /// Rebind array for other size \p OtherCount
             template <size_t OtherCount>
@@ -286,17 +351,27 @@ namespace cds { namespace gc {
                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
             };
 
+            /// Array capacity
+            static CDS_CONSTEXPR const size_t c_nCapacity = Count;
+
         public:
-            // Default ctor
-            GuardArray()
-            {}
+            /// Default ctor allocates \p Count hazard pointers
+            GuardArray(); // inline in dhp_impl.h
 
-            //@cond
-            GuardArray( GuardArray const& ) = delete;
+            /// Move ctor is prohibited
             GuardArray( GuardArray&& ) = delete;
-            GuardArray& operator=(GuardArray const&) = delete;
-            GuardArray& operator-(GuardArray&&) = delete;
-            //@endcond
+
+            /// Move assignment is prohibited
+            GuardArray& operator=( GuardArray&& ) = delete;
+
+            /// Copy ctor is prohibited
+            GuardArray( GuardArray const& ) = delete;
+
+            /// Copy assignment is prohibited
+            GuardArray& operator=( GuardArray const& ) = delete;
+
+            /// Frees allocated hazard pointers
+            ~GuardArray(); // inline in dhp_impl.h
 
             /// Protects a pointer of type \p atomic<T*>
             /**
@@ -351,7 +426,10 @@ namespace cds { namespace gc {
             template <typename T>
             T * assign( size_t nIndex, T * p )
             {
-                base_class::set(nIndex, p);
+                assert( nIndex < capacity());
+                assert( m_arr[nIndex] != nullptr );
+
+                m_arr[nIndex]->pPost.store( p, atomics::memory_order_release );
                 return p;
             }
 
@@ -382,7 +460,10 @@ namespace cds { namespace gc {
             /// Clear value of the slot \p nIndex
             void clear( size_t nIndex )
             {
-                base_class::clear( nIndex );
+                assert( nIndex < capacity() );
+                assert( m_arr[nIndex] != nullptr );
+
+                m_arr[nIndex]->pPost.store( nullptr, atomics::memory_order_release );
             }
 
             /// Get current value of slot \p nIndex
@@ -395,14 +476,33 @@ namespace cds { namespace gc {
             /// Get native guarded pointer stored
             guarded_pointer get_native( size_t nIndex ) const
             {
-                return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
+                assert( nIndex < capacity() );
+                assert( m_arr[nIndex] != nullptr );
+
+                return m_arr[nIndex]->pPost.load( atomics::memory_order_acquire );
             }
 
+            //@cond
+            dhp::details::guard_data* release( size_t nIndex ) CDS_NOEXCEPT
+            {
+                assert( nIndex < capacity() );
+
+                dhp::details::guard_data* ret = m_arr[ nIndex ];
+                m_arr[nIndex] = nullptr;
+                return ret;
+            }
+            //@endcond
+
             /// Capacity of the guard array
             static CDS_CONSTEXPR size_t capacity()
             {
                 return Count;
             }
+
+        private:
+            //@cond
+            dhp::details::guard_data* m_arr[c_nCapacity];
+            //@endcond
         };
 
         /// Guarded pointer
@@ -455,6 +555,8 @@ namespace cds { namespace gc {
                     return p;
                 }
             };
+
+            template <typename GT, typename VT, typename C> friend class guarded_ptr;
             //@endcond
 
         public:
@@ -464,38 +566,47 @@ namespace cds { namespace gc {
             /// Functor for casting \p guarded_type to \p value_type
             typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
 
-            //@cond
-            typedef cds::gc::dhp::details::guard native_guard;
-            //@endcond
-
-        private:
-            //@cond
-            native_guard    m_guard;
-            //@endcond
-
         public:
             /// Creates empty guarded pointer
             guarded_ptr() CDS_NOEXCEPT
+                : m_guard( nullptr )
             {}
 
             //@cond
+            explicit guarded_ptr( dhp::details::guard_data* g ) CDS_NOEXCEPT
+                : m_guard( g )
+            {}
+
             /// Initializes guarded pointer with \p p
             explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
             {
-                alloc_guard();
-                assert( m_guard.is_initialized() );
-                m_guard.set( p );
+                reset( p );
             }
             explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
+                : m_guard( nullptr )
             {}
             //@endcond
 
             /// Move ctor
             guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
+                : m_guard( gp.m_guard )
             {
-                m_guard.set_guard( gp.m_guard.release_guard() );
+                gp.m_guard = nullptr;
             }
 
+            /// Move ctor
+            template <typename GT, typename VT, typename C>
+            guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
+                : m_guard( gp.m_guard )
+            {
+                gp.m_guard = nullptr;
+            }
+
+            /// Ctor from \p Guard
+            explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
+                : m_guard( g.release() )
+            {}
+
             /// The guarded pointer is not copy-constructible
             guarded_ptr( guarded_ptr const& gp ) = delete;
 
@@ -505,14 +616,20 @@ namespace cds { namespace gc {
             */
             ~guarded_ptr() CDS_NOEXCEPT
             {
-                free_guard();
+                release();
             }
 
             /// Move-assignment operator
             guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
             {
-                free_guard();
-                m_guard.set_guard( gp.m_guard.release_guard() );
+                std::swap( m_guard, gp.m_guard );
+                return *this;
+            }
+
+            /// Move-assignment from \p Guard
+            guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
+            {
+                std::swap( m_guard, g.m_guard );
                 return *this;
             }
 
@@ -523,27 +640,27 @@ namespace cds { namespace gc {
             value_type * operator ->() const CDS_NOEXCEPT
             {
                 assert( !empty() );
-                return value_cast()( reinterpret_cast<guarded_type *>(m_guard.get()));
+                return value_cast()( reinterpret_cast<guarded_type *>(m_guard->get()));
             }
 
             /// Returns a reference to guarded value
             value_type& operator *() CDS_NOEXCEPT
             {
                 assert( !empty());
-                return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
+                return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
             }
 
             /// Returns const reference to guarded value
             value_type const& operator *() const CDS_NOEXCEPT
             {
                 assert( !empty() );
-                return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
+                return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
             }
 
             /// Checks if the guarded pointer is \p nullptr
             bool empty() const CDS_NOEXCEPT
             {
-                return !m_guard.is_initialized() || m_guard.get( atomics::memory_order_relaxed ) == nullptr;
+                return m_guard == nullptr || m_guard->get( atomics::memory_order_relaxed ) == nullptr;
             }
 
             /// \p bool operator returns <tt>!empty()</tt>
@@ -564,18 +681,11 @@ namespace cds { namespace gc {
 
             //@cond
             // For internal use only!!!
-            native_guard& guard() CDS_NOEXCEPT
-            {
-                alloc_guard();
-                assert( m_guard.is_initialized() );
-                return m_guard;
-            }
-
             void reset(guarded_type * p) CDS_NOEXCEPT
             {
                 alloc_guard();
-                assert( m_guard.is_initialized() );
-                m_guard.set(p);
+                assert( m_guard );
+                m_guard->set( p );
             }
 
             //@endcond
@@ -584,16 +694,23 @@ namespace cds { namespace gc {
             //@cond
             void alloc_guard()
             {
-                if ( !m_guard.is_initialized() )
-                    thread_gc::alloc_guard( m_guard );
+                if ( !m_guard )
+                    m_guard = thread_gc::alloc_guard();
             }
 
             void free_guard()
             {
-                if ( m_guard.is_initialized() )
+                if ( m_guard ) {
                     thread_gc::free_guard( m_guard );
+                    m_guard = nullptr;
+                }
             }
             //@endcond
+
+        private:
+            //@cond
+            dhp::details::guard_data* m_guard;
+            //@endcond
         };
 
     public:
index a051e86..f22d74d 100644 (file)
@@ -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_GC_IMPL_DHP_IMPL_H
@@ -38,27 +38,32 @@ namespace cds { namespace gc {
 
     namespace dhp {
 
-        inline Guard::Guard()
+        static inline ThreadGC& get_thread_gc()
         {
-            cds::threading::getGC<DHP>().allocGuard( *this );
+            return cds::threading::getGC<DHP>();
         }
 
-        inline Guard::~Guard()
-        {
-            cds::threading::getGC<DHP>().freeGuard( *this );
-        }
-
-        template <size_t Count>
-        inline GuardArray<Count>::GuardArray()
-        {
-            cds::threading::getGC<DHP>().allocGuard( *this );
-        }
-
-        template <size_t Count>
-        inline GuardArray<Count>::~GuardArray()
-        {
-            cds::threading::getGC<DHP>().freeGuard( *this );
-        }
+        //inline Guard::Guard()
+        //{
+        //    cds::threading::getGC<DHP>().allocGuard( *this );
+        //}
+
+        //inline Guard::~Guard()
+        //{
+        //    cds::threading::getGC<DHP>().freeGuard( *this );
+        //}
+
+        //template <size_t Count>
+        //inline GuardArray<Count>::GuardArray()
+        //{
+        //    cds::threading::getGC<DHP>().allocGuard( *this );
+        //}
+
+        //template <size_t Count>
+        //inline GuardArray<Count>::~GuardArray()
+        //{
+        //    cds::threading::getGC<DHP>().freeGuard( *this );
+        //}
     } // namespace dhp
 
 
@@ -77,13 +82,26 @@ namespace cds { namespace gc {
             cds::threading::Manager::detachThread();
     }
 
-    inline /*static*/ void DHP::thread_gc::alloc_guard( cds::gc::dhp::details::guard& g )
+    inline /*static*/ dhp::details::guard_data* DHP::thread_gc::alloc_guard()
+    {
+        return dhp::get_thread_gc().allocGuard();
+    }
+    inline /*static*/ void DHP::thread_gc::free_guard( dhp::details::guard_data* g )
     {
-        return cds::threading::getGC<DHP>().allocGuard(g);
+        if ( g )
+            dhp::get_thread_gc().freeGuard( g );
     }
-    inline /*static*/ void DHP::thread_gc::free_guard( cds::gc::dhp::details::guard& g )
+
+    template <size_t Count>
+    inline DHP::GuardArray<Count>::GuardArray()
+    {
+        dhp::get_thread_gc().allocGuard( m_arr );
+    }
+
+    template <size_t Count>
+    inline DHP::GuardArray<Count>::~GuardArray()
     {
-        cds::threading::getGC<DHP>().freeGuard(g);
+        dhp::get_thread_gc().freeGuard( m_arr );
     }
 
     inline void DHP::scan()
index 64f3cde..354ac6a 100644 (file)
@@ -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_GC_IMPL_HP_DECL_H
@@ -87,6 +87,9 @@ namespace cds { namespace gc {
         */
         typedef hp::ThreadGC   thread_gc_impl;
 
+        /// Exception "Too many Hazard Pointer"
+        typedef hp::GarbageCollector::too_many_hazard_ptr too_many_hazard_ptr_exception;
+
         /// Wrapper for hp::ThreadGC class
         /**
             @headerfile cds/gc/hp.h
@@ -121,8 +124,8 @@ namespace cds { namespace gc {
 
         public: // for internal use only!!!
             //@cond
-            static cds::gc::hp::details::hp_guard& alloc_guard(); // inline in hp_impl.h
-            static void free_guard( cds::gc::hp::details::hp_guard& g ); // inline in hp_impl.h
+            static cds::gc::hp::details::hp_guard* alloc_guard(); // inline in hp_impl.h
+            static void free_guard( cds::gc::hp::details::hp_guard* g ); // inline in hp_impl.h
             //@endcond
         };
 
@@ -130,29 +133,77 @@ namespace cds { namespace gc {
         /**
             @headerfile cds/gc/hp.h
 
-            A guard is the hazard pointer.
-            Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
+            A guard is a hazard pointer.
+            Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer.
+
+            \p %Guard object is movable but not copyable.
+
+            The guard object can be in two states:
+            - unlinked - the guard is not linked with any internal hazard pointer.
+              In this state no operation except \p link() and move assignment is supported.
+            - linked (default) - the guard allocates an internal hazard pointer and fully operable.
+
+            Due to performance reason the implementation does not check state of the guard in runtime.
 
-            A \p %Guard object is not copy- and move-constructible
-            and not copy- and move-assignable.
+            @warning Move assignment can transfer the guard in unlinked state, use with care.
         */
-        class Guard : public hp::guard
+        class Guard
         {
-            //@cond
-            typedef hp::guard base_class;
-            //@endcond
-
         public:
-            /// Default ctor
-            Guard()
+            /// Default ctor allocates a guard (hazard pointer) from thread-private storage
+            /**
+                @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted.
+            */
+            Guard();  // inline in hp_impl.h
+
+            /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
+            explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
+                : m_guard( nullptr )
             {}
 
-            //@cond
+            /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
+            Guard( Guard&& src ) CDS_NOEXCEPT
+                : m_guard( src.m_guard )
+            {
+                src.m_guard = nullptr;
+            }
+
+            /// Move assignment: the internal guards are swapped between \p src and \p this
+            /**
+                @warning \p src will become in unlinked state if \p this was unlinked on entry.
+            */
+            Guard& operator=( Guard&& src ) CDS_NOEXCEPT
+            {
+                std::swap( m_guard, src.m_guard );
+                return *this;
+            }
+
+            /// Copy ctor is prohibited - the guard is not copyable
             Guard( Guard const& ) = delete;
-            Guard( Guard&& s ) = delete;
-            Guard& operator=(Guard const&) = delete;
-            Guard& operator=(Guard&&) = delete;
-            //@endcond
+
+            /// Copy assignment is prohibited
+            Guard& operator=( Guard const& ) = delete;
+
+            /// Frees the internal hazard pointer if the guard is in linked state
+            ~Guard()
+            {
+                unlink();
+            }
+
+            /// Checks if the guard object linked with any internal hazard pointer
+            bool is_linked() const
+            {
+                return m_guard != nullptr;
+            }
+
+            /// Links the guard with internal hazard pointer if the guard is in unlinked state
+            /**
+                @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted.
+            */
+            void link(); // inline in hp_impl.h
+
+            /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
+            void unlink(); // inline in hp_impl.h
 
             /// Protects a pointer of type \p atomic<T*>
             /**
@@ -160,10 +211,14 @@ namespace cds { namespace gc {
 
                 The function tries to load \p toGuard and to store it
                 to the HP slot repeatedly until the guard's value equals \p toGuard
+
+                @warning The guad object should be in linked state, otherwise the result is undefined
             */
             template <typename T>
             T protect( atomics::atomic<T> const& toGuard )
             {
+                assert( m_guard != nullptr );
+
                 T pCur = toGuard.load(atomics::memory_order_acquire);
                 T pRet;
                 do {
@@ -188,11 +243,15 @@ namespace cds { namespace gc {
                         value_type * operator()( T * p );
                     };
                 \endcode
-                Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
+                Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
+
+                @warning The guad object should be in linked state, otherwise the result is undefined
             */
             template <typename T, class Func>
             T protect( atomics::atomic<T> const& toGuard, Func f )
             {
+                assert( m_guard != nullptr );
+
                 T pCur = toGuard.load(atomics::memory_order_acquire);
                 T pRet;
                 do {
@@ -207,18 +266,21 @@ namespace cds { namespace gc {
             /**
                 The function equals to a simple assignment the value \p p to guard, no loop is performed.
                 Can be used for a pointer that cannot be changed concurrently
+
+                @warning The guad object should be in linked state, otherwise the result is undefined
             */
             template <typename T>
-            T * assign( T * p );    // inline in hp_impl.h
+            T * assign( T* p );    // inline in hp_impl.h
 
             //@cond
             std::nullptr_t assign( std::nullptr_t )
             {
-                return base_class::operator =(nullptr);
+                assert(m_guard != nullptr );
+                return *m_guard = nullptr;
             }
             //@endcond
 
-            /// Copy from \p src guard to \p this guard
+            /// Copy a value guarded from \p src guard to \p this guard (valid only in linked state)
             void copy( Guard const& src )
             {
                 assign( src.get_native() );
@@ -228,31 +290,48 @@ namespace cds { namespace gc {
             /**
                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
                 Can be used for a marked pointer that cannot be changed concurrently.
+
+                @warning The guad object should be in linked state, otherwise the result is undefined
             */
             template <typename T, int BITMASK>
             T * assign( cds::details::marked_ptr<T, BITMASK> p )
             {
-                return base_class::operator =( p.ptr() );
+                return assign( p.ptr());
             }
 
-            /// Clear value of the guard
+            /// Clear value of the guard (valid only in linked state)
             void clear()
             {
                 assign( nullptr );
             }
 
-            /// Get the value currently protected
+            /// Get the value currently protected (valid only in linked state)
             template <typename T>
             T * get() const
             {
                 return reinterpret_cast<T *>( get_native() );
             }
 
-            /// Get native hazard pointer stored
+            /// Get native hazard pointer stored (valid only in linked state)
             guarded_pointer get_native() const
             {
-                return base_class::get();
+                assert( m_guard != nullptr );
+                return m_guard->get();
             }
+
+            //@cond
+            hp::details::hp_guard* release()
+            {
+                hp::details::hp_guard* g = m_guard;
+                m_guard = nullptr;
+                return g;
+            }
+            //@endcond
+
+        private:
+            //@cond
+            hp::details::hp_guard* m_guard;
+            //@endcond
         };
 
         /// Array of Hazard Pointer guards
@@ -261,33 +340,38 @@ namespace cds { namespace gc {
             The class is intended for allocating an array of hazard pointer guards.
             Template parameter \p Count defines the size of the array.
 
-            A \p %GuardArray object is not copy- and move-constructible
-            and not copy- and move-assignable.
         */
         template <size_t Count>
-        class GuardArray : public hp::array<Count>
+        class GuardArray
         {
-            //@cond
-            typedef hp::array<Count> base_class;
-            //@endcond
         public:
             /// Rebind array for other size \p Count2
             template <size_t Count2>
             struct rebind {
-                typedef GuardArray<Count2>  other   ;   ///< rebinding result
+                typedef GuardArray<Count2>  other;   ///< rebinding result
             };
 
+            /// Array capacity
+            static CDS_CONSTEXPR const size_t c_nCapacity = Count;
+
         public:
-            /// Default ctor
-            GuardArray()
-            {}
+            /// Default ctor allocates \p Count hazard pointers
+            GuardArray(); // inline in hp_impl.h
 
-            //@cond
-            GuardArray( GuardArray const& ) = delete;
+            /// Move ctor is prohibited
             GuardArray( GuardArray&& ) = delete;
-            GuardArray& operator=(GuardArray const&) = delete;
-            GuardArray& operator=(GuardArray&&) = delete;
-            //@endcond
+
+            /// Move assignment is prohibited
+            GuardArray& operator=( GuardArray&& ) = delete;
+
+            /// Copy ctor is prohibited
+            GuardArray( GuardArray const& ) = delete;
+
+            /// Copy assignment is prohibited
+            GuardArray& operator=( GuardArray const& ) = delete;
+
+            /// Frees allocated hazard pointers
+            ~GuardArray(); // inline in hp_impl.h
 
             /// Protects a pointer of type \p atomic<T*>
             /**
@@ -299,6 +383,8 @@ namespace cds { namespace gc {
             template <typename T>
             T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
             {
+                assert( nIndex < capacity());
+
                 T pRet;
                 do {
                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
@@ -327,6 +413,8 @@ namespace cds { namespace gc {
             template <typename T, class Func>
             T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
             {
+                assert( nIndex < capacity() );
+
                 T pRet;
                 do {
                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
@@ -368,7 +456,7 @@ namespace cds { namespace gc {
             /// Clear value of the slot \p nIndex
             void clear( size_t nIndex )
             {
-                base_class::clear( nIndex );
+                m_arr.clear( nIndex );
             }
 
             /// Get current value of slot \p nIndex
@@ -381,14 +469,27 @@ namespace cds { namespace gc {
             /// Get native hazard pointer stored
             guarded_pointer get_native( size_t nIndex ) const
             {
-                return base_class::operator[](nIndex).get();
+                assert( nIndex < capacity() );
+                return m_arr[nIndex]->get();
             }
 
+            //@cond
+            hp::details::hp_guard* release( size_t nIndex ) CDS_NOEXCEPT
+            {
+                return m_arr.release( nIndex );
+            }
+            //@endcond
+
             /// Capacity of the guard array
             static CDS_CONSTEXPR size_t capacity()
             {
-                return Count;
+                return c_nCapacity;
             }
+
+        private:
+            //@cond
+            hp::details::hp_array<Count> m_arr;
+            //@endcond
         };
 
         /// Guarded pointer
@@ -441,6 +542,8 @@ namespace cds { namespace gc {
                     return p;
                 }
             };
+
+            template <typename GT, typename VT, typename C> friend class guarded_ptr;
             //@endcond
 
         public:
@@ -450,26 +553,19 @@ namespace cds { namespace gc {
             /// Functor for casting \p guarded_type to \p value_type
             typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
 
-            //@cond
-            typedef cds::gc::hp::details::hp_guard native_guard;
-            //@endcond
-
-        private:
-            //@cond
-            native_guard *  m_pGuard;
-            //@endcond
-
         public:
             /// Creates empty guarded pointer
             guarded_ptr() CDS_NOEXCEPT
                 : m_pGuard(nullptr)
-            {
-                alloc_guard();
-            }
+            {}
 
             //@cond
+            explicit guarded_ptr( hp::details::hp_guard* g ) CDS_NOEXCEPT
+                : m_pGuard( g )
+            {}
+
             /// Initializes guarded pointer with \p p
-            explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
+            explicit guarded_ptr( guarded_type* p ) CDS_NOEXCEPT
                 : m_pGuard( nullptr )
             {
                 reset(p);
@@ -486,31 +582,42 @@ namespace cds { namespace gc {
                 gp.m_pGuard = nullptr;
             }
 
+            /// Move ctor
+            template <typename GT, typename VT, typename C>
+            guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
+                : m_pGuard( gp.m_pGuard )
+            {
+                gp.m_pGuard = nullptr;
+            }
+
+            /// Ctor from \p Guard
+            explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
+                : m_pGuard( g.release() )
+            {}
+
             /// The guarded pointer is not copy-constructible
             guarded_ptr( guarded_ptr const& gp ) = delete;
 
             /// Clears the guarded pointer
             /**
-                \ref release is called if guarded pointer is not \ref empty
+                \ref release() is called if guarded pointer is not \ref empty()
             */
             ~guarded_ptr() CDS_NOEXCEPT
             {
-                free_guard();
+                release();
             }
 
             /// Move-assignment operator
             guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
             {
-                // Hazard Pointer array is organized as a stack
-                if ( m_pGuard && m_pGuard > gp.m_pGuard ) {
-                    m_pGuard->set( gp.m_pGuard->get(atomics::memory_order_relaxed) );
-                    gp.free_guard();
-                }
-                else {
-                    free_guard();
-                    m_pGuard = gp.m_pGuard;
-                    gp.m_pGuard = nullptr;
-                }
+                std::swap( m_pGuard, gp.m_pGuard );
+                return *this;
+            }
+
+            /// Move-assignment from \p Guard
+            guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
+            {
+                std::swap( m_pGuard, g.m_guard );
                 return *this;
             }
 
@@ -562,13 +669,6 @@ namespace cds { namespace gc {
 
             //@cond
             // For internal use only!!!
-            native_guard& guard() CDS_NOEXCEPT
-            {
-                alloc_guard();
-                assert( m_pGuard );
-                return *m_pGuard;
-            }
-
             void reset(guarded_type * p) CDS_NOEXCEPT
             {
                 alloc_guard();
@@ -582,17 +682,22 @@ namespace cds { namespace gc {
             void alloc_guard()
             {
                 if ( !m_pGuard )
-                    m_pGuard = &thread_gc::alloc_guard();
+                    m_pGuard = thread_gc::alloc_guard();
             }
 
             void free_guard()
             {
                 if ( m_pGuard ) {
-                    thread_gc::free_guard( *m_pGuard );
+                    thread_gc::free_guard( m_pGuard );
                     m_pGuard = nullptr;
                 }
             }
             //@endcond
+
+        private:
+            //@cond
+            hp::details::hp_guard* m_pGuard;
+            //@endcond
         };
 
     public:
index 63d9dde..92bf749 100644 (file)
@@ -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_GC_IMPL_HP_IMPL_H
 namespace cds { namespace gc {
 
     namespace hp {
-        inline guard::guard()
-            : m_hp( cds::threading::getGC<HP>().allocGuard() )
-        {}
-
-        template <typename T>
-        inline guard::guard( T * p )
-            : m_hp( cds::threading::getGC<HP>().allocGuard() )
+        static inline ThreadGC& get_thread_gc()
         {
-            m_hp = p;
+            return cds::threading::getGC<HP>();
         }
-
-        inline guard::~guard()
-        {
-            cds::threading::getGC<HP>().freeGuard( m_hp );
-        }
-
-        template <size_t Count>
-        inline array<Count>::array()
-        {
-            cds::threading::getGC<HP>().allocGuard( *this );
-        }
-
-        template <size_t Count>
-        inline array<Count>::~array()
-        {
-            cds::threading::getGC<HP>().freeGuard( *this );
-        }
-
-
-
     } // namespace hp
 
     inline HP::thread_gc::thread_gc(
@@ -85,30 +59,71 @@ namespace cds { namespace gc {
             cds::threading::Manager::detachThread();
     }
 
-    inline /*static*/ cds::gc::hp::details::hp_guard& HP::thread_gc::alloc_guard()
+    inline /*static*/ cds::gc::hp::details::hp_guard* HP::thread_gc::alloc_guard()
     {
-        return cds::threading::getGC<HP>().allocGuard();
+        return hp::get_thread_gc().allocGuard();
     }
 
-    inline /*static*/ void HP::thread_gc::free_guard( cds::gc::hp::details::hp_guard& g )
+    inline /*static*/ void HP::thread_gc::free_guard( cds::gc::hp::details::hp_guard* g )
     {
-        cds::threading::getGC<HP>().freeGuard( g );
+        hp::get_thread_gc().freeGuard( g );
+    }
+
+    inline HP::Guard::Guard()
+        : m_guard( hp::get_thread_gc().allocGuard())
+    {
+        if ( !m_guard )
+            throw too_many_hazard_ptr_exception();
     }
 
     template <typename T>
     inline T * HP::Guard::assign( T * p )
     {
-        T * pp = base_class::operator =(p);
-        cds::threading::getGC<HP>().sync();
+        assert( m_guard != nullptr );
+
+        T * pp = ( *m_guard = p );
+        hp::get_thread_gc().sync();
         return pp;
     }
 
+    inline void HP::Guard::link()
+    {
+        if ( !m_guard ) {
+            m_guard = hp::get_thread_gc().allocGuard();
+            if ( !m_guard )
+                throw too_many_hazard_ptr_exception();
+        }
+    }
+
+    inline void HP::Guard::unlink()
+    {
+        if ( m_guard ) {
+            hp::get_thread_gc().freeGuard( m_guard );
+            m_guard = nullptr;
+        }
+    }
+
+    template <size_t Count>
+    inline HP::GuardArray<Count>::GuardArray()
+    {
+        if ( hp::get_thread_gc().allocGuard( m_arr ) != Count )
+            throw too_many_hazard_ptr_exception();
+    }
+
+    template <size_t Count>
+    inline HP::GuardArray<Count>::~GuardArray()
+    {
+        hp::get_thread_gc().freeGuard( m_arr );
+    }
+
     template <size_t Count>
     template <typename T>
-    inline T * HP::GuardArray<Count>::assign( size_t nIndex, T * p )
+    inline T * HP::GuardArray<Count>::assign( size_t nIndex, T* p )
     {
-        base_class::set(nIndex, p);
-        cds::threading::getGC<HP>().sync();
+        assert( nIndex < capacity() );
+
+        m_arr.set(nIndex, p);
+        hp::get_thread_gc().sync();
         return p;
     }
 
@@ -121,12 +136,12 @@ namespace cds { namespace gc {
     template <class Disposer, typename T>
     inline void HP::retire( T * p )
     {
-        cds::threading::getGC<HP>().retirePtr( p, cds::details::static_functor<Disposer, T>::call );
+        hp::get_thread_gc().retirePtr( p, cds::details::static_functor<Disposer, T>::call );
     }
 
     inline void HP::scan()
     {
-        cds::threading::getGC<HP>().scan();
+        hp::get_thread_gc().scan();
     }
 
 }} // namespace cds::gc
index 0ac96f1..792dc01 100644 (file)
@@ -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_DETAILS_FELDMAN_HASHSET_BASE_H
@@ -300,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
index c36729c..db0ce4d 100644 (file)
@@ -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_ELLEN_BINTREE_DHP_H
index 0f94eb5..1af9a48 100644 (file)
@@ -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_ELLEN_BINTREE_HP_H
index f8f0863..be8f88b 100644 (file)
@@ -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_ELLEN_BINTREE_H
@@ -601,9 +601,7 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            extract_min_( gp.guard() );
-            return gp;
+            return extract_min_();
         }
 
         /// Extracts an item with maximal key from the tree
@@ -622,9 +620,7 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            extract_max_( gp.guard());
-            return gp;
+            return extract_max_();
         }
 
         /// Extracts an item from the tree
@@ -640,9 +636,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_( gp.guard(), key );
-            return gp;
+            return extract_( key );
         }
 
         /// Extracts an item from the tree using \p pred for searching
@@ -656,9 +650,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less>
         guarded_ptr extract_with( Q const& key, Less pred )
         {
-            guarded_ptr gp;
-            extract_with_( gp.guard(), key, pred );
-            return gp;
+            return extract_with_( key, pred );
         }
 
         /// Checks whether the set contains \p key
@@ -785,9 +777,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key ) const
         {
-            guarded_ptr gp;
-            get_( gp.guard(), key );
-            return gp;
+            return get_( key );
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
@@ -801,9 +791,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less>
         guarded_ptr get_with( Q const& key, Less pred ) const
         {
-            guarded_ptr gp;
-            get_with_( gp.guard(), key, pred );
-            return gp;
+            return get_with_( key, pred );
         }
 
         /// Checks if the tree is empty
@@ -1359,16 +1347,62 @@ namespace cds { namespace intrusive {
             return true;
         }
 
+        template <typename Q, typename Compare>
+        guarded_ptr extract_item( Q const& key, Compare cmp )
+        {
+            update_desc * pOp = nullptr;
+            search_result res;
+            back_off bkoff;
+
+            for ( ;; ) {
+                if ( !search( res, key, cmp )) {
+                    if ( pOp )
+                        retire_update_desc( pOp );
+                    m_Stat.onEraseFailed();
+                    return guarded_ptr();
+                }
+
+                if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
+                    if ( !pOp )
+                        pOp = alloc_update_desc();
+                    if ( check_delete_precondition( res ) ) {
+                        typename gc::Guard guard;
+                        guard.assign( pOp );
+
+                        pOp->dInfo.pGrandParent = res.pGrandParent;
+                        pOp->dInfo.pParent = res.pParent;
+                        pOp->dInfo.pLeaf = res.pLeaf;
+                        pOp->dInfo.pUpdateParent = res.updParent.ptr();
+                        pOp->dInfo.bRightParent = res.bRightParent;
+                        pOp->dInfo.bRightLeaf = res.bRightLeaf;
+
+                        update_ptr updGP( res.updGrandParent.ptr() );
+                        if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ),
+                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+                            if ( help_delete( pOp ))
+                                break;
+                            pOp = nullptr;
+                        }
+                    }
+                }
+
+                bkoff();
+                m_Stat.onEraseRetry();
+            }
+
+            --m_ItemCounter;
+            m_Stat.onEraseSuccess();
+            return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+        }
+
         template <typename Q>
-        bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
+        guarded_ptr extract_( Q const& key )
         {
-            return erase_( key, node_compare(),
-                []( Q const&, leaf_node const& ) -> bool { return true; },
-                [&guard]( value_type& found ) { guard.set( &found ); } );
+            return extract_item( key, node_compare());
         }
 
         template <typename Q, typename Less>
-        bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less /*pred*/ )
+        guarded_ptr extract_with_( Q const& key, Less /*pred*/ )
         {
             typedef ellen_bintree::details::compare<
                 key_type,
@@ -1377,12 +1411,10 @@ namespace cds { namespace intrusive {
                 node_traits
             > compare_functor;
 
-            return erase_( key, compare_functor(),
-                []( Q const&, leaf_node const& ) -> bool { return true; },
-                [&guard]( value_type& found ) { guard.set( &found ); } );
+            return extract_item( key, compare_functor());
         }
 
-        bool extract_max_( typename guarded_ptr::native_guard& gp )
+        guarded_ptr extract_max_()
         {
             update_desc * pOp = nullptr;
             search_result res;
@@ -1394,7 +1426,7 @@ namespace cds { namespace intrusive {
                     if ( pOp )
                         retire_update_desc( pOp );
                     m_Stat.onExtractMaxFailed();
-                    return false;
+                    return guarded_ptr();
                 }
 
                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
@@ -1428,11 +1460,10 @@ namespace cds { namespace intrusive {
 
             --m_ItemCounter;
             m_Stat.onExtractMaxSuccess();
-            gp.set( node_traits::to_value_ptr( res.pLeaf ));
-            return true;
+            return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
         }
 
-        bool extract_min_( typename guarded_ptr::native_guard& gp )
+        guarded_ptr extract_min_()
         {
             update_desc * pOp = nullptr;
             search_result res;
@@ -1444,7 +1475,7 @@ namespace cds { namespace intrusive {
                     if ( pOp )
                         retire_update_desc( pOp );
                     m_Stat.onExtractMinFailed();
-                    return false;
+                    return guarded_ptr();
                 }
 
                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean ) {
@@ -1478,8 +1509,7 @@ namespace cds { namespace intrusive {
 
             --m_ItemCounter;
             m_Stat.onExtractMinSuccess();
-            gp.set( node_traits::to_value_ptr( res.pLeaf ));
-            return true;
+            return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
         }
 
         template <typename Q, typename Func>
@@ -1522,15 +1552,39 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q>
-        bool get_( typename guarded_ptr::native_guard& guard, Q const& val ) const
+        guarded_ptr get_( Q const& val ) const
         {
-            return find_( val, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
+            search_result    res;
+            if ( search( res, val, node_compare() ) ) {
+                assert( res.pLeaf );
+                m_Stat.onFindSuccess();
+                return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+            }
+
+            m_Stat.onFindFailed();
+            return guarded_ptr();
         }
 
         template <typename Q, typename Less>
-        bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Less pred ) const
+        guarded_ptr get_with_( Q const& val, Less pred ) const
         {
-            return find_with_( val, pred, [&guard]( value_type& found, Q const& ) { guard.set( &found ); } );
+            typedef ellen_bintree::details::compare<
+                key_type,
+                value_type,
+                opt::details::make_comparator_from_less<Less>,
+                node_traits
+            > compare_functor;
+
+            search_result    res;
+            if ( search( res, val, compare_functor() ) ) {
+                assert( res.pLeaf );
+                m_Stat.onFindSuccess();
+                return guarded_ptr( res.guards.release( search_result::Guard_Leaf ));
+            }
+
+            m_Stat.onFindFailed();
+            return guarded_ptr();
+
         }
 
         //@endcond
index 3382877..4078fcf 100644 (file)
@@ -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
@@ -782,16 +782,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
@@ -861,12 +855,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)
index 603d301..ea051c8 100644 (file)
@@ -585,7 +585,7 @@ namespace cds { namespace intrusive {
             ord_list theList;
             // ...
             {
-                ord_list::guarded_ptr gp(theList.extract( 5 ));
+                ord_list::guarded_ptr gp( theList.extract( 5 ));
                 if ( gp ) {
                     // Deal with gp
                     // ...
@@ -597,9 +597,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( m_pHead, gp.guard(), key, key_comparator());
-            return gp;
+            return extract_at( m_pHead, key, key_comparator());
         }
 
         /// Extracts the item using compare functor \p pred
@@ -615,9 +613,7 @@ namespace cds { namespace intrusive {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Finds \p key in the list
@@ -754,9 +750,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key ) const
         {
-            guarded_ptr gp;
-            get_at( m_pHead, gp.guard(), key, key_comparator());
-            return gp;
+            return get_at( m_pHead, key, key_comparator());
         }
 
         /// Finds the \p key and return the item found
@@ -772,9 +766,7 @@ namespace cds { namespace intrusive {
         guarded_ptr get_with( Q const& key, Less pred ) const
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Clears the list (thread safe, not atomic)
@@ -989,16 +981,16 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
+        guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
         {
             position pos;
             back_off bkoff;
             while ( search( refHead, val, pos, cmp )) {
                 if ( unlink_node( pos )) {
-                    dest.set( pos.pFound );
                     --m_ItemCounter;
                     m_Stat.onEraseSuccess();
-                    return true;
+                    assert( pos.pFound != nullptr );
+                    return guarded_ptr( std::move( pos.guard ));
                 }
                 else
                     bkoff();
@@ -1007,7 +999,7 @@ namespace cds { namespace intrusive {
             }
 
             m_Stat.onEraseFailed();
-            return false;
+            return guarded_ptr();
         }
 
         template <typename Q, typename Compare>
@@ -1054,17 +1046,16 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( atomic_node_ptr const& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp ) const
+        guarded_ptr get_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
         {
             position pos;
             if ( search( refHead, val, pos, cmp )) {
-                guard.set( pos.pFound );
                 m_Stat.onFindSuccess();
-                return true;
+                return guarded_ptr( std::move( pos.guard ));
             }
 
             m_Stat.onFindFailed();
-            return false;
+            return guarded_ptr();
         }
         //@endcond
 
index 845362a..13fa9b9 100644 (file)
@@ -721,9 +721,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( &m_Head, gp.guard(), key, key_comparator());
-            return gp;
+            return extract_at( &m_Head, key, key_comparator());
         }
 
         /// Extracts the item from the list with comparing functor \p pred
@@ -739,9 +737,7 @@ namespace cds { namespace intrusive {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return extract_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Finds the key \p key
@@ -867,9 +863,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_at( &m_Head, gp.guard(), key, key_comparator());
-            return gp;
+            return get_at( &m_Head, key, key_comparator());
         }
 
         /// Finds \p key and return the item found
@@ -885,9 +879,7 @@ namespace cds { namespace intrusive {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return get_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Clears the list
@@ -1154,14 +1146,12 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
+        guarded_ptr extract_at( node_type * pHead, const Q& val, Compare cmp )
         {
             position pos;
-            if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
-                gp.set( pos.guards.template get<value_type>(position::guard_current_item));
-                return true;
-            }
-            return false;
+            if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos ))
+                return guarded_ptr( pos.guards.release( position::guard_current_item ));
+            return guarded_ptr();
         }
 
         template <typename Q, typename Compare, typename Func>
@@ -1201,7 +1191,7 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
+        guarded_ptr get_at( node_type * pHead, Q const& val, Compare cmp )
         {
             position pos;
 
@@ -1210,13 +1200,12 @@ namespace cds { namespace intrusive {
                 && !pos.pCur->is_marked()
                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
             {
-                gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
                 m_Stat.onFindSuccess();
-                return true;
+                return guarded_ptr( pos.guards.release( position::guard_current_item ));
             }
 
             m_Stat.onFindFailed();
-            return false;
+            return guarded_ptr();
         }
 
         //@endcond
index 8e58bf4..d279a21 100644 (file)
@@ -732,9 +732,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_at( m_pHead, gp.guard(), key, key_comparator());
-            return gp;
+            return extract_at( m_pHead, key, key_comparator());
         }
 
         /// Extracts the item using compare functor \p pred
@@ -750,9 +748,7 @@ namespace cds { namespace intrusive {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Finds \p key in the list
@@ -883,9 +879,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_at( m_pHead, gp.guard(), key, key_comparator());
-            return gp;
+            return get_at( m_pHead, key, key_comparator());
         }
 
         /// Finds the \p key and return the item found
@@ -901,9 +895,7 @@ namespace cds { namespace intrusive {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
-            return gp;
+            return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
         }
 
         /// Clears the list
@@ -1119,16 +1111,15 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
+        guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
         {
             position pos;
             back_off bkoff;
             while ( search( refHead, val, pos, cmp )) {
                 if ( unlink_node( pos )) {
-                    dest.set( pos.guards.template get<value_type>( position::guard_current_item ));
                     --m_ItemCounter;
                     m_Stat.onEraseSuccess();
-                    return true;
+                    return guarded_ptr( pos.guards.release( position::guard_current_item ));
                 }
                 else
                     bkoff();
@@ -1136,7 +1127,7 @@ namespace cds { namespace intrusive {
             }
 
             m_Stat.onEraseFailed();
-            return false;
+            return guarded_ptr();
         }
 
         template <typename Q, typename Compare>
@@ -1167,17 +1158,16 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+        guarded_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
         {
             position pos;
             if ( search( refHead, val, pos, cmp )) {
-                guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
                 m_Stat.onFindSuccess();
-                return true;
+                return guarded_ptr( pos.guards.release( position::guard_current_item ));
             }
 
             m_Stat.onFindFailed();
-            return false;
+            return guarded_ptr();
         }
 
         //@endcond
index 57b1037..8b2f0ea 100644 (file)
@@ -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_SKIP_LIST_H
@@ -843,9 +843,12 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+        guarded_ptr get_with_( Q const& val, Compare cmp )
         {
-            return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
+            guarded_ptr gp;
+            if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
+                return gp;
+            return guarded_ptr();
         }
 
         template <typename Q, typename Compare, typename Func>
@@ -876,19 +879,19 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+        guarded_ptr extract_( Q const& val, Compare cmp )
         {
             position pos;
 
+            guarded_ptr gp;
             for (;;) {
                 if ( !find_position( val, pos, cmp, false ) ) {
                     m_Stat.onExtractFailed();
-                    guard.clear();
-                    return false;
+                    return guarded_ptr();
                 }
 
                 node_type * pDel = pos.pCur;
-                guard.set( node_traits::to_value_ptr(pDel));
+                gp.reset( node_traits::to_value_ptr( pDel ));
                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 
                 unsigned int nHeight = pDel->height();
@@ -896,62 +899,62 @@ namespace cds { namespace intrusive {
                     --m_ItemCounter;
                     m_Stat.onRemoveNode( nHeight );
                     m_Stat.onExtractSuccess();
-                    return true;
+                    return gp;
                 }
                 m_Stat.onExtractRetry();
             }
         }
 
-        bool extract_min_( typename guarded_ptr::native_guard& gDel )
+        guarded_ptr extract_min_()
         {
             position pos;
 
+            guarded_ptr gp;
             for (;;) {
                 if ( !find_min_position( pos ) ) {
                     // The list is empty
                     m_Stat.onExtractMinFailed();
-                    gDel.clear();
-                    return false;
+                    return guarded_ptr();
                 }
 
                 node_type * pDel = pos.pCur;
 
                 unsigned int nHeight = pDel->height();
-                gDel.set( node_traits::to_value_ptr(pDel) );
+                gp.reset( node_traits::to_value_ptr(pDel) );
 
                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
                     --m_ItemCounter;
                     m_Stat.onRemoveNode( nHeight );
                     m_Stat.onExtractMinSuccess();
-                    return true;
+                    return gp;
                 }
 
                 m_Stat.onExtractMinRetry();
             }
         }
 
-        bool extract_max_( typename guarded_ptr::native_guard& gDel )
+        guarded_ptr extract_max_()
         {
             position pos;
 
+            guarded_ptr gp;
             for (;;) {
                 if ( !find_max_position( pos ) ) {
                     // The list is empty
                     m_Stat.onExtractMaxFailed();
-                    gDel.clear();
-                    return false;
+                    return guarded_ptr();
                 }
 
                 node_type * pDel = pos.pCur;
 
                 unsigned int nHeight = pDel->height();
-                gDel.set( node_traits::to_value_ptr(pDel) );
+                gp.reset( node_traits::to_value_ptr(pDel) );
 
                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
                     --m_ItemCounter;
                     m_Stat.onRemoveNode( nHeight );
                     m_Stat.onExtractMaxSuccess();
-                    return true;
+                    return gp;
                 }
 
                 m_Stat.onExtractMaxRetry();
@@ -1308,9 +1311,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_( gp.guard(), key, key_comparator() );
-            return gp;
+            return extract_( key, key_comparator() );
         }
 
         /// Extracts the item from the set with comparing functor \p pred
@@ -1326,9 +1327,7 @@ namespace cds { namespace intrusive {
         guarded_ptr extract_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
-            return gp;
+            return extract_( key, cds::opt::details::make_comparator_from_less<Less>() );
         }
 
         /// Extracts an item with minimal key from the list
@@ -1363,9 +1362,7 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr extract_min()
         {
-            guarded_ptr gp;
-            extract_min_( gp.guard() );
-            return gp;
+            return extract_min_();
         }
 
         /// Extracts an item with maximal key from the list
@@ -1401,9 +1398,7 @@ namespace cds { namespace intrusive {
         */
         guarded_ptr extract_max()
         {
-            guarded_ptr gp;
-            extract_max_( gp.guard() );
-            return gp;
+            return extract_max_();
         }
 
         /// Deletes the item from the set
@@ -1606,9 +1601,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_with_( gp.guard(), key, key_comparator() );
-            return gp;
+            return get_with_( key, key_comparator() );
         }
 
         /// Finds \p key and return the item found
@@ -1624,9 +1617,7 @@ namespace cds { namespace intrusive {
         guarded_ptr get_with( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            guarded_ptr gp;
-            get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
-            return gp;
+            return get_with_( key, cds::opt::details::make_comparator_from_less<Less>() );
         }
 
         /// Returns item count in the set
@@ -1662,8 +1653,7 @@ namespace cds { namespace intrusive {
         */
         void clear()
         {
-            guarded_ptr gp;
-            while ( extract_min_( gp.guard() ));
+            while ( extract_min_());
         }
 
         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
index ad45c06..f4fce63 100644 (file)
@@ -330,11 +330,11 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            bool extract_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
+            guarded_ptr extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
-                return base_class::extract_at( h, guard, val, cmp );
+                return base_class::extract_at( h, val, cmp );
             }
 
             template <typename Q, typename Compare, typename Func>
@@ -354,11 +354,11 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            bool get_at( dummy_node_type * pHead, typename guarded_ptr::native_guard& guard, split_list::details::search_value_type<Q> const& val, Compare cmp )
+            guarded_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
-                return base_class::get_at( h, guard, val, cmp );
+                return base_class::get_at( h, val, cmp );
             }
 
             bool insert_aux_node( dummy_node_type * pNode )
@@ -539,26 +539,28 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool get_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+        guarded_ptr get_( Q const& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
             dummy_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
-            return m_Stat.onFind( m_List.get_at( pHead, guard, sv, cmp ));
+            guarded_ptr gp = m_List.get_at( pHead, sv, cmp );
+            m_Stat.onFind( !gp.empty() );
+            return gp;
         }
 
         template <typename Q>
-        bool get_( typename guarded_ptr::native_guard& guard, Q const& key )
+        guarded_ptr get_( Q const& key )
         {
-            return get_( guard, key, key_comparator());
+            return get_( key, key_comparator());
         }
 
         template <typename Q, typename Less>
-        bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
+        guarded_ptr get_with_( Q const& key, Less )
         {
-            return get_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
+            return get_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
         }
 
         template <typename Q, typename Compare, typename Func>
@@ -596,32 +598,33 @@ namespace cds { namespace intrusive {
         }
 
         template <typename Q, typename Compare>
-        bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
+        guarded_ptr extract_( Q const& val, Compare cmp )
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const> sv( val, split_list::regular_hash( nHash ));
             dummy_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
-            if ( m_List.extract_at( pHead, guard, sv, cmp )) {
+            guarded_ptr gp = m_List.extract_at( pHead, sv, cmp );
+            if ( gp ) {
                 --m_ItemCounter;
                 m_Stat.onExtractSuccess();
-                return true;
             }
-            m_Stat.onExtractFailed();
-            return false;
+            else
+                m_Stat.onExtractFailed();
+            return gp;
         }
 
         template <typename Q>
-        bool extract_( typename guarded_ptr::native_guard& guard, Q const& key )
+        guarded_ptr extract_( Q const& key )
         {
-            return extract_( guard, key, key_comparator());
+            return extract_( key, key_comparator());
         }
 
         template <typename Q, typename Less>
-        bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less )
+        guarded_ptr extract_with_( Q const& key, Less )
         {
-            return extract_( guard, key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
+            return extract_( key, typename wrapped_ordered_list::template make_compare_from_less<Less>());
         }
         //@endcond
 
@@ -898,9 +901,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr extract( Q const& key )
         {
-            guarded_ptr gp;
-            extract_( gp.guard(), key );
-            return gp;
+            return extract_( key );
         }
 
         /// Extracts the item using compare functor \p pred
@@ -915,9 +916,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less>
         guarded_ptr extract_with( Q const& key, Less pred )
         {
-            guarded_ptr gp;
-            extract_with_( gp.guard(), key, pred );
-            return gp;
+            return extract_with_( key, pred );
         }
 
         /// Finds the key \p key
@@ -1052,9 +1051,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         guarded_ptr get( Q const& key )
         {
-            guarded_ptr gp;
-            get_( gp.guard(), key );
-            return gp;
+            return get_( key );
         }
 
         /// Finds the key \p key and return the item found
@@ -1069,9 +1066,7 @@ namespace cds { namespace intrusive {
         template <typename Q, typename Less>
         guarded_ptr get_with( Q const& key, Less pred )
         {
-            guarded_ptr gp;
-            get_with_( gp.guard(), key, pred );
-            return gp;
+            return get_with_( key, pred );
         }
 
         /// Returns item count in the set
index c760a82..e7cb6e8 100644 (file)
       <PrecompiledHeader>NotUsing</PrecompiledHeader>
       <WarningLevel>Level3</WarningLevel>
       <Optimization>Disabled</Optimization>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
       <PrecompiledHeader>NotUsing</PrecompiledHeader>
       <WarningLevel>Level3</WarningLevel>
       <Optimization>Disabled</Optimization>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
       <PrecompiledHeader>NotUsing</PrecompiledHeader>
       <WarningLevel>Level3</WarningLevel>
       <Optimization>Disabled</Optimization>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
       <PrecompiledHeader>NotUsing</PrecompiledHeader>
       <WarningLevel>Level3</WarningLevel>
       <Optimization>Disabled</Optimization>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
       <Optimization>MaxSpeed</Optimization>
       <FunctionLevelLinking>true</FunctionLevelLinking>
       <IntrinsicFunctions>true</IntrinsicFunctions>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
       <Optimization>MaxSpeed</Optimization>
       <FunctionLevelLinking>true</FunctionLevelLinking>
       <IntrinsicFunctions>true</IntrinsicFunctions>
-      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;_SCL_SECURE_NO_WARNINGS;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
       <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
index 665ea99..28f809e 100644 (file)
@@ -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.
 */
 
 // Dynamic Hazard Pointer memory manager implementation
@@ -79,42 +79,69 @@ namespace cds { namespace gc { namespace dhp {
                 item_type& refBucket = bucket( node );
                 if ( refBucket ) {
                     item_type p = refBucket;
+                    item_type prev = nullptr;
                     do {
-                        if ( p->m_ptr.m_p == node.m_ptr.m_p ) {
-                            assert( node.m_pNextFree.load( atomics::memory_order_relaxed ) == nullptr );
-
-                            node.m_pNextFree.store( p->m_pNextFree.load( atomics::memory_order_relaxed ), atomics::memory_order_relaxed );
-                            p->m_pNextFree.store( &node, atomics::memory_order_relaxed );
+                        if ( p->m_ptr.m_p >= node.m_ptr.m_p ) {
+                            node.m_pNext.store( p, atomics::memory_order_relaxed );
+                            if ( prev )
+                                prev->m_pNext.store( &node, atomics::memory_order_relaxed );
+                            else
+                                refBucket = &node;
                             return;
                         }
+                        prev = p;
                         p = p->m_pNext.load(atomics::memory_order_relaxed);
                     } while ( p );
 
-                    node.m_pNext.store( refBucket, atomics::memory_order_relaxed );
+                    assert( prev != nullptr );
+                    prev->m_pNext.store( &node, atomics::memory_order_relaxed );
                 }
-                refBucket = &node;
+                else
+                    refBucket = &node;
             }
 
-            item_type erase( guard_data::guarded_ptr ptr )
+            struct erase_result
+            {
+                item_type head;
+                item_type tail;
+                size_t    size;
+
+                erase_result()
+                    : head( nullptr )
+                    , tail( nullptr )
+                    , size(0)
+                {}
+            };
+
+            erase_result erase( guard_data::guarded_ptr ptr )
             {
                 item_type& refBucket = bucket( ptr );
                 item_type p = refBucket;
                 item_type pPrev = nullptr;
 
-                while ( p ) {
+                erase_result ret;
+                while ( p && p->m_ptr.m_p <= ptr ) {
                     if ( p->m_ptr.m_p == ptr ) {
                         if ( pPrev )
                             pPrev->m_pNext.store( p->m_pNext.load(atomics::memory_order_relaxed ), atomics::memory_order_relaxed );
                         else
                             refBucket = p->m_pNext.load(atomics::memory_order_relaxed);
-                        p->m_pNext.store( nullptr, atomics::memory_order_relaxed );
-                        return p;
+
+                        if ( ret.head )
+                            ret.tail->m_pNext.store( p, atomics::memory_order_relaxed );
+                        else
+                            ret.head = p;
+                        ret.tail = p;
+                        ++ret.size;
                     }
-                    pPrev = p;
+                    else
+                        pPrev = p;
                     p = p->m_pNext.load( atomics::memory_order_relaxed );
                 }
 
-                return nullptr;
+                if ( ret.tail )
+                    ret.tail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
+                return ret;
             }
 
             typedef std::pair<item_type, item_type>     list_range;
@@ -128,10 +155,10 @@ namespace cds { namespace gc { namespace dhp {
                 for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) {
                     item_type pBucket = *ppBucket;
                     if ( pBucket ) {
-                        if ( !ret.first )
-                            ret.first = pBucket;
-                        else
+                        if ( ret.first )
                             pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed );
+                        else
+                            ret.first = pBucket;
 
                         pTail = pBucket;
                         for (;;) {
@@ -139,11 +166,13 @@ namespace cds { namespace gc { namespace dhp {
                             pTail->m_ptr.free();
                             pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
 
+                            /*
                             while ( pTail->m_pNextFree.load( atomics::memory_order_relaxed )) {
                                 pTail = pTail->m_pNextFree.load( atomics::memory_order_relaxed );
                                 pTail->m_ptr.free();
                                 pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
                             }
+                            */
 
                             if ( pNext ) {
                                 pTail->m_pNextFree.store( pNext, atomics::memory_order_relaxed );
@@ -215,8 +244,9 @@ namespace cds { namespace gc { namespace dhp {
 
             // Liberate cycle
 
-            details::retired_ptr_node * pBusyFirst = nullptr;
-            details::retired_ptr_node * pBusyLast = nullptr;
+            details::retired_ptr_node dummy;
+            dummy.m_pNext.store( nullptr, atomics::memory_order_relaxed );
+            details::retired_ptr_node * pBusyLast = &dummy;
             size_t nBusyCount = 0;
 
             for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
@@ -225,31 +255,21 @@ namespace cds { namespace gc { namespace dhp {
                 details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
 
                 if ( valGuarded ) {
-                    details::retired_ptr_node * pRetired = set.erase( valGuarded );
-                    if ( pRetired ) {
+                    auto retired = set.erase( valGuarded );
+                    if ( retired.head ) {
                         // Retired pointer is being guarded
-                        // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
-                        // List is linked on m_pNextFree field
+                        // [retired.head, retired.tail] is the list linked by m_pNext field
 
-                        if ( pBusyLast )
-                            pBusyLast->m_pNext.store( pRetired, atomics::memory_order_relaxed );
-                        else
-                            pBusyFirst = pRetired;
-                        pBusyLast = pRetired;
-                        ++nBusyCount;
-                        details::retired_ptr_node * p = pBusyLast->m_pNextFree.load(atomics::memory_order_relaxed);
-                        while ( p != nullptr ) {
-                            pBusyLast->m_pNext.store( p, atomics::memory_order_relaxed );
-                            pBusyLast = p;
-                            ++nBusyCount;
-                        }
+                        pBusyLast->m_pNext.store( retired.head, atomics::memory_order_relaxed );
+                        pBusyLast = retired.tail;
+                        nBusyCount += retired.size;
                     }
                 }
             }
 
-            // Place [pBusyList, pBusyLast] back to m_RetiredBuffer
-            if ( pBusyFirst )
-                m_RetiredBuffer.push_list( pBusyFirst, pBusyLast, nBusyCount );
+            // Place [dummy.m_pNext, pBusyLast] back to m_RetiredBuffer
+            if ( nBusyCount )
+                m_RetiredBuffer.push_list( dummy.m_pNext.load(atomics::memory_order_relaxed), pBusyLast, nBusyCount );
 
             // Free all retired pointers
             details::liberate_set::list_range range = set.free_all();
index 5d65d6a..48a9150 100644 (file)
@@ -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 CDSIMPL_HP_CONST_H
@@ -35,7 +35,6 @@
     File: hp_const.h
 
     Michael's Hazard Pointer reclamation schema global constants
-    Gidenstam's reclamation schema global constants
 
     Editions:
         2008.03.10    Maxim.Khiszinsky    Created
@@ -47,10 +46,10 @@ namespace cds { namespace gc {
     // Hazard Pointers reclamation schema constants
     namespace hp {
         // Max number of threads expected
-        static const size_t c_nMaxThreadCount     = 100;
+        static CDS_CONSTEXPR const size_t c_nMaxThreadCount     = 100;
 
         // Number of Hazard Pointers per thread
-        static const size_t c_nHazardPointerPerThread = 8;
+        static CDS_CONSTEXPR const size_t c_nHazardPointerPerThread = 8;
     } // namespace hp
 
 } /* namespace gc */ }    /* namespace cds */
index 9921444..a525c1c 100644 (file)
@@ -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.
 */
 
 /*
@@ -195,7 +195,7 @@ namespace cds { namespace gc {
             while ( pNode ) {
                 for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) {
                     pRec->sync();
-                    void * hptr = pNode->m_hzp[i];
+                    void * hptr = pNode->m_hzp[i].get();
                     if ( hptr )
                         plist.push_back( hptr );
                 }
@@ -277,7 +277,7 @@ namespace cds { namespace gc {
                     if ( !pNode->m_bFree.load( atomics::memory_order_acquire ) ) {
                         for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) {
                             pRec->sync();
-                            void * hptr = pNode->m_hzp[i];
+                            void * hptr = pNode->m_hzp[i].get();
                             if ( hptr ) {
                                 dummyRetired.m_p = hptr;
                                 details::retired_vector::iterator it = std::lower_bound( itRetired, itRetiredEnd, dummyRetired, cds::gc::details::retired_ptr::less );
index 8416a4c..1db06f9 100644 (file)
@@ -357,6 +357,9 @@ namespace cds_test {
                 EXPECT_EQ( i.s.nUpdateExistsCall, 1 );
             }
 
+            // Apply retired pointer to clean links
+            List::gc::force_dispose();
+
             for ( auto& i : arr ) {
                 EXPECT_EQ( i.s.nUpdateExistsCall, 0 );
                 std::pair<bool, bool> ret = l.update( i, []( value_type& i, value_type * old ) {
index 1bfbe3a..b1c76b0 100644 (file)
@@ -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 CDSUNIT_SET_TEST_FELDMAN_HASHSET_H
index aa06b34..ecc1382 100644 (file)
@@ -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 CDSUNIT_SET_TEST_FELDMAN_HASHSET_HP_H