X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=cds%2Fcontainer%2Fsplit_list_set.h;h=47d48865ea46408e8960f8e389d7e81768950ada;hb=1132246d5685f87a5b240e077b7e88d56e38b1ff;hp=5003474b90f79b7a148d9d776a9484591670ab7b;hpb=0bae61829528ed14ffee72c2e11ab0f9ce088cc1;p=libcds.git diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h index 5003474b..47d48865 100644 --- a/cds/container/split_list_set.h +++ b/cds/container/split_list_set.h @@ -1,11 +1,11 @@ /* This file is a part of libcds - Concurrent Data Structures library - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + (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: @@ -25,7 +25,7 @@ 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. + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H @@ -33,6 +33,7 @@ #include #include +#include namespace cds { namespace container { @@ -185,69 +186,14 @@ namespace cds { namespace container { 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: /// Guarded pointer typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set > guarded_ptr; - 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: //@cond template @@ -358,27 +304,27 @@ namespace cds { namespace container { \code class iterator { public: - // Default constructor - iterator(); + // Default constructor + iterator(); - // Copy construtor - iterator( iterator const& src ); + // Copy construtor + iterator( iterator const& src ); - // Dereference operator - value_type * operator ->() const; + // Dereference operator + value_type * operator ->() const; - // Dereference operator - value_type& operator *() const; + // Dereference operator + value_type& operator *() const; - // Preincrement operator - iterator& operator ++(); + // Preincrement operator + iterator& operator ++(); - // Assignment operator - iterator& operator = (iterator const& src); + // Assignment operator + iterator& operator = (iterator const& src); - // Equality operators - bool operator ==(iterator const& i ) const; - bool operator !=(iterator const& i ) const; + // Equality operators + bool operator ==(iterator const& i ) const; + bool operator !=(iterator const& i ) const; }; \endcode */ @@ -443,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 @@ -468,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(); @@ -489,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. @@ -496,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: @@ -509,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 ); @@ -531,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()") @@ -609,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, @@ -638,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 @@ -655,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 @@ -698,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)" @@ -718,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 @@ -732,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 /** @@ -753,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 @@ -791,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 @@ -808,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) @@ -841,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& v ) { f( item.m_Value, v ); } ); + } + + 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& v ) { f( item.m_Value, v ); } ); + } + template - bool extract_with_( typename guarded_ptr::native_guard& guard, Q const& key, Less pred ) + 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 base_class::extract_with_( guard, key, typename maker::template predicate_wrapper::type()); + 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 get_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::get_with_( guard, key, typename maker::template predicate_wrapper::type()); + return base_class::extract_with_( key, typename maker::template predicate_wrapper::type()); } - //@endcond + template + guarded_ptr get_with_( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return base_class::get_with_( key, typename maker::template predicate_wrapper::type()); + } + //@endcond }; - }} // namespace cds::container #endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_H