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 #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 >;
53 template <typename Pred, typename ReturnValue>
54 struct predicate_wrapper: public cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >
58 struct intrusive_traits: public original_type_traits
60 typedef intrusive::cuckoo::base_hook<
61 cds::intrusive::cuckoo::probeset_type< probeset_type >
62 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
65 typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
67 typedef typename std::conditional<
68 std::is_same< typename original_type_traits::equal_to, opt::none >::value
70 , predicate_wrapper< typename original_type_traits::equal_to, bool >
73 typedef typename std::conditional<
74 std::is_same< typename original_type_traits::compare, opt::none >::value
76 , predicate_wrapper< typename original_type_traits::compare, int >
79 typedef typename std::conditional<
80 std::is_same< typename original_type_traits::less, opt::none >::value
82 ,predicate_wrapper< typename original_type_traits::less, bool >
85 typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, value_accessor > hash;
88 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
90 } // namespace details
94 /** @ingroup cds_nonintrusive_set
97 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
98 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
100 <b>About Cuckoo hashing</b>
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.
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 nullptr, 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 nullptr, 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.
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.
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.
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>.
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.
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.
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.
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
185 Cuckoo-set with list-based unordered probe set and storing hash values
187 #include <cds/container/cuckoo_set.h>
189 // Data stored in cuckoo set
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
203 return d1.strKey.compare( d2.strKey ) == 0;
206 bool operator()( const my_data& d, const std::string& s ) const
208 return d.strKey.compare(s) == 0;
211 bool operator()( const std::string& s, const my_data& d ) const
213 return s.compare( d.strKey ) == 0;
217 // Provide two hash functor for my_data
219 size_t operator()(std::string const& s) const
221 return cds::opt::v::hash<std::string>( s );
223 size_t operator()( my_data const& d ) const
225 return (*this)( d.strKey );
229 struct hash2: private hash1 {
230 size_t operator()(std::string const& s) const
232 size_t h = ~( hash1::operator()(s));
233 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
235 size_t operator()( my_data const& d ) const
237 return (*this)( d.strKey );
241 // Declare type traits
242 struct my_traits: public cds::container::cuckoo::type_traits
244 typedef my_data_equa_to equal_to;
245 typedef std::tuple< hash1, hash2 > hash;
247 static bool const store_hash = true;
250 // Declare CuckooSet type
251 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
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 >
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
266 Example for ordered vector-based probe-set:
269 #include <cds/container/cuckoo_set.h>
271 // Data stored in cuckoo set
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
285 return d1.strKey.compare( d2.strKey );
288 int operator()( const my_data& d, const std::string& s ) const
290 return d.strKey.compare(s);
293 int operator()( const std::string& s, const my_data& d ) const
295 return s.compare( d.strKey );
299 // Provide two hash functor for my_data
301 size_t operator()(std::string const& s) const
303 return cds::opt::v::hash<std::string>( s );
305 size_t operator()( my_data const& d ) const
307 return (*this)( d.strKey );
311 struct hash2: private hash1 {
312 size_t operator()(std::string const& s) const
314 size_t h = ~( hash1::operator()(s));
315 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
317 size_t operator()( my_data const& d ) const
319 return (*this)( d.strKey );
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
327 typedef my_data_compare compare;
328 typedef std::tuple< hash1, hash2 > hash;
329 typedef cds::container::cuckoo::vector<4> probeset_type;
331 static bool const store_hash = true;
334 // Declare CuckooSet type
335 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
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 >
349 template <typename T, typename Traits = cuckoo::type_traits>
351 #ifdef CDS_DOXYGEN_INVOKED
352 protected intrusive::CuckooSet<T, Traits>
354 protected details::make_cuckoo_set<T, Traits>::type
358 typedef details::make_cuckoo_set<T, Traits> maker;
359 typedef typename maker::type base_class;
363 typedef T value_type ; ///< value type stored in the container
364 typedef Traits options ; ///< traits
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
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
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.
376 typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
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
380 typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
382 /// Node allocator type
383 typedef typename std::conditional<
384 std::is_same< typename options::node_allocator, opt::none >::value,
386 typename options::node_allocator
387 >::type node_allocator;
389 /// item counter type
390 typedef typename options::item_counter item_counter;
394 typedef typename base_class::value_type node_type;
395 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
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
405 template <typename Q>
406 static node_type * alloc_node( Q const& v )
408 return cxx_node_allocator().New( v );
410 # ifdef CDS_EMPLACE_SUPPORT
411 template <typename... Args>
412 static node_type * alloc_node( Args&&... args )
414 return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
418 static void free_node( node_type * pNode )
420 cxx_node_allocator().Delete( pNode );
426 struct node_disposer {
427 void operator()( node_type * pNode )
433 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
435 # ifndef CDS_CXX11_LAMBDA_SUPPORT
436 struct empty_insert_functor {
437 void operator()( value_type& ) const
441 struct empty_find_functor {
442 template <typename Q>
443 void operator()( node_type& item, Q& val ) const
447 template <typename Func>
448 class insert_wrapper: protected cds::details::functor_wrapper<Func>
450 typedef cds::details::functor_wrapper<Func> base_class;
452 insert_wrapper( Func f ): base_class(f) {}
454 void operator()( node_type& node )
456 base_class::get()( node.m_val );
460 template <typename Q, typename Func>
461 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
463 typedef cds::details::functor_wrapper<Func> base_class;
467 ensure_wrapper( Q const& v, Func f) : base_class(f), val(v) {}
469 void operator()( bool bNew, node_type& item, node_type const& )
471 base_class::get()( bNew, item.m_val, val );
475 template <typename Func>
476 class find_wrapper: protected cds::details::functor_wrapper<Func>
478 typedef cds::details::functor_wrapper<Func> base_class;
480 find_wrapper( Func f )
484 template <typename Q>
485 void operator()( node_type& item, Q& val )
487 base_class::get()( item.m_val, val );
494 /// Default constructor
496 Initial size = \ref c_nDefaultInitialSize
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>
502 Probe set threshold = probe set size - 1
507 /// Constructs the set object with given probe set size and threshold
509 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
510 then \p nProbesetSize should be equal to vector's \p Capacity.
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
517 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
520 /// Constructs the set object with given hash functor tuple
522 The probe set size and threshold are set as default, see 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>
530 /// Constructs the set object with given probe set properties and hash functor tuple
532 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
533 then \p nProbesetSize should be equal to vector's \p Capacity.
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>
541 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
544 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
545 /// Constructs the set object with given hash functor tuple (move semantics)
547 The probe set size and threshold are set as default, see 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>
552 : base_class( std::forward<hash_tuple_type>(h) )
555 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
557 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
558 then \p nProbesetSize should be equal to vector's \p Capacity.
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>
566 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
568 # endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
570 /// Destructor clears the set
579 The function creates a node with copy of \p val value
580 and then inserts the node created into the set.
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.
586 Returns \p true if \p val is inserted into the set, \p false otherwise.
588 template <typename Q>
589 bool insert( Q const& val )
591 # ifdef CDS_CXX11_LAMBDA_SUPPORT
592 return insert( val, []( value_type& ) {} );
594 return insert( val, empty_insert_functor() );
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 .
605 The functor signature is:
607 void func( value_type& item );
609 where \p item is the item inserted.
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.
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>
617 template <typename Q, typename Func>
618 bool insert( Q const& val, Func f )
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 ); } ))
624 insert_wrapper<Func> wrapper( f );
625 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
634 # ifdef CDS_EMPLACE_SUPPORT
635 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
637 Returns \p true if inserting successful, \p false otherwise.
639 This function is available only for compiler that supports
640 variadic template and move semantics
642 template <typename... Args>
643 bool emplace( Args&&... args )
645 scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
646 if ( base_class::insert( *pNode )) {
654 /// Ensures that the \p val exists in the set
656 The operation performs inserting or changing data.
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:
662 void func( bool bNew, value_type& item, const Q& val );
667 void operator()( bool bNew, value_type& item, const Q& val );
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
676 The functor can change non-key fields of the \p item.
678 You can pass \p func argument by value or by reference using <tt>boost::ref</tt>.
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
684 template <typename Q, typename Func>
685 std::pair<bool, bool> ensure( Q const& val, Func func )
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 ); }
693 ensure_wrapper<Q, Func> wrapper( val, func );
694 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
696 if ( res.first && res.second )
701 /// Delete \p key from the set
702 /** \anchor cds_nonintrusive_CuckooSet_erase
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
709 Return \p true if key is found and deleted, \p false otherwise
711 template <typename Q>
712 bool erase( Q const& key )
714 node_type * pNode = base_class::erase( key );
722 /// Deletes the item from the list using \p pred predicate for searching
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.
730 template <typename Q, typename Predicate>
731 bool erase_with( Q const& key, Predicate pred )
733 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
741 /// Delete \p key from the set
742 /** \anchor cds_nonintrusive_CuckooSet_erase_func
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.
747 The functor \p Func interface is:
750 void operator()(value_type const& val);
753 The functor can be passed by value or by reference using <tt>boost:ref</tt>
755 Return \p true if key is found and deleted, \p false otherwise
757 template <typename Q, typename Func>
758 bool erase( Q const& key, Func f )
760 node_type * pNode = base_class::erase( key );
762 cds::unref(f)( pNode->m_val );
769 /// Deletes the item from the list using \p pred predicate for searching
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.
777 template <typename Q, typename Predicate, typename Func>
778 bool erase_with( Q const& key, Predicate pred, Func f )
780 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
782 cds::unref(f)( pNode->m_val );
789 /// Find the key \p val
790 /** \anchor cds_nonintrusive_CuckooSet_find_func
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:
796 void operator()( value_type& item, Q& val );
799 where \p item is the item found, \p val is the <tt>find</tt> function argument.
801 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
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.
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.
810 The function returns \p true if \p val is found, \p false otherwise.
812 template <typename Q, typename Func>
813 bool find( Q& val, Func f )
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 );});
818 find_wrapper<Func> wrapper(f);
819 return base_class::find( val, cds::ref(wrapper) );
823 /// Find the key \p val using \p pred predicate for comparing
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.
831 template <typename Q, typename Predicate, typename Func>
832 bool find_with( Q& val, Predicate pred, Func f )
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 );});
838 find_wrapper<Func> wrapper(f);
839 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
843 /// Find the key \p val
844 /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
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:
850 void operator()( value_type& item, Q const& val );
853 where \p item is the item found, \p val is the <tt>find</tt> function argument.
855 You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
857 The functor can change non-key fields of \p item.
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.
862 The function returns \p true if \p val is found, \p false otherwise.
864 template <typename Q, typename Func>
865 bool find( Q const& val, Func f )
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 );});
870 find_wrapper<Func> wrapper(f);
871 return base_class::find( val, cds::ref(wrapper) );
875 /// Find the key \p val using \p pred predicate for comparing
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.
883 template <typename Q, typename Predicate, typename Func>
884 bool find_with( Q const& val, Predicate pred, Func f )
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 );});
890 find_wrapper<Func> wrapper(f);
891 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), cds::ref(wrapper) );
895 /// Find the key \p val
896 /** \anchor cds_nonintrusive_CuckooSet_find_val
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.
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.
904 template <typename Q>
905 bool find( Q const& val )
907 # ifdef CDS_CXX11_LAMBDA_SUPPORT
908 return base_class::find( val, [](node_type&, Q const&) {});
910 return base_class::find( val, empty_find_functor());
914 /// Find the key \p val using \p pred predicate for comparing
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.
922 template <typename Q, typename Predicate>
923 bool find_with( Q const& val, Predicate pred )
925 # ifdef CDS_CXX11_LAMBDA_SUPPORT
926 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
928 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), empty_find_functor());
934 The function erases all items from the set.
938 return base_class::clear_and_dispose( node_disposer() );
941 /// Checks if the set is empty
943 Emptiness is checked by item counting: if item count is zero then the set is empty.
947 return base_class::empty();
950 /// Returns item count in the set
953 return base_class::size();
956 /// Returns the size of hash table
958 The hash table size is non-constant and can be increased via resizing.
960 size_t bucket_count() const
962 return base_class::bucket_count();
965 /// Returns lock array size
966 size_t lock_count() const
968 return base_class::lock_count();
971 /// Returns const reference to internal statistics
972 stat const& statistics() const
974 return base_class::statistics();
977 /// Returns const reference to mutex policy internal statistics
978 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
980 return base_class::mutex_policy_statistics();
985 }} // namespace cds::container
987 #endif //#ifndef __CDS_CONTAINER_CUCKOO_SET_H