3 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H
4 #define CDSLIB_CONTAINER_MICHAEL_SET_RCU_H
6 #include <cds/container/details/michael_set_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace container {
11 /// Michael's hash set (template specialization for \ref cds_urcu_desc "RCU")
12 /** @ingroup cds_nonintrusive_set
13 \anchor cds_nonintrusive_MichaelHashSet_rcu
16 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
18 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
19 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
20 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
21 However, each bucket may contain unbounded number of items.
23 Template parameters are:
24 - \p RCU - one of \ref cds_urcu_gc "RCU type"
25 - \p OrderedList - ordered list implementation used as the bucket for hash set, for example,
26 \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
27 The ordered list implementation specifies the type \p T stored in the hash-set,
28 the comparison functor for the type \p T and other features specific for
30 - \p Traits - set traits, default is michael_set::traits.
31 Instead of defining \p Traits struct you may use option-based syntax with michael_set::make_traits metafunction.
33 About hash functor see \ref cds_nonintrusive_MichaelHashSet_hash_functor "MichaelSet hash functor".
37 Suppose, we have the following type \p Foo that we want to store in your \p %MichaelHashSet:
40 int nKey ; // key field
41 int nVal ; // value field
45 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
46 that will be used as a bucket for the set. We will cds::urcu::general_buffered<> RCU type and
47 MichaelList as a bucket type.
48 You should include RCU-related header file (<tt>cds/urcu/general_buffered.h</tt> in this example)
49 before including <tt>cds/container/michael_set_rcu.h</tt>.
50 Also, for ordered list we should develop a comparator for our \p Foo struct.
52 #include <cds/urcu/general_buffered.h>
53 #include <cds/container/michael_list_rcu.h>
54 #include <cds/container/michael_set_rcu.h>
56 namespace cc = cds::container;
60 int operator ()(Foo const& v1, Foo const& v2 ) const
62 if ( std::less( v1.nKey, v2.nKey ))
64 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
69 typedef cc::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo,
70 typename cc::michael_list::make_traits<
71 cc::opt::compare< Foo_cmp > // item comparator option
75 // Hash functor for Foo
77 size_t operator ()( int i ) const
79 return std::hash( i );
81 size_t operator()( Foo const& i ) const
83 return std::hash( i.nKey );
88 // Note that \p RCU template parameter of ordered list must be equal \p RCU for the set.
89 typedef cc::MichaelHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, bucket_list,
90 cc::michael_set::make_traits<
91 cc::opt::hash< foo_hash >
101 #ifdef CDS_DOXYGEN_INVOKED
102 class Traits = michael_set::traits
107 class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
110 typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector
111 typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation
112 typedef Traits traits; ///< Set traits
114 typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list
115 typedef typename bucket_type::key_comparator key_comparator; ///< key comparing functor
117 /// Hash functor for \ref value_type and all its derivatives that you use
118 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
119 typedef typename traits::item_counter item_counter; ///< Item counter type
121 /// Bucket table allocator
122 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
124 typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock
125 typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
126 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
127 static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
130 typedef cds::container::michael_set::implementation_tag implementation_tag;
134 item_counter m_ItemCounter; ///< Item counter
135 hash m_HashFunctor; ///< Hash functor
136 bucket_type * m_Buckets; ///< bucket table
140 const size_t m_nHashBitmask;
145 /// Calculates hash value of \p key
146 template <typename Q>
147 size_t hash_value( Q const& key ) const
149 return m_HashFunctor( key ) & m_nHashBitmask;
152 /// Returns the bucket (ordered list) for \p key
153 template <typename Q>
154 bucket_type& bucket( Q const& key )
156 return m_Buckets[ hash_value( key ) ];
158 template <typename Q>
159 bucket_type const& bucket( Q const& key ) const
161 return m_Buckets[ hash_value( key ) ];
167 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
168 - it has no post-increment operator
169 - it iterates items in unordered fashion
170 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
171 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
172 deleting operations it is no guarantee that you iterate all item in the set.
174 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
175 for debug purpose only.
177 typedef michael_set::details::iterator< bucket_type, false > iterator;
179 /// Const forward iterator
180 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
182 /// Returns a forward iterator addressing the first element in a set
184 For empty set \code begin() == end() \endcode
188 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
191 /// Returns an iterator that addresses the location succeeding the last element in a set
193 Do not use the value returned by <tt>end</tt> function to access any item.
194 The returned value can be used only to control reaching the end of the set.
195 For empty set \code begin() == end() \endcode
199 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
202 /// Returns a forward const iterator addressing the first element in a set
204 const_iterator begin() const
206 return get_const_begin();
208 const_iterator cbegin() const
210 return get_const_begin();
214 /// Returns an const iterator that addresses the location succeeding the last element in a set
216 const_iterator end() const
218 return get_const_end();
220 const_iterator cend() const
222 return get_const_end();
228 const_iterator get_const_begin() const
230 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
232 const_iterator get_const_end() const
234 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
239 /// Initialize hash set
240 /** @copydetails cds_nonintrusive_MichaelHashSet_hp_ctor
243 size_t nMaxItemCount, ///< estimation of max item count in the hash set
244 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
245 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
247 // GC and OrderedList::gc must be the same
248 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
250 // atomicity::empty_item_counter is not allowed as a item counter
251 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
252 "atomicity::empty_item_counter is not allowed as a item counter");
254 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
257 /// Clears hash set and destroys it
261 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
266 The function creates a node with copy of \p val value
267 and then inserts the node created into the set.
269 The type \p Q should contain as minimum the complete key for the node.
270 The object of \ref value_type should be constructible from a value of type \p Q.
271 In trivial case, \p Q is equal to \ref value_type.
273 The function applies RCU lock internally.
275 Returns \p true if \p val is inserted into the set, \p false otherwise.
277 template <typename Q>
278 bool insert( Q const& val )
280 const bool bRet = bucket( val ).insert( val );
288 The function allows to split creating of new item into two part:
289 - create item with key only
290 - insert new item into the set
291 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
293 The functor signature is:
295 void func( value_type& val );
297 where \p val is the item inserted.
298 The user-defined functor is called only if the inserting is success.
300 The function applies RCU lock internally.
302 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
303 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
306 template <typename Q, typename Func>
307 bool insert( Q const& val, Func f )
309 const bool bRet = bucket( val ).insert( val, f );
315 /// Ensures that the item exists in the set
317 The operation performs inserting or changing data with lock-free manner.
319 If the \p val key not found in the set, then the new item created from \p val
320 is inserted into the set. Otherwise, the functor \p func is called with the item found.
321 The functor \p Func signature is:
324 void operator()( bool bNew, value_type& item, const Q& val );
329 - \p bNew - \p true if the item has been inserted, \p false otherwise
330 - \p item - item of the set
331 - \p val - argument \p key passed into the \p ensure function
333 The functor may change non-key fields of the \p item.
335 The function applies RCU lock internally.
337 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
338 \p second is true if new item has been added or \p false if the item with \p key
339 already is in the set.
341 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
342 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
345 template <typename Q, typename Func>
346 std::pair<bool, bool> ensure( const Q& val, Func func )
348 std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
349 if ( bRet.first && bRet.second )
354 /// Inserts data of type \p value_type created from \p args
356 Returns \p true if inserting successful, \p false otherwise.
358 The function applies RCU lock internally.
360 template <typename... Args>
361 bool emplace( Args&&... args )
363 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
369 /// Deletes \p key from the set
370 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
372 Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
373 template parameter \p Q defines the key type searching in the list.
374 The set item comparator should be able to compare the type \p value_type
377 RCU \p synchronize method can be called. RCU should not be locked.
379 Return \p true if key is found and deleted, \p false otherwise
381 template <typename Q>
382 bool erase( Q const& key )
384 const bool bRet = bucket( key ).erase( key );
390 /// Deletes the item from the set using \p pred predicate for searching
392 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
393 but \p pred is used for key comparing.
394 \p Less functor has the interface like \p std::less.
395 \p Less must imply the same element order as the comparator used for building the set.
397 template <typename Q, typename Less>
398 bool erase_with( Q const& key, Less pred )
400 const bool bRet = bucket( key ).erase_with( key, pred );
406 /// Deletes \p key from the set
407 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
409 The function searches an item with key \p key, calls \p f functor
410 and deletes the item. If \p key is not found, the functor is not called.
412 The functor \p Func interface:
415 void operator()(value_type const& val);
419 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
420 template parameter \p Q defines the key type searching in the list.
421 The list item comparator should be able to compare the type \p T of list item
424 RCU \p synchronize method can be called. RCU should not be locked.
426 Return \p true if key is found and deleted, \p false otherwise
428 template <typename Q, typename Func>
429 bool erase( Q const& key, Func f )
431 const bool bRet = bucket( key ).erase( key, f );
437 /// Deletes the item from the set using \p pred predicate for searching
439 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
440 but \p pred is used for key comparing.
441 \p Less functor has the interface like \p std::less.
442 \p Less must imply the same element order as the comparator used for building the set.
444 template <typename Q, typename Less, typename Func>
445 bool erase_with( Q const& key, Less pred, Func f )
447 const bool bRet = bucket( key ).erase_with( key, pred, f );
453 /// Extracts an item from the set
454 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
455 The function searches an item with key equal to \p key in the set,
456 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
457 If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr.
459 @note The function does NOT call RCU read-side lock or synchronization,
460 and does NOT dispose the item found. It just excludes the item from the set
461 and returns a pointer to item found.
462 You should lock RCU before calling of the function, and you should synchronize RCU
463 outside the RCU lock to free extracted item
466 #include <cds/urcu/general_buffered.h>
467 #include <cds/container/michael_list_rcu.h>
468 #include <cds/container/michael_set_rcu.h>
470 typedef cds::urcu::gc< general_buffered<> > rcu;
471 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
472 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
474 rcu_michael_set theSet;
477 rcu_michael_set::exempt_ptr p;
479 // first, we should lock RCU
480 rcu_michael_set::rcu_lock lock;
482 // Now, you can apply extract function
483 // Note that you must not delete the item found inside the RCU lock
484 p = theSet.extract( 10 );
486 // do something with p
491 // We may safely release p here
492 // release() passes the pointer to RCU reclamation cycle
496 template <typename Q>
497 exempt_ptr extract( Q const& key )
499 exempt_ptr p = bucket( key ).extract( key );
505 /// Extracts an item from the set using \p pred predicate for searching
507 The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
508 \p Less functor has the interface like \p std::less.
509 \p pred must imply the same element order as the comparator used for building the set.
511 template <typename Q, typename Less>
512 exempt_ptr extract_with( Q const& key, Less pred )
514 exempt_ptr p = bucket( key ).extract_with( key, pred );
520 /// Finds the key \p key
521 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
523 The function searches the item with key equal to \p key and calls the functor \p f for item found.
524 The interface of \p Func functor is:
527 void operator()( value_type& item, Q& key );
530 where \p item is the item found, \p key is the <tt>find</tt> function argument.
532 The functor may change non-key fields of \p item. Note that the functor is only guarantee
533 that \p item cannot be disposed during functor is executing.
534 The functor does not serialize simultaneous access to the set's \p item. If such access is
535 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
537 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
538 can modify both arguments.
540 Note the hash functor specified for class \p Traits template parameter
541 should accept a parameter of type \p Q that may be not the same as \p value_type.
543 The function applies RCU lock internally.
545 The function returns \p true if \p key is found, \p false otherwise.
547 template <typename Q, typename Func>
548 bool find( Q& key, Func f ) const
550 return bucket( key ).find( key, f );
553 template <typename Q, typename Func>
554 bool find( Q const& key, Func f ) const
556 return bucket( key ).find( key, f );
560 /// Finds the key \p key using \p pred predicate for searching
562 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
563 but \p pred is used for key comparing.
564 \p Less functor has the interface like \p std::less.
565 \p Less must imply the same element order as the comparator used for building the set.
567 template <typename Q, typename Less, typename Func>
568 bool find_with( Q& key, Less pred, Func f ) const
570 return bucket( key ).find_with( key, pred, f );
573 template <typename Q, typename Less, typename Func>
574 bool find_with( Q const& key, Less pred, Func f ) const
576 return bucket( key ).find_with( key, pred, f );
580 /// Finds the key \p key
581 /** \anchor cds_nonintrusive_MichealSet_rcu_find_val
583 The function searches the item with key equal to \p key
584 and returns \p true if it is found, and \p false otherwise.
586 Note the hash functor specified for class \p Traits template parameter
587 should accept a parameter of type \p Q that may be not the same as \p value_type.
589 template <typename Q>
590 bool find( Q const & key ) const
592 return bucket( key ).find( key );
595 /// Finds the key \p key using \p pred predicate for searching
597 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_val "find(Q const&)"
598 but \p pred is used for key comparing.
599 \p Less functor has the interface like \p std::less.
600 \p Less must imply the same element order as the comparator used for building the set.
602 template <typename Q, typename Less>
603 bool find_with( Q const & key, Less pred ) const
605 return bucket( key ).find_with( key, pred );
608 /// Finds the key \p key and return the item found
609 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
610 The function searches the item with key equal to \p key and returns the pointer to item found.
611 If \p key is not found it returns \p nullptr.
613 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
615 RCU should be locked before call of this function.
616 Returned item is valid only while RCU is locked:
618 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
623 hash_set::rcu_lock lock;
625 foo * pVal = theSet.get( 5 );
630 // Unlock RCU by rcu_lock destructor
631 // pVal can be freed at any time after RCU has been unlocked
635 template <typename Q>
636 value_type * get( Q const& key ) const
638 return bucket( key ).get( key );
641 /// Finds the key \p key and return the item found
643 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
644 but \p pred is used for comparing the keys.
646 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
648 \p pred must imply the same element order as the comparator used for building the set.
650 template <typename Q, typename Less>
651 value_type * get_with( Q const& key, Less pred ) const
653 return bucket( key ).get_with( key, pred );
656 /// Clears the set (not atomic)
659 for ( size_t i = 0; i < bucket_count(); ++i )
660 m_Buckets[i].clear();
661 m_ItemCounter.reset();
664 /// Checks if the set is empty
666 Emptiness is checked by item counting: if item count is zero then the set is empty.
667 Thus, the correct item counting feature is an important part of Michael's set implementation.
674 /// Returns item count in the set
677 return m_ItemCounter;
680 /// Returns the size of hash table
682 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
683 the value returned is an constant depending on object initialization parameters;
684 see MichaelHashSet::MichaelHashSet for explanation.
686 size_t bucket_count() const
688 return m_nHashBitmask + 1;
692 }} // namespace cds::container
694 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H