Renamed get_result typedef to raw_ptr

[libcds.git] / cds / container / michael_kvlist_rcu.h

diff --git a/cds/container/michael_kvlist_rcu.h b/cds/container/michael_kvlist_rcu.h
index 7545e48c7fcb0b0b1f8086f4e209b1da3072591c..6c4f61b8be612dc54307ac0df5203ad6a34b9cc1 100644 (file)
--- a/cds/container/michael_kvlist_rcu.h
+++ b/cds/container/michael_kvlist_rcu.h
@@ -1,7 +1,7 @@
 //$$CDS-header$$
 
 //$$CDS-header$$
 

-#ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
-#define __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
+#ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H
+#define CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H

 
 #include <memory>
 #include <functional>   // ref
 
 #include <memory>
 #include <functional>   // ref


@@ -105,15 +105,15 @@ namespace cds { namespace container {
 #endif
         typedef Traits traits; ///< List traits
 
 #endif
         typedef Traits traits; ///< List traits
 

-        typedef typename base_class::back_off       back_off;       ///< Back-off strategy
-        typedef typename maker::allocator_type    allocator_type;   ///< Allocator type used for allocate/deallocate the nodes
-        typedef typename base_class::item_counter   item_counter;   ///< Item counting policy
-        typedef typename maker::key_comparator    key_comparator;   ///< key comparison functor
-        typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See \p michael_list::traits::memory_model
+        typedef typename base_class::back_off     back_off;       ///< Back-off strategy
+        typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
+        typedef typename base_class::item_counter item_counter;   ///< Item counting policy
+        typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
+        typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See \p michael_list::traits::memory_model

         typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
 
         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
         typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
 
         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock

-        static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
+        static CDS_CONSTEXPR const bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions do not require external locking

 
     protected:
         //@cond
 
     protected:
         //@cond


@@ -131,6 +131,31 @@ namespace cds { namespace container {
             cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
         >;
 
             cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
         >;
 

+    private:
+        //@cond
+        struct raw_ptr_converter
+        {
+            value_type * operator()( node_type * p ) const
+            {
+               return p ? &p->m_Data : nullptr;
+            }
+
+            value_type& operator()( node_type& n ) const
+            {
+                return n.m_Data;
+            }
+
+            value_type const& operator()( node_type const& n ) const
+            {
+                return n.m_Data;
+            }
+        };
+        //@endcond
+
+    public:
+        /// Result of \p get(), \p get_with() functions - pointer to the node found
+        typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr;
+

     protected:
         //@cond
         template <typename K>
     protected:
         //@cond
         template <typename K>


@@ -327,7 +352,7 @@ namespace cds { namespace container {
                 In trivial case, \p K is equal to \ref key_type.
             - The \ref mapped_type should be default-constructible.
 
                 In trivial case, \p K is equal to \ref key_type.
             - The \ref mapped_type should be default-constructible.
 

-            The function makes RCU lock internally.
+            The function applies RCU lock internally.

 
             Returns \p true if inserting successful, \p false otherwise.
         */
 
             Returns \p true if inserting successful, \p false otherwise.
         */


@@ -345,7 +370,7 @@ namespace cds { namespace container {
             - The \ref key_type should be constructible from \p key of type \p K.
             - The \ref mapped_type should be constructible from \p val of type \p V.
 
             - The \ref key_type should be constructible from \p key of type \p K.
             - The \ref mapped_type should be constructible from \p val of type \p V.
 

-            The function makes RCU lock internally.
+            The function applies RCU lock internally.

 
             Returns \p true if inserting successful, \p false otherwise.
         */
 
             Returns \p true if inserting successful, \p false otherwise.
         */


@@ -380,14 +405,14 @@ namespace cds { namespace container {
             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
             it is preferable that the initialization should be completed only if inserting is successful.
 
             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
             it is preferable that the initialization should be completed only if inserting is successful.
 

-            The function makes RCU lock internally.
+            The function applies RCU lock internally.

 
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>
 
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>

-        bool insert_key( const K& key, Func func )
+        bool insert_with( const K& key, Func func )

         {
         {

-            return insert_key_at( head(), key, func );
+            return insert_with_at( head(), key, func );

         }
 
         /// Ensures that the \p key exists in the list
         }
 
         /// Ensures that the \p key exists in the list


@@ -417,7 +442,7 @@ namespace cds { namespace container {
             however, \p func must guarantee that during changing no any other modifications
             could be made on this item by concurrent threads.
 
             however, \p func must guarantee that during changing no any other modifications
             could be made on this item by concurrent threads.
 

-            The function makes RCU lock internally.
+            The function applies RCU lock internally.

 
             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
             \p second is true if new item has been added or \p false if the item with \p key
 
             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
             \p second is true if new item has been added or \p false if the item with \p key


@@ -435,7 +460,7 @@ namespace cds { namespace container {
         /**
             Returns \p true if inserting successful, \p false otherwise.
 
         /**
             Returns \p true if inserting successful, \p false otherwise.
 

-            The function makes RCU lock internally.
+            The function applies RCU lock internally.

         */
         template <typename K, typename... Args>
         bool emplace( K&& key, Args&&... args )
         */
         template <typename K, typename... Args>
         bool emplace( K&& key, Args&&... args )


@@ -477,7 +502,7 @@ namespace cds { namespace container {
 
             The functor \p Func interface:
             \code
 
             The functor \p Func interface:
             \code

-            struct extractor {
+            struct functor {

                 void operator()(value_type& val) { ... }
             };
             \endcode
                 void operator()(value_type& val) { ... }
             };
             \endcode


@@ -515,10 +540,9 @@ namespace cds { namespace container {
             unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
             If \p key is not found the function returns an empty \p exempt_ptr.
 
             unlinks it from the list, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
             If \p key is not found the function returns an empty \p exempt_ptr.
 

-            @note The function does NOT call RCU read-side lock or synchronization,
-            and does NOT dispose the item found. It just excludes the item from the list
-            and returns a pointer to item found.
-            You should lock RCU before calling this function.
+            @note The function does NOT dispose the item found. 
+            It just excludes the item from the list and returns a pointer to item found.
+            You shouldn't lock RCU before calling this function.

 
             \code
             #include <cds/urcu/general_buffered.h>
 
             \code
             #include <cds/urcu/general_buffered.h>


@@ -531,19 +555,18 @@ namespace cds { namespace container {
             // ...
 
             rcu_michael_list::exempt_ptr p;
             // ...
 
             rcu_michael_list::exempt_ptr p;

-            {
-                // first, we should lock RCU
-                rcu_michael_list::rcu_lock sl;
-
-                // Now, you can apply extract function
-                // Note that you must not delete the item found inside the RCU lock
-                p = theList.extract( 10 );
-                if ( p ) {
-                    // do something with p
-                    ...
-                }
+
+            // The RCU should NOT be locked when extract() is called!
+            assert( !rcu::is_locked() );
+
+            // extract() call
+            p = theList.extract( 10 );
+            if ( p ) {
+                // do something with p
+                ...

             }
             }

-            // Outside RCU lock section we may safely release extracted pointer.
+
+            // we may safely release extracted pointer here.

             // release() passes the pointer to RCU reclamation cycle.
             p.release();
             \endcode
             // release() passes the pointer to RCU reclamation cycle.
             p.release();
             \endcode


@@ -556,7 +579,7 @@ namespace cds { namespace container {
 
         /// Extracts an item from the list using \p pred predicate for searching
         /**
 
         /// Extracts an item from the list using \p pred predicate for searching
         /**

-            This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)".
+            This function is the analog for \p extract(K const&).

             The \p pred is a predicate used for key comparing.
             \p Less has the interface like \p std::less.
             \p pred must imply the same element order as \ref key_comparator.
             The \p pred is a predicate used for key comparing.
             \p Less has the interface like \p std::less.
             \p pred must imply the same element order as \ref key_comparator.


@@ -577,7 +600,7 @@ namespace cds { namespace container {
             The function makes RCU lock internally.
         */
         template <typename Q>
             The function makes RCU lock internally.
         */
         template <typename Q>

-        bool find( Q const& key ) const
+        bool find( Q const& key )

         {
             return find_at( head(), key, intrusive_key_comparator() );
         }
         {
             return find_at( head(), key, intrusive_key_comparator() );
         }


@@ -590,7 +613,7 @@ namespace cds { namespace container {
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename Q, typename Less>
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename Q, typename Less>

-        bool find_with( Q const& key, Less pred ) const
+        bool find_with( Q const& key, Less pred )

         {
             CDS_UNUSED( pred );
             return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         {
             CDS_UNUSED( pred );
             return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );


@@ -617,7 +640,7 @@ namespace cds { namespace container {
             The function returns \p true if \p key is found, \p false otherwise.
         */
         template <typename Q, typename Func>
             The function returns \p true if \p key is found, \p false otherwise.
         */
         template <typename Q, typename Func>

-        bool find( Q const& key, Func f ) const
+        bool find( Q const& key, Func f )

         {
             return find_at( head(), key, intrusive_key_comparator(), f );
         }
         {
             return find_at( head(), key, intrusive_key_comparator(), f );
         }


@@ -630,7 +653,7 @@ namespace cds { namespace container {
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename Q, typename Less, typename Func>
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename Q, typename Less, typename Func>

-        bool find_with( Q const& key, Less pred, Func f ) const
+        bool find_with( Q const& key, Less pred, Func f )

         {
             CDS_UNUSED( pred );
             return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
         {
             CDS_UNUSED( pred );
             return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );


@@ -639,7 +662,7 @@ namespace cds { namespace container {
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
             The function searches the item with \p key and returns the pointer to item found.
         /// Finds \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
             The function searches the item with \p key and returns the pointer to item found.

-            If \p key is not found it returns \p nullptr.
+            If \p key is not found it returns an empty \p raw_ptr object.

 
             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 
 
             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 


@@ -649,22 +672,24 @@ namespace cds { namespace container {
             typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
             ord_list theList;
             // ...
             typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
             ord_list theList;
             // ...

+            tyename ord_list::raw_ptr rp;

             {
                 // Lock RCU
                 ord_list::rcu_lock lock;
 
             {
                 // Lock RCU
                 ord_list::rcu_lock lock;
 

-                ord_list::value_type * pVal = theList.get( 5 );
-                if ( pVal ) {
-                    // Deal with pVal
+                rp = theList.get( 5 );
+                if ( rp ) {
+                    // Deal with rp

                     //...
                 }
                 // Unlock RCU by rcu_lock destructor
                     //...
                 }
                 // Unlock RCU by rcu_lock destructor

-                // pVal can be freed at any time after RCU has been unlocked

             }
             }

+            // rp can be released at any time after RCU has been unlocked
+            rp.release();

             \endcode
         */
         template <typename K>
             \endcode
         */
         template <typename K>

-        value_type * get( K const& key ) const
+        raw_ptr get( K const& key )

         {
             return get_at( head(), key, intrusive_key_comparator());
         }
         {
             return get_at( head(), key, intrusive_key_comparator());
         }


@@ -679,7 +704,7 @@ namespace cds { namespace container {
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename K, typename Less>
             \p pred must imply the same element order as the comparator used for building the list.
         */
         template <typename K, typename Less>

-        value_type * get_with( K const& key, Less pred ) const
+        raw_ptr get_with( K const& key, Less pred )

         {
             CDS_UNUSED( pred );
             return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );
         {
             CDS_UNUSED( pred );
             return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );


@@ -739,7 +764,7 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Func>
         }
 
         template <typename K, typename Func>

-        bool insert_key_at( head_type& refHead, const K& key, Func f )
+        bool insert_with_at( head_type& refHead, const K& key, Func f )

         {
             scoped_node_ptr pNode( alloc_node( key ));
 
         {
             scoped_node_ptr pNode( alloc_node( key ));
 


@@ -788,22 +813,21 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
         }
 
         template <typename K, typename Compare>

-        bool find_at( head_type& refHead, K const& key, Compare cmp ) const
+        bool find_at( head_type& refHead, K const& key, Compare cmp )

         {
             return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
         }
 
         template <typename K, typename Compare, typename Func>
         {
             return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
         }
 
         template <typename K, typename Compare, typename Func>

-        bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
+        bool find_at( head_type& refHead, K& key, Compare cmp, Func f )

         {
             return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
         }
 
         template <typename K, typename Compare>
         {
             return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ f( node.m_Data ); });
         }
 
         template <typename K, typename Compare>

-        value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
+        raw_ptr get_at( head_type& refHead, K const& val, Compare cmp )

         {
         {

-            node_type * pNode = base_class::get_at( refHead, val, cmp );
-            return pNode ? &pNode->m_Data : nullptr;
+            return raw_ptr( base_class::get_at( refHead, val, cmp ));

         }
 
         //@endcond
         }
 
         //@endcond


@@ -811,4 +835,4 @@ namespace cds { namespace container {
 
 }}  // namespace cds::container
 
 
 }}  // namespace cds::container
 

-#endif  // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H
+#endif  // #ifndef CDSLIB_CONTAINER_MICHAEL_KVLIST_RCU_H