3 #ifndef __CDS_CONTAINER_MICHAEL_SET_RCU_H
4 #define __CDS_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 bucket for hash set, for example, MichaelList.
26 The ordered list implementation specifies the type \p T stored in the hash-set,
27 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.
31 Instead of defining \p Traits struct you may use option-based syntax with michael_set::make_traits metafunction.
32 For michael_set::make_traits the following option may be used:
33 - opt::hash - mandatory option, specifies hash functor.
34 - opt::item_counter - optional, specifies item counting policy. See michael_set::type_traits for explanation.
35 - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
37 \note About hash functor see \ref cds_nonintrusive_MichaelHashSet_hash_functor "MichaelSet".
41 Suppose, we have the following type \p Foo that we want to store in our MichaelHashSet:
44 int nKey ; // key field
45 int nVal ; // value field
49 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
50 that will be used as a bucket for the set. We will cds::urcu::general_buffered<> RCU type and
51 MichaelList as a bucket type.
52 You should include RCU-related header file (<tt>cds/urcu/general_buffered.h</tt> in this example)
53 before including <tt>cds/container/michael_set_rcu.h</tt>.
54 Also, for ordered list we should develop a comparator for our \p Foo struct.
56 #include <cds/urcu/general_buffered.h>
57 #include <cds/container/michael_list_rcu.h>
58 #include <cds/container/michael_set_rcu.h>
60 namespace cc = cds::container;
64 int operator ()(Foo const& v1, Foo const& v2 ) const
66 if ( std::less( v1.nKey, v2.nKey ))
68 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
73 typedef cc::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo,
74 typename cc::michael_list::make_traits<
75 cc::opt::compare< Foo_cmp > // item comparator option
79 // Hash functor for Foo
81 size_t operator ()( int i ) const
83 return std::hash( i );
85 size_t operator()( Foo const& i ) const
87 return std::hash( i.nKey );
92 // Note that \p RCU template parameter of ordered list must be equal \p RCU for the set.
93 typedef cc::MichaelHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, bucket_list,
94 cc::michael_set::make_traits<
95 cc::opt::hash< foo_hash >
106 #ifdef CDS_DOXYGEN_INVOKED
107 class Traits = michael_set::type_traits
112 class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
115 typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
116 typedef Traits options ; ///< Traits template parameters
118 typedef typename bucket_type::value_type value_type ; ///< type of value stored in the list
119 typedef cds::urcu::gc< RCU > gc ; ///< RCU used as garbage collector
120 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparing functor
122 /// Hash functor for \ref value_type and all its derivatives that you use
123 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
124 typedef typename options::item_counter item_counter ; ///< Item counter type
126 /// Bucket table allocator
127 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
129 typedef typename bucket_type::rcu_lock rcu_lock ; ///< RCU scoped lock
130 typedef typename bucket_type::exempt_ptr exempt_ptr ; ///< pointer to extracted node
131 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
132 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
135 item_counter m_ItemCounter ; ///< Item counter
136 hash m_HashFunctor ; ///< Hash functor
138 bucket_type * m_Buckets ; ///< bucket table
142 const size_t m_nHashBitmask;
146 /// Calculates hash value of \p key
147 template <typename Q>
148 size_t hash_value( Q const& key ) const
150 return m_HashFunctor( key ) & m_nHashBitmask;
153 /// Returns the bucket (ordered list) for \p key
155 template <typename Q>
156 bucket_type& bucket( Q const& key )
158 return m_Buckets[ hash_value( key ) ];
160 template <typename Q>
161 bucket_type const& bucket( Q const& key ) const
163 return m_Buckets[ hash_value( key ) ];
169 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
170 - it has no post-increment operator
171 - it iterates items in unordered fashion
172 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
173 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
174 deleting operations it is no guarantee that you iterate all item in the set.
176 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
177 for debug purpose only.
179 typedef michael_set::details::iterator< bucket_type, false > iterator;
181 /// Const forward iterator
182 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
184 /// Returns a forward iterator addressing the first element in a set
186 For empty set \code begin() == end() \endcode
190 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
193 /// Returns an iterator that addresses the location succeeding the last element in a set
195 Do not use the value returned by <tt>end</tt> function to access any item.
196 The returned value can be used only to control reaching the end of the set.
197 For empty set \code begin() == end() \endcode
201 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
204 /// Returns a forward const iterator addressing the first element in a set
206 const_iterator begin() const
208 return get_const_begin();
210 const_iterator cbegin()
212 return get_const_begin();
216 /// Returns an const iterator that addresses the location succeeding the last element in a set
218 const_iterator end() const
220 return get_const_end();
222 const_iterator cend()
224 return get_const_end();
230 const_iterator get_const_begin() const
232 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
234 const_iterator get_const_end() const
236 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
241 /// Initialize hash set
243 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
244 when you create an object.
245 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
246 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
247 Note, that many popular STL hash map implementation uses load factor 1.
249 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
252 size_t nMaxItemCount, ///< estimation of max item count in the hash set
253 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
254 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
256 // GC and OrderedList::gc must be the same
257 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
259 // atomicity::empty_item_counter is not allowed as a item counter
260 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
262 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
265 /// Clear hash set and destroy it
269 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
274 The function creates a node with copy of \p val value
275 and then inserts the node created into the set.
277 The type \p Q should contain as minimum the complete key for the node.
278 The object of \ref value_type should be constructible from a value of type \p Q.
279 In trivial case, \p Q is equal to \ref value_type.
281 The function applies RCU lock internally.
283 Returns \p true if \p val is inserted into the set, \p false otherwise.
285 template <typename Q>
286 bool insert( Q const& val )
288 const bool bRet = bucket( val ).insert( val );
296 The function allows to split creating of new item into two part:
297 - create item with key only
298 - insert new item into the set
299 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
301 The functor signature is:
303 void func( value_type& val );
305 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
306 \p val no any other changes could be made on this set's item by concurrent threads.
307 The user-defined functor is called only if the inserting is success. It may be passed by reference
310 The function applies RCU lock internally.
312 template <typename Q, typename Func>
313 bool insert( Q const& val, Func f )
315 const bool bRet = bucket( val ).insert( val, f );
321 /// Ensures that the item exists in the set
323 The operation performs inserting or changing data with lock-free manner.
325 If the \p val key not found in the set, then the new item created from \p val
326 is inserted into the set. Otherwise, the functor \p func is called with the item found.
327 The functor \p Func should be a function with signature:
329 void func( bool bNew, value_type& item, const Q& val );
334 void operator()( bool bNew, value_type& item, const Q& val );
339 - \p bNew - \p true if the item has been inserted, \p false otherwise
340 - \p item - item of the set
341 - \p val - argument \p key passed into the \p ensure function
343 The functor may change non-key fields of the \p item; however, \p func must guarantee
344 that during changing no any other modifications could be made on this item by concurrent threads.
346 You may pass \p func argument by reference using \p std::ref
348 The function applies RCU lock internally.
350 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
351 \p second is true if new item has been added or \p false if the item with \p key
352 already is in the set.
354 template <typename Q, typename Func>
355 std::pair<bool, bool> ensure( const Q& val, Func func )
357 std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
358 if ( bRet.first && bRet.second )
363 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
365 Returns \p true if inserting successful, \p false otherwise.
367 The function applies RCU lock internally.
369 template <typename... Args>
370 bool emplace( Args&&... args )
372 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
378 /// Deletes \p key from the set
379 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
381 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
382 template parameter \p Q defines the key type searching in the list.
383 The set item comparator should be able to compare the type \p value_type
386 RCU \p synchronize method can be called. RCU should not be locked.
388 Return \p true if key is found and deleted, \p false otherwise
390 template <typename Q>
391 bool erase( Q const& key )
393 const bool bRet = bucket( key ).erase( key );
399 /// Deletes the item from the set using \p pred predicate for searching
401 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
402 but \p pred is used for key comparing.
403 \p Less functor has the interface like \p std::less.
404 \p Less must imply the same element order as the comparator used for building the set.
406 template <typename Q, typename Less>
407 bool erase_with( Q const& key, Less pred )
409 const bool bRet = bucket( key ).erase_with( key, pred );
415 /// Deletes \p key from the set
416 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
418 The function searches an item with key \p key, calls \p f functor
419 and deletes the item. If \p key is not found, the functor is not called.
421 The functor \p Func interface:
424 void operator()(value_type const& val);
427 The functor may be passed by reference using <tt>boost:ref</tt>
429 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
430 template parameter \p Q defines the key type searching in the list.
431 The list item comparator should be able to compare the type \p T of list item
434 RCU \p synchronize method can be called. RCU should not be locked.
436 Return \p true if key is found and deleted, \p false otherwise
438 template <typename Q, typename Func>
439 bool erase( Q const& key, Func f )
441 const bool bRet = bucket( key ).erase( key, f );
447 /// Deletes the item from the set using \p pred predicate for searching
449 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
450 but \p pred is used for key comparing.
451 \p Less functor has the interface like \p std::less.
452 \p Less must imply the same element order as the comparator used for building the set.
454 template <typename Q, typename Less, typename Func>
455 bool erase_with( Q const& key, Less pred, Func f )
457 const bool bRet = bucket( key ).erase_with( key, pred, f );
463 /// Extracts an item from the set
464 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
465 The function searches an item with key equal to \p val in the set,
466 unlinks it from the set, places item pointer into \p dest argument, and returns \p true.
467 If the item with the key equal to \p val is not found the function return \p false.
469 @note The function does NOT call RCU read-side lock or synchronization,
470 and does NOT dispose the item found. It just excludes the item from the set
471 and returns a pointer to item found.
472 You should lock RCU before calling of the function, and you should synchronize RCU
473 outside the RCU lock to free extracted item
476 #include <cds/urcu/general_buffered.h>
477 #include <cds/container/michael_list_rcu.h>
478 #include <cds/container/michael_set_rcu.h>
480 typedef cds::urcu::gc< general_buffered<> > rcu;
481 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
482 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
484 rcu_michael_set theSet;
487 rcu_michael_set::exempt_ptr p;
489 // first, we should lock RCU
490 rcu_michael_set::rcu_lock lock;
492 // Now, you can apply extract function
493 // Note that you must not delete the item found inside the RCU lock
494 if ( theSet.extract( p, 10 )) {
495 // do something with p
500 // We may safely release p here
501 // release() passes the pointer to RCU reclamation cycle
505 template <typename Q>
506 bool extract( exempt_ptr& dest, Q const& val )
508 if ( bucket( val ).extract( dest, val )) {
515 /// Extracts an item from the set using \p pred predicate for searching
517 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_extract "extract(exempt_ptr&, Q const&)"
518 but \p pred is used for key comparing.
519 \p Less functor has the interface like \p std::less.
520 \p pred must imply the same element order as the comparator used for building the set.
522 template <typename Q, typename Less>
523 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
525 if ( bucket( val ).extract_with( dest, val, pred )) {
532 /// Finds the key \p val
533 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
535 The function searches the item with key equal to \p val and calls the functor \p f for item found.
536 The interface of \p Func functor is:
539 void operator()( value_type& item, Q& val );
542 where \p item is the item found, \p val is the <tt>find</tt> function argument.
544 You may pass \p f argument by reference using \p std::ref.
546 The functor may change non-key fields of \p item. Note that the functor is only guarantee
547 that \p item cannot be disposed during functor is executing.
548 The functor does not serialize simultaneous access to the set's \p item. If such access is
549 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
551 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
552 can modify both arguments.
554 Note the hash functor specified for class \p Traits template parameter
555 should accept a parameter of type \p Q that may be not the same as \p value_type.
557 The function applies RCU lock internally.
559 The function returns \p true if \p val is found, \p false otherwise.
561 template <typename Q, typename Func>
562 bool find( Q& val, Func f ) const
564 return bucket( val ).find( val, f );
567 /// Finds the key \p val using \p pred predicate for searching
569 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
570 but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p Less must imply the same element order as the comparator used for building the set.
574 template <typename Q, typename Less, typename Func>
575 bool find_with( Q& val, Less pred, Func f ) const
577 return bucket( val ).find_with( val, pred, f );
580 /// Finds the key \p val
581 /** \anchor cds_nonintrusive_MichealSet_rcu_find_cfunc
583 The function searches the item with key equal to \p val and calls the functor \p f for item found.
584 The interface of \p Func functor is:
587 void operator()( value_type& item, Q const& val );
590 where \p item is the item found, \p val is the <tt>find</tt> function argument.
592 You may pass \p f argument by reference using \p std::ref.
594 The functor may change non-key fields of \p item. Note that the functor is only guarantee
595 that \p item cannot be disposed during functor is executing.
596 The functor does not serialize simultaneous access to the set's \p item. If such access is
597 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
599 Note the hash functor specified for class \p Traits template parameter
600 should accept a parameter of type \p Q that may be not the same as \p value_type.
602 The function applies RCU lock internally.
604 The function returns \p true if \p val is found, \p false otherwise.
606 template <typename Q, typename Func>
607 bool find( Q const& val, Func f ) const
609 return bucket( val ).find( val, f );
612 /// Finds the key \p val using \p pred predicate for searching
614 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_cfunc "find(Q const&, Func)"
615 but \p pred is used for key comparing.
616 \p Less functor has the interface like \p std::less.
617 \p Less must imply the same element order as the comparator used for building the set.
619 template <typename Q, typename Less, typename Func>
620 bool find_with( Q const& val, Less pred, Func f ) const
622 return bucket( val ).find_with( val, pred, f );
625 /// Finds the key \p val
626 /** \anchor cds_nonintrusive_MichealSet_rcu_find_val
628 The function searches the item with key equal to \p val
629 and returns \p true if it is found, and \p false otherwise.
631 Note the hash functor specified for class \p Traits template parameter
632 should accept a parameter of type \p Q that may be not the same as \ref value_type.
634 template <typename Q>
635 bool find( Q const & val ) const
637 return bucket( val ).find( val );
640 /// Finds the key \p val using \p pred predicate for searching
642 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_val "find(Q const&)"
643 but \p pred is used for key comparing.
644 \p Less functor has the interface like \p std::less.
645 \p Less must imply the same element order as the comparator used for building the set.
647 template <typename Q, typename Less>
648 bool find_with( Q const & val, Less pred ) const
650 return bucket( val ).find_with( val, pred );
653 /// Finds the key \p val and return the item found
654 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
655 The function searches the item with key equal to \p val and returns the pointer to item found.
656 If \p val is not found it returns \p nullptr.
658 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
660 RCU should be locked before call of this function.
661 Returned item is valid only while RCU is locked:
663 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
668 hash_set::rcu_lock lock;
670 foo * pVal = theSet.get( 5 );
675 // Unlock RCU by rcu_lock destructor
676 // pVal can be freed at any time after RCU has been unlocked
680 template <typename Q>
681 value_type * get( Q const& val ) const
683 return bucket( val ).get( val );
686 /// Finds the key \p val and return the item found
688 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
689 but \p pred is used for comparing the keys.
691 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
693 \p pred must imply the same element order as the comparator used for building the set.
695 template <typename Q, typename Less>
696 value_type * get_with( Q const& val, Less pred ) const
698 return bucket( val ).get_with( val, pred );
701 /// Clears the set (non-atomic)
703 The function erases all items from the set.
705 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
706 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
707 <tt> empty() </tt> may return \p true but the set may contain item(s).
708 Therefore, \p clear may be used only for debugging purposes.
710 RCU \p synchronize method can be called. RCU should not be locked.
714 for ( size_t i = 0; i < bucket_count(); ++i )
715 m_Buckets[i].clear();
716 m_ItemCounter.reset();
719 /// Checks if the set is empty
721 Emptiness is checked by item counting: if item count is zero then the set is empty.
722 Thus, the correct item counting feature is an important part of Michael's set implementation.
729 /// Returns item count in the set
732 return m_ItemCounter;
735 /// Returns the size of hash table
737 Since MichaelHashSet cannot dynamically extend the hash table size,
738 the value returned is an constant depending on object initialization parameters;
739 see MichaelHashSet::MichaelHashSet for explanation.
741 size_t bucket_count() const
743 return m_nHashBitmask + 1;
747 }} // namespace cds::container
749 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_H