3 #ifndef CDSLIB_CONTAINER_CUCKOO_SET_H
4 #define CDSLIB_CONTAINER_CUCKOO_SET_H
6 #include <cds/container/details/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_traits;
18 typedef typename original_traits::probeset_type probeset_type;
19 static bool const store_hash = original_traits::store_hash;
20 static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_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_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::traits::disposer disposer;
56 typedef typename std::conditional<
57 std::is_same< typename original_traits::equal_to, opt::none >::value
59 , predicate_wrapper< typename original_traits::equal_to, bool >
62 typedef typename std::conditional<
63 std::is_same< typename original_traits::compare, opt::none >::value
65 , predicate_wrapper< typename original_traits::compare, int >
68 typedef typename std::conditional<
69 std::is_same< typename original_traits::less, opt::none >::value
71 ,predicate_wrapper< typename original_traits::less, bool >
74 typedef opt::details::hash_list_wrapper< typename original_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::traits for explanation.
137 It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
141 Cuckoo-set with list-based unordered probe set and storing hash values
143 #include <cds/container/cuckoo_set.h>
145 // Data stored in cuckoo set
155 // Provide equal_to functor for my_data since we will use unordered probe-set
156 struct my_data_equal_to {
157 bool operator()( const my_data& d1, const my_data& d2 ) const
159 return d1.strKey.compare( d2.strKey ) == 0;
162 bool operator()( const my_data& d, const std::string& s ) const
164 return d.strKey.compare(s) == 0;
167 bool operator()( const std::string& s, const my_data& d ) const
169 return s.compare( d.strKey ) == 0;
173 // Provide two hash functor for my_data
175 size_t operator()(std::string const& s) const
177 return cds::opt::v::hash<std::string>( s );
179 size_t operator()( my_data const& d ) const
181 return (*this)( d.strKey );
185 struct hash2: private hash1 {
186 size_t operator()(std::string const& s) const
188 size_t h = ~( hash1::operator()(s));
189 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
191 size_t operator()( my_data const& d ) const
193 return (*this)( d.strKey );
197 // Declare type traits
198 struct my_traits: public cds::container::cuckoo::traits
200 typedef my_data_equa_to equal_to;
201 typedef std::tuple< hash1, hash2 > hash;
203 static bool const store_hash = true;
206 // Declare CuckooSet type
207 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
209 // Equal option-based declaration
210 typedef cds::container::CuckooSet< my_data,
211 cds::container::cuckoo::make_traits<
212 cds::opt::hash< std::tuple< hash1, hash2 > >
213 ,cds::opt::equal_to< my_data_equal_to >
214 ,cds::container::cuckoo::store_hash< true >
219 If we provide \p compare function instead of \p equal_to for \p my_data
220 we get as a result a cuckoo set with ordered probe set that may improve
222 Example for ordered vector-based probe-set:
225 #include <cds/container/cuckoo_set.h>
227 // Data stored in cuckoo set
237 // Provide compare functor for my_data since we want to use ordered probe-set
238 struct my_data_compare {
239 int operator()( const my_data& d1, const my_data& d2 ) const
241 return d1.strKey.compare( d2.strKey );
244 int operator()( const my_data& d, const std::string& s ) const
246 return d.strKey.compare(s);
249 int operator()( const std::string& s, const my_data& d ) const
251 return s.compare( d.strKey );
255 // Provide two hash functor for my_data
257 size_t operator()(std::string const& s) const
259 return cds::opt::v::hash<std::string>( s );
261 size_t operator()( my_data const& d ) const
263 return (*this)( d.strKey );
267 struct hash2: private hash1 {
268 size_t operator()(std::string const& s) const
270 size_t h = ~( hash1::operator()(s));
271 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
273 size_t operator()( my_data const& d ) const
275 return (*this)( d.strKey );
279 // Declare type traits
280 // We use a vector of capacity 4 as probe-set container and store hash values in the node
281 struct my_traits: public cds::container::cuckoo::traits
283 typedef my_data_compare compare;
284 typedef std::tuple< hash1, hash2 > hash;
285 typedef cds::container::cuckoo::vector<4> probeset_type;
287 static bool const store_hash = true;
290 // Declare CuckooSet type
291 typedef cds::container::CuckooSet< my_data, my_traits > my_cuckoo_set;
293 // Equal option-based declaration
294 typedef cds::container::CuckooSet< my_data,
295 cds::container::cuckoo::make_traits<
296 cds::opt::hash< std::tuple< hash1, hash2 > >
297 ,cds::opt::compare< my_data_compare >
298 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
299 ,cds::container::cuckoo::store_hash< true >
305 template <typename T, typename Traits = cuckoo::traits>
307 #ifdef CDS_DOXYGEN_INVOKED
308 protected intrusive::CuckooSet<T, Traits>
310 protected details::make_cuckoo_set<T, Traits>::type
314 typedef details::make_cuckoo_set<T, Traits> maker;
315 typedef typename maker::type base_class;
319 typedef T value_type ; ///< value type stored in the container
320 typedef Traits traits ; ///< traits
322 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
323 typedef typename base_class::hash_tuple_type hash_tuple_type; ///< Type of hash tuple
325 typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see cuckoo::traits::mutex_policy
326 typedef typename base_class::stat stat; ///< internal statistics type
329 static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
330 static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
332 typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
334 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
336 typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
338 /// Node allocator type
339 typedef typename std::conditional<
340 std::is_same< typename traits::node_allocator, opt::none >::value,
342 typename traits::node_allocator
343 >::type node_allocator;
345 /// item counter type
346 typedef typename traits::item_counter item_counter;
349 typedef cds::container::cuckoo::implementation_tag implementation_tag;
354 typedef typename base_class::value_type node_type;
355 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
359 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
360 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
361 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
365 template <typename Q>
366 static node_type * alloc_node( Q const& v )
368 return cxx_node_allocator().New( v );
370 template <typename... Args>
371 static node_type * alloc_node( Args&&... args )
373 return cxx_node_allocator().MoveNew( std::forward<Args>(args)... );
376 static void free_node( node_type * pNode )
378 cxx_node_allocator().Delete( pNode );
384 struct node_disposer {
385 void operator()( node_type * pNode )
391 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
396 /// Default constructor
398 Initial size = \ref c_nDefaultInitialSize
401 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
402 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
404 Probe set threshold = probe set size - 1
409 /// Constructs the set object with given probe set size and threshold
411 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
412 then \p nProbesetSize should be equal to vector's \p Capacity.
415 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
416 , unsigned int nProbesetSize ///< probe set size
417 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
419 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
422 /// Constructs the set object with given hash functor tuple
424 The probe set size and threshold are set as default, see CuckooSet()
427 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
432 /// Constructs the set object with given probe set properties and hash functor tuple
434 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
435 then \p nProbesetSize should be equal to vector's \p Capacity.
438 size_t nInitialSize ///< Initial set size; if 0 - use default initial size \ref c_nDefaultInitialSize
439 , unsigned int nProbesetSize ///< probe set size
440 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
441 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
443 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
446 /// Constructs the set object with given hash functor tuple (move semantics)
448 The probe set size and threshold are set as default, see CuckooSet()
451 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
453 : base_class( std::forward<hash_tuple_type>(h) )
456 /// Constructs the set object with given probe set properties and hash functor tuple (move semantics)
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&& 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, std::forward<hash_tuple_type>(h) )
470 /// Destructor clears the set
479 The function creates a node with copy of \p val value
480 and then inserts the node created into the set.
482 The type \p Q should contain as minimum the complete key for the node.
483 The object of \ref value_type should be constructible from a value of type \p Q.
484 In trivial case, \p Q is equal to \ref value_type.
486 Returns \p true if \p val is inserted into the set, \p false otherwise.
488 template <typename Q>
489 bool insert( Q const& val )
491 return insert( val, []( value_type& ) {} );
496 The function allows to split creating of new item into two part:
497 - create item with key only
498 - insert new item into the set
499 - if inserting is success, calls \p f functor to initialize value-field of new item .
501 The functor signature is:
503 void func( value_type& item );
505 where \p item is the item inserted.
507 The type \p Q can differ from \ref value_type of items storing in the set.
508 Therefore, the \p value_type should be constructible from type \p Q.
510 The user-defined functor is called only if the inserting is success.
512 template <typename Q, typename Func>
513 bool insert( Q const& val, Func f )
515 scoped_node_ptr pNode( alloc_node( val ));
516 if ( base_class::insert( *pNode, [&f]( node_type& node ) { f( node.m_val ); } )) {
523 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
525 Returns \p true if inserting successful, \p false otherwise.
527 template <typename... Args>
528 bool emplace( Args&&... args )
530 scoped_node_ptr pNode( alloc_node( std::forward<Args>(args)... ));
531 if ( base_class::insert( *pNode )) {
538 /// Ensures that the \p val exists in the set
540 The operation performs inserting or changing data.
542 If the \p val key not found in the set, then the new item created from \p val
543 is inserted into the set. Otherwise, the functor \p func is called with the item found.
544 The functor \p Func should be a function with signature:
546 void func( bool bNew, value_type& item, const Q& val );
551 void operator()( bool bNew, value_type& item, const Q& val );
556 - \p bNew - \p true if the item has been inserted, \p false otherwise
557 - \p item - item of the set
558 - \p val - argument \p val passed into the \p ensure function
560 The functor can change non-key fields of the \p item.
562 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
563 \p second is true if new item has been added or \p false if the item with \p val key
566 template <typename Q, typename Func>
567 std::pair<bool, bool> ensure( Q const& val, Func func )
569 scoped_node_ptr pNode( alloc_node( val ));
570 std::pair<bool, bool> res = base_class::ensure( *pNode,
571 [&val,&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val, val ); }
573 if ( res.first && res.second )
578 /// Delete \p key from the set
579 /** \anchor cds_nonintrusive_CuckooSet_erase
581 Since the key of set's item type \ref value_type is not explicitly specified,
582 template parameter \p Q defines the key type searching in the list.
583 The set item comparator should be able to compare the type \p value_type
586 Return \p true if key is found and deleted, \p false otherwise
588 template <typename Q>
589 bool erase( Q const& key )
591 node_type * pNode = base_class::erase( key );
599 /// Deletes the item from the list using \p pred predicate for searching
601 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase "erase(Q const&)"
602 but \p pred is used for key comparing.
603 If cuckoo set is ordered, then \p Predicate should have the interface and semantics like \p std::less.
604 If cuckoo set is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
605 \p Predicate must imply the same element order as the comparator used for building the set.
607 template <typename Q, typename Predicate>
608 bool erase_with( Q const& key, Predicate pred )
611 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
619 /// Delete \p key from the set
620 /** \anchor cds_nonintrusive_CuckooSet_erase_func
622 The function searches an item with key \p key, calls \p f functor
623 and deletes the item. If \p key is not found, the functor is not called.
625 The functor \p Func interface is:
628 void operator()(value_type const& val);
632 Return \p true if key is found and deleted, \p false otherwise
634 template <typename Q, typename Func>
635 bool erase( Q const& key, Func f )
637 node_type * pNode = base_class::erase( key );
646 /// Deletes the item from the list using \p pred predicate for searching
648 The function is an analog of \ref cds_nonintrusive_CuckooSet_erase_func "erase(Q const&, Func)"
649 but \p pred is used for key comparing.
650 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
651 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
652 \p Predicate must imply the same element order as the comparator used for building the set.
654 template <typename Q, typename Predicate, typename Func>
655 bool erase_with( Q const& key, Predicate pred, Func f )
658 node_type * pNode = base_class::erase_with( key, typename maker::template predicate_wrapper<Predicate, bool>() );
667 /// Find the key \p val
668 /** \anchor cds_nonintrusive_CuckooSet_find_func
670 The function searches the item with key equal to \p val and calls the functor \p f for item found.
671 The interface of \p Func functor is:
674 void operator()( value_type& item, Q& val );
677 where \p item is the item found, \p val is the <tt>find</tt> function argument.
679 The functor can change non-key fields of \p item.
680 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
681 can modify both arguments.
683 The type \p Q can differ from \ref value_type of items storing in the container.
684 Therefore, the \p value_type should be comparable with type \p Q.
686 The function returns \p true if \p val is found, \p false otherwise.
688 template <typename Q, typename Func>
689 bool find( Q& val, Func f )
691 return base_class::find( val, [&f](node_type& item, Q& v) { f( item.m_val, v );});
694 /// Find the key \p val using \p pred predicate for comparing
696 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_func "find(Q&, Func)"
697 but \p pred is used for key comparison.
698 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
699 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
700 \p pred must imply the same element order as the comparator used for building the set.
702 template <typename Q, typename Predicate, typename Func>
703 bool find_with( Q& val, Predicate pred, Func f )
706 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
707 [&f](node_type& item, Q& v) { f( item.m_val, v );});
710 /// Find the key \p val
711 /** \anchor cds_nonintrusive_CuckooSet_find_cfunc
713 The function searches the item with key equal to \p val and calls the functor \p f for item found.
714 The interface of \p Func functor is:
717 void operator()( value_type& item, Q const& val );
720 where \p item is the item found, \p val is the <tt>find</tt> function argument.
722 The functor can change non-key fields of \p item.
724 The type \p Q can differ from \ref value_type of items storing in the container.
725 Therefore, the \p value_type should be comparable with type \p Q.
727 The function returns \p true if \p val is found, \p false otherwise.
729 template <typename Q, typename Func>
730 bool find( Q const& val, Func f )
732 return base_class::find( val, [&f](node_type& item, Q const& v) { f( item.m_val, v );});
735 /// Find the key \p val using \p pred predicate for comparing
737 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_cfunc "find(Q const&, Func)"
738 but \p pred is used for key comparison.
739 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
740 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
741 \p pred must imply the same element order as the comparator used for building the set.
743 template <typename Q, typename Predicate, typename Func>
744 bool find_with( Q const& val, Predicate pred, Func f )
747 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(),
748 [&f](node_type& item, Q const& v) { f( item.m_val, v );});
751 /// Find the key \p val
752 /** \anchor cds_nonintrusive_CuckooSet_find_val
754 The function searches the item with key equal to \p val
755 and returns \p true if it is found, and \p false otherwise.
757 Note the hash functor specified for class \p Traits template parameter
758 should accept a parameter of type \p Q that can be not the same as \ref value_type.
760 template <typename Q>
761 bool find( Q const& val )
763 return base_class::find( val, [](node_type&, Q const&) {});
766 /// Find the key \p val using \p pred predicate for comparing
768 The function is an analog of \ref cds_nonintrusive_CuckooSet_find_val "find(Q const&)"
769 but \p pred is used for key comparison.
770 If you use ordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::less.
771 If you use unordered cuckoo set, then \p Predicate should have the interface and semantics like \p std::equal_to.
772 \p pred must imply the same element order as the comparator used for building the set.
774 template <typename Q, typename Predicate>
775 bool find_with( Q const& val, Predicate pred )
778 return base_class::find_with( val, typename maker::template predicate_wrapper<Predicate, bool>(), [](node_type&, Q const&) {});
783 The function erases all items from the set.
787 return base_class::clear_and_dispose( node_disposer() );
790 /// Checks if the set is empty
792 Emptiness is checked by item counting: if item count is zero then the set is empty.
796 return base_class::empty();
799 /// Returns item count in the set
802 return base_class::size();
805 /// Returns the size of hash table
807 The hash table size is non-constant and can be increased via resizing.
809 size_t bucket_count() const
811 return base_class::bucket_count();
814 /// Returns lock array size
815 size_t lock_count() const
817 return base_class::lock_count();
820 /// Returns const reference to internal statistics
821 stat const& statistics() const
823 return base_class::statistics();
826 /// Returns const reference to mutex policy internal statistics
827 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
829 return base_class::mutex_policy_statistics();
833 }} // namespace cds::container
835 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_SET_H