Docfix

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

diff --git a/cds/container/michael_set_rcu.h b/cds/container/michael_set_rcu.h
index 1d1ebe87a94567de98654c21680ffcb6ec8b0201..a2a3180dbedfc0bce0b8c3e487139c259230f26d 100644 (file)
--- a/cds/container/michael_set_rcu.h
+++ b/cds/container/michael_set_rcu.h
@@ -123,6 +123,7 @@ namespace cds { namespace container {
 
         typedef typename bucket_type::rcu_lock   rcu_lock;   ///< RCU scoped lock
         typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
 
         typedef typename bucket_type::rcu_lock   rcu_lock;   ///< RCU scoped lock
         typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node

+        typedef typename bucket_type::raw_ptr    raw_ptr;    ///< Return type of \p get() member function and its derivatives

         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
         static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
 
         /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
         static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
 


@@ -233,7 +234,13 @@ namespace cds { namespace container {
 
     public:
         /// Initialize hash set
 
     public:
         /// Initialize hash set

-        /** @copydetails cds_nonintrusive_MichaelHashSet_hp_ctor
+        /**
+            The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
+            when you create an object.
+            \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
+            Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
+
+            The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.

         */
         MichaelHashSet(
             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
         */
         MichaelHashSet(
             size_t nMaxItemCount,   ///< estimation of max item count in the hash set


@@ -338,14 +345,50 @@ namespace cds { namespace container {
             \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */
             \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */

+        /// Updates the element
+        /**
+            The operation performs inserting or changing data with lock-free manner.
+
+            If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
+            Otherwise, the functor \p func is called with item found.
+            The functor signature is:
+            \code
+                struct functor {
+                    void operator()( bool bNew, value_type& item, Q const& val );
+                };
+            \endcode
+            with arguments:
+            - \p bNew - \p true if the item has been inserted, \p false otherwise
+            - \p item - item of the set
+            - \p val - argument \p val passed into the \p %update() function
+
+            The functor may change non-key fields of the \p item.
+
+            The function applies RCU lock internally.
+
+            Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
+            \p second is \p true if new item has been added or \p false if the item with \p key
+            already is in the set.
+
+            @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
+            \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
+            synchronization.
+        */

         template <typename Q, typename Func>
         template <typename Q, typename Func>

-        std::pair<bool, bool> ensure( const Q& val, Func func )
+        std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert = true )

         {
         {

-            std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
-            if ( bRet.first && bRet.second )
+            std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
+            if ( bRet.second )

                 ++m_ItemCounter;
             return bRet;
                 ++m_ItemCounter;
             return bRet;

+        }//@cond
+        template <typename Q, typename Func>
+        CDS_DEPRECATED("ensure() is deprecated, use update()")
+        std::pair<bool, bool> ensure( const Q& val, Func func )
+        {
+            return update( val, func, true );

         }
         }

+        //@endcond

 
         /// Inserts data of type \p value_type created from \p args
         /**
 
         /// Inserts data of type \p value_type created from \p args
         /**


@@ -452,11 +495,11 @@ namespace cds { namespace container {
             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
             If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr.
 
             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
             If the item with the key equal to \p key is not found the function return 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 set
-            and returns a pointer to item found.
-            You should lock RCU before calling of the function, and you should synchronize RCU
-            outside the RCU lock to free extracted item
+            The function just excludes the item from the set and returns a pointer to item found.
+            Depends on \p bucket_type you should or should not lock RCU before calling of this function:
+            - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
+            - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
+            See ordered list implementation for details.

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


@@ -470,18 +513,15 @@ namespace cds { namespace container {
             rcu_michael_set theSet;
             // ...
 
             rcu_michael_set theSet;
             // ...
 

-            rcu_michael_set::exempt_ptr p;
-            {
-                // first, we should lock RCU
-                rcu_michael_set::rcu_lock lock;
-
-                // Now, you can apply extract function
-                // Note that you must not delete the item found inside the RCU lock
-                p = theSet.extract( 10 );
-                if ( p ) {
-                    // do something with p
-                    ...
-                }
+            typename rcu_michael_set::exempt_ptr p;
+
+            // For MichaelList we should not lock RCU
+
+            // Note that you must not delete the item found inside the RCU lock
+            p = theSet.extract( 10 );
+            if ( p ) {
+                // do something with p
+                ...

             }
 
             // We may safely release p here
             }
 
             // We may safely release p here


@@ -500,8 +540,7 @@ namespace cds { namespace container {
 
         /// Extracts an item from the set using \p pred predicate for searching
         /**
 
         /// Extracts an item from the set using \p pred predicate for searching
         /**

-            The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_extract "extract(exempt_ptr&, Q const&)"
-            but \p pred is used for key comparing.
+            The function is an analog of \p extract(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.
         */
             \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.
         */


@@ -542,13 +581,13 @@ 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& key, Func f ) const
+        bool find( Q& key, Func f )

         {
             return bucket( key ).find( key, f );
         }
         //@cond
         template <typename Q, typename Func>
         {
             return bucket( key ).find( key, f );
         }
         //@cond
         template <typename Q, typename Func>

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

         {
             return bucket( key ).find( key, f );
         }
         {
             return bucket( key ).find( key, f );
         }


@@ -562,50 +601,66 @@ namespace cds { namespace container {
             \p Less must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less, typename Func>
             \p Less must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less, typename Func>

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

         {
             return bucket( key ).find_with( key, pred, f );
         }
         //@cond
         template <typename Q, typename Less, typename Func>
         {
             return bucket( key ).find_with( key, pred, f );
         }
         //@cond
         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 )

         {
             return bucket( key ).find_with( key, pred, f );
         }
         //@endcond
 
         {
             return bucket( key ).find_with( key, pred, f );
         }
         //@endcond
 

-        /// Finds the key \p key
-        /** \anchor cds_nonintrusive_MichealSet_rcu_find_val
-
+        /// Checks whether the set contains \p key
+        /** 

             The function searches the item with key equal to \p key
             The function searches the item with key equal to \p key

-            and returns \p true if it is found, and \p false otherwise.
+            and returns \p true if the key is found, and \p false otherwise.

 
             Note the hash functor specified for class \p Traits template parameter
 
             Note the hash functor specified for class \p Traits template parameter

-            should accept a parameter of type \p Q that may be not the same as \p value_type.
+            should accept a parameter of type \p Q that can be not the same as \p value_type.

         */
         template <typename Q>
         */
         template <typename Q>

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

         {
         {

-            return bucket( key ).find( key );
+            return bucket( key ).contains( key );

         }
         }

+        //@cond
+        template <typename Q>
+        CDS_DEPRECATED("use contains()")
+        bool find( Q const& key )
+        {
+            return contains( key );
+        }
+        //@endcond

 
 

-        /// Finds the key \p key using \p pred predicate for searching
+        /// Checks whether the set contains \p key using \p pred predicate for searching

         /**
         /**

-            The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_val "find(Q const&)"
-            but \p pred is used for key comparing.
+            The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.

             \p Less functor has the interface like \p std::less.
             \p Less must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less>
             \p Less functor has the interface like \p std::less.
             \p Less must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less>

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

         {
         {

-            return bucket( key ).find_with( key, pred );
+            return bucket( key ).contains( key, pred );

         }
         }

+        //@cond
+        template <typename Q, typename Less>
+        CDS_DEPRECATED("use contains()")
+        bool find_with( Q const& key, Less pred )
+        {
+            return contains( key, pred );
+        }
+        //@endcond

 
         /// Finds the key \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
             The function searches the item with key equal to \p key and returns the pointer to item found.
             If \p key is not found it returns \p nullptr.
 
         /// Finds the key \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
             The function searches the item with key equal to \p key and returns the pointer to item found.
             If \p key is not found it returns \p nullptr.

+            Note the type of returned value depends on underlying \p bucket_type.
+            For details, see documentation of ordered list you use.

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


@@ -614,23 +669,24 @@ namespace cds { namespace container {
             \code
             typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
             hash_set theSet;
             \code
             typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
             hash_set theSet;

+            typename hash_set::raw_ptr gp;

             // ...
             {
                 // Lock RCU
                 hash_set::rcu_lock lock;
 
             // ...
             {
                 // Lock RCU
                 hash_set::rcu_lock lock;
 

-                foo * pVal = theSet.get( 5 );
-                if ( pVal ) {
+                gp = theSet.get( 5 );
+                if ( gp ) {

                     // Deal with pVal
                     //...
                 }
                 // Unlock RCU by rcu_lock destructor
                     // Deal with pVal
                     //...
                 }
                 // Unlock RCU by rcu_lock destructor

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

             }
             \endcode
         */
         template <typename Q>
             }
             \endcode
         */
         template <typename Q>

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

         {
             return bucket( key ).get( key );
         }
         {
             return bucket( key ).get( key );
         }


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

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

         {
             return bucket( key ).get_with( key, pred );
         }
         {
             return bucket( key ).get_with( key, pred );
         }