X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_set_nogc.h;h=b3e7db4be2203531c6ce1da68e597f187ec5f5ca;hb=1e96341781fa47f1607e66bf15045ca5682781e5;hp=46b6058e73e4d10edc9a036c3829eecb398ab27e;hpb=7d15399a4d18ae2061ddb01656d85dbc940ff915;p=libcds.git diff --git a/cds/container/michael_set_nogc.h b/cds/container/michael_set_nogc.h index 46b6058e..b3e7db4b 100644 --- a/cds/container/michael_set_nogc.h +++ b/cds/container/michael_set_nogc.h @@ -1,9 +1,37 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_MICHAEL_SET_NOGC_H -#define __CDS_CONTAINER_MICHAEL_SET_NOGC_H - -#include +/* + This file is a part of libcds - Concurrent Data Structures library + + (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_MICHAEL_SET_NOGC_H +#define CDSLIB_CONTAINER_MICHAEL_SET_NOGC_H + +#include #include #include @@ -13,51 +41,60 @@ namespace cds { namespace container { /** @ingroup cds_nonintrusive_set \anchor cds_nonintrusive_MichaelHashSet_nogc - This specialization is intended for so-called persistent usage when no item + This specialization is so-called append-only when no item reclamation may be performed. The class does not support deleting of list item. See \ref cds_nonintrusive_MichaelHashSet_hp "MichaelHashSet" for description of template parameters. - The template parameter \p OrderedList should be any gc::nogc-derived ordered list, for example, - \ref cds_nonintrusive_MichaelList_nogc "persistent MichaelList". - - The interface of the specialization is a slightly different. + The template parameter \p OrderedList should be any \p gc::nogc -derived ordered list, for example, + \ref cds_nonintrusive_MichaelList_nogc "append-only MichaelList". */ template < class OrderedList, #ifdef CDS_DOXYGEN_INVOKED - class Traits = michael_set::type_traits + class Traits = michael_set::traits #else class Traits #endif > - class MichaelHashSet< gc::nogc, OrderedList, Traits > + class MichaelHashSet< cds::gc::nogc, OrderedList, Traits > { public: - typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation - typedef Traits options ; ///< Traits template parameters + typedef cds::gc::nogc gc; ///< Garbage collector + typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation + typedef Traits traits; ///< Set traits - typedef typename bucket_type::value_type value_type ; ///< type of value stored in the list - typedef gc::nogc gc ; ///< Garbage collector - typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor + typedef typename bucket_type::value_type value_type; ///< type of value stored in the list + typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor /// Hash functor for \ref value_type and all its derivatives that you use - typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash; - typedef typename options::item_counter item_counter ; ///< Item counter type - - /// Bucket table allocator - typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator; + typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash; + typedef typename traits::item_counter item_counter; ///< Item counter type protected: //@cond - typedef typename bucket_type::iterator bucket_iterator; - typedef typename bucket_type::const_iterator bucket_const_iterator; + class internal_bucket_type: public bucket_type + { + typedef bucket_type base_class; + public: + using base_class::node_type; + using base_class::alloc_node; + using base_class::insert_node; + using base_class::node_to_value; + }; + + /// Bucket table allocator + typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator; + + typedef typename bucket_type::iterator bucket_iterator; + typedef typename bucket_type::const_iterator bucket_const_iterator; //@endcond protected: - item_counter m_ItemCounter ; ///< Item counter - hash m_HashFunctor ; ///< Hash functor - - bucket_type * m_Buckets ; ///< bucket table + //@cond + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + internal_bucket_type * m_Buckets; ///< bucket table + //@endcond private: //@cond @@ -65,6 +102,7 @@ namespace cds { namespace container { //@endcond protected: + //@cond /// Calculates hash value of \p key template size_t hash_value( const Q& key ) const @@ -74,17 +112,48 @@ namespace cds { namespace container { /// Returns the bucket (ordered list) for \p key template - bucket_type& bucket( const Q& key ) + internal_bucket_type& bucket( const Q& key ) { return m_Buckets[ hash_value( key ) ]; } + //@endcond public: + ///@name Forward iterators + //@{ /// Forward iterator /** The forward iterator for Michael's set 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 michael_set::details::iterator< bucket_type, false > iterator; @@ -115,45 +184,51 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a set - //@{ const_iterator begin() const { return get_const_begin(); } - const_iterator cbegin() + + /// Returns a forward const iterator addressing the first element in a set + const_iterator cbegin() const { return get_const_begin(); } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a set - //@{ const_iterator end() const { return get_const_end(); } - const_iterator cend() + + /// Returns an const iterator that addresses the location succeeding the last element in a set + const_iterator cend() const { return get_const_end(); } - //@} + //@} private: - //@{ + //@cond const_iterator get_const_begin() const { - return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); + return const_iterator( const_cast(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() ); } const_iterator get_const_end() const { - return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); + return const_iterator( const_cast(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() ); } - //@} + //@endcond public: /// Initialize hash set /** - See \ref cds_nonintrusive_MichaelHashSet_hp "MichaelHashSet" ctor for explanation + The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount + when you create an object. + \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10. + Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [O(nLoadFactor)]. + + The ctor defines hash table size as rounding nMaxItemCount / nLoadFactor up to nearest power of two. */ MichaelHashSet( size_t nMaxItemCount, ///< estimation of max item count in the hash set @@ -161,15 +236,16 @@ namespace cds { namespace container { ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor )) { // GC and OrderedList::gc must be the same - static_assert(( std::is_same::value ), "GC and OrderedList::gc must be the same"); + static_assert( std::is_same::value, "GC and OrderedList::gc must be the same"); // atomicity::empty_item_counter is not allowed as a item counter - static_assert(( !std::is_same::value ), "atomicity::empty_item_counter is not allowed as a item counter"); + static_assert( !std::is_same::value, + "cds::atomicity::empty_item_counter is not allowed as a item counter"); m_Buckets = bucket_table_allocator().NewArray( bucket_count() ); } - /// Clear hash set and destroy it + /// Clears hash set and destroys it ~MichaelHashSet() { clear(); @@ -186,7 +262,7 @@ namespace cds { namespace container { template iterator insert( const Q& val ) { - bucket_type& refBucket = bucket( val ); + internal_bucket_type& refBucket = bucket( val ); bucket_iterator it = refBucket.insert( val ); if ( it != refBucket.end() ) { @@ -197,20 +273,16 @@ namespace cds { namespace container { return end(); } -#ifdef CDS_EMPLACE_SUPPORT /// Inserts data of type \ref value_type constructed with std::forward(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 */ template iterator emplace( Args&&... args ) { - bucket_type& refBucket = bucket( value_type(std::forward(args)...)); - bucket_iterator it = refBucket.emplace( std::forward(args)... ); - + typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward( args )... ); + internal_bucket_type& refBucket = bucket( internal_bucket_type::node_to_value( *pNode )); + bucket_iterator it = refBucket.insert_node( pNode ); if ( it != refBucket.end() ) { ++m_ItemCounter; return iterator( it, &refBucket, m_Buckets + bucket_count() ); @@ -218,76 +290,98 @@ namespace cds { namespace container { return end(); } -#endif - /// Ensures that the item \p val exists in the set + /// Updates the element /** - The operation inserts new item if the key \p val is not found in the set. - Otherwise, the function returns an iterator that points to item found. + The operation performs inserting or changing data with lock-free manner. + + If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true. + + Returns std::pair where \p first is an iterator pointing to + item found or inserted, or \p end() if \p bAllowInsert is \p false, + + \p second is true if new item has been added or \p false if the item is already in the set. - 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 - 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". + \ref cds_intrusive_LazyList_hp "LazyList" 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& val, bool bAllowInsert = true ) { - bucket_type& refBucket = bucket( val ); - std::pair ret = refBucket.ensure( val ); + internal_bucket_type& refBucket = bucket( val ); + std::pair ret = refBucket.update( val, bAllowInsert ); if ( ret.first != refBucket.end() ) { if ( ret.second ) ++m_ItemCounter; return std::make_pair( iterator( ret.first, &refBucket, m_Buckets + bucket_count() ), ret.second ); } - return std::make_pair( end(), ret.second ); } + //@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( Q const& val ) + { + return update( val, true ); + } + //@endcond - /// Find the key \p key - /** \anchor cds_nonintrusive_MichealSet_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 + or \ref end() otherwise. + + Note the hash functor specified for class \p Traits template parameter + should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - iterator find( Q const& key ) + iterator contains( Q const& key ) { - bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find( key ); + internal_bucket_type& refBucket = bucket( key ); + bucket_iterator it = refBucket.contains( key ); if ( it != refBucket.end() ) return iterator( it, &refBucket, m_Buckets + bucket_count() ); return end(); } + //@cond + template + CDS_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_MichealSet_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. */ template - iterator find_with( Q const& key, Less pred ) + iterator contains( Q const& key, Less pred ) { - bucket_type& refBucket = bucket( key ); - bucket_iterator it = refBucket.find_with( key, pred ); + internal_bucket_type& refBucket = bucket( key ); + bucket_iterator it = refBucket.contains( key, pred ); if ( it != refBucket.end() ) return iterator( it, &refBucket, m_Buckets + bucket_count() ); return end(); } + //@cond + template + CDS_DEPRECATED("use contains()") + iterator find_with( Q const& key, Less pred ) + { + return contains( key, pred ); + } + //@endcond - - /// Clears the set (non-atomic, not thread-safe) - /** - The function deletes all items from the set. - The function is not atomic and even not thread-safe. - It cleans up each bucket and then resets the item counter to zero. - If there are a thread that performs insertion while \p clear is working the result is undefined in general case: - empty() may return \p true but the set may contain item(s). - */ + /// Clears the set (not atomic) void clear() { for ( size_t i = 0; i < bucket_count(); ++i ) @@ -295,10 +389,9 @@ namespace cds { namespace container { m_ItemCounter.reset(); } - /// Checks if the set is empty /** - Emptiness is checked by item counting: if item count is zero then the set is empty. + The emptiness is checked by the item counting: if item count is zero then the set is empty. Thus, the correct item counting feature is an important part of Michael's set implementation. */ bool empty() const @@ -314,7 +407,7 @@ namespace cds { namespace container { /// Returns the size of hash table /** - Since MichaelHashSet cannot dynamically extend the hash table size, + Since \p %MichaelHashSet cannot dynamically extend the hash table size, the value returned is an constant depending on object initialization parameters; see MichaelHashSet::MichaelHashSet for explanation. */ @@ -326,4 +419,4 @@ namespace cds { namespace container { }} // cds::container -#endif // ifndef __CDS_CONTAINER_MICHAEL_SET_NOGC_H +#endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_NOGC_H