X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Flazy_kvlist.h;h=5db39fc912feea0b8c326f3052e88e2918752f98;hb=ba2a5aa1155973b202518c6fb013c0fb84f0d9e6;hp=953b5bc1cb25a4551df3f737ce6fdcf9e3397a8d;hpb=68c4bb6ce67fc8fccf8d850868e1e95b91f334a4;p=libcds.git diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index 953b5bc1..5db39fc9 100644 --- a/cds/container/impl/lazy_kvlist.h +++ b/cds/container/impl/lazy_kvlist.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_IMPL_LAZY_KVLIST_H -#define __CDS_CONTAINER_IMPL_LAZY_KVLIST_H +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + 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_IMPL_LAZY_KVLIST_H +#define CDSLIB_CONTAINER_IMPL_LAZY_KVLIST_H #include #include @@ -106,6 +134,8 @@ namespace cds { namespace container { typedef typename maker::key_comparator key_comparator; ///< key comparing functor typedef typename base_class::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm + protected: //@cond typedef typename base_class::value_type node_type; @@ -118,7 +148,7 @@ namespace cds { namespace container { public: /// Guarded pointer - typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_map > guarded_ptr; + typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_map > guarded_ptr; protected: //@cond @@ -263,8 +293,7 @@ namespace cds { namespace container { - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the list. - Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container - for debug purpose only. + @warning Use this iterator on the concurrent container for debugging purpose only. The iterator interface to access item data: - operator -> - returns a pointer to \ref value_type for iterator @@ -282,6 +311,8 @@ namespace cds { namespace container { */ typedef iterator_type const_iterator; + ///@name Forward iterators (only for debugging purpose) + //@{ /// Returns a forward iterator addressing the first element in a list /** For empty list \code begin() == end() \endcode @@ -307,32 +338,33 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a list - //@{ const_iterator begin() const { const_iterator it( head() ); ++it; // skip dummy head return it; } + + /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { const_iterator it( head() ); ++it; // skip dummy head return it; } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a list - //@{ const_iterator end() const { return const_iterator( tail()); } + + /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator cend() const { return const_iterator( tail()); } - //@} + //@} public: /// Default constructor @@ -406,9 +438,9 @@ namespace cds { namespace container { it is preferable that the initialization should be completed only if inserting is successful. */ template - 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 ); } /// Inserts data of type \ref mapped_type constructed with std::forward(args)... @@ -421,36 +453,46 @@ namespace cds { namespace container { return emplace_at( head(), std::forward(args)... ); } - /// Ensures that the \p key exists in the list + /// Updates data by \p key /** - The operation performs inserting or changing data with lock-free manner. + The operation performs inserting or replacing the element with lock-free manner. If the \p key not found in the list, then the new item created from \p key - is inserted into the list (note that in this case the \p key_type should be - constructible from type \p K). - Otherwise, the functor \p func is called with item found. - The functor signature is: + will be inserted iff \p bAllowInsert is \p true. + (note that in this case the \ref key_type should be constructible from type \p K). + Otherwise, if \p key is found, 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 ); }; \endcode - with arguments: - \p bNew - \p true if the item has been inserted, \p false otherwise - - \p item - item of the list + - \p item - the item found or inserted - The functor may change any fields of the \p item.second that is \p mapped_type. + The functor may change any fields of the \p item.second of \p mapped_type; + during \p func call \p item is locked so it is safe to modify the item in + multi-threaded environment. 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 list. + already exists. */ template + std::pair update( const K& key, Func f, bool bAllowInsert = true ) + { + return update_at( head(), key, f, bAllowInsert ); + } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") std::pair ensure( const K& key, Func f ) { - return ensure_at( head(), key, f ); + return update( key, f, true ); } + //@endcond /// Deletes \p key from the list /** \anchor cds_nonintrusive_LazyKVList_hp_erase_val @@ -514,8 +556,8 @@ namespace cds { namespace container { /// Extracts the item from the list with specified \p key /** \anchor cds_nonintrusive_LazyKVList_hp_extract The function searches an item with key equal to \p key, - unlinks it from the list, and returns it in \p dest parameter. - If the item with key equal to \p key is not found the function returns \p false. + unlinks it from the list, and returns it as \p guarded_ptr. + If \p key is not found the function returns an empty guarded pointer. Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type. @@ -527,24 +569,26 @@ namespace cds { namespace container { ord_list theList; // ... { - ord_list::guarded_ptr gp; - theList.extract( gp, 5 ); - // Deal with gp - // ... - + ord_list::guarded_ptr gp( theList.extract( 5 )); + if ( gp ) { + // Deal with gp + // ... + } // Destructor of gp releases internal HP guard and frees the item } \endcode */ template - bool extract( guarded_ptr& dest, K const& key ) + guarded_ptr extract( K const& key ) { - return extract_at( head(), dest.guard(), key, intrusive_key_comparator() ); + guarded_ptr gp; + extract_at( head(), gp.guard(), key, intrusive_key_comparator() ); + return gp; } /// Extracts the item from the list with comparing functor \p pred /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_extract "extract(guarded_ptr&, K const&)" + The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_extract "extract(K const&)" but \p pred predicate is used for key comparing. \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K @@ -552,36 +596,53 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool extract_with( guarded_ptr& dest, K const& key, Less pred ) + guarded_ptr extract_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return extract_at( head(), dest.guard(), key, typename maker::template less_wrapper::type() ); + guarded_ptr gp; + extract_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; } - /// Finds the key \p key - /** \anchor cds_nonintrusive_LazyKVList_hp_find_val + /// Checks whether the list 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 + and returns \p true if it is found, and \p false otherwise. */ template - bool find( Q const& key ) + bool contains( Q const& key ) { return find_at( head(), key, intrusive_key_comparator() ); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val using \p pred predicate for searching + /// Checks whether the map contains \p key using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_find_val "find(Q const&)" - but \p pred is used for key comparing. + The function is an analog of contains( key ) 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 list. + \p Less must imply the same element order as the comparator used for building the list. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); return find_at( head(), key, typename maker::template less_wrapper::type() ); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds the key \p key and performs an action with it /** \anchor cds_nonintrusive_LazyKVList_hp_find_func @@ -624,9 +685,8 @@ namespace cds { namespace container { /// Finds \p key and return the item found /** \anchor cds_nonintrusive_LazyKVList_hp_get The function searches the item with key equal to \p key - and assigns the item found to guarded pointer \p ptr. - The function returns \p true if \p key is found, and \p false otherwise. - If \p key is not found the \p ptr parameter is not changed. + and returns the item found as a guarded pointer. + If \p key is not found the functions returns an empty \p guarded_ptr. @note Each \p guarded_ptr object uses one GC's guard which can be limited resource. @@ -636,8 +696,8 @@ namespace cds { namespace container { ord_list theList; // ... { - ord_list::guarded_ptr gp; - if ( theList.get( gp, 5 )) { + ord_list::guarded_ptr gp( theList.get( 5 )); + if ( gp ) { // Deal with gp //... } @@ -649,14 +709,16 @@ namespace cds { namespace container { should accept a parameter of type \p K that can be not the same as \p key_type. */ template - bool get( guarded_ptr& ptr, K const& key ) + guarded_ptr get( K const& key ) { - return get_at( head(), ptr.guard(), key, intrusive_key_comparator() ); + guarded_ptr gp; + get_at( head(), gp.guard(), key, intrusive_key_comparator() ); + return gp; } /// Finds the key \p val and return the item found /** - The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_get "get(guarded_ptr& ptr, K const&)" + The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_get "get(K const&)" but \p pred is used for comparing the keys. \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K @@ -664,10 +726,12 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the list. */ template - bool get_with( guarded_ptr& ptr, K const& key, Less pred ) + guarded_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return get_at( head(), ptr.guard(), key, typename maker::template less_wrapper::type() ); + guarded_ptr gp; + get_at( head(), gp.guard(), key, typename maker::template less_wrapper::type() ); + return gp; } /// Checks if the list is empty @@ -723,7 +787,7 @@ namespace cds { namespace container { } template - 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 )); @@ -753,18 +817,19 @@ namespace cds { namespace container { } template - bool extract_at( head_type& refHead, typename gc::Guard& dest, K const& key, Compare cmp ) + bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) { - return base_class::extract_at( &refHead, dest, key, cmp ); + return base_class::extract_at( &refHead, guard, key, cmp ); } template - std::pair ensure_at( head_type& refHead, const K& key, Func f ) + std::pair update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert ) { scoped_node_ptr pNode( alloc_node( key )); - std::pair ret = base_class::ensure_at( &refHead, *pNode, - [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }); + std::pair ret = base_class::update_at( &refHead, *pNode, + [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); }, + bAllowInsert ); if ( ret.first && ret.second ) pNode.release(); @@ -784,7 +849,7 @@ namespace cds { namespace container { } template - bool get_at( head_type& refHead, typename gc::Guard& guard, K const& key, Compare cmp ) + bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp ) { return base_class::get_at( &refHead, guard, key, cmp ); } @@ -794,4 +859,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_IMPL_LAZY_KVLIST_H +#endif // #ifndef CDSLIB_CONTAINER_IMPL_LAZY_KVLIST_H