3 #ifndef __CDS_INTRUSIVE_MICHAEL_SET_RCU_H
4 #define __CDS_INTRUSIVE_MICHAEL_SET_RCU_H
6 #include <cds/intrusive/michael_set_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace intrusive {
11 /// Michael's hash set, \ref cds_urcu_desc "RCU" specialization
12 /** @ingroup cds_intrusive_map
13 \anchor cds_intrusive_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 bucket for hash set, for example, MichaelList, LazyList.
26 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
27 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
29 - \p Traits - type traits. See michael_set::type_traits for explanation.
30 Instead of defining \p Traits struct you can use option-based syntax with michael_set::make_traits metafunction.
33 Before including <tt><cds/intrusive/michael_set_rcu.h></tt> you should include appropriate RCU header file,
34 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
35 For example, for \ref cds_urcu_general_buffered_gc "general-purpose buffered RCU" you should include:
37 #include <cds/urcu/general_buffered.h>
38 #include <cds/intrusive/michael_list_rcu.h>
39 #include <cds/intrusive/michael_set_rcu.h>
42 // Hash functor for struct Foo
44 size_t operator()( Foo const& foo ) const { return ... }
47 // Now, you can declare Michael's list for type Foo and default traits:
48 typedef cds::intrusive::MichaelList<cds::urcu::gc< general_buffered<> >, Foo > rcu_michael_list;
50 // Declare Michael's set with MichaelList as bucket type
51 typedef cds::intrusive::MichaelSet<
52 cds::urcu::gc< general_buffered<> >,
54 cds::intrusive::michael_set::make_traits<
55 cds::opt::::hash< foo_hash >
59 // Declares hash set for 1000000 items with load factor 2
60 rcu_michael_set theSet( 1000000, 2 );
62 // Now you can use theSet object in many threads without any synchronization.
68 #ifdef CDS_DOXYGEN_INVOKED
69 class Traits = michael_set::type_traits
74 class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
77 typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
78 typedef Traits options ; ///< Traits template parameters
80 typedef typename bucket_type::value_type value_type ; ///< type of value stored in the list
81 typedef cds::urcu::gc< RCU > gc ; ///< RCU schema
82 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
83 typedef typename bucket_type::disposer disposer ; ///< Node disposer functor
85 /// Hash functor for \ref value_type and all its derivatives that you use
86 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
87 typedef typename options::item_counter item_counter ; ///< Item counter type
89 /// Bucket table allocator
90 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
92 typedef typename bucket_type::rcu_lock rcu_lock ; ///< RCU scoped lock
93 typedef typename bucket_type::exempt_ptr exempt_ptr ; ///< pointer to extracted node
94 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
95 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
98 item_counter m_ItemCounter ; ///< Item counter
99 hash m_HashFunctor ; ///< Hash functor
101 bucket_type * m_Buckets ; ///< bucket table
105 const size_t m_nHashBitmask;
110 /// Calculates hash value of \p key
111 template <typename Q>
112 size_t hash_value( Q const& key ) const
114 return m_HashFunctor( key ) & m_nHashBitmask;
117 /// Returns the bucket (ordered list) for \p key
118 template <typename Q>
119 bucket_type& bucket( Q const& key )
121 return m_Buckets[ hash_value( key ) ];
123 template <typename Q>
124 bucket_type const& bucket( Q const& key ) const
126 return m_Buckets[ hash_value( key ) ];
133 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
134 - it has no post-increment operator
135 - it iterates items in unordered fashion
137 typedef michael_set::details::iterator< bucket_type, false > iterator;
139 /// Const forward iterator
141 For iterator's features and requirements see \ref iterator
143 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
145 /// Returns a forward iterator addressing the first element in a set
147 For empty set \code begin() == end() \endcode
151 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
154 /// Returns an iterator that addresses the location succeeding the last element in a set
156 Do not use the value returned by <tt>end</tt> function to access any item.
157 The returned value can be used only to control reaching the end of the set.
158 For empty set \code begin() == end() \endcode
162 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
165 /// Returns a forward const iterator addressing the first element in a set
167 const_iterator begin() const
169 return get_const_begin();
171 const_iterator cbegin()
173 return get_const_begin();
177 /// Returns an const iterator that addresses the location succeeding the last element in a set
179 const_iterator end() const
181 return get_const_end();
183 const_iterator cend()
185 return get_const_end();
191 const_iterator get_const_begin() const
193 return const_iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
195 const_iterator get_const_end() const
197 return const_iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
202 /// Initialize hash set
204 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
205 At construction time you should pass estimated maximum item count and a load factor.
206 The load factor is average size of one bucket - a small number between 1 and 10.
207 The bucket is an ordered single-linked list, the complexity of searching in the bucket is linear <tt>O(nLoadFactor)</tt>.
208 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
211 size_t nMaxItemCount, ///< estimation of max item count in the hash set
212 size_t nLoadFactor ///< load factor: average size of the bucket
213 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
215 // GC and OrderedList::gc must be the same
216 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
218 // atomicity::empty_item_counter is not allowed as a item counter
219 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
221 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
224 /// Clear hash set and destroy it
228 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
233 The function inserts \p val in the set if it does not contain
234 an item with key equal to \p val.
236 Returns \p true if \p val is placed into the set, \p false otherwise.
238 bool insert( value_type& val )
240 bool bRet = bucket( val ).insert( val );
248 This function is intended for derived non-intrusive containers.
250 The function allows to split creating of new item into two part:
251 - create item with key only
252 - insert new item into the set
253 - if inserting is success, calls \p f functor to initialize value-field of \p val.
255 The functor signature is:
257 void func( value_type& val );
259 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
260 \p val no any other changes could be made on this set's item by concurrent threads.
261 The user-defined functor is called only if the inserting is success and can be passed by reference
262 using <tt>boost::ref</tt>
264 template <typename Func>
265 bool insert( value_type& val, Func f )
267 bool bRet = bucket( val ).insert( val, f );
273 /// Ensures that the \p item exists in the set
275 The operation performs inserting or changing data with lock-free manner.
277 If the item \p val not found in the set, then \p val is inserted into the set.
278 Otherwise, the functor \p func is called with item found.
279 The functor signature is:
281 void func( bool bNew, value_type& item, value_type& val );
284 - \p bNew - \p true if the item has been inserted, \p false otherwise
285 - \p item - item of the set
286 - \p val - argument \p val passed into the \p ensure function
287 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
288 refers to the same thing.
290 The functor can change non-key fields of the \p item; however, \p func must guarantee
291 that during changing no any other modifications could be made on this item by concurrent threads.
293 You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
295 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
296 \p second is \p true if new item has been added or \p false if the item with \p key
297 already is in the set.
299 template <typename Func>
300 std::pair<bool, bool> ensure( value_type& val, Func func )
302 std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
303 if ( bRet.first && bRet.second )
308 /// Unlinks the item \p val from the set
310 The function searches the item \p val in the set and unlink it from the set
311 if it is found and is equal to \p val.
313 The function returns \p true if success and \p false otherwise.
315 bool unlink( value_type& val )
317 bool bRet = bucket( val ).unlink( val );
323 /// Deletes the item from the set
324 /** \anchor cds_intrusive_MichaelHashSet_rcu_erase
325 The function searches an item with key equal to \p val in the set,
326 unlinks it from the set, and returns \p true.
327 If the item with key equal to \p val is not found the function return \p false.
329 Note the hash functor should accept a parameter of type \p Q that may be not the same as \p value_type.
331 template <typename Q>
332 bool erase( Q const& val )
334 if ( bucket( val ).erase( val )) {
341 /// Deletes the item from the set using \p pred predicate for searching
343 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_erase "erase(Q const&)"
344 but \p pred is used for key comparing.
345 \p Less functor has the interface like \p std::less.
346 \p pred must imply the same element order as the comparator used for building the set.
348 template <typename Q, typename Less>
349 bool erase_with( Q const& val, Less pred )
351 if ( bucket( val ).erase_with( val, pred )) {
358 /// Deletes the item from the set
359 /** \anchor cds_intrusive_MichaelHashSet_rcu_erase_func
360 The function searches an item with key equal to \p val in the set,
361 call \p f functor with item found, and unlinks it from the set.
362 The \ref disposer specified in \p OrderedList class template parameter is called
363 by garbage collector \p GC asynchronously.
365 The \p Func interface is
368 void operator()( value_type const& item );
371 The functor may be passed by reference with <tt>boost:ref</tt>
373 If the item with key equal to \p val is not found the function return \p false.
375 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
377 template <typename Q, typename Func>
378 bool erase( const Q& val, Func f )
380 if ( bucket( val ).erase( val, f )) {
387 /// Deletes the item from the set using \p pred predicate for searching
389 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_erase_func "erase(Q const&)"
390 but \p pred is used for key comparing.
391 \p Less functor has the interface like \p std::less.
392 \p pred must imply the same element order as the comparator used for building the set.
394 template <typename Q, typename Less, typename Func>
395 bool erase_with( const Q& val, Less pred, Func f )
397 if ( bucket( val ).erase_with( val, pred, f )) {
404 /// Extracts an item from the set
405 /** \anchor cds_intrusive_MichaelHashSet_rcu_extract
406 The function searches an item with key equal to \p val in the set,
407 unlinks it from the set, places item pointer into \p dest argument, and returns \p true.
408 If the item with the key equal to \p val is not found the function return \p false.
410 @note The function does NOT call RCU read-side lock or synchronization,
411 and does NOT dispose the item found. It just excludes the item from the set
412 and returns a pointer to item found.
413 You should lock RCU before calling of the function, and you should synchronize RCU
414 outside the RCU lock before reusing returned pointer.
417 #include <cds/urcu/general_buffered.h>
418 #include <cds/intrusive/michael_list_rcu.h>
419 #include <cds/intrusive/michael_set_rcu.h>
421 typedef cds::urcu::gc< general_buffered<> > rcu;
422 typedef cds::intrusive::MichaelList< rcu, Foo > rcu_michael_list;
423 typedef cds::intrusive::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
425 rcu_michael_set theSet;
428 rcu_michael_set::exempt_ptr p;
430 // first, we should lock RCU
431 rcu_michael_set::rcu_lock lock;
433 // Now, you can apply extract function
434 // Note that you must not delete the item found inside the RCU lock
435 if ( theSet.extract( p, 10 )) {
436 // do something with p
441 // We may safely release p here
442 // release() passes the pointer to RCU reclamation cycle:
443 // it invokes RCU retire_ptr function with the disposer you provided for rcu_michael_list.
447 template <typename Q>
448 bool extract( exempt_ptr& dest, Q const& val )
450 if ( bucket( val ).extract( dest, val )) {
457 /// Extracts an item from the set using \p pred predicate for searching
459 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_extract "extract(exempt_ptr&, Q const&)"
460 but \p pred is used for key comparing.
461 \p Less functor has the interface like \p std::less.
462 \p pred must imply the same element order as the comparator used for building the set.
464 template <typename Q, typename Less>
465 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
467 if ( bucket( val ).extract_with( dest, val, pred )) {
474 /// Finds the key \p val
475 /** \anchor cds_intrusive_MichaelHashSet_rcu_find_val
476 The function searches the item with key equal to \p val
477 and returns \p true if \p val found or \p false otherwise.
479 template <typename Q>
480 bool find( Q const& val ) const
482 return bucket( val ).find( val );
485 /// Finds the key \p val using \p pred predicate for searching
487 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_find_val "find(Q const&)"
488 but \p pred is used for key comparing.
489 \p Less functor has the interface like \p std::less.
490 \p pred must imply the same element order as the comparator used for building the set.
492 template <typename Q, typename Less>
493 bool find_with( Q const& val, Less pred ) const
495 return bucket( val ).find_with( val, pred );
498 /// Find the key \p val
499 /** \anchor cds_intrusive_MichaelHashSet_rcu_find_func
500 The function searches the item with key equal to \p val and calls the functor \p f for item found.
501 The interface of \p Func functor is:
504 void operator()( value_type& item, Q& val );
507 where \p item is the item found, \p val is the <tt>find</tt> function argument.
509 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
511 The functor can change non-key fields of \p item.
512 The functor does not serialize simultaneous access to the set \p item. If such access is
513 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
515 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
516 can modify both arguments.
518 Note the hash functor specified for class \p Traits template parameter
519 should accept a parameter of type \p Q that can be not the same as \p value_type.
521 The function returns \p true if \p val is found, \p false otherwise.
523 template <typename Q, typename Func>
524 bool find( Q& val, Func f ) const
526 return bucket( val ).find( val, f );
529 /// Finds the key \p val using \p pred predicate for searching
531 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_find_func "find(Q&, Func)"
532 but \p pred is used for key comparing.
533 \p Less functor has the interface like \p std::less.
534 \p pred must imply the same element order as the comparator used for building the set.
536 template <typename Q, typename Less, typename Func>
537 bool find_with( Q& val, Less pred, Func f ) const
539 return bucket( val ).find_with( val, pred, f );
542 /// Find the key \p val
543 /** \anchor cds_intrusive_MichaelHashSet_rcu_find_cfunc
544 The function searches the item with key equal to \p val and calls the functor \p f for item found.
545 The interface of \p Func functor is:
548 void operator()( value_type& item, Q const& val );
551 where \p item is the item found, \p val is the <tt>find</tt> function argument.
553 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
555 The functor can change non-key fields of \p item.
556 The functor does not serialize simultaneous access to the set \p item. If such access is
557 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
559 Note the hash functor specified for class \p Traits template parameter
560 should accept a parameter of type \p Q that can be not the same as \p value_type.
562 The function returns \p true if \p val is found, \p false otherwise.
564 template <typename Q, typename Func>
565 bool find( Q const& val, Func f ) const
567 return bucket( val ).find( val, f );
570 /// Finds the key \p val using \p pred predicate for searching
572 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_find_cfunc "find(Q const&, Func)"
573 but \p pred is used for key comparing.
574 \p Less functor has the interface like \p std::less.
575 \p pred must imply the same element order as the comparator used for building the set.
577 template <typename Q, typename Less, typename Func>
578 bool find_with( Q const& val, Less pred, Func f ) const
580 return bucket( val ).find_with( val, pred, f );
583 /// Finds the key \p val and return the item found
584 /** \anchor cds_intrusive_MichaelHashSet_rcu_get
585 The function searches the item with key equal to \p val and returns the pointer to item found.
586 If \p val is not found it returns \p nullptr.
588 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
590 RCU should be locked before call of this function.
591 Returned item is valid only while RCU is locked:
593 typedef cds::intrusive::MichaelHashSet< your_template_parameters > hash_set;
598 hash_set::rcu_lock lock;
600 foo * pVal = theSet.get( 5 );
605 // Unlock RCU by rcu_lock destructor
606 // pVal can be retired by disposer at any time after RCU has been unlocked
610 template <typename Q>
611 value_type * get( Q const& val ) const
613 return bucket( val ).get( val );
616 /// Finds the key \p val and return the item found
618 The function is an analog of \ref cds_intrusive_MichaelHashSet_rcu_get "get(Q const&)"
619 but \p pred is used for comparing the keys.
621 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
623 \p pred must imply the same element order as the comparator used for building the set.
625 template <typename Q, typename Less>
626 value_type * get_with( Q const& val, Less pred ) const
628 return bucket( val ).get_with( val, pred );
631 /// Clears the set (non-atomic)
633 The function unlink all items from the set.
634 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
635 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
636 <tt> empty() </tt> may return \p true but the set may contain item(s).
637 Therefore, \p clear may be used only for debugging purposes.
639 For each item the \p disposer is called after unlinking.
643 for ( size_t i = 0; i < bucket_count(); ++i )
644 m_Buckets[i].clear();
645 m_ItemCounter.reset();
649 /// Checks if the set is empty
651 Emptiness is checked by item counting: if item count is zero then the set is empty.
652 Thus, the correct item counting feature is an important part of Michael's set implementation.
659 /// Returns item count in the set
662 return m_ItemCounter;
665 /// Returns the size of hash table
667 Since %MichaelHashSet cannot dynamically extend the hash table size,
668 the value returned is an constant depending on object initialization parameters;
669 see \ref cds_intrusive_MichaelHashSet_hp "MichaelHashSet" for explanation.
671 size_t bucket_count() const
673 return m_nHashBitmask + 1;
678 }} // namespace cds::intrusive
680 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_SET_NOGC_H