2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_CUCKOO_SET_H
32 #define CDSLIB_CONTAINER_CUCKOO_SET_H
34 #include <cds/container/details/cuckoo_base.h>
35 #include <cds/details/binary_functor_wrapper.h>
37 namespace cds { namespace container {
41 template <typename T, typename Traits>
42 struct make_cuckoo_set
45 typedef Traits original_traits;
46 typedef typename original_traits::probeset_type probeset_type;
47 static bool const store_hash = original_traits::store_hash;
48 static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_traits::hash::hash_tuple_type >::value) : 0;
50 struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
55 node_type( Q const& v )
59 template <typename... Args>
60 node_type( Args&&... args )
61 : m_val( std::forward<Args>(args)...)
65 struct value_accessor {
66 value_type const& operator()( node_type const& node ) const
72 template <typename Pred, typename ReturnValue>
73 using predicate_wrapper = cds::details::binary_functor_wrapper< ReturnValue, Pred, node_type, value_accessor >;
75 struct intrusive_traits: public original_traits
77 typedef intrusive::cuckoo::base_hook<
78 cds::intrusive::cuckoo::probeset_type< probeset_type >
79 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
82 typedef cds::intrusive::cuckoo::traits::disposer disposer;
84 typedef typename std::conditional<
85 std::is_same< typename original_traits::equal_to, opt::none >::value
87 , predicate_wrapper< typename original_traits::equal_to, bool >
90 typedef typename std::conditional<
91 std::is_same< typename original_traits::compare, opt::none >::value
93 , predicate_wrapper< typename original_traits::compare, int >
96 typedef typename std::conditional<
97 std::is_same< typename original_traits::less, opt::none >::value
99 ,predicate_wrapper< typename original_traits::less, bool >
102 typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, value_accessor > hash;
105 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
107 } // namespace details
111 /** @ingroup cds_nonintrusive_set
114 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
115 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
117 <b>About Cuckoo hashing</b>
119 [From "The Art of Multiprocessor Programming"]
120 <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item
121 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
122 N = 2k we use a two-entry array of tables, and two independent hash functions,
123 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
124 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
125 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
126 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
127 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
129 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
130 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
131 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
132 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
133 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
134 until it finds an empty slot. We might not find an empty slot, either because the table is full,
135 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
136 number of successive displacements we are willing to undertake. When this limit is exceeded,
137 we resize the hash table, choose new hash functions and start over.
139 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
140 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
141 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
142 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
143 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
144 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
146 In current implementation, a probe set can be defined either as a (single-linked) list
147 or as a fixed-sized vector, optionally ordered.
149 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
150 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
151 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
153 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
154 The probe set may be ordered or not. Ordered probe set can be a little better since
155 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
156 However, the overhead of sorting can eliminate a gain of ordered search.
158 The probe set is ordered if \p compare or \p less is specified in \p Traits
159 template parameter. Otherwise, the probe set is unordered and \p Traits must contain
160 \p equal_to predicate.
163 - \p T - the type stored in the set.
164 - \p Traits - type traits. See cuckoo::traits for explanation.
165 It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
169 Cuckoo-set with list-based unordered probe set and storing hash values
171 #include <cds/container/cuckoo_set.h>
173 // Data stored in cuckoo set
183 // Provide equal_to functor for my_data since we will use unordered probe-set
184 struct my_data_equal_to {
185 bool operator()( const my_data& d1, const my_data& d2 ) const
187 return d1.strKey.compare( d2.strKey ) == 0;
190 bool operator()( const my_data& d, const std::string& s ) const
192 return d.strKey.compare(s) == 0;
195 bool operator()( const std::string& s, const my_data& d ) const
197 return s.compare( d.strKey ) == 0;
201 // Provide two hash functor for my_data
203 size_t operator()(std::string const& s) const
205 return cds::opt::v::hash<std::string>( s );
207 size_t operator()( my_data const& d ) const
209 return (*this)( d.strKey );
213 struct hash2: private hash1 {
214 size_t operator()(std::string const& s) const
216 size_t h = ~( hash1::operator()(s));
217 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
219 size_t operator()( my_data const& d ) const
221 return (*this)( d.strKey );
225 // Declare type traits
226 struct my_traits: public cds::container::cuckoo::traits
228 typedef my_data_equa_to equal_to;
229 typedef std::tuple< hash1, hash2 > hash;
231 static bool const store_hash = true;
234 // Declare CuckooSet type
235 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
237 // Equal option-based declaration
238 typedef cds::container::CuckooSet< my_data,
239 cds::container::cuckoo::make_traits<
240 cds::opt::hash< std::tuple< hash1, hash2 > >
241 ,cds::opt::equal_to< my_data_equal_to >
242 ,cds::container::cuckoo::store_hash< true >
247 If we provide \p compare function instead of \p equal_to for \p my_data
248 we get as a result a cuckoo set with ordered probe set that may improve
250 Example for ordered vector-based probe-set:
253 #include <cds/container/cuckoo_set.h>
255 // Data stored in cuckoo set
265 // Provide compare functor for my_data since we want to use ordered probe-set
266 struct my_data_compare {
267 int operator()( const my_data& d1, const my_data& d2 ) const
269 return d1.strKey.compare( d2.strKey );
272 int operator()( const my_data& d, const std::string& s ) const
274 return d.strKey.compare(s);
277 int operator()( const std::string& s, const my_data& d ) const
279 return s.compare( d.strKey );
283 // Provide two hash functor for my_data
285 size_t operator()(std::string const& s) const
287 return cds::opt::v::hash<std::string>( s );
289 size_t operator()( my_data const& d ) const
291 return (*this)( d.strKey );
295 struct hash2: private hash1 {
296 size_t operator()(std::string const& s) const
298 size_t h = ~( hash1::operator()(s));
299 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
301 size_t operator()( my_data const& d ) const
303 return (*this)( d.strKey );
307 // Declare type traits
308 // We use a vector of capacity 4 as probe-set container and store hash values in the node
309 struct my_traits: public cds::container::cuckoo::traits
311 typedef my_data_compare compare;
312 typedef std::tuple< hash1, hash2 > hash;
313 typedef cds::container::cuckoo::vector<4> probeset_type;
315 static bool const store_hash = true;
318 // Declare CuckooSet type
319 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
321 // Equal option-based declaration
322 typedef cds::container::CuckooSet< my_data,
323 cds::container::cuckoo::make_traits<
324 cds::opt::hash< std::tuple< hash1, hash2 > >
325 ,cds::opt::compare< my_data_compare >
326 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
327 ,cds::container::cuckoo::store_hash< true >
333 template <typename T, typename Traits = cuckoo::traits>
335 #ifdef CDS_DOXYGEN_INVOKED
336 protected intrusive::CuckooSet<T, Traits>
338 protected details::make_cuckoo_set<T, Traits>::type
342 typedef details::make_cuckoo_set<T, Traits> maker;
343 typedef typename maker::type base_class;
347 typedef T value_type ; ///< value type stored in the container
348 typedef Traits traits ; ///< traits
350 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
351 typedef typename base_class::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
353 typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see cuckoo::traits::mutex_policy
354 typedef typename base_class::stat stat; ///< internal statistics type
357 static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
358 static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
360 typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
362 typedef typename base_class::key_comparator key_comparator; ///< key comparing functor based on \p Traits::compare and \p Traits::less option setter. Used only for ordered probe set
364 typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
366 /// Node allocator type
367 typedef typename std::conditional<
368 std::is_same< typename traits::node_allocator, opt::none >::value,
370 typename traits::node_allocator
371 >::type node_allocator;
373 /// item counter type
374 typedef typename traits::item_counter item_counter;
378 typedef typename base_class::value_type node_type;
379 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
383 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
384 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
385 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
389 template <typename Q>
390 static node_type * alloc_node( Q const& v )
392 return cxx_node_allocator().New( v );
394 template <typename... Args>
395 static node_type * alloc_node( Args&&... args )
397 return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
400 static void free_node( node_type * pNode )
402 cxx_node_allocator().Delete( pNode );
408 struct node_disposer {
409 void operator()( node_type * pNode )
415 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
420 /// Default constructor
422 Initial size = \ref c_nDefaultInitialSize
425 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
426 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
428 Probe set threshold = probe set size - 1
433 /// Constructs the set object with given probe set size and threshold
435 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
436 then \p nProbesetSize should be equal to vector's \p Capacity.
439 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
440 , unsigned int nProbesetSize ///< probe set size
441 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
443 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
446 /// Constructs the set object with given hash functor tuple
448 The probe set size and threshold are set as default, see CuckooSet()
451 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
456 /// Constructs the set object with given probe set properties and hash functor tuple
458 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
459 then \p nProbesetSize should be equal to vector's \p Capacity.
462 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
463 , unsigned int nProbesetSize ///< probe set size
464 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
465 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
467 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
470 /// Constructs the set object with given hash functor tuple (move semantics)
472 The probe set size and threshold are set as default, see CuckooSet()
475 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
477 : base_class( std::forward<hash_tuple_type>(h))
480 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
482 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
483 then \p nProbesetSize should be equal to vector's \p Capacity.
486 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
487 , unsigned int nProbesetSize ///< probe set size
488 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
489 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
491 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h))
494 /// Destructor clears the set
503 The function creates a node with copy of \p val value
504 and then inserts the node created into the set.
506 The type \p Q should contain as minimum the complete key for the node.
507 The object of \ref value_type should be constructible from a value of type \p Q.
508 In trivial case, \p Q is equal to \ref value_type.
510 Returns \p true if \p val is inserted into the set, \p false otherwise.
512 template <typename Q>
513 bool insert( Q const& val )
515 return insert( val, []( value_type& ) {} );
520 The function allows to split creating of new item into two part:
521 - create item with key only
522 - insert new item into the set
523 - if inserting is success, calls \p f functor to initialize value-field of new item .
525 The functor signature is:
527 void func( value_type& item );
529 where \p item is the item inserted.
531 The type \p Q can differ from \ref value_type of items storing in the set.
532 Therefore, the \p value_type should be constructible from type \p Q.
534 The user-defined functor is called only if the inserting is success.
536 template <typename Q, typename Func>
537 bool insert( Q const& val, Func f )
539 scoped_node_ptr pNode( alloc_node( val ));
540 if ( base_class::insert( *pNode, [&f]( node_type& node ) { f( node.m_val ); } )) {
547 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
549 Returns \p true if inserting successful, \p false otherwise.
551 template <typename... Args>
552 bool emplace( Args&&... args )
554 scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
555 if ( base_class::insert( *pNode )) {
564 The operation performs inserting or changing data with lock-free manner.
566 If the item \p val is not found in the set, then \p val is inserted into the set
567 iff \p bAllowInsert is \p true.
568 Otherwise, the functor \p func is called with item found.
569 The functor \p func signature is:
572 void operator()( bool bNew, value_type& item, const Q& val );
576 - \p bNew - \p true if the item has been inserted, \p false otherwise
577 - \p item - item of the set
578 - \p val - argument \p val passed into the \p %update() function
579 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
580 refer to the same thing.
582 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
583 i.e. the node has been inserted or updated,
584 \p second is \p true if new item has been added or \p false if the item with \p key
587 template <typename Q, typename Func>
588 std::pair<bool, bool> update( Q const& val, Func func, bool bAllowInsert = true )
590 scoped_node_ptr pNode( alloc_node( val ));
591 std::pair<bool, bool> res = base_class::update( *pNode,
592 [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); },
595 if ( res.first && res.second )
600 template <typename Q, typename Func>
601 CDS_DEPRECATED("ensure() is deprecated, use update()")
602 std::pair<bool, bool> ensure( Q const& val, Func func )
604 return update( val, func, true );
608 /// Delete \p key from the set
609 /** \anchor cds_nonintrusive_CuckooSet_erase
611 Since the key of set's item type \ref value_type is not explicitly specified,
612 template parameter \p Q defines the key type searching in the list.
613 The set item comparator should be able to compare the type \p value_type
616 Return \p true if key is found and deleted, \p false otherwise
618 template <typename Q>
619 bool erase( Q const& key )
621 node_type * pNode = base_class::erase( key );
629 /// Deletes the item from the list using \p pred predicate for searching
631 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
632 but \p pred is used for key comparing.
633 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
634 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
635 \p Predicate must imply the same element order as the comparator used for building the set.
637 template <typename Q, typename Predicate>
638 bool erase_with( Q const& key, Predicate pred )
641 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>());
649 /// Delete \p key from the set
650 /** \anchor cds_nonintrusive_CuckooSet_erase_func
652 The function searches an item with key \p key, calls \p f functor
653 and deletes the item. If \p key is not found, the functor is not called.
655 The functor \p Func interface is:
658 void operator()(value_type const& val);
662 Return \p true if key is found and deleted, \p false otherwise
664 template <typename Q, typename Func>
665 bool erase( Q const& key, Func f )
667 node_type * pNode = base_class::erase( key );
676 /// Deletes the item from the list using \p pred predicate for searching
678 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
679 but \p pred is used for key comparing.
680 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
681 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
682 \p Predicate must imply the same element order as the comparator used for building the set.
684 template <typename Q, typename Predicate, typename Func>
685 bool erase_with( Q const& key, Predicate pred, Func f )
688 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>());
697 /// Find the key \p val
698 /** \anchor cds_nonintrusive_CuckooSet_find_func
700 The function searches the item with key equal to \p val and calls the functor \p f for item found.
701 The interface of \p Func functor is:
704 void operator()( value_type& item, Q& val );
707 where \p item is the item found, \p val is the <tt>find</tt> function argument.
709 The functor can change non-key fields of \p item.
710 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
711 can modify both arguments.
713 The type \p Q can differ from \ref value_type of items storing in the container.
714 Therefore, the \p value_type should be comparable with type \p Q.
716 The function returns \p true if \p val is found, \p false otherwise.
718 template <typename Q, typename Func>
719 bool find( Q& val, Func f )
721 return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
724 template <typename Q, typename Func>
725 bool find( Q const& val, Func f )
727 return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
731 /// Find the key \p val using \p pred predicate for comparing
733 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
734 but \p pred is used for key comparison.
735 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
736 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
737 \p pred must imply the same element order as the comparator used for building the set.
739 template <typename Q, typename Predicate, typename Func>
740 bool find_with( Q& val, Predicate pred, Func f )
743 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
744 [&f](node_type& item, Q& v) { f( item.m_val, v );});
747 template <typename Q, typename Predicate, typename Func>
748 bool find_with( Q const& val, Predicate pred, Func f )
751 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
752 [&f](node_type& item, Q const& v) { f( item.m_val, v );});
756 /// Checks whether the set contains \p key
758 The function searches the item with key equal to \p key
759 and returns \p true if it is found, and \p false otherwise.
761 template <typename Q>
762 bool contains( Q const& key )
764 return base_class::find( key, [](node_type&, Q const&) {});
767 template <typename Q>
768 CDS_DEPRECATED("the function is deprecated, use contains()")
769 bool find( Q const& key )
771 return contains( key );
775 /// Checks whether the set contains \p key using \p pred predicate for searching
777 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
778 \p Less functor has the interface like \p std::less.
779 \p Less must imply the same element order as the comparator used for building the set.
781 template <typename Q, typename Predicate>
782 bool contains( Q const& key, Predicate pred )
785 return base_class::find_with( key, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
788 template <typename Q, typename Predicate>
789 CDS_DEPRECATED("the function is deprecated, use contains()")
790 bool find_with( Q const& key, Predicate pred )
792 return contains( key, pred );
798 The function erases all items from the set.
802 return base_class::clear_and_dispose( node_disposer());
805 /// Checks if the set is empty
807 Emptiness is checked by item counting: if item count is zero then the set is empty.
811 return base_class::empty();
814 /// Returns item count in the set
817 return base_class::size();
820 /// Returns the size of hash table
822 The hash table size is non-constant and can be increased via resizing.
824 size_t bucket_count() const
826 return base_class::bucket_count();
829 /// Returns lock array size
830 size_t lock_count() const
832 return base_class::lock_count();
835 /// Returns const reference to internal statistics
836 stat const& statistics() const
838 return base_class::statistics();
841 /// Returns const reference to mutex policy internal statistics
842 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
844 return base_class::mutex_policy_statistics();
848 }} // namespace cds::container
850 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_SET_H