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 typedef typename bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives
127 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
128 static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
131 item_counter m_ItemCounter; ///< Item counter
132 hash m_HashFunctor; ///< Hash functor
133 bucket_type * m_Buckets; ///< bucket table
137 const size_t m_nHashBitmask;
142 /// Calculates hash value of \p key
143 template <typename Q>
144 size_t hash_value( Q const& key ) const
146 return m_HashFunctor( key ) & m_nHashBitmask;
149 /// Returns the bucket (ordered list) for \p key
150 template <typename Q>
151 bucket_type& bucket( Q const& key )
153 return m_Buckets[ hash_value( key ) ];
155 template <typename Q>
156 bucket_type const& bucket( Q const& key ) const
158 return m_Buckets[ hash_value( key ) ];
164 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
165 - it has no post-increment operator
166 - it iterates items in unordered fashion
167 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
168 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
169 deleting operations it is no guarantee that you iterate all item in the set.
171 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
172 for debug purpose only.
174 typedef michael_set::details::iterator< bucket_type, false > iterator;
176 /// Const forward iterator
177 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
179 /// Returns a forward iterator addressing the first element in a set
181 For empty set \code begin() == end() \endcode
185 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
188 /// Returns an iterator that addresses the location succeeding the last element in a set
190 Do not use the value returned by <tt>end</tt> function to access any item.
191 The returned value can be used only to control reaching the end of the set.
192 For empty set \code begin() == end() \endcode
196 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
199 /// Returns a forward const iterator addressing the first element in a set
201 const_iterator begin() const
203 return get_const_begin();
205 const_iterator cbegin() const
207 return get_const_begin();
211 /// Returns an const iterator that addresses the location succeeding the last element in a set
213 const_iterator end() const
215 return get_const_end();
217 const_iterator cend() const
219 return get_const_end();
225 const_iterator get_const_begin() const
227 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
229 const_iterator get_const_end() const
231 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
236 /// Initialize hash set
238 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
239 when you create an object.
240 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
241 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
243 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
246 size_t nMaxItemCount, ///< estimation of max item count in the hash set
247 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
248 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
250 // GC and OrderedList::gc must be the same
251 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
253 // atomicity::empty_item_counter is not allowed as a item counter
254 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
255 "atomicity::empty_item_counter is not allowed as a item counter");
257 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
260 /// Clears hash set and destroys it
264 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
269 The function creates a node with copy of \p val value
270 and then inserts the node created into the set.
272 The type \p Q should contain as minimum the complete key for the node.
273 The object of \ref value_type should be constructible from a value of type \p Q.
274 In trivial case, \p Q is equal to \ref value_type.
276 The function applies RCU lock internally.
278 Returns \p true if \p val is inserted into the set, \p false otherwise.
280 template <typename Q>
281 bool insert( Q const& val )
283 const bool bRet = bucket( val ).insert( val );
291 The function allows to split creating of new item into two part:
292 - create item with key only
293 - insert new item into the set
294 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
296 The functor signature is:
298 void func( value_type& val );
300 where \p val is the item inserted.
301 The user-defined functor is called only if the inserting is success.
303 The function applies RCU lock internally.
305 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
306 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
309 template <typename Q, typename Func>
310 bool insert( Q const& val, Func f )
312 const bool bRet = bucket( val ).insert( val, f );
318 /// Ensures that the item exists in the set
320 The operation performs inserting or changing data with lock-free manner.
322 If the \p val key not found in the set, then the new item created from \p val
323 is inserted into the set. Otherwise, the functor \p func is called with the item found.
324 The functor \p Func signature is:
327 void operator()( bool bNew, value_type& item, const Q& val );
332 - \p bNew - \p true if the item has been inserted, \p false otherwise
333 - \p item - item of the set
334 - \p val - argument \p key passed into the \p ensure function
336 The functor may change non-key fields of the \p item.
338 The function applies RCU lock internally.
340 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
341 \p second is true if new item has been added or \p false if the item with \p key
342 already is in the set.
344 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
345 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
348 /// Updates the element
350 The operation performs inserting or changing data with lock-free manner.
352 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
353 Otherwise, the functor \p func is called with item found.
354 The functor signature is:
357 void operator()( bool bNew, value_type& item, Q const& val );
361 - \p bNew - \p true if the item has been inserted, \p false otherwise
362 - \p item - item of the set
363 - \p val - argument \p val passed into the \p %update() function
365 The functor may change non-key fields of the \p item.
367 The function applies RCU lock internally.
369 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
370 \p second is \p true if new item has been added or \p false if the item with \p key
371 already is in the set.
373 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
374 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
377 template <typename Q, typename Func>
378 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert = true )
380 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
385 template <typename Q, typename Func>
386 CDS_DEPRECATED("ensure() is deprecated, use update()")
387 std::pair<bool, bool> ensure( const Q& val, Func func )
389 return update( val, func, true );
393 /// Inserts data of type \p value_type created from \p args
395 Returns \p true if inserting successful, \p false otherwise.
397 The function applies RCU lock internally.
399 template <typename... Args>
400 bool emplace( Args&&... args )
402 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
408 /// Deletes \p key from the set
409 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
411 Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
412 template parameter \p Q defines the key type searching in the list.
413 The set item comparator should be able to compare the type \p value_type
416 RCU \p synchronize method can be called. RCU should not be locked.
418 Return \p true if key is found and deleted, \p false otherwise
420 template <typename Q>
421 bool erase( Q const& key )
423 const bool bRet = bucket( key ).erase( key );
429 /// Deletes the item from the set using \p pred predicate for searching
431 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
432 but \p pred is used for key comparing.
433 \p Less functor has the interface like \p std::less.
434 \p Less must imply the same element order as the comparator used for building the set.
436 template <typename Q, typename Less>
437 bool erase_with( Q const& key, Less pred )
439 const bool bRet = bucket( key ).erase_with( key, pred );
445 /// Deletes \p key from the set
446 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
448 The function searches an item with key \p key, calls \p f functor
449 and deletes the item. If \p key is not found, the functor is not called.
451 The functor \p Func interface:
454 void operator()(value_type const& val);
458 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
459 template parameter \p Q defines the key type searching in the list.
460 The list item comparator should be able to compare the type \p T of list item
463 RCU \p synchronize method can be called. RCU should not be locked.
465 Return \p true if key is found and deleted, \p false otherwise
467 template <typename Q, typename Func>
468 bool erase( Q const& key, Func f )
470 const bool bRet = bucket( key ).erase( key, f );
476 /// Deletes the item from the set using \p pred predicate for searching
478 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
479 but \p pred is used for key comparing.
480 \p Less functor has the interface like \p std::less.
481 \p Less must imply the same element order as the comparator used for building the set.
483 template <typename Q, typename Less, typename Func>
484 bool erase_with( Q const& key, Less pred, Func f )
486 const bool bRet = bucket( key ).erase_with( key, pred, f );
492 /// Extracts an item from the set
493 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
494 The function searches an item with key equal to \p key in the set,
495 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
496 If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr.
498 The function just excludes the item from the set and returns a pointer to item found.
499 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
500 - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
501 - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
502 See ordered list implementation for details.
505 #include <cds/urcu/general_buffered.h>
506 #include <cds/container/michael_list_rcu.h>
507 #include <cds/container/michael_set_rcu.h>
509 typedef cds::urcu::gc< general_buffered<> > rcu;
510 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
511 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
513 rcu_michael_set theSet;
516 typename rcu_michael_set::exempt_ptr p;
518 // For MichaelList we should not lock RCU
520 // Note that you must not delete the item found inside the RCU lock
521 p = theSet.extract( 10 );
523 // do something with p
527 // We may safely release p here
528 // release() passes the pointer to RCU reclamation cycle
532 template <typename Q>
533 exempt_ptr extract( Q const& key )
535 exempt_ptr p = bucket( key ).extract( key );
541 /// Extracts an item from the set using \p pred predicate for searching
543 The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
544 \p Less functor has the interface like \p std::less.
545 \p pred must imply the same element order as the comparator used for building the set.
547 template <typename Q, typename Less>
548 exempt_ptr extract_with( Q const& key, Less pred )
550 exempt_ptr p = bucket( key ).extract_with( key, pred );
556 /// Finds the key \p key
557 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
559 The function searches the item with key equal to \p key and calls the functor \p f for item found.
560 The interface of \p Func functor is:
563 void operator()( value_type& item, Q& key );
566 where \p item is the item found, \p key is the <tt>find</tt> function argument.
568 The functor may change non-key fields of \p item. Note that the functor is only guarantee
569 that \p item cannot be disposed during functor is executing.
570 The functor does not serialize simultaneous access to the set's \p item. If such access is
571 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
573 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
574 can modify both arguments.
576 Note the hash functor specified for class \p Traits template parameter
577 should accept a parameter of type \p Q that may be not the same as \p value_type.
579 The function applies RCU lock internally.
581 The function returns \p true if \p key is found, \p false otherwise.
583 template <typename Q, typename Func>
584 bool find( Q& key, Func f )
586 return bucket( key ).find( key, f );
589 template <typename Q, typename Func>
590 bool find( Q const& key, Func f )
592 return bucket( key ).find( key, f );
596 /// Finds the key \p key using \p pred predicate for searching
598 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
599 but \p pred is used for key comparing.
600 \p Less functor has the interface like \p std::less.
601 \p Less must imply the same element order as the comparator used for building the set.
603 template <typename Q, typename Less, typename Func>
604 bool find_with( Q& key, Less pred, Func f )
606 return bucket( key ).find_with( key, pred, f );
609 template <typename Q, typename Less, typename Func>
610 bool find_with( Q const& key, Less pred, Func f )
612 return bucket( key ).find_with( key, pred, f );
616 /// Checks whether the set contains \p key
618 The function searches the item with key equal to \p key
619 and returns \p true if the key is found, and \p false otherwise.
621 Note the hash functor specified for class \p Traits template parameter
622 should accept a parameter of type \p Q that can be not the same as \p value_type.
624 template <typename Q>
625 bool contains( Q const& key )
627 return bucket( key ).contains( key );
630 template <typename Q>
631 CDS_DEPRECATED("use contains()")
632 bool find( Q const& key )
634 return contains( key );
638 /// Checks whether the set contains \p key using \p pred predicate for searching
640 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
641 \p Less functor has the interface like \p std::less.
642 \p Less must imply the same element order as the comparator used for building the set.
644 template <typename Q, typename Less>
645 bool contains( Q const& key, Less pred )
647 return bucket( key ).contains( key, pred );
650 template <typename Q, typename Less>
651 CDS_DEPRECATED("use contains()")
652 bool find_with( Q const& key, Less pred )
654 return contains( key, pred );
658 /// Finds the key \p key and return the item found
659 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
660 The function searches the item with key equal to \p key and returns the pointer to item found.
661 If \p key is not found it returns \p nullptr.
662 Note the type of returned value depends on underlying \p bucket_type.
663 For details, see documentation of ordered list you use.
665 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
667 RCU should be locked before call of this function.
668 Returned item is valid only while RCU is locked:
670 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
672 typename hash_set::raw_ptr gp;
676 hash_set::rcu_lock lock;
678 gp = theSet.get( 5 );
683 // Unlock RCU by rcu_lock destructor
684 // gp can be reclaimed at any time after RCU has been unlocked
688 template <typename Q>
689 raw_ptr get( Q const& key )
691 return bucket( key ).get( key );
694 /// Finds the key \p key and return the item found
696 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
697 but \p pred is used for comparing the keys.
699 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
701 \p pred must imply the same element order as the comparator used for building the set.
703 template <typename Q, typename Less>
704 raw_ptr get_with( Q const& key, Less pred )
706 return bucket( key ).get_with( key, pred );
709 /// Clears the set (not atomic)
712 for ( size_t i = 0; i < bucket_count(); ++i )
713 m_Buckets[i].clear();
714 m_ItemCounter.reset();
717 /// Checks if the set is empty
719 Emptiness is checked by item counting: if item count is zero then the set is empty.
720 Thus, the correct item counting feature is an important part of Michael's set implementation.
727 /// Returns item count in the set
730 return m_ItemCounter;
733 /// Returns the size of hash table
735 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
736 the value returned is an constant depending on object initialization parameters;
737 see MichaelHashSet::MichaelHashSet for explanation.
739 size_t bucket_count() const
741 return m_nHashBitmask + 1;
745 }} // namespace cds::container
747 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H