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/container/details/iterable_list_base.h>
36 #include <cds/details/allocator.h>
38 namespace cds { namespace container {
40 /// Michael's hash set
41 /** @ingroup cds_nonintrusive_set
42 \anchor cds_nonintrusive_MichaelHashSet_hp
45 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
47 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
48 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
49 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
50 However, each bucket may contain unbounded number of items.
52 Template parameters are:
53 - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
54 from the \p libcds library.
55 Note the \p GC must be the same as the \p GC used for \p OrderedList
56 - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations:
57 \p MichaelList, \p LazyList, \p IterableList.
58 The ordered list implementation specifies the type \p T to be stored in the hash-set,
59 the comparing functor for the type \p T and other features specific for the ordered list.
60 - \p Traits - set traits, default is \p michael_set::traits.
61 Instead of defining \p Traits struct you may use option-based syntax with \p michael_set::make_traits metafunction.
63 There are the specializations:
64 - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_set_rcu.h</tt>,
65 see \ref cds_nonintrusive_MichaelHashSet_rcu "MichaelHashSet<RCU>".
66 - for \ref cds::gc::nogc declared in <tt>cds/container/michael_set_nogc.h</tt>,
67 see \ref cds_nonintrusive_MichaelHashSet_nogc "MichaelHashSet<gc::nogc>".
69 \anchor cds_nonintrusive_MichaelHashSet_hash_functor
72 Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from node type \p value_type.
73 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
74 are equal the hash values of these keys must be equal too.
76 The hash functor \p Traits::hash should accept parameters of both type:
80 std::string key_; // key field
86 size_t operator()( const std::string& s ) const
88 return std::hash( s );
91 size_t operator()( const Foo& f ) const
93 return (*this)( f.key_ );
100 Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
103 int nKey; // key field
104 int nVal; // value field
108 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
109 that will be used as a bucket for the set. We will use \p gc::DHP reclamation schema and
110 \p MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
113 #include <cds/container/michael_list_dhp.h>
114 #include <cds/container/michael_set.h>
116 namespace cc = cds::container;
120 int operator ()(Foo const& v1, Foo const& v2 ) const
122 if ( std::less( v1.nKey, v2.nKey ))
124 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
129 typedef cc::MichaelList< cds::gc::DHP, Foo,
130 typename cc::michael_list::make_traits<
131 cc::opt::compare< Foo_cmp > // item comparator option
135 // Hash functor for Foo
137 size_t operator ()( int i ) const
139 return std::hash( i );
141 size_t operator()( Foo const& i ) const
143 return std::hash( i.nKey );
148 // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
149 typedef cc::MichaelHashSet< cds::gc::DHP, bucket_list,
150 cc::michael_set::make_traits<
151 cc::opt::hash< foo_hash >
162 #ifdef CDS_DOXYGEN_INVOKED
163 class Traits = michael_set::traits
171 typedef GC gc; ///< Garbage collector
172 typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
173 typedef Traits traits; ///< Set traits
175 typedef typename ordered_list::value_type value_type; ///< type of value to be stored in the list
176 typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
177 #ifdef CDS_DOXYGEN_INVOKED
178 typedef typename ordered_list::stat stat; ///< Internal statistics
181 /// Hash functor for \ref value_type and all its derivatives that you use
182 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
183 typedef typename traits::item_counter item_counter; ///< Item counter type
184 typedef typename traits::allocator allocator; ///< Bucket table allocator
186 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
188 // GC and OrderedList::gc must be the same
189 static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
191 // atomicity::empty_item_counter is not allowed as a item counter
192 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
193 "cds::atomicity::empty_item_counter is not allowed as a item counter");
196 typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
198 typedef typename ordered_list::template rebind_traits<
199 cds::opt::item_counter< cds::atomicity::empty_item_counter >
200 , cds::opt::stat< typename bucket_stat::wrapped_stat >
201 >::type internal_bucket_type;
203 /// Bucket table allocator
204 typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
206 typedef typename bucket_stat::stat stat;
209 /// Guarded pointer - a result of \p get() and \p extract() functions
210 typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
214 size_t const m_nHashBitmask;
215 internal_bucket_type * m_Buckets; ///< bucket table
216 item_counter m_ItemCounter; ///< Item counter
217 hash m_HashFunctor; ///< Hash functor
218 stat m_Stat; ///< Internal statistics
222 ///@name Forward iterators
226 The forward iterator for Michael's set has some features:
227 - it has no post-increment operator
228 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
229 For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
230 may be thrown if the limit of guard count per thread is exceeded.
231 - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
233 Iterator thread safety depends on type of \p OrderedList:
234 - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
235 because that item is guarded by hazard pointer.
236 However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
237 Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
238 Use this iterator on the concurrent container for debugging purpose only.
239 - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
241 The iterator interface:
245 // Default constructor
249 iterator( iterator const& src );
251 // Dereference operator
252 value_type * operator ->() const;
254 // Dereference operator
255 value_type& operator *() const;
257 // Preincrement operator
258 iterator& operator ++();
260 // Assignment operator
261 iterator& operator = (iterator const& src);
263 // Equality operators
264 bool operator ==(iterator const& i ) const;
265 bool operator !=(iterator const& i ) const;
271 typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
273 /// Const forward iterator
274 typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
276 /// Returns a forward iterator addressing the first element in a set
278 For empty set \code begin() == end() \endcode
282 return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
285 /// Returns an iterator that addresses the location succeeding the last element in a set
287 Do not use the value returned by <tt>end</tt> function to access any item.
288 The returned value can be used only to control reaching the end of the set.
289 For empty set \code begin() == end() \endcode
293 return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
296 /// Returns a forward const iterator addressing the first element in a set
297 const_iterator begin() const
299 return get_const_begin();
302 /// Returns a forward const iterator addressing the first element in a set
303 const_iterator cbegin() const
305 return get_const_begin();
308 /// Returns an const iterator that addresses the location succeeding the last element in a set
309 const_iterator end() const
311 return get_const_end();
314 /// Returns an const iterator that addresses the location succeeding the last element in a set
315 const_iterator cend() const
317 return get_const_end();
322 /// Initialize hash set
324 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
325 when you create an object.
326 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
327 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
329 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
332 size_t nMaxItemCount, ///< estimation of max item count in the hash set
333 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
334 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
335 , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
337 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
338 construct_bucket<bucket_stat>( it );
341 /// Clears hash set and destroys it
346 for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
347 it->~internal_bucket_type();
348 bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
353 The function creates a node with copy of \p val value
354 and then inserts the node created into the set.
356 The type \p Q should contain as minimum the complete key for the node.
357 The object of \ref value_type should be constructible from a value of type \p Q.
358 In trivial case, \p Q is equal to \ref value_type.
360 Returns \p true if \p val is inserted into the set, \p false otherwise.
362 template <typename Q>
363 bool insert( Q&& val )
365 const bool bRet = bucket( val ).insert( std::forward<Q>( val ));
373 The function allows to split creating of new item into two part:
374 - create item with key only
375 - insert new item into the set
376 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
378 The functor signature is:
380 void func( value_type& val );
382 where \p val is the item inserted.
383 The user-defined functor is called only if the inserting is success.
385 @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
386 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
387 @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
390 template <typename Q, typename Func>
391 bool insert( Q&& val, Func f )
393 const bool bRet = bucket( val ).insert( std::forward<Q>( val ), f );
399 /// Updates the element
401 The operation performs inserting or changing data with lock-free manner.
403 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
404 Otherwise, the functor \p func is called with item found.
406 The functor \p func signature depends of \p OrderedList:
408 <b>for \p MichaelList, \p LazyList</b>
411 void operator()( bool bNew, value_type& item, Q const& val );
415 - \p bNew - \p true if the item has been inserted, \p false otherwise
416 - \p item - item of the set
417 - \p val - argument \p val passed into the \p %update() function
419 The functor may change non-key fields of the \p item.
421 <b>for \p IterableList</b>
423 void func( value_type& val, value_type * old );
426 - \p val - a new data constructed from \p key
427 - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
429 @return <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
430 \p second is \p true if new item has been added or \p false if the item with \p key
431 already is in the set.
433 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
434 as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
435 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
438 template <typename Q, typename Func>
439 std::pair<bool, bool> update( Q&& val, Func func, bool bAllowUpdate = true )
441 std::pair<bool, bool> bRet = bucket( val ).update( std::forward<Q>( val ), func, bAllowUpdate );
447 template <typename Q, typename Func>
448 CDS_DEPRECATED("ensure() is deprecated, use update()")
449 std::pair<bool, bool> ensure( const Q& val, Func func )
451 return update( val, func, true );
455 /// Inserts or updates the node (only for \p IterableList)
457 The operation performs inserting or changing data with lock-free manner.
459 If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
460 Otherwise, the current element is changed to \p val, the old element will be retired later.
462 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
463 \p second is \p true if \p val has been added or \p false if the item with that key
466 template <typename Q>
467 #ifdef CDS_DOXYGEN_INVOKED
468 std::pair<bool, bool>
470 typename std::enable_if<
471 std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
472 std::pair<bool, bool>
475 upsert( Q&& val, bool bAllowInsert = true )
477 std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( val ), bAllowInsert );
483 /// Inserts data of type \p value_type constructed from \p args
485 Returns \p true if inserting successful, \p false otherwise.
487 template <typename... Args>
488 bool emplace( Args&&... args )
490 bool bRet = bucket_emplace<internal_bucket_type>( std::forward<Args>(args)... );
496 /// Deletes \p key from the set
498 Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
499 template parameter \p Q defines the key type searching in the list.
500 The set item comparator should be able to compare the type \p value_type
503 Return \p true if key is found and deleted, \p false otherwise.
505 template <typename Q>
506 bool erase( Q const& key )
508 const bool bRet = bucket( key ).erase( key );
514 /// Deletes the item from the set using \p pred predicate for searching
516 The function is an analog of \p erase(Q const&) but \p pred is used for key comparing.
517 \p Less functor has the interface like \p std::less.
518 \p Less must imply the same element order as the comparator used for building the set.
520 template <typename Q, typename Less>
521 bool erase_with( Q const& key, Less pred )
523 const bool bRet = bucket( key ).erase_with( key, pred );
529 /// Deletes \p key from the set
531 The function searches an item with key \p key, calls \p f functor
532 and deletes the item. If \p key is not found, the functor is not called.
534 The functor \p Func interface:
537 void operator()(value_type& item);
540 where \p item - the item found.
542 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
543 template parameter \p Q defines the key type searching in the list.
544 The list item comparator should be able to compare the type \p T of list item
547 Return \p true if key is found and deleted, \p false otherwise
549 template <typename Q, typename Func>
550 bool erase( Q const& key, Func f )
552 const bool bRet = bucket( key ).erase( key, f );
558 /// Deletes the item from the set using \p pred predicate for searching
560 The function is an analog of \p erase(Q const&, Func) but \p pred is used for key comparing.
561 \p Less functor has the interface like \p std::less.
562 \p Less must imply the same element order as the comparator used for building the set.
564 template <typename Q, typename Less, typename Func>
565 bool erase_with( Q const& key, Less pred, Func f )
567 const bool bRet = bucket( key ).erase_with( key, pred, f );
573 /// Extracts the item with specified \p key
574 /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
575 The function searches an item with key equal to \p key,
576 unlinks it from the set, and returns it as \p guarded_ptr.
577 If \p key is not found the function returns an empty guadd pointer.
579 Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
581 The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
582 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
586 typedef cds::container::MichaelHashSet< your_template_args > michael_set;
590 typename michael_set::guarded_ptr gp( theSet.extract( 5 ));
595 // Destructor of gp releases internal HP guard
599 template <typename Q>
600 guarded_ptr extract( Q const& key )
602 guarded_ptr gp( bucket( key ).extract( key ));
608 /// Extracts the item using compare functor \p pred
610 The function is an analog of \p extract(Q const&)
611 but \p pred predicate is used for key comparing.
613 \p Less functor has the semantics like \p std::less but should take arguments
614 of type \p value_type and \p Q in any order.
615 \p pred must imply the same element order as the comparator used for building the set.
617 template <typename Q, typename Less>
618 guarded_ptr extract_with( Q const& key, Less pred )
620 guarded_ptr gp( bucket( key ).extract_with( key, pred ));
626 /// Finds the key \p key
628 The function searches the item with key equal to \p key and calls the functor \p f for item found.
629 The interface of \p Func functor is:
632 void operator()( value_type& item, Q& key );
635 where \p item is the item found, \p key is the <tt>find</tt> function argument.
637 The functor may change non-key fields of \p item. Note that the functor is only guarantee
638 that \p item cannot be disposed during functor is executing.
639 The functor does not serialize simultaneous access to the set's \p item. If such access is
640 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
642 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
643 can modify both arguments.
645 Note the hash functor specified for class \p Traits template parameter
646 should accept a parameter of type \p Q that may be not the same as \p value_type.
648 The function returns \p true if \p key is found, \p false otherwise.
650 template <typename Q, typename Func>
651 bool find( Q& key, Func f )
653 return bucket( key ).find( key, f );
656 template <typename Q, typename Func>
657 bool find( Q const& key, Func f )
659 return bucket( key ).find( key, f );
663 /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
665 If \p key is not found the function returns \p end().
667 @note This function is supported only for the set based on \p IterableList
669 template <typename Q>
670 #ifdef CDS_DOXYGEN_INVOKED
673 typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
677 internal_bucket_type& b = bucket( key );
678 typename internal_bucket_type::iterator it = b.find( key );
681 return iterator( it, &b, bucket_end());
684 template <typename Q>
685 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
688 internal_bucket_type& b = bucket( key );
689 typename internal_bucket_type::iterator it = b.find( key );
692 return iterator( it, &b, bucket_end() );
696 /// Finds the key \p key using \p pred predicate for searching
698 The function is an analog of \p find(Q&, Func) but \p pred is used for key comparing.
699 \p Less functor has the interface like \p std::less.
700 \p Less must imply the same element order as the comparator used for building the set.
702 template <typename Q, typename Less, typename Func>
703 bool find_with( Q& key, Less pred, Func f )
705 return bucket( key ).find_with( key, pred, f );
708 template <typename Q, typename Less, typename Func>
709 bool find_with( Q const& key, Less pred, Func f )
711 return bucket( key ).find_with( key, pred, f );
715 /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
717 The function is an analog of \p find(Q&) but \p pred is used for key comparing.
718 \p Less functor has the interface like \p std::less.
719 \p pred must imply the same element order as the comparator used for building the set.
721 If \p key is not found the function returns \p end().
723 @note This function is supported only for the set based on \p IterableList
725 template <typename Q, typename Less>
726 #ifdef CDS_DOXYGEN_INVOKED
729 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
731 find_with( Q& key, Less pred )
733 internal_bucket_type& b = bucket( key );
734 typename internal_bucket_type::iterator it = b.find_with( key, pred );
737 return iterator( it, &b, bucket_end() );
740 template <typename Q, typename Less>
741 typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
742 find_with( Q const& key, Less pred )
744 internal_bucket_type& b = bucket( key );
745 typename internal_bucket_type::iterator it = b.find_with( key, pred );
748 return iterator( it, &b, bucket_end() );
752 /// Checks whether the set contains \p key
754 The function searches the item with key equal to \p key
755 and returns \p true if the key is found, and \p false otherwise.
757 Note the hash functor specified for class \p Traits template parameter
758 should accept a parameter of type \p Q that can be not the same as \p value_type.
760 template <typename Q>
761 bool contains( Q const& key )
763 return bucket( key ).contains( key );
766 /// Checks whether the set contains \p key using \p pred predicate for searching
768 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
769 \p Less functor has the interface like \p std::less.
770 \p Less must imply the same element order as the comparator used for building the set.
772 template <typename Q, typename Less>
773 bool contains( Q const& key, Less pred )
775 return bucket( key ).contains( key, pred );
778 /// Finds the key \p key and return the item found
779 /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
780 The function searches the item with key equal to \p key
781 and returns the guarded pointer to the item found.
782 If \p key is not found the functin returns an empty guarded pointer.
784 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
788 typedef cds::container::MichaeHashSet< your_template_params > michael_set;
792 typename michael_set::guarded_ptr gp( theSet.get( 5 ));
797 // Destructor of guarded_ptr releases internal HP guard
801 Note the compare functor specified for \p OrderedList template parameter
802 should accept a parameter of type \p Q that can be not the same as \p value_type.
804 template <typename Q>
805 guarded_ptr get( Q const& key )
807 return bucket( key ).get( key );
810 /// Finds the key \p key and return the item found
812 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
813 but \p pred is used for comparing the keys.
815 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
817 \p pred must imply the same element order as the comparator used for building the set.
819 template <typename Q, typename Less>
820 guarded_ptr get_with( Q const& key, Less pred )
822 return bucket( key ).get_with( key, pred );
825 /// Clears the set (non-atomic)
827 The function erases all items from the set.
829 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
830 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
831 <tt> empty() </tt> may return \p true but the set may contain item(s).
832 Therefore, \p clear may be used only for debugging purposes.
836 for ( size_t i = 0; i < bucket_count(); ++i )
837 m_Buckets[i].clear();
838 m_ItemCounter.reset();
841 /// Checks if the set is empty
843 Emptiness is checked by item counting: if item count is zero then the set is empty.
844 Thus, the correct item counting feature is an important part of Michael's set implementation.
851 /// Returns item count in the set
854 return m_ItemCounter;
857 /// Returns const reference to internal statistics
858 stat const& statistics() const
863 /// Returns the size of hash table
865 Since MichaelHashSet cannot dynamically extend the hash table size,
866 the value returned is an constant depending on object initialization parameters;
867 see MichaelHashSet::MichaelHashSet for explanation.
869 size_t bucket_count() const
871 return m_nHashBitmask + 1;
876 /// Calculates hash value of \p key
877 template <typename Q>
878 size_t hash_value( Q const& key ) const
880 return m_HashFunctor( key ) & m_nHashBitmask;
883 /// Returns the bucket (ordered list) for \p key
884 template <typename Q>
885 internal_bucket_type& bucket( Q const& key )
887 return m_Buckets[ hash_value( key ) ];
889 template <typename Q>
890 internal_bucket_type const& bucket( Q const& key ) const
892 return m_Buckets[hash_value( key )];
898 internal_bucket_type* bucket_begin() const
903 internal_bucket_type* bucket_end() const
905 return m_Buckets + bucket_count();
908 const_iterator get_const_begin() const
910 return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() );
912 const_iterator get_const_end() const
914 return const_iterator(( bucket_end() -1 )->cend(), bucket_end() - 1, bucket_end() );
917 template <typename Stat>
918 typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
920 new (bucket) internal_bucket_type;
923 template <typename Stat>
924 typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
926 new (bucket) internal_bucket_type( m_Stat );
929 template <typename List, typename... Args>
930 typename std::enable_if< !is_iterable_list<List>::value, bool>::type
931 bucket_emplace( Args&&... args )
933 class list_accessor: public List
936 using List::alloc_node;
937 using List::node_to_value;
938 using List::insert_node;
941 auto pNode = list_accessor::alloc_node( std::forward<Args>( args )... );
942 assert( pNode != nullptr );
943 return static_cast<list_accessor&>( bucket( list_accessor::node_to_value( *pNode ))).insert_node( pNode );
946 template <typename List, typename... Args>
947 typename std::enable_if< is_iterable_list<List>::value, bool>::type
948 bucket_emplace( Args&&... args )
950 class list_accessor: public List
953 using List::alloc_data;
954 using List::insert_node;
957 auto pData = list_accessor::alloc_data( std::forward<Args>( args )... );
958 assert( pData != nullptr );
959 return static_cast<list_accessor&>( bucket( *pData )).insert_node( pData );
964 }} // namespace cds::container
966 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H