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_MAP_H
32 #define CDSLIB_CONTAINER_CUCKOO_MAP_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 Key, typename T, typename Traits>
42 struct make_cuckoo_map
44 typedef Key key_type; ///< key type
45 typedef T mapped_type; ///< type of value stored in the map
46 typedef std::pair<key_type const, mapped_type> value_type; ///< Pair type
48 typedef Traits original_traits;
49 typedef typename original_traits::probeset_type probeset_type;
50 static bool const store_hash = original_traits::store_hash;
51 static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_traits::hash::hash_tuple_type >::value) : 0;
53 struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
58 node_type( K const& key )
59 : m_val( std::make_pair( key_type(key), mapped_type()))
62 template <typename K, typename Q>
63 node_type( K const& key, Q const& v )
64 : m_val( std::make_pair( key_type(key), mapped_type(v)))
67 template <typename K, typename... Args>
68 node_type( K&& key, Args&&... args )
69 : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)))
74 key_type const& operator()( node_type const& node ) const
76 return node.m_val.first;
80 struct intrusive_traits: public original_traits
82 typedef intrusive::cuckoo::base_hook<
83 cds::intrusive::cuckoo::probeset_type< probeset_type >
84 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
87 typedef cds::intrusive::cuckoo::traits::disposer disposer;
89 typedef typename std::conditional<
90 std::is_same< typename original_traits::equal_to, opt::none >::value
92 , cds::details::predicate_wrapper< node_type, typename original_traits::equal_to, key_accessor >
95 typedef typename std::conditional<
96 std::is_same< typename original_traits::compare, opt::none >::value
98 , cds::details::compare_wrapper< node_type, typename original_traits::compare, key_accessor >
101 typedef typename std::conditional<
102 std::is_same< typename original_traits::less, opt::none >::value
104 ,cds::details::predicate_wrapper< node_type, typename original_traits::less, key_accessor >
107 typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, key_accessor > hash;
110 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
112 } // namespace details
116 /** @ingroup cds_nonintrusive_map
119 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
120 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
122 <b>About Cuckoo hashing</b>
124 [From "The Art of Multiprocessor Programming"]
125 <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
126 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
127 N = 2k we use a two-entry array of tables, and two independent hash functions,
128 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
129 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
130 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
131 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
132 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
134 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
135 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
136 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
137 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
138 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
139 until it finds an empty slot. We might not find an empty slot, either because the table is full,
140 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
141 number of successive displacements we are willing to undertake. When this limit is exceeded,
142 we resize the hash table, choose new hash functions and start over.
144 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
145 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
146 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
147 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
148 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
149 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
151 In current implementation, a probe set can be defined either as a (single-linked) list
152 or as a fixed-sized vector, optionally ordered.
154 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
155 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
156 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
158 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
159 The probe set may be ordered or not. Ordered probe set can be a little better since
160 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
161 However, the overhead of sorting can eliminate a gain of ordered search.
163 The probe set is ordered if \p compare or \p less is specified in \p Traits
164 template parameter. Otherwise, the probe set is unordered and \p Traits must contain
165 \p equal_to predicate.
169 - \p T - the type stored in the map.
170 - \p Traits - map traits, default is \p cuckoo::traits.
171 It is possible to declare option-based set with \p cuckoo::make_traits metafunction
172 result as \p Traits template argument.
176 Declares cuckoo mapping from \p std::string to struct \p foo.
177 For cuckoo hashing we should provide at least two hash functions:
180 size_t operator()(std::string const& s) const
182 return cds::opt::v::hash<std::string>( s );
186 struct hash2: private hash1 {
187 size_t operator()(std::string const& s) const
189 size_t h = ~( hash1::operator()(s));
190 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
195 Cuckoo-map with list-based unordered probe set and storing hash values
197 #include <cds/container/cuckoo_map.h>
199 // Declare type traits
200 struct my_traits: public cds::container::cuckoo::traits
202 typedef std::equal_to< std::string > equal_to;
203 typedef std::tuple< hash1, hash2 > hash;
205 static bool const store_hash = true;
208 // Declare CuckooMap type
209 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
211 // Equal option-based declaration
212 typedef cds::container::CuckooMap< std::string, foo,
213 cds::container::cuckoo::make_traits<
214 cds::opt::hash< std::tuple< hash1, hash2 > >
215 ,cds::opt::equal_to< std::equal_to< std::string > >
216 ,cds::container::cuckoo::store_hash< true >
221 If we provide \p less functor instead of \p equal_to
222 we get as a result a cuckoo map with ordered probe set that may improve
224 Example for ordered vector-based probe-set:
227 #include <cds/container/cuckoo_map.h>
229 // Declare type traits
230 // We use a vector of capacity 4 as probe-set container and store hash values in the node
231 struct my_traits: public cds::container::cuckoo::traits
233 typedef std::less< std::string > less;
234 typedef std::tuple< hash1, hash2 > hash;
235 typedef cds::container::cuckoo::vector<4> probeset_type;
237 static bool const store_hash = true;
240 // Declare CuckooMap type
241 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
243 // Equal option-based declaration
244 typedef cds::container::CuckooMap< std::string, foo,
245 cds::container::cuckoo::make_traits<
246 cds::opt::hash< std::tuple< hash1, hash2 > >
247 ,cds::opt::less< std::less< std::string > >
248 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
249 ,cds::container::cuckoo::store_hash< true >
255 template <typename Key, typename T, typename Traits = cuckoo::traits>
257 #ifdef CDS_DOXYGEN_INVOKED
258 protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
260 protected details::make_cuckoo_map<Key, T, Traits>::type
264 typedef details::make_cuckoo_map<Key, T, Traits> maker;
265 typedef typename maker::type base_class;
268 typedef Key key_type; ///< key type
269 typedef T mapped_type; ///< value type stored in the container
270 typedef std::pair<key_type const, mapped_type> value_type; ///< Key-value pair type stored in the map
271 typedef Traits traits; ///< Map traits
273 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
274 typedef typename base_class::hash_tuple_type hash_tuple_type; ///< hash tuple type
276 typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
277 typedef typename base_class::stat stat; ///< internal statistics type
279 static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
280 static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
282 typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
284 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
286 typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
288 /// Node allocator type
289 typedef typename std::conditional<
290 std::is_same< typename traits::node_allocator, opt::none >::value,
292 typename traits::node_allocator
293 >::type node_allocator;
295 /// item counter type
296 typedef typename traits::item_counter item_counter;
300 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
301 typedef typename base_class::scoped_full_lock scoped_full_lock;
302 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
303 typedef typename maker::key_accessor key_accessor;
305 typedef typename base_class::value_type node_type;
306 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
310 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
311 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
312 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
316 template <typename K>
317 static node_type * alloc_node( K const& key )
319 return cxx_node_allocator().New( key );
321 template <typename K, typename... Args>
322 static node_type * alloc_node( K&& key, Args&&... args )
324 return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
327 static void free_node( node_type * pNode )
329 cxx_node_allocator().Delete( pNode );
335 struct node_disposer {
336 void operator()( node_type * pNode )
342 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
347 /// Default constructor
349 Initial size = \ref c_nDefaultInitialSize
352 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
353 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
355 Probe set threshold = probe set size - 1
360 /// Constructs an object with given probe set size and threshold
362 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
363 then \p nProbesetSize should be equal to vector's \p Capacity.
366 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
367 , unsigned int nProbesetSize ///< probe set size
368 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
370 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
373 /// Constructs an object with given hash functor tuple
375 The probe set size and threshold are set as default, see CuckooSet()
378 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
383 /// Constructs a map with given probe set properties and hash functor tuple
385 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
386 then \p nProbesetSize should be equal to vector's \p Capacity.
389 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
390 , unsigned int nProbesetSize ///< probe set size
391 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
392 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
394 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
397 /// Constructs a map with given hash functor tuple (move semantics)
399 The probe set size and threshold are set as default, see CuckooSet()
402 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
404 : base_class( std::forward<hash_tuple_type>(h))
407 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
409 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
410 then \p nProbesetSize should be equal to vector's \p Capacity.
413 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
414 , unsigned int nProbesetSize ///< probe set size
415 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
416 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
418 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h))
421 /// Destructor clears the map
428 /// Inserts new node with key and default value
430 The function creates a node with \p key and default value, and then inserts the node created into the map.
433 - The \ref key_type should be constructible from a value of type \p K.
434 In trivial case, \p K is equal to \ref key_type.
435 - The \ref mapped_type should be default-constructible.
437 Returns \p true if inserting successful, \p false otherwise.
439 template <typename K>
440 bool insert( K const& key )
442 return insert_with( key, [](value_type&){} );
447 The function creates a node with copy of \p val value
448 and then inserts the node created into the map.
451 - The \ref key_type should be constructible from \p key of type \p K.
452 - The \ref value_type should be constructible from \p val of type \p V.
454 Returns \p true if \p val is inserted into the set, \p false otherwise.
456 template <typename K, typename V>
457 bool insert( K const& key, V const& val )
459 return insert_with( key, [&val](value_type& item) { item.second = val ; } );
462 /// Inserts new node and initialize it by a functor
464 This function inserts new node with key \p key and if inserting is successful then it calls
465 \p func functor with signature
468 void operator()( value_type& item );
472 The argument \p item of user-defined functor \p func is the reference
473 to the map's item inserted:
474 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
475 - <tt>item.second</tt> is a reference to item's value that may be changed.
477 The key_type should be constructible from value of type \p K.
479 The function allows to split creating of new item into two part:
480 - create item from \p key;
481 - insert new item into the map;
482 - if inserting is successful, initialize the value of item by calling \p func functor
484 This can be useful if complete initialization of object of \p value_type is heavyweight and
485 it is preferable that the initialization should be completed only if inserting is successful.
487 template <typename K, typename Func>
488 bool insert_with( const K& key, Func func )
490 scoped_node_ptr pNode( alloc_node( key ));
491 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
498 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
500 Returns \p true if inserting successful, \p false otherwise.
502 template <typename K, typename... Args>
503 bool emplace( K&& key, Args&&... args )
505 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
506 if ( base_class::insert( *pNode )) {
515 The operation performs inserting or changing data with lock-free manner.
517 If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.
518 Otherwise, the functor \p func is called with item found.
519 The functor \p func signature is:
522 void operator()( bool bNew, value_type& item );
526 - \p bNew - \p true if the item has been inserted, \p false otherwise
527 - \p item - an item of the map for \p key
529 Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
530 i.e. the node has been inserted or updated,
531 \p second is \p true if new item has been added or \p false if the item with \p key
534 template <typename K, typename Func>
535 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
537 scoped_node_ptr pNode( alloc_node( key ));
538 std::pair<bool, bool> res = base_class::update( *pNode,
539 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); },
542 if ( res.first && res.second )
547 template <typename K, typename Func>
548 CDS_DEPRECATED("ensure() is deprecated, use update()")
549 std::pair<bool, bool> ensure( K const& key, Func func )
551 return update( key, func, true );
555 /// Delete \p key from the map
556 /** \anchor cds_nonintrusive_CuckooMap_erase_val
558 Return \p true if \p key is found and deleted, \p false otherwise
560 template <typename K>
561 bool erase( K const& key )
563 node_type * pNode = base_class::erase(key);
571 /// Deletes the item from the list using \p pred predicate for searching
573 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
574 but \p pred is used for key comparing.
575 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
576 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
577 \p Predicate must imply the same element order as the comparator used for building the map.
579 template <typename K, typename Predicate>
580 bool erase_with( K const& key, Predicate pred )
583 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
591 /// Delete \p key from the map
592 /** \anchor cds_nonintrusive_CuckooMap_erase_func
594 The function searches an item with key \p key, calls \p f functor
595 and deletes the item. If \p key is not found, the functor is not called.
597 The functor \p Func interface:
600 void operator()(value_type& item) { ... }
604 Return \p true if key is found and deleted, \p false otherwise
608 template <typename K, typename Func>
609 bool erase( K const& key, Func f )
611 node_type * pNode = base_class::erase( key );
620 /// Deletes the item from the list using \p pred predicate for searching
622 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
623 but \p pred is used for key comparing.
624 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
625 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
626 \p Predicate must imply the same element order as the comparator used for building the map.
628 template <typename K, typename Predicate, typename Func>
629 bool erase_with( K const& key, Predicate pred, Func f )
632 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
641 /// Find the key \p key
642 /** \anchor cds_nonintrusive_CuckooMap_find_func
644 The function searches the item with key equal to \p key and calls the functor \p f for item found.
645 The interface of \p Func functor is:
648 void operator()( value_type& item );
651 where \p item is the item found.
653 The functor may change \p item.second.
655 The function returns \p true if \p key is found, \p false otherwise.
657 template <typename K, typename Func>
658 bool find( K const& key, Func f )
660 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
663 /// Find the key \p val using \p pred predicate for comparing
665 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
666 but \p pred is used for key comparison.
667 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
668 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
669 \p pred must imply the same element order as the comparator used for building the map.
671 template <typename K, typename Predicate, typename Func>
672 bool find_with( K const& key, Predicate pred, Func f )
675 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
676 [&f](node_type& item, K const& ) { f( item.m_val );});
679 /// Checks whether the map contains \p key
681 The function searches the item with key equal to \p key
682 and returns \p true if it is found, and \p false otherwise.
684 template <typename K>
685 bool contains( K const& key )
687 return base_class::contains( key );
690 template <typename K>
691 CDS_DEPRECATED("the function is deprecated, use contains()")
692 bool find( K const& key )
694 return contains( key );
698 /// Checks whether the map contains \p key using \p pred predicate for searching
700 The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
701 \p Less functor has the interface like \p std::less.
702 \p Less must imply the same element order as the comparator used for building the map.
704 template <typename K, typename Predicate>
705 bool contains( K const& key, Predicate pred )
708 return base_class::contains( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
711 template <typename K, typename Predicate>
712 CDS_DEPRECATED("the function is deprecated, use contains()")
713 bool find_with( K const& key, Predicate pred )
715 return contains( key, pred );
722 base_class::clear_and_dispose( node_disposer());
725 /// Checks if the map is empty
727 Emptiness is checked by item counting: if item count is zero then the map is empty.
731 return base_class::empty();
734 /// Returns item count in the map
737 return base_class::size();
740 /// Returns the size of hash table
742 The hash table size is non-constant and can be increased via resizing.
744 size_t bucket_count() const
746 return base_class::bucket_count();
749 /// Returns lock array size
751 The lock array size is constant.
753 size_t lock_count() const
755 return base_class::lock_count();
758 /// Returns const reference to internal statistics
759 stat const& statistics() const
761 return base_class::statistics();
764 /// Returns const reference to mutex policy internal statistics
765 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
767 return base_class::mutex_policy_statistics();
770 }} // namespace cds::container
772 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H