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_INTRUSIVE_MICHAEL_SET_H
32 #define CDSLIB_INTRUSIVE_MICHAEL_SET_H
34 #include <cds/intrusive/details/michael_set_base.h>
35 #include <cds/details/allocator.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, for example, \p MichaelList, \p LazyList.
54 The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
55 schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
57 - \p Traits - type traits. See \p michael_set::traits for explanation.
58 Instead of defining \p Traits struct you can use option-based syntax with \p michael_set::make_traits metafunction.
60 There are several specializations of \p %MichaelHashSet for each GC. You should include:
61 - <tt><cds/intrusive/michael_set_rcu.h></tt> for \ref cds_intrusive_MichaelHashSet_rcu "RCU type"
62 - <tt><cds/intrusive/michael_set_nogc.h></tt> for \ref cds_intrusive_MichaelHashSet_nogc for append-only set
63 - <tt><cds/intrusive/michael_set.h></tt> for \p gc::HP, \p gc::DHP
67 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from \p value_type.
68 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
69 the hash values of these keys must be equal.
70 The hash functor \p Traits::hash should accept parameters of both type:
74 std::string key_; // key field
80 size_t operator()( const std::string& s ) const
82 return std::hash( s );
85 size_t operator()( const Foo& f ) const
87 return (*this)( f.key_ );
94 First, you should define ordered list type to use in your hash set:
96 // For gc::HP-based MichaelList implementation
97 #include <cds/intrusive/michael_list_hp.h>
99 // cds::intrusive::MichaelHashSet declaration
100 #include <cds/intrusive/michael_set.h>
102 // Type of hash-set items
103 struct Foo: public cds::intrusive::michael_list::node< cds::gc::HP >
105 std::string key_ ; // key field
106 unsigned val_ ; // value field
107 // ... other value fields
110 // Declare comparator for the item
113 int operator()( const Foo& f1, const Foo& f2 ) const
115 return f1.key_.compare( f2.key_ );
119 // Declare bucket type for Michael's hash set
120 // The bucket type is any ordered list type like MichaelList, LazyList
121 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
122 typename cds::intrusive::michael_list::make_traits<
124 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >
125 // item comparator option
126 ,cds::opt::compare< FooCmp >
131 Second, you should declare Michael's hash set container:
134 // Declare hash functor
135 // Note, the hash functor accepts parameter type Foo and std::string
137 size_t operator()( const Foo& f ) const
139 return cds::opt::v::hash<std::string>()( f.key_ );
141 size_t operator()( const std::string& f ) const
143 return cds::opt::v::hash<std::string>()( f );
147 // Michael's set typedef
148 typedef cds::intrusive::MichaelHashSet<
151 ,typename cds::intrusive::michael_set::make_traits<
152 cds::opt::hash< FooHash >
157 Now, you can use \p Foo_set in your application.
159 Like other intrusive containers, you may build several containers on single item structure:
161 #include <cds/intrusive/michael_list_hp.h>
162 #include <cds/intrusive/michael_list_dhp.h>
163 #include <cds/intrusive/michael_set.h>
169 // The first key is maintained by gc::HP, second key is maintained by gc::DHP garbage collectors
170 // (I don't know what is needed for, but it is correct)
172 : public cds::intrusive::michael_list::node< cds::gc::HP, tag_key1_idx >
173 , public cds::intrusive::michael_list::node< cds::gc::DHP, tag_key2_idx >
175 std::string key1_ ; // first key field
176 unsigned int key2_ ; // second key field
178 // ... value fields and fields for controlling item's lifetime
181 // Declare comparators for the item
184 int operator()( const Foo& f1, const Foo& f2 ) const { return f1.key1_.compare( f2.key1_ ) ; }
188 bool operator()( const Foo& f1, const Foo& f2 ) const { return f1.key2_ < f2.key1_ ; }
191 // Declare bucket type for Michael's hash set indexed by key1_ field and maintained by gc::HP
192 typedef cds::intrusive::MichaelList< cds::gc::HP, Foo,
193 typename cds::intrusive::michael_list::make_traits<
195 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP >, tag_key1_idx > >
196 // item comparator option
197 ,cds::opt::compare< Key1Cmp >
201 // Declare bucket type for Michael's hash set indexed by key2_ field and maintained by gc::DHP
202 typedef cds::intrusive::MichaelList< cds::gc::DHP, Foo,
203 typename cds::intrusive::michael_list::make_traits<
205 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::DHP >, tag_key2_idx > >
206 // item comparator option
207 ,cds::opt::less< Key2Less >
211 // Declare hash functor
213 size_t operator()( const Foo& f ) const { return cds::opt::v::hash<std::string>()( f.key1_ ) ; }
214 size_t operator()( const std::string& s ) const { return cds::opt::v::hash<std::string>()( s ) ; }
216 inline size_t Key2Hash( const Foo& f ) { return (size_t) f.key2_ ; }
218 // Michael's set indexed by key1_ field
219 typedef cds::intrusive::MichaelHashSet<
222 ,typename cds::intrusive::michael_set::make_traits<
223 cds::opt::hash< Key1Hash >
227 // Michael's set indexed by key2_ field
228 typedef cds::intrusive::MichaelHashSet<
231 ,typename cds::intrusive::michael_set::make_traits<
232 cds::opt::hash< Key2Hash >
240 #ifdef CDS_DOXYGEN_INVOKED
241 class Traits = michael_set::traits
249 typedef GC gc; ///< Garbage collector
250 typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
251 typedef ordered_list bucket_type; ///< bucket type
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
258 /// Hash functor for \p value_type and all its derivatives that you use
259 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
260 typedef typename traits::item_counter item_counter; ///< Item counter type
262 typedef typename ordered_list::guarded_ptr guarded_ptr; ///< Guarded pointer
264 /// Bucket table allocator
265 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
267 /// Count of hazard pointer required for the algorithm
268 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount;
272 item_counter m_ItemCounter; ///< Item counter
273 hash m_HashFunctor; ///< Hash functor
274 bucket_type * m_Buckets; ///< bucket table
278 const size_t m_nHashBitmask;
283 /// Calculates hash value of \p key
284 template <typename Q>
285 size_t hash_value( const Q& key ) const
287 return m_HashFunctor( key ) & m_nHashBitmask;
290 /// Returns the bucket (ordered list) for \p key
291 template <typename Q>
292 bucket_type& bucket( const Q& key )
294 return m_Buckets[ hash_value( key ) ];
299 ///@name Forward iterators (only for debugging purpose)
303 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
304 - it has no post-increment operator
305 - it iterates items in unordered fashion
306 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
307 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
308 deleting operations it is no guarantee that you iterate all item in the set.
309 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
311 @warning Use this iterator on the concurrent container for debugging purpose only.
313 typedef michael_set::details::iterator< bucket_type, false > iterator;
315 /// Const forward iterator
317 For iterator's features and requirements see \ref iterator
319 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
321 /// Returns a forward iterator addressing the first element in a set
323 For empty set \code begin() == end() \endcode
327 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
330 /// Returns an iterator that addresses the location succeeding the last element in a set
332 Do not use the value returned by <tt>end</tt> function to access any item.
333 The returned value can be used only to control reaching the end of the set.
334 For empty set \code begin() == end() \endcode
338 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
341 /// Returns a forward const iterator addressing the first element in a set
342 const_iterator begin() const
344 return get_const_begin();
347 /// Returns a forward const iterator addressing the first element in a set
348 const_iterator cbegin() const
350 return get_const_begin();
353 /// Returns an const iterator that addresses the location succeeding the last element in a set
354 const_iterator end() const
356 return get_const_end();
359 /// Returns an const iterator that addresses the location succeeding the last element in a set
360 const_iterator cend() const
362 return get_const_end();
368 const_iterator get_const_begin() const
370 return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
372 const_iterator get_const_end() const
374 return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
379 /// Initializes hash set
380 /** @anchor cds_intrusive_MichaelHashSet_hp_ctor
381 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
382 At construction time you should pass estimated maximum item count and a load factor.
383 The load factor is average size of one bucket - a small number between 1 and 10.
384 The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
385 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
388 size_t nMaxItemCount, ///< estimation of max item count in the hash set
389 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
390 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
392 // GC and OrderedList::gc must be the same
393 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
395 // atomicity::empty_item_counter is not allowed as a item counter
396 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
397 "cds::atomicity::empty_item_counter is not allowed as a item counter");
399 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
402 /// Clears hash set object and destroys it
406 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
411 The function inserts \p val in the set if it does not contain
412 an item with key equal to \p val.
414 Returns \p true if \p val is placed into the set, \p false otherwise.
416 bool insert( value_type& val )
418 bool bRet = bucket( val ).insert( val );
426 This function is intended for derived non-intrusive containers.
428 The function allows to split creating of new item into two part:
429 - create item with key only
430 - insert new item into the set
431 - if inserting is success, calls \p f functor to initialize value-field of \p val.
433 The functor signature is:
435 void func( value_type& val );
437 where \p val is the item inserted.
439 The user-defined functor is called only if the inserting is success.
441 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
442 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
445 template <typename Func>
446 bool insert( value_type& val, Func f )
448 bool bRet = bucket( val ).insert( val, f );
454 /// Updates the element
456 The operation performs inserting or changing data with lock-free manner.
458 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
459 Otherwise, the functor \p func is called with item found.
460 The functor signature is:
463 void operator()( bool bNew, value_type& item, value_type& val );
467 - \p bNew - \p true if the item has been inserted, \p false otherwise
468 - \p item - item of the set
469 - \p val - argument \p val passed into the \p %update() function
470 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
471 refers to the same thing.
473 The functor may change non-key fields of the \p item.
475 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
476 \p second is \p true if new item has been added or \p false if the item with \p key
477 already is in the set.
479 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
480 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
483 template <typename Func>
484 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
486 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
492 template <typename Func>
493 CDS_DEPRECATED("ensure() is deprecated, use update()")
494 std::pair<bool, bool> ensure( value_type& val, Func func )
496 return update( val, func, true );
500 /// Unlinks the item \p val from the set
502 The function searches the item \p val in the set and unlink it
503 if it is found and is equal to \p val.
505 The function returns \p true if success and \p false otherwise.
507 bool unlink( value_type& val )
509 bool bRet = bucket( val ).unlink( val );
515 /// Deletes the item from the set
516 /** \anchor cds_intrusive_MichaelHashSet_hp_erase
517 The function searches an item with key equal to \p key in the set,
518 unlinks it, and returns \p true.
519 If the item with key equal to \p key is not found the function return \p false.
521 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
523 template <typename Q>
524 bool erase( Q const& key )
526 if ( bucket( key ).erase( key )) {
533 /// Deletes the item from the set using \p pred predicate for searching
535 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase "erase(Q const&)"
536 but \p pred is used for key comparing.
537 \p Less functor has the interface like \p std::less.
538 \p pred must imply the same element order as the comparator used for building the set.
540 template <typename Q, typename Less>
541 bool erase_with( Q const& key, Less pred )
543 if ( bucket( key ).erase_with( key, pred )) {
550 /// Deletes the item from the set
551 /** \anchor cds_intrusive_MichaelHashSet_hp_erase_func
552 The function searches an item with key equal to \p key in the set,
553 call \p f functor with item found, and unlinks it from the set.
554 The \ref disposer specified in \p OrderedList class template parameter is called
555 by garbage collector \p GC asynchronously.
557 The \p Func interface is
560 void operator()( value_type const& item );
564 If the item with key equal to \p key is not found the function return \p false.
566 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
568 template <typename Q, typename Func>
569 bool erase( Q const& key, Func f )
571 if ( bucket( key ).erase( key, f )) {
578 /// Deletes the item from the set using \p pred predicate for searching
580 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase_func "erase(Q const&, Func)"
581 but \p pred is used for key comparing.
582 \p Less functor has the interface like \p std::less.
583 \p pred must imply the same element order as the comparator used for building the set.
585 template <typename Q, typename Less, typename Func>
586 bool erase_with( Q const& key, Less pred, Func f )
588 if ( bucket( key ).erase_with( key, pred, f )) {
595 /// Extracts the item with specified \p key
596 /** \anchor cds_intrusive_MichaelHashSet_hp_extract
597 The function searches an item with key equal to \p key,
598 unlinks it from the set, and returns an guarded pointer to the item extracted.
599 If \p key is not found the function returns an empty guarded pointer.
601 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
603 The \p disposer specified in \p OrderedList class' template parameter is called automatically
604 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
605 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
609 typedef cds::intrusive::MichaelHashSet< your_template_args > michael_set;
613 michael_set::guarded_ptr gp( theSet.extract( 5 ));
618 // Destructor of gp releases internal HP guard
622 template <typename Q>
623 guarded_ptr extract( Q const& key )
625 guarded_ptr gp = bucket( key ).extract( key );
631 /// Extracts the item using compare functor \p pred
633 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_extract "extract(Q const&)"
634 but \p pred predicate is used for key comparing.
636 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
638 \p pred must imply the same element order as the comparator used for building the list.
640 template <typename Q, typename Less>
641 guarded_ptr extract_with( Q const& key, Less pred )
643 guarded_ptr gp = bucket( key ).extract_with( key, pred );
649 /// Finds the key \p key
650 /** \anchor cds_intrusive_MichaelHashSet_hp_find_func
651 The function searches the item with key equal to \p key and calls the functor \p f for item found.
652 The interface of \p Func functor is:
655 void operator()( value_type& item, Q& key );
658 where \p item is the item found, \p key is the <tt>find</tt> function argument.
660 The functor may change non-key fields of \p item. Note that the functor is only guarantee
661 that \p item cannot be disposed during functor is executing.
662 The functor does not serialize simultaneous access to the set \p item. If such access is
663 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
665 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
666 may modify both arguments.
668 Note the hash functor specified for class \p Traits template parameter
669 should accept a parameter of type \p Q that can be not the same as \p value_type.
671 The function returns \p true if \p key is found, \p false otherwise.
673 template <typename Q, typename Func>
674 bool find( Q& key, Func f )
676 return bucket( key ).find( key, f );
679 template <typename Q, typename Func>
680 bool find( Q const& key, Func f )
682 return bucket( key ).find( key, f );
686 /// Finds the key \p key using \p pred predicate for searching
688 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
689 but \p pred is used for key comparing.
690 \p Less functor has the interface like \p std::less.
691 \p pred must imply the same element order as the comparator used for building the set.
693 template <typename Q, typename Less, typename Func>
694 bool find_with( Q& key, Less pred, Func f )
696 return bucket( key ).find_with( key, pred, f );
699 template <typename Q, typename Less, typename Func>
700 bool find_with( Q const& key, Less pred, Func f )
702 return bucket( key ).find_with( key, pred, f );
706 /// Checks whether the set contains \p key
709 The function searches the item with key equal to \p key
710 and returns \p true if the key is found, and \p false otherwise.
712 Note the hash functor specified for class \p Traits template parameter
713 should accept a parameter of type \p Q that can be not the same as \p value_type.
715 template <typename Q>
716 bool contains( Q const& key )
718 return bucket( key ).contains( key );
721 template <typename Q>
722 CDS_DEPRECATED("use contains()")
723 bool find( Q const& key )
725 return contains( key );
729 /// Checks whether the set contains \p key using \p pred predicate for searching
731 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
732 \p Less functor has the interface like \p std::less.
733 \p Less must imply the same element order as the comparator used for building the set.
735 template <typename Q, typename Less>
736 bool contains( Q const& key, Less pred )
738 return bucket( key ).contains( key, pred );
741 template <typename Q, typename Less>
742 CDS_DEPRECATED("use contains()")
743 bool find_with( Q const& key, Less pred )
745 return contains( key, pred );
749 /// Finds the key \p key and return the item found
750 /** \anchor cds_intrusive_MichaelHashSet_hp_get
751 The function searches the item with key equal to \p key
752 and returns the guarded pointer to the item found.
753 If \p key is not found the function returns an empty \p guarded_ptr.
755 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
759 typedef cds::intrusive::MichaelHashSet< your_template_params > michael_set;
763 michael_set::guarded_ptr gp( theSet.get( 5 ));
764 if ( theSet.get( 5 )) {
768 // Destructor of guarded_ptr releases internal HP guard
772 Note the compare functor specified for \p OrderedList template parameter
773 should accept a parameter of type \p Q that can be not the same as \p value_type.
775 template <typename Q>
776 guarded_ptr get( Q const& key )
778 return bucket( key ).get( key );
781 /// Finds the key \p key and return the item found
783 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_get "get( Q const&)"
784 but \p pred is used for comparing the keys.
786 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
788 \p pred must imply the same element order as the comparator used for building the set.
790 template <typename Q, typename Less>
791 guarded_ptr get_with( Q const& key, Less pred )
793 return bucket( key ).get_with( key, pred );
796 /// Clears the set (non-atomic)
798 The function unlink all items from the set.
799 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
800 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
801 \p empty() may return \p true but the set may contain item(s).
802 Therefore, \p %clear() may be used only for debugging purposes.
804 For each item the \p disposer is called after unlinking.
808 for ( size_t i = 0; i < bucket_count(); ++i )
809 m_Buckets[i].clear();
810 m_ItemCounter.reset();
813 /// Checks if the set is empty
815 Emptiness is checked by item counting: if item count is zero then the set is empty.
816 Thus, the correct item counting feature is an important part of Michael's set implementation.
823 /// Returns item count in the set
826 return m_ItemCounter;
829 /// Returns the size of hash table
831 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
832 the value returned is an constant depending on object initialization parameters,
833 see \p MichaelHashSet::MichaelHashSet.
835 size_t bucket_count() const
837 return m_nHashBitmask + 1;
841 }} // namespace cds::intrusive
843 #endif // ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H