3 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_H
4 #define CDSLIB_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 \p GC used for \p OrderedList
27 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList.
28 The ordered list implementation specifies the type \p T to be stored in the hash-set,
29 the comparing functor for the type \p T and other features specific for the ordered list.
30 - \p Traits - set traits, default is \p michael_set::traits.
31 Instead of defining \p Traits struct you may use option-based syntax with \p michael_set::make_traits metafunction.
33 There are the specializations:
34 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_set_rcu.h</tt>,
35 see \ref cds_nonintrusive_MichaelHashSet_rcu "MichaelHashSet<RCU>".
36 - for \ref cds::gc::nogc declared in <tt>cds/container/michael_set_nogc.h</tt>,
37 see \ref cds_nonintrusive_MichaelHashSet_nogc "MichaelHashSet<gc::nogc>".
39 \anchor cds_nonintrusive_MichaelHashSet_hash_functor
42 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from node type \p value_type.
43 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
44 are equal the hash values of these keys must be equal too.
46 The hash functor \p Traits::hash should accept parameters of both type:
50 std::string key_ ; // key field
56 size_t operator()( const std::string& s ) const
58 return std::hash( s );
61 size_t operator()( const Foo& f ) const
63 return (*this)( f.key_ );
70 The class supports a forward iterator (\ref iterator and \ref const_iterator).
71 The iteration is unordered.
72 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
73 so, the element cannot be reclaimed while the iterator object is alive.
74 However, passing an iterator object between threads is dangerous.
76 @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
77 all elements in the set: any concurrent deletion can exclude the element
78 pointed by the iterator from the set, and your iteration can be terminated
79 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
81 Remember, each iterator object requires an additional hazard pointer, that may be
82 a limited resource for \p GC like \p gc::HP (for \p gc::DHP the total count of
85 The iterator class supports the following minimalistic interface:
92 iterator( iterator const& s);
94 value_type * operator ->() const;
95 value_type& operator *() const;
98 iterator& operator ++();
101 iterator& operator = (const iterator& src);
103 bool operator ==(iterator const& i ) const;
104 bool operator !=(iterator const& i ) const;
107 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
111 Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
114 int nKey ; // key field
115 int nVal ; // value field
119 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
120 that will be used as a bucket for the set. We will use \p gc::DHP reclamation schema and
121 \p MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
124 #include <cds/container/michael_list_dhp.h>
125 #include <cds/container/michael_set.h>
127 namespace cc = cds::container;
131 int operator ()(Foo const& v1, Foo const& v2 ) const
133 if ( std::less( v1.nKey, v2.nKey ))
135 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
140 typedef cc::MichaelList< cds::gc::DHP, Foo,
141 typename cc::michael_list::make_traits<
142 cc::opt::compare< Foo_cmp > // item comparator option
146 // Hash functor for Foo
148 size_t operator ()( int i ) const
150 return std::hash( i );
152 size_t operator()( Foo const& i ) const
154 return std::hash( i.nKey );
159 // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
160 typedef cc::MichaelHashSet< cds::gc::DHP, bucket_list,
161 cc::michael_set::make_traits<
162 cc::opt::hash< foo_hash >
173 #ifdef CDS_DOXYGEN_INVOKED
174 class Traits = michael_set::traits
182 typedef GC gc; ///< Garbage collector
183 typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
184 typedef Traits traits; ///< Set traits
186 typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list
187 typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor
189 /// Hash functor for \ref value_type and all its derivatives that you use
190 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
191 typedef typename traits::item_counter item_counter; ///< Item counter type
193 /// Bucket table allocator
194 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
196 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
199 item_counter m_ItemCounter; ///< Item counter
200 hash m_HashFunctor; ///< Hash functor
201 bucket_type * m_Buckets; ///< bucket table
205 const size_t m_nHashBitmask;
210 /// Calculates hash value of \p key
211 template <typename Q>
212 size_t hash_value( Q const& key ) const
214 return m_HashFunctor( key ) & m_nHashBitmask;
217 /// Returns the bucket (ordered list) for \p key
218 template <typename Q>
219 bucket_type& bucket( Q const& key )
221 return m_Buckets[ hash_value( key ) ];
227 typedef michael_set::details::iterator< bucket_type, false > iterator;
229 /// Const forward iterator
230 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
232 /// Returns a forward iterator addressing the first element in a set
234 For empty set \code begin() == end() \endcode
238 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
241 /// Returns an iterator that addresses the location succeeding the last element in a set
243 Do not use the value returned by <tt>end</tt> function to access any item.
244 The returned value can be used only to control reaching the end of the set.
245 For empty set \code begin() == end() \endcode
249 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
252 /// Returns a forward const iterator addressing the first element in a set
254 const_iterator begin() const
256 return get_const_begin();
258 const_iterator cbegin() const
260 return get_const_begin();
264 /// Returns an const iterator that addresses the location succeeding the last element in a set
266 const_iterator end() const
268 return get_const_end();
270 const_iterator cend() const
272 return get_const_end();
278 const_iterator get_const_begin() const
280 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
282 const_iterator get_const_end() const
284 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
289 /// Initialize hash set
290 /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor
291 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
292 when you create an object.
293 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
294 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
296 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
299 size_t nMaxItemCount, ///< estimation of max item count in the hash set
300 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
301 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
303 // GC and OrderedList::gc must be the same
304 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
306 // atomicity::empty_item_counter is not allowed as a item counter
307 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
308 "cds::atomicity::empty_item_counter is not allowed as a item counter");
310 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
313 /// Clears hash set and destroys it
317 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
322 The function creates a node with copy of \p val value
323 and then inserts the node created into the set.
325 The type \p Q should contain as minimum the complete key for the node.
326 The object of \ref value_type should be constructible from a value of type \p Q.
327 In trivial case, \p Q is equal to \ref value_type.
329 Returns \p true if \p val is inserted into the set, \p false otherwise.
331 template <typename Q>
332 bool insert( Q const& val )
334 const bool bRet = bucket( val ).insert( val );
342 The function allows to split creating of new item into two part:
343 - create item with key only
344 - insert new item into the set
345 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
347 The functor signature is:
349 void func( value_type& val );
351 where \p val is the item inserted.
352 The user-defined functor is called only if the inserting is success.
354 @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
355 @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
358 template <typename Q, typename Func>
359 bool insert( Q const& val, Func f )
361 const bool bRet = bucket( val ).insert( val, f );
367 /// Updates the element
369 The operation performs inserting or changing data with lock-free manner.
371 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
372 Otherwise, the functor \p func is called with item found.
373 The functor signature is:
376 void operator()( bool bNew, value_type& item, Q const& val );
380 - \p bNew - \p true if the item has been inserted, \p false otherwise
381 - \p item - item of the set
382 - \p val - argument \p val passed into the \p %update() function
384 The functor may change non-key fields of the \p item.
386 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
387 \p second is \p true if new item has been added or \p false if the item with \p key
388 already is in the set.
390 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
391 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
394 template <typename Q, typename Func>
395 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowUpdate = true )
397 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowUpdate );
403 template <typename Q, typename Func>
404 CDS_DEPRECATED("ensure() is deprecated, use update()")
405 std::pair<bool, bool> ensure( const Q& val, Func func )
407 return update( val, func, true );
411 /// Inserts data of type \p value_type constructed from \p args
413 Returns \p true if inserting successful, \p false otherwise.
415 template <typename... Args>
416 bool emplace( Args&&... args )
418 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
424 /// Deletes \p key from the set
425 /** \anchor cds_nonintrusive_MichaelSet_erase_val
427 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
428 template parameter \p Q defines the key type searching in the list.
429 The set item comparator should be able to compare the type \p value_type
432 Return \p true if key is found and deleted, \p false otherwise
434 template <typename Q>
435 bool erase( Q const& key )
437 const bool bRet = bucket( key ).erase( key );
443 /// Deletes the item from the set using \p pred predicate for searching
445 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
446 but \p pred is used for key comparing.
447 \p Less functor has the interface like \p std::less.
448 \p Less must imply the same element order as the comparator used for building the set.
450 template <typename Q, typename Less>
451 bool erase_with( Q const& key, Less pred )
453 const bool bRet = bucket( key ).erase_with( key, pred );
459 /// Deletes \p key from the set
460 /** \anchor cds_nonintrusive_MichaelSet_erase_func
462 The function searches an item with key \p key, calls \p f functor
463 and deletes the item. If \p key is not found, the functor is not called.
465 The functor \p Func interface:
468 void operator()(value_type& item);
471 where \p item - the item found.
473 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
474 template parameter \p Q defines the key type searching in the list.
475 The list item comparator should be able to compare the type \p T of list item
478 Return \p true if key is found and deleted, \p false otherwise
480 template <typename Q, typename Func>
481 bool erase( Q const& key, Func f )
483 const bool bRet = bucket( key ).erase( key, f );
489 /// Deletes the item from the set using \p pred predicate for searching
491 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
492 but \p pred is used for key comparing.
493 \p Less functor has the interface like \p std::less.
494 \p Less must imply the same element order as the comparator used for building the set.
496 template <typename Q, typename Less, typename Func>
497 bool erase_with( Q const& key, Less pred, Func f )
499 const bool bRet = bucket( key ).erase_with( key, pred, f );
505 /// Extracts the item with specified \p key
506 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
507 The function searches an item with key equal to \p key,
508 unlinks it from the set, and returns it as \p guarded_ptr.
509 If \p key is not found the function returns an empty guadd pointer.
511 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
513 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
514 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
518 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
522 michael_set::guarded_ptr gp( theSet.extract( 5 ));
527 // Destructor of gp releases internal HP guard
531 template <typename Q>
532 guarded_ptr extract( Q const& key )
534 guarded_ptr gp( bucket( key ).extract( key ));
540 /// Extracts the item using compare functor \p pred
542 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)"
543 but \p pred predicate is used for key comparing.
545 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
547 \p pred must imply the same element order as the comparator used for building the set.
549 template <typename Q, typename Less>
550 guarded_ptr extract_with( Q const& key, Less pred )
552 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
558 /// Finds the key \p key
559 /** \anchor cds_nonintrusive_MichaelSet_find_func
561 The function searches the item with key equal to \p key and calls the functor \p f for item found.
562 The interface of \p Func functor is:
565 void operator()( value_type& item, Q& key );
568 where \p item is the item found, \p key is the <tt>find</tt> function argument.
570 The functor may change non-key fields of \p item. Note that the functor is only guarantee
571 that \p item cannot be disposed during functor is executing.
572 The functor does not serialize simultaneous access to the set's \p item. If such access is
573 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
575 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
576 can modify both arguments.
578 Note the hash functor specified for class \p Traits template parameter
579 should accept a parameter of type \p Q that may be not the same as \p value_type.
581 The function returns \p true if \p key is found, \p false otherwise.
583 template <typename Q, typename Func>
584 bool find( Q& key, Func f )
586 return bucket( key ).find( key, f );
589 template <typename Q, typename Func>
590 bool find( Q const& key, Func f )
592 return bucket( key ).find( key, f );
596 /// Finds the key \p key using \p pred predicate for searching
598 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
599 but \p pred is used for key comparing.
600 \p Less functor has the interface like \p std::less.
601 \p Less must imply the same element order as the comparator used for building the set.
603 template <typename Q, typename Less, typename Func>
604 bool find_with( Q& key, Less pred, Func f )
606 return bucket( key ).find_with( key, pred, f );
609 template <typename Q, typename Less, typename Func>
610 bool find_with( Q const& key, Less pred, Func f )
612 return bucket( key ).find_with( key, pred, f );
616 /// Checks whether the set contains \p key
618 The function searches the item with key equal to \p key
619 and returns \p true if the key is found, and \p false otherwise.
621 Note the hash functor specified for class \p Traits template parameter
622 should accept a parameter of type \p Q that can be not the same as \p value_type.
624 template <typename Q>
625 bool contains( Q const& key )
627 return bucket( key ).contains( key );
630 template <typename Q>
631 CDS_DEPRECATED("use contains()")
632 bool find( Q const& key )
634 return contains( key );
638 /// Checks whether the set contains \p key using \p pred predicate for searching
640 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
641 \p Less functor has the interface like \p std::less.
642 \p Less must imply the same element order as the comparator used for building the set.
644 template <typename Q, typename Less>
645 bool contains( Q const& key, Less pred )
647 return bucket( key ).contains( key, pred );
650 template <typename Q, typename Less>
651 CDS_DEPRECATED("use contains()")
652 bool find_with( Q const& key, Less pred )
654 return contains( key, pred );
658 /// Finds the key \p key and return the item found
659 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
660 The function searches the item with key equal to \p key
661 and returns the guarded pointer to the item found.
662 If \p key is not found the functin returns an empty guarded pointer.
664 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
668 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
672 michael_set::guarded_ptr gp( theSet.get( 5 ));
677 // Destructor of guarded_ptr releases internal HP guard
681 Note the compare functor specified for \p OrderedList template parameter
682 should accept a parameter of type \p Q that can be not the same as \p value_type.
684 template <typename Q>
685 guarded_ptr get( Q const& key )
687 return bucket( key ).get( key );
690 /// Finds the key \p key and return the item found
692 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
693 but \p pred is used for comparing the keys.
695 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
697 \p pred must imply the same element order as the comparator used for building the set.
699 template <typename Q, typename Less>
700 guarded_ptr get_with( Q const& key, Less pred )
702 return bucket( key ).get_with( key, pred );
705 /// Clears the set (non-atomic)
707 The function erases all items from the set.
709 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
710 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
711 <tt> empty() </tt> may return \p true but the set may contain item(s).
712 Therefore, \p clear may be used only for debugging purposes.
716 for ( size_t i = 0; i < bucket_count(); ++i )
717 m_Buckets[i].clear();
718 m_ItemCounter.reset();
721 /// Checks if the set is empty
723 Emptiness is checked by item counting: if item count is zero then the set is empty.
724 Thus, the correct item counting feature is an important part of Michael's set implementation.
731 /// Returns item count in the set
734 return m_ItemCounter;
737 /// Returns the size of hash table
739 Since MichaelHashSet cannot dynamically extend the hash table size,
740 the value returned is an constant depending on object initialization parameters;
741 see MichaelHashSet::MichaelHashSet for explanation.
743 size_t bucket_count() const
745 return m_nHashBitmask + 1;
749 }} // namespace cds::container
751 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H