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