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