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 Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
101 int nKey ; // key field
102 int nVal ; // value field
106 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
107 that will be used as a bucket for the set. We will use \p gc::DHP reclamation schema and
108 \p MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
111 #include <cds/container/michael_list_dhp.h>
112 #include <cds/container/michael_set.h>
114 namespace cc = cds::container;
118 int operator ()(Foo const& v1, Foo const& v2 ) const
120 if ( std::less( v1.nKey, v2.nKey ))
122 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
127 typedef cc::MichaelList< cds::gc::DHP, Foo,
128 typename cc::michael_list::make_traits<
129 cc::opt::compare< Foo_cmp > // item comparator option
133 // Hash functor for Foo
135 size_t operator ()( int i ) const
137 return std::hash( i );
139 size_t operator()( Foo const& i ) const
141 return std::hash( i.nKey );
146 // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
147 typedef cc::MichaelHashSet< cds::gc::DHP, bucket_list,
148 cc::michael_set::make_traits<
149 cc::opt::hash< foo_hash >
160 #ifdef CDS_DOXYGEN_INVOKED
161 class Traits = michael_set::traits
169 typedef GC gc; ///< Garbage collector
170 typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
171 typedef Traits traits; ///< Set traits
173 typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list
174 typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor
176 /// Hash functor for \ref value_type and all its derivatives that you use
177 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
178 typedef typename traits::item_counter item_counter; ///< Item counter type
180 typedef typename bucket_type::guarded_ptr guarded_ptr; ///< Guarded pointer
181 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = bucket_type::c_nHazardPtrCount; ///< Count of hazard pointer required
185 class internal_bucket_type: public bucket_type
187 typedef bucket_type base_class;
189 using base_class::node_type;
190 using base_class::alloc_node;
191 using base_class::insert_node;
192 using base_class::node_to_value;
195 /// Bucket table allocator
196 typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator;
201 item_counter m_ItemCounter; ///< Item counter
202 hash m_HashFunctor; ///< Hash functor
203 internal_bucket_type * m_Buckets; ///< bucket table
208 const size_t m_nHashBitmask;
213 /// Calculates hash value of \p key
214 template <typename Q>
215 size_t hash_value( Q const& key ) const
217 return m_HashFunctor( key ) & m_nHashBitmask;
220 /// Returns the bucket (ordered list) for \p key
221 template <typename Q>
222 internal_bucket_type& bucket( Q const& key )
224 return m_Buckets[ hash_value( key ) ];
229 ///@name Forward iterators (only for debugging purpose)
233 The forward iterator for Michael's set has some features:
234 - it has no post-increment operator
235 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
236 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
237 may be thrown if the limit of guard count per thread is exceeded.
238 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
239 - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
240 deleting operations there is no guarantee that you iterate all item in the set.
241 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
243 @warning Use this iterator on the concurrent container for debugging purpose only.
245 The iterator interface:
249 // Default constructor
253 iterator( iterator const& src );
255 // Dereference operator
256 value_type * operator ->() const;
258 // Dereference operator
259 value_type& operator *() const;
261 // Preincrement operator
262 iterator& operator ++();
264 // Assignment operator
265 iterator& operator = (iterator const& src);
267 // Equality operators
268 bool operator ==(iterator const& i ) const;
269 bool operator !=(iterator const& i ) const;
275 typedef michael_set::details::iterator< bucket_type, false > iterator;
277 /// Const forward iterator
278 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
280 /// Returns a forward iterator addressing the first element in a set
282 For empty set \code begin() == end() \endcode
286 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
289 /// Returns an iterator that addresses the location succeeding the last element in a set
291 Do not use the value returned by <tt>end</tt> function to access any item.
292 The returned value can be used only to control reaching the end of the set.
293 For empty set \code begin() == end() \endcode
297 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
300 /// Returns a forward const iterator addressing the first element in a set
301 const_iterator begin() const
303 return get_const_begin();
306 /// Returns a forward const iterator addressing the first element in a set
307 const_iterator cbegin() const
309 return get_const_begin();
312 /// Returns an const iterator that addresses the location succeeding the last element in a set
313 const_iterator end() const
315 return get_const_end();
318 /// Returns an const iterator that addresses the location succeeding the last element in a set
319 const_iterator cend() const
321 return get_const_end();
327 const_iterator get_const_begin() const
329 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
331 const_iterator get_const_end() const
333 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
338 /// Initialize hash set
339 /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor
340 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
341 when you create an object.
342 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
343 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
345 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
348 size_t nMaxItemCount, ///< estimation of max item count in the hash set
349 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
350 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
352 // GC and OrderedList::gc must be the same
353 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
355 // atomicity::empty_item_counter is not allowed as a item counter
356 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
357 "cds::atomicity::empty_item_counter is not allowed as a item counter");
359 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
362 /// Clears hash set and destroys it
366 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
371 The function creates a node with copy of \p val value
372 and then inserts the node created into the set.
374 The type \p Q should contain as minimum the complete key for the node.
375 The object of \ref value_type should be constructible from a value of type \p Q.
376 In trivial case, \p Q is equal to \ref value_type.
378 Returns \p true if \p val is inserted into the set, \p false otherwise.
380 template <typename Q>
381 bool insert( Q const& val )
383 const bool bRet = bucket( val ).insert( val );
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-fields of \p val.
396 The functor signature is:
398 void func( value_type& val );
400 where \p val is the item inserted.
401 The user-defined functor is called only if the inserting is success.
403 @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
404 @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
407 template <typename Q, typename Func>
408 bool insert( Q const& val, Func f )
410 const bool bRet = bucket( val ).insert( val, f );
416 /// Updates the element
418 The operation performs inserting or changing data with lock-free manner.
420 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
421 Otherwise, the functor \p func is called with item found.
422 The functor signature is:
425 void operator()( bool bNew, value_type& item, Q const& val );
429 - \p bNew - \p true if the item has been inserted, \p false otherwise
430 - \p item - item of the set
431 - \p val - argument \p val passed into the \p %update() function
433 The functor may change non-key fields of the \p item.
435 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
436 \p second is \p true if new item has been added or \p false if the item with \p key
437 already is in the set.
439 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
440 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
443 template <typename Q, typename Func>
444 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowUpdate = true )
446 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowUpdate );
452 template <typename Q, typename Func>
453 CDS_DEPRECATED("ensure() is deprecated, use update()")
454 std::pair<bool, bool> ensure( const Q& val, Func func )
456 return update( val, func, true );
460 /// Inserts data of type \p value_type constructed from \p args
462 Returns \p true if inserting successful, \p false otherwise.
464 template <typename... Args>
465 bool emplace( Args&&... args )
467 typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward<Args>( args )... );
468 bool bRet = bucket( internal_bucket_type::node_to_value( *pNode )).insert_node( pNode );
474 /// Deletes \p key from the set
475 /** \anchor cds_nonintrusive_MichaelSet_erase_val
477 Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
478 template parameter \p Q defines the key type searching in the list.
479 The set item comparator should be able to compare the type \p value_type
482 Return \p true if key is found and deleted, \p false otherwise
484 template <typename Q>
485 bool erase( Q const& key )
487 const bool bRet = bucket( key ).erase( key );
493 /// Deletes the item from the set using \p pred predicate for searching
495 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
496 but \p pred is used for key comparing.
497 \p Less functor has the interface like \p std::less.
498 \p Less must imply the same element order as the comparator used for building the set.
500 template <typename Q, typename Less>
501 bool erase_with( Q const& key, Less pred )
503 const bool bRet = bucket( key ).erase_with( key, pred );
509 /// Deletes \p key from the set
510 /** \anchor cds_nonintrusive_MichaelSet_erase_func
512 The function searches an item with key \p key, calls \p f functor
513 and deletes the item. If \p key is not found, the functor is not called.
515 The functor \p Func interface:
518 void operator()(value_type& item);
521 where \p item - the item found.
523 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
524 template parameter \p Q defines the key type searching in the list.
525 The list item comparator should be able to compare the type \p T of list item
528 Return \p true if key is found and deleted, \p false otherwise
530 template <typename Q, typename Func>
531 bool erase( Q const& key, Func f )
533 const bool bRet = bucket( key ).erase( key, f );
539 /// Deletes the item from the set using \p pred predicate for searching
541 The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
542 but \p pred is used for key comparing.
543 \p Less functor has the interface like \p std::less.
544 \p Less must imply the same element order as the comparator used for building the set.
546 template <typename Q, typename Less, typename Func>
547 bool erase_with( Q const& key, Less pred, Func f )
549 const bool bRet = bucket( key ).erase_with( key, pred, f );
555 /// Extracts the item with specified \p key
556 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
557 The function searches an item with key equal to \p key,
558 unlinks it from the set, and returns it as \p guarded_ptr.
559 If \p key is not found the function returns an empty guadd pointer.
561 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
563 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
564 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
568 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
572 michael_set::guarded_ptr gp( theSet.extract( 5 ));
577 // Destructor of gp releases internal HP guard
581 template <typename Q>
582 guarded_ptr extract( Q const& key )
584 guarded_ptr gp( bucket( key ).extract( key ));
590 /// Extracts the item using compare functor \p pred
592 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)"
593 but \p pred predicate is used for key comparing.
595 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
597 \p pred must imply the same element order as the comparator used for building the set.
599 template <typename Q, typename Less>
600 guarded_ptr extract_with( Q const& key, Less pred )
602 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
608 /// Finds the key \p key
609 /** \anchor cds_nonintrusive_MichaelSet_find_func
611 The function searches the item with key equal to \p key and calls the functor \p f for item found.
612 The interface of \p Func functor is:
615 void operator()( value_type& item, Q& key );
618 where \p item is the item found, \p key is the <tt>find</tt> function argument.
620 The functor may change non-key fields of \p item. Note that the functor is only guarantee
621 that \p item cannot be disposed during functor is executing.
622 The functor does not serialize simultaneous access to the set's \p item. If such access is
623 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
625 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
626 can modify both arguments.
628 Note the hash functor specified for class \p Traits template parameter
629 should accept a parameter of type \p Q that may be not the same as \p value_type.
631 The function returns \p true if \p key is found, \p false otherwise.
633 template <typename Q, typename Func>
634 bool find( Q& key, Func f )
636 return bucket( key ).find( key, f );
639 template <typename Q, typename Func>
640 bool find( Q const& key, Func f )
642 return bucket( key ).find( key, f );
646 /// Finds the key \p key using \p pred predicate for searching
648 The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
649 but \p pred is used for key comparing.
650 \p Less functor has the interface like \p std::less.
651 \p Less must imply the same element order as the comparator used for building the set.
653 template <typename Q, typename Less, typename Func>
654 bool find_with( Q& key, Less pred, Func f )
656 return bucket( key ).find_with( key, pred, f );
659 template <typename Q, typename Less, typename Func>
660 bool find_with( Q const& key, Less pred, Func f )
662 return bucket( key ).find_with( key, pred, f );
666 /// Checks whether the set contains \p key
669 The function searches the item with key equal to \p key
670 and returns \p true if the key is found, and \p false otherwise.
672 Note the hash functor specified for class \p Traits template parameter
673 should accept a parameter of type \p Q that can be not the same as \p value_type.
675 template <typename Q>
676 bool contains( Q const& key )
678 return bucket( key ).contains( key );
681 template <typename Q>
682 CDS_DEPRECATED("use contains()")
683 bool find( Q const& key )
685 return contains( key );
689 /// Checks whether the set contains \p key using \p pred predicate for searching
691 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
692 \p Less functor has the interface like \p std::less.
693 \p Less must imply the same element order as the comparator used for building the set.
695 template <typename Q, typename Less>
696 bool contains( Q const& key, Less pred )
698 return bucket( key ).contains( key, pred );
701 template <typename Q, typename Less>
702 CDS_DEPRECATED("use contains()")
703 bool find_with( Q const& key, Less pred )
705 return contains( key, pred );
709 /// Finds the key \p key and return the item found
710 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
711 The function searches the item with key equal to \p key
712 and returns the guarded pointer to the item found.
713 If \p key is not found the functin returns an empty guarded pointer.
715 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
719 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
723 michael_set::guarded_ptr gp( theSet.get( 5 ));
728 // Destructor of guarded_ptr releases internal HP guard
732 Note the compare functor specified for \p OrderedList template parameter
733 should accept a parameter of type \p Q that can be not the same as \p value_type.
735 template <typename Q>
736 guarded_ptr get( Q const& key )
738 return bucket( key ).get( key );
741 /// Finds the key \p key and return the item found
743 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
744 but \p pred is used for comparing the keys.
746 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
748 \p pred must imply the same element order as the comparator used for building the set.
750 template <typename Q, typename Less>
751 guarded_ptr get_with( Q const& key, Less pred )
753 return bucket( key ).get_with( key, pred );
756 /// Clears the set (non-atomic)
758 The function erases all items from the set.
760 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
761 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
762 <tt> empty() </tt> may return \p true but the set may contain item(s).
763 Therefore, \p clear may be used only for debugging purposes.
767 for ( size_t i = 0; i < bucket_count(); ++i )
768 m_Buckets[i].clear();
769 m_ItemCounter.reset();
772 /// Checks if the set is empty
774 Emptiness is checked by item counting: if item count is zero then the set is empty.
775 Thus, the correct item counting feature is an important part of Michael's set implementation.
782 /// Returns item count in the set
785 return m_ItemCounter;
788 /// Returns the size of hash table
790 Since MichaelHashSet cannot dynamically extend the hash table size,
791 the value returned is an constant depending on object initialization parameters;
792 see MichaelHashSet::MichaelHashSet for explanation.
794 size_t bucket_count() const
796 return m_nHashBitmask + 1;
800 }} // namespace cds::container
802 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H