X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fcontainer%2Fsplit_list_set.h;h=f6a7831e993213c766dad735530c01debd6dd514;hp=616f0f2c6561924967ae4c57321c6769042c4d8a;hb=65f7355b1eaa63b1a46d2172d10d45e400e6d862;hpb=364713fa3a507065fbf38839612538a3cde74050 diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index 616f0f2c..f6a7831e 100644 --- a/cds/container/split_list_set.h +++ b/cds/container/split_list_set.h @@ -1,10 +1,39 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (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_SPLIT_LIST_SET_H #define CDSLIB_CONTAINER_SPLIT_LIST_SET_H #include #include +#include namespace cds { namespace container { @@ -152,10 +181,13 @@ namespace cds { namespace container { typedef typename base_class::item_counter item_counter; ///< Item counter type typedef typename base_class::stat stat; ///< Internal statistics + /// Count of hazard pointer required + static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; + protected: //@cond - typedef typename maker::cxx_node_allocator cxx_node_allocator; - typedef typename maker::node_type node_type; + typedef typename maker::cxx_node_allocator cxx_node_allocator; + typedef typename maker::node_type node_type; //@endcond public: @@ -164,80 +196,12 @@ namespace cds { namespace container { protected: //@cond - template - static node_type * alloc_node(Q const& v ) - { - return cxx_node_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_node_allocator().MoveNew( std::forward( args )... ); - } - - static void free_node( node_type * pNode ) - { - cxx_node_allocator().Delete( pNode ); - } - - template - bool find_( Q& val, Func f ) - { - return base_class::find( val, [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } ); - } - - template - bool find_with_( Q& val, Less pred, Func f ) - { - CDS_UNUSED( pred ); - return base_class::find_with( val, typename maker::template predicate_wrapper::type(), - [&f]( node_type& item, Q& val ) { f(item.m_Value, val) ; } ); - } - - struct node_disposer { - void operator()( node_type * pNode ) - { - free_node( pNode ); - } - }; - typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - bool insert_node( node_type * pNode ) - { - assert( pNode != nullptr ); - scoped_node_ptr p(pNode); - - if ( base_class::insert( *pNode )) { - p.release(); - return true; - } - return false; - } - - //@endcond - - protected: - /// Forward iterator - /** - \p IsConst - constness boolean flag - - The forward iterator for a split-list has the following features: - - it has no post-increment operator - - it depends on underlying ordered list iterator - - The iterator object cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data. - - 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 split-list. - - Therefore, the use of iterators in concurrent environment is not good idea. Use it for debug purpose only. - */ template class iterator_type: protected base_class::template iterator_type { - //@cond typedef typename base_class::template iterator_type iterator_base_class; friend class SplitListSet; - //@endcond + public: /// Value pointer type (const for const iterator) typedef typename cds::details::make_const_type::pointer value_ptr; @@ -255,11 +219,9 @@ namespace cds { namespace container { {} protected: - //@cond explicit iterator_type( iterator_base_class const& src ) : iterator_base_class( src ) {} - //@endcond public: /// Dereference operator @@ -302,6 +264,7 @@ namespace cds { namespace container { return iterator_base_class::operator!=(i); } }; + //@endcond public: /// Initializes split-ordered list of default capacity @@ -323,7 +286,48 @@ namespace cds { namespace container { {} public: + ///@name Forward iterators (only for debugging purpose) + //@{ /// Forward iterator + /** + The forward iterator for a split-list has the following features: + - it has no post-increment operator + - it depends on underlying ordered list iterator + - The iterator object cannot be moved across thread boundary because it contains GC's guard that is thread-private GC data. + - 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 split-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 iterator_type iterator; /// Const forward iterator @@ -370,6 +374,7 @@ namespace cds { namespace container { { return const_iterator( base_class::cend()); } + //@} public: /// Inserts new node @@ -384,9 +389,9 @@ namespace cds { namespace container { Returns \p true if \p val is inserted into the set, \p false otherwise. */ template - bool insert( Q const& val ) + bool insert( Q&& val ) { - return insert_node( alloc_node( val )); + return insert_node( alloc_node( std::forward( val ))); } /// Inserts new node @@ -409,9 +414,9 @@ namespace cds { namespace container { synchronization. */ template - bool insert( Q const& val, Func f ) + bool insert( Q&& val, Func f ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( std::forward( val ))); if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) { pNode.release(); @@ -430,6 +435,37 @@ namespace cds { namespace container { return insert_node( alloc_node( std::forward(args)...)); } + /// Inserts or updates the node (only for \p IterableList -based set) + /** + The operation performs inserting or changing data with lock-free manner. + + If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true. + Otherwise, the current element is changed to \p val, the old element will be retired later. + + Returns std::pair where \p first is \p true if operation is successful, + \p second is \p true if \p val has been added or \p false if the item with that key + already in the set. + */ + template +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value, + std::pair + >::type +#endif + upsert( Q&& val, bool bAllowInsert = true ) + { + scoped_node_ptr pNode( alloc_node( std::forward( val ))); + + auto bRet = base_class::upsert( *pNode, bAllowInsert ); + + if ( bRet.first ) + pNode.release(); + return bRet; + } + /// Updates the node /** The operation performs inserting or changing data with lock-free manner. @@ -437,10 +473,12 @@ namespace cds { namespace container { If \p key is not found in the set, then \p key is inserted 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 depends of ordered list: + + for \p MichaelList, \p LazyList \code - struct my_functor { - void operator()( bool bNew, value_type& item, const Q& val ); + struct functor { + void operator()( bool bNew, value_type& item, Q const& val ); }; \endcode with arguments: @@ -450,20 +488,37 @@ namespace cds { namespace container { The functor may change non-key fields of the \p item. - Returns std::pair where \p first is true if operation is successfull, + for \p IterableList + \code + void func( value_type& val, value_type * old ); + \endcode + where + - \p val - a new data constructed from \p key + - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr. + + Returns std::pair where \p first is true if operation is successful, \p second is true if new item has been added or \p false if the item with \p key - already is in the map. + already is in the set. - @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". + @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList" + as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level synchronization. */ template - std::pair update( Q const& val, Func func, bool bAllowInsert = true ) +#ifdef CDS_DOXYGEN_INVOKED + std::pair +#else + typename std::enable_if< + std::is_same::value && !is_iterable_list::value, + std::pair + >::type +#endif + update( Q&& val, Func func, bool bAllowInsert = true ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( std::forward( val ))); - std::pair bRet = base_class::update( *pNode, + auto bRet = base_class::update( *pNode, [&func, &val]( bool bNew, node_type& item, node_type const& /*val*/ ) { func( bNew, item.m_Value, val ); }, bAllowInsert ); @@ -472,6 +527,27 @@ namespace cds { namespace container { pNode.release(); return bRet; } + //@cond + template + typename std::enable_if< + std::is_same::value && is_iterable_list::value, + std::pair + >::type + update( Q&& val, Func func, bool bAllowInsert = true ) + { + scoped_node_ptr pNode( alloc_node( std::forward( val ))); + + auto bRet = base_class::update( *pNode, + [&func]( node_type& item, node_type* old ) { + func( item.m_Value, old ? &old->m_Value : nullptr ); + }, bAllowInsert ); + + if ( bRet.first ) + pNode.release(); + return bRet; + } + //@endcond + //@cond template CDS_DEPRECATED("ensure() is deprecated, use update()") @@ -550,6 +626,28 @@ namespace cds { namespace container { [&f](node_type& node) { f( node.m_Value ); } ); } + /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set) + /** + Returns \p true if the operation is successful, \p false otherwise. + The function can return \p false if the node the iterator points to has already been deleted + by other thread. + + The function does not invalidate the iterator, it remains valid and can be used for further traversing. + + @note \p %erase_at() is supported only for \p %SplitListSet based on \p IterableList. + */ +#ifdef CDS_DOXYGEN_INVOKED + bool erase_at( iterator const& iter ) +#else + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, bool >::type + erase_at( Iterator const& iter ) +#endif + { + return base_class::erase_at( static_cast( iter )); + } + + /// Extracts the item with specified \p key /** \anchor cds_nonintrusive_SplitListSet_hp_extract The function searches an item with key equal to \p key, @@ -579,9 +677,7 @@ namespace cds { namespace container { template guarded_ptr extract( Q const& key ) { - guarded_ptr gp; - extract_( gp.guard(), key ); - return gp; + return extract_( key ); } /// Extracts the item using compare functor \p pred @@ -596,9 +692,7 @@ namespace cds { namespace container { template guarded_ptr extract_with( Q const& key, Less pred ) { - guarded_ptr gp; - extract_with_( gp.guard(), key, pred ); - return gp; + return extract_with_( key, pred ); } /// Finds the key \p key @@ -639,6 +733,32 @@ namespace cds { namespace container { } //@endcond + /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList -based set) + /** + If \p key is not found the function returns \p end(). + + @note This function is supported only for the set based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find( Q& key ) + { + return find_iterator_( key ); + } + //@cond + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type + find( Q const& key ) + { + return find_iterator_( key ); + } + //@endcond + + /// Finds the key \p key using \p pred predicate for searching /** The function is an analog of \ref cds_nonintrusive_SplitListSet_find_func "find(Q&, Func)" @@ -659,6 +779,35 @@ namespace cds { namespace container { } //@endcond + /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList -based set) + /** + The function is an analog of \p find(Q&) 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 set. + + If \p key is not found the function returns \p end(). + + @note This function is supported only for the set based on \p IterableList + */ + template +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type +#endif + find_with( Q& key, Less pred ) + { + return find_iterator_with_( key, pred ); + } + //@cond + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator >::type + find_with( Q const& key, Less pred ) + { + return find_iterator_with_( key, pred ); + } + //@endcond + /// Checks whether the set contains \p key /** The function searches the item with key equal to \p key @@ -673,14 +822,6 @@ namespace cds { namespace container { { return base_class::contains( key ); } - //@cond - template - CDS_DEPRECATED("deprecated, use contains()") - bool find( Q const& key ) - { - return contains( key ); - } - //@endcond /// Checks whether the map contains \p key using \p pred predicate for searching /** @@ -694,14 +835,6 @@ namespace cds { namespace container { CDS_UNUSED( pred ); return base_class::contains( key, typename maker::template predicate_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 return the item found /** \anchor cds_nonintrusive_SplitListSet_hp_get @@ -732,9 +865,7 @@ namespace cds { namespace container { template guarded_ptr get( Q const& key ) { - guarded_ptr gp; - get_( gp.guard(), key ); - return gp; + return get_( key ); } /// Finds \p key and return the item found @@ -749,9 +880,7 @@ namespace cds { namespace container { template guarded_ptr get_with( Q const& key, Less pred ) { - guarded_ptr gp; - get_with_( gp.guard(), key, pred ); - return gp; + return get_with_( key, pred ); } /// Clears the set (not atomic) @@ -782,30 +911,94 @@ namespace cds { namespace container { return base_class::statistics(); } + /// Returns internal statistics for \p ordered_list + typename ordered_list::stat const& list_statistics() const + { + return base_class::list_statistics(); + } + protected: //@cond using base_class::extract_; using base_class::get_; + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_node_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_node_allocator().Delete( pNode ); + } + + template + bool find_( Q& val, Func f ) + { + return base_class::find( val, [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } ); + } + + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator>::type + find_iterator_( Q& val ) + { + return iterator( base_class::find( val )); + } + + template + bool find_with_( Q& val, Less pred, Func f ) + { + CDS_UNUSED( pred ); + return base_class::find_with( val, typename maker::template predicate_wrapper::type(), + [&f]( node_type& item, Q& val ) { f( item.m_Value, val ); } ); + } + + template + typename std::enable_if< std::is_same::value && is_iterable_list< ordered_list >::value, iterator>::type + find_iterator_with_( Q& val, Less pred ) + { + CDS_UNUSED( pred ); + return iterator( base_class::find_with( val, typename maker::template predicate_wrapper::type())); + } + + struct node_disposer { + void operator()( node_type * pNode ) + { + free_node( pNode ); + } + }; + typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; + + bool insert_node( node_type * pNode ) + { + assert( pNode != nullptr ); + scoped_node_ptr p( pNode ); + + if ( base_class::insert( *pNode )) { + p.release(); + return true; + } + return false; + } + template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + guarded_ptr extract_with_( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::extract_with_( guard, key, typename maker::template predicate_wrapper::type()); + return base_class::extract_with_( key, typename maker::template predicate_wrapper::type()); } template - bool get_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + guarded_ptr get_with_( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return base_class::get_with_( guard, key, typename maker::template predicate_wrapper::type()); + return base_class::get_with_( key, typename maker::template predicate_wrapper::type()); } //@endcond - }; - }} // namespace cds::container #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H