605f2a43e6c656a77ba62edc8af3610aa94c3edb
[libcds.git] / cds / container / cuckoo_set.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_CONTAINER_CUCKOO_SET_H
4 #define __CDS_CONTAINER_CUCKOO_SET_H
5
6 #include <cds/container/details/cuckoo_base.h>
7 #include <cds/details/binary_functor_wrapper.h>
8
9 namespace cds { namespace container {
10
11     //@cond
12     namespace details {
13         template <typename T, typename Traits>
14         struct make_cuckoo_set
15         {
16             typedef T value_type;
17             typedef Traits original_type_traits;
18             typedef typename original_type_traits::probeset_type probeset_type;
19             static bool const store_hash = original_type_traits::store_hash;
20             static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_type_traits::hash::hash_tuple_type >::value) : 0;
21
22             struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
23             {
24                 value_type  m_val;
25
26                 template <typename Q>
27                 node_type( Q const& v )
28                     : m_val(v)
29                 {}
30
31                 template <typename... Args>
32                 node_type( Args&&... args )
33                     : m_val( std::forward<Args>(args)...)
34                 {}
35             };
36
37             struct value_accessor {
38                 value_type const& operator()( node_type const& node ) const
39                 {
40                     return node.m_val;
41                 }
42             };
43
44             template <typename Pred, typename ReturnValue>
45             using predicate_wrapper = cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >;
46
47             struct intrusive_traits: public original_type_traits
48             {
49                 typedef intrusive::cuckoo::base_hook<
50                     cds::intrusive::cuckoo::probeset_type< probeset_type >
51                     ,cds::intrusive::cuckoo::store_hash< store_hash_count >
52                 >  hook;
53
54                 typedef cds::intrusive::cuckoo::type_traits::disposer   disposer;
55
56                 typedef typename std::conditional<
57                     std::is_same< typename original_type_traits::equal_to, opt::none >::value
58                     , opt::none
59                     , predicate_wrapper< typename original_type_traits::equal_to, bool >
60                 >::type equal_to;
61
62                 typedef typename std::conditional<
63                     std::is_same< typename original_type_traits::compare, opt::none >::value
64                     , opt::none
65                     , predicate_wrapper< typename original_type_traits::compare, int >
66                 >::type compare;
67
68                 typedef typename std::conditional<
69                     std::is_same< typename original_type_traits::less, opt::none >::value
70                     ,opt::none
71                     ,predicate_wrapper< typename original_type_traits::less, bool >
72                 >::type less;
73
74                 typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, value_accessor >    hash;
75             };
76
77             typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
78         };
79     } // namespace details
80     //@endcond
81
82     /// Cuckoo hash set
83     /** @ingroup cds_nonintrusive_set
84
85         Source
86             - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
87             - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
88
89         <b>About Cuckoo hashing</b>
90
91             [From "The Art of Multiprocessor Programming"]
92             Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
93             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
94             N = 2k we use a two-entry array of tables, and two independent hash functions,
95             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
96             mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
97             <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
98             equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
99             or <tt>table[1][h1(x)]</tt>, ad removes it if found.
100
101             The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
102             To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
103             If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
104             for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
105             was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
106             until it finds an empty slot. We might not find an empty slot, either because the table is full,
107             or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
108             number of successive displacements we are willing to undertake. When this limit is exceeded,
109             we resize the hash table, choose new hash functions and start over.
110
111             For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
112             items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
113             of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
114             tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
115             holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
116             set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
117
118             In current implementation, a probe set can be defined either as a (single-linked) list
119             or as a fixed-sized vector, optionally ordered.
120
121             In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
122             We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
123             <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
124
125             The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
126             The probe set may be ordered or not. Ordered probe set can be a little better since
127             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
128             However, the overhead of sorting can eliminate a gain of ordered search.
129
130             The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
131             declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
132             opt::equal_to option.
133
134         Template arguments:
135         - \p T - the type stored in the set.
136         - \p Traits - type traits. See cuckoo::type_traits for explanation.
137             It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
138
139         Template argument list \p Options... of cuckoo::make_traits metafunction are:
140         - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
141             should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
142             The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
143             the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
144             then k is unlimited, otherwise up to 10 different hash functors are supported.
145         - opt::mutex_policy - concurrent access policy.
146             Available policies: cuckoo::striping, cuckoo::refinable.
147             Default is cuckoo::striping.
148         - opt::equal_to - key equality functor like \p std::equal_to.
149             If this functor is defined then the probe-set will be unordered.
150             If opt::compare or opt::less option is specified too, then the probe-set will be ordered
151             and opt::equal_to will be ignored.
152         - opt::compare - key comparison functor. No default functor is provided.
153             If the option is not specified, the opt::less is used.
154             If opt::compare or opt::less option is specified, then the probe-set will be ordered.
155         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
156             If opt::compare or opt::less option is specified, then the probe-set will be ordered.
157         - opt::item_counter - the type of item counting feature. Default is \ref opt::v::sequential_item_counter.
158         - opt::allocator - the allocator type using for allocating bucket tables.
159             Default is \p CDS_DEFAULT_ALLOCATOR
160         - opt::node_allocator - the allocator type using for allocating set's items. If this option
161             is not specified then the type defined in opt::allocator option is used.
162         - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
163             of the object once it's introduced in the container. When this option is used,
164             the unordered container will store the calculated hash value in the node and rehashing operations won't need
165             to recalculate the hash of the value. This option will improve the performance of unordered containers
166             when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
167         - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
168             Default is \p cuckoo::list.
169         - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
170             Default is cuckoo::empty_stat
171
172         <b>Examples</b>
173
174         Cuckoo-set with list-based unordered probe set and storing hash values
175         \code
176         #include <cds/container/cuckoo_set.h>
177
178         // Data stored in cuckoo set
179         struct my_data
180         {
181             // key field
182             std::string     strKey;
183
184             // other data
185             // ...
186         };
187
188         // Provide equal_to functor for my_data since we will use unordered probe-set
189         struct my_data_equal_to {
190             bool operator()( const my_data& d1, const my_data& d2 ) const
191             {
192                 return d1.strKey.compare( d2.strKey ) == 0;
193             }
194
195             bool operator()( const my_data& d, const std::string& s ) const
196             {
197                 return d.strKey.compare(s) == 0;
198             }
199
200             bool operator()( const std::string& s, const my_data& d ) const
201             {
202                 return s.compare( d.strKey ) == 0;
203             }
204         };
205
206         // Provide two hash functor for my_data
207         struct hash1 {
208             size_t operator()(std::string const& s) const
209             {
210                 return cds::opt::v::hash<std::string>( s );
211             }
212             size_t operator()( my_data const& d ) const
213             {
214                 return (*this)( d.strKey );
215             }
216         };
217
218         struct hash2: private hash1 {
219             size_t operator()(std::string const& s) const
220             {
221                 size_t h = ~( hash1::operator()(s));
222                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
223             }
224             size_t operator()( my_data const& d ) const
225             {
226                 return (*this)( d.strKey );
227             }
228         };
229
230         // Declare type traits
231         struct my_traits: public cds::container::cuckoo::type_traits
232         {
233             typedef my_data_equa_to equal_to;
234             typedef std::tuple< hash1, hash2 >  hash;
235
236             static bool const store_hash = true;
237         };
238
239         // Declare CuckooSet type
240         typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
241
242         // Equal option-based declaration
243         typedef cds::container::CuckooSet< my_data,
244             cds::container::cuckoo::make_traits<
245                 cds::opt::hash< std::tuple< hash1, hash2 > >
246                 ,cds::opt::equal_to< my_data_equal_to >
247                 ,cds::container::cuckoo::store_hash< true >
248             >::type
249         > opt_cuckoo_set;
250         \endcode
251
252         If we provide \p compare function instead of \p equal_to for \p my_data
253         we get as a result a cuckoo set with ordered probe set that may improve
254         performance.
255         Example for ordered vector-based probe-set:
256
257         \code
258         #include <cds/container/cuckoo_set.h>
259
260         // Data stored in cuckoo set
261         struct my_data
262         {
263             // key field
264             std::string     strKey;
265
266             // other data
267             // ...
268         };
269
270         // Provide compare functor for my_data since we want to use ordered probe-set
271         struct my_data_compare {
272             int operator()( const my_data& d1, const my_data& d2 ) const
273             {
274                 return d1.strKey.compare( d2.strKey );
275             }
276
277             int operator()( const my_data& d, const std::string& s ) const
278             {
279                 return d.strKey.compare(s);
280             }
281
282             int operator()( const std::string& s, const my_data& d ) const
283             {
284                 return s.compare( d.strKey );
285             }
286         };
287
288         // Provide two hash functor for my_data
289         struct hash1 {
290             size_t operator()(std::string const& s) const
291             {
292                 return cds::opt::v::hash<std::string>( s );
293             }
294             size_t operator()( my_data const& d ) const
295             {
296                 return (*this)( d.strKey );
297             }
298         };
299
300         struct hash2: private hash1 {
301             size_t operator()(std::string const& s) const
302             {
303                 size_t h = ~( hash1::operator()(s));
304                 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
305             }
306             size_t operator()( my_data const& d ) const
307             {
308                 return (*this)( d.strKey );
309             }
310         };
311
312         // Declare type traits
313         // We use a vector of capacity 4 as probe-set container and store hash values in the node
314         struct my_traits: public cds::container::cuckoo::type_traits
315         {
316             typedef my_data_compare compare;
317             typedef std::tuple< hash1, hash2 >  hash;
318             typedef cds::container::cuckoo::vector<4> probeset_type;
319
320             static bool const store_hash = true;
321         };
322
323         // Declare CuckooSet type
324         typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
325
326         // Equal option-based declaration
327         typedef cds::container::CuckooSet< my_data,
328             cds::container::cuckoo::make_traits<
329                 cds::opt::hash< std::tuple< hash1, hash2 > >
330                 ,cds::opt::compare< my_data_compare >
331                 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
332                 ,cds::container::cuckoo::store_hash< true >
333             >::type
334         > opt_cuckoo_set;
335         \endcode
336
337     */
338     template <typename T, typename Traits = cuckoo::type_traits>
339     class CuckooSet:
340 #ifdef CDS_DOXYGEN_INVOKED
341         protected intrusive::CuckooSet<T, Traits>
342 #else
343         protected details::make_cuckoo_set<T, Traits>::type
344 #endif
345     {
346         //@cond
347         typedef details::make_cuckoo_set<T, Traits> maker;
348         typedef typename maker::type  base_class;
349         //@endcond
350
351     public:
352         typedef T       value_type  ;   ///< value type stored in the container
353         typedef Traits  options     ;   ///< traits
354
355         typedef typename options::hash                  hash            ;   ///< hash functor tuple wrapped for internal use
356         typedef typename base_class::hash_tuple_type    hash_tuple_type ;   ///< Type of hash tuple
357
358         typedef typename base_class::mutex_policy       mutex_policy    ;   ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
359         typedef typename base_class::stat               stat            ;   ///< internal statistics type
360
361
362         static bool const c_isSorted = base_class::c_isSorted   ; ///< whether the probe set should be ordered
363         static size_t const c_nArity = base_class::c_nArity     ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
364
365         typedef typename base_class::key_equal_to key_equal_to  ; ///< Key equality functor; used only for unordered probe-set
366
367         typedef typename base_class::key_comparator  key_comparator ; ///< key comparing functor based on opt::compare and opt::less option setter. Used only for ordered probe set
368
369         typedef typename base_class::allocator     allocator   ; ///< allocator type used for internal bucket table allocations
370
371         /// Node allocator type
372         typedef typename std::conditional<
373             std::is_same< typename options::node_allocator, opt::none >::value,
374             allocator,
375             typename options::node_allocator
376         >::type node_allocator;
377
378         /// item counter type
379         typedef typename options::item_counter  item_counter;
380
381     protected:
382         //@cond
383         typedef typename base_class::value_type         node_type;
384         typedef cds::details::Allocator< node_type, node_allocator >    cxx_node_allocator;
385         //@endcond
386
387     public:
388         static unsigned int const   c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ;   ///< default probeset size
389         static size_t const         c_nDefaultInitialSize = base_class::c_nDefaultInitialSize   ;   ///< default initial size
390         static unsigned int const   c_nRelocateLimit = base_class::c_nRelocateLimit             ;   ///< Count of attempts to relocate before giving up
391
392     protected:
393         //@cond
394         template <typename Q>
395         static node_type * alloc_node( Q const& v )
396         {
397             return cxx_node_allocator().New( v );
398         }
399         template <typename... Args>
400         static node_type * alloc_node( Args&&... args )
401         {
402             return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
403         }
404
405         static void free_node( node_type * pNode )
406         {
407             cxx_node_allocator().Delete( pNode );
408         }
409         //@endcond
410
411     protected:
412         //@cond
413         struct node_disposer {
414             void operator()( node_type * pNode )
415             {
416                 free_node( pNode );
417             }
418         };
419
420         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
421
422         //@endcond
423
424     public:
425         /// Default constructor
426         /**
427             Initial size = \ref c_nDefaultInitialSize
428
429             Probe set size:
430             - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
431             - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
432
433             Probe set threshold = probe set size - 1
434         */
435         CuckooSet()
436         {}
437
438         /// Constructs the set object with given probe set size and threshold
439         /**
440             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
441             then \p nProbesetSize should be equal to vector's \p Capacity.
442         */
443         CuckooSet(
444             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
445             , unsigned int nProbesetSize        ///< probe set size
446             , unsigned int nProbesetThreshold = 0  ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
447         )
448         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
449         {}
450
451         /// Constructs the set object with given hash functor tuple
452         /**
453             The probe set size and threshold are set as default, see CuckooSet()
454         */
455         CuckooSet(
456             hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
457         )
458         : base_class( h )
459         {}
460
461         /// Constructs the set object with given probe set properties and hash functor tuple
462         /**
463             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
464             then \p nProbesetSize should be equal to vector's \p Capacity.
465         */
466         CuckooSet(
467             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
468             , unsigned int nProbesetSize        ///< probe set size
469             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
470             , hash_tuple_type const& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
471         )
472         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
473         {}
474
475         /// Constructs the set object with given hash functor tuple (move semantics)
476         /**
477             The probe set size and threshold are set as default, see CuckooSet()
478         */
479         CuckooSet(
480             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
481         )
482         : base_class( std::forward<hash_tuple_type>(h) )
483         {}
484
485         /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
486         /**
487             If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
488             then \p nProbesetSize should be equal to vector's \p Capacity.
489         */
490         CuckooSet(
491             size_t nInitialSize                 ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
492             , unsigned int nProbesetSize        ///< probe set size
493             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
494             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
495         )
496         : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
497         {}
498
499         /// Destructor clears the set
500         ~CuckooSet()
501         {
502             clear();
503         }
504
505     public:
506         /// Inserts new node
507         /**
508             The function creates a node with copy of \p val value
509             and then inserts the node created into the set.
510
511             The type \p Q should contain as minimum the complete key for the node.
512             The object of \ref value_type should be constructible from a value of type \p Q.
513             In trivial case, \p Q is equal to \ref value_type.
514
515             Returns \p true if \p val is inserted into the set, \p false otherwise.
516         */
517         template <typename Q>
518         bool insert( Q const& val )
519         {
520             return insert( val, []( value_type& ) {} );
521         }
522
523         /// Inserts new node
524         /**
525             The function allows to split creating of new item into two part:
526             - create item with key only
527             - insert new item into the set
528             - if inserting is success, calls \p f functor to initialize value-field of new item .
529
530             The functor signature is:
531             \code
532                 void func( value_type& item );
533             \endcode
534             where \p item is the item inserted.
535
536             The type \p Q can differ from \ref value_type of items storing in the set.
537             Therefore, the \p value_type should be constructible from type \p Q.
538
539             The user-defined functor is called only if the inserting is success. It can be passed by reference
540             using \p std::ref
541         */
542         template <typename Q, typename Func>
543         bool insert( Q const& val, Func f )
544         {
545             scoped_node_ptr pNode( alloc_node( val ));
546             if ( base_class::insert( *pNode, [&f]( node_type& node ) { f( node.m_val ); } )) {
547                 pNode.release();
548                 return true;
549             }
550             return false;
551         }
552
553         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
554         /**
555             Returns \p true if inserting successful, \p false otherwise.
556         */
557         template <typename... Args>
558         bool emplace( Args&&... args )
559         {
560             scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
561             if ( base_class::insert( *pNode )) {
562                 pNode.release();
563                 return true;
564             }
565             return false;
566         }
567
568         /// Ensures that the \p val exists in the set
569         /**
570             The operation performs inserting or changing data.
571
572             If the \p val key not found in the set, then the new item created from \p val
573             is inserted into the set. Otherwise, the functor \p func is called with the item found.
574             The functor \p Func should be a function with signature:
575             \code
576                 void func( bool bNew, value_type& item, const Q& val );
577             \endcode
578             or a functor:
579             \code
580                 struct my_functor {
581                     void operator()( bool bNew, value_type& item, const Q& val );
582                 };
583             \endcode
584
585             with arguments:
586             - \p bNew - \p true if the item has been inserted, \p false otherwise
587             - \p item - item of the set
588             - \p val - argument \p val passed into the \p ensure function
589
590             The functor can change non-key fields of the \p item.
591
592             You can pass \p func argument by value or by reference using \p std::ref
593
594             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
595             \p second is true if new item has been added or \p false if the item with \p val key
596             already exists.
597         */
598         template <typename Q, typename Func>
599         std::pair<bool, bool> ensure( Q const& val, Func func )
600         {
601             scoped_node_ptr pNode( alloc_node( val ));
602             std::pair<bool, bool> res = base_class::ensure( *pNode,
603                 [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); }
604             );
605             if ( res.first && res.second )
606                 pNode.release();
607             return res;
608         }
609
610         /// Delete \p key from the set
611         /** \anchor cds_nonintrusive_CuckooSet_erase
612
613             Since the key of set's item type \ref value_type is not explicitly specified,
614             template parameter \p Q defines the key type searching in the list.
615             The set item comparator should be able to compare the type \p value_type
616             and the type \p Q.
617
618             Return \p true if key is found and deleted, \p false otherwise
619         */
620         template <typename Q>
621         bool erase( Q const& key )
622         {
623             node_type * pNode = base_class::erase( key );
624             if ( pNode ) {
625                 free_node( pNode );
626                 return true;
627             }
628             return false;
629         }
630
631         /// Deletes the item from the list using \p pred predicate for searching
632         /**
633             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
634             but \p pred is used for key comparing.
635             If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
636             If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
637             \p Predicate must imply the same element order as the comparator used for building the set.
638         */
639         template <typename Q, typename Predicate>
640         bool erase_with( Q const& key, Predicate pred )
641         {
642             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
643             if ( pNode ) {
644                 free_node( pNode );
645                 return true;
646             }
647             return false;
648         }
649
650         /// Delete \p key from the set
651         /** \anchor cds_nonintrusive_CuckooSet_erase_func
652
653             The function searches an item with key \p key, calls \p f functor
654             and deletes the item. If \p key is not found, the functor is not called.
655
656             The functor \p Func interface is:
657             \code
658             struct functor {
659                 void operator()(value_type const& val);
660             };
661             \endcode
662             The functor can be passed by value or by reference using <tt>boost:ref</tt>
663
664             Return \p true if key is found and deleted, \p false otherwise
665         */
666         template <typename Q, typename Func>
667         bool erase( Q const& key, Func f )
668         {
669             node_type * pNode = base_class::erase( key );
670             if ( pNode ) {
671                 f( pNode->m_val );
672                 free_node( pNode );
673                 return true;
674             }
675             return false;
676         }
677
678         /// Deletes the item from the list using \p pred predicate for searching
679         /**
680             The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
681             but \p pred is used for key comparing.
682             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
683             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
684             \p Predicate must imply the same element order as the comparator used for building the set.
685         */
686         template <typename Q, typename Predicate, typename Func>
687         bool erase_with( Q const& key, Predicate pred, Func f )
688         {
689             node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
690             if ( pNode ) {
691                 f( pNode->m_val );
692                 free_node( pNode );
693                 return true;
694             }
695             return false;
696         }
697
698         /// Find the key \p val
699         /** \anchor cds_nonintrusive_CuckooSet_find_func
700
701             The function searches the item with key equal to \p val and calls the functor \p f for item found.
702             The interface of \p Func functor is:
703             \code
704             struct functor {
705                 void operator()( value_type& item, Q& val );
706             };
707             \endcode
708             where \p item is the item found, \p val is the <tt>find</tt> function argument.
709
710             You can pass \p f argument by value or by reference using \p std::ref
711
712             The functor can change non-key fields of \p item.
713             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
714             can modify both arguments.
715
716             The type \p Q can differ from \ref value_type of items storing in the container.
717             Therefore, the \p value_type should be comparable with type \p Q.
718
719             The function returns \p true if \p val is found, \p false otherwise.
720         */
721         template <typename Q, typename Func>
722         bool find( Q& val, Func f )
723         {
724             return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
725         }
726
727         /// Find the key \p val using \p pred predicate for comparing
728         /**
729             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
730             but \p pred is used for key comparison.
731             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
732             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
733             \p pred must imply the same element order as the comparator used for building the set.
734         */
735         template <typename Q, typename Predicate, typename Func>
736         bool find_with( Q& val, Predicate pred, Func f )
737         {
738             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
739                 [&f](node_type& item, Q& v) { f( item.m_val, v );});
740         }
741
742         /// Find the key \p val
743         /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
744
745             The function searches the item with key equal to \p val and calls the functor \p f for item found.
746             The interface of \p Func functor is:
747             \code
748             struct functor {
749                 void operator()( value_type& item, Q const& val );
750             };
751             \endcode
752             where \p item is the item found, \p val is the <tt>find</tt> function argument.
753
754             You can pass \p f argument by value or by reference using \p std::ref
755
756             The functor can change non-key fields of \p item.
757
758             The type \p Q can differ from \ref value_type of items storing in the container.
759             Therefore, the \p value_type should be comparable with type \p Q.
760
761             The function returns \p true if \p val is found, \p false otherwise.
762         */
763         template <typename Q, typename Func>
764         bool find( Q const& val, Func f )
765         {
766             return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
767         }
768
769         /// Find the key \p val using \p pred predicate for comparing
770         /**
771             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
772             but \p pred is used for key comparison.
773             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
774             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
775             \p pred must imply the same element order as the comparator used for building the set.
776         */
777         template <typename Q, typename Predicate, typename Func>
778         bool find_with( Q const& val, Predicate pred, Func f )
779         {
780             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
781                 [&f](node_type& item, Q const& v) { f( item.m_val, v );});
782         }
783
784         /// Find the key \p val
785         /** \anchor cds_nonintrusive_CuckooSet_find_val
786
787             The function searches the item with key equal to \p val
788             and returns \p true if it is found, and \p false otherwise.
789
790             Note the hash functor specified for class \p Traits template parameter
791             should accept a parameter of type \p Q that can be not the same as \ref value_type.
792         */
793         template <typename Q>
794         bool find( Q const& val )
795         {
796             return base_class::find( val, [](node_type&, Q const&) {});
797         }
798
799         /// Find the key \p val using \p pred predicate for comparing
800         /**
801             The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
802             but \p pred is used for key comparison.
803             If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
804             If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
805             \p pred must imply the same element order as the comparator used for building the set.
806         */
807         template <typename Q, typename Predicate>
808         bool find_with( Q const& val, Predicate pred )
809         {
810             return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
811         }
812
813         /// Clears the set
814         /**
815             The function erases all items from the set.
816         */
817         void clear()
818         {
819             return base_class::clear_and_dispose( node_disposer() );
820         }
821
822         /// Checks if the set is empty
823         /**
824             Emptiness is checked by item counting: if item count is zero then the set is empty.
825         */
826         bool empty() const
827         {
828             return base_class::empty();
829         }
830
831         /// Returns item count in the set
832         size_t size() const
833         {
834             return base_class::size();
835         }
836
837         /// Returns the size of hash table
838         /**
839             The hash table size is non-constant and can be increased via resizing.
840         */
841         size_t bucket_count() const
842         {
843             return base_class::bucket_count();
844         }
845
846         /// Returns lock array size
847         size_t lock_count() const
848         {
849             return base_class::lock_count();
850         }
851
852         /// Returns const reference to internal statistics
853         stat const& statistics() const
854         {
855             return base_class::statistics();
856         }
857
858         /// Returns const reference to mutex policy internal statistics
859         typename mutex_policy::statistics_type const& mutex_policy_statistics() const
860         {
861             return base_class::mutex_policy_statistics();
862         }
863
864     };
865
866 }} // namespace cds::container
867
868 #endif //#ifndef __CDS_CONTAINER_CUCKOO_SET_H