3 #ifndef __CDS_CONTAINER_MICHAEL_SET_H
4 #define __CDS_CONTAINER_MICHAEL_SET_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
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
359 using <tt>boost::ref</tt>
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 <tt>boost::ref</tt>.
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 # ifdef CDS_EMPLACE_SUPPORT
411 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
413 Returns \p true if inserting successful, \p false otherwise.
415 @note This function is available only for compiler that supports
416 variadic template and move semantics
418 template <typename... Args>
419 bool emplace( Args&&... args )
421 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
428 /// Deletes \p key from the set
429 /** \anchor cds_nonintrusive_MichaelSet_erase_val
431 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
432 template parameter \p Q defines the key type searching in the list.
433 The set item comparator should be able to compare the type \p value_type
436 Return \p true if key is found and deleted, \p false otherwise
438 template <typename Q>
439 bool erase( Q const& key )
441 const bool bRet = bucket( key ).erase( key );
447 /// Deletes the item from the set using \p pred predicate for searching
449 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
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>
455 bool erase_with( Q const& key, Less pred )
457 const bool bRet = bucket( key ).erase_with( key, pred );
463 /// Deletes \p key from the set
464 /** \anchor cds_nonintrusive_MichaelSet_erase_func
466 The function searches an item with key \p key, calls \p f functor
467 and deletes the item. If \p key is not found, the functor is not called.
469 The functor \p Func interface:
472 void operator()(value_type const& val);
475 The functor may be passed by reference using <tt>boost:ref</tt>
477 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
478 template parameter \p Q defines the key type searching in the list.
479 The list item comparator should be able to compare the type \p T of list item
482 Return \p true if key is found and deleted, \p false otherwise
484 template <typename Q, typename Func>
485 bool erase( Q const& key, Func f )
487 const bool bRet = bucket( key ).erase( key, f );
493 /// Deletes the item from the set using \p pred predicate for searching
495 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
496 but \p pred is used for key comparing.
497 \p Less functor has the interface like \p std::less.
498 \p Less must imply the same element order as the comparator used for building the set.
500 template <typename Q, typename Less, typename Func>
501 bool erase_with( Q const& key, Less pred, Func f )
503 const bool bRet = bucket( key ).erase_with( key, pred, f );
509 /// Extracts the item with specified \p key
510 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
511 The function searches an item with key equal to \p key,
512 unlinks it from the set, and returns it in \p dest parameter.
513 If the item with key equal to \p key is not found the function returns \p false.
515 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
517 The extracted item is freed automatically when returned \ref guarded_ptr object will be destroyed or released.
518 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
522 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
526 michael_set::guarded_ptr gp;
527 theSet.extract( gp, 5 );
531 // Destructor of gp releases internal HP guard
535 template <typename Q>
536 bool extract( guarded_ptr& dest, Q const& key )
538 const bool bRet = bucket( key ).extract( dest, key );
544 /// Extracts the item using compare functor \p pred
546 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(guarded_ptr&, Q const&)"
547 but \p pred predicate is used for key comparing.
549 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
551 \p pred must imply the same element order as the comparator used for building the set.
553 template <typename Q, typename Less>
554 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
556 const bool bRet = bucket( key ).extract_with( dest, key, pred );
562 /// Finds the key \p val
563 /** \anchor cds_nonintrusive_MichaelSet_find_func
565 The function searches the item with key equal to \p val and calls the functor \p f for item found.
566 The interface of \p Func functor is:
569 void operator()( value_type& item, Q& val );
572 where \p item is the item found, \p val is the <tt>find</tt> function argument.
574 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
576 The functor may change non-key fields of \p item. Note that the functor is only guarantee
577 that \p item cannot be disposed during functor is executing.
578 The functor does not serialize simultaneous access to the set's \p item. If such access is
579 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
581 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
582 can modify both arguments.
584 Note the hash functor specified for class \p Traits template parameter
585 should accept a parameter of type \p Q that may be not the same as \p value_type.
587 The function returns \p true if \p val is found, \p false otherwise.
589 template <typename Q, typename Func>
590 bool find( Q& val, Func f )
592 return bucket( val ).find( val, f );
595 /// Finds the key \p val using \p pred predicate for searching
597 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
598 but \p pred is used for key comparing.
599 \p Less functor has the interface like \p std::less.
600 \p Less must imply the same element order as the comparator used for building the set.
602 template <typename Q, typename Less, typename Func>
603 bool find_with( Q& val, Less pred, Func f )
605 return bucket( val ).find_with( val, pred, f );
608 /// Finds the key \p val
609 /** \anchor cds_nonintrusive_MichaelSet_find_cfunc
611 The function searches the item with key equal to \p val and calls the functor \p f for item found.
612 The interface of \p Func functor is:
615 void operator()( value_type& item, Q const& val );
618 where \p item is the item found, \p val is the <tt>find</tt> function argument.
620 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
622 The functor may change non-key fields of \p item. Note that the functor is only guarantee
623 that \p item cannot be disposed during functor is executing.
624 The functor does not serialize simultaneous access to the set's \p item. If such access is
625 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
627 Note the hash functor specified for class \p Traits template parameter
628 should accept a parameter of type \p Q that may be not the same as \p value_type.
630 The function returns \p true if \p val is found, \p false otherwise.
632 template <typename Q, typename Func>
633 bool find( Q const& val, Func f )
635 return bucket( val ).find( val, f );
638 /// Finds the key \p val using \p pred predicate for searching
640 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_cfunc "find(Q const&, Func)"
641 but \p pred is used for key comparing.
642 \p Less functor has the interface like \p std::less.
643 \p Less must imply the same element order as the comparator used for building the set.
645 template <typename Q, typename Less, typename Func>
646 bool find_with( Q const& val, Less pred, Func f )
648 return bucket( val ).find_with( val, pred, f );
651 /// Finds the key \p val
652 /** \anchor cds_nonintrusive_MichaelSet_find_val
653 The function searches the item with key equal to \p val
654 and returns \p true if it is found, and \p false otherwise.
656 Note the hash functor specified for class \p Traits template parameter
657 should accept a parameter of type \p Q that may be not the same as \ref value_type.
659 template <typename Q>
660 bool find( Q const& val )
662 return bucket( val ).find( val );
665 /// Finds the key \p val using \p pred predicate for searching
667 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_val "find(Q const&)"
668 but \p pred is used for key comparing.
669 \p Less functor has the interface like \p std::less.
670 \p Less must imply the same element order as the comparator used for building the set.
672 template <typename Q, typename Less>
673 bool find_with( Q const& val, Less pred )
675 return bucket( val ).find_with( val, pred );
678 /// Finds the key \p val and return the item found
679 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
680 The function searches the item with key equal to \p val
681 and assigns the item found to guarded pointer \p ptr.
682 The function returns \p true if \p val is found, and \p false otherwise.
683 If \p val is not found the \p ptr parameter is not changed.
685 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
689 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
693 michael_set::guarded_ptr gp;
694 if ( theSet.get( gp, 5 )) {
698 // Destructor of guarded_ptr releases internal HP guard
702 Note the compare functor specified for \p OrderedList template parameter
703 should accept a parameter of type \p Q that can be not the same as \p value_type.
705 template <typename Q>
706 bool get( guarded_ptr& ptr, Q const& val )
708 return bucket( val ).get( ptr, val );
711 /// Finds the key \p val and return the item found
713 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( guarded_ptr& ptr, Q const&)"
714 but \p pred is used for comparing the keys.
716 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
718 \p pred must imply the same element order as the comparator used for building the set.
720 template <typename Q, typename Less>
721 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
723 return bucket( val ).get_with( ptr, val, pred );
726 /// Clears the set (non-atomic)
728 The function erases all items from the set.
730 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
731 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
732 <tt> empty() </tt> may return \p true but the set may contain item(s).
733 Therefore, \p clear may be used only for debugging purposes.
737 for ( size_t i = 0; i < bucket_count(); ++i )
738 m_Buckets[i].clear();
739 m_ItemCounter.reset();
742 /// Checks if the set is empty
744 Emptiness is checked by item counting: if item count is zero then the set is empty.
745 Thus, the correct item counting feature is an important part of Michael's set implementation.
752 /// Returns item count in the set
755 return m_ItemCounter;
758 /// Returns the size of hash table
760 Since MichaelHashSet cannot dynamically extend the hash table size,
761 the value returned is an constant depending on object initialization parameters;
762 see MichaelHashSet::MichaelHashSet for explanation.
764 size_t bucket_count() const
766 return m_nHashBitmask + 1;
770 }} // namespace cds::container
772 #endif // ifndef __CDS_CONTAINER_MICHAEL_SET_H