3 #ifndef __CDS_CONTAINER_CUCKOO_MAP_H
4 #define __CDS_CONTAINER_CUCKOO_MAP_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 Key, typename T, typename Traits>
14 struct make_cuckoo_map
16 typedef Key key_type ; ///< key type
17 typedef T mapped_type ; ///< type of value stored in the map
18 typedef std::pair<key_type const, mapped_type> value_type ; ///< Pair type
20 typedef Traits original_type_traits;
21 typedef typename original_type_traits::probeset_type probeset_type;
22 static bool const store_hash = original_type_traits::store_hash;
23 static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_type_traits::hash::hash_tuple_type >::value) : 0;
25 struct node_type: public intrusive::cuckoo::node<probeset_type, store_hash_count>
30 node_type( K const& key )
31 : m_val( std::make_pair( key_type(key), mapped_type() ))
34 template <typename K, typename Q>
35 node_type( K const& key, Q const& v )
36 : m_val( std::make_pair( key_type(key), mapped_type(v) ))
39 template <typename K, typename... Args>
40 node_type( K&& key, Args&&... args )
41 : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
46 template <typename Pred, typename ReturnValue>
47 struct predicate_wrapper {
48 typedef Pred native_predicate;
50 ReturnValue operator()( node_type const& n1, node_type const& n2) const
52 return native_predicate()(n1.m_val.first, n2.m_val.first );
55 ReturnValue operator()( node_type const& n, Q const& v) const
57 return native_predicate()(n.m_val.first, v);
60 ReturnValue operator()( Q const& v, node_type const& n) const
62 return native_predicate()(v, n.m_val.first);
65 template <typename Q1, typename Q2>
66 ReturnValue operator()( Q1 const& v1, Q2 const& v2) const
68 return native_predicate()(v1, v2);
74 key_type const& operator()( node_type const& node ) const
76 return node.m_val.first;
80 struct intrusive_traits: public original_type_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::type_traits::disposer disposer;
89 typedef typename std::conditional<
90 std::is_same< typename original_type_traits::equal_to, opt::none >::value
92 , cds::details::predicate_wrapper< node_type, typename original_type_traits::equal_to, key_accessor >
95 typedef typename std::conditional<
96 std::is_same< typename original_type_traits::compare, opt::none >::value
98 , cds::details::compare_wrapper< node_type, typename original_type_traits::compare, key_accessor >
101 typedef typename std::conditional<
102 std::is_same< typename original_type_traits::less, opt::none >::value
104 ,cds::details::predicate_wrapper< node_type, typename original_type_traits::less, key_accessor >
107 typedef opt::details::hash_list_wrapper< typename original_type_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 Cuckoo hashing 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 opt::compare or opt::less is specified in \p %CuckooSet
164 declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
165 opt::equal_to option.
169 - \p T - the type stored in the map.
170 - \p Traits - type traits. See cuckoo::type_traits for explanation.
171 It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
173 Template argument list \p Options... of cuckoo::make_traits metafunction are:
174 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
175 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
176 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
177 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
178 then k is unlimited, otherwise up to 10 different hash functors are supported.
179 - opt::mutex_policy - concurrent access policy.
180 Available policies: cuckoo::striping, cuckoo::refinable.
181 Default is cuckoo::striping.
182 - opt::equal_to - key equality functor like \p std::equal_to.
183 If this functor is defined then the probe-set will be unordered.
184 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
185 and opt::equal_to will be ignored.
186 - opt::compare - key comparison functor. No default functor is provided.
187 If the option is not specified, the opt::less is used.
188 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
189 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
190 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
191 - opt::item_counter - the type of item counting feature. Default is \ref opt::v::sequential_item_counter.
192 - opt::allocator - the allocator type using for allocating bucket tables.
193 Default is \p CDS_DEFAULT_ALLOCATOR
194 - opt::node_allocator - the allocator type using for allocating map's items. If this option
195 is not specified then the type defined in opt::allocator option is used.
196 - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
197 of the object once it's introduced in the container. When this option is used,
198 the map will store the calculated hash value in the node and rehashing operations won't need
199 to recalculate the hash of the value. This option will improve the performance of maps
200 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
201 - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
202 Default is \p cuckoo::list.
203 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
204 Default is cuckoo::empty_stat
208 Declares cuckoo mapping from \p std::string to struct \p foo.
209 For cuckoo hashing we should provide at least two hash functions:
212 size_t operator()(std::string const& s) const
214 return cds::opt::v::hash<std::string>( s );
218 struct hash2: private hash1 {
219 size_t operator()(std::string const& s) const
221 size_t h = ~( hash1::operator()(s));
222 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
227 Cuckoo-map with list-based unordered probe set and storing hash values
229 #include <cds/container/cuckoo_map.h>
231 // Declare type traits
232 struct my_traits: public cds::container::cuckoo::type_traits
234 typedef std::equal_to< std::string > equal_to;
235 typedef std::tuple< hash1, hash2 > hash;
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::equal_to< std::equal_to< std::string > >
248 ,cds::container::cuckoo::store_hash< true >
253 If we provide \p less functor instead of \p equal_to
254 we get as a result a cuckoo map with ordered probe set that may improve
256 Example for ordered vector-based probe-set:
259 #include <cds/container/cuckoo_map.h>
261 // Declare type traits
262 // We use a vector of capacity 4 as probe-set container and store hash values in the node
263 struct my_traits: public cds::container::cuckoo::type_traits
265 typedef std::less< std::string > less;
266 typedef std::tuple< hash1, hash2 > hash;
267 typedef cds::container::cuckoo::vector<4> probeset_type;
269 static bool const store_hash = true;
272 // Declare CuckooMap type
273 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
275 // Equal option-based declaration
276 typedef cds::container::CuckooMap< std::string, foo,
277 cds::container::cuckoo::make_traits<
278 cds::opt::hash< std::tuple< hash1, hash2 > >
279 ,cds::opt::less< std::less< std::string > >
280 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
281 ,cds::container::cuckoo::store_hash< true >
287 template <typename Key, typename T, typename Traits = cuckoo::type_traits>
289 #ifdef CDS_DOXYGEN_INVOKED
290 protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
292 protected details::make_cuckoo_map<Key, T, Traits>::type
296 typedef details::make_cuckoo_map<Key, T, Traits> maker;
297 typedef typename maker::type base_class;
300 typedef Key key_type ; ///< key type
301 typedef T mapped_type ; ///< value type stored in the container
302 typedef std::pair<key_type const, mapped_type> value_type ; ///< Key-value pair type stored in the map
304 typedef Traits options ; ///< traits
306 typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
307 typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< hash tuple type
309 typedef typename base_class::mutex_policy mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
310 typedef typename base_class::stat stat ; ///< internal statistics type
312 static bool const c_isSorted = base_class::c_isSorted ; ///< whether the probe set should be ordered
313 static size_t const c_nArity = base_class::c_nArity ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
315 typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
317 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
319 typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
321 /// Node allocator type
322 typedef typename std::conditional<
323 std::is_same< typename options::node_allocator, opt::none >::value,
325 typename options::node_allocator
326 >::type node_allocator;
328 /// item counter type
329 typedef typename options::item_counter item_counter;
333 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
334 typedef typename base_class::scoped_full_lock scoped_full_lock;
335 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
336 typedef typename maker::key_accessor key_accessor;
338 typedef typename base_class::value_type node_type;
339 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
343 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ; ///< default probeset size
344 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize ; ///< default initial size
345 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit ; ///< Count of attempts to relocate before giving up
349 template <typename K>
350 static node_type * alloc_node( K const& key )
352 return cxx_node_allocator().New( key );
354 template <typename K, typename... Args>
355 static node_type * alloc_node( K&& key, Args&&... args )
357 return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
360 static void free_node( node_type * pNode )
362 cxx_node_allocator().Delete( pNode );
368 struct node_disposer {
369 void operator()( node_type * pNode )
375 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
380 /// Default constructor
382 Initial size = \ref c_nDefaultInitialSize
385 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
386 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
388 Probe set threshold = probe set size - 1
393 /// Constructs an object with given probe set size and threshold
395 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
396 then \p nProbesetSize should be equal to vector's \p Capacity.
399 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
400 , unsigned int nProbesetSize ///< probe set size
401 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
403 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
406 /// Constructs an object with given hash functor tuple
408 The probe set size and threshold are set as default, see CuckooSet()
411 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
416 /// Constructs a map with given probe set properties and hash functor tuple
418 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
419 then \p nProbesetSize should be equal to vector's \p Capacity.
422 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
423 , unsigned int nProbesetSize ///< probe set size
424 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
425 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
427 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
430 /// Constructs a map with given hash functor tuple (move semantics)
432 The probe set size and threshold are set as default, see CuckooSet()
435 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
437 : base_class( std::forward<hash_tuple_type>(h) )
440 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
442 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
443 then \p nProbesetSize should be equal to vector's \p Capacity.
446 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
447 , unsigned int nProbesetSize ///< probe set size
448 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
449 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
451 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
454 /// Destructor clears the map
461 /// Inserts new node with key and default value
463 The function creates a node with \p key and default value, and then inserts the node created into the map.
466 - The \ref key_type should be constructible from a value of type \p K.
467 In trivial case, \p K is equal to \ref key_type.
468 - The \ref mapped_type should be default-constructible.
470 Returns \p true if inserting successful, \p false otherwise.
472 template <typename K>
473 bool insert( K const& key )
475 return insert_key( key, [](value_type&){} );
480 The function creates a node with copy of \p val value
481 and then inserts the node created into the map.
484 - The \ref key_type should be constructible from \p key of type \p K.
485 - The \ref value_type should be constructible from \p val of type \p V.
487 Returns \p true if \p val is inserted into the set, \p false otherwise.
489 template <typename K, typename V>
490 bool insert( K const& key, V const& val )
492 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
495 /// Inserts new node and initialize it by a functor
497 This function inserts new node with key \p key and if inserting is successful then it calls
498 \p func functor with signature
501 void operator()( value_type& item );
505 The argument \p item of user-defined functor \p func is the reference
506 to the map's item inserted:
507 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
508 - <tt>item.second</tt> is a reference to item's value that may be changed.
510 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
511 and it is called only if inserting is successful.
513 The key_type should be constructible from value of type \p K.
515 The function allows to split creating of new item into two part:
516 - create item from \p key;
517 - insert new item into the map;
518 - if inserting is successful, initialize the value of item by calling \p func functor
520 This can be useful if complete initialization of object of \p value_type is heavyweight and
521 it is preferable that the initialization should be completed only if inserting is successful.
523 template <typename K, typename Func>
524 bool insert_key( const K& key, Func func )
526 scoped_node_ptr pNode( alloc_node( key ));
527 if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_val ); } )) {
534 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
536 Returns \p true if inserting successful, \p false otherwise.
538 template <typename K, typename... Args>
539 bool emplace( K&& key, Args&&... args )
541 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
542 if ( base_class::insert( *pNode )) {
549 /// Ensures that the \p key exists in the map
551 The operation performs inserting or changing data with lock-free manner.
553 If the \p key not found in the map, then the new item created from \p key
554 is inserted into the map (note that in this case the \ref key_type should be
555 constructible from type \p K).
556 Otherwise, the functor \p func is called with item found.
557 The functor \p Func may be a function with signature:
559 void func( bool bNew, value_type& item );
564 void operator()( bool bNew, value_type& item );
569 - \p bNew - \p true if the item has been inserted, \p false otherwise
570 - \p item - item of the list
572 The functor may change any fields of the \p item.second that is \ref value_type.
574 You may pass \p func argument by reference using <tt>boost::ref</tt>.
576 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
577 \p second is true if new item has been added or \p false if the item with \p key
578 already is in the list.
580 template <typename K, typename Func>
581 std::pair<bool, bool> ensure( K const& key, Func func )
583 scoped_node_ptr pNode( alloc_node( key ));
584 std::pair<bool, bool> res = base_class::ensure( *pNode,
585 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val ); }
587 if ( res.first && res.second )
592 /// Delete \p key from the map
593 /** \anchor cds_nonintrusive_CuckooMap_erase_val
595 Return \p true if \p key is found and deleted, \p false otherwise
597 template <typename K>
598 bool erase( K const& key )
600 node_type * pNode = base_class::erase(key);
608 /// Deletes the item from the list using \p pred predicate for searching
610 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
611 but \p pred is used for key comparing.
612 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
613 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
614 \p Predicate must imply the same element order as the comparator used for building the map.
616 template <typename K, typename Predicate>
617 bool erase_with( K const& key, Predicate pred )
619 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
627 /// Delete \p key from the map
628 /** \anchor cds_nonintrusive_CuckooMap_erase_func
630 The function searches an item with key \p key, calls \p f functor
631 and deletes the item. If \p key is not found, the functor is not called.
633 The functor \p Func interface:
636 void operator()(value_type& item) { ... }
639 The functor may be passed by reference using <tt>boost:ref</tt>
641 Return \p true if key is found and deleted, \p false otherwise
645 template <typename K, typename Func>
646 bool erase( K const& key, Func f )
648 node_type * pNode = base_class::erase( key );
650 cds::unref(f)( pNode->m_val );
657 /// Deletes the item from the list using \p pred predicate for searching
659 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
660 but \p pred is used for key comparing.
661 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
662 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
663 \p Predicate must imply the same element order as the comparator used for building the map.
665 template <typename K, typename Predicate, typename Func>
666 bool erase_with( K const& key, Predicate pred, Func f )
668 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
670 cds::unref(f)( pNode->m_val );
677 /// Find the key \p key
678 /** \anchor cds_nonintrusive_CuckooMap_find_func
680 The function searches the item with key equal to \p key and calls the functor \p f for item found.
681 The interface of \p Func functor is:
684 void operator()( value_type& item );
687 where \p item is the item found.
689 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
691 The functor may change \p item.second.
693 The function returns \p true if \p key is found, \p false otherwise.
695 template <typename K, typename Func>
696 bool find( K const& key, Func f )
698 return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
701 /// Find the key \p val using \p pred predicate for comparing
703 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
704 but \p pred is used for key comparison.
705 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
706 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
707 \p pred must imply the same element order as the comparator used for building the map.
709 template <typename K, typename Predicate, typename Func>
710 bool find_with( K const& key, Predicate pred, Func f )
712 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
713 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
716 /// Find the key \p key
717 /** \anchor cds_nonintrusive_CuckooMap_find_val
719 The function searches the item with key equal to \p key
720 and returns \p true if it is found, and \p false otherwise.
722 template <typename K>
723 bool find( K const& key )
725 return base_class::find( key );
728 /// Find the key \p val using \p pred predicate for comparing
730 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
731 but \p pred is used for key comparison.
732 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
733 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
734 \p pred must imply the same element order as the comparator used for building the map.
736 template <typename K, typename Predicate>
737 bool find_with( K const& key, Predicate pred )
739 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
745 base_class::clear_and_dispose( node_disposer() );
748 /// Checks if the map is empty
750 Emptiness is checked by item counting: if item count is zero then the map is empty.
754 return base_class::empty();
757 /// Returns item count in the map
760 return base_class::size();
763 /// Returns the size of hash table
765 The hash table size is non-constant and can be increased via resizing.
767 size_t bucket_count() const
769 return base_class::bucket_count();
772 /// Returns lock array size
774 The lock array size is constant.
776 size_t lock_count() const
778 return base_class::lock_count();
781 /// Returns const reference to internal statistics
782 stat const& statistics() const
784 return base_class::statistics();
787 /// Returns const reference to mutex policy internal statistics
788 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
790 return base_class::mutex_policy_statistics();
794 }} // namespace cds::container
796 #endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H