X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fsplit_list_set_nogc.h;h=beca1d3a99c4dee63ee9bd319124ed0877934044;hb=40e34e6d0b104b6f5aff506ad67d43fd410e52bc;hp=49e07c06eba2f4d6290bca0a7cfb44c8402ae43e;hpb=3e8abcbbbbb3809e809bec65a8a4d83cba8c4927;p=libcds.git diff --git a/cds/container/split_list_set_nogc.h b/cds/container/split_list_set_nogc.h index 49e07c06..beca1d3a 100644 --- a/cds/container/split_list_set_nogc.h +++ b/cds/container/split_list_set_nogc.h @@ -1,7 +1,35 @@ -//$$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 @@ -21,7 +49,7 @@ namespace cds { namespace container { @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, + but you should provide an exclusive access to it, see \ref cds_intrusive_item_creating "insert item troubleshooting". */ template < @@ -109,21 +137,13 @@ namespace cds { namespace container { {} 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; @@ -141,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 @@ -188,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 @@ -202,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 @@ -213,20 +267,31 @@ 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 @@ -236,7 +301,7 @@ namespace cds { namespace container { scoped_node_ptr p(pNode); iterator it( base_class::insert_( *pNode )); - if ( it != end() ) { + if ( it != end()) { p.release(); return it; } @@ -257,7 +322,7 @@ namespace cds { namespace container { template iterator insert( const Q& val ) { - return insert_node( alloc_node( val ) ); + return insert_node( alloc_node( val )); } /// Inserts data of type \p value_type created from \p args @@ -267,25 +332,36 @@ namespace cds { namespace container { template iterator emplace( Args&&... args ) { - return insert_node( alloc_node( std::forward(args)... ) ); + return insert_node( alloc_node( std::forward(args)... )); } - /// 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, \p second is true if new item has been added or \p false if the item + item found or inserted (if inserting is not allowed and \p key is not found, the iterator will be \p end()), + + \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::ensure_( *pNode, [](bool /*bNew*/, node_type& /*item*/, node_type& /*val*/){} ); + std::pair ret = base_class::update_( *pNode, + + [](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 ); @@ -293,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 key - /** \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 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_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 maker::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 @@ -341,8 +445,14 @@ 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(); + } }; }} // namespace cds::container -#endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_SET_NOGC_H +#endif // #ifndef CDSLIB_CONTAINER_SPLIT_LIST_SET_NOGC_H