3 #ifndef __CDS_CONTAINER_CUCKOO_SET_H
4 #define __CDS_CONTAINER_CUCKOO_SET_H
6 #include <cds/container/cuckoo_base.h>
7 #include <cds/details/binary_functor_wrapper.h>
9 namespace cds { namespace container {
13 template <typename T, typename Traits>
14 struct make_cuckoo_set
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;
22 struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
27 node_type( Q const& v )
31 # ifdef CDS_EMPLACE_SUPPORT
32 template <typename... Args>
33 node_type( Args&&... args )
34 : m_val( std::forward<Args>(args)...)
42 struct value_accessor {
43 value_type const& operator()( node_type const& node ) const
49 template <typename Pred, typename ReturnValue>
50 using predicate_wrapper = cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >;
52 struct intrusive_traits: public original_type_traits
54 typedef intrusive::cuckoo::base_hook<
55 cds::intrusive::cuckoo::probeset_type< probeset_type >
56 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
59 typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
61 typedef typename std::conditional<
62 std::is_same< typename original_type_traits::equal_to, opt::none >::value
64 , predicate_wrapper< typename original_type_traits::equal_to, bool >
67 typedef typename std::conditional<
68 std::is_same< typename original_type_traits::compare, opt::none >::value
70 , predicate_wrapper< typename original_type_traits::compare, int >
73 typedef typename std::conditional<
74 std::is_same< typename original_type_traits::less, opt::none >::value
76 ,predicate_wrapper< typename original_type_traits::less, bool >
79 typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, value_accessor > hash;
82 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
84 } // namespace details
88 /** @ingroup cds_nonintrusive_set
91 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
92 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
94 <b>About Cuckoo hashing</b>
96 [From "The Art of Multiprocessor Programming"]
97 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
98 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
99 N = 2k we use a two-entry array of tables, and two independent hash functions,
100 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
101 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
102 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
103 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
104 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
106 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
107 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
108 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
109 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
110 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
111 until it finds an empty slot. We might not find an empty slot, either because the table is full,
112 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
113 number of successive displacements we are willing to undertake. When this limit is exceeded,
114 we resize the hash table, choose new hash functions and start over.
116 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
117 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
118 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
119 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
120 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
121 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
123 In current implementation, a probe set can be defined either as a (single-linked) list
124 or as a fixed-sized vector, optionally ordered.
126 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
127 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
128 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
130 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
131 The probe set may be ordered or not. Ordered probe set can be a little better since
132 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
133 However, the overhead of sorting can eliminate a gain of ordered search.
135 The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
136 declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
137 opt::equal_to option.
140 - \p T - the type stored in the set.
141 - \p Traits - type traits. See cuckoo::type_traits for explanation.
142 It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
144 Template argument list \p Options... of cuckoo::make_traits metafunction are:
145 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
146 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
147 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
148 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
149 then k is unlimited, otherwise up to 10 different hash functors are supported.
150 - opt::mutex_policy - concurrent access policy.
151 Available policies: cuckoo::striping, cuckoo::refinable.
152 Default is cuckoo::striping.
153 - opt::equal_to - key equality functor like \p std::equal_to.
154 If this functor is defined then the probe-set will be unordered.
155 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
156 and opt::equal_to will be ignored.
157 - opt::compare - key comparison functor. No default functor is provided.
158 If the option is not specified, the opt::less is used.
159 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
160 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
161 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
162 - opt::item_counter - the type of item counting feature. Default is \ref opt::v::sequential_item_counter.
163 - opt::allocator - the allocator type using for allocating bucket tables.
164 Default is \p CDS_DEFAULT_ALLOCATOR
165 - opt::node_allocator - the allocator type using for allocating set's items. If this option
166 is not specified then the type defined in opt::allocator option is used.
167 - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
168 of the object once it's introduced in the container. When this option is used,
169 the unordered container will store the calculated hash value in the node and rehashing operations won't need
170 to recalculate the hash of the value. This option will improve the performance of unordered containers
171 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
172 - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
173 Default is \p cuckoo::list.
174 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
175 Default is cuckoo::empty_stat
179 Cuckoo-set with list-based unordered probe set and storing hash values
181 #include <cds/container/cuckoo_set.h>
183 // Data stored in cuckoo set
193 // Provide equal_to functor for my_data since we will use unordered probe-set
194 struct my_data_equal_to {
195 bool operator()( const my_data& d1, const my_data& d2 ) const
197 return d1.strKey.compare( d2.strKey ) == 0;
200 bool operator()( const my_data& d, const std::string& s ) const
202 return d.strKey.compare(s) == 0;
205 bool operator()( const std::string& s, const my_data& d ) const
207 return s.compare( d.strKey ) == 0;
211 // Provide two hash functor for my_data
213 size_t operator()(std::string const& s) const
215 return cds::opt::v::hash<std::string>( s );
217 size_t operator()( my_data const& d ) const
219 return (*this)( d.strKey );
223 struct hash2: private hash1 {
224 size_t operator()(std::string const& s) const
226 size_t h = ~( hash1::operator()(s));
227 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
229 size_t operator()( my_data const& d ) const
231 return (*this)( d.strKey );
235 // Declare type traits
236 struct my_traits: public cds::container::cuckoo::type_traits
238 typedef my_data_equa_to equal_to;
239 typedef std::tuple< hash1, hash2 > hash;
241 static bool const store_hash = true;
244 // Declare CuckooSet type
245 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
247 // Equal option-based declaration
248 typedef cds::container::CuckooSet< my_data,
249 cds::container::cuckoo::make_traits<
250 cds::opt::hash< std::tuple< hash1, hash2 > >
251 ,cds::opt::equal_to< my_data_equal_to >
252 ,cds::container::cuckoo::store_hash< true >
257 If we provide \p compare function instead of \p equal_to for \p my_data
258 we get as a result a cuckoo set with ordered probe set that may improve
260 Example for ordered vector-based probe-set:
263 #include <cds/container/cuckoo_set.h>
265 // Data stored in cuckoo set
275 // Provide compare functor for my_data since we want to use ordered probe-set
276 struct my_data_compare {
277 int operator()( const my_data& d1, const my_data& d2 ) const
279 return d1.strKey.compare( d2.strKey );
282 int operator()( const my_data& d, const std::string& s ) const
284 return d.strKey.compare(s);
287 int operator()( const std::string& s, const my_data& d ) const
289 return s.compare( d.strKey );
293 // Provide two hash functor for my_data
295 size_t operator()(std::string const& s) const
297 return cds::opt::v::hash<std::string>( s );
299 size_t operator()( my_data const& d ) const
301 return (*this)( d.strKey );
305 struct hash2: private hash1 {
306 size_t operator()(std::string const& s) const
308 size_t h = ~( hash1::operator()(s));
309 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
311 size_t operator()( my_data const& d ) const
313 return (*this)( d.strKey );
317 // Declare type traits
318 // We use a vector of capacity 4 as probe-set container and store hash values in the node
319 struct my_traits: public cds::container::cuckoo::type_traits
321 typedef my_data_compare compare;
322 typedef std::tuple< hash1, hash2 > hash;
323 typedef cds::container::cuckoo::vector<4> probeset_type;
325 static bool const store_hash = true;
328 // Declare CuckooSet type
329 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
331 // Equal option-based declaration
332 typedef cds::container::CuckooSet< my_data,
333 cds::container::cuckoo::make_traits<
334 cds::opt::hash< std::tuple< hash1, hash2 > >
335 ,cds::opt::compare< my_data_compare >
336 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
337 ,cds::container::cuckoo::store_hash< true >
343 template <typename T, typename Traits = cuckoo::type_traits>
345 #ifdef CDS_DOXYGEN_INVOKED
346 protected intrusive::CuckooSet<T, Traits>
348 protected details::make_cuckoo_set<T, Traits>::type
352 typedef details::make_cuckoo_set<T, Traits> maker;
353 typedef typename maker::type base_class;
357 typedef T value_type ; ///< value type stored in the container
358 typedef Traits options ; ///< traits
360 typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
361 typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< Type of hash tuple
363 typedef typename base_class::mutex_policy mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
364 typedef typename base_class::stat stat ; ///< internal statistics type
367 static bool const c_isSorted = base_class::c_isSorted ; ///< whether the probe set should be ordered
368 static size_t const c_nArity = base_class::c_nArity ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
370 typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
372 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
374 typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
376 /// Node allocator type
377 typedef typename std::conditional<
378 std::is_same< typename options::node_allocator, opt::none >::value,
380 typename options::node_allocator
381 >::type node_allocator;
383 /// item counter type
384 typedef typename options::item_counter item_counter;
388 typedef typename base_class::value_type node_type;
389 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
393 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ; ///< default probeset size
394 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize ; ///< default initial size
395 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit ; ///< Count of attempts to relocate before giving up
399 template <typename Q>
400 static node_type * alloc_node( Q const& v )
402 return cxx_node_allocator().New( v );
404 # ifdef CDS_EMPLACE_SUPPORT
405 template <typename... Args>
406 static node_type * alloc_node( Args&&... args )
408 return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
412 static void free_node( node_type * pNode )
414 cxx_node_allocator().Delete( pNode );
420 struct node_disposer {
421 void operator()( node_type * pNode )
427 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
429 # ifndef CDS_CXX11_LAMBDA_SUPPORT
430 struct empty_insert_functor {
431 void operator()( value_type& ) const
435 struct empty_find_functor {
436 template <typename Q>
437 void operator()( node_type& item, Q& val ) const
441 template <typename Func>
442 class insert_wrapper: protected cds::details::functor_wrapper<Func>
444 typedef cds::details::functor_wrapper<Func> base_class;
446 insert_wrapper( Func f ): base_class(f) {}
448 void operator()( node_type& node )
450 base_class::get()( node.m_val );
454 template <typename Q, typename Func>
455 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
457 typedef cds::details::functor_wrapper<Func> base_class;
461 ensure_wrapper( Q const& v, Func f) : base_class(f), val(v) {}
463 void operator()( bool bNew, node_type& item, node_type const& )
465 base_class::get()( bNew, item.m_val, val );
469 template <typename Func>
470 class find_wrapper: protected cds::details::functor_wrapper<Func>
472 typedef cds::details::functor_wrapper<Func> base_class;
474 find_wrapper( Func f )
478 template <typename Q>
479 void operator()( node_type& item, Q& val )
481 base_class::get()( item.m_val, val );
488 /// Default constructor
490 Initial size = \ref c_nDefaultInitialSize
493 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
494 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
496 Probe set threshold = probe set size - 1
501 /// Constructs the set object with given probe set size and threshold
503 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
504 then \p nProbesetSize should be equal to vector's \p Capacity.
507 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
508 , unsigned int nProbesetSize ///< probe set size
509 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
511 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
514 /// Constructs the set object with given hash functor tuple
516 The probe set size and threshold are set as default, see CuckooSet()
519 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
524 /// Constructs the set object with given probe set properties and hash functor tuple
526 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
527 then \p nProbesetSize should be equal to vector's \p Capacity.
530 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
531 , unsigned int nProbesetSize ///< probe set size
532 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
533 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
535 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
538 /// Constructs the set object with given hash functor tuple (move semantics)
540 The probe set size and threshold are set as default, see CuckooSet()
543 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
545 : base_class( std::forward<hash_tuple_type>(h) )
548 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
550 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
551 then \p nProbesetSize should be equal to vector's \p Capacity.
554 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
555 , unsigned int nProbesetSize ///< probe set size
556 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
557 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
559 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
562 /// Destructor clears the set
571 The function creates a node with copy of \p val value
572 and then inserts the node created into the set.
574 The type \p Q should contain as minimum the complete key for the node.
575 The object of \ref value_type should be constructible from a value of type \p Q.
576 In trivial case, \p Q is equal to \ref value_type.
578 Returns \p true if \p val is inserted into the set, \p false otherwise.
580 template <typename Q>
581 bool insert( Q const& val )
583 # ifdef CDS_CXX11_LAMBDA_SUPPORT
584 return insert( val, []( value_type& ) {} );
586 return insert( val, empty_insert_functor() );
592 The function allows to split creating of new item into two part:
593 - create item with key only
594 - insert new item into the set
595 - if inserting is success, calls \p f functor to initialize value-field of new item .
597 The functor signature is:
599 void func( value_type& item );
601 where \p item is the item inserted.
603 The type \p Q can differ from \ref value_type of items storing in the set.
604 Therefore, the \p value_type should be constructible from type \p Q.
606 The user-defined functor is called only if the inserting is success. It can be passed by reference
607 using <tt>boost::ref</tt>
609 template <typename Q, typename Func>
610 bool insert( Q const& val, Func f )
612 scoped_node_ptr pNode( alloc_node( val ));
613 # ifdef CDS_CXX11_LAMBDA_SUPPORT
614 if ( base_class::insert( *pNode, [&f]( node_type& node ) { cds::unref(f)( node.m_val ); } ))
616 insert_wrapper<Func> wrapper( f );
617 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
626 # ifdef CDS_EMPLACE_SUPPORT
627 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
629 Returns \p true if inserting successful, \p false otherwise.
631 This function is available only for compiler that supports
632 variadic template and move semantics
634 template <typename... Args>
635 bool emplace( Args&&... args )
637 scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
638 if ( base_class::insert( *pNode )) {
646 /// Ensures that the \p val exists in the set
648 The operation performs inserting or changing data.
650 If the \p val key not found in the set, then the new item created from \p val
651 is inserted into the set. Otherwise, the functor \p func is called with the item found.
652 The functor \p Func should be a function with signature:
654 void func( bool bNew, value_type& item, const Q& val );
659 void operator()( bool bNew, value_type& item, const Q& val );
664 - \p bNew - \p true if the item has been inserted, \p false otherwise
665 - \p item - item of the set
666 - \p val - argument \p val passed into the \p ensure function
668 The functor can change non-key fields of the \p item.
670 You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
672 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
673 \p second is true if new item has been added or \p false if the item with \p val key
676 template <typename Q, typename Func>
677 std::pair<bool, bool> ensure( Q const& val, Func func )
679 scoped_node_ptr pNode( alloc_node( val ));
680 # ifdef CDS_CXX11_LAMBDA_SUPPORT
681 std::pair<bool, bool> res = base_class::ensure( *pNode,
682 [&val,&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val, val ); }
685 ensure_wrapper<Q, Func> wrapper( val, func );
686 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
688 if ( res.first && res.second )
693 /// Delete \p key from the set
694 /** \anchor cds_nonintrusive_CuckooSet_erase
696 Since the key of set's item type \ref value_type is not explicitly specified,
697 template parameter \p Q defines the key type searching in the list.
698 The set item comparator should be able to compare the type \p value_type
701 Return \p true if key is found and deleted, \p false otherwise
703 template <typename Q>
704 bool erase( Q const& key )
706 node_type * pNode = base_class::erase( key );
714 /// Deletes the item from the list using \p pred predicate for searching
716 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
717 but \p pred is used for key comparing.
718 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
719 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
720 \p Predicate must imply the same element order as the comparator used for building the set.
722 template <typename Q, typename Predicate>
723 bool erase_with( Q const& key, Predicate pred )
725 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
733 /// Delete \p key from the set
734 /** \anchor cds_nonintrusive_CuckooSet_erase_func
736 The function searches an item with key \p key, calls \p f functor
737 and deletes the item. If \p key is not found, the functor is not called.
739 The functor \p Func interface is:
742 void operator()(value_type const& val);
745 The functor can be passed by value or by reference using <tt>boost:ref</tt>
747 Return \p true if key is found and deleted, \p false otherwise
749 template <typename Q, typename Func>
750 bool erase( Q const& key, Func f )
752 node_type * pNode = base_class::erase( key );
754 cds::unref(f)( pNode->m_val );
761 /// Deletes the item from the list using \p pred predicate for searching
763 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
764 but \p pred is used for key comparing.
765 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
766 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
767 \p Predicate must imply the same element order as the comparator used for building the set.
769 template <typename Q, typename Predicate, typename Func>
770 bool erase_with( Q const& key, Predicate pred, Func f )
772 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
774 cds::unref(f)( pNode->m_val );
781 /// Find the key \p val
782 /** \anchor cds_nonintrusive_CuckooSet_find_func
784 The function searches the item with key equal to \p val and calls the functor \p f for item found.
785 The interface of \p Func functor is:
788 void operator()( value_type& item, Q& val );
791 where \p item is the item found, \p val is the <tt>find</tt> function argument.
793 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
795 The functor can change non-key fields of \p item.
796 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
797 can modify both arguments.
799 The type \p Q can differ from \ref value_type of items storing in the container.
800 Therefore, the \p value_type should be comparable with type \p Q.
802 The function returns \p true if \p val is found, \p false otherwise.
804 template <typename Q, typename Func>
805 bool find( Q& val, Func f )
807 # ifdef CDS_CXX11_LAMBDA_SUPPORT
808 return base_class::find( val, [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
810 find_wrapper<Func> wrapper(f);
811 return base_class::find( val, cds::ref(wrapper) );
815 /// Find the key \p val using \p pred predicate for comparing
817 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
818 but \p pred is used for key comparison.
819 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
820 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
821 \p pred must imply the same element order as the comparator used for building the set.
823 template <typename Q, typename Predicate, typename Func>
824 bool find_with( Q& val, Predicate pred, Func f )
826 # ifdef CDS_CXX11_LAMBDA_SUPPORT
827 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
828 [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
830 find_wrapper<Func> wrapper(f);
831 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
835 /// Find the key \p val
836 /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
838 The function searches the item with key equal to \p val and calls the functor \p f for item found.
839 The interface of \p Func functor is:
842 void operator()( value_type& item, Q const& val );
845 where \p item is the item found, \p val is the <tt>find</tt> function argument.
847 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
849 The functor can change non-key fields of \p item.
851 The type \p Q can differ from \ref value_type of items storing in the container.
852 Therefore, the \p value_type should be comparable with type \p Q.
854 The function returns \p true if \p val is found, \p false otherwise.
856 template <typename Q, typename Func>
857 bool find( Q const& val, Func f )
859 # ifdef CDS_CXX11_LAMBDA_SUPPORT
860 return base_class::find( val, [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
862 find_wrapper<Func> wrapper(f);
863 return base_class::find( val, cds::ref(wrapper) );
867 /// Find the key \p val using \p pred predicate for comparing
869 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
870 but \p pred is used for key comparison.
871 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
872 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
873 \p pred must imply the same element order as the comparator used for building the set.
875 template <typename Q, typename Predicate, typename Func>
876 bool find_with( Q const& val, Predicate pred, Func f )
878 # ifdef CDS_CXX11_LAMBDA_SUPPORT
879 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
880 [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
882 find_wrapper<Func> wrapper(f);
883 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
887 /// Find the key \p val
888 /** \anchor cds_nonintrusive_CuckooSet_find_val
890 The function searches the item with key equal to \p val
891 and returns \p true if it is found, and \p false otherwise.
893 Note the hash functor specified for class \p Traits template parameter
894 should accept a parameter of type \p Q that can be not the same as \ref value_type.
896 template <typename Q>
897 bool find( Q const& val )
899 # ifdef CDS_CXX11_LAMBDA_SUPPORT
900 return base_class::find( val, [](node_type&, Q const&) {});
902 return base_class::find( val, empty_find_functor());
906 /// Find the key \p val using \p pred predicate for comparing
908 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
909 but \p pred is used for key comparison.
910 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
911 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
912 \p pred must imply the same element order as the comparator used for building the set.
914 template <typename Q, typename Predicate>
915 bool find_with( Q const& val, Predicate pred )
917 # ifdef CDS_CXX11_LAMBDA_SUPPORT
918 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
920 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), empty_find_functor());
926 The function erases all items from the set.
930 return base_class::clear_and_dispose( node_disposer() );
933 /// Checks if the set is empty
935 Emptiness is checked by item counting: if item count is zero then the set is empty.
939 return base_class::empty();
942 /// Returns item count in the set
945 return base_class::size();
948 /// Returns the size of hash table
950 The hash table size is non-constant and can be increased via resizing.
952 size_t bucket_count() const
954 return base_class::bucket_count();
957 /// Returns lock array size
958 size_t lock_count() const
960 return base_class::lock_count();
963 /// Returns const reference to internal statistics
964 stat const& statistics() const
966 return base_class::statistics();
969 /// Returns const reference to mutex policy internal statistics
970 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
972 return base_class::mutex_policy_statistics();
977 }} // namespace cds::container
979 #endif //#ifndef __CDS_CONTAINER_CUCKOO_SET_H