3 #ifndef __CDS_CONTAINER_CUCKOO_MAP_H
4 #define __CDS_CONTAINER_CUCKOO_MAP_H
6 #include <cds/container/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;
377 #ifndef CDS_CXX11_LAMBDA_SUPPORT
378 struct empty_insert_functor
380 void operator()( value_type& ) const
384 template <typename Q>
385 class insert_value_functor
389 insert_value_functor( Q const & v)
393 void operator()( value_type& item )
399 template <typename Func>
400 class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
402 typedef cds::details::functor_wrapper<Func> base_class;
404 insert_key_wrapper( Func f ): base_class(f) {}
406 void operator()( node_type& item )
408 base_class::get()( item.m_val );
412 template <typename Func>
413 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
415 typedef cds::details::functor_wrapper<Func> base_class;
417 ensure_wrapper( Func f) : base_class(f) {}
419 void operator()( bool bNew, node_type& item, node_type const& )
421 base_class::get()( bNew, item.m_val );
425 template <typename Func>
426 class find_wrapper: protected cds::details::functor_wrapper<Func>
428 typedef cds::details::functor_wrapper<Func> base_class;
430 find_wrapper( Func f )
434 template <typename Q>
435 void operator()( node_type& item, Q& val )
437 base_class::get()( item.m_val, val );
440 #endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT
445 /// Default constructor
447 Initial size = \ref c_nDefaultInitialSize
450 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
451 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
453 Probe set threshold = probe set size - 1
458 /// Constructs an object with given probe set size and threshold
460 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
461 then \p nProbesetSize should be equal to vector's \p Capacity.
464 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
465 , unsigned int nProbesetSize ///< probe set size
466 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
468 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
471 /// Constructs an object with given hash functor tuple
473 The probe set size and threshold are set as default, see CuckooSet()
476 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
481 /// Constructs a map with given probe set properties and hash functor tuple
483 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
484 then \p nProbesetSize should be equal to vector's \p Capacity.
487 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
488 , unsigned int nProbesetSize ///< probe set size
489 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
490 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
492 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
495 /// Constructs a map with given hash functor tuple (move semantics)
497 The probe set size and threshold are set as default, see CuckooSet()
500 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
502 : base_class( std::forward<hash_tuple_type>(h) )
505 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
507 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
508 then \p nProbesetSize should be equal to vector's \p Capacity.
511 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
512 , unsigned int nProbesetSize ///< probe set size
513 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
514 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
516 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
519 /// Destructor clears the map
526 /// Inserts new node with key and default value
528 The function creates a node with \p key and default value, and then inserts the node created into the map.
531 - The \ref key_type should be constructible from a value of type \p K.
532 In trivial case, \p K is equal to \ref key_type.
533 - The \ref mapped_type should be default-constructible.
535 Returns \p true if inserting successful, \p false otherwise.
537 template <typename K>
538 bool insert( K const& key )
540 # ifdef CDS_CXX11_LAMBDA_SUPPORT
541 return insert_key( key, [](value_type&){} );
543 return insert_key( key, empty_insert_functor() );
549 The function creates a node with copy of \p val value
550 and then inserts the node created into the map.
553 - The \ref key_type should be constructible from \p key of type \p K.
554 - The \ref value_type should be constructible from \p val of type \p V.
556 Returns \p true if \p val is inserted into the set, \p false otherwise.
558 template <typename K, typename V>
559 bool insert( K const& key, V const& val )
561 # ifdef CDS_CXX11_LAMBDA_SUPPORT
562 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
564 insert_value_functor<V> f(val);
565 return insert_key( key, cds::ref(f) );
569 /// Inserts new node and initialize it by a functor
571 This function inserts new node with key \p key and if inserting is successful then it calls
572 \p func functor with signature
575 void operator()( value_type& item );
579 The argument \p item of user-defined functor \p func is the reference
580 to the map's item inserted:
581 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
582 - <tt>item.second</tt> is a reference to item's value that may be changed.
584 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
585 and it is called only if inserting is successful.
587 The key_type should be constructible from value of type \p K.
589 The function allows to split creating of new item into two part:
590 - create item from \p key;
591 - insert new item into the map;
592 - if inserting is successful, initialize the value of item by calling \p func functor
594 This can be useful if complete initialization of object of \p value_type is heavyweight and
595 it is preferable that the initialization should be completed only if inserting is successful.
597 template <typename K, typename Func>
598 bool insert_key( const K& key, Func func )
600 scoped_node_ptr pNode( alloc_node( key ));
601 # ifdef CDS_CXX11_LAMBDA_SUPPORT
602 if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_val ); } ))
604 insert_key_wrapper<Func> wrapper(func);
605 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
614 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
616 Returns \p true if inserting successful, \p false otherwise.
618 template <typename K, typename... Args>
619 bool emplace( K&& key, Args&&... args )
621 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
622 if ( base_class::insert( *pNode )) {
629 /// Ensures that the \p key exists in the map
631 The operation performs inserting or changing data with lock-free manner.
633 If the \p key not found in the map, then the new item created from \p key
634 is inserted into the map (note that in this case the \ref key_type should be
635 constructible from type \p K).
636 Otherwise, the functor \p func is called with item found.
637 The functor \p Func may be a function with signature:
639 void func( bool bNew, value_type& item );
644 void operator()( bool bNew, value_type& item );
649 - \p bNew - \p true if the item has been inserted, \p false otherwise
650 - \p item - item of the list
652 The functor may change any fields of the \p item.second that is \ref value_type.
654 You may pass \p func argument by reference using <tt>boost::ref</tt>.
656 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
657 \p second is true if new item has been added or \p false if the item with \p key
658 already is in the list.
660 template <typename K, typename Func>
661 std::pair<bool, bool> ensure( K const& key, Func func )
663 scoped_node_ptr pNode( alloc_node( key ));
664 # ifdef CDS_CXX11_LAMBDA_SUPPORT
665 std::pair<bool, bool> res = base_class::ensure( *pNode,
666 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val ); }
669 ensure_wrapper<Func> wrapper( func );
670 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
672 if ( res.first && res.second )
677 /// Delete \p key from the map
678 /** \anchor cds_nonintrusive_CuckooMap_erase_val
680 Return \p true if \p key is found and deleted, \p false otherwise
682 template <typename K>
683 bool erase( K const& key )
685 node_type * pNode = base_class::erase(key);
693 /// Deletes the item from the list using \p pred predicate for searching
695 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
696 but \p pred is used for key comparing.
697 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
698 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
699 \p Predicate must imply the same element order as the comparator used for building the map.
701 template <typename K, typename Predicate>
702 bool erase_with( K const& key, Predicate pred )
704 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
712 /// Delete \p key from the map
713 /** \anchor cds_nonintrusive_CuckooMap_erase_func
715 The function searches an item with key \p key, calls \p f functor
716 and deletes the item. If \p key is not found, the functor is not called.
718 The functor \p Func interface:
721 void operator()(value_type& item) { ... }
724 The functor may be passed by reference using <tt>boost:ref</tt>
726 Return \p true if key is found and deleted, \p false otherwise
730 template <typename K, typename Func>
731 bool erase( K const& key, Func f )
733 node_type * pNode = base_class::erase( key );
735 cds::unref(f)( pNode->m_val );
742 /// Deletes the item from the list using \p pred predicate for searching
744 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
745 but \p pred is used for key comparing.
746 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
747 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
748 \p Predicate must imply the same element order as the comparator used for building the map.
750 template <typename K, typename Predicate, typename Func>
751 bool erase_with( K const& key, Predicate pred, Func f )
753 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
755 cds::unref(f)( pNode->m_val );
762 /// Find the key \p key
763 /** \anchor cds_nonintrusive_CuckooMap_find_func
765 The function searches the item with key equal to \p key and calls the functor \p f for item found.
766 The interface of \p Func functor is:
769 void operator()( value_type& item );
772 where \p item is the item found.
774 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
776 The functor may change \p item.second.
778 The function returns \p true if \p key is found, \p false otherwise.
780 template <typename K, typename Func>
781 bool find( K const& key, Func f )
783 # ifdef CDS_CXX11_LAMBDA_SUPPORT
784 return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
786 find_wrapper<Func> wrapper(f);
787 return base_class::find( key, cds::ref(wrapper) );
791 /// Find the key \p val using \p pred predicate for comparing
793 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
794 but \p pred is used for key comparison.
795 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
796 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
797 \p pred must imply the same element order as the comparator used for building the map.
799 template <typename K, typename Predicate, typename Func>
800 bool find_with( K const& key, Predicate pred, Func f )
802 # ifdef CDS_CXX11_LAMBDA_SUPPORT
803 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
804 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
806 find_wrapper<Func> wrapper(f);
807 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(), cds::ref(wrapper) );
811 /// Find the key \p key
812 /** \anchor cds_nonintrusive_CuckooMap_find_val
814 The function searches the item with key equal to \p key
815 and returns \p true if it is found, and \p false otherwise.
817 template <typename K>
818 bool find( K const& key )
820 return base_class::find( key );
823 /// Find the key \p val using \p pred predicate for comparing
825 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
826 but \p pred is used for key comparison.
827 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
828 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
829 \p pred must imply the same element order as the comparator used for building the map.
831 template <typename K, typename Predicate>
832 bool find_with( K const& key, Predicate pred )
834 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
840 base_class::clear_and_dispose( node_disposer() );
843 /// Checks if the map is empty
845 Emptiness is checked by item counting: if item count is zero then the map is empty.
849 return base_class::empty();
852 /// Returns item count in the map
855 return base_class::size();
858 /// Returns the size of hash table
860 The hash table size is non-constant and can be increased via resizing.
862 size_t bucket_count() const
864 return base_class::bucket_count();
867 /// Returns lock array size
869 The lock array size is constant.
871 size_t lock_count() const
873 return base_class::lock_count();
876 /// Returns const reference to internal statistics
877 stat const& statistics() const
879 return base_class::statistics();
882 /// Returns const reference to mutex policy internal statistics
883 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
885 return base_class::mutex_policy_statistics();
889 }} // namespace cds::container
891 #endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H