3 #ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H
4 #define CDSLIB_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, \p MichaelList, \p 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 \p michael_set::traits for explanation.
30 Instead of defining \p Traits struct you can use option-based syntax with \p 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 append-only set
35 - <tt><cds/intrusive/michael_set.h></tt> for \p gc::HP, \p gc::DHP
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.
42 The hash functor \p Traits::hash 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_ );
66 First, you should define ordered list type to use in your hash set:
68 // For gc::HP-based MichaelList implementation
69 #include <cds/intrusive/michael_list_hp.h>
71 // cds::intrusive::MichaelHashSet declaration
72 #include <cds/intrusive/michael_set.h>
74 // Type of hash-set items
75 struct Foo: public cds::intrusive::michael_list::node< cds::gc::HP >
77 std::string key_ ; // key field
78 unsigned val_ ; // value field
79 // ... other value fields
82 // Declare comparator for the item
85 int operator()( const Foo& f1, const Foo& f2 ) const
87 return f1.key_.compare( f2.key_ );
91 // Declare bucket type for Michael's hash set
92 // The bucket type is any ordered list type like MichaelList, LazyList
93 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
94 typename cds::intrusive::michael_list::make_traits<
96 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
97 // item comparator option
98 ,cds::opt::compare< FooCmp >
103 Second, you should declare Michael's hash set container:
106 // Declare hash functor
107 // Note, the hash functor accepts parameter type Foo and std::string
109 size_t operator()( const Foo& f ) const
111 return cds::opt::v::hash<std::string>()( f.key_ );
113 size_t operator()( const std::string& f ) const
115 return cds::opt::v::hash<std::string>()( f );
119 // Michael's set typedef
120 typedef cds::intrusive::MichaelHashSet<
123 ,typename cds::intrusive::michael_set::make_traits<
124 cds::opt::hash< FooHash >
129 Now, you can use \p Foo_set in your application.
131 Like other intrusive containers, you may build several containers on single item structure:
133 #include <cds/intrusive/michael_list_hp.h>
134 #include <cds/intrusive/michael_list_dhp.h>
135 #include <cds/intrusive/michael_set.h>
141 // The first key is maintained by gc::HP, second key is maintained by gc::DHP garbage collectors
142 // (I don't know what is needed for, but it is correct)
144 : public cds::intrusive::michael_list::node< cds::gc::HP, tag_key1_idx >
145 , public cds::intrusive::michael_list::node< cds::gc::DHP, 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::DHP
174 typedef cds::intrusive::MichaelList< cds::gc::DHP, 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::DHP >, 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::traits
221 typedef GC gc; ///< Garbage collector
222 typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
223 typedef ordered_list bucket_type; ///< bucket type
224 typedef Traits traits; ///< Set traits
226 typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
227 typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
228 typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
230 /// Hash functor for \p value_type and all its derivatives that you use
231 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
232 typedef typename traits::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 traits::allocator > bucket_table_allocator;
240 typedef cds::intrusive::michael_set::implementation_tag implementation_tag;
244 item_counter m_ItemCounter; ///< Item counter
245 hash m_HashFunctor; ///< Hash functor
246 bucket_type * m_Buckets; ///< bucket table
250 const size_t m_nHashBitmask;
255 /// Calculates hash value of \p key
256 template <typename Q>
257 size_t hash_value( const Q& key ) const
259 return m_HashFunctor( key ) & m_nHashBitmask;
262 /// Returns the bucket (ordered list) for \p key
263 template <typename Q>
264 bucket_type& bucket( const Q& key )
266 return m_Buckets[ hash_value( key ) ];
273 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
274 - it has no post-increment operator
275 - it iterates items in unordered fashion
276 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
277 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
278 deleting operations it is no guarantee that you iterate all item in the set.
280 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
281 for debug purpose only.
283 typedef michael_set::details::iterator< bucket_type, false > iterator;
285 /// Const forward iterator
287 For iterator's features and requirements see \ref iterator
289 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
291 /// Returns a forward iterator addressing the first element in a set
293 For empty set \code begin() == end() \endcode
297 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
300 /// Returns an iterator that addresses the location succeeding the last element in a set
302 Do not use the value returned by <tt>end</tt> function to access any item.
303 The returned value can be used only to control reaching the end of the set.
304 For empty set \code begin() == end() \endcode
308 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
311 /// Returns a forward const iterator addressing the first element in a set
313 const_iterator begin() const
315 return get_const_begin();
317 const_iterator cbegin() const
319 return get_const_begin();
323 /// Returns an const iterator that addresses the location succeeding the last element in a set
325 const_iterator end() const
327 return get_const_end();
329 const_iterator cend() const
331 return get_const_end();
337 const_iterator get_const_begin() const
339 return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
341 const_iterator get_const_end() const
343 return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
348 /// Initializes hash set
349 /** @anchor cds_intrusive_MichaelHashSet_hp_ctor
350 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
351 At construction time you should pass estimated maximum item count and a load factor.
352 The load factor is average size of one bucket - a small number between 1 and 10.
353 The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
354 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
357 size_t nMaxItemCount, ///< estimation of max item count in the hash set
358 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
359 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
361 // GC and OrderedList::gc must be the same
362 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
364 // atomicity::empty_item_counter is not allowed as a item counter
365 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
366 "cds::atomicity::empty_item_counter is not allowed as a item counter");
368 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
371 /// Clears hash set object and destroys it
375 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
380 The function inserts \p val in the set if it does not contain
381 an item with key equal to \p val.
383 Returns \p true if \p val is placed into the set, \p false otherwise.
385 bool insert( value_type& val )
387 bool bRet = bucket( val ).insert( val );
395 This function is intended for derived non-intrusive containers.
397 The function allows to split creating of new item into two part:
398 - create item with key only
399 - insert new item into the set
400 - if inserting is success, calls \p f functor to initialize value-field of \p val.
402 The functor signature is:
404 void func( value_type& val );
406 where \p val is the item inserted.
408 The user-defined functor is called only if the inserting is success.
410 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
411 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
414 template <typename Func>
415 bool insert( value_type& val, Func f )
417 bool bRet = bucket( val ).insert( val, f );
423 /// Updates the element
425 The operation performs inserting or changing data with lock-free manner.
427 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
428 Otherwise, the functor \p func is called with item found.
429 The functor signature is:
432 void operator()( bool bNew, value_type& item, value_type& val );
436 - \p bNew - \p true if the item has been inserted, \p false otherwise
437 - \p item - item of the set
438 - \p val - argument \p val passed into the \p %update() function
439 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
440 refers to the same thing.
442 The functor may change non-key fields of the \p item.
444 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
445 \p second is \p true if new item has been added or \p false if the item with \p key
446 already is in the set.
448 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
449 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
452 template <typename Func>
453 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
455 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
461 template <typename Func>
462 CDS_DEPRECATED("ensure() is deprecated, use update()")
463 std::pair<bool, bool> ensure( value_type& val, Func func )
465 return update( val, func, true );
469 /// Unlinks the item \p val from the set
471 The function searches the item \p val in the set and unlink it
472 if it is found and is equal to \p val.
474 The function returns \p true if success and \p false otherwise.
476 bool unlink( value_type& val )
478 bool bRet = bucket( val ).unlink( val );
484 /// Deletes the item from the set
485 /** \anchor cds_intrusive_MichaelHashSet_hp_erase
486 The function searches an item with key equal to \p key in the set,
487 unlinks it, and returns \p true.
488 If the item with key equal to \p key is not found the function return \p false.
490 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
492 template <typename Q>
493 bool erase( Q const& key )
495 if ( bucket( key ).erase( key )) {
502 /// Deletes the item from the set using \p pred predicate for searching
504 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase "erase(Q const&)"
505 but \p pred is used for key comparing.
506 \p Less functor has the interface like \p std::less.
507 \p pred must imply the same element order as the comparator used for building the set.
509 template <typename Q, typename Less>
510 bool erase_with( Q const& key, Less pred )
512 if ( bucket( key ).erase_with( key, pred )) {
519 /// Deletes the item from the set
520 /** \anchor cds_intrusive_MichaelHashSet_hp_erase_func
521 The function searches an item with key equal to \p key in the set,
522 call \p f functor with item found, and unlinks it from the set.
523 The \ref disposer specified in \p OrderedList class template parameter is called
524 by garbage collector \p GC asynchronously.
526 The \p Func interface is
529 void operator()( value_type const& item );
533 If the item with key equal to \p key is not found the function return \p false.
535 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
537 template <typename Q, typename Func>
538 bool erase( const Q& key, Func f )
540 if ( bucket( key ).erase( key, f )) {
547 /// Deletes the item from the set using \p pred predicate for searching
549 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase_func "erase(Q const&, Func)"
550 but \p pred is used for key comparing.
551 \p Less functor has the interface like \p std::less.
552 \p pred must imply the same element order as the comparator used for building the set.
554 template <typename Q, typename Less, typename Func>
555 bool erase_with( const Q& key, Less pred, Func f )
557 if ( bucket( key ).erase_with( key, pred, f )) {
564 /// Extracts the item with specified \p key
565 /** \anchor cds_intrusive_MichaelHashSet_hp_extract
566 The function searches an item with key equal to \p key,
567 unlinks it from the set, and returns an guarded pointer to the item extracted.
568 If \p key is not found the function returns an empty guarded pointer.
570 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
572 The \p disposer specified in \p OrderedList class' template parameter is called automatically
573 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
574 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
578 typedef cds::intrusive::MichaelHashSet< your_template_args > michael_set;
582 michael_set::guarded_ptr gp( theSet.extract( 5 ));
587 // Destructor of gp releases internal HP guard
591 template <typename Q>
592 guarded_ptr extract( Q const& key )
594 guarded_ptr gp = bucket( key ).extract( key );
600 /// Extracts the item using compare functor \p pred
602 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_extract "extract(Q const&)"
603 but \p pred predicate is used for key comparing.
605 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
607 \p pred must imply the same element order as the comparator used for building the list.
609 template <typename Q, typename Less>
610 guarded_ptr extract_with( Q const& key, Less pred )
612 guarded_ptr gp = bucket( key ).extract_with( key, pred );
618 /// Finds the key \p key
619 /** \anchor cds_intrusive_MichaelHashSet_hp_find_func
620 The function searches the item with key equal to \p key and calls the functor \p f for item found.
621 The interface of \p Func functor is:
624 void operator()( value_type& item, Q& key );
627 where \p item is the item found, \p key is the <tt>find</tt> function argument.
629 The functor may change non-key fields of \p item. Note that the functor is only guarantee
630 that \p item cannot be disposed during functor is executing.
631 The functor does not serialize simultaneous access to the set \p item. If such access is
632 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
634 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
635 may modify both arguments.
637 Note the hash functor specified for class \p Traits template parameter
638 should accept a parameter of type \p Q that can be not the same as \p value_type.
640 The function returns \p true if \p key is found, \p false otherwise.
642 template <typename Q, typename Func>
643 bool find( Q& key, Func f )
645 return bucket( key ).find( key, f );
648 template <typename Q, typename Func>
649 bool find( Q const& key, Func f )
651 return bucket( key ).find( key, f );
655 /// Finds the key \p key using \p pred predicate for searching
657 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
658 but \p pred is used for key comparing.
659 \p Less functor has the interface like \p std::less.
660 \p pred must imply the same element order as the comparator used for building the set.
662 template <typename Q, typename Less, typename Func>
663 bool find_with( Q& key, Less pred, Func f )
665 return bucket( key ).find_with( key, pred, f );
668 template <typename Q, typename Less, typename Func>
669 bool find_with( Q const& key, Less pred, Func f )
671 return bucket( key ).find_with( key, pred, f );
675 /// Checks whether the set contains \p key
677 The function searches the item with key equal to \p key
678 and returns \p true if the key is found, and \p false otherwise.
680 Note the hash functor specified for class \p Traits template parameter
681 should accept a parameter of type \p Q that can be not the same as \p value_type.
683 template <typename Q>
684 bool contains( Q const& key )
686 return bucket( key ).contains( key );
689 template <typename Q>
690 CDS_DEPRECATED("use contains()")
691 bool find( Q const& key )
693 return contains( key );
697 /// Checks whether the set contains \p key using \p pred predicate for searching
699 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
700 \p Less functor has the interface like \p std::less.
701 \p Less must imply the same element order as the comparator used for building the set.
703 template <typename Q, typename Less>
704 bool contains( Q const& key, Less pred )
706 return bucket( key ).contains( key, pred );
709 template <typename Q, typename Less>
710 CDS_DEPRECATED("use contains()")
711 bool find_with( Q const& key, Less pred )
713 return contains( key, pred );
717 /// Finds the key \p key and return the item found
718 /** \anchor cds_intrusive_MichaelHashSet_hp_get
719 The function searches the item with key equal to \p key
720 and returns the guarded pointer to the item found.
721 If \p key is not found the function returns an empty \p guarded_ptr.
723 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
727 typedef cds::intrusive::MichaelHashSet< your_template_params > michael_set;
731 michael_set::guarded_ptr gp( theSet.get( 5 ));
732 if ( theSet.get( 5 )) {
736 // Destructor of guarded_ptr releases internal HP guard
740 Note the compare functor specified for \p OrderedList template parameter
741 should accept a parameter of type \p Q that can be not the same as \p value_type.
743 template <typename Q>
744 guarded_ptr get( Q const& key )
746 return bucket( key ).get( key );
749 /// Finds the key \p key and return the item found
751 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_get "get( Q const&)"
752 but \p pred is used for comparing the keys.
754 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
756 \p pred must imply the same element order as the comparator used for building the set.
758 template <typename Q, typename Less>
759 guarded_ptr get_with( Q const& key, Less pred )
761 return bucket( key ).get_with( key, pred );
764 /// Clears the set (non-atomic)
766 The function unlink all items from the set.
767 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
768 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
769 \p empty() may return \p true but the set may contain item(s).
770 Therefore, \p %clear() may be used only for debugging purposes.
772 For each item the \p disposer is called after unlinking.
776 for ( size_t i = 0; i < bucket_count(); ++i )
777 m_Buckets[i].clear();
778 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 \p %MichaelHashSet cannot dynamically extend the hash table size,
800 the value returned is an constant depending on object initialization parameters,
801 see \p MichaelHashSet::MichaelHashSet.
803 size_t bucket_count() const
805 return m_nHashBitmask + 1;
809 }} // namespace cds::intrusive
811 #endif // ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H