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_traits;
21 typedef typename original_traits::probeset_type probeset_type;
22 static bool const store_hash = original_traits::store_hash;
23 static unsigned int const store_hash_count = store_hash ? ((unsigned int) std::tuple_size< typename original_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 key_type const& operator()( node_type const& node ) const
48 return node.m_val.first;
52 struct intrusive_traits: public original_traits
54 typedef intrusive::cuckoo::base_hook<
55 cds::intrusive::cuckoo::probeset_type< probeset_type >
56 ,cds::intrusive::cuckoo::store_hash< store_hash_count >
59 typedef cds::intrusive::cuckoo::traits::disposer disposer;
61 typedef typename std::conditional<
62 std::is_same< typename original_traits::equal_to, opt::none >::value
64 , cds::details::predicate_wrapper< node_type, typename original_traits::equal_to, key_accessor >
67 typedef typename std::conditional<
68 std::is_same< typename original_traits::compare, opt::none >::value
70 , cds::details::compare_wrapper< node_type, typename original_traits::compare, key_accessor >
73 typedef typename std::conditional<
74 std::is_same< typename original_traits::less, opt::none >::value
76 ,cds::details::predicate_wrapper< node_type, typename original_traits::less, key_accessor >
79 typedef opt::details::hash_list_wrapper< typename original_traits::hash, node_type, key_accessor > hash;
82 typedef intrusive::CuckooSet< node_type, intrusive_traits > type;
84 } // namespace details
88 /** @ingroup cds_nonintrusive_map
91 - [2007] M.Herlihy, N.Shavit, M.Tzafrir "Concurrent Cuckoo Hashing. Technical report"
92 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
94 <b>About Cuckoo hashing</b>
96 [From "The Art of Multiprocessor Programming"]
97 Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
98 occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
99 N = 2k we use a two-entry array of tables, and two independent hash functions,
100 <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
101 mapping the set of possible keys to entries in he array. To test whether a value \p x is in the set,
102 <tt>find(x)</tt> tests whether either <tt>table[0][h0(x)]</tt> or <tt>table[1][h1(x)]</tt> is
103 equal to \p x. Similarly, <tt>erase(x)</tt>checks whether \p x is in either <tt>table[0][h0(x)]</tt>
104 or <tt>table[1][h1(x)]</tt>, ad removes it if found.
106 The <tt>insert(x)</tt> successively "kicks out" conflicting items until every key has a slot.
107 To add \p x, the method swaps \p x with \p y, the current occupant of <tt>table[0][h0(x)]</tt>.
108 If the prior value was \p nullptr, it is done. Otherwise, it swaps the newly nest-less value \p y
109 for the current occupant of <tt>table[1][h1(y)]</tt> in the same way. As before, if the prior value
110 was \p nullptr, it is done. Otherwise, the method continues swapping entries (alternating tables)
111 until it finds an empty slot. We might not find an empty slot, either because the table is full,
112 or because the sequence of displacement forms a cycle. We therefore need an upper limit on the
113 number of successive displacements we are willing to undertake. When this limit is exceeded,
114 we resize the hash table, choose new hash functions and start over.
116 For concurrent cuckoo hashing, rather than organizing the set as a two-dimensional table of
117 items, we use two-dimensional table of probe sets, where a probe set is a constant-sized set
118 of items with the same hash code. Each probe set holds at most \p PROBE_SIZE items, but the algorithm
119 tries to ensure that when the set is quiescent (i.e no method call in progress) each probe set
120 holds no more than <tt>THRESHOLD < PROBE_SET</tt> items. While method calls are in-flight, a probe
121 set may temporarily hold more than \p THRESHOLD but never more than \p PROBE_SET items.
123 In current implementation, a probe set can be defined either as a (single-linked) list
124 or as a fixed-sized vector, optionally ordered.
126 In description above two-table cuckoo hashing (<tt>k = 2</tt>) has been considered.
127 We can generalize this approach for <tt>k >= 2</tt> when we have \p k hash functions
128 <tt>h[0], ... h[k-1]</tt> and \p k tables <tt>table[0], ... table[k-1]</tt>.
130 The search in probe set is linear, the complexity is <tt> O(PROBE_SET) </tt>.
131 The probe set may be ordered or not. Ordered probe set can be a little better since
132 the average search complexity is <tt>O(PROBE_SET/2)</tt>.
133 However, the overhead of sorting can eliminate a gain of ordered search.
135 The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
136 declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
137 opt::equal_to option.
141 - \p T - the type stored in the map.
142 - \p Traits - map traits., default is \p cuckoo::traits.
143 It is possible to declare option-based set with \p cuckoo::make_traits metafunction
144 result as \p Traits template argument.
148 Declares cuckoo mapping from \p std::string to struct \p foo.
149 For cuckoo hashing we should provide at least two hash functions:
152 size_t operator()(std::string const& s) const
154 return cds::opt::v::hash<std::string>( s );
158 struct hash2: private hash1 {
159 size_t operator()(std::string const& s) const
161 size_t h = ~( hash1::operator()(s));
162 return ~h + 0x9e3779b9 + (h << 6) + (h >> 2);
167 Cuckoo-map with list-based unordered probe set and storing hash values
169 #include <cds/container/cuckoo_map.h>
171 // Declare type traits
172 struct my_traits: public cds::container::cuckoo::traits
174 typedef std::equal_to< std::string > equal_to;
175 typedef std::tuple< hash1, hash2 > hash;
177 static bool const store_hash = true;
180 // Declare CuckooMap type
181 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
183 // Equal option-based declaration
184 typedef cds::container::CuckooMap< std::string, foo,
185 cds::container::cuckoo::make_traits<
186 cds::opt::hash< std::tuple< hash1, hash2 > >
187 ,cds::opt::equal_to< std::equal_to< std::string > >
188 ,cds::container::cuckoo::store_hash< true >
193 If we provide \p less functor instead of \p equal_to
194 we get as a result a cuckoo map with ordered probe set that may improve
196 Example for ordered vector-based probe-set:
199 #include <cds/container/cuckoo_map.h>
201 // Declare type traits
202 // We use a vector of capacity 4 as probe-set container and store hash values in the node
203 struct my_traits: public cds::container::cuckoo::traits
205 typedef std::less< std::string > less;
206 typedef std::tuple< hash1, hash2 > hash;
207 typedef cds::container::cuckoo::vector<4> probeset_type;
209 static bool const store_hash = true;
212 // Declare CuckooMap type
213 typedef cds::container::CuckooMap< std::string, foo, my_traits > my_cuckoo_map;
215 // Equal option-based declaration
216 typedef cds::container::CuckooMap< std::string, foo,
217 cds::container::cuckoo::make_traits<
218 cds::opt::hash< std::tuple< hash1, hash2 > >
219 ,cds::opt::less< std::less< std::string > >
220 ,cds::container::cuckoo::probeset_type< cds::container::cuckoo::vector<4> >
221 ,cds::container::cuckoo::store_hash< true >
227 template <typename Key, typename T, typename Traits = cuckoo::traits>
229 #ifdef CDS_DOXYGEN_INVOKED
230 protected intrusive::CuckooSet< std::pair< Key const, T>, Traits>
232 protected details::make_cuckoo_map<Key, T, Traits>::type
236 typedef details::make_cuckoo_map<Key, T, Traits> maker;
237 typedef typename maker::type base_class;
240 typedef Key key_type; ///< key type
241 typedef T mapped_type; ///< value type stored in the container
242 typedef std::pair<key_type const, mapped_type> value_type; ///< Key-value pair type stored in the map
243 typedef Traits traits; ///< Map traits
245 typedef typename traits::hash hash; ///< hash functor tuple wrapped for internal use
246 typedef typename base_class::hash_tuple_type hash_tuple_type; ///< hash tuple type
248 typedef typename base_class::mutex_policy mutex_policy; ///< Concurrent access policy, see \p cuckoo::traits::mutex_policy
249 typedef typename base_class::stat stat; ///< internal statistics type
251 static bool const c_isSorted = base_class::c_isSorted; ///< whether the probe set should be ordered
252 static size_t const c_nArity = base_class::c_nArity; ///< the arity of cuckoo hashing: the number of hash functors provided; minimum 2.
254 typedef typename base_class::key_equal_to key_equal_to; ///< Key equality functor; used only for unordered probe-set
256 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
258 typedef typename base_class::allocator allocator; ///< allocator type used for internal bucket table allocations
260 /// Node allocator type
261 typedef typename std::conditional<
262 std::is_same< typename traits::node_allocator, opt::none >::value,
264 typename traits::node_allocator
265 >::type node_allocator;
267 /// item counter type
268 typedef typename traits::item_counter item_counter;
272 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
273 typedef typename base_class::scoped_full_lock scoped_full_lock;
274 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
275 typedef typename maker::key_accessor key_accessor;
277 typedef typename base_class::value_type node_type;
278 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
282 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
283 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
284 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
288 template <typename K>
289 static node_type * alloc_node( K const& key )
291 return cxx_node_allocator().New( key );
293 template <typename K, typename... Args>
294 static node_type * alloc_node( K&& key, Args&&... args )
296 return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
299 static void free_node( node_type * pNode )
301 cxx_node_allocator().Delete( pNode );
307 struct node_disposer {
308 void operator()( node_type * pNode )
314 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
319 /// Default constructor
321 Initial size = \ref c_nDefaultInitialSize
324 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
325 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
327 Probe set threshold = probe set size - 1
332 /// Constructs an object with given probe set size and threshold
334 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
335 then \p nProbesetSize should be equal to vector's \p Capacity.
338 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
339 , unsigned int nProbesetSize ///< probe set size
340 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
342 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
345 /// Constructs an object with given hash functor tuple
347 The probe set size and threshold are set as default, see CuckooSet()
350 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
355 /// Constructs a map with given probe set properties and hash functor tuple
357 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
358 then \p nProbesetSize should be equal to vector's \p Capacity.
361 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
362 , unsigned int nProbesetSize ///< probe set size
363 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
364 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
366 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
369 /// Constructs a map with given hash functor tuple (move semantics)
371 The probe set size and threshold are set as default, see CuckooSet()
374 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
376 : base_class( std::forward<hash_tuple_type>(h) )
379 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
381 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
382 then \p nProbesetSize should be equal to vector's \p Capacity.
385 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
386 , unsigned int nProbesetSize ///< probe set size
387 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
388 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
390 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
393 /// Destructor clears the map
400 /// Inserts new node with key and default value
402 The function creates a node with \p key and default value, and then inserts the node created into the map.
405 - The \ref key_type should be constructible from a value of type \p K.
406 In trivial case, \p K is equal to \ref key_type.
407 - The \ref mapped_type should be default-constructible.
409 Returns \p true if inserting successful, \p false otherwise.
411 template <typename K>
412 bool insert( K const& key )
414 return insert_key( key, [](value_type&){} );
419 The function creates a node with copy of \p val value
420 and then inserts the node created into the map.
423 - The \ref key_type should be constructible from \p key of type \p K.
424 - The \ref value_type should be constructible from \p val of type \p V.
426 Returns \p true if \p val is inserted into the set, \p false otherwise.
428 template <typename K, typename V>
429 bool insert( K const& key, V const& val )
431 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
434 /// Inserts new node and initialize it by a functor
436 This function inserts new node with key \p key and if inserting is successful then it calls
437 \p func functor with signature
440 void operator()( value_type& item );
444 The argument \p item of user-defined functor \p func is the reference
445 to the map's item inserted:
446 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
447 - <tt>item.second</tt> is a reference to item's value that may be changed.
449 The key_type should be constructible from value of type \p K.
451 The function allows to split creating of new item into two part:
452 - create item from \p key;
453 - insert new item into the map;
454 - if inserting is successful, initialize the value of item by calling \p func functor
456 This can be useful if complete initialization of object of \p value_type is heavyweight and
457 it is preferable that the initialization should be completed only if inserting is successful.
459 template <typename K, typename Func>
460 bool insert_key( const K& key, Func func )
462 scoped_node_ptr pNode( alloc_node( key ));
463 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
470 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
472 Returns \p true if inserting successful, \p false otherwise.
474 template <typename K, typename... Args>
475 bool emplace( K&& key, Args&&... args )
477 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
478 if ( base_class::insert( *pNode )) {
485 /// Ensures that the \p key exists in the map
487 The operation performs inserting or changing data with lock-free manner.
489 If the \p key not found in the map, then the new item created from \p key
490 is inserted into the map (note that in this case the \ref key_type should be
491 constructible from type \p K).
492 Otherwise, the functor \p func is called with item found.
493 The functor \p Func may be a function with signature:
495 void func( bool bNew, value_type& item );
500 void operator()( bool bNew, value_type& item );
505 - \p bNew - \p true if the item has been inserted, \p false otherwise
506 - \p item - item of the list
508 The functor may change any fields of the \p item.second that is \ref value_type.
510 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
511 \p second is true if new item has been added or \p false if the item with \p key
512 already is in the list.
514 template <typename K, typename Func>
515 std::pair<bool, bool> ensure( K const& key, Func func )
517 scoped_node_ptr pNode( alloc_node( key ));
518 std::pair<bool, bool> res = base_class::ensure( *pNode,
519 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
521 if ( res.first && res.second )
526 /// Delete \p key from the map
527 /** \anchor cds_nonintrusive_CuckooMap_erase_val
529 Return \p true if \p key is found and deleted, \p false otherwise
531 template <typename K>
532 bool erase( K const& key )
534 node_type * pNode = base_class::erase(key);
542 /// Deletes the item from the list using \p pred predicate for searching
544 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
545 but \p pred is used for key comparing.
546 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
547 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
548 \p Predicate must imply the same element order as the comparator used for building the map.
550 template <typename K, typename Predicate>
551 bool erase_with( K const& key, Predicate pred )
553 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
561 /// Delete \p key from the map
562 /** \anchor cds_nonintrusive_CuckooMap_erase_func
564 The function searches an item with key \p key, calls \p f functor
565 and deletes the item. If \p key is not found, the functor is not called.
567 The functor \p Func interface:
570 void operator()(value_type& item) { ... }
574 Return \p true if key is found and deleted, \p false otherwise
578 template <typename K, typename Func>
579 bool erase( K const& key, Func f )
581 node_type * pNode = base_class::erase( key );
590 /// Deletes the item from the list using \p pred predicate for searching
592 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
593 but \p pred is used for key comparing.
594 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
595 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
596 \p Predicate must imply the same element order as the comparator used for building the map.
598 template <typename K, typename Predicate, typename Func>
599 bool erase_with( K const& key, Predicate pred, Func f )
601 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
610 /// Find the key \p key
611 /** \anchor cds_nonintrusive_CuckooMap_find_func
613 The function searches the item with key equal to \p key and calls the functor \p f for item found.
614 The interface of \p Func functor is:
617 void operator()( value_type& item );
620 where \p item is the item found.
622 The functor may change \p item.second.
624 The function returns \p true if \p key is found, \p false otherwise.
626 template <typename K, typename Func>
627 bool find( K const& key, Func f )
629 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
632 /// Find the key \p val using \p pred predicate for comparing
634 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
635 but \p pred is used for key comparison.
636 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
637 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
638 \p pred must imply the same element order as the comparator used for building the map.
640 template <typename K, typename Predicate, typename Func>
641 bool find_with( K const& key, Predicate pred, Func f )
643 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
644 [&f](node_type& item, K const& ) { f( item.m_val );});
647 /// Find the key \p key
648 /** \anchor cds_nonintrusive_CuckooMap_find_val
650 The function searches the item with key equal to \p key
651 and returns \p true if it is found, and \p false otherwise.
653 template <typename K>
654 bool find( K const& key )
656 return base_class::find( key );
659 /// Find the key \p val using \p pred predicate for comparing
661 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
662 but \p pred is used for key comparison.
663 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
664 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
665 \p pred must imply the same element order as the comparator used for building the map.
667 template <typename K, typename Predicate>
668 bool find_with( K const& key, Predicate pred )
670 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
676 base_class::clear_and_dispose( node_disposer() );
679 /// Checks if the map is empty
681 Emptiness is checked by item counting: if item count is zero then the map is empty.
685 return base_class::empty();
688 /// Returns item count in the map
691 return base_class::size();
694 /// Returns the size of hash table
696 The hash table size is non-constant and can be increased via resizing.
698 size_t bucket_count() const
700 return base_class::bucket_count();
703 /// Returns lock array size
705 The lock array size is constant.
707 size_t lock_count() const
709 return base_class::lock_count();
712 /// Returns const reference to internal statistics
713 stat const& statistics() const
715 return base_class::statistics();
718 /// Returns const reference to mutex policy internal statistics
719 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
721 return base_class::mutex_policy_statistics();
725 }} // namespace cds::container
727 #endif //#ifndef __CDS_CONTAINER_CUCKOO_MAP_H