Merge branch 'master' into dev
[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-2017
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/container/details/iterable_list_base.h>
36 #include <cds/details/allocator.h>
37
38 namespace cds { namespace container {
39
40     /// Michael's hash set
41     /** @ingroup cds_nonintrusive_set
42         \anchor cds_nonintrusive_MichaelHashSet_hp
43
44         Source:
45             - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
46
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.
51
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.
62
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>".
68
69         \anchor cds_nonintrusive_MichaelHashSet_hash_functor
70         <b>Hash functor</b>
71
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.
75
76         The hash functor \p Traits::hash should accept parameters of both type:
77         \code
78         // Our node type
79         struct Foo {
80             std::string     key_;   // key field
81             // ... other fields
82         };
83
84         // Hash functor
85         struct fooHash {
86             size_t operator()( const std::string& s ) const
87             {
88                 return std::hash( s );
89             }
90
91             size_t operator()( const Foo& f ) const
92             {
93                 return (*this)( f.key_ );
94             }
95         };
96         \endcode
97
98         <b>How to use</b>
99
100         Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
101         \code
102         struct Foo {
103             int     nKey;   // key field
104             int     nVal;   // value field
105         };
106         \endcode
107
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
111         struct.
112         \code
113         #include <cds/container/michael_list_dhp.h>
114         #include <cds/container/michael_set.h>
115
116         namespace cc = cds::container;
117
118         // Foo comparator
119         struct Foo_cmp {
120             int operator ()(Foo const& v1, Foo const& v2 ) const
121             {
122                 if ( std::less( v1.nKey, v2.nKey ))
123                     return -1;
124                 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
125             }
126         };
127
128         // Our ordered list
129         typedef cc::MichaelList< cds::gc::DHP, Foo,
130             typename cc::michael_list::make_traits<
131                 cc::opt::compare< Foo_cmp >     // item comparator option
132             >::type
133         > bucket_list;
134
135         // Hash functor for Foo
136         struct foo_hash {
137             size_t operator ()( int i ) const
138             {
139                 return std::hash( i );
140             }
141             size_t operator()( Foo const& i ) const
142             {
143                 return std::hash( i.nKey );
144             }
145         };
146
147         // Declare set type.
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 >
152             >::type
153         > foo_set;
154
155         // Set variable
156         foo_set fooSet;
157         \endcode
158     */
159     template <
160         class GC,
161         class OrderedList,
162 #ifdef CDS_DOXYGEN_INVOKED
163         class Traits = michael_set::traits
164 #else
165         class Traits
166 #endif
167     >
168     class MichaelHashSet
169     {
170     public:
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
174
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
179 #endif
180
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
185
186         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
187
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");
190
191         //@cond
192         typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
193
194         typedef typename ordered_list::template rebind_traits<
195             cds::opt::item_counter< cds::atomicity::empty_item_counter >
196             , cds::opt::stat< typename bucket_stat::wrapped_stat >
197         >::type internal_bucket_type;
198
199         /// Bucket table allocator
200         typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
201
202         typedef typename bucket_stat::stat stat;
203         //@endcond
204
205         /// Guarded pointer - a result of \p get() and \p extract() functions
206         typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
207
208     protected:
209         //@cond
210         size_t const           m_nHashBitmask;
211         internal_bucket_type * m_Buckets;     ///< bucket table
212         hash                   m_HashFunctor; ///< Hash functor
213         item_counter           m_ItemCounter; ///< Item counter
214         stat                   m_Stat;        ///< Internal statistics
215         //@endcond
216
217     public:
218     ///@name Forward iterators
219     //@{
220         /// Forward iterator
221         /**
222             The forward iterator for Michael's set has some features:
223             - it has no post-increment operator
224             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
225               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
226               may be thrown if the limit of guard count per thread is exceeded.
227             - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
228
229             Iterator thread safety depends on type of \p OrderedList:
230             - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
231               because that item is guarded by hazard pointer.
232               However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
233               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
234               Use this iterator on the concurrent container for debugging purpose only.
235             - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
236
237             The iterator interface:
238             \code
239             class iterator {
240             public:
241                 // Default constructor
242                 iterator();
243
244                 // Copy construtor
245                 iterator( iterator const& src );
246
247                 // Dereference operator
248                 value_type * operator ->() const;
249
250                 // Dereference operator
251                 value_type& operator *() const;
252
253                 // Preincrement operator
254                 iterator& operator ++();
255
256                 // Assignment operator
257                 iterator& operator = (iterator const& src);
258
259                 // Equality operators
260                 bool operator ==(iterator const& i ) const;
261                 bool operator !=(iterator const& i ) const;
262             };
263             \endcode
264         */
265
266         /// Forward iterator
267         typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
268
269         /// Const forward iterator
270         typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
271
272         /// Returns a forward iterator addressing the first element in a set
273         /**
274             For empty set \code begin() == end() \endcode
275         */
276         iterator begin()
277         {
278             return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
279         }
280
281         /// Returns an iterator that addresses the location succeeding the last element in a set
282         /**
283             Do not use the value returned by <tt>end</tt> function to access any item.
284             The returned value can be used only to control reaching the end of the set.
285             For empty set \code begin() == end() \endcode
286         */
287         iterator end()
288         {
289             return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
290         }
291
292         /// Returns a forward const iterator addressing the first element in a set
293         const_iterator begin() const
294         {
295             return get_const_begin();
296         }
297
298         /// Returns a forward const iterator addressing the first element in a set
299         const_iterator cbegin() const
300         {
301             return get_const_begin();
302         }
303
304         /// Returns an const iterator that addresses the location succeeding the last element in a set
305         const_iterator end() const
306         {
307             return get_const_end();
308         }
309
310         /// Returns an const iterator that addresses the location succeeding the last element in a set
311         const_iterator cend() const
312         {
313             return get_const_end();
314         }
315     //@}
316
317     public:
318         /// Initialize hash set
319         /**
320             The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
321             when you create an object.
322             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
323             Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
324
325             The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
326         */
327         MichaelHashSet(
328             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
329             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
330         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
331           , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
332         {
333             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
334                 construct_bucket<bucket_stat>( it );
335         }
336
337         /// Clears hash set and destroys it
338         ~MichaelHashSet()
339         {
340             clear();
341
342             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
343                 it->~internal_bucket_type();
344             bucket_table_allocator().deallocate( m_Buckets, bucket_count());
345         }
346
347         /// Inserts new node
348         /**
349             The function creates a node with copy of \p val value
350             and then inserts the node created into the set.
351
352             The type \p Q should contain as minimum the complete key for the node.
353             The object of \ref value_type should be constructible from a value of type \p Q.
354             In trivial case, \p Q is equal to \ref value_type.
355
356             Returns \p true if \p val is inserted into the set, \p false otherwise.
357         */
358         template <typename Q>
359         bool insert( Q&& val )
360         {
361             const bool bRet = bucket( val ).insert( std::forward<Q>( val ));
362             if ( bRet )
363                 ++m_ItemCounter;
364             return bRet;
365         }
366
367         /// Inserts new node
368         /**
369             The function allows to split creating of new item into two part:
370             - create item with key only
371             - insert new item into the set
372             - if inserting is success, calls  \p f functor to initialize value-fields of \p val.
373
374             The functor signature is:
375             \code
376                 void func( value_type& val );
377             \endcode
378             where \p val is the item inserted.
379             The user-defined functor is called only if the inserting is success.
380
381             @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
382             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&& val, Func f )
388         {
389             const bool bRet = bucket( val ).insert( std::forward<Q>( 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
402             The functor \p func signature depends of \p OrderedList:
403
404             <b>for \p MichaelList, \p LazyList</b>
405             \code
406                 struct functor {
407                     void operator()( bool bNew, value_type& item, Q const& val );
408                 };
409             \endcode
410             with arguments:
411             - \p bNew - \p true if the item has been inserted, \p false otherwise
412             - \p item - item of the set
413             - \p val - argument \p val passed into the \p %update() function
414
415             The functor may change non-key fields of the \p item.
416
417             <b>for \p IterableList</b>
418             \code
419                 void func( value_type& val, value_type * old );
420             \endcode
421             where
422             - \p val - a new data constructed from \p key
423             - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
424
425             @return <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
426             \p second is \p true if new item has been added or \p false if the item with \p key
427             already is in the set.
428
429             @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
430             as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
431             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
432             synchronization.
433         */
434         template <typename Q, typename Func>
435         std::pair<bool, bool> update( Q&& val, Func func, bool bAllowUpdate = true )
436         {
437             std::pair<bool, bool> bRet = bucket( val ).update( std::forward<Q>( val ), func, bAllowUpdate );
438             if ( bRet.second )
439                 ++m_ItemCounter;
440             return bRet;
441         }
442         //@cond
443         template <typename Q, typename Func>
444         CDS_DEPRECATED("ensure() is deprecated, use update()")
445         std::pair<bool, bool> ensure( const Q& val, Func func )
446         {
447             return update( val, func, true );
448         }
449         //@endcond
450
451         /// Inserts or updates the node (only for \p IterableList)
452         /**
453             The operation performs inserting or changing data with lock-free manner.
454
455             If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
456             Otherwise, the current element is changed to \p val, the old element will be retired later.
457
458             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
459             \p second is \p true if \p val has been added or \p false if the item with that key
460             already in the set.
461         */
462         template <typename Q>
463 #ifdef CDS_DOXYGEN_INVOKED
464         std::pair<bool, bool>
465 #else
466         typename std::enable_if<
467             std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
468             std::pair<bool, bool>
469         >::type
470 #endif
471         upsert( Q&& val, bool bAllowInsert = true )
472         {
473             std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( val ), bAllowInsert );
474             if ( bRet.second )
475                 ++m_ItemCounter;
476             return bRet;
477         }
478
479         /// Inserts data of type \p value_type constructed from \p args
480         /**
481             Returns \p true if inserting successful, \p false otherwise.
482         */
483         template <typename... Args>
484         bool emplace( Args&&... args )
485         {
486             bool bRet = bucket_emplace<internal_bucket_type>( std::forward<Args>(args)... );
487             if ( bRet )
488                 ++m_ItemCounter;
489             return bRet;
490         }
491
492         /// Deletes \p key from the set
493         /**
494             Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
495             template parameter \p Q defines the key type searching in the list.
496             The set item comparator should be able to compare the type \p value_type
497             and the type \p Q.
498
499             Return \p true if key is found and deleted, \p false otherwise.
500         */
501         template <typename Q>
502         bool erase( Q const& key )
503         {
504             const bool bRet = bucket( key ).erase( key );
505             if ( bRet )
506                 --m_ItemCounter;
507             return bRet;
508         }
509
510         /// Deletes the item from the set using \p pred predicate for searching
511         /**
512             The function is an analog of \p erase(Q const&) but \p pred is used for key comparing.
513             \p Less functor has the interface like \p std::less.
514             \p Less must imply the same element order as the comparator used for building the set.
515         */
516         template <typename Q, typename Less>
517         bool erase_with( Q const& key, Less pred )
518         {
519             const bool bRet = bucket( key ).erase_with( key, pred );
520             if ( bRet )
521                 --m_ItemCounter;
522             return bRet;
523         }
524
525         /// Deletes \p key from the set
526         /**
527             The function searches an item with key \p key, calls \p f functor
528             and deletes the item. If \p key is not found, the functor is not called.
529
530             The functor \p Func interface:
531             \code
532             struct extractor {
533                 void operator()(value_type& item);
534             };
535             \endcode
536             where \p item - the item found.
537
538             Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
539             template parameter \p Q defines the key type searching in the list.
540             The list item comparator should be able to compare the type \p T of list item
541             and the type \p Q.
542
543             Return \p true if key is found and deleted, \p false otherwise
544         */
545         template <typename Q, typename Func>
546         bool erase( Q const& key, Func f )
547         {
548             const bool bRet = bucket( key ).erase( key, f );
549             if ( bRet )
550                 --m_ItemCounter;
551             return bRet;
552         }
553
554         /// Deletes the item from the set using \p pred predicate for searching
555         /**
556             The function is an analog of \p erase(Q const&, Func) but \p pred is used for key comparing.
557             \p Less functor has the interface like \p std::less.
558             \p Less must imply the same element order as the comparator used for building the set.
559         */
560         template <typename Q, typename Less, typename Func>
561         bool erase_with( Q const& key, Less pred, Func f )
562         {
563             const bool bRet = bucket( key ).erase_with( key, pred, f );
564             if ( bRet )
565                 --m_ItemCounter;
566             return bRet;
567         }
568
569         /// Deletes the item pointed by iterator \p iter (only for \p IterableList based set)
570         /**
571             Returns \p true if the operation is successful, \p false otherwise.
572             The function can return \p false if the node the iterator points to has already been deleted
573             by other thread.
574
575             The function does not invalidate the iterator, it remains valid and can be used for further traversing.
576
577             @note \p %erase_at() is supported only for \p %MichaelHashSet based on \p IterableList.
578         */
579 #ifdef CDS_DOXYGEN_INVOKED
580         bool erase_at( iterator const& iter )
581 #else
582         template <typename Iterator>
583         typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
584         erase_at( Iterator const& iter )
585 #endif
586         {
587             assert( iter != end());
588             assert( iter.bucket() != nullptr );
589
590             if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
591                 --m_ItemCounter;
592                 return true;
593             }
594             return false;
595         }
596
597         /// Extracts the item with specified \p key
598         /** \anchor cds_nonintrusive_MichaelHashSet_hp_extract
599             The function searches an item with key equal to \p key,
600             unlinks it from the set, and returns it as \p guarded_ptr.
601             If \p key is not found the function returns an empty guadd pointer.
602
603             Note the compare functor should accept a parameter of type \p Q that may be not the same as \p value_type.
604
605             The extracted item is freed automatically when returned \p guarded_ptr object will be destroyed or released.
606             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
607
608             Usage:
609             \code
610             typedef cds::container::MichaelHashSet< your_template_args > michael_set;
611             michael_set theSet;
612             // ...
613             {
614                 typename michael_set::guarded_ptr gp( theSet.extract( 5 ));
615                 if ( gp ) {
616                     // Deal with gp
617                     // ...
618                 }
619                 // Destructor of gp releases internal HP guard
620             }
621             \endcode
622         */
623         template <typename Q>
624         guarded_ptr extract( Q const& key )
625         {
626             guarded_ptr gp( bucket( key ).extract( key ));
627             if ( gp )
628                 --m_ItemCounter;
629             return gp;
630         }
631
632         /// Extracts the item using compare functor \p pred
633         /**
634             The function is an analog of \p extract(Q const&)
635             but \p pred predicate is used for key comparing.
636
637             \p Less functor has the semantics like \p std::less but should take arguments
638             of type \p value_type and \p Q in any order.
639             \p pred must imply the same element order as the comparator used for building the set.
640         */
641         template <typename Q, typename Less>
642         guarded_ptr extract_with( Q const& key, Less pred )
643         {
644             guarded_ptr gp( bucket( key ).extract_with( key, pred ));
645             if ( gp )
646                 --m_ItemCounter;
647             return gp;
648         }
649
650         /// Finds the key \p key
651         /**
652             The function searches the item with key equal to \p key and calls the functor \p f for item found.
653             The interface of \p Func functor is:
654             \code
655             struct functor {
656                 void operator()( value_type& item, Q& key );
657             };
658             \endcode
659             where \p item is the item found, \p key is the <tt>find</tt> function argument.
660
661             The functor may change non-key fields of \p item. Note that the functor is only guarantee
662             that \p item cannot be disposed during functor is executing.
663             The functor does not serialize simultaneous access to the set's \p item. If such access is
664             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
665
666             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
667             can modify both arguments.
668
669             Note the hash functor specified for class \p Traits template parameter
670             should accept a parameter of type \p Q that may be not the same as \p value_type.
671
672             The function returns \p true if \p key is found, \p false otherwise.
673         */
674         template <typename Q, typename Func>
675         bool find( Q& key, Func f )
676         {
677             return bucket( key ).find( key, f );
678         }
679         //@cond
680         template <typename Q, typename Func>
681         bool find( Q const& key, Func f )
682         {
683             return bucket( key ).find( key, f );
684         }
685         //@endcond
686
687         /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
688         /**
689             If \p key is not found the function returns \p end().
690
691             @note This function is supported only for the set based on \p IterableList
692         */
693         template <typename Q>
694 #ifdef CDS_DOXYGEN_INVOKED
695         iterator
696 #else
697         typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
698 #endif
699         find( Q& key )
700         {
701             internal_bucket_type& b = bucket( key );
702             typename internal_bucket_type::iterator it = b.find( key );
703             if ( it == b.end())
704                 return end();
705             return iterator( it, &b, bucket_end());
706         }
707         //@cond
708         template <typename Q>
709         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
710         find( Q const& key )
711         {
712             internal_bucket_type& b = bucket( key );
713             typename internal_bucket_type::iterator it = b.find( key );
714             if ( it == b.end())
715                 return end();
716             return iterator( it, &b, bucket_end());
717         }
718         //@endcond
719
720         /// Finds the key \p key using \p pred predicate for searching
721         /**
722             The function is an analog of \p find(Q&, Func) but \p pred is used for key comparing.
723             \p Less functor has the interface like \p std::less.
724             \p Less must imply the same element order as the comparator used for building the set.
725         */
726         template <typename Q, typename Less, typename Func>
727         bool find_with( Q& key, Less pred, Func f )
728         {
729             return bucket( key ).find_with( key, pred, f );
730         }
731         //@cond
732         template <typename Q, typename Less, typename Func>
733         bool find_with( Q const& key, Less pred, Func f )
734         {
735             return bucket( key ).find_with( key, pred, f );
736         }
737         //@endcond
738
739         /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
740         /**
741             The function is an analog of \p find(Q&) but \p pred is used for key comparing.
742             \p Less functor has the interface like \p std::less.
743             \p pred must imply the same element order as the comparator used for building the set.
744
745             If \p key is not found the function returns \p end().
746
747             @note This function is supported only for the set based on \p IterableList
748         */
749         template <typename Q, typename Less>
750 #ifdef CDS_DOXYGEN_INVOKED
751         iterator
752 #else
753         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
754 #endif
755         find_with( Q& key, Less pred )
756         {
757             internal_bucket_type& b = bucket( key );
758             typename internal_bucket_type::iterator it = b.find_with( key, pred );
759             if ( it == b.end())
760                 return end();
761             return iterator( it, &b, bucket_end());
762         }
763         //@cond
764         template <typename Q, typename Less>
765         typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
766         find_with( Q const& key, Less pred )
767         {
768             internal_bucket_type& b = bucket( key );
769             typename internal_bucket_type::iterator it = b.find_with( key, pred );
770             if ( it == b.end())
771                 return end();
772             return iterator( it, &b, bucket_end());
773         }
774         //@endcond
775
776         /// Checks whether the set contains \p key
777         /**
778             The function searches the item with key equal to \p key
779             and returns \p true if the key is found, and \p false otherwise.
780
781             Note the hash functor specified for class \p Traits template parameter
782             should accept a parameter of type \p Q that can be not the same as \p value_type.
783         */
784         template <typename Q>
785         bool contains( Q const& key )
786         {
787             return bucket( key ).contains( key );
788         }
789
790         /// Checks whether the set contains \p key using \p pred predicate for searching
791         /**
792             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
793             \p Less functor has the interface like \p std::less.
794             \p Less must imply the same element order as the comparator used for building the set.
795         */
796         template <typename Q, typename Less>
797         bool contains( Q const& key, Less pred )
798         {
799             return bucket( key ).contains( key, pred );
800         }
801
802         /// Finds the key \p key and return the item found
803         /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
804             The function searches the item with key equal to \p key
805             and returns the guarded pointer to the item found.
806             If \p key is not found the functin returns an empty guarded pointer.
807
808             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
809
810             Usage:
811             \code
812             typedef cds::container::MichaeHashSet< your_template_params >  michael_set;
813             michael_set theSet;
814             // ...
815             {
816                 typename michael_set::guarded_ptr gp( theSet.get( 5 ));
817                 if ( gp ) {
818                     // Deal with gp
819                     //...
820                 }
821                 // Destructor of guarded_ptr releases internal HP guard
822             }
823             \endcode
824
825             Note the compare functor specified for \p OrderedList template parameter
826             should accept a parameter of type \p Q that can be not the same as \p value_type.
827         */
828         template <typename Q>
829         guarded_ptr get( Q const& key )
830         {
831             return bucket( key ).get( key );
832         }
833
834         /// Finds the key \p key and return the item found
835         /**
836             The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_get "get( Q const&)"
837             but \p pred is used for comparing the keys.
838
839             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
840             in any order.
841             \p pred must imply the same element order as the comparator used for building the set.
842         */
843         template <typename Q, typename Less>
844         guarded_ptr get_with( Q const& key, Less pred )
845         {
846             return bucket( key ).get_with( key, pred );
847         }
848
849         /// Clears the set (non-atomic)
850         /**
851             The function erases all items from the set.
852
853             The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
854             If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
855             <tt> empty() </tt> may return \p true but the set may contain item(s).
856             Therefore, \p clear may be used only for debugging purposes.
857         */
858         void clear()
859         {
860             for ( size_t i = 0; i < bucket_count(); ++i )
861                 m_Buckets[i].clear();
862             m_ItemCounter.reset();
863         }
864
865         /// Checks if the set is empty
866         /**
867             @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
868             the function always returns \p true.
869         */
870         bool empty() const
871         {
872             return size() == 0;
873         }
874
875         /// Returns item count in the set
876         /**
877             @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
878             the function always returns 0.
879         */
880         size_t size() const
881         {
882             return m_ItemCounter;
883         }
884
885         /// Returns const reference to internal statistics
886         stat const& statistics() const
887         {
888             return m_Stat;
889         }
890
891         /// Returns the size of hash table
892         /**
893             Since MichaelHashSet cannot dynamically extend the hash table size,
894             the value returned is an constant depending on object initialization parameters;
895             see MichaelHashSet::MichaelHashSet for explanation.
896         */
897         size_t bucket_count() const
898         {
899             return m_nHashBitmask + 1;
900         }
901
902     protected:
903         //@cond
904         /// Calculates hash value of \p key
905         template <typename Q>
906         size_t hash_value( Q const& key ) const
907         {
908             return m_HashFunctor( key ) & m_nHashBitmask;
909         }
910
911         /// Returns the bucket (ordered list) for \p key
912         template <typename Q>
913         internal_bucket_type& bucket( Q const& key )
914         {
915             return m_Buckets[ hash_value( key ) ];
916         }
917         template <typename Q>
918         internal_bucket_type const& bucket( Q const& key ) const
919         {
920             return m_Buckets[hash_value( key )];
921         }
922         //@endcond
923
924     private:
925         //@cond
926         internal_bucket_type* bucket_begin() const
927         {
928             return m_Buckets;
929         }
930
931         internal_bucket_type* bucket_end() const
932         {
933             return m_Buckets + bucket_count();
934         }
935
936         const_iterator get_const_begin() const
937         {
938             return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end());
939         }
940         const_iterator get_const_end() const
941         {
942             return const_iterator(( bucket_end() -1 )->cend(), bucket_end() - 1, bucket_end());
943         }
944
945         template <typename Stat>
946         typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
947         {
948             new (bucket) internal_bucket_type;
949         }
950
951         template <typename Stat>
952         typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
953         {
954             new (bucket) internal_bucket_type( m_Stat );
955         }
956
957         template <typename List, typename... Args>
958         typename std::enable_if< !is_iterable_list<List>::value, bool>::type
959         bucket_emplace( Args&&... args )
960         {
961             class list_accessor: public List
962             {
963             public:
964                 using List::alloc_node;
965                 using List::node_to_value;
966                 using List::insert_node;
967             };
968
969             auto pNode = list_accessor::alloc_node( std::forward<Args>( args )... );
970             assert( pNode != nullptr );
971             return static_cast<list_accessor&>( bucket( list_accessor::node_to_value( *pNode ))).insert_node( pNode );
972         }
973
974         template <typename List, typename... Args>
975         typename std::enable_if< is_iterable_list<List>::value, bool>::type
976         bucket_emplace( Args&&... args )
977         {
978             class list_accessor: public List
979             {
980             public:
981                 using List::alloc_data;
982                 using List::insert_node;
983             };
984
985             auto pData = list_accessor::alloc_data( std::forward<Args>( args )... );
986             assert( pData != nullptr );
987             return static_cast<list_accessor&>( bucket( *pData )).insert_node( pData );
988         }
989         //@endcond
990     };
991
992 }} // namespace cds::container
993
994 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_H