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 template <typename... Args>
32 node_type( Args&&... args )
33 : m_val( std::forward<Args>(args)...)
37 struct value_accessor {
38 value_type const& operator()( node_type const& node ) const
44 template <typename Pred, typename ReturnValue>
45 using predicate_wrapper = cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >;
47 struct intrusive_traits: public original_type_traits
49 typedef intrusive::cuckoo::base_hook<
50 cds::intrusive::cuckoo::probeset_type< probeset_type >
51 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
54 typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
56 typedef typename std::conditional<
57 std::is_same< typename original_type_traits::equal_to, opt::none >::value
59 , predicate_wrapper< typename original_type_traits::equal_to, bool >
62 typedef typename std::conditional<
63 std::is_same< typename original_type_traits::compare, opt::none >::value
65 , predicate_wrapper< typename original_type_traits::compare, int >
68 typedef typename std::conditional<
69 std::is_same< typename original_type_traits::less, opt::none >::value
71 ,predicate_wrapper< typename original_type_traits::less, bool >
74 typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, value_accessor > hash;
77 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
79 } // namespace details
83 /** @ingroup cds_nonintrusive_set
86 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
87 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
89 <b>About Cuckoo hashing</b>
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.
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.
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.
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.
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>.
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.
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.
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.
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
174 Cuckoo-set with list-based unordered probe set and storing hash values
176 #include <cds/container/cuckoo_set.h>
178 // Data stored in cuckoo set
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
192 return d1.strKey.compare( d2.strKey ) == 0;
195 bool operator()( const my_data& d, const std::string& s ) const
197 return d.strKey.compare(s) == 0;
200 bool operator()( const std::string& s, const my_data& d ) const
202 return s.compare( d.strKey ) == 0;
206 // Provide two hash functor for my_data
208 size_t operator()(std::string const& s) const
210 return cds::opt::v::hash<std::string>( s );
212 size_t operator()( my_data const& d ) const
214 return (*this)( d.strKey );
218 struct hash2: private hash1 {
219 size_t operator()(std::string const& s) const
221 size_t h = ~( hash1::operator()(s));
222 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
224 size_t operator()( my_data const& d ) const
226 return (*this)( d.strKey );
230 // Declare type traits
231 struct my_traits: public cds::container::cuckoo::type_traits
233 typedef my_data_equa_to equal_to;
234 typedef std::tuple< hash1, hash2 > hash;
236 static bool const store_hash = true;
239 // Declare CuckooSet type
240 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
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 >
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
255 Example for ordered vector-based probe-set:
258 #include <cds/container/cuckoo_set.h>
260 // Data stored in cuckoo set
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
274 return d1.strKey.compare( d2.strKey );
277 int operator()( const my_data& d, const std::string& s ) const
279 return d.strKey.compare(s);
282 int operator()( const std::string& s, const my_data& d ) const
284 return s.compare( d.strKey );
288 // Provide two hash functor for my_data
290 size_t operator()(std::string const& s) const
292 return cds::opt::v::hash<std::string>( s );
294 size_t operator()( my_data const& d ) const
296 return (*this)( d.strKey );
300 struct hash2: private hash1 {
301 size_t operator()(std::string const& s) const
303 size_t h = ~( hash1::operator()(s));
304 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
306 size_t operator()( my_data const& d ) const
308 return (*this)( d.strKey );
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
316 typedef my_data_compare compare;
317 typedef std::tuple< hash1, hash2 > hash;
318 typedef cds::container::cuckoo::vector<4> probeset_type;
320 static bool const store_hash = true;
323 // Declare CuckooSet type
324 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
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 >
338 template <typename T, typename Traits = cuckoo::type_traits>
340 #ifdef CDS_DOXYGEN_INVOKED
341 protected intrusive::CuckooSet<T, Traits>
343 protected details::make_cuckoo_set<T, Traits>::type
347 typedef details::make_cuckoo_set<T, Traits> maker;
348 typedef typename maker::type base_class;
352 typedef T value_type ; ///< value type stored in the container
353 typedef Traits options ; ///< traits
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
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
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.
365 typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
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
369 typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
371 /// Node allocator type
372 typedef typename std::conditional<
373 std::is_same< typename options::node_allocator, opt::none >::value,
375 typename options::node_allocator
376 >::type node_allocator;
378 /// item counter type
379 typedef typename options::item_counter item_counter;
383 typedef typename base_class::value_type node_type;
384 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
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
394 template <typename Q>
395 static node_type * alloc_node( Q const& v )
397 return cxx_node_allocator().New( v );
399 template <typename... Args>
400 static node_type * alloc_node( Args&&... args )
402 return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
405 static void free_node( node_type * pNode )
407 cxx_node_allocator().Delete( pNode );
413 struct node_disposer {
414 void operator()( node_type * pNode )
420 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
422 # ifndef CDS_CXX11_LAMBDA_SUPPORT
423 struct empty_insert_functor {
424 void operator()( value_type& ) const
428 struct empty_find_functor {
429 template <typename Q>
430 void operator()( node_type& item, Q& val ) const
434 template <typename Func>
435 class insert_wrapper: protected cds::details::functor_wrapper<Func>
437 typedef cds::details::functor_wrapper<Func> base_class;
439 insert_wrapper( Func f ): base_class(f) {}
441 void operator()( node_type& node )
443 base_class::get()( node.m_val );
447 template <typename Q, typename Func>
448 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
450 typedef cds::details::functor_wrapper<Func> base_class;
454 ensure_wrapper( Q const& v, Func f) : base_class(f), val(v) {}
456 void operator()( bool bNew, node_type& item, node_type const& )
458 base_class::get()( bNew, item.m_val, val );
462 template <typename Func>
463 class find_wrapper: protected cds::details::functor_wrapper<Func>
465 typedef cds::details::functor_wrapper<Func> base_class;
467 find_wrapper( Func f )
471 template <typename Q>
472 void operator()( node_type& item, Q& val )
474 base_class::get()( item.m_val, val );
481 /// Default constructor
483 Initial size = \ref c_nDefaultInitialSize
486 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
487 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
489 Probe set threshold = probe set size - 1
494 /// Constructs the set object with given probe set size and threshold
496 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
497 then \p nProbesetSize should be equal to vector's \p Capacity.
500 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
501 , unsigned int nProbesetSize ///< probe set size
502 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
504 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
507 /// Constructs the set object with given hash functor tuple
509 The probe set size and threshold are set as default, see CuckooSet()
512 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
517 /// Constructs the set object with given probe set properties and hash functor tuple
519 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
520 then \p nProbesetSize should be equal to vector's \p Capacity.
523 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
524 , unsigned int nProbesetSize ///< probe set size
525 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
526 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
528 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
531 /// Constructs the set object with given hash functor tuple (move semantics)
533 The probe set size and threshold are set as default, see CuckooSet()
536 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
538 : base_class( std::forward<hash_tuple_type>(h) )
541 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
543 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
544 then \p nProbesetSize should be equal to vector's \p Capacity.
547 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
548 , unsigned int nProbesetSize ///< probe set size
549 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
550 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
552 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
555 /// Destructor clears the set
564 The function creates a node with copy of \p val value
565 and then inserts the node created into the set.
567 The type \p Q should contain as minimum the complete key for the node.
568 The object of \ref value_type should be constructible from a value of type \p Q.
569 In trivial case, \p Q is equal to \ref value_type.
571 Returns \p true if \p val is inserted into the set, \p false otherwise.
573 template <typename Q>
574 bool insert( Q const& val )
576 # ifdef CDS_CXX11_LAMBDA_SUPPORT
577 return insert( val, []( value_type& ) {} );
579 return insert( val, empty_insert_functor() );
585 The function allows to split creating of new item into two part:
586 - create item with key only
587 - insert new item into the set
588 - if inserting is success, calls \p f functor to initialize value-field of new item .
590 The functor signature is:
592 void func( value_type& item );
594 where \p item is the item inserted.
596 The type \p Q can differ from \ref value_type of items storing in the set.
597 Therefore, the \p value_type should be constructible from type \p Q.
599 The user-defined functor is called only if the inserting is success. It can be passed by reference
600 using <tt>boost::ref</tt>
602 template <typename Q, typename Func>
603 bool insert( Q const& val, Func f )
605 scoped_node_ptr pNode( alloc_node( val ));
606 # ifdef CDS_CXX11_LAMBDA_SUPPORT
607 if ( base_class::insert( *pNode, [&f]( node_type& node ) { cds::unref(f)( node.m_val ); } ))
609 insert_wrapper<Func> wrapper( f );
610 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
619 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
621 Returns \p true if inserting successful, \p false otherwise.
623 template <typename... Args>
624 bool emplace( Args&&... args )
626 scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
627 if ( base_class::insert( *pNode )) {
634 /// Ensures that the \p val exists in the set
636 The operation performs inserting or changing data.
638 If the \p val key not found in the set, then the new item created from \p val
639 is inserted into the set. Otherwise, the functor \p func is called with the item found.
640 The functor \p Func should be a function with signature:
642 void func( bool bNew, value_type& item, const Q& val );
647 void operator()( bool bNew, value_type& item, const Q& val );
652 - \p bNew - \p true if the item has been inserted, \p false otherwise
653 - \p item - item of the set
654 - \p val - argument \p val passed into the \p ensure function
656 The functor can change non-key fields of the \p item.
658 You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
660 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
661 \p second is true if new item has been added or \p false if the item with \p val key
664 template <typename Q, typename Func>
665 std::pair<bool, bool> ensure( Q const& val, Func func )
667 scoped_node_ptr pNode( alloc_node( val ));
668 # ifdef CDS_CXX11_LAMBDA_SUPPORT
669 std::pair<bool, bool> res = base_class::ensure( *pNode,
670 [&val,&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val, val ); }
673 ensure_wrapper<Q, Func> wrapper( val, func );
674 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
676 if ( res.first && res.second )
681 /// Delete \p key from the set
682 /** \anchor cds_nonintrusive_CuckooSet_erase
684 Since the key of set's item type \ref value_type is not explicitly specified,
685 template parameter \p Q defines the key type searching in the list.
686 The set item comparator should be able to compare the type \p value_type
689 Return \p true if key is found and deleted, \p false otherwise
691 template <typename Q>
692 bool erase( Q const& key )
694 node_type * pNode = base_class::erase( key );
702 /// Deletes the item from the list using \p pred predicate for searching
704 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
705 but \p pred is used for key comparing.
706 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
707 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
708 \p Predicate must imply the same element order as the comparator used for building the set.
710 template <typename Q, typename Predicate>
711 bool erase_with( Q const& key, Predicate pred )
713 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
721 /// Delete \p key from the set
722 /** \anchor cds_nonintrusive_CuckooSet_erase_func
724 The function searches an item with key \p key, calls \p f functor
725 and deletes the item. If \p key is not found, the functor is not called.
727 The functor \p Func interface is:
730 void operator()(value_type const& val);
733 The functor can be passed by value or by reference using <tt>boost:ref</tt>
735 Return \p true if key is found and deleted, \p false otherwise
737 template <typename Q, typename Func>
738 bool erase( Q const& key, Func f )
740 node_type * pNode = base_class::erase( key );
742 cds::unref(f)( pNode->m_val );
749 /// Deletes the item from the list using \p pred predicate for searching
751 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
752 but \p pred is used for key comparing.
753 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
754 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
755 \p Predicate must imply the same element order as the comparator used for building the set.
757 template <typename Q, typename Predicate, typename Func>
758 bool erase_with( Q const& key, Predicate pred, Func f )
760 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
762 cds::unref(f)( pNode->m_val );
769 /// Find the key \p val
770 /** \anchor cds_nonintrusive_CuckooSet_find_func
772 The function searches the item with key equal to \p val and calls the functor \p f for item found.
773 The interface of \p Func functor is:
776 void operator()( value_type& item, Q& val );
779 where \p item is the item found, \p val is the <tt>find</tt> function argument.
781 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
783 The functor can change non-key fields of \p item.
784 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
785 can modify both arguments.
787 The type \p Q can differ from \ref value_type of items storing in the container.
788 Therefore, the \p value_type should be comparable with type \p Q.
790 The function returns \p true if \p val is found, \p false otherwise.
792 template <typename Q, typename Func>
793 bool find( Q& val, Func f )
795 # ifdef CDS_CXX11_LAMBDA_SUPPORT
796 return base_class::find( val, [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
798 find_wrapper<Func> wrapper(f);
799 return base_class::find( val, cds::ref(wrapper) );
803 /// Find the key \p val using \p pred predicate for comparing
805 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
806 but \p pred is used for key comparison.
807 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
808 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
809 \p pred must imply the same element order as the comparator used for building the set.
811 template <typename Q, typename Predicate, typename Func>
812 bool find_with( Q& val, Predicate pred, Func f )
814 # ifdef CDS_CXX11_LAMBDA_SUPPORT
815 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
816 [&f](node_type& item, Q& v) { cds::unref(f)( item.m_val, v );});
818 find_wrapper<Func> wrapper(f);
819 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
823 /// Find the key \p val
824 /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
826 The function searches the item with key equal to \p val and calls the functor \p f for item found.
827 The interface of \p Func functor is:
830 void operator()( value_type& item, Q const& val );
833 where \p item is the item found, \p val is the <tt>find</tt> function argument.
835 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
837 The functor can change non-key fields of \p item.
839 The type \p Q can differ from \ref value_type of items storing in the container.
840 Therefore, the \p value_type should be comparable with type \p Q.
842 The function returns \p true if \p val is found, \p false otherwise.
844 template <typename Q, typename Func>
845 bool find( Q const& val, Func f )
847 # ifdef CDS_CXX11_LAMBDA_SUPPORT
848 return base_class::find( val, [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
850 find_wrapper<Func> wrapper(f);
851 return base_class::find( val, cds::ref(wrapper) );
855 /// Find the key \p val using \p pred predicate for comparing
857 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
858 but \p pred is used for key comparison.
859 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
860 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
861 \p pred must imply the same element order as the comparator used for building the set.
863 template <typename Q, typename Predicate, typename Func>
864 bool find_with( Q const& val, Predicate pred, Func f )
866 # ifdef CDS_CXX11_LAMBDA_SUPPORT
867 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
868 [&f](node_type& item, Q const& v) { cds::unref(f)( item.m_val, v );});
870 find_wrapper<Func> wrapper(f);
871 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
875 /// Find the key \p val
876 /** \anchor cds_nonintrusive_CuckooSet_find_val
878 The function searches the item with key equal to \p val
879 and returns \p true if it is found, and \p false otherwise.
881 Note the hash functor specified for class \p Traits template parameter
882 should accept a parameter of type \p Q that can be not the same as \ref value_type.
884 template <typename Q>
885 bool find( Q const& val )
887 # ifdef CDS_CXX11_LAMBDA_SUPPORT
888 return base_class::find( val, [](node_type&, Q const&) {});
890 return base_class::find( val, empty_find_functor());
894 /// Find the key \p val using \p pred predicate for comparing
896 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
897 but \p pred is used for key comparison.
898 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
899 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
900 \p pred must imply the same element order as the comparator used for building the set.
902 template <typename Q, typename Predicate>
903 bool find_with( Q const& val, Predicate pred )
905 # ifdef CDS_CXX11_LAMBDA_SUPPORT
906 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
908 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), empty_find_functor());
914 The function erases all items from the set.
918 return base_class::clear_and_dispose( node_disposer() );
921 /// Checks if the set is empty
923 Emptiness is checked by item counting: if item count is zero then the set is empty.
927 return base_class::empty();
930 /// Returns item count in the set
933 return base_class::size();
936 /// Returns the size of hash table
938 The hash table size is non-constant and can be increased via resizing.
940 size_t bucket_count() const
942 return base_class::bucket_count();
945 /// Returns lock array size
946 size_t lock_count() const
948 return base_class::lock_count();
951 /// Returns const reference to internal statistics
952 stat const& statistics() const
954 return base_class::statistics();
957 /// Returns const reference to mutex policy internal statistics
958 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
960 return base_class::mutex_policy_statistics();
965 }} // namespace cds::container
967 #endif //#ifndef __CDS_CONTAINER_CUCKOO_SET_H