3 #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
4 #define CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H
6 #include <cds/intrusive/multilevel_hashset_rcu.h>
7 #include <cds/container/details/multilevel_hashmap_base.h>
9 namespace cds { namespace container {
11 /// Hash map based on multi-level array
12 /** @ingroup cds_nonintrusive_map
13 @anchor cds_container_MultilevelHashMap_rcu
16 - [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays:
17 Wait-free Extensible Hash Maps"
19 See algorithm short description @ref cds_container_MultilevelHashMap_hp "here"
21 @note Two important things you should keep in mind when you're using \p %MultiLevelHashMap:
22 - all keys is converted to fixed-size bit-string by hash functor provided.
23 You can use variable-length keys, for example, \p std::string as a key for \p %MultiLevelHashMap,
24 but real key in the map will be fixed-size hash values of your keys.
25 For the strings you may use well-known hashing algorithms like <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithm">SHA1, SHA2</a>,
26 <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>, <a href="https://en.wikipedia.org/wiki/CityHash">CityHash</a>
27 or its successor <a href="https://code.google.com/p/farmhash/">FarmHash</a> and so on, which
28 converts variable-length strings to fixed-length bit-strings, and such hash values will be the keys in \p %MultiLevelHashMap.
29 - \p %MultiLevelHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
30 have identical hash then you cannot insert both that keys in the map. \p %MultiLevelHashMap does not maintain the key,
31 it maintains its fixed-size hash value.
33 The map supports @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional thread-safe iterators".
36 - \p RCU - one of \ref cds_urcu_gc "RCU type"
37 - \p Key - a key type to be stored in the map
38 - \p T - a value type to be stored in the map
39 - \p Traits - type traits, the structure based on \p multilevel_hashmap::traits or result of \p multilevel_hashmap::make_traits metafunction.
41 @note Before including <tt><cds/intrusive/multilevel_hashset_rcu.h></tt> you should include appropriate RCU header file,
42 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
48 #ifdef CDS_DOXYGEN_INVOKED
49 ,class Traits = multilevel_hashmap::traits
54 class MultiLevelHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
55 #ifdef CDS_DOXYGEN_INVOKED
56 : protected cds::intrusive::MultiLevelHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
58 : protected cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
62 typedef cds::container::details::make_multilevel_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
63 typedef typename maker::type base_class;
66 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
67 typedef Key key_type; ///< Key type
68 typedef T mapped_type; ///< Mapped type
69 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
70 typedef Traits traits; ///< Map traits
71 #ifdef CDS_DOXYGEN_INVOKED
72 typedef typename traits::hash hasher; ///< Hash functor, see \p multilevel_hashmap::traits::hash
74 typedef typename maker::hasher hasher;
77 typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
78 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
79 typedef typename traits::item_counter item_counter; ///< Item counter type
80 typedef typename traits::allocator allocator; ///< Element allocator
81 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
82 typedef typename traits::memory_model memory_model; ///< Memory model
83 typedef typename traits::back_off back_off; ///< Backoff strategy
84 typedef typename traits::stat stat; ///< Internal statistics type
85 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
86 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
87 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
91 typedef typename maker::node_type node_type;
92 typedef typename maker::cxx_node_allocator cxx_node_allocator;
93 typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
97 value_type * operator()(node_type * p) const
99 return p ? &p->m_Value : nullptr;
104 /// pointer to extracted node
105 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
108 template <bool IsConst>
109 class bidirectional_iterator: public base_class::iterator_base
111 friend class MultiLevelHashMap;
112 typedef typename base_class::iterator_base iterator_base;
115 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
118 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
119 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
122 bidirectional_iterator() CDS_NOEXCEPT
125 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
126 : iterator_base( rhs )
129 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
131 iterator_base::operator=( rhs );
135 bidirectional_iterator& operator++()
137 iterator_base::operator++();
141 bidirectional_iterator& operator--()
143 iterator_base::operator--();
147 value_ptr operator ->() const CDS_NOEXCEPT
149 node_type * p = iterator_base::pointer();
150 return p ? &p->m_Value : nullptr;
153 value_ref operator *() const CDS_NOEXCEPT
155 node_type * p = iterator_base::pointer();
162 iterator_base::release();
165 template <bool IsConst2>
166 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
168 return iterator_base::operator==( rhs );
171 template <bool IsConst2>
172 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
174 return !( *this == rhs );
177 public: // for internal use only!
178 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
179 : iterator_base( set, pNode, idx, false )
182 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
183 : iterator_base( set, pNode, idx )
187 /// Reverse bidirectional iterator
188 template <bool IsConst>
189 class reverse_bidirectional_iterator : public base_class::iterator_base
191 friend class MultiLevelHashMap;
192 typedef typename base_class::iterator_base iterator_base;
195 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
196 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
199 reverse_bidirectional_iterator() CDS_NOEXCEPT
203 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
204 : iterator_base( rhs )
207 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
209 iterator_base::operator=( rhs );
213 reverse_bidirectional_iterator& operator++()
215 iterator_base::operator--();
219 reverse_bidirectional_iterator& operator--()
221 iterator_base::operator++();
225 value_ptr operator ->() const CDS_NOEXCEPT
227 node_type * p = iterator_base::pointer();
228 return p ? &p->m_Value : nullptr;
231 value_ref operator *() const CDS_NOEXCEPT
233 node_type * p = iterator_base::pointer();
240 iterator_base::release();
243 template <bool IsConst2>
244 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
246 return iterator_base::operator==( rhs );
249 template <bool IsConst2>
250 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
252 return !( *this == rhs );
255 public: // for internal use only!
256 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
257 : iterator_base( set, pNode, idx, false )
260 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
261 : iterator_base( set, pNode, idx, false )
263 iterator_base::backward();
269 #ifdef CDS_DOXYGEN_INVOKED
270 typedef implementation_defined iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional iterator" type
271 typedef implementation_defined const_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional const iterator" type
272 typedef implementation_defined reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse iterator" type
273 typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_MultilevelHashMap_rcu_iterators "bidirectional reverse const iterator" type
275 typedef bidirectional_iterator<false> iterator;
276 typedef bidirectional_iterator<true> const_iterator;
277 typedef reverse_bidirectional_iterator<false> reverse_iterator;
278 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
287 /// Creates empty map
289 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
290 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
292 Equation for \p head_bits and \p array_bits:
294 sizeof(hash_type) * 8 == head_bits + N * array_bits
296 where \p N is multi-level array depth.
298 MultiLevelHashMap( size_t head_bits = 8, size_t array_bits = 4 )
299 : base_class( head_bits, array_bits )
302 /// Destructs the map and frees all data
306 /// Inserts new element with key and default value
308 The function creates an element with \p key and default value, and then inserts the node created into the map.
311 - The \p key_type should be constructible from a value of type \p K.
312 In trivial case, \p K is equal to \p key_type.
313 - The \p mapped_type should be default-constructible.
315 Returns \p true if inserting successful, \p false otherwise.
317 The function locks RCU internally.
319 template <typename K>
320 bool insert( K&& key )
322 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
323 if ( base_class::insert( *sp )) {
330 /// Inserts new element
332 The function creates a node with copy of \p val value
333 and then inserts the node created into the map.
336 - The \p key_type should be constructible from \p key of type \p K.
337 - The \p value_type should be constructible from \p val of type \p V.
339 Returns \p true if \p val is inserted into the map, \p false otherwise.
341 The function locks RCU internally.
343 template <typename K, typename V>
344 bool insert( K&& key, V&& val )
346 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
347 if ( base_class::insert( *sp )) {
354 /// Inserts new element and initialize it by a functor
356 This function inserts new element with key \p key and if inserting is successful then it calls
357 \p func functor with signature
360 void operator()( value_type& item );
364 The argument \p item of user-defined functor \p func is the reference
365 to the map's item inserted:
366 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
367 - <tt>item.second</tt> is a reference to item's value that may be changed.
369 \p key_type should be constructible from value of type \p K.
371 The function allows to split creating of new item into two part:
372 - create item from \p key;
373 - insert new item into the map;
374 - if inserting is successful, initialize the value of item by calling \p func functor
376 This can be useful if complete initialization of object of \p value_type is heavyweight and
377 it is preferable that the initialization should be completed only if inserting is successful.
379 The function locks RCU internally.
381 template <typename K, typename Func>
382 bool insert_with( K&& key, Func func )
384 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
385 if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
392 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
394 Returns \p true if inserting successful, \p false otherwise.
396 The function locks RCU internally.
398 template <typename K, typename... Args>
399 bool emplace( K&& key, Args&&... args )
401 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
402 if ( base_class::insert( *sp )) {
409 /// Updates data by \p key
411 The operation performs inserting or replacing the element with lock-free manner.
413 If the \p key not found in the map, then the new item created from \p key
414 will be inserted into the map iff \p bInsert is \p true
415 (note that in this case the \ref key_type should be constructible from type \p K).
416 Otherwise, if \p key is found, it is replaced with a new item created from
418 The functor \p Func signature:
421 void operator()( value_type& item, value_type * old );
425 - \p item - item of the map
426 - \p old - old item of the map, if \p nullptr - the new item was inserted
428 The functor may change any fields of the \p item.second.
430 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
431 \p second is \p true if new item has been added or \p false if \p key already exists.
433 The function locks RCU internally.
435 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
437 template <typename K, typename Func>
438 std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
440 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
441 std::pair<bool, bool> result = base_class::do_update( *sp,
442 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
449 /// Delete \p key from the map
451 \p key_type must be constructible from value of type \p K.
452 The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
454 Return \p true if \p key is found and deleted, \p false otherwise.
456 RCU should not be locked. The function locks RCU internally.
458 template <typename K>
459 bool erase( K const& key )
461 hash_type h = m_Hasher( key_type( key ));
462 return base_class::erase( h );
465 /// Delete \p key from the map
467 The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
468 calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
470 The functor \p Func interface:
473 void operator()(value_type& item) { ... }
476 where \p item is the element found.
478 \p key_type must be constructible from value of type \p K.
480 Return \p true if key is found and deleted, \p false otherwise
482 RCU should not be locked. The function locks RCU internally.
484 template <typename K, typename Func>
485 bool erase( K const& key, Func f )
487 hash_type h = m_Hasher( key_type( key ));
488 return base_class::erase( h, [&f]( node_type& node) { f( node.m_Value ); } );
491 /// Extracts the item from the map with specified \p key
493 The function searches an item with key equal to <tt>hash( key_type( key ))</tt> in the map,
494 unlinks it from the map, and returns a guarded pointer to the item found.
495 If \p key is not found the function returns an empty guarded pointer.
497 RCU \p synchronize method can be called. RCU should NOT be locked.
498 The function does not call the disposer for the item found.
499 The disposer will be implicitly invoked when the returned object is destroyed or when
500 its \p release() member function is called.
503 typedef cds::container::MultiLevelHashMap< cds::urcu::gc< cds::urcu::general_buffered<>>, int, foo, my_traits > map_type;
507 typename map_type::exempt_ptr ep( theMap.extract( 5 ));
512 // Dispose returned item.
517 template <typename K>
518 exempt_ptr extract( K const& key )
520 check_deadlock_policy::check();
525 p = base_class::do_erase( m_Hasher( key_type(key)), [](node_type const&) -> bool {return true;});
527 return exempt_ptr(p);
530 /// Checks whether the map contains \p key
532 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
533 and returns \p true if it is found, or \p false otherwise.
535 template <typename K>
536 bool contains( K const& key )
538 return base_class::contains( m_Hasher( key_type( key )) );
541 /// Find the key \p key
544 The function searches the item by its hash that is equal to <tt>hash( key_type( key ))</tt>
545 and calls the functor \p f for item found.
546 The interface of \p Func functor is:
549 void operator()( value_type& item );
552 where \p item is the item found.
554 The functor may change \p item.second.
556 The function returns \p true if \p key is found, \p false otherwise.
558 template <typename K, typename Func>
559 bool find( K const& key, Func f )
561 return base_class::find( m_Hasher( key_type( key )), [&f](node_type& node) { f( node.m_Value );});
564 /// Finds the key \p key and return the item found
566 The function searches the item by its \p hash
567 and returns the pointer to the item found.
568 If \p hash is not found the function returns \p nullptr.
570 RCU should be locked before the function invocation.
571 Returned pointer is valid only while RCU is locked.
575 typedef cds::container::MultiLevelHashMap< your_template_params > my_map;
582 foo * p = theMap.get( 5 );
590 template <typename K>
591 value_type * get( K const& key )
593 node_type * p = base_class::get( m_Hasher( key_type( key )));
594 return p ? &p->m_Value : nullptr;
597 /// Clears the map (non-atomic)
599 The function unlink all data node from the map.
600 The function is not atomic but is thread-safe.
601 After \p %clear() the map may not be empty because another threads may insert items.
608 /// Checks if the map is empty
610 Emptiness is checked by item counting: if item count is zero then the map is empty.
611 Thus, the correct item counting feature is an important part of the map implementation.
615 return base_class::empty();
618 /// Returns item count in the map
621 return base_class::size();
624 /// Returns const reference to internal statistics
625 stat const& statistics() const
627 return base_class::statistics();
630 /// Returns the size of head node
631 size_t head_size() const
633 return base_class::head_size();
636 /// Returns the size of the array node
637 size_t array_node_size() const
639 return base_class::array_node_size();
643 ///@name Thread-safe iterators
644 /** @anchor cds_container_MultilevelHashMap_rcu_iterators
645 The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
646 under explicit RCU lock.
647 RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
648 since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
649 while your thread is iterating.
651 A typical example is:
655 uint32_t payload; // only for example
657 typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
658 typedef cds::container::MultiLevelHashMap< rcu, std::string, foo> map_type;
664 // iterate over the map
667 typename set_type::rcu_lock l; // scoped RCU lock
670 for ( auto i = m.begin(); i != s.end(); ++i ) {
671 // deal with i. Remember, erasing is prohibited here!
674 } // at this point RCU lock is released
677 Each iterator object supports the common interface:
678 - dereference operators:
680 value_type [const] * operator ->() noexcept
681 value_type [const] & operator *() noexcept
683 - pre-increment and pre-decrement. Post-operators is not supported
684 - equality operators <tt>==</tt> and <tt>!=</tt>.
685 Iterators are equal iff they point to the same cell of the same array node.
686 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
687 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
689 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
690 in an array node that is being splitted.
693 /// Returns an iterator to the beginning of the map
696 return base_class::template init_begin<iterator>();
699 /// Returns an const iterator to the beginning of the map
700 const_iterator begin() const
702 return base_class::template init_begin<const_iterator>();
705 /// Returns an const iterator to the beginning of the map
706 const_iterator cbegin()
708 return base_class::template init_begin<const_iterator>();
711 /// Returns an iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
714 return base_class::template init_end<iterator>();
717 /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
718 const_iterator end() const
720 return base_class::template init_end<const_iterator>();
723 /// Returns a const iterator to the element following the last element of the map. This element acts as a placeholder; attempting to access it results in undefined behavior.
724 const_iterator cend()
726 return base_class::template init_end<const_iterator>();
729 /// Returns a reverse iterator to the first element of the reversed map
730 reverse_iterator rbegin()
732 return base_class::template init_rbegin<reverse_iterator>();
735 /// Returns a const reverse iterator to the first element of the reversed map
736 const_reverse_iterator rbegin() const
738 return base_class::template init_rbegin<const_reverse_iterator>();
741 /// Returns a const reverse iterator to the first element of the reversed map
742 const_reverse_iterator crbegin()
744 return base_class::template init_rbegin<const_reverse_iterator>();
747 /// Returns a reverse iterator to the element following the last element of the reversed map
749 It corresponds to the element preceding the first element of the non-reversed container.
750 This element acts as a placeholder, attempting to access it results in undefined behavior.
752 reverse_iterator rend()
754 return base_class::template init_rend<reverse_iterator>();
757 /// Returns a const reverse iterator to the element following the last element of the reversed map
759 It corresponds to the element preceding the first element of the non-reversed container.
760 This element acts as a placeholder, attempting to access it results in undefined behavior.
762 const_reverse_iterator rend() const
764 return base_class::template init_rend<const_reverse_iterator>();
767 /// Returns a const reverse iterator to the element following the last element of the reversed map
769 It corresponds to the element preceding the first element of the non-reversed container.
770 This element acts as a placeholder, attempting to access it results in undefined behavior.
772 const_reverse_iterator crend()
774 return base_class::template init_rend<const_reverse_iterator>();
778 }} // namespace cds::container
780 #endif // #ifndef CDSLIB_CONTAINER_MULTILEVEL_HASHMAP_RCU_H