2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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_INTRUSIVE_MICHAEL_SET_H
32 #define CDSLIB_INTRUSIVE_MICHAEL_SET_H
34 #include <cds/intrusive/details/michael_set_base.h>
35 #include <cds/intrusive/details/iterable_list_base.h>
37 namespace cds { namespace intrusive {
39 /// Michael's hash set
40 /** @ingroup cds_intrusive_map
41 \anchor cds_intrusive_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. Note the \p GC must be the same as the GC used for \p OrderedList
53 - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations:
54 \p MichaelList, \p LazyList, \p IterableList.
55 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
56 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
58 - \p Traits - type traits. See \p michael_set::traits for explanation.
59 Instead of defining \p Traits struct you can use option-based syntax with \p michael_set::make_traits metafunction.
61 There are several specializations of \p %MichaelHashSet for each GC. You should include:
62 - <tt><cds/intrusive/michael_set_rcu.h></tt> for \ref cds_intrusive_MichaelHashSet_rcu "RCU type"
63 - <tt><cds/intrusive/michael_set_nogc.h></tt> for \ref cds_intrusive_MichaelHashSet_nogc for append-only set
64 - <tt><cds/intrusive/michael_set.h></tt> for \p gc::HP, \p gc::DHP
68 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from \p value_type.
69 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
70 the hash values of these keys must be equal.
71 The hash functor \p Traits::hash should accept parameters of both type:
75 std::string key_; // key field
81 size_t operator()( const std::string& s ) const
83 return std::hash( s );
86 size_t operator()( const Foo& f ) const
88 return (*this)( f.key_ );
95 First, you should define ordered list type to use in your hash set:
97 // For gc::HP-based MichaelList implementation
98 #include <cds/intrusive/michael_list_hp.h>
100 // cds::intrusive::MichaelHashSet declaration
101 #include <cds/intrusive/michael_set.h>
103 // Type of hash-set items
104 struct Foo: public cds::intrusive::michael_list::node< cds::gc::HP >
106 std::string key_ ; // key field
107 unsigned val_ ; // value field
108 // ... other value fields
111 // Declare comparator for the item
114 int operator()( const Foo& f1, const Foo& f2 ) const
116 return f1.key_.compare( f2.key_ );
120 // Declare bucket type for Michael's hash set
121 // The bucket type is any ordered list type like MichaelList, LazyList
122 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
123 typename cds::intrusive::michael_list::make_traits<
125 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
126 // item comparator option
127 ,cds::opt::compare< FooCmp >
132 Second, you should declare Michael's hash set container:
135 // Declare hash functor
136 // Note, the hash functor accepts parameter type Foo and std::string
138 size_t operator()( const Foo& f ) const
140 return cds::opt::v::hash<std::string>()( f.key_ );
142 size_t operator()( const std::string& f ) const
144 return cds::opt::v::hash<std::string>()( f );
148 // Michael's set typedef
149 typedef cds::intrusive::MichaelHashSet<
152 ,typename cds::intrusive::michael_set::make_traits<
153 cds::opt::hash< FooHash >
158 Now, you can use \p Foo_set in your application.
160 Like other intrusive containers, you may build several containers on single item structure:
162 #include <cds/intrusive/michael_list_hp.h>
163 #include <cds/intrusive/michael_list_dhp.h>
164 #include <cds/intrusive/michael_set.h>
170 // The first key is maintained by gc::HP, second key is maintained by gc::DHP garbage collectors
171 // (I don't know what is needed for, but it is correct)
173 : public cds::intrusive::michael_list::node< cds::gc::HP, tag_key1_idx >
174 , public cds::intrusive::michael_list::node< cds::gc::DHP, tag_key2_idx >
176 std::string key1_ ; // first key field
177 unsigned int key2_ ; // second key field
179 // ... value fields and fields for controlling item's lifetime
182 // Declare comparators for the item
185 int operator()( const Foo& f1, const Foo& f2 ) const { return f1.key1_.compare( f2.key1_ ) ; }
189 bool operator()( const Foo& f1, const Foo& f2 ) const { return f1.key2_ < f2.key1_ ; }
192 // Declare bucket type for Michael's hash set indexed by key1_ field and maintained by gc::HP
193 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
194 typename cds::intrusive::michael_list::make_traits<
196 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP >, tag_key1_idx > >
197 // item comparator option
198 ,cds::opt::compare< Key1Cmp >
202 // Declare bucket type for Michael's hash set indexed by key2_ field and maintained by gc::DHP
203 typedef cds::intrusive::MichaelList< cds::gc::DHP, Foo,
204 typename cds::intrusive::michael_list::make_traits<
206 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP >, tag_key2_idx > >
207 // item comparator option
208 ,cds::opt::less< Key2Less >
212 // Declare hash functor
214 size_t operator()( const Foo& f ) const { return cds::opt::v::hash<std::string>()( f.key1_ ) ; }
215 size_t operator()( const std::string& s ) const { return cds::opt::v::hash<std::string>()( s ) ; }
217 inline size_t Key2Hash( const Foo& f ) { return (size_t) f.key2_ ; }
219 // Michael's set indexed by key1_ field
220 typedef cds::intrusive::MichaelHashSet<
223 ,typename cds::intrusive::michael_set::make_traits<
224 cds::opt::hash< Key1Hash >
228 // Michael's set indexed by key2_ field
229 typedef cds::intrusive::MichaelHashSet<
232 ,typename cds::intrusive::michael_set::make_traits<
233 cds::opt::hash< Key2Hash >
241 #ifdef CDS_DOXYGEN_INVOKED
242 class Traits = michael_set::traits
250 typedef GC gc; ///< Garbage collector
251 typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
252 typedef Traits traits; ///< Set traits
254 typedef typename ordered_list::value_type value_type ; ///< type of value to be stored in the set
255 typedef typename ordered_list::key_comparator key_comparator ; ///< key comparing functor
256 typedef typename ordered_list::disposer disposer ; ///< Node disposer functor
257 #ifdef CDS_DOXYGEN_INVOKED
258 typedef typename ordered_list::stat stat ; ///< Internal statistics
261 /// Hash functor for \p value_type and all its derivatives that you use
262 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
263 typedef typename traits::item_counter item_counter; ///< Item counter type
264 typedef typename traits::allocator allocator; ///< Bucket table allocator
266 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
268 /// Count of hazard pointer required for the algorithm
269 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount;
271 // GC and OrderedList::gc must be the same
272 static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
274 // atomicity::empty_item_counter is not allowed as a item counter
275 static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
276 "cds::atomicity::empty_item_counter is not allowed as a item counter");
280 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
282 typedef typename ordered_list::template rebind_traits<
283 cds::opt::item_counter< cds::atomicity::empty_item_counter >
284 , cds::opt::stat< typename bucket_stat::wrapped_stat >
285 >::type internal_bucket_type;
287 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
292 typedef typename bucket_stat::stat stat;
297 hash m_HashFunctor; ///< Hash functor
298 size_t const m_nHashBitmask;
299 internal_bucket_type* m_Buckets; ///< bucket table
300 item_counter m_ItemCounter; ///< Item counter
301 stat m_Stat; ///< Internal statistics
305 ///@name Forward iterators
309 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
310 - it has no post-increment operator
311 - it iterates items in unordered fashion
312 - The iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
314 Iterator thread safety depends on type of \p OrderedList:
315 - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
316 because that item is guarded by hazard pointer.
317 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
318 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
319 Use this iterator on the concurrent container for debugging purpose only.
320 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
322 typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
324 /// Const forward iterator
326 For iterator's features and requirements see \ref iterator
328 typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
330 /// Returns a forward iterator addressing the first element in a set
332 For empty set \code begin() == end() \endcode
336 return iterator( m_Buckets[0].begin(), bucket_begin(), bucket_end());
339 /// Returns an iterator that addresses the location succeeding the last element in a set
341 Do not use the value returned by <tt>end</tt> function to access any item.
342 The returned value can be used only to control reaching the end of the set.
343 For empty set \code begin() == end() \endcode
347 return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
350 /// Returns a forward const iterator addressing the first element in a set
351 const_iterator begin() const
353 return get_const_begin();
356 /// Returns a forward const iterator addressing the first element in a set
357 const_iterator cbegin() const
359 return get_const_begin();
362 /// Returns an const iterator that addresses the location succeeding the last element in a set
363 const_iterator end() const
365 return get_const_end();
368 /// Returns an const iterator that addresses the location succeeding the last element in a set
369 const_iterator cend() const
371 return get_const_end();
376 /// Initializes hash set
378 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
379 At construction time you should pass estimated maximum item count and a load factor.
380 The load factor is average size of one bucket - a small number between 1 and 10.
381 The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
382 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
385 size_t nMaxItemCount, ///< estimation of max item count in the hash set
386 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
387 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
388 , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
390 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
391 construct_bucket<bucket_stat>( it );
394 /// Clears hash set object and destroys it
399 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
400 it->~internal_bucket_type();
401 bucket_table_allocator().deallocate( m_Buckets, bucket_count());
406 The function inserts \p val in the set if it does not contain
407 an item with key equal to \p val.
409 Returns \p true if \p val is placed into the set, \p false otherwise.
411 bool insert( value_type& val )
413 bool bRet = bucket( val ).insert( val );
421 This function is intended for derived non-intrusive containers.
423 The function allows to split creating of new item into two part:
424 - create item with key only
425 - insert new item into the set
426 - if inserting is success, calls \p f functor to initialize value-field of \p val.
428 The functor signature is:
430 void func( value_type& val );
432 where \p val is the item inserted.
434 The user-defined functor is called only if the inserting is success.
436 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
437 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
440 template <typename Func>
441 bool insert( value_type& val, Func f )
443 bool bRet = bucket( val ).insert( val, f );
449 /// Updates the element
451 The operation performs inserting or changing data with lock-free manner.
453 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
454 Otherwise, the functor \p func is called with item found.
456 The functor signature depends of the type of \p OrderedList:
458 <b>for \p MichaelList, \p LazyList</b>
461 void operator()( bool bNew, value_type& item, value_type& val );
465 - \p bNew - \p true if the item has been inserted, \p false otherwise
466 - \p item - item of the set
467 - \p val - argument \p val passed into the \p %update() function
468 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
469 refers to the same thing.
471 The functor may change non-key fields of the \p item.
472 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
473 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
476 <b>for \p IterableList</b>
478 void func( value_type& val, value_type * old );
481 - \p val - argument \p val passed into the \p %update() function
482 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
484 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
485 \p second is \p true if new item has been added or \p false if the item with \p key
486 already is in the set.
488 template <typename Func>
489 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
491 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
497 template <typename Func>
498 CDS_DEPRECATED("ensure() is deprecated, use update()")
499 std::pair<bool, bool> ensure( value_type& val, Func func )
501 return update( val, func, true );
505 /// Inserts or updates the node (only for \p IterableList)
507 The operation performs inserting or changing data with lock-free manner.
509 If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
510 Otherwise, the current element is changed to \p val, the old element will be retired later
511 by call \p Traits::disposer.
513 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
514 \p second is \p true if \p val has been added or \p false if the item with that key
517 #ifdef CDS_DOXYGEN_INVOKED
518 std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
520 template <typename Q>
521 typename std::enable_if<
522 std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
523 std::pair<bool, bool>
525 upsert( Q& val, bool bAllowInsert = true )
528 std::pair<bool, bool> bRet = bucket( val ).upsert( val, bAllowInsert );
534 /// Unlinks the item \p val from the set
536 The function searches the item \p val in the set and unlink it
537 if it is found and is equal to \p val.
539 The function returns \p true if success and \p false otherwise.
541 bool unlink( value_type& val )
543 bool bRet = bucket( val ).unlink( val );
549 /// Deletes the item from the set
550 /** \anchor cds_intrusive_MichaelHashSet_hp_erase
551 The function searches an item with key equal to \p key in the set,
552 unlinks it, and returns \p true.
553 If the item with key equal to \p key is not found the function return \p false.
555 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
557 template <typename Q>
558 bool erase( Q const& key )
560 if ( bucket( key ).erase( key )) {
567 /// Deletes the item from the set using \p pred predicate for searching
569 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase "erase(Q const&)"
570 but \p pred is used for key comparing.
571 \p Less functor has the interface like \p std::less.
572 \p pred must imply the same element order as the comparator used for building the set.
574 template <typename Q, typename Less>
575 bool erase_with( Q const& key, Less pred )
577 if ( bucket( key ).erase_with( key, pred )) {
584 /// Deletes the item from the set
585 /** \anchor cds_intrusive_MichaelHashSet_hp_erase_func
586 The function searches an item with key equal to \p key in the set,
587 call \p f functor with item found, and unlinks it from the set.
588 The \ref disposer specified in \p OrderedList class template parameter is called
589 by garbage collector \p GC asynchronously.
591 The \p Func interface is
594 void operator()( value_type const& item );
598 If the item with key equal to \p key is not found the function return \p false.
600 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
602 template <typename Q, typename Func>
603 bool erase( Q const& key, Func f )
605 if ( bucket( key ).erase( key, f )) {
612 /// Deletes the item from the set using \p pred predicate for searching
614 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase_func "erase(Q const&, Func)"
615 but \p pred is used for key comparing.
616 \p Less functor has the interface like \p std::less.
617 \p pred must imply the same element order as the comparator used for building the set.
619 template <typename Q, typename Less, typename Func>
620 bool erase_with( Q const& key, Less pred, Func f )
622 if ( bucket( key ).erase_with( key, pred, f )) {
629 /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
631 Returns \p true if the operation is successful, \p false otherwise.
632 The function can return \p false if the node the iterator points to has already been deleted
635 The function does not invalidate the iterator, it remains valid and can be used for further traversing.
637 @note \p %erase_at() is supported only for \p %MichaelHashSet based on \p IterableList.
639 #ifdef CDS_DOXYGEN_INVOKED
640 bool erase_at( iterator const& iter )
642 template <typename Iterator>
643 typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
644 erase_at( Iterator const& iter )
647 assert( iter != end() );
648 assert( iter.bucket() != nullptr );
650 if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
657 /// Extracts the item with specified \p key
658 /** \anchor cds_intrusive_MichaelHashSet_hp_extract
659 The function searches an item with key equal to \p key,
660 unlinks it from the set, and returns an guarded pointer to the item extracted.
661 If \p key is not found the function returns an empty guarded pointer.
663 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
665 The \p disposer specified in \p OrderedList class' template parameter is called automatically
666 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
667 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
671 typedef cds::intrusive::MichaelHashSet< your_template_args > michael_set;
675 michael_set::guarded_ptr gp( theSet.extract( 5 ));
680 // Destructor of gp releases internal HP guard
684 template <typename Q>
685 guarded_ptr extract( Q const& key )
687 guarded_ptr gp = bucket( key ).extract( key );
693 /// Extracts the item using compare functor \p pred
695 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_extract "extract(Q const&)"
696 but \p pred predicate is used for key comparing.
698 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
700 \p pred must imply the same element order as the comparator used for building the list.
702 template <typename Q, typename Less>
703 guarded_ptr extract_with( Q const& key, Less pred )
705 guarded_ptr gp = bucket( key ).extract_with( key, pred );
711 /// Finds the key \p key
712 /** \anchor cds_intrusive_MichaelHashSet_hp_find_func
713 The function searches the item with key equal to \p key and calls the functor \p f for item found.
714 The interface of \p Func functor is:
717 void operator()( value_type& item, Q& key );
720 where \p item is the item found, \p key is the <tt>find</tt> function argument.
722 The functor may change non-key fields of \p item. Note that the functor is only guarantee
723 that \p item cannot be disposed during functor is executing.
724 The functor does not serialize simultaneous access to the set \p item. If such access is
725 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
727 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
728 may modify both arguments.
730 Note the hash functor specified for class \p Traits template parameter
731 should accept a parameter of type \p Q that can be not the same as \p value_type.
733 The function returns \p true if \p key is found, \p false otherwise.
735 template <typename Q, typename Func>
736 bool find( Q& key, Func f )
738 return bucket( key ).find( key, f );
741 template <typename Q, typename Func>
742 bool find( Q const& key, Func f )
744 return bucket( key ).find( key, f );
748 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
750 If \p key is not found the function returns \p end().
752 @note This function is supported only for the set based on \p IterableList
754 template <typename Q>
755 #ifdef CDS_DOXYGEN_INVOKED
758 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
762 internal_bucket_type& b = bucket( key );
763 typename internal_bucket_type::iterator it = b.find( key );
766 return iterator( it, &b, bucket_end());
769 template <typename Q>
770 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
773 internal_bucket_type& b = bucket( key );
774 typename internal_bucket_type::iterator it = b.find( key );
777 return iterator( it, &b, bucket_end());
782 /// Finds the key \p key using \p pred predicate for searching
784 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
785 but \p pred is used for key comparing.
786 \p Less functor has the interface like \p std::less.
787 \p pred must imply the same element order as the comparator used for building the set.
789 template <typename Q, typename Less, typename Func>
790 bool find_with( Q& key, Less pred, Func f )
792 return bucket( key ).find_with( key, pred, f );
795 template <typename Q, typename Less, typename Func>
796 bool find_with( Q const& key, Less pred, Func f )
798 return bucket( key ).find_with( key, pred, f );
802 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
804 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
805 \p Less functor has the interface like \p std::less.
806 \p pred must imply the same element order as the comparator used for building the set.
808 If \p key is not found the function returns \p end().
810 @note This function is supported only for the set based on \p IterableList
812 template <typename Q, typename Less>
813 #ifdef CDS_DOXYGEN_INVOKED
816 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
818 find_with( Q& key, Less pred )
820 internal_bucket_type& b = bucket( key );
821 typename internal_bucket_type::iterator it = b.find_with( key, pred );
824 return iterator( it, &b, bucket_end());
827 template <typename Q, typename Less>
828 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
829 find_with( Q const& key, Less pred )
831 internal_bucket_type& b = bucket( key );
832 typename internal_bucket_type::iterator it = b.find_with( key, pred );
835 return iterator( it, &b, bucket_end());
839 /// Checks whether the set contains \p key
842 The function searches the item with key equal to \p key
843 and returns \p true if the key is found, and \p false otherwise.
845 Note the hash functor specified for class \p Traits template parameter
846 should accept a parameter of type \p Q that can be not the same as \p value_type.
848 template <typename Q>
849 bool contains( Q const& key )
851 return bucket( key ).contains( key );
854 /// Checks whether the set contains \p key using \p pred predicate for searching
856 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
857 \p Less functor has the interface like \p std::less.
858 \p Less must imply the same element order as the comparator used for building the set.
860 template <typename Q, typename Less>
861 bool contains( Q const& key, Less pred )
863 return bucket( key ).contains( key, pred );
866 /// Finds the key \p key and return the item found
867 /** \anchor cds_intrusive_MichaelHashSet_hp_get
868 The function searches the item with key equal to \p key
869 and returns the guarded pointer to the item found.
870 If \p key is not found the function returns an empty \p guarded_ptr.
872 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
876 typedef cds::intrusive::MichaelHashSet< your_template_params > michael_set;
880 michael_set::guarded_ptr gp( theSet.get( 5 ));
881 if ( theSet.get( 5 )) {
885 // Destructor of guarded_ptr releases internal HP guard
889 Note the compare functor specified for \p OrderedList template parameter
890 should accept a parameter of type \p Q that can be not the same as \p value_type.
892 template <typename Q>
893 guarded_ptr get( Q const& key )
895 return bucket( key ).get( key );
898 /// Finds the key \p key and return the item found
900 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_get "get( Q const&)"
901 but \p pred is used for comparing the keys.
903 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
905 \p pred must imply the same element order as the comparator used for building the set.
907 template <typename Q, typename Less>
908 guarded_ptr get_with( Q const& key, Less pred )
910 return bucket( key ).get_with( key, pred );
913 /// Clears the set (non-atomic)
915 The function unlink all items from the set.
916 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
917 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
918 \p empty() may return \p true but the set may contain item(s).
919 Therefore, \p %clear() may be used only for debugging purposes.
921 For each item the \p disposer is called after unlinking.
925 for ( size_t i = 0; i < bucket_count(); ++i )
926 m_Buckets[i].clear();
927 m_ItemCounter.reset();
930 /// Checks if the set is empty
932 Emptiness is checked by item counting: if item count is zero then the set is empty.
933 Thus, the correct item counting feature is an important part of Michael's set implementation.
940 /// Returns item count in the set
943 return m_ItemCounter;
946 /// Returns const reference to internal statistics
947 stat const& statistics() const
952 /// Returns the size of hash table
954 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
955 the value returned is an constant depending on object initialization parameters,
956 see \p MichaelHashSet::MichaelHashSet.
958 size_t bucket_count() const
960 return m_nHashBitmask + 1;
965 internal_bucket_type * bucket_begin() const
970 internal_bucket_type * bucket_end() const
972 return m_Buckets + bucket_count();
975 const_iterator get_const_begin() const
977 return const_iterator( m_Buckets[0].cbegin(), bucket_begin(), bucket_end());
979 const_iterator get_const_end() const
981 return const_iterator( bucket_end()[-1].cend(), bucket_end() - 1, bucket_end());
984 template <typename Stat>
985 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
987 new (bucket) internal_bucket_type;
990 template <typename Stat>
991 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type * bucket )
993 new (bucket) internal_bucket_type( m_Stat );
996 /// Calculates hash value of \p key
997 template <typename Q>
998 size_t hash_value( const Q& key ) const
1000 return m_HashFunctor( key ) & m_nHashBitmask;
1003 /// Returns the bucket (ordered list) for \p key
1004 template <typename Q>
1005 internal_bucket_type& bucket( const Q& key )
1007 return m_Buckets[hash_value( key )];
1012 }} // namespace cds::intrusive
1014 #endif // ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H