3 #ifndef __CDS_CONTAINER_MICHAEL_SET_H
4 #define __CDS_CONTAINER_MICHAEL_SET_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
12 /** @ingroup cds_nonintrusive_set
13 \anchor cds_nonintrusive_MichaelHashSet_hp
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 GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
25 from the \p libcds library.
26 Note the \p GC must be the same as the GC used for \p OrderedList
27 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList.
28 The ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
29 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
31 - \p Traits - type traits. See michael_set::type_traits for explanation.
33 Instead of defining \p Traits struct you may use option-based syntax with michael_set::make_traits metafunction.
34 For michael_set::make_traits the following option may be used:
35 - opt::hash - mandatory option, specifies hash functor.
36 - opt::item_counter - optional, specifies item counting policy. See michael_set::type_traits for explanation.
37 - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
39 There are the specializations:
40 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_set_rcu.h</tt>,
41 see \ref cds_nonintrusive_MichaelHashSet_rcu "MichaelHashSet<RCU>".
42 - for \ref cds::gc::nogc declared in <tt>cds/container/michael_set_nogc.h</tt>,
43 see \ref cds_nonintrusive_MichaelHashSet_nogc "MichaelHashSet<gc::nogc>".
45 \anchor cds_nonintrusive_MichaelHashSet_hash_functor
48 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from node type \p value_type.
49 It is expected that type \p Q contains full key of node type \p value_type, and if keys of type \p Q and \p value_type
50 are equal the hash values of these keys must be equal too.
52 The hash functor <tt>Traits::hash</tt> should accept parameters of both type:
56 std::string key_ ; // key field
62 size_t operator()( const std::string& s ) const
64 return std::hash( s );
67 size_t operator()( const Foo& f ) const
69 return (*this)( f.key_ );
76 The class supports a forward iterator (\ref iterator and \ref const_iterator).
77 The iteration is unordered.
78 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
79 so, the element cannot be reclaimed while the iterator object is alive.
80 However, passing an iterator object between threads is dangerous.
82 \warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
83 all elements in the set: any concurrent deletion can exclude the element
84 pointed by the iterator from the set, and your iteration can be terminated
85 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
87 Remember, each iterator object requires an additional hazard pointer, that may be
88 a limited resource for \p GC like as gc::HP and gc::HRC (for gc::PTB the count of
91 The iterator class supports the following minimalistic interface:
98 iterator( iterator const& s);
100 value_type * operator ->() const;
101 value_type& operator *() const;
104 iterator& operator ++();
107 iterator& operator = (const iterator& src);
109 bool operator ==(iterator const& i ) const;
110 bool operator !=(iterator const& i ) const;
113 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
117 Suppose, we have the following type \p Foo that we want to store in our MichaelHashSet:
120 int nKey ; // key field
121 int nVal ; // value field
125 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
126 that will be used as a bucket for the set. We will use gc::PTB reclamation schema and
127 MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
130 #include <cds/container/michael_list_ptb.h>
131 #include <cds/container/michael_set.h>
133 namespace cc = cds::container;
137 int operator ()(Foo const& v1, Foo const& v2 ) const
139 if ( std::less( v1.nKey, v2.nKey ))
141 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
146 typedef cc::MichaelList< cds::gc::PTB, Foo,
147 typename cc::michael_list::make_traits<
148 cc::opt::compare< Foo_cmp > // item comparator option
152 // Hash functor for Foo
154 size_t operator ()( int i ) const
156 return std::hash( i );
158 size_t operator()( Foo const& i ) const
160 return std::hash( i.nKey );
165 // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
166 typedef cc::MichaelHashSet< cds::gc::PTB, bucket_list,
167 cc::michael_set::make_traits<
168 cc::opt::hash< foo_hash >
179 #ifdef CDS_DOXYGEN_INVOKED
180 class Traits = michael_set::type_traits
188 typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
189 typedef Traits options ; ///< Traits template parameters
191 typedef typename bucket_type::value_type value_type ; ///< type of value stored in the list
192 typedef GC gc ; ///< Garbage collector
193 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
195 /// Hash functor for \ref value_type and all its derivatives that you use
196 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
197 typedef typename options::item_counter item_counter ; ///< Item counter type
199 /// Bucket table allocator
200 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
202 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
205 item_counter m_ItemCounter ; ///< Item counter
206 hash m_HashFunctor ; ///< Hash functor
208 bucket_type * m_Buckets ; ///< bucket table
212 const size_t m_nHashBitmask;
216 /// Calculates hash value of \p key
217 template <typename Q>
218 size_t hash_value( Q const& key ) const
220 return m_HashFunctor( key ) & m_nHashBitmask;
223 /// Returns the bucket (ordered list) for \p key
224 template <typename Q>
225 bucket_type& bucket( Q const& key )
227 return m_Buckets[ hash_value( key ) ];
232 typedef michael_set::details::iterator< bucket_type, false > iterator;
234 /// Const forward iterator
235 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
237 /// Returns a forward iterator addressing the first element in a set
239 For empty set \code begin() == end() \endcode
243 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
246 /// Returns an iterator that addresses the location succeeding the last element in a set
248 Do not use the value returned by <tt>end</tt> function to access any item.
249 The returned value can be used only to control reaching the end of the set.
250 For empty set \code begin() == end() \endcode
254 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
257 /// Returns a forward const iterator addressing the first element in a set
259 const_iterator begin() const
261 return get_const_begin();
263 const_iterator cbegin()
265 return get_const_begin();
269 /// Returns an const iterator that addresses the location succeeding the last element in a set
271 const_iterator end() const
273 return get_const_end();
275 const_iterator cend()
277 return get_const_end();
283 const_iterator get_const_begin() const
285 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
287 const_iterator get_const_end() const
289 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
294 /// Initialize hash set
296 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
297 when you create an object.
298 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
299 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
300 Note, that many popular STL hash map implementation uses load factor 1.
302 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
305 size_t nMaxItemCount, ///< estimation of max item count in the hash set
306 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
307 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
309 // GC and OrderedList::gc must be the same
310 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
312 // atomicity::empty_item_counter is not allowed as a item counter
313 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
315 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
318 /// Clear hash set and destroy it
322 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
327 The function creates a node with copy of \p val value
328 and then inserts the node created into the set.
330 The type \p Q should contain as minimum the complete key for the node.
331 The object of \ref value_type should be constructible from a value of type \p Q.
332 In trivial case, \p Q is equal to \ref value_type.
334 Returns \p true if \p val is inserted into the set, \p false otherwise.
336 template <typename Q>
337 bool insert( Q const& val )
339 const bool bRet = bucket( val ).insert( val );
347 The function allows to split creating of new item into two part:
348 - create item with key only
349 - insert new item into the set
350 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
352 The functor signature is:
354 void func( value_type& val );
356 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
357 \p val no any other changes could be made on this set's item by concurrent threads.
358 The user-defined functor is called only if the inserting is success. It may be passed by reference
361 template <typename Q, typename Func>
362 bool insert( Q const& val, Func f )
364 const bool bRet = bucket( val ).insert( val, f );
370 /// Ensures that the item exists in the set
372 The operation performs inserting or changing data with lock-free manner.
374 If the \p val key not found in the set, then the new item created from \p val
375 is inserted into the set. Otherwise, the functor \p func is called with the item found.
376 The functor \p Func should be a function with signature:
378 void func( bool bNew, value_type& item, const Q& val );
383 void operator()( bool bNew, value_type& item, const Q& val );
388 - \p bNew - \p true if the item has been inserted, \p false otherwise
389 - \p item - item of the set
390 - \p val - argument \p key passed into the \p ensure function
392 The functor may change non-key fields of the \p item; however, \p func must guarantee
393 that during changing no any other modifications could be made on this item by concurrent threads.
395 You may pass \p func argument by reference using \p std::ref
397 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
398 \p second is true if new item has been added or \p false if the item with \p key
399 already is in the set.
401 template <typename Q, typename Func>
402 std::pair<bool, bool> ensure( const Q& val, Func func )
404 std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
405 if ( bRet.first && bRet.second )
410 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
412 Returns \p true if inserting successful, \p false otherwise.
414 template <typename... Args>
415 bool emplace( Args&&... args )
417 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
423 /// Deletes \p key from the set
424 /** \anchor cds_nonintrusive_MichaelSet_erase_val
426 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
427 template parameter \p Q defines the key type searching in the list.
428 The set item comparator should be able to compare the type \p value_type
431 Return \p true if key is found and deleted, \p false otherwise
433 template <typename Q>
434 bool erase( Q const& key )
436 const bool bRet = bucket( key ).erase( key );
442 /// Deletes the item from the set using \p pred predicate for searching
444 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
445 but \p pred is used for key comparing.
446 \p Less functor has the interface like \p std::less.
447 \p Less must imply the same element order as the comparator used for building the set.
449 template <typename Q, typename Less>
450 bool erase_with( Q const& key, Less pred )
452 const bool bRet = bucket( key ).erase_with( key, pred );
458 /// Deletes \p key from the set
459 /** \anchor cds_nonintrusive_MichaelSet_erase_func
461 The function searches an item with key \p key, calls \p f functor
462 and deletes the item. If \p key is not found, the functor is not called.
464 The functor \p Func interface:
467 void operator()(value_type const& val);
470 The functor may be passed by reference using <tt>boost:ref</tt>
472 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
473 template parameter \p Q defines the key type searching in the list.
474 The list item comparator should be able to compare the type \p T of list item
477 Return \p true if key is found and deleted, \p false otherwise
479 template <typename Q, typename Func>
480 bool erase( Q const& key, Func f )
482 const bool bRet = bucket( key ).erase( key, f );
488 /// Deletes the item from the set using \p pred predicate for searching
490 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
491 but \p pred is used for key comparing.
492 \p Less functor has the interface like \p std::less.
493 \p Less must imply the same element order as the comparator used for building the set.
495 template <typename Q, typename Less, typename Func>
496 bool erase_with( Q const& key, Less pred, Func f )
498 const bool bRet = bucket( key ).erase_with( key, pred, f );
504 /// Extracts the item with specified \p key
505 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
506 The function searches an item with key equal to \p key,
507 unlinks it from the set, and returns it in \p dest parameter.
508 If the item with key equal to \p key is not found the function returns \p false.
510 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
512 The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
513 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
517 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
521 michael_set::guarded_ptr gp;
522 theSet.extract( gp, 5 );
526 // Destructor of gp releases internal HP guard
530 template <typename Q>
531 bool extract( guarded_ptr& dest, Q const& key )
533 const bool bRet = bucket( key ).extract( dest, key );
539 /// Extracts the item using compare functor \p pred
541 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(guarded_ptr&, Q const&)"
542 but \p pred predicate is used for key comparing.
544 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
546 \p pred must imply the same element order as the comparator used for building the set.
548 template <typename Q, typename Less>
549 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
551 const bool bRet = bucket( key ).extract_with( dest, key, pred );
557 /// Finds the key \p val
558 /** \anchor cds_nonintrusive_MichaelSet_find_func
560 The function searches the item with key equal to \p val and calls the functor \p f for item found.
561 The interface of \p Func functor is:
564 void operator()( value_type& item, Q& val );
567 where \p item is the item found, \p val is the <tt>find</tt> function argument.
569 You may pass \p f argument by reference using \p std::ref.
571 The functor may change non-key fields of \p item. Note that the functor is only guarantee
572 that \p item cannot be disposed during functor is executing.
573 The functor does not serialize simultaneous access to the set's \p item. If such access is
574 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
576 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
577 can modify both arguments.
579 Note the hash functor specified for class \p Traits template parameter
580 should accept a parameter of type \p Q that may be not the same as \p value_type.
582 The function returns \p true if \p val is found, \p false otherwise.
584 template <typename Q, typename Func>
585 bool find( Q& val, Func f )
587 return bucket( val ).find( val, f );
590 /// Finds the key \p val using \p pred predicate for searching
592 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
593 but \p pred is used for key comparing.
594 \p Less functor has the interface like \p std::less.
595 \p Less must imply the same element order as the comparator used for building the set.
597 template <typename Q, typename Less, typename Func>
598 bool find_with( Q& val, Less pred, Func f )
600 return bucket( val ).find_with( val, pred, f );
603 /// Finds the key \p val
604 /** \anchor cds_nonintrusive_MichaelSet_find_cfunc
606 The function searches the item with key equal to \p val and calls the functor \p f for item found.
607 The interface of \p Func functor is:
610 void operator()( value_type& item, Q const& val );
613 where \p item is the item found, \p val is the <tt>find</tt> function argument.
615 You may pass \p f argument by reference using \p std::ref.
617 The functor may change non-key fields of \p item. Note that the functor is only guarantee
618 that \p item cannot be disposed during functor is executing.
619 The functor does not serialize simultaneous access to the set's \p item. If such access is
620 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
622 Note the hash functor specified for class \p Traits template parameter
623 should accept a parameter of type \p Q that may be not the same as \p value_type.
625 The function returns \p true if \p val is found, \p false otherwise.
627 template <typename Q, typename Func>
628 bool find( Q const& val, Func f )
630 return bucket( val ).find( val, f );
633 /// Finds the key \p val using \p pred predicate for searching
635 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_cfunc "find(Q const&, Func)"
636 but \p pred is used for key comparing.
637 \p Less functor has the interface like \p std::less.
638 \p Less must imply the same element order as the comparator used for building the set.
640 template <typename Q, typename Less, typename Func>
641 bool find_with( Q const& val, Less pred, Func f )
643 return bucket( val ).find_with( val, pred, f );
646 /// Finds the key \p val
647 /** \anchor cds_nonintrusive_MichaelSet_find_val
648 The function searches the item with key equal to \p val
649 and returns \p true if it is found, and \p false otherwise.
651 Note the hash functor specified for class \p Traits template parameter
652 should accept a parameter of type \p Q that may be not the same as \ref value_type.
654 template <typename Q>
655 bool find( Q const& val )
657 return bucket( val ).find( val );
660 /// Finds the key \p val using \p pred predicate for searching
662 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_val "find(Q const&)"
663 but \p pred is used for key comparing.
664 \p Less functor has the interface like \p std::less.
665 \p Less must imply the same element order as the comparator used for building the set.
667 template <typename Q, typename Less>
668 bool find_with( Q const& val, Less pred )
670 return bucket( val ).find_with( val, pred );
673 /// Finds the key \p val and return the item found
674 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
675 The function searches the item with key equal to \p val
676 and assigns the item found to guarded pointer \p ptr.
677 The function returns \p true if \p val is found, and \p false otherwise.
678 If \p val is not found the \p ptr parameter is not changed.
680 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
684 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
688 michael_set::guarded_ptr gp;
689 if ( theSet.get( gp, 5 )) {
693 // Destructor of guarded_ptr releases internal HP guard
697 Note the compare functor specified for \p OrderedList template parameter
698 should accept a parameter of type \p Q that can be not the same as \p value_type.
700 template <typename Q>
701 bool get( guarded_ptr& ptr, Q const& val )
703 return bucket( val ).get( ptr, val );
706 /// Finds the key \p val and return the item found
708 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( guarded_ptr& ptr, Q const&)"
709 but \p pred is used for comparing the keys.
711 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
713 \p pred must imply the same element order as the comparator used for building the set.
715 template <typename Q, typename Less>
716 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
718 return bucket( val ).get_with( ptr, val, pred );
721 /// Clears the set (non-atomic)
723 The function erases all items from the set.
725 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
726 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
727 <tt> empty() </tt> may return \p true but the set may contain item(s).
728 Therefore, \p clear may be used only for debugging purposes.
732 for ( size_t i = 0; i < bucket_count(); ++i )
733 m_Buckets[i].clear();
734 m_ItemCounter.reset();
737 /// Checks if the set is empty
739 Emptiness is checked by item counting: if item count is zero then the set is empty.
740 Thus, the correct item counting feature is an important part of Michael's set implementation.
747 /// Returns item count in the set
750 return m_ItemCounter;
753 /// Returns the size of hash table
755 Since MichaelHashSet cannot dynamically extend the hash table size,
756 the value returned is an constant depending on object initialization parameters;
757 see MichaelHashSet::MichaelHashSet for explanation.
759 size_t bucket_count() const
761 return m_nHashBitmask + 1;
765 }} // namespace cds::container
767 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_H