2ecdcf6a696930a70a14a0012b20989e0d464ceb
[libcds.git] / cds / container / michael_set.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8     
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.     
29 */
30
31 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_H
32 #define CDSLIB_CONTAINER_MICHAEL_SET_H
33
34 #include <cds/container/details/michael_set_base.h>
35 #include <cds/details/allocator.h>
36
37 namespace cds { namespace container {
38
39     /// Michael's hash set
40     /** @ingroup cds_nonintrusive_set
41         \anchor cds_nonintrusive_MichaelHashSet_hp
42
43         Source:
44             - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
45
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.
50
51         Template parameters are:
52         - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
53             from the \p libcds library.
54             Note the \p GC must be the same as the \p GC used for \p OrderedList
55         - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList.
56             The ordered list implementation specifies the type \p T to be stored in the hash-set,
57             the comparing functor for the type \p T and other features specific for the ordered list.
58         - \p Traits - set traits, default is \p michael_set::traits.
59             Instead of defining \p Traits struct you may use option-based syntax with \p michael_set::make_traits metafunction.
60
61         There are the specializations:
62         - for \ref cds_urcu_desc "RCU" - declared in <tt>cd/container/michael_set_rcu.h</tt>,
63             see \ref cds_nonintrusive_MichaelHashSet_rcu "MichaelHashSet<RCU>".
64         - for \ref cds::gc::nogc declared in <tt>cds/container/michael_set_nogc.h</tt>,
65             see \ref cds_nonintrusive_MichaelHashSet_nogc "MichaelHashSet<gc::nogc>".
66
67         \anchor cds_nonintrusive_MichaelHashSet_hash_functor
68         <b>Hash functor</b>
69
70         Some member functions of Michael's hash set accept the key parameter of type \p Q which differs from node type \p value_type.
71         It is expected that type \p Q contains full key of node type \p value_type, and if keys of type \p Q and \p value_type
72         are equal the hash values of these keys must be equal too.
73
74         The hash functor \p Traits::hash should accept parameters of both type:
75         \code
76         // Our node type
77         struct Foo {
78             std::string     key_    ;   // key field
79             // ... other fields
80         };
81
82         // Hash functor
83         struct fooHash {
84             size_t operator()( const std::string& s ) const
85             {
86                 return std::hash( s );
87             }
88
89             size_t operator()( const Foo& f ) const
90             {
91                 return (*this)( f.key_ );
92             }
93         };
94         \endcode
95
96         <b>Iterators</b>
97
98         The class supports a forward iterator (\ref iterator and \ref const_iterator).
99         The iteration is unordered.
100         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
101         so, the element cannot be reclaimed while the iterator object is alive.
102         However, passing an iterator object between threads is dangerous.
103
104         @warning Due to concurrent nature of Michael's set it is not guarantee that you can iterate
105         all elements in the set: any concurrent deletion can exclude the element
106         pointed by the iterator from the set, and your iteration can be terminated
107         before end of the set. Therefore, such iteration is more suitable for debugging purpose only
108
109         Remember, each iterator object requires an additional hazard pointer, that may be
110         a limited resource for \p GC like \p gc::HP (for \p gc::DHP the total count of
111         guards is unlimited).
112
113         The iterator class supports the following minimalistic interface:
114         \code
115         struct iterator {
116         // Default ctor
117         iterator();
118
119         // Copy ctor
120         iterator( iterator const& s);
121
122         value_type * operator ->() const;
123         value_type& operator *() const;
124
125         // Pre-increment
126         iterator& operator ++();
127
128         // Copy assignment
129         iterator& operator = (const iterator& src);
130
131         bool operator ==(iterator const& i ) const;
132         bool operator !=(iterator const& i ) const;
133         };
134         \endcode
135         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
136
137         <b>How to use</b>
138
139         Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
140         \code
141         struct Foo {
142             int     nKey    ;   // key field
143             int     nVal    ;   // value field
144         };
145         \endcode
146
147         To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
148         that will be used as a bucket for the set. We will use \p gc::DHP reclamation schema and
149         \p MichaelList as a bucket type. Also, for ordered list we should develop a comparator for our \p Foo
150         struct.
151         \code
152         #include <cds/container/michael_list_dhp.h>
153         #include <cds/container/michael_set.h>
154
155         namespace cc = cds::container;
156
157         // Foo comparator
158         struct Foo_cmp {
159             int operator ()(Foo const& v1, Foo const& v2 ) const
160             {
161                 if ( std::less( v1.nKey, v2.nKey ))
162                     return -1;
163                 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
164             }
165         };
166
167         // Our ordered list
168         typedef cc::MichaelList< cds::gc::DHP, Foo,
169             typename cc::michael_list::make_traits<
170                 cc::opt::compare< Foo_cmp >     // item comparator option
171             >::type
172         > bucket_list;
173
174         // Hash functor for Foo
175         struct foo_hash {
176             size_t operator ()( int i ) const
177             {
178                 return std::hash( i );
179             }
180             size_t operator()( Foo const& i ) const
181             {
182                 return std::hash( i.nKey );
183             }
184         };
185
186         // Declare set type.
187         // Note that \p GC template parameter of ordered list must be equal \p GC for the set.
188         typedef cc::MichaelHashSet< cds::gc::DHP, bucket_list,
189             cc::michael_set::make_traits<
190                 cc::opt::hash< foo_hash >
191             >::type
192         > foo_set;
193
194         // Set variable
195         foo_set fooSet;
196         \endcode
197     */
198     template <
199         class GC,
200         class OrderedList,
201 #ifdef CDS_DOXYGEN_INVOKED
202         class Traits = michael_set::traits
203 #else
204         class Traits
205 #endif
206     >
207     class MichaelHashSet
208     {
209     public:
210         typedef GC          gc;          ///< Garbage collector
211         typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
212         typedef Traits      traits;      ///< Set traits
213
214         typedef typename bucket_type::value_type     value_type;     ///< type of value to be stored in the list
215         typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor
216
217         /// Hash functor for \ref value_type and all its derivatives that you use
218         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
219         typedef typename traits::item_counter item_counter; ///< Item counter type
220
221         /// Bucket table allocator
222         typedef cds::details::Allocator< bucket_type, typename traits::allocator >  bucket_table_allocator;
223
224         typedef typename bucket_type::guarded_ptr  guarded_ptr; ///< Guarded pointer
225
226     protected:
227         item_counter    m_ItemCounter; ///< Item counter
228         hash            m_HashFunctor; ///< Hash functor
229         bucket_type *   m_Buckets;     ///< bucket table
230
231     private:
232         //@cond
233         const size_t    m_nHashBitmask;
234         //@endcond
235
236     protected:
237         //@cond
238         /// Calculates hash value of \p key
239         template <typename Q>
240         size_t hash_value( Q const& key ) const
241         {
242             return m_HashFunctor( key ) & m_nHashBitmask;
243         }
244
245         /// Returns the bucket (ordered list) for \p key
246         template <typename Q>
247         bucket_type&    bucket( Q const& key )
248         {
249             return m_Buckets[ hash_value( key ) ];
250         }
251         //@endcond
252
253     public:
254         /// Forward iterator
255         typedef michael_set::details::iterator< bucket_type, false >    iterator;
256
257         /// Const forward iterator
258         typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
259
260         /// Returns a forward iterator addressing the first element in a set
261         /**
262             For empty set \code begin() == end() \endcode
263         */
264         iterator begin()
265         {
266             return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
267         }
268
269         /// Returns an iterator that addresses the location succeeding the last element in a set
270         /**
271             Do not use the value returned by <tt>end</tt> function to access any item.
272             The returned value can be used only to control reaching the end of the set.
273             For empty set \code begin() == end() \endcode
274         */
275         iterator end()
276         {
277             return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
278         }
279
280         /// Returns a forward const iterator addressing the first element in a set
281         //@{
282         const_iterator begin() const
283         {
284             return get_const_begin();
285         }
286         const_iterator cbegin() const
287         {
288             return get_const_begin();
289         }
290         //@}
291
292         /// Returns an const iterator that addresses the location succeeding the last element in a set
293         //@{
294         const_iterator end() const
295         {
296             return get_const_end();
297         }
298         const_iterator cend() const
299         {
300             return get_const_end();
301         }
302         //@}
303
304     private:
305         //@cond
306         const_iterator get_const_begin() const
307         {
308             return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
309         }
310         const_iterator get_const_end() const
311         {
312             return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
313         }
314         //@endcond
315
316     public:
317         /// Initialize hash set
318         /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor
319             The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
320             when you create an object.
321             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
322             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
323
324             The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
325         */
326         MichaelHashSet(
327             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
328             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
329         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
330         {
331             // GC and OrderedList::gc must be the same
332             static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
333
334             // atomicity::empty_item_counter is not allowed as a item counter
335             static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
336                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
337
338             m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
339         }
340
341         /// Clears hash set and destroys it
342         ~MichaelHashSet()
343         {
344             clear();
345             bucket_table_allocator().Delete( m_Buckets, bucket_count() );
346         }
347
348         /// Inserts new node
349         /**
350             The function creates a node with copy of \p val value
351             and then inserts the node created into the set.
352
353             The type \p Q should contain as minimum the complete key for the node.
354             The object of \ref value_type should be constructible from a value of type \p Q.
355             In trivial case, \p Q is equal to \ref value_type.
356
357             Returns \p true if \p val is inserted into the set, \p false otherwise.
358         */
359         template <typename Q>
360         bool insert( Q const& val )
361         {
362             const bool bRet = bucket( val ).insert( val );
363             if ( bRet )
364                 ++m_ItemCounter;
365             return bRet;
366         }
367
368         /// Inserts new node
369         /**
370             The function allows to split creating of new item into two part:
371             - create item with key only
372             - insert new item into the set
373             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
374
375             The functor signature is:
376             \code
377                 void func( value_type& val );
378             \endcode
379             where \p val is the item inserted.
380             The user-defined functor is called only if the inserting is success.
381
382             @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
383             @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
384             synchronization.
385         */
386         template <typename Q, typename Func>
387         bool insert( Q const& val, Func f )
388         {
389             const bool bRet = bucket( val ).insert( val, f );
390             if ( bRet )
391                 ++m_ItemCounter;
392             return bRet;
393         }
394
395         /// Updates the element
396         /**
397             The operation performs inserting or changing data with lock-free manner.
398
399             If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
400             Otherwise, the functor \p func is called with item found.
401             The functor signature is:
402             \code
403                 struct functor {
404                     void operator()( bool bNew, value_type& item, Q const& val );
405                 };
406             \endcode
407             with arguments:
408             - \p bNew - \p true if the item has been inserted, \p false otherwise
409             - \p item - item of the set
410             - \p val - argument \p val passed into the \p %update() function
411
412             The functor may change non-key fields of the \p item.
413
414             Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
415             \p second is \p true if new item has been added or \p false if the item with \p key
416             already is in the set.
417
418             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
419             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
420             synchronization.
421         */
422         template <typename Q, typename Func>
423         std::pair<bool, bool> update( const Q& val, Func func, bool bAllowUpdate = true )
424         {
425             std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowUpdate );
426             if ( bRet.second )
427                 ++m_ItemCounter;
428             return bRet;
429         }
430         //@cond
431         template <typename Q, typename Func>
432         CDS_DEPRECATED("ensure() is deprecated, use update()")
433         std::pair<bool, bool> ensure( const Q& val, Func func )
434         {
435             return update( val, func, true );
436         }
437         //@endcond
438
439         /// Inserts data of type \p value_type constructed from \p args
440         /**
441             Returns \p true if inserting successful, \p false otherwise.
442         */
443         template <typename... Args>
444         bool emplace( Args&&... args )
445         {
446             bool bRet = bucket( value_type(std::forward<Args>(args)...) ).emplace( std::forward<Args>(args)... );
447             if ( bRet )
448                 ++m_ItemCounter;
449             return bRet;
450         }
451
452         /// Deletes \p key from the set
453         /** \anchor cds_nonintrusive_MichaelSet_erase_val
454
455             Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
456             template parameter \p Q defines the key type searching in the list.
457             The set item comparator should be able to compare the type \p value_type
458             and the type \p Q.
459
460             Return \p true if key is found and deleted, \p false otherwise
461         */
462         template <typename Q>
463         bool erase( Q const& key )
464         {
465             const bool bRet = bucket( key ).erase( key );
466             if ( bRet )
467                 --m_ItemCounter;
468             return bRet;
469         }
470
471         /// Deletes the item from the set using \p pred predicate for searching
472         /**
473             The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
474             but \p pred is used for key comparing.
475             \p Less functor has the interface like \p std::less.
476             \p Less must imply the same element order as the comparator used for building the set.
477         */
478         template <typename Q, typename Less>
479         bool erase_with( Q const& key, Less pred )
480         {
481             const bool bRet = bucket( key ).erase_with( key, pred );
482             if ( bRet )
483                 --m_ItemCounter;
484             return bRet;
485         }
486
487         /// Deletes \p key from the set
488         /** \anchor cds_nonintrusive_MichaelSet_erase_func
489
490             The function searches an item with key \p key, calls \p f functor
491             and deletes the item. If \p key is not found, the functor is not called.
492
493             The functor \p Func interface:
494             \code
495             struct extractor {
496                 void operator()(value_type& item);
497             };
498             \endcode
499             where \p item - the item found.
500
501             Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
502             template parameter \p Q defines the key type searching in the list.
503             The list item comparator should be able to compare the type \p T of list item
504             and the type \p Q.
505
506             Return \p true if key is found and deleted, \p false otherwise
507         */
508         template <typename Q, typename Func>
509         bool erase( Q const& key, Func f )
510         {
511             const bool bRet = bucket( key ).erase( key, f );
512             if ( bRet )
513                 --m_ItemCounter;
514             return bRet;
515         }
516
517         /// Deletes the item from the set using \p pred predicate for searching
518         /**
519             The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
520             but \p pred is used for key comparing.
521             \p Less functor has the interface like \p std::less.
522             \p Less must imply the same element order as the comparator used for building the set.
523         */
524         template <typename Q, typename Less, typename Func>
525         bool erase_with( Q const& key, Less pred, Func f )
526         {
527             const bool bRet = bucket( key ).erase_with( key, pred, f );
528             if ( bRet )
529                 --m_ItemCounter;
530             return bRet;
531         }
532
533         /// Extracts the item with specified \p key
534         /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
535             The function searches an item with key equal to \p key,
536             unlinks it from the set, and returns it as \p guarded_ptr.
537             If \p key is not found the function returns an empty guadd pointer.
538
539             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
540
541             The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
542             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
543
544             Usage:
545             \code
546             typedef cds::container::MichaelHashSet< your_template_args > michael_set;
547             michael_set theSet;
548             // ...
549             {
550                 michael_set::guarded_ptr gp( theSet.extract( 5 ));
551                 if ( gp ) {
552                     // Deal with gp
553                     // ...
554                 }
555                 // Destructor of gp releases internal HP guard
556             }
557             \endcode
558         */
559         template <typename Q>
560         guarded_ptr extract( Q const& key )
561         {
562             guarded_ptr gp( bucket( key ).extract( key ));
563             if ( gp )
564                 --m_ItemCounter;
565             return gp;
566         }
567
568         /// Extracts the item using compare functor \p pred
569         /**
570             The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)"
571             but \p pred predicate is used for key comparing.
572
573             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
574             in any order.
575             \p pred must imply the same element order as the comparator used for building the set.
576         */
577         template <typename Q, typename Less>
578         guarded_ptr extract_with( Q const& key, Less pred )
579         {
580             guarded_ptr gp( bucket( key ).extract_with( key, pred ));
581             if ( gp )
582                 --m_ItemCounter;
583             return gp;
584         }
585
586         /// Finds the key \p key
587         /** \anchor cds_nonintrusive_MichaelSet_find_func
588
589             The function searches the item with key equal to \p key and calls the functor \p f for item found.
590             The interface of \p Func functor is:
591             \code
592             struct functor {
593                 void operator()( value_type& item, Q& key );
594             };
595             \endcode
596             where \p item is the item found, \p key is the <tt>find</tt> function argument.
597
598             The functor may change non-key fields of \p item. Note that the functor is only guarantee
599             that \p item cannot be disposed during functor is executing.
600             The functor does not serialize simultaneous access to the set's \p item. If such access is
601             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
602
603             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
604             can modify both arguments.
605
606             Note the hash functor specified for class \p Traits template parameter
607             should accept a parameter of type \p Q that may be not the same as \p value_type.
608
609             The function returns \p true if \p key is found, \p false otherwise.
610         */
611         template <typename Q, typename Func>
612         bool find( Q& key, Func f )
613         {
614             return bucket( key ).find( key, f );
615         }
616         //@cond
617         template <typename Q, typename Func>
618         bool find( Q const& key, Func f )
619         {
620             return bucket( key ).find( key, f );
621         }
622         //@endcond
623
624         /// Finds the key \p key using \p pred predicate for searching
625         /**
626             The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
627             but \p pred is used for key comparing.
628             \p Less functor has the interface like \p std::less.
629             \p Less must imply the same element order as the comparator used for building the set.
630         */
631         template <typename Q, typename Less, typename Func>
632         bool find_with( Q& key, Less pred, Func f )
633         {
634             return bucket( key ).find_with( key, pred, f );
635         }
636         //@cond
637         template <typename Q, typename Less, typename Func>
638         bool find_with( Q const& key, Less pred, Func f )
639         {
640             return bucket( key ).find_with( key, pred, f );
641         }
642         //@endcond
643
644         /// Checks whether the set contains \p key
645         /**
646
647             The function searches the item with key equal to \p key
648             and returns \p true if the key is found, and \p false otherwise.
649
650             Note the hash functor specified for class \p Traits template parameter
651             should accept a parameter of type \p Q that can be not the same as \p value_type.
652         */
653         template <typename Q>
654         bool contains( Q const& key )
655         {
656             return bucket( key ).contains( key );
657         }
658         //@cond
659         template <typename Q>
660         CDS_DEPRECATED("use contains()")
661         bool find( Q const& key )
662         {
663             return contains( key );
664         }
665         //@endcond
666
667         /// Checks whether the set contains \p key using \p pred predicate for searching
668         /**
669             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
670             \p Less functor has the interface like \p std::less.
671             \p Less must imply the same element order as the comparator used for building the set.
672         */
673         template <typename Q, typename Less>
674         bool contains( Q const& key, Less pred )
675         {
676             return bucket( key ).contains( key, pred );
677         }
678         //@cond
679         template <typename Q, typename Less>
680         CDS_DEPRECATED("use contains()")
681         bool find_with( Q const& key, Less pred )
682         {
683             return contains( key, pred );
684         }
685         //@endcond
686
687         /// Finds the key \p key and return the item found
688         /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
689             The function searches the item with key equal to \p key
690             and returns the guarded pointer to the item found.
691             If \p key is not found the functin returns an empty guarded pointer.
692
693             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
694
695             Usage:
696             \code
697             typedef cds::container::MichaeHashSet< your_template_params >  michael_set;
698             michael_set theSet;
699             // ...
700             {
701                 michael_set::guarded_ptr gp( theSet.get( 5 ));
702                 if ( gp ) {
703                     // Deal with gp
704                     //...
705                 }
706                 // Destructor of guarded_ptr releases internal HP guard
707             }
708             \endcode
709
710             Note the compare functor specified for \p OrderedList template parameter
711             should accept a parameter of type \p Q that can be not the same as \p value_type.
712         */
713         template <typename Q>
714         guarded_ptr get( Q const& key )
715         {
716             return bucket( key ).get( key );
717         }
718
719         /// Finds the key \p key and return the item found
720         /**
721             The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
722             but \p pred is used for comparing the keys.
723
724             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
725             in any order.
726             \p pred must imply the same element order as the comparator used for building the set.
727         */
728         template <typename Q, typename Less>
729         guarded_ptr get_with( Q const& key, Less pred )
730         {
731             return bucket( key ).get_with( key, pred );
732         }
733
734         /// Clears the set (non-atomic)
735         /**
736             The function erases all items from the set.
737
738             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
739             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
740             <tt> empty() </tt> may return \p true but the set may contain item(s).
741             Therefore, \p clear may be used only for debugging purposes.
742         */
743         void clear()
744         {
745             for ( size_t i = 0; i < bucket_count(); ++i )
746                 m_Buckets[i].clear();
747             m_ItemCounter.reset();
748         }
749
750         /// Checks if the set is empty
751         /**
752             Emptiness is checked by item counting: if item count is zero then the set is empty.
753             Thus, the correct item counting feature is an important part of Michael's set implementation.
754         */
755         bool empty() const
756         {
757             return size() == 0;
758         }
759
760         /// Returns item count in the set
761         size_t size() const
762         {
763             return m_ItemCounter;
764         }
765
766         /// Returns the size of hash table
767         /**
768             Since MichaelHashSet cannot dynamically extend the hash table size,
769             the value returned is an constant depending on object initialization parameters;
770             see MichaelHashSet::MichaelHashSet for explanation.
771         */
772         size_t bucket_count() const
773         {
774             return m_nHashBitmask + 1;
775         }
776     };
777
778 }} // namespace cds::container
779
780 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H