X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Flazy_kvlist.h;h=5db39fc912feea0b8c326f3052e88e2918752f98;hb=ba2a5aa1155973b202518c6fb013c0fb84f0d9e6;hp=e8b83f7a7cbc001194618e5465ae86ea95454784;hpb=82c41f9cd6c72a53cdb7d50c948b4d489df835a0;p=libcds.git diff --git a/cds/container/impl/lazy_kvlist.h b/cds/container/impl/lazy_kvlist.h index e8b83f7a..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; @@ -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 @@ -562,30 +604,45 @@ namespace cds { namespace container { 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 @@ -730,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 )); @@ -766,12 +823,13 @@ namespace cds { namespace container { } 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(); @@ -801,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