X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fsplit_list_set_nogc.h;h=beca1d3a99c4dee63ee9bd319124ed0877934044;hb=e7b85eede16163c24360bf45861570d482a924f7;hp=2dfaa74aff0853dbb7cc3ee1726a1388985dde5a;hpb=7d15399a4d18ae2061ddb01656d85dbc940ff915;p=libcds.git diff --git a/cds/container/split_list_set_nogc.h b/cds/container/split_list_set_nogc.h index 2dfaa74a..beca1d3a 100644 --- a/cds/container/split_list_set_nogc.h +++ b/cds/container/split_list_set_nogc.h @@ -1,30 +1,61 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H -#define __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H + (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_NOGC_H +#define CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H #include -#include +#include #include #include namespace cds { namespace container { - /// Split-ordered list set (template specialization for gc::nogc) + /// Split-ordered list set (template specialization for \p gc::nogc) /** @ingroup cds_nonintrusive_set \anchor cds_nonintrusive_SplitListSet_nogc - This specialization is intended for so-called persistent usage when no item + This specialization is so-called append-only container when no item reclamation may be performed. The class does not support deleting of list item. See \ref cds_nonintrusive_SplitListSet_hp "SplitListSet" for description of template parameters. - The interface of the specialization is a slightly different. + @warning Many member functions return an iterator pointing to an item. + The iterator can be used to set up field of the item, + but you should provide an exclusive access to it, + see \ref cds_intrusive_item_creating "insert item troubleshooting". */ template < class T, #ifdef CDS_DOXYGEN_INVOKED - class Traits = split_list::type_traits + class Traits = split_list::traits #else class Traits #endif @@ -38,24 +69,27 @@ namespace cds { namespace container { { protected: //@cond - typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits > options; - typedef typename options::type base_class; + typedef details::make_split_list_set< cds::gc::nogc, T, typename Traits::ordered_list, split_list::details::wrap_set_traits > maker; + typedef typename maker::type base_class; //@endcond public: - typedef typename options::gc gc ; ///< Garbage collector - typedef typename options::value_type value_type ; ///< type of value stored in the list - typedef typename options::ordered_list ordered_list ; ///< Underlying ordered list class - typedef typename base_class::key_comparator key_comparator ; ///< key comparison functor + typedef cds::gc::nogc gc; ///< Garbage collector + typedef T value_type; ///< type of value to be stored in the list + typedef Traits traits; ///< List traits + + typedef typename maker::ordered_list ordered_list; ///< Underlying ordered list class + typedef typename base_class::key_comparator key_comparator; ///< key comparison functor /// Hash functor for \ref value_type and all its derivatives that you use typedef typename base_class::hash hash; - typedef typename base_class::item_counter item_counter ; ///< Item counter type + typedef typename base_class::item_counter item_counter; ///< Item counter type + typedef typename base_class::stat stat; ///< Internal statistics protected: //@cond - typedef typename options::cxx_node_allocator cxx_node_allocator; - typedef typename options::node_type node_type; + typedef typename maker::cxx_node_allocator cxx_node_allocator; + typedef typename maker::node_type node_type; template static node_type * alloc_node(Q const& v ) @@ -63,13 +97,11 @@ namespace cds { namespace container { return cxx_node_allocator().New( v ); } -# ifdef CDS_EMPLACE_SUPPORT template static node_type * alloc_node( Args&&... args ) { return cxx_node_allocator().MoveNew( std::forward(args)...); } -# endif static void free_node( node_type * pNode ) { @@ -83,27 +115,14 @@ namespace cds { namespace container { } }; typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - - //@endcond - - protected: - //@cond -# ifndef CDS_CXX11_LAMBDA_SUPPORT - struct empty_ensure_functor - { - void operator()( bool /*bNew*/, node_type& /*item*/, node_type& /*val*/ ) - {} - }; -# endif //@endcond - public: /// Initialize split-ordered list of default capacity /** The default capacity is defined in bucket table constructor. - See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_ducket_table - which selects by intrusive::split_list::dynamic_bucket_table option. + See \p intrusive::split_list::expandable_bucket_table, \p intrusive::split_list::static_bucket_table + which selects by \p split_list::dynamic_bucket_table option. */ SplitListSet() : base_class() @@ -111,28 +130,20 @@ namespace cds { namespace container { /// Initialize split-ordered list SplitListSet( - size_t nItemCount ///< estimate average of item count + size_t nItemCount ///< estimated average of item count , size_t nLoadFactor = 1 ///< load factor - average item count per bucket. Small integer up to 10, default is 1. ) : base_class( nItemCount, nLoadFactor ) {} protected: - /// Forward iterator - /** - \p IsConst - constness boolean flag - - The forward iterator has the following features: - - it has no post-increment operator - - it depends on underlying ordered list iterator - */ + //@cond 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; @@ -150,11 +161,9 @@ namespace cds { namespace container { {} protected: - //@cond explicit iterator_type( iterator_base_class const& src ) : iterator_base_class( src ) {} - //@endcond public: /// Dereference operator @@ -197,9 +206,45 @@ namespace cds { namespace container { return iterator_base_class::operator!=(i); } }; + //@endcond public: + ///@name Forward iterators + //@{ /// Forward iterator + /** + The forward iterator for split-list is based on \p OrderedList forward iterator and has some features: + - it has no post-increment operator + - it iterates items in unordered fashion + + 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 @@ -211,7 +256,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( base_class::begin() ); + return iterator( base_class::begin()); } /// Returns an iterator that addresses the location succeeding the last element in a set @@ -222,30 +267,41 @@ namespace cds { namespace container { */ iterator end() { - return iterator( base_class::end() ); + return iterator( base_class::end()); } /// Returns a forward const iterator addressing the first element in a set const_iterator begin() const { - return const_iterator( base_class::begin() ); + return cbegin(); + } + /// Returns a forward const iterator addressing the first element in a set + const_iterator cbegin() const + { + return const_iterator( base_class::cbegin()); } /// Returns an const iterator that addresses the location succeeding the last element in a set const_iterator end() const { - return const_iterator( base_class::end() ); + return cend(); + } + /// Returns an const iterator that addresses the location succeeding the last element in a set + const_iterator cend() const + { + return const_iterator( base_class::cend()); } + //@} protected: //@cond iterator insert_node( node_type * pNode ) { - assert( pNode != null_ptr() ); + assert( pNode != nullptr ); scoped_node_ptr p(pNode); iterator it( base_class::insert_( *pNode )); - if ( it != end() ) { + if ( it != end()) { p.release(); return it; } @@ -259,51 +315,53 @@ namespace cds { namespace container { /** The function inserts \p val in the set if it does not contain an item with key equal to \p val. - The \ref value_type should be constructible from a value of type \p Q. + The \p value_type should be constructible from a value of type \p Q. - Return an iterator pointing to inserted item if success \ref end() otherwise + Return an iterator pointing to inserted item if success \p end() otherwise */ template iterator insert( const Q& val ) { - return insert_node( alloc_node( val ) ); + return insert_node( alloc_node( val )); } -#ifdef CDS_EMPLACE_SUPPORT - /// Inserts data of type \ref value_type constructed with std::forward(args)... + /// Inserts data of type \p value_type created from \p args /** - Return an iterator pointing to inserted item if success \ref end() otherwise - - This function is available only for compiler that supports - variadic template and move semantics + Return an iterator pointing to inserted item if success \p end() otherwise */ template iterator emplace( Args&&... args ) { - return insert_node( alloc_node( std::forward(args)... ) ); + return insert_node( alloc_node( std::forward(args)... )); } -#endif - /// Ensures that the item \p val exists in the set + /// Updates the item /** - The operation inserts new item created from \p val if the key \p val is not found in the set. - Otherwise, the function returns an iterator that points to item found. - The \p value_type should be constructible from a value of type \p Q. + If \p key is not in the set and \p bAllowInsert is \p true, the function inserts a new item. + Otherwise, the function returns an iterator pointing to the item found. + + Returns std::pair where \p first is an iterator pointing to + item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()), - Returns std::pair where \p first is an iterator pointing to - item found or inserted, \p second is true if new item has been added or \p false if the item + \p second is true if new item has been added or \p false if the item already is in the set. + + @warning If the set is based on \ref cds_nonintrusive_MichaelList_nogc "MichaelList", + + see \ref cds_intrusive_item_creating "insert item troubleshooting". + \ref cds_nonintrusive_LazyList_nogc "LazyList" as the base provides exclusive access to inserted item + + and does not require any node-level synchronization. */ template - std::pair ensure( const Q& val ) + std::pair update( Q const& key, bool bAllowInsert = true ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( key )); + + std::pair ret = base_class::update_( *pNode, -# ifdef CDS_CXX11_LAMBDA_SUPPORT - std::pair ret = base_class::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} ); -# else - std::pair ret = base_class::ensure_( *pNode, empty_ensure_functor() ); -# endif + [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){}, + bAllowInsert ); if ( ret.first != base_class::end() && ret.second ) { pNode.release(); return std::make_pair( iterator(ret.first), ret.second ); @@ -311,31 +369,59 @@ namespace cds { namespace container { return std::make_pair( iterator(ret.first), ret.second ); } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( const Q& val ) + { + return update( val, true ); + } + //@endcond - /// Find the key \p val - /** \anchor cds_nonintrusive_SplitListSet_nogc_find - + /// Checks whether the set contains \p key + /** The function searches the item with key equal to \p key - and returns an iterator pointed to item found if the key is found, - and \ref end() otherwise + and returns an iterator pointed to item found and \ref end() otherwise */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { return iterator( base_class::find_( key )); } + //@cond + template + CDS_DEPRECATED("deprecated, use contains()") + iterator find( Q const& key ) + { + return contains( key ); + } + //@endcond - /// Finds the key \p val 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_SplitListSet_nogc_find "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 Less must imply the same element order as the comparator used for building the set. + \p pred must imply the same element order as the comparator used for building the set. */ template + iterator contains( Q const& key, Less pred ) + { + CDS_UNUSED( pred ); + return iterator( base_class::find_with_( key, typename maker::template predicate_wrapper::type())); + } + //@cond + // eprecated, use contains() + template iterator find_with( Q const& key, Less pred ) { - return iterator( base_class::find_with_( key, typename options::template predicate_wrapper::type() )); + return contains( key, pred ); + } + //@endcond + + /// Clears the set (not atomic, for debugging purposes only) + void clear() + { + base_class::clear(); } /// Checks if the set is empty @@ -353,8 +439,20 @@ namespace cds { namespace container { { return base_class::size(); } + + /// Returns internal statistics + stat const& statistics() const + { + return base_class::statistics(); + } + + /// Returns internal statistics for \p ordered_list + typename ordered_list::stat const& list_statistics() const + { + return base_class::list_statistics(); + } }; }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H +#endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H