X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fellen_bintree_set_rcu.h;h=dd5c41918c351f1ca76e655e062d4ee6e0967e47;hb=1132246d5685f87a5b240e077b7e88d56e38b1ff;hp=a0f79b138d7faf122171c69fcdb6f2665d2b7c98;hpb=1831737c7cc9d4b31ee6f555f8450fba0748571d;p=libcds.git diff --git a/cds/container/ellen_bintree_set_rcu.h b/cds/container/ellen_bintree_set_rcu.h index a0f79b13..dd5c4191 100644 --- a/cds/container/ellen_bintree_set_rcu.h +++ b/cds/container/ellen_bintree_set_rcu.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_ELLEN_BINTREE_SET_RCU_H -#define __CDS_CONTAINER_ELLEN_BINTREE_SET_RCU_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + 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. +*/ + +#ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_SET_RCU_H +#define CDSLIB_CONTAINER_ELLEN_BINTREE_SET_RCU_H #include #include @@ -30,7 +58,7 @@ namespace cds { namespace container { the priority value plus some uniformly distributed random value. @warning Recall the tree is unbalanced. The complexity of operations is O(log N) - for uniformly distributed random keys, but in worst case the complexity is O(N). + for uniformly distributed random keys, but in the worst case the complexity is O(N). @note In the current implementation we do not use helping technique described in original paper. So, the current implementation is near to fine-grained lock-based tree. @@ -176,7 +204,7 @@ namespace cds { namespace container { bool insert( Q const& val ) { scoped_node_ptr sp( cxx_leaf_node_allocator().New( val )); - if ( base_class::insert( *sp.get() )) { + if ( base_class::insert( *sp.get())) { sp.release(); return true; } @@ -204,56 +232,60 @@ namespace cds { namespace container { bool insert( Q const& val, Func f ) { scoped_node_ptr sp( cxx_leaf_node_allocator().New( val )); - if ( base_class::insert( *sp.get(), [&f]( leaf_node& val ) { f( val.m_Value ); } )) { + if ( base_class::insert( *sp.get(), [&f]( leaf_node& v ) { f( v.m_Value ); } )) { sp.release(); return true; } return false; } - /// Ensures that the item exists in the set + /// Updates the node /** The operation performs inserting or changing data with lock-free manner. - If the \p val key not found in the set, then the new item created from \p val - is inserted into the set. Otherwise, the functor \p func is called with the item found. - The functor \p Func should be a function with signature: - \code - void func( bool bNew, value_type& item, const Q& val ); - \endcode - or a functor: + 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 \p func signature is: \code - struct my_functor { - void operator()( bool bNew, value_type& item, const Q& val ); - }; + 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 - item of the set - - \p val - argument \p key passed into the \p ensure function + - \p val - argument \p val passed into the \p %update() function - The functor may change non-key fields of the \p item; however, \p func must guarantee + The functor can change non-key fields of the \p item; however, \p func must guarantee that during changing no any other modifications could be made on this item by concurrent threads. - RCU \p synchronize() can be called. RCU should not be locked. + RCU \p synchronize method can be called. RCU should not be locked. - Returns std::pair 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 - already is in the set. + Returns std::pair where \p first is \p true if operation is successful, + 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 exists. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair ensure( const Q& val, Func func ) + std::pair update( Q const& val, Func func, bool bAllowInsert = true ) { scoped_node_ptr sp( cxx_leaf_node_allocator().New( val )); - std::pair bRes = base_class::ensure( *sp, - [&func, &val](bool bNew, leaf_node& node, leaf_node&){ func( bNew, node.m_Value, val ); }); + std::pair bRes = base_class::update( *sp, + [&func, &val](bool bNew, leaf_node& node, leaf_node&){ func( bNew, node.m_Value, val ); }, + bAllowInsert ); if ( bRes.first && bRes.second ) sp.release(); return bRes; } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( const Q& val, Func func ) + { + return update( val, func, true ); + } + //@endcond /// Inserts data of type \p value_type created in-place from \p args /** @@ -264,8 +296,8 @@ namespace cds { namespace container { template bool emplace( Args&&... args ) { - scoped_node_ptr sp( cxx_leaf_node_allocator().New( std::forward(args)... )); - if ( base_class::insert( *sp.get() )) { + scoped_node_ptr sp( cxx_leaf_node_allocator().MoveNew( std::forward(args)... )); + if ( base_class::insert( *sp.get())) { sp.release(); return true; } @@ -406,18 +438,17 @@ namespace cds { namespace container { /// Extracts an item from the set using \p pred for searching /** - The function is an analog of \ref cds_nonintrusive_EllenBinTreeSet_rcu_extract "extract(exempt_ptr&, Q const&)" - but \p pred is used for key compare. + The function is an analog of \p 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_container_EllenBinTreeSet_rcu_less "predicate requirements". \p pred must imply the same element order as the comparator used for building the set. */ template - exempt_ptr extract_with( Q const& val, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return exempt_ptr( base_class::extract_with_( val, - cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >() )); + return exempt_ptr( base_class::extract_with_( key, + cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >())); } /// Find the key \p key @@ -485,36 +516,49 @@ namespace cds { namespace container { } //@endcond - /// Find the key \p key - /** @anchor cds_nonintrusive_EllenBinTreeSet_rcu_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 may be not the same as \ref value_type. - The function applies RCU lock internally. */ template + bool contains( Q const& key ) const + { + return base_class::contains( key ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") bool find( Q const& key ) const { - return base_class::find( 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_EllenBinTreeSet_rcu_find_val "find(Q const&)" - but \p pred is used for key comparing. - \p Less functor has the interface like \p std::less. + The function is similar to contains( key ) 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_rcu_less + "Predicate requirements". \p Less must imply the same element order as the comparator used for building the set. + \p pred should accept arguments of type \p Q, \p key_type, \p value_type in any combination. */ template - bool find_with( Q const& key, Less pred ) const + bool contains( Q const& key, Less pred ) const { CDS_UNUSED( pred ); - return base_class::find_with( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >()); + return base_class::contains( key, cds::details::predicate_wrapper< leaf_node, Less, typename maker::value_accessor >()); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( Q const& key, Less pred ) const + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_EllenBinTreeSet_rcu_get @@ -556,7 +600,7 @@ namespace cds { namespace container { this sequence \code set.clear(); - assert( set.empty() ); + assert( set.empty()); \endcode the assertion could be raised. @@ -606,4 +650,4 @@ namespace cds { namespace container { }; }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_SET_RCU_H +#endif // #ifndef CDSLIB_CONTAINER_ELLEN_BINTREE_SET_RCU_H