movable guarded_ptr: EllenBinTree
authorkhizmax <khizmax@gmail.com>
Mon, 17 Nov 2014 17:33:26 +0000 (20:33 +0300)
committerkhizmax <khizmax@gmail.com>
Mon, 17 Nov 2014 17:33:26 +0000 (20:33 +0300)
cds/container/impl/ellen_bintree_map.h
cds/container/impl/ellen_bintree_set.h
cds/gc/details/hp.h
cds/gc/guarded_ptr.h
cds/gc/impl/hp_decl.h
cds/intrusive/impl/ellen_bintree.h
tests/test-hdr/tree/hdr_ellenbintree_map.h
tests/test-hdr/tree/hdr_ellenbintree_set.h
tests/test-hdr/tree/hdr_intrusive_bintree.h
tests/test-hdr/tree/hdr_intrusive_ellen_bintree_dhp_member.cpp
tests/test-hdr/tree/hdr_intrusive_ellen_bintree_hp.cpp

index 3187f55..7f0b645 100644 (file)
@@ -318,70 +318,78 @@ namespace cds { namespace container {
 
         /// Extracts an item with minimal key from the map
         /**
-            If the map is not empty, the function returns \p true, \p result contains a pointer to minimum value.
-            If the map is empty, the function returns \p false, \p result is left unchanged.
+            If the map is not empty, the function returns an guarded pointer to minimum value.
+            If the map is empty, the function returns an empty \p guarded_ptr.
 
             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> minimum key.
             It means that the function gets leftmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
             So, the function returns the item with minimum key at the moment of tree traversing.
 
-            The guarded pointer \p result prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_min( guarded_ptr& result )
+        guarded_ptr extract_min()
         {
-            return base_class::extract_min_( result.guard() );
+            guarded_ptr gp;
+            base_class::extract_min_( gp.guard() );
+            return gp;
         }
 
         /// Extracts an item with maximal key from the map
         /**
-            If the map is not empty, the function returns \p true, \p result contains a pointer to maximal value.
-            If the map is empty, the function returns \p false, \p result is left unchanged.
+            If the map is not empty, the function returns a guarded pointer to maximal value.
+            If the map is empty, the function returns an empty \p guarded_ptr.
 
             @note Due the concurrent nature of the map, the function extracts <i>nearly</i> maximal key.
             It means that the function gets rightmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
             So, the function returns the item with maximum key at the moment of tree traversing.
 
-            The guarded pointer \p result prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_max( guarded_ptr& result )
+        guarded_ptr extract_max()
         {
-            return base_class::extract_max_( result.guard() );
+            guarded_ptr gp;
+            base_class::extract_max_( gp.guard() );
+            return gp;
         }
 
         /// Extracts an item from the tree
         /** \anchor cds_nonintrusive_EllenBinTreeMap_extract
             The function searches an item with key equal to \p key in the tree,
-            unlinks it, and returns pointer to an item found in \p result parameter.
-            If the item  is not found the function returns \p false.
+            unlinks it, and returns a guarded pointer to an item found.
+            If the item  is not found the function returns an empty \p guarded_ptr.
 
-            The guarded pointer \p result prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool extract( guarded_ptr& result, Q const& key )
+        guarded_ptr extract( Q const& key )
         {
-            return base_class::extract_( result.guard(), key );
+            guarded_ptr gp;
+            base_class::extract_( gp.guard(), key );
+            return gp;
         }
 
         /// Extracts an item from the map using \p pred for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(guarded_ptr&, Q const&)"
+            The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_extract "extract(Q const&)"
             but \p pred is used for key compare.
             \p Less has the interface like \p std::less.
             \p pred must imply the same element order as the comparator used for building the map.
         */
         template <typename Q, typename Less>
-        bool extract_with( guarded_ptr& result, Q const& key, Less pred )
+        guarded_ptr extract_with( Q const& key, Less pred )
         {
-            return base_class::extract_with_( result.guard(), key,
+            guarded_ptr gp;
+            base_class::extract_with_( gp.guard(), key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >());
+            return gp;
         }
 
         /// Find the key \p key
@@ -447,31 +455,35 @@ namespace cds { namespace container {
 
         /// Finds \p key and returns the item found
         /** @anchor cds_nonintrusive_EllenBinTreeMap_get
-            The function searches the item with key equal to \p key and returns the item found in \p result parameter.
-            The function returns \p true if \p key is found, \p false otherwise.
+            The function searches the item with key equal to \p key and returns the item found as a guarded pointer.
+            If \p key is not foudn the function returns an empty \p guarded_ptr.
 
-            The guarded pointer \p result prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool get( guarded_ptr& result, Q const& key )
+        guarded_ptr get( Q const& key )
         {
-            return base_class::get_( result.guard(), key );
+            guarded_ptr gp;
+            base_class::get_( gp.guard(), key );
+            return gp;
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
         /**
-            The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(guarded_ptr&, Q const&)"
+            The function is an analog of \ref cds_nonintrusive_EllenBinTreeMap_get "get(Q const&)"
             but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less.
             \p pred must imply the same element order as the comparator used for building the map.
         */
         template <typename Q, typename Less>
-        bool get_with( guarded_ptr& result, Q const& key, Less pred )
+        guarded_ptr get_with( Q const& key, Less pred )
         {
-            return base_class::get_with_( result.guard(), key,
+            guarded_ptr gp;
+            base_class::get_with_( gp.guard(), key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::key_accessor >() );
+            return gp;
         }
 
         /// Clears the map (not atomic)
index 432947e..72c5f4e 100644 (file)
@@ -332,70 +332,78 @@ namespace cds { namespace container {
 
         /// Extracts an item with minimal key from the set
         /**
-            If the set is not empty, the function returns \p true, \p result contains a pointer to minimum value.
-            If the set is empty, the function returns \p false, \p result is left unchanged.
+            If the set is not empty, the function returns a guarded pointer to minimum value.
+            If the set is empty, the function returns an empty \p guarded_ptr.
 
             @note Due the concurrent nature of the set, the function extracts <i>nearly</i> minimum key.
             It means that the function gets leftmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
             So, the function returns the item with minimum key at the moment of tree traversing.
 
-            The guarded pointer \p dest prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_min( guarded_ptr& result )
+        guarded_ptr extract_min()
         {
-            return base_class::extract_min_( result.guard() );
+            guarded_ptr gp;
+            base_class::extract_min_( gp.guard() );
+            return gp;
         }
 
         /// Extracts an item with maximal key from the set
         /**
-            If the set is not empty, the function returns \p true, \p result contains a pointer to maximal value.
-            If the set is empty, the function returns \p false, \p result is left unchanged.
+            If the set is not empty, the function returns a guarded pointer to maximal value.
+            If the set is empty, the function returns an empty \p guarded_ptr.
 
             @note Due the concurrent nature of the set, the function extracts <i>nearly</i> maximal key.
             It means that the function gets rightmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key great than leftmost item's key.
             So, the function returns the item with maximum key at the moment of tree traversing.
 
-            The guarded pointer \p dest prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_max( guarded_ptr& result )
+        guarded_ptr extract_max()
         {
-            return base_class::extract_max_( result.guard() );
+            guarded_ptr gp;
+            base_class::extract_max_( gp.guard() );
+            return gp;
         }
 
         /// Extracts an item from the tree
         /** \anchor cds_nonintrusive_EllenBinTreeSet_extract
             The function searches an item with key equal to \p key in the tree,
-            unlinks it, and returns pointer to an item found in \p result parameter.
-            If the item  is not found the function returns \p false.
+            unlinks it, and returns an guarded pointer to it.
+            If the item  is not found the function returns an empty \p guarded_ptr.
 
-            The guarded pointer \p dest prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool extract( guarded_ptr& result, Q const& key )
+        guarded_ptr extract( Q const& key )
         {
-            return base_class::extract_( result.guard(), key );
+            guarded_ptr gp;
+            base_class::extract_( gp.guard(), key );
+            return gp;
         }
 
         /// Extracts an item from the set using \p pred for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(guarded_ptr& dest, Q const&)"
+            The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_extract "extract(Q const&)"
             but \p pred is used for key compare.
             \p Less has the interface like \p std::less.
             \p pred must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less>
-        bool extract_with( guarded_ptr& result, Q const& key, Less pred )
+        guarded_ptr extract_with( Q const& key, Less pred )
         {
-            return base_class::extract_with_( result.guard(), key,
+            guarded_ptr gp;
+            base_class::extract_with_( gp.guard(), key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >());
+            return gp;
         }
 
         /// Find the key \p key
@@ -489,31 +497,35 @@ namespace cds { namespace container {
 
         /// Finds \p key and returns the item found
         /** @anchor cds_nonintrusive_EllenBinTreeSet_get
-            The function searches the item with key equal to \p key and returns the item found in \p result parameter.
+            The function searches the item with key equal to \p key and returns the item found as an guarded pointer.
             The function returns \p true if \p key is found, \p false otherwise.
 
-            The guarded pointer \p dest prevents deallocation of returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The guarded pointer prevents deallocation of returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool get( guarded_ptr& result, Q const& key )
+        guarded_ptr get( Q const& key )
         {
-            return base_class::get_( result.guard(), key );
+            guarded_ptr gp;
+            base_class::get_( gp.guard(), key );
+            return gp;
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
         /**
-            The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(guarded_ptr&, Q const&)"
+            The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_get "get(Q const&)"
             but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less.
             \p pred must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less>
-        bool get_with( guarded_ptr& result, Q const& key, Less pred )
+        guarded_ptr get_with( Q const& key, Less pred )
         {
-            return base_class::get_with_( result.guard(), key,
+            guarded_ptr gp;
+            base_class::get_with_( gp.guard(), key,
                 cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() );
+            return gp;
         }
 
         /// Clears the set (not atomic)
index 9e191b0..ab475a3 100644 (file)
@@ -613,7 +613,7 @@ namespace cds {
         */
         class guard
         {
-            details::hp_guard&   m_hp    ; ///< Hazard pointer guarded
+            details::hp_guard&  m_hp    ; ///< Hazard pointer guarded
             ThreadGC&           m_gc    ; ///< Thread GC
 
         public:
index b578103..82925e0 100644 (file)
@@ -15,7 +15,7 @@ namespace cds { namespace gc {
         After destructing \p %guarded_ptr object the pointer can be automatically disposed (freed) at any time.
 
         Template arguments:
-        - \p GC - a garbage collector type like cds::gc::HP and any other from cds::gc namespace
+        - \p GC - a garbage collector type like \p cds::gc::HP and any other from cds::gc namespace
         - \p GuardedType - a type which the guard stores
         - \p ValueType - a value type
         - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
@@ -52,10 +52,10 @@ namespace cds { namespace gc {
     {
         //TODO: use moce semantics and explicit operator bool!
     public:
-        typedef GC          gc         ;   ///< Garbage collector like cds::gc::HP and any other from cds::gc namespace
-        typedef GuardedType guarded_type;  ///< Guarded type
-        typedef ValueType   value_type ;   ///< Value type
-        typedef Cast        value_cast ;   ///< Functor for casting \p guarded_type to \p value_type
+        typedef GC          gc;           ///< Garbage collector like cds::gc::HP and any other from cds::gc namespace
+        typedef GuardedType guarded_type; ///< Guarded type
+        typedef ValueType   value_type;   ///< Value type
+        typedef Cast        value_cast;   ///< Functor for casting \p guarded_type to \p value_type
 
     private:
         //@cond
@@ -67,18 +67,26 @@ namespace cds { namespace gc {
         guarded_ptr() CDS_NOEXCEPT
         {}
 
+        //@cond
         /// Initializes guarded pointer with \p p
         guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
         {
             m_guard.assign( p );
         }
+        guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
+        {}
+        //@endcond
 
-        /// Copy constructor
-        guarded_ptr( guarded_ptr const& gp ) CDS_NOEXCEPT
+        /// Move ctor
+        guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
         {
-            m_guard.copy( gp.m_guard );
+            m_guard.assign( gp.m_guard.get_native() );
+            gp.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
@@ -88,13 +96,17 @@ namespace cds { namespace gc {
             release();
         }
 
-        /// Assignment operator
-        guarded_ptr& operator=( guarded_ptr const& gp ) CDS_NOEXCEPT
+        /// Move-assignment operator
+        guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
         {
-            m_guard.copy( gp.m_guard );
+            m_guard.assign( gp.m_guard.get_native() );
+            gp.release();
             return *this;
         }
 
+        /// The guarded pointer is not copy-assignable
+        guarded_ptr& operator=(guarded_ptr const& gp) = delete;
+
         /// Returns a pointer to guarded value
         value_type * operator ->() const CDS_NOEXCEPT
         {
@@ -121,6 +133,12 @@ namespace cds { namespace gc {
             return m_guard.template get<guarded_type>() == nullptr;
         }
 
+        /// \p bool operator returns <tt>!empty()</tt>
+        explicit operator bool() const CDS_NOEXCEPT
+        {
+            return !empty();
+        }
+
         /// Clears guarded pointer
         /**
             If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
@@ -163,22 +181,28 @@ namespace cds { namespace gc {
             m_guard.assign( p );
         }
 
-        guarded_ptr( guarded_ptr const& gp ) CDS_NOEXCEPT
+        guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
         {
-            m_guard.copy( gp.m_guard );
+            m_guard.assign( gp.m_guard.get_native() );
+            gp.release();
         }
 
+        guarded_ptr( guarded_ptr const& gp ) = delete;
+
         ~guarded_ptr() CDS_NOEXCEPT
         {
             release();
         }
 
-        guarded_ptr& operator=( guarded_ptr const& gp ) CDS_NOEXCEPT
+        guarded_ptr& operator=(guarded_ptr&& gp) CDS_NOEXCEPT
         {
-            m_guard.copy( gp.m_guard );
+            m_guard.assign( gp.m_guard.get_native() );
+            gp.release();
             return *this;
         }
 
+        guarded_ptr& operator=(guarded_ptr const& gp) = delete;
+
         value_type * operator ->() const CDS_NOEXCEPT
         {
             return m_guard.template get<value_type>();
@@ -201,6 +225,11 @@ namespace cds { namespace gc {
             return m_guard.template get<guarded_type>() == nullptr;
         }
 
+        explicit operator bool() const CDS_NOEXCEPT
+        {
+            return !empty();
+        }
+
         void release() CDS_NOEXCEPT
         {
             m_guard.clear();
index 14c9831..c139736 100644 (file)
@@ -146,7 +146,7 @@ namespace cds { namespace gc {
                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 
                 The function is useful for intrusive containers when \p toGuard is a node pointer
-                that should be converted to a pointer to the value type before protecting.
+                that should be converted to a pointer to the value before protecting.
                 The parameter \p f of type Func is a functor that makes this conversion:
                 \code
                     struct functor {
index e6f2e99..38df2b5 100644 (file)
@@ -549,70 +549,78 @@ namespace cds { namespace intrusive {
 
         /// Extracts an item with minimal key from the tree
         /**
-            The function searches an item with minimal key, unlinks it, and returns pointer to an item found in \p dest parameter.
-            If the tree is empty the function returns \p false.
+            The function searches an item with minimal key, unlinks it, and returns a guarded pointer to an item found.
+            If the tree is empty the function returns an empty guarded pointer.
 
             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> minimum key.
             It means that the function gets leftmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
             So, the function returns the item with minimum key at the moment of tree traversing.
 
-            The guarded pointer \p dest prevents disposer invocation for returned item,
-            see cds::gc::guarded_ptr for explanation.
+            The returned \p guarded_ptr prevents disposer invocation for returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_min( guarded_ptr& dest )
+        guarded_ptr extract_min()
         {
-            return extract_min_( dest.guard());
+            guarded_ptr gp;
+            extract_min_( gp.guard() );
+            return gp;
         }
 
         /// Extracts an item with maximal key from the tree
         /**
-            The function searches an item with maximal key, unlinks it, and returns pointer to an item found in \p dest parameter.
-            If the tree is empty the function returns \p false.
+            The function searches an item with maximal key, unlinks it, and returns a guarded pointer to an item found.
+            If the tree is empty the function returns an empty \p guarded_ptr.
 
             @note Due the concurrent nature of the tree, the function extracts <i>nearly</i> maximal key.
             It means that the function gets rightmost leaf of the tree and tries to unlink it.
             During unlinking, a concurrent thread may insert an item with key great than rightmost item's key.
             So, the function returns the item with maximal key at the moment of tree traversing.
 
-            The guarded pointer \p dest prevents disposer invocation for returned item,
+            The returned \p guarded_ptr prevents disposer invocation for returned item,
             see cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
-        bool extract_max( guarded_ptr& dest )
+        guarded_ptr extract_max()
         {
-            return extract_max_( dest.guard() );
+            guarded_ptr gp;
+            extract_max_( gp.guard());
+            return gp;
         }
 
         /// Extracts an item from the tree
         /** \anchor cds_intrusive_EllenBinTree_extract
             The function searches an item with key equal to \p key in the tree,
-            unlinks it, and returns pointer to an item found in \p dest parameter.
-            If the item  is not found the function returns \p false.
+            unlinks it, and returns a guarded pointer to an item found.
+            If the item  is not found the function returns an empty \p guarded_ptr.
 
-            The guarded pointer \p dest prevents disposer invocation for returned item,
+            \p guarded_ptr prevents disposer invocation for returned item,
             see cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool extract( guarded_ptr& dest, Q const& key )
+        guarded_ptr extract( Q const& key )
         {
-            return extract_( dest.guard(), key );
+            guarded_ptr gp;
+            extract_( gp.guard(), key );
+            return gp;
         }
 
         /// Extracts an item from the tree using \p pred for searching
         /**
-            The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(guarded_ptr& dest, Q const&)"
+            The function is an analog of \ref cds_intrusive_EllenBinTree_extract "extract(Q const&)"
             but \p pred is used for key compare.
             \p Less has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
             "Predicate requirements".
             \p pred must imply the same element order as the comparator used for building the tree.
         */
         template <typename Q, typename Less>
-        bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
+        guarded_ptr extract_with( Q const& key, Less pred )
         {
-            return extract_with_( dest.guard(), key, pred );
+            guarded_ptr gp;
+            extract_with_( gp.guard(), key, pred );
+            return gp;
         }
 
         /// Finds the key \p key
@@ -718,31 +726,35 @@ namespace cds { namespace intrusive {
 
         /// Finds \p key and returns the item found
         /** @anchor cds_intrusive_EllenBinTree_get
-            The function searches the item with key equal to \p key and returns the item found in \p dest parameter.
-            The function returns \p true if \p key is found, \p false otherwise.
+            The function searches the item with key equal to \p key and returns the item found as \p guarded_ptr object.
+            The function returns an empty guarded pointer is \p key is not found.
 
-            The guarded pointer \p dest prevents disposer invocation for returned item,
-            see cds::gc::guarded_ptr for explanation.
+            \p guarded_ptr prevents disposer invocation for returned item,
+            see \p cds::gc::guarded_ptr for explanation.
             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
         */
         template <typename Q>
-        bool get( guarded_ptr& dest, Q const& key ) const
+        guarded_ptr get( Q const& key ) const
         {
-            return get_( dest.guard(), key );
+            guarded_ptr gp;
+            get_( gp.guard(), key );
+            return gp;
         }
 
         /// Finds \p key with predicate \p pred and returns the item found
         /**
-            The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(guarded_ptr&, Q const&)"
+            The function is an analog of \ref cds_intrusive_EllenBinTree_get "get(Q const&)"
             but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less and should meet \ref cds_intrusive_EllenBinTree_less
             "Predicate requirements".
             \p pred must imply the same element order as the comparator used for building the tree.
         */
         template <typename Q, typename Less>
-        bool get_with( guarded_ptr& dest, Q const& key, Less pred ) const
+        guarded_ptr get_with( Q const& key, Less pred ) const
         {
-            return get_with_( dest.guard(), key, pred );
+            guarded_ptr gp;
+            get_with_( gp.guard(), key, pred );
+            return gp;
         }
 
         /// Checks if the tree is empty
@@ -767,7 +779,9 @@ namespace cds { namespace intrusive {
         void clear()
         {
             guarded_ptr gp;
-            while ( extract_min(gp));
+            do {
+                gp = extract_min();
+            }  while ( gp );
         }
 
         /// Clears the tree (not thread safe)
@@ -1315,6 +1329,7 @@ namespace cds { namespace intrusive {
         template <typename Q>
         bool extract_( typename gc::Guard& guard, Q const& key )
         {
+            guarded_ptr gp;
             return erase_( key, node_compare(),
                 []( Q const&, leaf_node const& ) -> bool { return true; },
                 [&guard]( value_type& found ) { guard.assign( &found ); } );
@@ -1335,7 +1350,7 @@ namespace cds { namespace intrusive {
                 [&guard]( value_type& found ) { guard.assign( &found ); } );
         }
 
-        bool extract_max_( typename gc::Guard& guard )
+        bool extract_max_( typename gc::Guard& gp )
         {
             update_desc * pOp = nullptr;
             search_result res;
@@ -1381,11 +1396,11 @@ namespace cds { namespace intrusive {
 
             --m_ItemCounter;
             m_Stat.onExtractMaxSuccess();
-            guard.assign( node_traits::to_value_ptr( res.pLeaf ) );
+            gp.assign( node_traits::to_value_ptr( res.pLeaf ));
             return true;
         }
 
-        bool extract_min_( typename gc::Guard& guard )
+        bool extract_min_( typename gc::Guard& gp )
         {
             update_desc * pOp = nullptr;
             search_result res;
@@ -1431,7 +1446,7 @@ namespace cds { namespace intrusive {
 
             --m_ItemCounter;
             m_Stat.onExtractMinSuccess();
-            guard.assign( node_traits::to_value_ptr( res.pLeaf ));
+            gp.assign( node_traits::to_value_ptr( res.pLeaf ));
             return true;
         }
 
index cf0ccaf..d4849aa 100644 (file)
@@ -386,11 +386,11 @@ namespace tree {
                 int i = 0;
                 std::pair<key_type, value_type> v;
                 while ( !m.empty() ) {
-                    CPPUNIT_ASSERT( m.extract_min( gp ) );
+                    gp = m.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_ASSERT( gp->first == i );
                     ++i;
-                    gp.release();
                 }
                 CPPUNIT_ASSERT( m.empty() );
                 CPPUNIT_ASSERT( check_size( m, 0 ));
@@ -399,11 +399,11 @@ namespace tree {
                 fill_map( m, arr );
                 i = (int) c_nItemCount - 1;
                 while ( !m.empty() ) {
-                    CPPUNIT_ASSERT( m.extract_max( gp ) );
+                    gp = m.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_ASSERT( gp->first == i );
                     --i;
-                    gp.release();
                 }
                 CPPUNIT_ASSERT( m.empty() );
                 CPPUNIT_ASSERT( check_size( m, 0 ));
@@ -411,19 +411,20 @@ namespace tree {
                 fill_map( m, arr );
                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
                     int nKey = arr[i];
-                    CPPUNIT_ASSERT( m.get( gp, nKey ));
+                    gp = m.get( nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->first == nKey );
 
-                    gp.release();
-                    CPPUNIT_ASSERT( m.extract( gp, nKey ));
+                    gp = m.extract( nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->first == nKey );
 
-                    gp.release();
-                    CPPUNIT_CHECK( !m.get( gp, nKey ));
+                    gp = m.get( nKey );
+                    CPPUNIT_CHECK( !gp );
                     CPPUNIT_CHECK( gp.empty());
-                    CPPUNIT_CHECK( !m.extract( gp, nKey ));
+                    CPPUNIT_CHECK( !m.extract( nKey ));
                     CPPUNIT_CHECK( gp.empty());
                 }
                 CPPUNIT_ASSERT( m.empty() );
@@ -432,19 +433,20 @@ namespace tree {
                 fill_map( m, arr );
                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
                     int nKey = arr[i];
-                    CPPUNIT_ASSERT( m.get_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = m.get_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->first == nKey );
 
-                    gp.release();
-                    CPPUNIT_ASSERT( m.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = m.extract_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->first == nKey );
 
-                    gp.release();
-                    CPPUNIT_CHECK( !m.get_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = m.get_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_CHECK( !gp );
                     CPPUNIT_CHECK( gp.empty());
-                    CPPUNIT_CHECK( !m.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    CPPUNIT_CHECK( !m.extract_with( wrapped_int(nKey), wrapped_less() ));
                     CPPUNIT_CHECK( gp.empty());
                 }
 
index 12dc860..08658ef 100644 (file)
@@ -495,7 +495,8 @@ namespace tree {
 
                 int i = 0;
                 while ( !s.empty() ) {
-                    CPPUNIT_ASSERT( s.extract_min( gp ) );
+                    gp = s.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( gp->nKey == i );
                     ++i;
                 }
@@ -505,7 +506,8 @@ namespace tree {
                 fill_set( s, arr );
                 i = (int) c_nItemCount - 1;
                 while ( !s.empty() ) {
-                    CPPUNIT_ASSERT( s.extract_max( gp ) );
+                    gp = s.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( gp->nKey == i );
                     --i;
                 }
@@ -515,19 +517,20 @@ namespace tree {
                 fill_set( s, arr );
                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
                     int nKey = arr[i];
-                    CPPUNIT_ASSERT( s.get( gp, nKey ));
+                    gp = s.get( nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == nKey );
 
-                    gp.release();
-                    CPPUNIT_ASSERT( s.extract( gp, nKey ));
+                    gp = s.extract( nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == nKey );
 
-                    gp.release();
-                    CPPUNIT_CHECK( !s.get( gp, nKey ));
+                    gp = s.get( nKey );
+                    CPPUNIT_CHECK( !gp );
                     CPPUNIT_CHECK( gp.empty());
-                    CPPUNIT_CHECK( !s.extract( gp, nKey ));
+                    CPPUNIT_CHECK( !s.extract( nKey ));
                     CPPUNIT_CHECK( gp.empty());
                 }
                 CPPUNIT_ASSERT( s.empty() );
@@ -536,19 +539,20 @@ namespace tree {
                 fill_set( s, arr );
                 for ( int i = 0; i < static_cast<int>( c_nItemCount ); ++i ) {
                     int nKey = arr[i];
-                    CPPUNIT_ASSERT( s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = s.get_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == nKey );
 
-                    gp.release();
-                    CPPUNIT_ASSERT( s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = s.extract_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == nKey );
 
-                    gp.release();
-                    CPPUNIT_CHECK( !s.get_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    gp = s.get_with( wrapped_int( nKey ), wrapped_less() );
+                    CPPUNIT_CHECK( !gp );
                     CPPUNIT_CHECK( gp.empty());
-                    CPPUNIT_CHECK( !s.extract_with( gp, wrapped_int(nKey), wrapped_less() ));
+                    CPPUNIT_CHECK( !s.extract_with( wrapped_int(nKey), wrapped_less() ));
                     CPPUNIT_CHECK( gp.empty());
                 }
                 CPPUNIT_ASSERT( s.empty() );
index bbc010c..78a17c5 100644 (file)
@@ -673,50 +673,58 @@ namespace tree {
                 {
                     typename tree_type::guarded_ptr gp;
 
-                    CPPUNIT_ASSERT( t.get( gp, v2.nKey ));
+                    gp = t.get( v2.nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == v2.nKey );
-                    gp.release();
-                    CPPUNIT_ASSERT( t.extract( gp, v2.nKey ));
+                    gp = t.extract( v2.nKey );
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
-                    CPPUNIT_ASSERT( !t.extract( gp, v2.nKey ));
-                    CPPUNIT_CHECK( !t.get( gp, v2.nKey ));
+                    gp = t.extract( v2.nKey );
+                    CPPUNIT_ASSERT( !gp );
+                    gp = t.get( v2.nKey );
+                    CPPUNIT_CHECK( !gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
 
-                    CPPUNIT_ASSERT( t.extract_min(gp));
+                    gp = t.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
                     CPPUNIT_ASSERT( gp->nKey == v5.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_min(gp));
+                    gp = t.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_min(gp));
+                    gp = t.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_min(gp));
+                    gp = t.extract_min();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
 
-                    CPPUNIT_ASSERT( !t.extract_min(gp));
-                    CPPUNIT_ASSERT( !t.extract_max(gp));
-                    CPPUNIT_ASSERT( !t.extract( gp, v1.nKey ));
+                    gp = t.extract_min();
+                    CPPUNIT_ASSERT( !gp );
+                    CPPUNIT_ASSERT( !t.extract_max());
+                    CPPUNIT_ASSERT( !t.extract( v1.nKey ));
                 }
 
                 tree_type::gc::force_dispose();
@@ -733,38 +741,45 @@ namespace tree {
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 5 ));
 
-                    CPPUNIT_ASSERT( t.get_with( gp, wrapped_int(v4.nKey), wrapped_less<value_type>() ));
+                    gp = t.get_with( wrapped_int( v4.nKey ), wrapped_less<value_type>());
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == v4.nKey );
-                    CPPUNIT_ASSERT( t.extract_with( gp, wrapped_int(v4.nKey), wrapped_less<value_type>() ));
+                    gp = t.extract_with( wrapped_int( v4.nKey ), wrapped_less<value_type>());
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 4 ));
                     CPPUNIT_ASSERT( gp->nKey == v4.nKey );
 
-                    CPPUNIT_ASSERT( !t.extract_with( gp, v4.nKey, less<value_type>() ) );
+                    gp = t.extract_with( v4.nKey, less<value_type>());
+                    CPPUNIT_ASSERT( !gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
-                    CPPUNIT_ASSERT( !t.get_with( gp, v4.nKey, less<value_type>() ) );
+                    CPPUNIT_ASSERT( !t.get_with( v4.nKey, less<value_type>() ) );
 
-                    CPPUNIT_ASSERT( t.extract_max(gp));
+                    gp = t.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 3 ));
                     CPPUNIT_ASSERT( gp->nKey == v3.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_max(gp) );
+                    gp = t.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 2 ));
                     CPPUNIT_ASSERT( gp->nKey == v2.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_max(gp) );
+                    gp = t.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( !t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 1 ));
                     CPPUNIT_ASSERT( gp->nKey == v1.nKey );
 
-                    CPPUNIT_ASSERT( t.extract_max(gp) );
+                    gp = t.extract_max();
+                    CPPUNIT_ASSERT( gp );
                     CPPUNIT_ASSERT( t.check_consistency() );
                     CPPUNIT_ASSERT( t.empty() );
                     CPPUNIT_ASSERT( misc::check_size( t, 0 ));
@@ -783,8 +798,7 @@ namespace tree {
                     CPPUNIT_ASSERT( t.ensure( *p, ensure_functor()).second );
                 }
                 for ( int n = 0; n < (int) c_nItemCount; ++n ) {
-                    typename tree_type::guarded_ptr gp;
-                    CPPUNIT_ASSERT( t.extract_min(gp));
+                    typename tree_type::guarded_ptr gp( t.extract_min() );
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == n );
                 }
@@ -793,8 +807,7 @@ namespace tree {
                     CPPUNIT_ASSERT( t.insert( *p ) );
                 }
                 for ( int n = (int) c_nItemCount - 1; n >= 0; --n ) {
-                    typename tree_type::guarded_ptr gp;
-                    CPPUNIT_ASSERT( t.extract_max(gp));
+                    typename tree_type::guarded_ptr gp( t.extract_max());
                     CPPUNIT_ASSERT( !gp.empty());
                     CPPUNIT_CHECK( gp->nKey == n );
                 }
index f07e18c..79b3765 100644 (file)
@@ -24,7 +24,7 @@ namespace tree {
         };
 
         typedef ci::ellen_bintree::internal_node< IntrusiveBinTreeHdrTest::key_type, leaf_node > internal_node;
-        typedef ci::ellen_bintree::update_desc< leaf_node, internal_node >   update_desc;
+        typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
     }
 
     void IntrusiveBinTreeHdrTest::EllenBinTree_dhp_member_less()
index 2134c97..d813cb2 100644 (file)
@@ -22,7 +22,7 @@ namespace tree {
         };
 
         typedef ci::ellen_bintree::internal_node< IntrusiveBinTreeHdrTest::key_type, leaf_node > internal_node;
-        typedef ci::ellen_bintree::update_desc< leaf_node, internal_node >   update_desc;
+        typedef ci::ellen_bintree::update_desc< leaf_node, internal_node > update_desc;
     }
 
     void IntrusiveBinTreeHdrTest::EllenBinTree_hp_base_less()