3 #ifndef __CDS_INTRUSIVE_MICHAEL_SET_H
4 #define __CDS_INTRUSIVE_MICHAEL_SET_H
6 #include <cds/intrusive/details/michael_set_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace intrusive {
11 /// Michael's hash set
12 /** @ingroup cds_intrusive_map
13 \anchor cds_intrusive_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. Note the \p GC must be the same as the GC used for \p OrderedList
25 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, MichaelList, LazyList.
26 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
27 schema \p GC used by hash-set, 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.
30 Instead of defining \p Traits struct you can use option-based syntax with michael_set::make_traits metafunction.
32 There are several specializations of \p %MichaelHashSet for each GC. You should include:
33 - <tt><cds/intrusive/michael_set_rcu.h></tt> for \ref cds_intrusive_MichaelHashSet_rcu "RCU type"
34 - <tt><cds/intrusive/michael_set_nogc.h></tt> for \ref cds_intrusive_MichaelHashSet_nogc for persistent set
35 - <tt><cds/intrusive/michael_set.h></tt> for other GC (gc::HP, gc::HRC, gc::PTB)
39 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from \p value_type.
40 It is expected that type \p Q contains full key of \p value_type, and for equal keys of type \p Q and \p value_type
41 the hash values of these keys must be equal too.
42 The hash functor <tt>Traits::hash</tt> should accept parameters of both type:
46 std::string key_ ; // key field
52 size_t operator()( const std::string& s ) const
54 return std::hash( s );
57 size_t operator()( const Foo& f ) const
59 return (*this)( f.key_ );
67 First, you should define ordered list type to use in your hash set:
69 // For gc::HP-based MichaelList implementation
70 #include <cds/intrusive/michael_list_hp.h>
72 // cds::intrusive::MichaelHashSet declaration
73 #include <cds/intrusive/michael_set.h>
75 // Type of hash-set items
76 struct Foo: public cds::intrusive::michael_list::node< cds::gc::HP >
78 std::string key_ ; // key field
79 unsigned val_ ; // value field
80 // ... other value fields
83 // Declare comparator for the item
86 int operator()( const Foo& f1, const Foo& f2 ) const
88 return f1.key_.compare( f2.key_ );
92 // Declare bucket type for Michael's hash set
93 // The bucket type is any ordered list type like MichaelList, LazyList
94 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
95 typename cds::intrusive::michael_list::make_traits<
97 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
98 // item comparator option
99 ,cds::opt::compare< FooCmp >
104 Second, you should declare Michael's hash set container:
107 // Declare hash functor
108 // Note, the hash functor accepts parameter type Foo and std::string
110 size_t operator()( const Foo& f ) const
112 return cds::opt::v::hash<std::string>()( f.key_ );
114 size_t operator()( const std::string& f ) const
116 return cds::opt::v::hash<std::string>()( f );
120 // Michael's set typedef
121 typedef cds::intrusive::MichaelHashSet<
124 ,typename cds::intrusive::michael_set::make_traits<
125 cds::opt::hash< FooHash >
130 Now, you can use \p Foo_set in your application.
132 Like other intrusive containers, you may build several containers on single item structure:
134 #include <cds/intrusive/michael_list_hp.h>
135 #include <cds/intrusive/michael_list_dhp.h>
136 #include <cds/intrusive/michael_set.h>
142 // The first key is maintained by gc::HP, second key is maintained by gc::PTB garbage collectors
144 : public cds::intrusive::michael_list::node< cds::gc::HP, tag_key1_idx >
145 , public cds::intrusive::michael_list::node< cds::gc::PTB, tag_key2_idx >
147 std::string key1_ ; // first key field
148 unsigned int key2_ ; // second key field
150 // ... value fields and fields for controlling item's lifetime
153 // Declare comparators for the item
156 int operator()( const Foo& f1, const Foo& f2 ) const { return f1.key1_.compare( f2.key1_ ) ; }
160 bool operator()( const Foo& f1, const Foo& f2 ) const { return f1.key2_ < f2.key1_ ; }
163 // Declare bucket type for Michael's hash set indexed by key1_ field and maintained by gc::HP
164 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
165 typename cds::intrusive::michael_list::make_traits<
167 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP >, tag_key1_idx > >
168 // item comparator option
169 ,cds::opt::compare< Key1Cmp >
173 // Declare bucket type for Michael's hash set indexed by key2_ field and maintained by gc::PTB
174 typedef cds::intrusive::MichaelList< cds::gc::PTB, Foo,
175 typename cds::intrusive::michael_list::make_traits<
177 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB >, tag_key2_idx > >
178 // item comparator option
179 ,cds::opt::less< Key2Less >
183 // Declare hash functor
185 size_t operator()( const Foo& f ) const { return cds::opt::v::hash<std::string>()( f.key1_ ) ; }
186 size_t operator()( const std::string& s ) const { return cds::opt::v::hash<std::string>()( s ) ; }
188 inline size_t Key2Hash( const Foo& f ) { return (size_t) f.key2_ ; }
190 // Michael's set indexed by key1_ field
191 typedef cds::intrusive::MichaelHashSet<
194 ,typename cds::intrusive::michael_set::make_traits<
195 cds::opt::hash< Key1Hash >
199 // Michael's set indexed by key2_ field
200 typedef cds::intrusive::MichaelHashSet<
203 ,typename cds::intrusive::michael_set::make_traits<
204 cds::opt::hash< Key2Hash >
212 #ifdef CDS_DOXYGEN_INVOKED
213 class Traits = michael_set::type_traits
221 typedef OrderedList ordered_list ; ///< type of ordered list used as a bucket implementation
222 typedef ordered_list bucket_type ; ///< bucket type
223 typedef Traits options ; ///< Traits template parameters
225 typedef typename ordered_list::value_type value_type ; ///< type of value stored in the list
226 typedef GC gc ; ///< Garbage collector
227 typedef typename ordered_list::key_comparator key_comparator ; ///< key comparison functor
228 typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
230 /// Hash functor for \ref value_type and all its derivatives that you use
231 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
232 typedef typename options::item_counter item_counter ; ///< Item counter type
234 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
236 /// Bucket table allocator
237 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
240 item_counter m_ItemCounter ; ///< Item counter
241 hash m_HashFunctor ; ///< Hash functor
243 bucket_type * m_Buckets ; ///< bucket table
247 const size_t m_nHashBitmask;
251 /// Calculates hash value of \p key
252 template <typename Q>
253 size_t hash_value( const Q& key ) const
255 return m_HashFunctor( key ) & m_nHashBitmask;
258 /// Returns the bucket (ordered list) for \p key
259 template <typename Q>
260 bucket_type& bucket( const Q& key )
262 return m_Buckets[ hash_value( key ) ];
268 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
269 - it has no post-increment operator
270 - it iterates items in unordered fashion
271 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
272 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
273 deleting operations it is no guarantee that you iterate all item in the set.
275 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
276 for debug purpose only.
278 typedef michael_set::details::iterator< bucket_type, false > iterator;
280 /// Const forward iterator
282 For iterator's features and requirements see \ref iterator
284 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
286 /// Returns a forward iterator addressing the first element in a set
288 For empty set \code begin() == end() \endcode
292 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
295 /// Returns an iterator that addresses the location succeeding the last element in a set
297 Do not use the value returned by <tt>end</tt> function to access any item.
298 The returned value can be used only to control reaching the end of the set.
299 For empty set \code begin() == end() \endcode
303 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
306 /// Returns a forward const iterator addressing the first element in a set
308 const_iterator begin() const
310 return get_const_begin();
312 const_iterator cbegin()
314 return get_const_begin();
318 /// Returns an const iterator that addresses the location succeeding the last element in a set
320 const_iterator end() const
322 return get_const_end();
324 const_iterator cend()
326 return get_const_end();
332 const_iterator get_const_begin() const
334 return const_iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
336 const_iterator get_const_end() const
338 return const_iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
343 /// Initializes hash set
345 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
346 At construction time you should pass estimated maximum item count and a load factor.
347 The load factor is average size of one bucket - a small number between 1 and 10.
348 The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
349 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
352 size_t nMaxItemCount, ///< estimation of max item count in the hash set
353 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10, default is 1.
354 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
356 // GC and OrderedList::gc must be the same
357 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
359 // atomicity::empty_item_counter is not allowed as a item counter
360 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
362 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
365 /// Clears hash set object and destroys it
369 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
374 The function inserts \p val in the set if it does not contain
375 an item with key equal to \p val.
377 Returns \p true if \p val is placed into the set, \p false otherwise.
379 bool insert( value_type& val )
381 bool bRet = bucket( val ).insert( val );
389 This function is intended for derived non-intrusive containers.
391 The function allows to split creating of new item into two part:
392 - create item with key only
393 - insert new item into the set
394 - if inserting is success, calls \p f functor to initialize value-field of \p val.
396 The functor signature is:
398 void func( value_type& val );
400 where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
401 \p val no any other changes could be made on this set's item by concurrent threads.
402 The user-defined functor is called only if the inserting is success and can be passed by reference
405 template <typename Func>
406 bool insert( value_type& val, Func f )
408 bool bRet = bucket( val ).insert( val, f );
414 /// Ensures that the \p val exists in the set
416 The operation performs inserting or changing data with lock-free manner.
418 If the item \p val not found in the set, then \p val is inserted into the set.
419 Otherwise, the functor \p func is called with item found.
420 The functor signature is:
422 void func( bool bNew, value_type& item, value_type& val );
425 - \p bNew - \p true if the item has been inserted, \p false otherwise
426 - \p item - item of the set
427 - \p val - argument \p val passed into the \p ensure function
428 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
429 refers to the same thing.
431 The functor may change non-key fields of the \p item; however, \p func must guarantee
432 that during changing no any other modifications could be made on this item by concurrent threads.
434 You may pass \p func argument by reference using \p std::ref.
436 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
437 \p second is \p true if new item has been added or \p false if the item with \p key
438 already is in the set.
440 template <typename Func>
441 std::pair<bool, bool> ensure( value_type& val, Func func )
443 std::pair<bool, bool> bRet = bucket( val ).ensure( val, func );
444 if ( bRet.first && bRet.second )
449 /// Unlinks the item \p val from the set
451 The function searches the item \p val in the set and unlink it from the set
452 if it is found and is equal to \p val.
454 The function returns \p true if success and \p false otherwise.
456 bool unlink( value_type& val )
458 bool bRet = bucket( val ).unlink( val );
464 /// Deletes the item from the set
465 /** \anchor cds_intrusive_MichaelHashSet_hp_erase
466 The function searches an item with key equal to \p val in the set,
467 unlinks it from the set, and returns \p true.
468 If the item with key equal to \p val is not found the function return \p false.
470 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
472 template <typename Q>
473 bool erase( Q const& val )
475 if ( bucket( val ).erase( val )) {
482 /// Deletes the item from the set using \p pred predicate for searching
484 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase "erase(Q const&)"
485 but \p pred is used for key comparing.
486 \p Less functor has the interface like \p std::less.
487 \p pred must imply the same element order as the comparator used for building the set.
489 template <typename Q, typename Less>
490 bool erase_with( Q const& val, Less pred )
492 if ( bucket( val ).erase_with( val, pred )) {
499 /// Deletes the item from the set
500 /** \anchor cds_intrusive_MichaelHashSet_hp_erase_func
501 The function searches an item with key equal to \p val in the set,
502 call \p f functor with item found, and unlinks it from the set.
503 The \ref disposer specified in \p OrderedList class template parameter is called
504 by garbage collector \p GC asynchronously.
506 The \p Func interface is
509 void operator()( value_type const& item );
512 The functor may be passed by reference with <tt>boost:ref</tt>
514 If the item with key equal to \p val is not found the function return \p false.
516 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
518 template <typename Q, typename Func>
519 bool erase( const Q& val, Func f )
521 if ( bucket( val ).erase( val, f )) {
528 /// Deletes the item from the set using \p pred predicate for searching
530 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase_func "erase(Q const&, Func)"
531 but \p pred is used for key comparing.
532 \p Less functor has the interface like \p std::less.
533 \p pred must imply the same element order as the comparator used for building the set.
535 template <typename Q, typename Less, typename Func>
536 bool erase_with( const Q& val, Less pred, Func f )
538 if ( bucket( val ).erase_with( val, pred, f )) {
545 /// Extracts the item with specified \p key
546 /** \anchor cds_intrusive_MichaelHashSet_hp_extract
547 The function searches an item with key equal to \p key,
548 unlinks it from the set, and returns it in \p dest parameter.
549 If the item with key equal to \p key is not found the function returns \p false.
551 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
553 The \ref disposer specified in \p OrderedList class' template parameter is called automatically
554 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
555 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
559 typedef cds::intrusive::MichaelHashSet< your_template_args > michael_set;
563 michael_set::guarded_ptr gp;
564 theSet.extract( gp, 5 );
568 // Destructor of gp releases internal HP guard
572 template <typename Q>
573 bool extract( guarded_ptr& dest, Q const& key )
575 if ( bucket( key ).extract( dest, key )) {
582 /// Extracts the item using compare functor \p pred
584 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_extract "extract(guarded_ptr&, Q const&)"
585 but \p pred predicate is used for key comparing.
587 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
589 \p pred must imply the same element order as the comparator used for building the list.
591 template <typename Q, typename Less>
592 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
594 if ( bucket( key ).extract_with( dest, key, pred )) {
601 /// Finds the key \p val
602 /** \anchor cds_intrusive_MichaelHashSet_hp_find_func
603 The function searches the item with key equal to \p val and calls the functor \p f for item found.
604 The interface of \p Func functor is:
607 void operator()( value_type& item, Q& val );
610 where \p item is the item found, \p val is the <tt>find</tt> function argument.
612 You can pass \p f argument by reference using \p std::ref.
614 The functor may change non-key fields of \p item. Note that the functor is only guarantee
615 that \p item cannot be disposed during functor is executing.
616 The functor does not serialize simultaneous access to the set \p item. If such access is
617 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
619 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
620 may modify both arguments.
622 Note the hash functor specified for class \p Traits template parameter
623 should accept a parameter of type \p Q that can 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& 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_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
636 but \p pred is used for key comparing.
637 \p Less functor has the interface like \p std::less.
638 \p pred 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& val, Less pred, Func f )
643 return bucket( val ).find_with( val, pred, f );
646 /// Finds the key \p val
647 /** \anchor cds_intrusive_MichaelHashSet_hp_find_cfunc
648 The function searches the item with key equal to \p val and calls the functor \p f for item found.
649 The interface of \p Func functor is:
652 void operator()( value_type& item, Q& val );
655 where \p item is the item found, \p val is the <tt>find</tt> function argument.
657 You can pass \p f argument by reference using \p std::ref.
659 The functor may change non-key fields of \p item. Note that the functor is only guarantee
660 that \p item cannot be disposed during functor is executing.
661 The functor does not serialize simultaneous access to the set \p item. If such access is
662 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
664 Note the hash functor specified for class \p Traits template parameter
665 should accept a parameter of type \p Q that can be not the same as \p value_type.
667 The function returns \p true if \p val is found, \p false otherwise.
669 template <typename Q, typename Func>
670 bool find( Q const& val, Func f )
672 return bucket( val ).find( val, f );
675 /// Finds the key \p val using \p pred predicate for searching
677 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_cfunc "find(Q const&, Func)"
678 but \p pred is used for key comparing.
679 \p Less functor has the interface like \p std::less.
680 \p pred must imply the same element order as the comparator used for building the set.
682 template <typename Q, typename Less, typename Func>
683 bool find_with( Q const& val, Less pred, Func f )
685 return bucket( val ).find_with( val, pred, f );
688 /// Finds the key \p val
689 /** \anchor cds_intrusive_MichaelHashSet_hp_find_val
690 The function searches the item with key equal to \p val
691 and returns \p true if it is found, and \p false otherwise.
693 Note the hash functor specified for class \p Traits template parameter
694 should accept a parameter of type \p Q that can be not the same as \p value_type.
696 template <typename Q>
697 bool find( Q const & val )
699 return bucket( val ).find( val );
702 /// Finds the key \p val using \p pred predicate for searching
704 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_val "find(Q const&)"
705 but \p pred is used for key comparing.
706 \p Less functor has the interface like \p std::less.
707 \p pred must imply the same element order as the comparator used for building the set.
709 template <typename Q, typename Less>
710 bool find_with( Q const & val, Less pred )
712 return bucket( val ).find_with( val, pred );
715 /// Finds the key \p val and return the item found
716 /** \anchor cds_intrusive_MichaelHashSet_hp_get
717 The function searches the item with key equal to \p val
718 and assigns the item found to guarded pointer \p ptr.
719 The function returns \p true if \p val is found, and \p false otherwise.
720 If \p val is not found the \p ptr parameter is not changed.
722 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
726 typedef cds::intrusive::MichaeHashSet< your_template_params > michael_set;
730 michael_set::guarded_ptr gp;
731 if ( theSet.get( gp, 5 )) {
735 // Destructor of guarded_ptr releases internal HP guard
739 Note the compare functor specified for \p OrderedList template parameter
740 should accept a parameter of type \p Q that can be not the same as \p value_type.
742 template <typename Q>
743 bool get( guarded_ptr& ptr, Q const& val )
745 return bucket( val ).get( ptr, val );
748 /// Finds the key \p val and return the item found
750 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_get "get( guarded_ptr& ptr, Q const&)"
751 but \p pred is used for comparing the keys.
753 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
755 \p pred must imply the same element order as the comparator used for building the set.
757 template <typename Q, typename Less>
758 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
760 return bucket( val ).get_with( ptr, val, pred );
763 /// Clears the set (non-atomic)
765 The function unlink all items from the set.
766 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
767 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
768 <tt> empty() </tt> may return \p true but the set may contain item(s).
769 Therefore, \p clear may be used only for debugging purposes.
771 For each item the \p disposer is called after unlinking.
775 for ( size_t i = 0; i < bucket_count(); ++i )
776 m_Buckets[i].clear();
777 m_ItemCounter.reset();
781 /// Checks if the set is empty
783 Emptiness is checked by item counting: if item count is zero then the set is empty.
784 Thus, the correct item counting feature is an important part of Michael's set implementation.
791 /// Returns item count in the set
794 return m_ItemCounter;
797 /// Returns the size of hash table
799 Since MichaelHashSet cannot dynamically extend the hash table size,
800 the value returned is an constant depending on object initialization parameters;
801 see MichaelHashSet::MichaelHashSet for explanation.
803 size_t bucket_count() const
805 return m_nHashBitmask + 1;
809 }} // namespace cds::intrusive
811 #endif // ifndef __CDS_INTRUSIVE_MICHAEL_SET_H