2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_H
32 #define CDSLIB_CONTAINER_MICHAEL_SET_H
34 #include <cds/container/details/michael_set_base.h>
35 #include <cds/details/allocator.h>
37 namespace cds { namespace container {
39 /// Michael's hash set
40 /** @ingroup cds_nonintrusive_set
41 \anchor cds_nonintrusive_MichaelHashSet_hp
44 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
46 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
47 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
48 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
49 However, each bucket may contain unbounded number of items.
51 Template parameters are:
52 - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
53 from the \p libcds library.
54 Note the \p GC must be the same as the \p GC used for \p OrderedList
55 - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList.
56 The ordered list implementation specifies the type \p T to be stored in the hash-set,
57 the comparing functor for the type \p T and other features specific for the ordered list.
58 - \p Traits - set traits, default is \p michael_set::traits.
59 Instead of defining \p Traits struct you may use option-based syntax with \p michael_set::make_traits metafunction.
61 There are the specializations:
62 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_set_rcu.h</tt>,
63 see \ref cds_nonintrusive_MichaelHashSet_rcu "MichaelHashSet<RCU>".
64 - for \ref cds::gc::nogc declared in <tt>cds/container/michael_set_nogc.h</tt>,
65 see \ref cds_nonintrusive_MichaelHashSet_nogc "MichaelHashSet<gc::nogc>".
67 \anchor cds_nonintrusive_MichaelHashSet_hash_functor
70 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from node type \p value_type.
71 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
72 are equal the hash values of these keys must be equal too.
74 The hash functor \p Traits::hash should accept parameters of both type:
78 std::string key_ ; // key field
84 size_t operator()( const std::string& s ) const
86 return std::hash( s );
89 size_t operator()( const Foo& f ) const
91 return (*this)( f.key_ );
98 The class supports a forward iterator (\ref iterator and \ref const_iterator).
99 The iteration is unordered.
100 The iterator object is thread-safe: the element pointed by the iterator object is guarded,
101 so, the element cannot be reclaimed while the iterator object is alive.
102 However, passing an iterator object between threads is dangerous.
104 @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
105 all elements in the set: any concurrent deletion can exclude the element
106 pointed by the iterator from the set, and your iteration can be terminated
107 before end of the set. Therefore, such iteration is more suitable for debugging purpose only
109 Remember, each iterator object requires an additional hazard pointer, that may be
110 a limited resource for \p GC like \p gc::HP (for \p gc::DHP the total count of
111 guards is unlimited).
113 The iterator class supports the following minimalistic interface:
120 iterator( iterator const& s);
122 value_type * operator ->() const;
123 value_type& operator *() const;
126 iterator& operator ++();
129 iterator& operator = (const iterator& src);
131 bool operator ==(iterator const& i ) const;
132 bool operator !=(iterator const& i ) const;
135 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
139 Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
142 int nKey ; // key field
143 int nVal ; // value field
147 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
148 that will be used as a bucket for the set. We will use \p gc::DHP reclamation schema and
149 \p MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
152 #include <cds/container/michael_list_dhp.h>
153 #include <cds/container/michael_set.h>
155 namespace cc = cds::container;
159 int operator ()(Foo const& v1, Foo const& v2 ) const
161 if ( std::less( v1.nKey, v2.nKey ))
163 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
168 typedef cc::MichaelList< cds::gc::DHP, Foo,
169 typename cc::michael_list::make_traits<
170 cc::opt::compare< Foo_cmp > // item comparator option
174 // Hash functor for Foo
176 size_t operator ()( int i ) const
178 return std::hash( i );
180 size_t operator()( Foo const& i ) const
182 return std::hash( i.nKey );
187 // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
188 typedef cc::MichaelHashSet< cds::gc::DHP, bucket_list,
189 cc::michael_set::make_traits<
190 cc::opt::hash< foo_hash >
201 #ifdef CDS_DOXYGEN_INVOKED
202 class Traits = michael_set::traits
210 typedef GC gc; ///< Garbage collector
211 typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
212 typedef Traits traits; ///< Set traits
214 typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list
215 typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor
217 /// Hash functor for \ref value_type and all its derivatives that you use
218 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
219 typedef typename traits::item_counter item_counter; ///< Item counter type
221 /// Bucket table allocator
222 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
224 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
227 item_counter m_ItemCounter; ///< Item counter
228 hash m_HashFunctor; ///< Hash functor
229 bucket_type * m_Buckets; ///< bucket table
233 const size_t m_nHashBitmask;
238 /// Calculates hash value of \p key
239 template <typename Q>
240 size_t hash_value( Q const& key ) const
242 return m_HashFunctor( key ) & m_nHashBitmask;
245 /// Returns the bucket (ordered list) for \p key
246 template <typename Q>
247 bucket_type& bucket( Q const& key )
249 return m_Buckets[ hash_value( key ) ];
255 typedef michael_set::details::iterator< bucket_type, false > iterator;
257 /// Const forward iterator
258 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
260 /// Returns a forward iterator addressing the first element in a set
262 For empty set \code begin() == end() \endcode
266 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
269 /// Returns an iterator that addresses the location succeeding the last element in a set
271 Do not use the value returned by <tt>end</tt> function to access any item.
272 The returned value can be used only to control reaching the end of the set.
273 For empty set \code begin() == end() \endcode
277 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
280 /// Returns a forward const iterator addressing the first element in a set
282 const_iterator begin() const
284 return get_const_begin();
286 const_iterator cbegin() const
288 return get_const_begin();
292 /// Returns an const iterator that addresses the location succeeding the last element in a set
294 const_iterator end() const
296 return get_const_end();
298 const_iterator cend() const
300 return get_const_end();
306 const_iterator get_const_begin() const
308 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
310 const_iterator get_const_end() const
312 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
317 /// Initialize hash set
318 /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor
319 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
320 when you create an object.
321 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
322 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
324 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
327 size_t nMaxItemCount, ///< estimation of max item count in the hash set
328 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
329 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
331 // GC and OrderedList::gc must be the same
332 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
334 // atomicity::empty_item_counter is not allowed as a item counter
335 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
336 "cds::atomicity::empty_item_counter is not allowed as a item counter");
338 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
341 /// Clears hash set and destroys it
345 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
350 The function creates a node with copy of \p val value
351 and then inserts the node created into the set.
353 The type \p Q should contain as minimum the complete key for the node.
354 The object of \ref value_type should be constructible from a value of type \p Q.
355 In trivial case, \p Q is equal to \ref value_type.
357 Returns \p true if \p val is inserted into the set, \p false otherwise.
359 template <typename Q>
360 bool insert( Q const& val )
362 const bool bRet = bucket( val ).insert( val );
370 The function allows to split creating of new item into two part:
371 - create item with key only
372 - insert new item into the set
373 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
375 The functor signature is:
377 void func( value_type& val );
379 where \p val is the item inserted.
380 The user-defined functor is called only if the inserting is success.
382 @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
383 @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
386 template <typename Q, typename Func>
387 bool insert( Q const& val, Func f )
389 const bool bRet = bucket( val ).insert( val, f );
395 /// Updates the element
397 The operation performs inserting or changing data with lock-free manner.
399 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
400 Otherwise, the functor \p func is called with item found.
401 The functor signature is:
404 void operator()( bool bNew, value_type& item, Q const& val );
408 - \p bNew - \p true if the item has been inserted, \p false otherwise
409 - \p item - item of the set
410 - \p val - argument \p val passed into the \p %update() function
412 The functor may change non-key fields of the \p item.
414 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
415 \p second is \p true if new item has been added or \p false if the item with \p key
416 already is in the set.
418 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
419 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
422 template <typename Q, typename Func>
423 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowUpdate = true )
425 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowUpdate );
431 template <typename Q, typename Func>
432 CDS_DEPRECATED("ensure() is deprecated, use update()")
433 std::pair<bool, bool> ensure( const Q& val, Func func )
435 return update( val, func, true );
439 /// Inserts data of type \p value_type constructed from \p args
441 Returns \p true if inserting successful, \p false otherwise.
443 template <typename... Args>
444 bool emplace( Args&&... args )
446 bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
452 /// Deletes \p key from the set
453 /** \anchor cds_nonintrusive_MichaelSet_erase_val
455 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
456 template parameter \p Q defines the key type searching in the list.
457 The set item comparator should be able to compare the type \p value_type
460 Return \p true if key is found and deleted, \p false otherwise
462 template <typename Q>
463 bool erase( Q const& key )
465 const bool bRet = bucket( key ).erase( key );
471 /// Deletes the item from the set using \p pred predicate for searching
473 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
474 but \p pred is used for key comparing.
475 \p Less functor has the interface like \p std::less.
476 \p Less must imply the same element order as the comparator used for building the set.
478 template <typename Q, typename Less>
479 bool erase_with( Q const& key, Less pred )
481 const bool bRet = bucket( key ).erase_with( key, pred );
487 /// Deletes \p key from the set
488 /** \anchor cds_nonintrusive_MichaelSet_erase_func
490 The function searches an item with key \p key, calls \p f functor
491 and deletes the item. If \p key is not found, the functor is not called.
493 The functor \p Func interface:
496 void operator()(value_type& item);
499 where \p item - the item found.
501 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
502 template parameter \p Q defines the key type searching in the list.
503 The list item comparator should be able to compare the type \p T of list item
506 Return \p true if key is found and deleted, \p false otherwise
508 template <typename Q, typename Func>
509 bool erase( Q const& key, Func f )
511 const bool bRet = bucket( key ).erase( key, f );
517 /// Deletes the item from the set using \p pred predicate for searching
519 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
520 but \p pred is used for key comparing.
521 \p Less functor has the interface like \p std::less.
522 \p Less must imply the same element order as the comparator used for building the set.
524 template <typename Q, typename Less, typename Func>
525 bool erase_with( Q const& key, Less pred, Func f )
527 const bool bRet = bucket( key ).erase_with( key, pred, f );
533 /// Extracts the item with specified \p key
534 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
535 The function searches an item with key equal to \p key,
536 unlinks it from the set, and returns it as \p guarded_ptr.
537 If \p key is not found the function returns an empty guadd pointer.
539 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
541 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
542 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
546 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
550 michael_set::guarded_ptr gp( theSet.extract( 5 ));
555 // Destructor of gp releases internal HP guard
559 template <typename Q>
560 guarded_ptr extract( Q const& key )
562 guarded_ptr gp( bucket( key ).extract( key ));
568 /// Extracts the item using compare functor \p pred
570 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)"
571 but \p pred predicate is used for key comparing.
573 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
575 \p pred must imply the same element order as the comparator used for building the set.
577 template <typename Q, typename Less>
578 guarded_ptr extract_with( Q const& key, Less pred )
580 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
586 /// Finds the key \p key
587 /** \anchor cds_nonintrusive_MichaelSet_find_func
589 The function searches the item with key equal to \p key and calls the functor \p f for item found.
590 The interface of \p Func functor is:
593 void operator()( value_type& item, Q& key );
596 where \p item is the item found, \p key is the <tt>find</tt> function argument.
598 The functor may change non-key fields of \p item. Note that the functor is only guarantee
599 that \p item cannot be disposed during functor is executing.
600 The functor does not serialize simultaneous access to the set's \p item. If such access is
601 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
603 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
604 can modify both arguments.
606 Note the hash functor specified for class \p Traits template parameter
607 should accept a parameter of type \p Q that may be not the same as \p value_type.
609 The function returns \p true if \p key is found, \p false otherwise.
611 template <typename Q, typename Func>
612 bool find( Q& key, Func f )
614 return bucket( key ).find( key, f );
617 template <typename Q, typename Func>
618 bool find( Q const& key, Func f )
620 return bucket( key ).find( key, f );
624 /// Finds the key \p key using \p pred predicate for searching
626 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
627 but \p pred is used for key comparing.
628 \p Less functor has the interface like \p std::less.
629 \p Less must imply the same element order as the comparator used for building the set.
631 template <typename Q, typename Less, typename Func>
632 bool find_with( Q& key, Less pred, Func f )
634 return bucket( key ).find_with( key, pred, f );
637 template <typename Q, typename Less, typename Func>
638 bool find_with( Q const& key, Less pred, Func f )
640 return bucket( key ).find_with( key, pred, f );
644 /// Checks whether the set contains \p key
647 The function searches the item with key equal to \p key
648 and returns \p true if the key is found, and \p false otherwise.
650 Note the hash functor specified for class \p Traits template parameter
651 should accept a parameter of type \p Q that can be not the same as \p value_type.
653 template <typename Q>
654 bool contains( Q const& key )
656 return bucket( key ).contains( key );
659 template <typename Q>
660 CDS_DEPRECATED("use contains()")
661 bool find( Q const& key )
663 return contains( key );
667 /// Checks whether the set contains \p key using \p pred predicate for searching
669 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
670 \p Less functor has the interface like \p std::less.
671 \p Less must imply the same element order as the comparator used for building the set.
673 template <typename Q, typename Less>
674 bool contains( Q const& key, Less pred )
676 return bucket( key ).contains( key, pred );
679 template <typename Q, typename Less>
680 CDS_DEPRECATED("use contains()")
681 bool find_with( Q const& key, Less pred )
683 return contains( key, pred );
687 /// Finds the key \p key and return the item found
688 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
689 The function searches the item with key equal to \p key
690 and returns the guarded pointer to the item found.
691 If \p key is not found the functin returns an empty guarded pointer.
693 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
697 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
701 michael_set::guarded_ptr gp( theSet.get( 5 ));
706 // Destructor of guarded_ptr releases internal HP guard
710 Note the compare functor specified for \p OrderedList template parameter
711 should accept a parameter of type \p Q that can be not the same as \p value_type.
713 template <typename Q>
714 guarded_ptr get( Q const& key )
716 return bucket( key ).get( key );
719 /// Finds the key \p key and return the item found
721 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
722 but \p pred is used for comparing the keys.
724 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
726 \p pred must imply the same element order as the comparator used for building the set.
728 template <typename Q, typename Less>
729 guarded_ptr get_with( Q const& key, Less pred )
731 return bucket( key ).get_with( key, pred );
734 /// Clears the set (non-atomic)
736 The function erases all items from the set.
738 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
739 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
740 <tt> empty() </tt> may return \p true but the set may contain item(s).
741 Therefore, \p clear may be used only for debugging purposes.
745 for ( size_t i = 0; i < bucket_count(); ++i )
746 m_Buckets[i].clear();
747 m_ItemCounter.reset();
750 /// Checks if the set is empty
752 Emptiness is checked by item counting: if item count is zero then the set is empty.
753 Thus, the correct item counting feature is an important part of Michael's set implementation.
760 /// Returns item count in the set
763 return m_ItemCounter;
766 /// Returns the size of hash table
768 Since MichaelHashSet cannot dynamically extend the hash table size,
769 the value returned is an constant depending on object initialization parameters;
770 see MichaelHashSet::MichaelHashSet for explanation.
772 size_t bucket_count() const
774 return m_nHashBitmask + 1;
778 }} // namespace cds::container
780 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H