EllenBinTreeMap, EllenBinTreeSet:

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

diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h
index 58c6a6acbc694c97851a53091241be064a9679c5..5428090f4bbcdf7c95fc5b53effd65db78b5b2e0 100644 (file)
--- a/cds/intrusive/impl/ellen_bintree.h
+++ b/cds/intrusive/impl/ellen_bintree.h
@@ -369,20 +369,21 @@ namespace cds { namespace intrusive {
             return true;
         }
 
-        /// Ensures that the \p val exists in the tree
+        /// Updates the node
         /**
             The operation performs inserting or changing data with lock-free manner.
 
-            If the item \p val is not found in the tree, then \p val is inserted into the tree.
+            If the item \p val is not found in the set, then \p val is inserted into the set
+            iff \p bAllowInsert is \p true.
             Otherwise, the functor \p func is called with item found.
-            The functor signature is:
+            The functor \p func signature is:
             \code
                 void func( bool bNew, value_type& item, value_type& val );
             \endcode
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
-            - \p item - an item of the tree
-            - \p val - the argument \p val passed to the \p ensure function
+            - \p item - item of the set
+            - \p val - argument \p val passed into the \p %update() function
             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
             refer to the same thing.
 
@@ -390,13 +391,14 @@ namespace cds { namespace intrusive {
             that during changing no any other modifications could be made on this item by concurrent threads.
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+            i.e. the node has been inserted or updated,
             \p second is \p true if new item has been added or \p false if the item with \p key
-            already is in the tree.
+            already exists.
 
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename Func>
-        std::pair<bool, bool> ensure( value_type& val, Func func )
+        std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
         {
             typename gc::Guard guardInsert;
             guardInsert.assign( &val );
@@ -415,6 +417,8 @@ namespace cds { namespace intrusive {
                 }
 
                 if ( res.updGrandParent.bits() == update_desc::Clean && res.updParent.bits() == update_desc::Clean )  {
+                    if ( !bAllowInsert )
+                        return std::make_pair( false, false );
 
                     if ( !pNewInternal.get() )
                         pNewInternal.reset( alloc_internal_node() );
@@ -434,6 +438,14 @@ namespace cds { namespace intrusive {
             m_Stat.onEnsureNew();
             return std::make_pair( true, true );
         }
+        //@cond
+        // Deprecated, us update()
+        template <typename Func>
+        std::pair<bool, bool> ensure( value_type& val, Func func )
+        {
+            return update( val, func, true );
+        }
+        //@endcond
 
         /// Unlinks the item \p val from the tree
         /**
@@ -622,16 +634,13 @@ namespace cds { namespace intrusive {
             return gp;
         }
 
-        /// Finds the key \p key
-        /** @anchor cds_intrusive_EllenBinTree_find_val
+        /// Checks whether the set contains \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.
-
-            Note the hash functor specified for class \p Traits template parameter
-            should accept a parameter of type \p Q that can be not the same as \p value_type.
         */
         template <typename Q>
-        bool find( Q const& key ) const
+        bool contains( Q const& key ) const
         {
             search_result    res;
             if ( search( res, key, node_compare() )) {
@@ -642,18 +651,23 @@ namespace cds { namespace intrusive {
             m_Stat.onFindFailed();
             return false;
         }
+        //@cond
+        // Deprecated, use contains()
+        template <typename Q>
+        bool find( Q const& key ) const
+        {
+            return contains( key );
+        }
+        //@endcond
 
-        /// Finds the key \p key with comparing functor \p pred
+        /// Checks whether the set contains \p key using \p pred predicate for searching
         /**
-            The function is an analog of \ref cds_intrusive_EllenBinTree_find_val "find(Q const&)"
-            but \p pred is used for key compare.
-            \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.
-            \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination.
+            The function is similar to <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>
-        bool find_with( Q const& key, Less pred ) const
+        bool contains( Q const& key, Less pred ) const
         {
             CDS_UNUSED( pred );
             typedef ellen_bintree::details::compare<
@@ -671,6 +685,14 @@ namespace cds { namespace intrusive {
             m_Stat.onFindFailed();
             return false;
         }
+        //@cond
+        // Deprecated, use contains()
+        template <typename Q, typename Less>
+        bool find_with( Q const& key, Less pred ) const
+        {
+            return contains( key, pred );
+        }
+        //@endcond
 
         /// Finds the key \p key
         /** @anchor cds_intrusive_EllenBinTree_find_func