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;
271 item_counter m_ItemCounter; ///< Item counter
272 hash m_HashFunctor; ///< Hash functor
273 bucket_type * m_Buckets; ///< bucket table
277 const size_t m_nHashBitmask;
282 /// Calculates hash value of \p key
283 template <typename Q>
284 size_t hash_value( const Q& key ) const
286 return m_HashFunctor( key ) & m_nHashBitmask;
289 /// Returns the bucket (ordered list) for \p key
290 template <typename Q>
291 bucket_type& bucket( const Q& key )
293 return m_Buckets[ hash_value( key ) ];
298 ///@name Forward iterators (only for debugging purpose)
302 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
303 - it has no post-increment operator
304 - it iterates items in unordered fashion
305 - The iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
306 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
307 deleting operations it is no guarantee that you iterate all item in the set.
308 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
310 @warning Use this iterator on the concurrent container for debugging purpose only.
312 typedef michael_set::details::iterator< bucket_type, false > iterator;
314 /// Const forward iterator
316 For iterator's features and requirements see \ref iterator
318 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
320 /// Returns a forward iterator addressing the first element in a set
322 For empty set \code begin() == end() \endcode
326 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
329 /// Returns an iterator that addresses the location succeeding the last element in a set
331 Do not use the value returned by <tt>end</tt> function to access any item.
332 The returned value can be used only to control reaching the end of the set.
333 For empty set \code begin() == end() \endcode
337 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
340 /// Returns a forward const iterator addressing the first element in a set
341 const_iterator begin() const
343 return get_const_begin();
346 /// Returns a forward const iterator addressing the first element in a set
347 const_iterator cbegin() const
349 return get_const_begin();
352 /// Returns an const iterator that addresses the location succeeding the last element in a set
353 const_iterator end() const
355 return get_const_end();
358 /// Returns an const iterator that addresses the location succeeding the last element in a set
359 const_iterator cend() const
361 return get_const_end();
367 const_iterator get_const_begin() const
369 return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
371 const_iterator get_const_end() const
373 return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
378 /// Initializes hash set
379 /** @anchor cds_intrusive_MichaelHashSet_hp_ctor
380 The Michael's hash set is an unbounded container, but its hash table is non-expandable.
381 At construction time you should pass estimated maximum item count and a load factor.
382 The load factor is average size of one bucket - a small number between 1 and 10.
383 The bucket is an ordered single-linked list, searching in the bucket has linear complexity <tt>O(nLoadFactor)</tt>.
384 The constructor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
387 size_t nMaxItemCount, ///< estimation of max item count in the hash set
388 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket. Small integer up to 10.
389 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
391 // GC and OrderedList::gc must be the same
392 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
394 // atomicity::empty_item_counter is not allowed as a item counter
395 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
396 "cds::atomicity::empty_item_counter is not allowed as a item counter");
398 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
401 /// Clears hash set object and destroys it
405 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
410 The function inserts \p val in the set if it does not contain
411 an item with key equal to \p val.
413 Returns \p true if \p val is placed into the set, \p false otherwise.
415 bool insert( value_type& val )
417 bool bRet = bucket( val ).insert( val );
425 This function is intended for derived non-intrusive containers.
427 The function allows to split creating of new item into two part:
428 - create item with key only
429 - insert new item into the set
430 - if inserting is success, calls \p f functor to initialize value-field of \p val.
432 The functor signature is:
434 void func( value_type& val );
436 where \p val is the item inserted.
438 The user-defined functor is called only if the inserting is success.
440 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
441 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
444 template <typename Func>
445 bool insert( value_type& val, Func f )
447 bool bRet = bucket( val ).insert( val, f );
453 /// Updates the element
455 The operation performs inserting or changing data with lock-free manner.
457 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
458 Otherwise, the functor \p func is called with item found.
459 The functor signature is:
462 void operator()( bool bNew, value_type& item, value_type& val );
466 - \p bNew - \p true if the item has been inserted, \p false otherwise
467 - \p item - item of the set
468 - \p val - argument \p val passed into the \p %update() function
469 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
470 refers to the same thing.
472 The functor may change non-key fields of the \p item.
474 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
475 \p second is \p true if new item has been added or \p false if the item with \p key
476 already is in the set.
478 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
479 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
482 template <typename Func>
483 std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
485 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
491 template <typename Func>
492 CDS_DEPRECATED("ensure() is deprecated, use update()")
493 std::pair<bool, bool> ensure( value_type& val, Func func )
495 return update( val, func, true );
499 /// Unlinks the item \p val from the set
501 The function searches the item \p val in the set and unlink it
502 if it is found and is equal to \p val.
504 The function returns \p true if success and \p false otherwise.
506 bool unlink( value_type& val )
508 bool bRet = bucket( val ).unlink( val );
514 /// Deletes the item from the set
515 /** \anchor cds_intrusive_MichaelHashSet_hp_erase
516 The function searches an item with key equal to \p key in the set,
517 unlinks it, and returns \p true.
518 If the item with key equal to \p key is not found the function return \p false.
520 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
522 template <typename Q>
523 bool erase( Q const& key )
525 if ( bucket( key ).erase( key )) {
532 /// Deletes the item from the set using \p pred predicate for searching
534 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase "erase(Q const&)"
535 but \p pred is used for key comparing.
536 \p Less functor has the interface like \p std::less.
537 \p pred must imply the same element order as the comparator used for building the set.
539 template <typename Q, typename Less>
540 bool erase_with( Q const& key, Less pred )
542 if ( bucket( key ).erase_with( key, pred )) {
549 /// Deletes the item from the set
550 /** \anchor cds_intrusive_MichaelHashSet_hp_erase_func
551 The function searches an item with key equal to \p key in the set,
552 call \p f functor with item found, and unlinks it from the set.
553 The \ref disposer specified in \p OrderedList class template parameter is called
554 by garbage collector \p GC asynchronously.
556 The \p Func interface is
559 void operator()( value_type const& item );
563 If the item with key equal to \p key is not found the function return \p false.
565 Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
567 template <typename Q, typename Func>
568 bool erase( Q const& key, Func f )
570 if ( bucket( key ).erase( key, f )) {
577 /// Deletes the item from the set using \p pred predicate for searching
579 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_erase_func "erase(Q const&, Func)"
580 but \p pred is used for key comparing.
581 \p Less functor has the interface like \p std::less.
582 \p pred must imply the same element order as the comparator used for building the set.
584 template <typename Q, typename Less, typename Func>
585 bool erase_with( Q const& key, Less pred, Func f )
587 if ( bucket( key ).erase_with( key, pred, f )) {
594 /// Extracts the item with specified \p key
595 /** \anchor cds_intrusive_MichaelHashSet_hp_extract
596 The function searches an item with key equal to \p key,
597 unlinks it from the set, and returns an guarded pointer to the item extracted.
598 If \p key is not found the function returns an empty guarded pointer.
600 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
602 The \p disposer specified in \p OrderedList class' template parameter is called automatically
603 by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
604 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
608 typedef cds::intrusive::MichaelHashSet< your_template_args > michael_set;
612 michael_set::guarded_ptr gp( theSet.extract( 5 ));
617 // Destructor of gp releases internal HP guard
621 template <typename Q>
622 guarded_ptr extract( Q const& key )
624 guarded_ptr gp = bucket( key ).extract( key );
630 /// Extracts the item using compare functor \p pred
632 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_extract "extract(Q const&)"
633 but \p pred predicate is used for key comparing.
635 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
637 \p pred must imply the same element order as the comparator used for building the list.
639 template <typename Q, typename Less>
640 guarded_ptr extract_with( Q const& key, Less pred )
642 guarded_ptr gp = bucket( key ).extract_with( key, pred );
648 /// Finds the key \p key
649 /** \anchor cds_intrusive_MichaelHashSet_hp_find_func
650 The function searches the item with key equal to \p key and calls the functor \p f for item found.
651 The interface of \p Func functor is:
654 void operator()( value_type& item, Q& key );
657 where \p item is the item found, \p key is the <tt>find</tt> function argument.
659 The functor may change non-key fields of \p item. Note that the functor is only guarantee
660 that \p item cannot be disposed during functor is executing.
661 The functor does not serialize simultaneous access to the set \p item. If such access is
662 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
664 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
665 may modify both arguments.
667 Note the hash functor specified for class \p Traits template parameter
668 should accept a parameter of type \p Q that can be not the same as \p value_type.
670 The function returns \p true if \p key is found, \p false otherwise.
672 template <typename Q, typename Func>
673 bool find( Q& key, Func f )
675 return bucket( key ).find( key, f );
678 template <typename Q, typename Func>
679 bool find( Q const& key, Func f )
681 return bucket( key ).find( key, f );
685 /// Finds the key \p key using \p pred predicate for searching
687 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
688 but \p pred is used for key comparing.
689 \p Less functor has the interface like \p std::less.
690 \p pred must imply the same element order as the comparator used for building the set.
692 template <typename Q, typename Less, typename Func>
693 bool find_with( Q& key, Less pred, Func f )
695 return bucket( key ).find_with( key, pred, f );
698 template <typename Q, typename Less, typename Func>
699 bool find_with( Q const& key, Less pred, Func f )
701 return bucket( key ).find_with( key, pred, f );
705 /// Checks whether the set contains \p key
708 The function searches the item with key equal to \p key
709 and returns \p true if the key is found, and \p false otherwise.
711 Note the hash functor specified for class \p Traits template parameter
712 should accept a parameter of type \p Q that can be not the same as \p value_type.
714 template <typename Q>
715 bool contains( Q const& key )
717 return bucket( key ).contains( key );
720 template <typename Q>
721 CDS_DEPRECATED("use contains()")
722 bool find( Q const& key )
724 return contains( key );
728 /// Checks whether the set contains \p key using \p pred predicate for searching
730 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
731 \p Less functor has the interface like \p std::less.
732 \p Less must imply the same element order as the comparator used for building the set.
734 template <typename Q, typename Less>
735 bool contains( Q const& key, Less pred )
737 return bucket( key ).contains( key, pred );
740 template <typename Q, typename Less>
741 CDS_DEPRECATED("use contains()")
742 bool find_with( Q const& key, Less pred )
744 return contains( key, pred );
748 /// Finds the key \p key and return the item found
749 /** \anchor cds_intrusive_MichaelHashSet_hp_get
750 The function searches the item with key equal to \p key
751 and returns the guarded pointer to the item found.
752 If \p key is not found the function returns an empty \p guarded_ptr.
754 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
758 typedef cds::intrusive::MichaelHashSet< your_template_params > michael_set;
762 michael_set::guarded_ptr gp( theSet.get( 5 ));
763 if ( theSet.get( 5 )) {
767 // Destructor of guarded_ptr releases internal HP guard
771 Note the compare functor specified for \p OrderedList template parameter
772 should accept a parameter of type \p Q that can be not the same as \p value_type.
774 template <typename Q>
775 guarded_ptr get( Q const& key )
777 return bucket( key ).get( key );
780 /// Finds the key \p key and return the item found
782 The function is an analog of \ref cds_intrusive_MichaelHashSet_hp_get "get( Q const&)"
783 but \p pred is used for comparing the keys.
785 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
787 \p pred must imply the same element order as the comparator used for building the set.
789 template <typename Q, typename Less>
790 guarded_ptr get_with( Q const& key, Less pred )
792 return bucket( key ).get_with( key, pred );
795 /// Clears the set (non-atomic)
797 The function unlink all items from the set.
798 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
799 If there are a thread that performs insertion while \p %clear() is working the result is undefined in general case:
800 \p empty() may return \p true but the set may contain item(s).
801 Therefore, \p %clear() may be used only for debugging purposes.
803 For each item the \p disposer is called after unlinking.
807 for ( size_t i = 0; i < bucket_count(); ++i )
808 m_Buckets[i].clear();
809 m_ItemCounter.reset();
812 /// Checks if the set is empty
814 Emptiness is checked by item counting: if item count is zero then the set is empty.
815 Thus, the correct item counting feature is an important part of Michael's set implementation.
822 /// Returns item count in the set
825 return m_ItemCounter;
828 /// Returns the size of hash table
830 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
831 the value returned is an constant depending on object initialization parameters,
832 see \p MichaelHashSet::MichaelHashSet.
834 size_t bucket_count() const
836 return m_nHashBitmask + 1;
840 }} // namespace cds::intrusive
842 #endif // ifndef CDSLIB_INTRUSIVE_MICHAEL_SET_H