3 #ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
4 #define CDSLIB_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;
271 typedef cds::container::cuckoo::implementation_tag implementation_tag;
276 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
277 typedef typename base_class::scoped_full_lock scoped_full_lock;
278 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
279 typedef typename maker::key_accessor key_accessor;
281 typedef typename base_class::value_type node_type;
282 typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
286 static unsigned int const c_nDefaultProbesetSize = base_class::c_nDefaultProbesetSize; ///< default probeset size
287 static size_t const c_nDefaultInitialSize = base_class::c_nDefaultInitialSize; ///< default initial size
288 static unsigned int const c_nRelocateLimit = base_class::c_nRelocateLimit; ///< Count of attempts to relocate before giving up
292 template <typename K>
293 static node_type * alloc_node( K const& key )
295 return cxx_node_allocator().New( key );
297 template <typename K, typename... Args>
298 static node_type * alloc_node( K&& key, Args&&... args )
300 return cxx_node_allocator().MoveNew( std::forward<K>( key ), std::forward<Args>(args)... );
303 static void free_node( node_type * pNode )
305 cxx_node_allocator().Delete( pNode );
311 struct node_disposer {
312 void operator()( node_type * pNode )
318 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
323 /// Default constructor
325 Initial size = \ref c_nDefaultInitialSize
328 - \ref c_nDefaultProbesetSize if \p probeset_type is \p cuckoo::list
329 - \p Capacity if \p probeset_type is <tt> cuckoo::vector<Capacity> </tt>
331 Probe set threshold = probe set size - 1
336 /// Constructs an object with given probe set size and threshold
338 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
339 then \p nProbesetSize should be equal to vector's \p Capacity.
342 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
343 , unsigned int nProbesetSize ///< probe set size
344 , unsigned int nProbesetThreshold = 0 ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
346 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold )
349 /// Constructs an object with given hash functor tuple
351 The probe set size and threshold are set as default, see CuckooSet()
354 hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
359 /// Constructs a map with given probe set properties and hash functor tuple
361 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
362 then \p nProbesetSize should be equal to vector's \p Capacity.
365 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
366 , unsigned int nProbesetSize ///< probe set size
367 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
368 , hash_tuple_type const& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
370 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, h )
373 /// Constructs a map with given hash functor tuple (move semantics)
375 The probe set size and threshold are set as default, see CuckooSet()
378 hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
380 : base_class( std::forward<hash_tuple_type>(h) )
383 /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
385 If probe set type is <tt> cuckoo::vector<Capacity> </tt> vector
386 then \p nProbesetSize should be equal to vector's \p Capacity.
389 size_t nInitialSize ///< Initial map size; if 0 - use default initial size \ref c_nDefaultInitialSize
390 , unsigned int nProbesetSize ///< probe set size
391 , unsigned int nProbesetThreshold ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
392 , hash_tuple_type&& h ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
394 : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
397 /// Destructor clears the map
404 /// Inserts new node with key and default value
406 The function creates a node with \p key and default value, and then inserts the node created into the map.
409 - The \ref key_type should be constructible from a value of type \p K.
410 In trivial case, \p K is equal to \ref key_type.
411 - The \ref mapped_type should be default-constructible.
413 Returns \p true if inserting successful, \p false otherwise.
415 template <typename K>
416 bool insert( K const& key )
418 return insert_with( key, [](value_type&){} );
423 The function creates a node with copy of \p val value
424 and then inserts the node created into the map.
427 - The \ref key_type should be constructible from \p key of type \p K.
428 - The \ref value_type should be constructible from \p val of type \p V.
430 Returns \p true if \p val is inserted into the set, \p false otherwise.
432 template <typename K, typename V>
433 bool insert( K const& key, V const& val )
435 return insert_with( key, [&val](value_type& item) { item.second = val ; } );
438 /// Inserts new node and initialize it by a functor
440 This function inserts new node with key \p key and if inserting is successful then it calls
441 \p func functor with signature
444 void operator()( value_type& item );
448 The argument \p item of user-defined functor \p func is the reference
449 to the map's item inserted:
450 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
451 - <tt>item.second</tt> is a reference to item's value that may be changed.
453 The key_type should be constructible from value of type \p K.
455 The function allows to split creating of new item into two part:
456 - create item from \p key;
457 - insert new item into the map;
458 - if inserting is successful, initialize the value of item by calling \p func functor
460 This can be useful if complete initialization of object of \p value_type is heavyweight and
461 it is preferable that the initialization should be completed only if inserting is successful.
463 template <typename K, typename Func>
464 bool insert_with( const K& key, Func func )
466 scoped_node_ptr pNode( alloc_node( key ));
467 if ( base_class::insert( *pNode, [&func]( node_type& item ) { func( item.m_val ); } )) {
474 /// For key \p key inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
476 Returns \p true if inserting successful, \p false otherwise.
478 template <typename K, typename... Args>
479 bool emplace( K&& key, Args&&... args )
481 scoped_node_ptr pNode( alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
482 if ( base_class::insert( *pNode )) {
489 /// Ensures that the \p key exists in the map
491 The operation performs inserting or changing data with lock-free manner.
493 If the \p key not found in the map, then the new item created from \p key
494 is inserted into the map (note that in this case the \ref key_type should be
495 constructible from type \p K).
496 Otherwise, the functor \p func is called with item found.
497 The functor \p Func may be a function with signature:
499 void func( bool bNew, value_type& item );
504 void operator()( bool bNew, value_type& item );
509 - \p bNew - \p true if the item has been inserted, \p false otherwise
510 - \p item - item of the list
512 The functor may change any fields of the \p item.second that is \ref value_type.
514 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
515 \p second is true if new item has been added or \p false if the item with \p key
516 already is in the list.
518 template <typename K, typename Func>
519 std::pair<bool, bool> ensure( K const& key, Func func )
521 scoped_node_ptr pNode( alloc_node( key ));
522 std::pair<bool, bool> res = base_class::ensure( *pNode,
523 [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
525 if ( res.first && res.second )
530 /// Delete \p key from the map
531 /** \anchor cds_nonintrusive_CuckooMap_erase_val
533 Return \p true if \p key is found and deleted, \p false otherwise
535 template <typename K>
536 bool erase( K const& key )
538 node_type * pNode = base_class::erase(key);
546 /// Deletes the item from the list using \p pred predicate for searching
548 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_val "erase(Q const&)"
549 but \p pred is used for key comparing.
550 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
551 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
552 \p Predicate must imply the same element order as the comparator used for building the map.
554 template <typename K, typename Predicate>
555 bool erase_with( K const& key, Predicate pred )
558 node_type * pNode = base_class::erase_with(key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
566 /// Delete \p key from the map
567 /** \anchor cds_nonintrusive_CuckooMap_erase_func
569 The function searches an item with key \p key, calls \p f functor
570 and deletes the item. If \p key is not found, the functor is not called.
572 The functor \p Func interface:
575 void operator()(value_type& item) { ... }
579 Return \p true if key is found and deleted, \p false otherwise
583 template <typename K, typename Func>
584 bool erase( K const& key, Func f )
586 node_type * pNode = base_class::erase( key );
595 /// Deletes the item from the list using \p pred predicate for searching
597 The function is an analog of \ref cds_nonintrusive_CuckooMap_erase_func "erase(Q const&, Func)"
598 but \p pred is used for key comparing.
599 If cuckoo map is ordered, then \p Predicate should have the interface and semantics like \p std::less.
600 If cuckoo map is unordered, then \p Predicate should have the interface and semantics like \p std::equal_to.
601 \p Predicate must imply the same element order as the comparator used for building the map.
603 template <typename K, typename Predicate, typename Func>
604 bool erase_with( K const& key, Predicate pred, Func f )
607 node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
616 /// Find the key \p key
617 /** \anchor cds_nonintrusive_CuckooMap_find_func
619 The function searches the item with key equal to \p key and calls the functor \p f for item found.
620 The interface of \p Func functor is:
623 void operator()( value_type& item );
626 where \p item is the item found.
628 The functor may change \p item.second.
630 The function returns \p true if \p key is found, \p false otherwise.
632 template <typename K, typename Func>
633 bool find( K const& key, Func f )
635 return base_class::find( key, [&f](node_type& item, K const& ) { f( item.m_val );});
638 /// Find the key \p val using \p pred predicate for comparing
640 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_func "find(K const&, Func)"
641 but \p pred is used for key comparison.
642 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
643 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
644 \p pred must imply the same element order as the comparator used for building the map.
646 template <typename K, typename Predicate, typename Func>
647 bool find_with( K const& key, Predicate pred, Func f )
650 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>(),
651 [&f](node_type& item, K const& ) { f( item.m_val );});
654 /// Find the key \p key
655 /** \anchor cds_nonintrusive_CuckooMap_find_val
657 The function searches the item with key equal to \p key
658 and returns \p true if it is found, and \p false otherwise.
660 template <typename K>
661 bool find( K const& key )
663 return base_class::find( key );
666 /// Find the key \p val using \p pred predicate for comparing
668 The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
669 but \p pred is used for key comparison.
670 If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
671 If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
672 \p pred must imply the same element order as the comparator used for building the map.
674 template <typename K, typename Predicate>
675 bool find_with( K const& key, Predicate pred )
678 return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
684 base_class::clear_and_dispose( node_disposer() );
687 /// Checks if the map is empty
689 Emptiness is checked by item counting: if item count is zero then the map is empty.
693 return base_class::empty();
696 /// Returns item count in the map
699 return base_class::size();
702 /// Returns the size of hash table
704 The hash table size is non-constant and can be increased via resizing.
706 size_t bucket_count() const
708 return base_class::bucket_count();
711 /// Returns lock array size
713 The lock array size is constant.
715 size_t lock_count() const
717 return base_class::lock_count();
720 /// Returns const reference to internal statistics
721 stat const& statistics() const
723 return base_class::statistics();
726 /// Returns const reference to mutex policy internal statistics
727 typename mutex_policy::statistics_type const& mutex_policy_statistics() const
729 return base_class::mutex_policy_statistics();
732 }} // namespace cds::container
734 #endif //#ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H