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 # ifdef CDS_EMPLACE_SUPPORT
40 template <typename K, typename... Args>
41 node_type( K&& key, Args&&... args )
42 : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
51 template <typename Pred, typename ReturnValue>
52 struct predicate_wrapper {
53 typedef Pred native_predicate;
55 ReturnValue operator()( node_type const& n1, node_type const& n2) const
57 return native_predicate()(n1.m_val.first, n2.m_val.first );
60 ReturnValue operator()( node_type const& n, Q const& v) const
62 return native_predicate()(n.m_val.first, v);
65 ReturnValue operator()( Q const& v, node_type const& n) const
67 return native_predicate()(v, n.m_val.first);
70 template <typename Q1, typename Q2>
71 ReturnValue operator()( Q1 const& v1, Q2 const& v2) const
73 return native_predicate()(v1, v2);
79 key_type const& operator()( node_type const& node ) const
81 return node.m_val.first;
85 struct intrusive_traits: public original_type_traits
87 typedef intrusive::cuckoo::base_hook<
88 cds::intrusive::cuckoo::probeset_type< probeset_type >
89 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
92 typedef cds::intrusive::cuckoo::type_traits::disposer disposer;
94 typedef typename std::conditional<
95 std::is_same< typename original_type_traits::equal_to, opt::none >::value
97 , cds::details::predicate_wrapper< node_type, typename original_type_traits::equal_to, key_accessor >
100 typedef typename std::conditional<
101 std::is_same< typename original_type_traits::compare, opt::none >::value
103 , cds::details::compare_wrapper< node_type, typename original_type_traits::compare, key_accessor >
106 typedef typename std::conditional<
107 std::is_same< typename original_type_traits::less, opt::none >::value
109 ,cds::details::predicate_wrapper< node_type, typename original_type_traits::less, key_accessor >
112 typedef opt::details::hash_list_wrapper< typename original_type_traits::hash, node_type, key_accessor > hash;
115 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
117 } // namespace details
121 /** @ingroup cds_nonintrusive_map
124 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
125 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
127 <b>About Cuckoo hashing</b>
129 [From "The Art of Multiprocessor Programming"]
130 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
131 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
132 N = 2k we use a two-entry array of tables, and two independent hash functions,
133 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
134 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
135 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
136 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
137 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
139 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
140 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
141 If the prior value was \p NULL, it is done. Otherwise, it swaps the newly nest-less value \p y
142 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
143 was \p NULL, it is done. Otherwise, the method continues swapping entries (alternating tables)
144 until it finds an empty slot. We might not find an empty slot, either because the table is full,
145 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
146 number of successive displacements we are willing to undertake. When this limit is exceeded,
147 we resize the hash table, choose new hash functions and start over.
149 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
150 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
151 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
152 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
153 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
154 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
156 In current implementation, a probe set can be defined either as a (single-linked) list
157 or as a fixed-sized vector, optionally ordered.
159 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
160 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
161 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
163 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
164 The probe set may be ordered or not. Ordered probe set can be a little better since
165 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
166 However, the overhead of sorting can eliminate a gain of ordered search.
168 The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
169 declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
170 opt::equal_to option.
174 - \p T - the type stored in the map.
175 - \p Traits - type traits. See cuckoo::type_traits for explanation.
176 It is possible to declare option-based set with cuckoo::make_traits metafunction result as \p Traits template argument.
178 Template argument list \p Options... of cuckoo::make_traits metafunction are:
179 - opt::hash - hash functor tuple, mandatory option. At least, two hash functors should be provided. All hash functor
180 should be orthogonal (different): for each <tt> i,j: i != j => h[i](x) != h[j](x) </tt>.
181 The hash functors are passed as <tt> std::tuple< H1, H2, ... Hn > </tt>. The number of hash functors specifies
182 the number \p k - the count of hash tables in cuckoo hashing. If the compiler supports variadic templates
183 then k is unlimited, otherwise up to 10 different hash functors are supported.
184 - opt::mutex_policy - concurrent access policy.
185 Available policies: cuckoo::striping, cuckoo::refinable.
186 Default is cuckoo::striping.
187 - opt::equal_to - key equality functor like \p std::equal_to.
188 If this functor is defined then the probe-set will be unordered.
189 If opt::compare or opt::less option is specified too, then the probe-set will be ordered
190 and opt::equal_to will be ignored.
191 - opt::compare - key comparison functor. No default functor is provided.
192 If the option is not specified, the opt::less is used.
193 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
194 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
195 If opt::compare or opt::less option is specified, then the probe-set will be ordered.
196 - opt::item_counter - the type of item counting feature. Default is \ref opt::v::sequential_item_counter.
197 - opt::allocator - the allocator type using for allocating bucket tables.
198 Default is \p CDS_DEFAULT_ALLOCATOR
199 - opt::node_allocator - the allocator type using for allocating map's items. If this option
200 is not specified then the type defined in opt::allocator option is used.
201 - cuckoo::store_hash - this option reserves additional space in the node to store the hash value
202 of the object once it's introduced in the container. When this option is used,
203 the map will store the calculated hash value in the node and rehashing operations won't need
204 to recalculate the hash of the value. This option will improve the performance of maps
205 when rehashing is frequent or hashing the value is a slow operation. Default value is \p false.
206 - \ref intrusive::cuckoo::probeset_type "cuckoo::probeset_type" - type of probe set, may be \p cuckoo::list or <tt>cuckoo::vector<Capacity></tt>,
207 Default is \p cuckoo::list.
208 - opt::stat - internal statistics. Possibly types: cuckoo::stat, cuckoo::empty_stat.
209 Default is cuckoo::empty_stat
213 Declares cuckoo mapping from \p std::string to struct \p foo.
214 For cuckoo hashing we should provide at least two hash functions:
217 size_t operator()(std::string const& s) const
219 return cds::opt::v::hash<std::string>( s );
223 struct hash2: private hash1 {
224 size_t operator()(std::string const& s) const
226 size_t h = ~( hash1::operator()(s));
227 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
232 Cuckoo-map with list-based unordered probe set and storing hash values
234 #include <cds/container/cuckoo_map.h>
236 // Declare type traits
237 struct my_traits: public cds::container::cuckoo::type_traits
239 typedef std::equal_to< std::string > equal_to;
240 typedef std::tuple< hash1, hash2 > hash;
242 static bool const store_hash = true;
245 // Declare CuckooMap type
246 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
248 // Equal option-based declaration
249 typedef cds::container::CuckooMap< std::string, foo,
250 cds::container::cuckoo::make_traits<
251 cds::opt::hash< std::tuple< hash1, hash2 > >
252 ,cds::opt::equal_to< std::equal_to< std::string > >
253 ,cds::container::cuckoo::store_hash< true >
258 If we provide \p less functor instead of \p equal_to
259 we get as a result a cuckoo map with ordered probe set that may improve
261 Example for ordered vector-based probe-set:
264 #include <cds/container/cuckoo_map.h>
266 // Declare type traits
267 // We use a vector of capacity 4 as probe-set container and store hash values in the node
268 struct my_traits: public cds::container::cuckoo::type_traits
270 typedef std::less< std::string > less;
271 typedef std::tuple< hash1, hash2 > hash;
272 typedef cds::container::cuckoo::vector<4> probeset_type;
274 static bool const store_hash = true;
277 // Declare CuckooMap type
278 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
280 // Equal option-based declaration
281 typedef cds::container::CuckooMap< std::string, foo,
282 cds::container::cuckoo::make_traits<
283 cds::opt::hash< std::tuple< hash1, hash2 > >
284 ,cds::opt::less< std::less< std::string > >
285 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
286 ,cds::container::cuckoo::store_hash< true >
292 template <typename Key, typename T, typename Traits = cuckoo::type_traits>
294 #ifdef CDS_DOXYGEN_INVOKED
295 protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
297 protected details::make_cuckoo_map<Key, T, Traits>::type
301 typedef details::make_cuckoo_map<Key, T, Traits> maker;
302 typedef typename maker::type base_class;
305 typedef Key key_type ; ///< key type
306 typedef T mapped_type ; ///< value type stored in the container
307 typedef std::pair<key_type const, mapped_type> value_type ; ///< Key-value pair type stored in the map
309 typedef Traits options ; ///< traits
311 typedef typename options::hash hash ; ///< hash functor tuple wrapped for internal use
312 typedef typename base_class::hash_tuple_type hash_tuple_type ; ///< hash tuple type
314 typedef typename base_class::mutex_policy mutex_policy ; ///< Concurrent access policy, see cuckoo::type_traits::mutex_policy
315 typedef typename base_class::stat stat ; ///< internal statistics type
317 static bool const c_isSorted = base_class::c_isSorted ; ///< whether the probe set should be ordered
318 static size_t const c_nArity = base_class::c_nArity ; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
320 typedef typename base_class::key_equal_to key_equal_to ; ///< Key equality functor; used only for unordered probe-set
322 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
324 typedef typename base_class::allocator allocator ; ///< allocator type used for internal bucket table allocations
326 /// Node allocator type
327 typedef typename std::conditional<
328 std::is_same< typename options::node_allocator, opt::none >::value,
330 typename options::node_allocator
331 >::type node_allocator;
333 /// item counter type
334 typedef typename options::item_counter item_counter;
338 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
339 typedef typename base_class::scoped_full_lock scoped_full_lock;
340 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
341 typedef typename maker::key_accessor key_accessor;
343 typedef typename base_class::value_type node_type;
344 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
348 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize ; ///< default probeset size
349 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize ; ///< default initial size
350 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit ; ///< Count of attempts to relocate before giving up
354 template <typename K>
355 static node_type * alloc_node( K const& key )
357 return cxx_node_allocator().New( key );
359 # ifdef CDS_EMPLACE_SUPPORT
360 template <typename K, typename... Args>
361 static node_type * alloc_node( K&& key, Args&&... args )
363 return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
367 static void free_node( node_type * pNode )
369 cxx_node_allocator().Delete( pNode );
375 struct node_disposer {
376 void operator()( node_type * pNode )
382 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
384 #ifndef CDS_CXX11_LAMBDA_SUPPORT
385 struct empty_insert_functor
387 void operator()( value_type& ) const
391 template <typename Q>
392 class insert_value_functor
396 insert_value_functor( Q const & v)
400 void operator()( value_type& item )
406 template <typename Func>
407 class insert_key_wrapper: protected cds::details::functor_wrapper<Func>
409 typedef cds::details::functor_wrapper<Func> base_class;
411 insert_key_wrapper( Func f ): base_class(f) {}
413 void operator()( node_type& item )
415 base_class::get()( item.m_val );
419 template <typename Func>
420 class ensure_wrapper: protected cds::details::functor_wrapper<Func>
422 typedef cds::details::functor_wrapper<Func> base_class;
424 ensure_wrapper( Func f) : base_class(f) {}
426 void operator()( bool bNew, node_type& item, node_type const& )
428 base_class::get()( bNew, item.m_val );
432 template <typename Func>
433 class find_wrapper: protected cds::details::functor_wrapper<Func>
435 typedef cds::details::functor_wrapper<Func> base_class;
437 find_wrapper( Func f )
441 template <typename Q>
442 void operator()( node_type& item, Q& val )
444 base_class::get()( item.m_val, val );
447 #endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT
452 /// Default constructor
454 Initial size = \ref c_nDefaultInitialSize
457 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
458 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
460 Probe set threshold = probe set size - 1
465 /// Constructs an object with given probe set size and threshold
467 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
468 then \p nProbesetSize should be equal to vector's \p Capacity.
471 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
472 , unsigned int nProbesetSize ///< probe set size
473 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
475 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
478 /// Constructs an object with given hash functor tuple
480 The probe set size and threshold are set as default, see CuckooSet()
483 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
488 /// Constructs a map with given probe set properties and hash functor tuple
490 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
491 then \p nProbesetSize should be equal to vector's \p Capacity.
494 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
495 , unsigned int nProbesetSize ///< probe set size
496 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
497 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
499 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
502 # ifdef CDS_MOVE_SEMANTICS_SUPPORT
503 /// Constructs a map with given hash functor tuple (move semantics)
505 The probe set size and threshold are set as default, see CuckooSet()
508 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
510 : base_class( std::forward<hash_tuple_type>(h) )
513 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
515 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
516 then \p nProbesetSize should be equal to vector's \p Capacity.
519 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
520 , unsigned int nProbesetSize ///< probe set size
521 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
522 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
524 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
526 # endif // ifdef CDS_MOVE_SEMANTICS_SUPPORT
528 /// Destructor clears the map
535 /// Inserts new node with key and default value
537 The function creates a node with \p key and default value, and then inserts the node created into the map.
540 - The \ref key_type should be constructible from a value of type \p K.
541 In trivial case, \p K is equal to \ref key_type.
542 - The \ref mapped_type should be default-constructible.
544 Returns \p true if inserting successful, \p false otherwise.
546 template <typename K>
547 bool insert( K const& key )
549 # ifdef CDS_CXX11_LAMBDA_SUPPORT
550 return insert_key( key, [](value_type&){} );
552 return insert_key( key, empty_insert_functor() );
558 The function creates a node with copy of \p val value
559 and then inserts the node created into the map.
562 - The \ref key_type should be constructible from \p key of type \p K.
563 - The \ref value_type should be constructible from \p val of type \p V.
565 Returns \p true if \p val is inserted into the set, \p false otherwise.
567 template <typename K, typename V>
568 bool insert( K const& key, V const& val )
570 # ifdef CDS_CXX11_LAMBDA_SUPPORT
571 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
573 insert_value_functor<V> f(val);
574 return insert_key( key, cds::ref(f) );
578 /// Inserts new node and initialize it by a functor
580 This function inserts new node with key \p key and if inserting is successful then it calls
581 \p func functor with signature
584 void operator()( value_type& item );
588 The argument \p item of user-defined functor \p func is the reference
589 to the map's item inserted:
590 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
591 - <tt>item.second</tt> is a reference to item's value that may be changed.
593 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
594 and it is called only if inserting is successful.
596 The key_type should be constructible from value of type \p K.
598 The function allows to split creating of new item into two part:
599 - create item from \p key;
600 - insert new item into the map;
601 - if inserting is successful, initialize the value of item by calling \p func functor
603 This can be useful if complete initialization of object of \p value_type is heavyweight and
604 it is preferable that the initialization should be completed only if inserting is successful.
606 template <typename K, typename Func>
607 bool insert_key( const K& key, Func func )
609 scoped_node_ptr pNode( alloc_node( key ));
610 # ifdef CDS_CXX11_LAMBDA_SUPPORT
611 if ( base_class::insert( *pNode, [&func]( node_type& item ) { cds::unref(func)( item.m_val ); } ))
613 insert_key_wrapper<Func> wrapper(func);
614 if ( base_class::insert( *pNode, cds::ref(wrapper) ))
623 # ifdef CDS_EMPLACE_SUPPORT
624 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
626 Returns \p true if inserting successful, \p false otherwise.
628 This function is available only for compiler that supports
629 variadic template and move semantics
631 template <typename K, typename... Args>
632 bool emplace( K&& key, Args&&... args )
634 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
635 if ( base_class::insert( *pNode )) {
644 /// Ensures that the \p key exists in the map
646 The operation performs inserting or changing data with lock-free manner.
648 If the \p key not found in the map, then the new item created from \p key
649 is inserted into the map (note that in this case the \ref key_type should be
650 constructible from type \p K).
651 Otherwise, the functor \p func is called with item found.
652 The functor \p Func may be a function with signature:
654 void func( bool bNew, value_type& item );
659 void operator()( bool bNew, value_type& item );
664 - \p bNew - \p true if the item has been inserted, \p false otherwise
665 - \p item - item of the list
667 The functor may change any fields of the \p item.second that is \ref value_type.
669 You may pass \p func argument by reference using <tt>boost::ref</tt>.
671 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
672 \p second is true if new item has been added or \p false if the item with \p key
673 already is in the list.
675 template <typename K, typename Func>
676 std::pair<bool, bool> ensure( K const& key, Func func )
678 scoped_node_ptr pNode( alloc_node( key ));
679 # ifdef CDS_CXX11_LAMBDA_SUPPORT
680 std::pair<bool, bool> res = base_class::ensure( *pNode,
681 [&func](bool bNew, node_type& item, node_type const& ){ cds::unref(func)( bNew, item.m_val ); }
684 ensure_wrapper<Func> wrapper( func );
685 std::pair<bool, bool> res = base_class::ensure( *pNode, cds::ref(wrapper) );
687 if ( res.first && res.second )
692 /// Delete \p key from the map
693 /** \anchor cds_nonintrusive_CuckooMap_erase_val
695 Return \p true if \p key is found and deleted, \p false otherwise
697 template <typename K>
698 bool erase( K const& key )
700 node_type * pNode = base_class::erase(key);
708 /// Deletes the item from the list using \p pred predicate for searching
710 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
711 but \p pred is used for key comparing.
712 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
713 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
714 \p Predicate must imply the same element order as the comparator used for building the map.
716 template <typename K, typename Predicate>
717 bool erase_with( K const& key, Predicate pred )
719 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
727 /// Delete \p key from the map
728 /** \anchor cds_nonintrusive_CuckooMap_erase_func
730 The function searches an item with key \p key, calls \p f functor
731 and deletes the item. If \p key is not found, the functor is not called.
733 The functor \p Func interface:
736 void operator()(value_type& item) { ... }
739 The functor may be passed by reference using <tt>boost:ref</tt>
741 Return \p true if key is found and deleted, \p false otherwise
745 template <typename K, typename Func>
746 bool erase( K const& key, Func f )
748 node_type * pNode = base_class::erase( key );
750 cds::unref(f)( pNode->m_val );
757 /// Deletes the item from the list using \p pred predicate for searching
759 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
760 but \p pred is used for key comparing.
761 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
762 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
763 \p Predicate must imply the same element order as the comparator used for building the map.
765 template <typename K, typename Predicate, typename Func>
766 bool erase_with( K const& key, Predicate pred, Func f )
768 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
770 cds::unref(f)( pNode->m_val );
777 /// Find the key \p key
778 /** \anchor cds_nonintrusive_CuckooMap_find_func
780 The function searches the item with key equal to \p key and calls the functor \p f for item found.
781 The interface of \p Func functor is:
784 void operator()( value_type& item );
787 where \p item is the item found.
789 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
791 The functor may change \p item.second.
793 The function returns \p true if \p key is found, \p false otherwise.
795 template <typename K, typename Func>
796 bool find( K const& key, Func f )
798 # ifdef CDS_CXX11_LAMBDA_SUPPORT
799 return base_class::find( key, [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
801 find_wrapper<Func> wrapper(f);
802 return base_class::find( key, cds::ref(wrapper) );
806 /// Find the key \p val using \p pred predicate for comparing
808 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
809 but \p pred is used for key comparison.
810 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
811 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
812 \p pred must imply the same element order as the comparator used for building the map.
814 template <typename K, typename Predicate, typename Func>
815 bool find_with( K const& key, Predicate pred, Func f )
817 # ifdef CDS_CXX11_LAMBDA_SUPPORT
818 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
819 [&f](node_type& item, K const& ) { cds::unref(f)( item.m_val );});
821 find_wrapper<Func> wrapper(f);
822 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(), cds::ref(wrapper) );
826 /// Find the key \p key
827 /** \anchor cds_nonintrusive_CuckooMap_find_val
829 The function searches the item with key equal to \p key
830 and returns \p true if it is found, and \p false otherwise.
832 template <typename K>
833 bool find( K const& key )
835 return base_class::find( key );
838 /// Find the key \p val using \p pred predicate for comparing
840 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
841 but \p pred is used for key comparison.
842 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
843 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
844 \p pred must imply the same element order as the comparator used for building the map.
846 template <typename K, typename Predicate>
847 bool find_with( K const& key, Predicate pred )
849 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
855 base_class::clear_and_dispose( node_disposer() );
858 /// Checks if the map is empty
860 Emptiness is checked by item counting: if item count is zero then the map is empty.
864 return base_class::empty();
867 /// Returns item count in the map
870 return base_class::size();
873 /// Returns the size of hash table
875 The hash table size is non-constant and can be increased via resizing.
877 size_t bucket_count() const
879 return base_class::bucket_count();
882 /// Returns lock array size
884 The lock array size is constant.
886 size_t lock_count() const
888 return base_class::lock_count();
891 /// Returns const reference to internal statistics
892 stat const& statistics() const
894 return base_class::statistics();
897 /// Returns const reference to mutex policy internal statistics
898 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
900 return base_class::mutex_policy_statistics();
904 }} // namespace cds::container
906 #endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H