X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_set_rcu.h;h=45fac82a43d80eaf2634c6cf1ad69a56fa55e437;hb=f31988b031453d7fdf7fe212f966554fa558af3e;hp=7655ebedb482e5e0015ff0b9dd98580462e288a5;hpb=0594e601c8b1fcf9f8ca595d49ef025be04aa8d1;p=libcds.git diff --git a/cds/container/michael_set_rcu.h b/cds/container/michael_set_rcu.h index 7655ebed..45fac82a 100644 --- a/cds/container/michael_set_rcu.h +++ b/cds/container/michael_set_rcu.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ - -#ifndef __CDS_CONTAINER_MICHAEL_SET_RCU_H -#define __CDS_CONTAINER_MICHAEL_SET_RCU_H +/* + 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_RCU_H +#define CDSLIB_CONTAINER_MICHAEL_SET_RCU_H #include #include @@ -22,7 +50,7 @@ namespace cds { namespace container { Template parameters are: - \p RCU - one of \ref cds_urcu_gc "RCU type" - - \p OrderedList - ordered list implementation used as the bucket for hash set, for example, + - \p OrderedList - ordered list implementation used as the bucket for hash set, for example, \ref cds_nonintrusive_MichaelList_rcu "MichaelList". The ordered list implementation specifies the type \p T stored in the hash-set, the comparison functor for the type \p T and other features specific for @@ -118,18 +146,33 @@ namespace cds { namespace container { typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash; typedef typename traits::item_counter item_counter; ///< Item counter type - /// Bucket table allocator - typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator; - typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node + typedef typename bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal; protected: - item_counter m_ItemCounter; ///< Item counter - hash m_HashFunctor; ///< Hash functor - bucket_type * m_Buckets; ///< bucket table + //@cond + 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; + + //@endcond + + protected: + item_counter m_ItemCounter; ///< Item counter + hash m_HashFunctor; ///< Hash functor + internal_bucket_type * m_Buckets; ///< bucket table private: //@cond @@ -147,28 +190,55 @@ namespace cds { namespace container { /// Returns the bucket (ordered list) for \p key template - bucket_type& bucket( Q const& key ) + internal_bucket_type& bucket( Q const& key ) { return m_Buckets[ hash_value( key ) ]; } template - bucket_type const& bucket( Q const& key ) const + internal_bucket_type const& bucket( Q const& key ) const { return m_Buckets[ hash_value( key ) ]; } //@endcond public: + ///@name Forward iterators (thread-safe under RCU lock) + //@{ /// 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 cannot be moved across thread boundary since it may contain 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 set. - Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container - for debug purpose only. + You may safely use iterators in multi-threaded environment only under RCU lock. + Otherwise, a crash is possible if another thread deletes the element the iterator points to. + + 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; @@ -196,44 +266,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(); } + + /// 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(); } + + /// 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 - /** @copydetails cds_nonintrusive_MichaelHashSet_hp_ctor + /** + 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 @@ -243,7 +320,6 @@ namespace cds { namespace container { // 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"); @@ -308,44 +384,51 @@ namespace cds { namespace container { return bRet; } - /// Ensures that the item exists in the set + + /// Updates the element /** The operation performs inserting or changing data with lock-free manner. - If the \p val key not found in the set, then the new item created from \p val - is inserted into the set. Otherwise, the functor \p func is called with the item found. - The functor \p Func signature is: + If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true. + Otherwise, the functor \p func is called with item found. + The functor signature is: \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: - \p bNew - \p true if the item has been inserted, \p false otherwise - \p item - item of the set - - \p val - argument \p key passed into the \p ensure function + - \p val - argument \p val passed into the \p %update() function The functor may change non-key fields of the \p item. The function applies RCU lock internally. - Returns std::pair where \p first is true if operation is successfull, - \p second is true if new item has been added or \p false if the item with \p key + Returns std::pair where \p first is \p true if operation is successful, + \p second is \p true if new item has been added or \p false if the item with \p key already is in the set. - @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting". - \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level + @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, Func func ) + std::pair update( const Q& val, Func func, bool bAllowInsert = true ) { - std::pair bRet = bucket( val ).ensure( val, func ); - if ( bRet.first && bRet.second ) + std::pair bRet = bucket( val ).update( val, func, bAllowInsert ); + if ( bRet.second ) ++m_ItemCounter; return bRet; + }//@cond + template + CDS_DEPRECATED("ensure() is deprecated, use update()") + std::pair ensure( const Q& val, Func func ) + { + return update( val, func, true ); } + //@endcond /// Inserts data of type \p value_type created from \p args /** @@ -356,7 +439,8 @@ namespace cds { namespace container { template bool emplace( Args&&... args ) { - bool bRet = bucket( value_type(std::forward(args)...) ).emplace( std::forward(args)... ); + typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward( args )... ); + bool bRet = bucket( internal_bucket_type::node_to_value( *pNode ) ).insert_node( pNode ); if ( bRet ) ++m_ItemCounter; return bRet; @@ -449,14 +533,14 @@ namespace cds { namespace container { /// Extracts an item from the set /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract The function searches an item with key equal to \p key in the set, - unlinks it from the set, places item pointer into \p dest argument, and returns \p true. - If the item with the key equal to \p key is not found the function return \p false. + unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found. + If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr. - @note The function does NOT call RCU read-side lock or synchronization, - and does NOT dispose the item found. It just excludes the item from the set - and returns a pointer to item found. - You should lock RCU before calling of the function, and you should synchronize RCU - outside the RCU lock to free extracted item + The function just excludes the item from the set and returns a pointer to item found. + Depends on \p bucket_type you should or should not lock RCU before calling of this function: + - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked + - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked + See ordered list implementation for details. \code #include @@ -470,17 +554,15 @@ namespace cds { namespace container { rcu_michael_set theSet; // ... - rcu_michael_set::exempt_ptr p; - { - // first, we should lock RCU - rcu_michael_set::rcu_lock lock; - - // Now, you can apply extract function - // Note that you must not delete the item found inside the RCU lock - if ( theSet.extract( p, 10 )) { - // do something with p - ... - } + typename rcu_michael_set::exempt_ptr p; + + // For MichaelList we should not lock RCU + + // Note that you must not delete the item found inside the RCU lock + p = theSet.extract( 10 ); + if ( p ) { + // do something with p + ... } // We may safely release p here @@ -489,30 +571,27 @@ namespace cds { namespace container { \endcode */ template - bool extract( exempt_ptr& dest, Q const& key ) + exempt_ptr extract( Q const& key ) { - if ( bucket( key ).extract( dest, key )) { + exempt_ptr p = bucket( key ).extract( key ); + if ( p ) --m_ItemCounter; - return true; - } - return false; + return p; } /// Extracts an item from the set using \p pred predicate for searching /** - The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_extract "extract(exempt_ptr&, Q const&)" - but \p pred is used for key comparing. + The function is an analog of \p extract(Q const&) 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. */ template - bool extract_with( exempt_ptr& dest, Q const& key, Less pred ) + exempt_ptr extract_with( Q const& key, Less pred ) { - if ( bucket( key ).extract_with( dest, key, pred )) { + exempt_ptr p = bucket( key ).extract_with( key, pred ); + if ( p ) --m_ItemCounter; - return true; - } - return false; + return p; } /// Finds the key \p key @@ -543,10 +622,17 @@ namespace cds { namespace container { The function returns \p true if \p key is found, \p false otherwise. */ template - bool find( Q& key, Func f ) const + bool find( Q& key, Func f ) + { + return bucket( key ).find( key, f ); + } + //@cond + template + bool find( Q const& key, Func f ) { return bucket( key ).find( key, f ); } + //@endcond /// Finds the key \p key using \p pred predicate for searching /** @@ -556,43 +642,67 @@ namespace cds { namespace container { \p Less must imply the same element order as the comparator used for building the set. */ template - bool find_with( Q& key, Less pred, Func f ) const + bool find_with( Q& key, Less pred, Func f ) { return bucket( key ).find_with( key, pred, f ); } + //@cond + template + bool find_with( Q const& key, Less pred, Func f ) + { + return bucket( key ).find_with( key, pred, f ); + } + //@endcond - /// Finds the key \p key - /** \anchor cds_nonintrusive_MichealSet_rcu_find_val + /// Checks whether the set contains \p key + /** The function searches the item with key equal to \p key - and returns \p true if it is found, and \p false otherwise. + and returns \p true if the key is found, and \p false otherwise. Note the hash functor specified for class \p Traits template parameter - should accept a parameter of type \p Q that may be not the same as \p value_type. + should accept a parameter of type \p Q that can be not the same as \p value_type. */ template - bool find( Q const & key ) const + bool contains( Q const& key ) + { + return bucket( key ).contains( key ); + } + //@cond + template + CDS_DEPRECATED("use contains()") + bool find( Q const& key ) { - return bucket( key ).find( 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_MichealSet_rcu_find_val "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 - bool find_with( Q const & key, Less pred ) const + bool contains( Q const& key, Less pred ) + { + return bucket( key ).contains( key, pred ); + } + //@cond + template + CDS_DEPRECATED("use contains()") + bool find_with( Q const& key, Less pred ) { - return bucket( key ).find_with( key, pred ); + return contains( key, pred ); } + //@endcond /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get The function searches the item with key equal to \p key and returns the pointer to item found. If \p key is not found it returns \p nullptr. + Note the type of returned value depends on underlying \p bucket_type. + For details, see documentation of ordered list you use. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -601,23 +711,24 @@ namespace cds { namespace container { \code typedef cds::container::MichaelHashSet< your_template_parameters > hash_set; hash_set theSet; + typename hash_set::raw_ptr gp; // ... { // Lock RCU hash_set::rcu_lock lock; - foo * pVal = theSet.get( 5 ); - if ( pVal ) { + gp = theSet.get( 5 ); + if ( gp ) { // Deal with pVal //... } // Unlock RCU by rcu_lock destructor - // pVal can be freed at any time after RCU has been unlocked + // gp can be reclaimed at any time after RCU has been unlocked } \endcode */ template - value_type * get( Q const& key ) const + raw_ptr get( Q const& key ) { return bucket( key ).get( key ); } @@ -632,7 +743,7 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the set. */ template - value_type * get_with( Q const& key, Less pred ) const + raw_ptr get_with( Q const& key, Less pred ) { return bucket( key ).get_with( key, pred ); } @@ -675,4 +786,4 @@ namespace cds { namespace container { }} // namespace cds::container -#endif // ifndef __CDS_CONTAINER_MICHAEL_SET_RCU_H +#endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H