3 #ifndef __CDS_CONTAINER_MICHAEL_SET_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_SET_RCU_H
6 #include <cds/container/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
308 using <tt>boost::ref</tt>
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 <tt>boost::ref</tt>.
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 # ifdef CDS_EMPLACE_SUPPORT
364 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
366 Returns \p true if inserting successful, \p false otherwise.
368 The function applies RCU lock internally.
370 @note This function is available only for compiler that supports
371 variadic template and move semantics
373 template <typename... Args>
374 bool emplace( Args&&... args )
376 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
383 /// Deletes \p key from the set
384 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
386 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
387 template parameter \p Q defines the key type searching in the list.
388 The set item comparator should be able to compare the type \p value_type
391 RCU \p synchronize method can be called. RCU should not be locked.
393 Return \p true if key is found and deleted, \p false otherwise
395 template <typename Q>
396 bool erase( Q const& key )
398 const bool bRet = bucket( key ).erase( key );
404 /// Deletes the item from the set using \p pred predicate for searching
406 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
407 but \p pred is used for key comparing.
408 \p Less functor has the interface like \p std::less.
409 \p Less must imply the same element order as the comparator used for building the set.
411 template <typename Q, typename Less>
412 bool erase_with( Q const& key, Less pred )
414 const bool bRet = bucket( key ).erase_with( key, pred );
420 /// Deletes \p key from the set
421 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
423 The function searches an item with key \p key, calls \p f functor
424 and deletes the item. If \p key is not found, the functor is not called.
426 The functor \p Func interface:
429 void operator()(value_type const& val);
432 The functor may be passed by reference using <tt>boost:ref</tt>
434 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
435 template parameter \p Q defines the key type searching in the list.
436 The list item comparator should be able to compare the type \p T of list item
439 RCU \p synchronize method can be called. RCU should not be locked.
441 Return \p true if key is found and deleted, \p false otherwise
443 template <typename Q, typename Func>
444 bool erase( Q const& key, Func f )
446 const bool bRet = bucket( key ).erase( key, f );
452 /// Deletes the item from the set using \p pred predicate for searching
454 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
455 but \p pred is used for key comparing.
456 \p Less functor has the interface like \p std::less.
457 \p Less must imply the same element order as the comparator used for building the set.
459 template <typename Q, typename Less, typename Func>
460 bool erase_with( Q const& key, Less pred, Func f )
462 const bool bRet = bucket( key ).erase_with( key, pred, f );
468 /// Extracts an item from the set
469 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
470 The function searches an item with key equal to \p val in the set,
471 unlinks it from the set, places item pointer into \p dest argument, and returns \p true.
472 If the item with the key equal to \p val is not found the function return \p false.
474 @note The function does NOT call RCU read-side lock or synchronization,
475 and does NOT dispose the item found. It just excludes the item from the set
476 and returns a pointer to item found.
477 You should lock RCU before calling of the function, and you should synchronize RCU
478 outside the RCU lock to free extracted item
481 #include <cds/urcu/general_buffered.h>
482 #include <cds/container/michael_list_rcu.h>
483 #include <cds/container/michael_set_rcu.h>
485 typedef cds::urcu::gc< general_buffered<> > rcu;
486 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
487 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
489 rcu_michael_set theSet;
492 rcu_michael_set::exempt_ptr p;
494 // first, we should lock RCU
495 rcu_michael_set::rcu_lock lock;
497 // Now, you can apply extract function
498 // Note that you must not delete the item found inside the RCU lock
499 if ( theSet.extract( p, 10 )) {
500 // do something with p
505 // We may safely release p here
506 // release() passes the pointer to RCU reclamation cycle
510 template <typename Q>
511 bool extract( exempt_ptr& dest, Q const& val )
513 if ( bucket( val ).extract( dest, val )) {
520 /// Extracts an item from the set using \p pred predicate for searching
522 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_extract "extract(exempt_ptr&, Q const&)"
523 but \p pred is used for key comparing.
524 \p Less functor has the interface like \p std::less.
525 \p pred must imply the same element order as the comparator used for building the set.
527 template <typename Q, typename Less>
528 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
530 if ( bucket( val ).extract_with( dest, val, pred )) {
537 /// Finds the key \p val
538 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
540 The function searches the item with key equal to \p val and calls the functor \p f for item found.
541 The interface of \p Func functor is:
544 void operator()( value_type& item, Q& val );
547 where \p item is the item found, \p val is the <tt>find</tt> function argument.
549 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
551 The functor may change non-key fields of \p item. Note that the functor is only guarantee
552 that \p item cannot be disposed during functor is executing.
553 The functor does not serialize simultaneous access to the set's \p item. If such access is
554 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
556 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
557 can modify both arguments.
559 Note the hash functor specified for class \p Traits template parameter
560 should accept a parameter of type \p Q that may be not the same as \p value_type.
562 The function applies RCU lock internally.
564 The function returns \p true if \p val is found, \p false otherwise.
566 template <typename Q, typename Func>
567 bool find( Q& val, Func f ) const
569 return bucket( val ).find( val, f );
572 /// Finds the key \p val using \p pred predicate for searching
574 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
575 but \p pred is used for key comparing.
576 \p Less functor has the interface like \p std::less.
577 \p Less must imply the same element order as the comparator used for building the set.
579 template <typename Q, typename Less, typename Func>
580 bool find_with( Q& val, Less pred, Func f ) const
582 return bucket( val ).find_with( val, pred, f );
585 /// Finds the key \p val
586 /** \anchor cds_nonintrusive_MichealSet_rcu_find_cfunc
588 The function searches the item with key equal to \p val and calls the functor \p f for item found.
589 The interface of \p Func functor is:
592 void operator()( value_type& item, Q const& val );
595 where \p item is the item found, \p val is the <tt>find</tt> function argument.
597 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
599 The functor may change non-key fields of \p item. Note that the functor is only guarantee
600 that \p item cannot be disposed during functor is executing.
601 The functor does not serialize simultaneous access to the set's \p item. If such access is
602 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
604 Note the hash functor specified for class \p Traits template parameter
605 should accept a parameter of type \p Q that may be not the same as \p value_type.
607 The function applies RCU lock internally.
609 The function returns \p true if \p val is found, \p false otherwise.
611 template <typename Q, typename Func>
612 bool find( Q const& val, Func f ) const
614 return bucket( val ).find( val, f );
617 /// Finds the key \p val using \p pred predicate for searching
619 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_cfunc "find(Q const&, Func)"
620 but \p pred is used for key comparing.
621 \p Less functor has the interface like \p std::less.
622 \p Less must imply the same element order as the comparator used for building the set.
624 template <typename Q, typename Less, typename Func>
625 bool find_with( Q const& val, Less pred, Func f ) const
627 return bucket( val ).find_with( val, pred, f );
630 /// Finds the key \p val
631 /** \anchor cds_nonintrusive_MichealSet_rcu_find_val
633 The function searches the item with key equal to \p val
634 and returns \p true if it is found, and \p false otherwise.
636 Note the hash functor specified for class \p Traits template parameter
637 should accept a parameter of type \p Q that may be not the same as \ref value_type.
639 template <typename Q>
640 bool find( Q const & val ) const
642 return bucket( val ).find( val );
645 /// Finds the key \p val using \p pred predicate for searching
647 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_val "find(Q const&)"
648 but \p pred is used for key comparing.
649 \p Less functor has the interface like \p std::less.
650 \p Less must imply the same element order as the comparator used for building the set.
652 template <typename Q, typename Less>
653 bool find_with( Q const & val, Less pred ) const
655 return bucket( val ).find_with( val, pred );
658 /// Finds the key \p val and return the item found
659 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
660 The function searches the item with key equal to \p val and returns the pointer to item found.
661 If \p val is not found it returns \p NULL.
663 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
665 RCU should be locked before call of this function.
666 Returned item is valid only while RCU is locked:
668 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
673 hash_set::rcu_lock lock;
675 foo * pVal = theSet.get( 5 );
680 // Unlock RCU by rcu_lock destructor
681 // pVal can be freed at any time after RCU has been unlocked
685 template <typename Q>
686 value_type * get( Q const& val ) const
688 return bucket( val ).get( val );
691 /// Finds the key \p val and return the item found
693 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
694 but \p pred is used for comparing the keys.
696 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
698 \p pred must imply the same element order as the comparator used for building the set.
700 template <typename Q, typename Less>
701 value_type * get_with( Q const& val, Less pred ) const
703 return bucket( val ).get_with( val, pred );
706 /// Clears the set (non-atomic)
708 The function erases all items from the set.
710 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
711 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
712 <tt> empty() </tt> may return \p true but the set may contain item(s).
713 Therefore, \p clear may be used only for debugging purposes.
715 RCU \p synchronize method can be called. RCU should not be locked.
719 for ( size_t i = 0; i < bucket_count(); ++i )
720 m_Buckets[i].clear();
721 m_ItemCounter.reset();
724 /// Checks if the set is empty
726 Emptiness is checked by item counting: if item count is zero then the set is empty.
727 Thus, the correct item counting feature is an important part of Michael's set implementation.
734 /// Returns item count in the set
737 return m_ItemCounter;
740 /// Returns the size of hash table
742 Since MichaelHashSet cannot dynamically extend the hash table size,
743 the value returned is an constant depending on object initialization parameters;
744 see MichaelHashSet::MichaelHashSet for explanation.
746 size_t bucket_count() const
748 return m_nHashBitmask + 1;
752 }} // namespace cds::container
754 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_H