X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Fskip_list_set.h;h=18fa118266b834cae769723b8a7360b0728bc0ae;hp=3f42454415748f855f601d43c4bb10c1854eb941;hb=2402fb1beb25ec532cea91c8dfbb9425eb5bdf48;hpb=35a035d8d6c7b53a1b3bc1fbb268ca72fa61e387 diff --git a/cds/container/impl/skip_list_set.h b/cds/container/impl/skip_list_set.h index 3f424544..18fa1182 100644 --- a/cds/container/impl/skip_list_set.h +++ b/cds/container/impl/skip_list_set.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H -#define __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H + (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_SKIP_LIST_SET_H +#define CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H #include #include @@ -36,7 +64,7 @@ namespace cds { namespace container { - \p GC - Garbage collector used. - \p T - type to be stored in the list. - \p Traits - set traits, default is \p skip_list::traits. - It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction + It is possible to declare option-based list with \p cds::container::skip_list::make_traits metafunction istead of \p Traits template argument. @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which @@ -124,6 +152,8 @@ namespace cds { namespace container { typedef typename traits::random_level_generator random_level_generator; ///< random level generator typedef typename traits::stat stat; ///< internal statistics type + static size_t const c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the skip-list + protected: //@cond typedef typename maker::node_type node_type; @@ -155,7 +185,50 @@ namespace cds { namespace container { {} public: + ///@name Forward iterators (only for debugging purpose) + //@{ /// Iterator type + /** + The forward iterator has some features: + - it has no post-increment operator + - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator. + For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard" + may be thrown if the limit of guard count per thread is exceeded. + - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard. + - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent + deleting operations there is no guarantee that you iterate all item in the list. + Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread. + + @warning Use this iterator on the concurrent container for debugging purpose only. + + The iterator interface: + \code + class iterator { + public: + // Default constructor + iterator(); + + // Copy construtor + iterator( iterator const& src ); + + // Dereference operator + value_type * operator ->() const; + + // Dereference operator + value_type& operator *() const; + + // Preincrement operator + iterator& operator ++(); + + // Assignment operator + iterator& operator = (iterator const& src); + + // Equality operators + bool operator ==(iterator const& i ) const; + bool operator !=(iterator const& i ) const; + }; + \endcode + */ typedef skip_list::details::iterator< typename base_class::iterator > iterator; /// Const iterator type @@ -164,38 +237,39 @@ namespace cds { namespace container { /// Returns a forward iterator addressing the first element in a set iterator begin() { - return iterator( base_class::begin() ); + return iterator( base_class::begin()); } /// Returns a forward const iterator addressing the first element in a set const_iterator begin() const { - return const_iterator( base_class::begin() ); + return const_iterator( base_class::begin()); } /// Returns a forward const iterator addressing the first element in a set const_iterator cbegin() const { - return const_iterator( base_class::cbegin() ); + return const_iterator( base_class::cbegin()); } /// Returns a forward iterator that addresses the location succeeding the last element in a set. iterator end() { - return iterator( base_class::end() ); + return iterator( base_class::end()); } /// Returns a forward const iterator that addresses the location succeeding the last element in a set. const_iterator end() const { - return const_iterator( base_class::end() ); + return const_iterator( base_class::end()); } /// Returns a forward const iterator that addresses the location succeeding the last element in a set. const_iterator cend() const { - return const_iterator( base_class::cend() ); + return const_iterator( base_class::cend()); } + //@} public: /// Inserts new node @@ -213,7 +287,7 @@ namespace cds { namespace container { bool insert( Q const& val ) { scoped_node_ptr sp( node_allocator().New( random_level(), val )); - if ( base_class::insert( *sp.get() )) { + if ( base_class::insert( *sp.get())) { sp.release(); return true; } @@ -246,47 +320,54 @@ namespace cds { namespace container { return false; } - /// Ensures that the item exists in the set + /// Updates the item /** 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: + will be inserted into the set iff \p bInsert is \p true. + Otherwise, if \p val is found, the functor \p func will be called with the item found. + + The functor \p Func signature: \code struct my_functor { void operator()( bool bNew, value_type& item, const Q& val ); }; \endcode - - with arguments: + where: - \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 key passed into the \p %update() function The functor may 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. - 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 item has been inserted or updated, + \p second is \p true if new item has been added or \p false if the item with key equal to \p val + already exists. @warning See \ref cds_intrusive_item_creating "insert item troubleshooting" */ template - std::pair ensure( const Q& val, Func func ) + std::pair update( const Q& val, Func func, bool bInsert = true ) { scoped_node_ptr sp( node_allocator().New( random_level(), val )); - std::pair bRes = base_class::ensure( *sp, - [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); }); + std::pair bRes = base_class::update( *sp, + [&func, &val](bool bNew, node_type& node, node_type&){ func( bNew, node.m_Value, val ); }, + bInsert ); 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 std::forward(args)... /** @@ -296,7 +377,7 @@ namespace cds { namespace container { bool emplace( Args&&... args ) { scoped_node_ptr sp( node_allocator().New( random_level(), std::forward(args)... )); - if ( base_class::insert( *sp.get() )) { + if ( base_class::insert( *sp.get())) { sp.release(); return true; } @@ -328,7 +409,7 @@ namespace cds { namespace container { bool erase_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() ); + return base_class::erase_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()); } /// Delete \p key from the set @@ -402,9 +483,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - base_class::extract_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::extract_( key, typename base_class::key_comparator()); } /// Extracts the item from the set with comparing functor \p pred @@ -421,9 +500,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - guarded_ptr gp; - base_class::extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less() ); - return gp; + return base_class::extract_( key, cds::opt::details::make_comparator_from_less()); } /// Extracts an item with minimal key from the set @@ -452,9 +529,7 @@ namespace cds { namespace container { */ guarded_ptr extract_min() { - guarded_ptr gp; - base_class::extract_min_( gp.guard() ); - return gp; + return base_class::extract_min_(); } /// Extracts an item with maximal key from the set @@ -483,9 +558,7 @@ namespace cds { namespace container { */ guarded_ptr extract_max() { - guarded_ptr gp; - base_class::extract_max_( gp.guard() ); - return gp; + return base_class::extract_max_(); } /// Find the \p key @@ -543,38 +616,49 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >(), - [&f]( node_type& node, Q& v ) { f( node.m_Value, v ); } ); + [&f]( node_type& node, Q const& v ) { f( node.m_Value, v ); } ); } //@endcond - /// Find \p key - /** \anchor cds_nonintrusive_SkipListSet_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. */ template + bool contains( Q const& key ) + { + return base_class::contains( key ); + } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") bool find( Q const& key ) { - return base_class::find( key ); + return contains( key ); } + //@endcond - /// Finds \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_SkipListSet_find_val "find(Q const&)" - but \p pred is used for key comparing. + 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. \p Less must imply the same element order as the comparator used for building the set. */ template - bool find_with( Q const& key, Less pred ) + bool contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::find_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()); + return base_class::contains( key, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >()); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + bool find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond /// Finds \p key and return the item found /** \anchor cds_nonintrusive_SkipListSet_hp_get @@ -608,9 +692,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, typename base_class::key_comparator() ); - return gp; + return base_class::get_with_( key, typename base_class::key_comparator()); } /// Finds \p key and return the item found @@ -627,9 +709,7 @@ namespace cds { namespace container { { CDS_UNUSED( pred ); typedef cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor > wrapped_less; - guarded_ptr gp; - base_class::get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less< wrapped_less >()); - return gp; + return base_class::get_with_( key, cds::opt::details::make_comparator_from_less< wrapped_less >()); } /// Clears the set (not atomic). @@ -639,7 +719,7 @@ namespace cds { namespace container { this sequence \code set.clear(); - assert( set.empty() ); + assert( set.empty()); \endcode the assertion could be raised. @@ -677,4 +757,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_IMPL_SKIP_LIST_SET_H +#endif // #ifndef CDSLIB_CONTAINER_IMPL_SKIP_LIST_SET_H