3 #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
4 #define CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H
6 #include <cds/intrusive/feldman_hashset_rcu.h>
7 #include <cds/container/details/feldman_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_FeldmanHashMap_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_FeldmanHashMap_hp "here"
21 @note Two important things you should keep in mind when you're using \p %FeldmanHashMap:
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 %FeldmanHashMap,
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 %FeldmanHashMap.
29 If your key is fixed-sized the hash functor is optional, see \p feldman_hashmap::traits::hash for explanation and examples.
30 - \p %FeldmanHashMap uses a perfect hashing. It means that if two different keys, for example, of type \p std::string,
31 have identical hash then you cannot insert both that keys in the map. \p %FeldmanHashMap does not maintain the key,
32 it maintains its fixed-size hash value.
34 The map supports @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional thread-safe iterators".
37 - \p RCU - one of \ref cds_urcu_gc "RCU type"
38 - \p Key - a key type to be stored in the map
39 - \p T - a value type to be stored in the map
40 - \p Traits - type traits, the structure based on \p feldman_hashmap::traits or result of \p feldman_hashmap::make_traits metafunction.
42 @note Before including <tt><cds/intrusive/feldman_hashset_rcu.h></tt> you should include appropriate RCU header file,
43 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
49 #ifdef CDS_DOXYGEN_INVOKED
50 ,class Traits = feldman_hashmap::traits
55 class FeldmanHashMap< cds::urcu::gc< RCU >, Key, T, Traits >
56 #ifdef CDS_DOXYGEN_INVOKED
57 : protected cds::intrusive::FeldmanHashSet< cds::urcu::gc< RCU >, std::pair<Key const, T>, Traits >
59 : protected cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits >::type
63 typedef cds::container::details::make_feldman_hashmap< cds::urcu::gc< RCU >, Key, T, Traits > maker;
64 typedef typename maker::type base_class;
67 typedef cds::urcu::gc< RCU > gc; ///< RCU garbage collector
68 typedef Key key_type; ///< Key type
69 typedef T mapped_type; ///< Mapped type
70 typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair to be stored in the map
71 typedef Traits traits; ///< Map traits
72 #ifdef CDS_DOXYGEN_INVOKED
73 typedef typename traits::hash hasher; ///< Hash functor, see \p feldman_hashmap::traits::hash
75 typedef typename maker::hasher hasher;
78 typedef typename maker::hash_type hash_type; ///< Hash type deduced from \p hasher return type
79 typedef typename base_class::hash_comparator hash_comparator; ///< hash compare functor based on \p Traits::compare and \p Traits::less
80 typedef typename traits::item_counter item_counter; ///< Item counter type
81 typedef typename traits::allocator allocator; ///< Element allocator
82 typedef typename traits::node_allocator node_allocator; ///< Array node allocator
83 typedef typename traits::memory_model memory_model; ///< Memory model
84 typedef typename traits::back_off back_off; ///< Backoff strategy
85 typedef typename traits::stat stat; ///< Internal statistics type
86 typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
87 typedef typename gc::scoped_lock rcu_lock; ///< RCU scoped lock
88 static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
92 typedef typename maker::node_type node_type;
93 typedef typename maker::cxx_node_allocator cxx_node_allocator;
94 typedef std::unique_ptr< node_type, typename maker::node_disposer > scoped_node_ptr;
95 typedef typename base_class::check_deadlock_policy check_deadlock_policy;
99 value_type * operator()(node_type * p) const
101 return p ? &p->m_Value : nullptr;
106 /// pointer to extracted node
107 using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename base_class::disposer, node_cast >;
110 template <bool IsConst>
111 class bidirectional_iterator: public base_class::iterator_base
113 friend class FeldmanHashMap;
114 typedef typename base_class::iterator_base iterator_base;
117 static CDS_CONSTEXPR bool const c_bConstantIterator = IsConst;
120 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
121 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
124 bidirectional_iterator() CDS_NOEXCEPT
127 bidirectional_iterator( bidirectional_iterator const& rhs ) CDS_NOEXCEPT
128 : iterator_base( rhs )
131 bidirectional_iterator& operator=(bidirectional_iterator const& rhs) CDS_NOEXCEPT
133 iterator_base::operator=( rhs );
137 bidirectional_iterator& operator++()
139 iterator_base::operator++();
143 bidirectional_iterator& operator--()
145 iterator_base::operator--();
149 value_ptr operator ->() const CDS_NOEXCEPT
151 node_type * p = iterator_base::pointer();
152 return p ? &p->m_Value : nullptr;
155 value_ref operator *() const CDS_NOEXCEPT
157 node_type * p = iterator_base::pointer();
164 iterator_base::release();
167 template <bool IsConst2>
168 bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
170 return iterator_base::operator==( rhs );
173 template <bool IsConst2>
174 bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const CDS_NOEXCEPT
176 return !( *this == rhs );
179 public: // for internal use only!
180 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
181 : iterator_base( set, pNode, idx, false )
184 bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
185 : iterator_base( set, pNode, idx )
189 /// Reverse bidirectional iterator
190 template <bool IsConst>
191 class reverse_bidirectional_iterator : public base_class::iterator_base
193 friend class FeldmanHashMap;
194 typedef typename base_class::iterator_base iterator_base;
197 typedef typename std::conditional< IsConst, value_type const*, value_type*>::type value_ptr; ///< Value pointer
198 typedef typename std::conditional< IsConst, value_type const&, value_type&>::type value_ref; ///< Value reference
201 reverse_bidirectional_iterator() CDS_NOEXCEPT
205 reverse_bidirectional_iterator( reverse_bidirectional_iterator const& rhs ) CDS_NOEXCEPT
206 : iterator_base( rhs )
209 reverse_bidirectional_iterator& operator=( reverse_bidirectional_iterator const& rhs) CDS_NOEXCEPT
211 iterator_base::operator=( rhs );
215 reverse_bidirectional_iterator& operator++()
217 iterator_base::operator--();
221 reverse_bidirectional_iterator& operator--()
223 iterator_base::operator++();
227 value_ptr operator ->() const CDS_NOEXCEPT
229 node_type * p = iterator_base::pointer();
230 return p ? &p->m_Value : nullptr;
233 value_ref operator *() const CDS_NOEXCEPT
235 node_type * p = iterator_base::pointer();
242 iterator_base::release();
245 template <bool IsConst2>
246 bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
248 return iterator_base::operator==( rhs );
251 template <bool IsConst2>
252 bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
254 return !( *this == rhs );
257 public: // for internal use only!
258 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx, bool )
259 : iterator_base( set, pNode, idx, false )
262 reverse_bidirectional_iterator( base_class const& set, typename base_class::array_node * pNode, size_t idx )
263 : iterator_base( set, pNode, idx, false )
265 iterator_base::backward();
271 #ifdef CDS_DOXYGEN_INVOKED
272 typedef implementation_defined iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional iterator" type
273 typedef implementation_defined const_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional const iterator" type
274 typedef implementation_defined reverse_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse iterator" type
275 typedef implementation_defined const_reverse_iterator; ///< @ref cds_container_FeldmanHashMap_rcu_iterators "bidirectional reverse const iterator" type
277 typedef bidirectional_iterator<false> iterator;
278 typedef bidirectional_iterator<true> const_iterator;
279 typedef reverse_bidirectional_iterator<false> reverse_iterator;
280 typedef reverse_bidirectional_iterator<true> const_reverse_iterator;
289 /// Creates empty map
291 @param head_bits: 2<sup>head_bits</sup> specifies the size of head array, minimum is 4.
292 @param array_bits: 2<sup>array_bits</sup> specifies the size of array node, minimum is 2.
294 Equation for \p head_bits and \p array_bits:
296 sizeof(hash_type) * 8 == head_bits + N * array_bits
298 where \p N is multi-level array depth.
300 FeldmanHashMap( size_t head_bits = 8, size_t array_bits = 4 )
301 : base_class( head_bits, array_bits )
304 /// Destructs the map and frees all data
308 /// Inserts new element with key and default value
310 The function creates an element with \p key and default value, and then inserts the node created into the map.
313 - The \p key_type should be constructible from a value of type \p K.
314 In trivial case, \p K is equal to \p key_type.
315 - The \p mapped_type should be default-constructible.
317 Returns \p true if inserting successful, \p false otherwise.
319 The function locks RCU internally.
321 template <typename K>
322 bool insert( K&& key )
324 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key) ));
325 if ( base_class::insert( *sp )) {
332 /// Inserts new element
334 The function creates a node with copy of \p val value
335 and then inserts the node created into the map.
338 - The \p key_type should be constructible from \p key of type \p K.
339 - The \p value_type should be constructible from \p val of type \p V.
341 Returns \p true if \p val is inserted into the map, \p false otherwise.
343 The function locks RCU internally.
345 template <typename K, typename V>
346 bool insert( K&& key, V&& val )
348 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<V>(val)));
349 if ( base_class::insert( *sp )) {
356 /// Inserts new element and initialize it by a functor
358 This function inserts new element with key \p key and if inserting is successful then it calls
359 \p func functor with signature
362 void operator()( value_type& item );
366 The argument \p item of user-defined functor \p func is the reference
367 to the map's item inserted:
368 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
369 - <tt>item.second</tt> is a reference to item's value that may be changed.
371 \p key_type should be constructible from value of type \p K.
373 The function allows to split creating of new item into two part:
374 - create item from \p key;
375 - insert new item into the map;
376 - if inserting is successful, initialize the value of item by calling \p func functor
378 This can be useful if complete initialization of object of \p value_type is heavyweight and
379 it is preferable that the initialization should be completed only if inserting is successful.
381 The function locks RCU internally.
383 template <typename K, typename Func>
384 bool insert_with( K&& key, Func func )
386 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
387 if ( base_class::insert( *sp, [&func]( node_type& item ) { func( item.m_Value ); } )) {
394 /// For key \p key inserts data of type \p value_type created in-place from <tt>std::forward<Args>(args)...</tt>
396 Returns \p true if inserting successful, \p false otherwise.
398 The function locks RCU internally.
400 template <typename K, typename... Args>
401 bool emplace( K&& key, Args&&... args )
403 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key), std::forward<Args>(args)... ));
404 if ( base_class::insert( *sp )) {
411 /// Updates data by \p key
413 The operation performs inserting or replacing the element with lock-free manner.
415 If the \p key not found in the map, then the new item created from \p key
416 will be inserted into the map iff \p bInsert is \p true
417 (note that in this case the \ref key_type should be constructible from type \p K).
418 Otherwise, if \p key is found, it is replaced with a new item created from
420 The functor \p Func signature:
423 void operator()( value_type& item, value_type * old );
427 - \p item - item of the map
428 - \p old - old item of the map, if \p nullptr - the new item was inserted
430 The functor may change any fields of the \p item.second.
432 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
433 \p second is \p true if new item has been added or \p false if \p key already exists.
435 The function locks RCU internally.
437 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
439 template <typename K, typename Func>
440 std::pair<bool, bool> update( K&& key, Func func, bool bInsert = true )
442 scoped_node_ptr sp( cxx_node_allocator().MoveNew( m_Hasher, std::forward<K>(key)));
443 std::pair<bool, bool> result = base_class::do_update( *sp,
444 [&func]( node_type& node, node_type * old ) { func( node.m_Value, old ? &old->m_Value : nullptr );},
451 /// Delete \p key from the map
453 \p key_type must be constructible from value of type \p K.
454 The function deeltes the element with hash value equal to <tt>hash( key_type( key ))</tt>
456 Return \p true if \p key is found and deleted, \p false otherwise.
458 RCU should not be locked. The function locks RCU internally.
460 template <typename K>
461 bool erase( K const& key )
463 return base_class::erase(m_Hasher(key_type(key)));
466 /// Delete \p key from the map
468 The function searches an item with hash value equal to <tt>hash( key_type( key ))</tt>,
469 calls \p f functor and deletes the item. If \p key is not found, the functor is not called.
471 The functor \p Func interface:
474 void operator()(value_type& item) { ... }
477 where \p item is the element found.
479 \p key_type must be constructible from value of type \p K.
481 Return \p true if key is found and deleted, \p false otherwise
483 RCU should not be locked. The function locks RCU internally.
485 template <typename K, typename Func>
486 bool erase( K const& key, Func f )
488 return base_class::erase(m_Hasher(key_type(key)), [&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::FeldmanHashMap< 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::FeldmanHashMap< 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();
642 /// Collects tree level statistics into \p stat
643 /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
645 void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const
647 base_class::get_level_statistics(stat);
651 ///@name Thread-safe iterators
652 /** @anchor cds_container_FeldmanHashMap_rcu_iterators
653 The map supports thread-safe iterators: you may iterate over the map in multi-threaded environment
654 under explicit RCU lock.
655 RCU lock requirement means that inserting or searching is allowed but you must not erase the items from the map
656 since erasing under RCU lock can lead to a deadlock. However, another thread can call \p erase() safely
657 while your thread is iterating.
659 A typical example is:
663 uint32_t payload; // only for example
665 typedef cds::urcu::gc< cds::urcu::general_buffered<>> rcu;
666 typedef cds::container::FeldmanHashMap< rcu, std::string, foo> map_type;
672 // iterate over the map
675 typename set_type::rcu_lock l; // scoped RCU lock
678 for ( auto i = m.begin(); i != s.end(); ++i ) {
679 // deal with i. Remember, erasing is prohibited here!
682 } // at this point RCU lock is released
685 Each iterator object supports the common interface:
686 - dereference operators:
688 value_type [const] * operator ->() noexcept
689 value_type [const] & operator *() noexcept
691 - pre-increment and pre-decrement. Post-operators is not supported
692 - equality operators <tt>==</tt> and <tt>!=</tt>.
693 Iterators are equal iff they point to the same cell of the same array node.
694 Note that for two iterators \p it1 and \p it2 the condition <tt> it1 == it2 </tt>
695 does not entail <tt> &(*it1) == &(*it2) </tt>: welcome to concurrent containers
697 @note It is possible the item can be iterated more that once, for example, if an iterator points to the item
698 in an array node that is being splitted.
701 /// Returns an iterator to the beginning of the map
704 return base_class::template init_begin<iterator>();
707 /// Returns an const iterator to the beginning of the map
708 const_iterator begin() const
710 return base_class::template init_begin<const_iterator>();
713 /// Returns an const iterator to the beginning of the map
714 const_iterator cbegin()
716 return base_class::template init_begin<const_iterator>();
719 /// 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.
722 return base_class::template init_end<iterator>();
725 /// 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.
726 const_iterator end() const
728 return base_class::template init_end<const_iterator>();
731 /// 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.
732 const_iterator cend()
734 return base_class::template init_end<const_iterator>();
737 /// Returns a reverse iterator to the first element of the reversed map
738 reverse_iterator rbegin()
740 return base_class::template init_rbegin<reverse_iterator>();
743 /// Returns a const reverse iterator to the first element of the reversed map
744 const_reverse_iterator rbegin() const
746 return base_class::template init_rbegin<const_reverse_iterator>();
749 /// Returns a const reverse iterator to the first element of the reversed map
750 const_reverse_iterator crbegin()
752 return base_class::template init_rbegin<const_reverse_iterator>();
755 /// Returns a reverse iterator to the element following the last element of the reversed map
757 It corresponds to the element preceding the first element of the non-reversed container.
758 This element acts as a placeholder, attempting to access it results in undefined behavior.
760 reverse_iterator rend()
762 return base_class::template init_rend<reverse_iterator>();
765 /// Returns a const reverse iterator to the element following the last element of the reversed map
767 It corresponds to the element preceding the first element of the non-reversed container.
768 This element acts as a placeholder, attempting to access it results in undefined behavior.
770 const_reverse_iterator rend() const
772 return base_class::template init_rend<const_reverse_iterator>();
775 /// Returns a const reverse iterator to the element following the last element of the reversed map
777 It corresponds to the element preceding the first element of the non-reversed container.
778 This element acts as a placeholder, attempting to access it results in undefined behavior.
780 const_reverse_iterator crend()
782 return base_class::template init_rend<const_reverse_iterator>();
786 }} // namespace cds::container
788 #endif // #ifndef CDSLIB_CONTAINER_FELDMAN_HASHMAP_RCU_H