3 #ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_MAP_RCU_H
6 #include <cds/container/michael_map_base.h>
7 #include <cds/details/allocator.h>
9 namespace cds { namespace container {
11 /// Michael's hash map (template specialization for \ref cds_urcu_desc "RCU")
12 /** @ingroup cds_nonintrusive_map
13 \anchor cds_nonintrusive_MichaelHashMap_rcu
16 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
18 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
19 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
20 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
21 However, each bucket may contain unbounded number of items.
23 Template parameters are:
24 - \p RCU - one of \ref cds_urcu_gc "RCU type"
25 - \p OrderedList - ordered key-value list implementation used as bucket for hash map, for example, MichaelKVList.
26 The ordered list implementation specifies the \p Key and \p Value types stored in the hash-map, the reclamation
27 schema \p GC used by hash-map, the comparison functor for the type \p Key and other features specific for
29 - \p Traits - type traits. See michael_map::type_traits for explanation.
31 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction
32 (this metafunction is a synonym for michael_set::make_traits).
33 For \p michael_map::make_traits the following option may be used:
34 - opt::hash - mandatory option, specifies hash functor.
35 - opt::item_counter - optional, specifies item counting policy. See michael_map::type_traits for explanation.
36 - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
38 Many of the class function take a key argument of type \p K that in general is not \ref key_type.
39 \p key_type and an argument of template type \p K must meet the following requirements:
40 - \p key_type should be constructible from value of type \p K;
41 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
42 <tt> hash( key_type(key) ) == hash( key ) </tt>
43 - values of type \p key_type and \p K should be comparable
47 The tips about how to use Michael's map see \ref cds_nonintrusive_MichaelHashMap_how_touse "MichaelHashMap".
48 Remember, that you should include RCU-related header file (for example, <tt>cds/urcu/general_buffered.h</tt>)
49 before including <tt>cds/container/michael_map_rcu.h</tt>.
54 #ifdef CDS_DOXYGEN_INVOKED
55 class Traits = michael_map::type_traits
60 class MichaelHashMap< cds::urcu::gc< RCU >, OrderedList, Traits >
63 typedef OrderedList bucket_type ; ///< type of ordered list used as a bucket implementation
64 typedef Traits options ; ///< Traits template parameters
66 typedef typename bucket_type::key_type key_type ; ///< key type
67 typedef typename bucket_type::mapped_type mapped_type ; ///< value type
68 typedef typename bucket_type::value_type value_type ; ///< key/value pair stored in the list
70 typedef cds::urcu::gc< RCU > gc ; ///< RCU used as garbage collector
71 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
73 /// Hash functor for \ref key_type and all its derivatives that you use
74 typedef typename cds::opt::v::hash_selector< typename options::hash >::type hash;
75 typedef typename options::item_counter item_counter ; ///< Item counter type
77 /// Bucket table allocator
78 typedef cds::details::Allocator< bucket_type, typename options::allocator > bucket_table_allocator;
80 typedef typename bucket_type::rcu_lock rcu_lock ; ///< RCU scoped lock
81 typedef typename bucket_type::exempt_ptr exempt_ptr ; ///< pointer to extracted node
82 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
83 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
86 item_counter m_ItemCounter ; ///< Item counter
87 hash m_HashFunctor ; ///< Hash functor
89 bucket_type * m_Buckets ; ///< bucket table
93 const size_t m_nHashBitmask;
97 /// Calculates hash value of \p key
99 size_t hash_value( Q const& key ) const
101 return m_HashFunctor( key ) & m_nHashBitmask;
104 /// Returns the bucket (ordered list) for \p key
106 template <typename Q>
107 bucket_type& bucket( Q const& key )
109 return m_Buckets[ hash_value( key ) ];
111 template <typename Q>
112 bucket_type const& bucket( Q const& key ) const
114 return m_Buckets[ hash_value( key ) ];
120 \p IsConst - constness boolean flag
122 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features:
123 - it has no post-increment operator, only pre-increment
124 - it iterates items in unordered fashion
125 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
126 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
127 deleting operations it is no guarantee that you iterate all item in the map.
129 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
130 for debug purpose only.
132 template <bool IsConst>
133 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
136 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
137 friend class MichaelHashMap;
142 //typedef typename base_class::bucket_type bucket_type;
143 typedef typename base_class::bucket_ptr bucket_ptr;
144 typedef typename base_class::list_iterator list_iterator;
146 //typedef typename bucket_type::key_type key_type;
150 /// Value pointer type (const for const_iterator)
151 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
152 /// Value reference type (const for const_iterator)
153 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
155 /// Key-value pair pointer type (const for const_iterator)
156 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
157 /// Key-value pair reference type (const for const_iterator)
158 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
162 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
163 : base_class( it, pFirst, pLast )
174 iterator_type( const iterator_type& src )
178 /// Dereference operator
179 pair_ptr operator ->() const
181 assert( base_class::m_pCurBucket != nullptr );
182 return base_class::m_itList.operator ->();
185 /// Dereference operator
186 pair_ref operator *() const
188 assert( base_class::m_pCurBucket != nullptr );
189 return base_class::m_itList.operator *();
193 iterator_type& operator ++()
195 base_class::operator++();
199 /// Assignment operator
200 iterator_type& operator = (const iterator_type& src)
202 base_class::operator =(src);
206 /// Returns current bucket (debug function)
207 bucket_ptr bucket() const
209 return base_class::bucket();
212 /// Equality operator
214 bool operator ==(iterator_type<C> const& i )
216 return base_class::operator ==( i );
218 /// Equality operator
220 bool operator !=(iterator_type<C> const& i )
222 return !( *this == i );
228 typedef iterator_type< false > iterator;
230 /// Const forward iterator
231 typedef iterator_type< true > const_iterator;
233 /// Returns a forward iterator addressing the first element in a map
235 For empty map \code begin() == end() \endcode
239 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
242 /// Returns an iterator that addresses the location succeeding the last element in a map
244 Do not use the value returned by <tt>end</tt> function to access any item.
245 The returned value can be used only to control reaching the end of the map.
246 For empty map \code begin() == end() \endcode
250 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
253 /// Returns a forward const iterator addressing the first element in a map
255 const_iterator begin() const
257 return get_const_begin();
259 const_iterator cbegin()
261 return get_const_begin();
265 /// Returns an const iterator that addresses the location succeeding the last element in a map
267 const_iterator end() const
269 return get_const_end();
271 const_iterator cend()
273 return get_const_end();
279 const_iterator get_const_begin() const
281 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
283 const_iterator get_const_end() const
285 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
290 /// Initializes the map
292 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
293 when you create an object.
294 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
295 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
296 Note, that many popular STL hash map implementation uses load factor 1.
298 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
301 size_t nMaxItemCount, ///< estimation of max item count in the hash map
302 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
303 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
305 // GC and OrderedList::gc must be the same
306 static_assert(( std::is_same<gc, typename bucket_type::gc>::value ), "GC and OrderedList::gc must be the same");
308 // atomicity::empty_item_counter is not allowed as a item counter
309 static_assert(( !std::is_same<item_counter, atomicity::empty_item_counter>::value ), "atomicity::empty_item_counter is not allowed as a item counter");
311 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
314 /// Clears hash map and destroys it
318 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
321 /// Inserts new node with key and default value
323 The function creates a node with \p key and default value, and then inserts the node created into the map.
326 - The \ref key_type should be constructible from value of type \p K.
327 In trivial case, \p K is equal to \ref key_type.
328 - The \ref mapped_type should be default-constructible.
330 The function applies RCU lock internally.
332 Returns \p true if inserting successful, \p false otherwise.
334 template <typename K>
335 bool insert( const K& key )
337 const bool bRet = bucket( key ).insert( key );
345 The function creates a node with copy of \p val value
346 and then inserts the node created into the map.
349 - The \ref key_type should be constructible from \p key of type \p K.
350 - The \ref mapped_type should be constructible from \p val of type \p V.
352 The function applies RCU lock internally.
354 Returns \p true if \p val is inserted into the map, \p false otherwise.
356 template <typename K, typename V>
357 bool insert( K const& key, V const& val )
359 const bool bRet = bucket( key ).insert( key, val );
365 /// Inserts new node and initialize it by a functor
367 This function inserts new node with key \p key and if inserting is successful then it calls
368 \p func functor with signature
371 void operator()( value_type& item );
375 The argument \p item of user-defined functor \p func is the reference
376 to the map's item inserted:
377 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
378 - <tt>item.second</tt> is a reference to item's value that may be changed.
380 User-defined functor \p func should guarantee that during changing item's value no any other changes
381 could be made on this map's item by concurrent threads.
382 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
383 and it is called only if inserting is successful.
385 The key_type should be constructible from value of type \p K.
387 The function allows to split creating of new item into two part:
388 - create item from \p key;
389 - insert new item into the map;
390 - if inserting is successful, initialize the value of item by calling \p func functor
392 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
393 it is preferable that the initialization should be completed only if inserting is successful.
395 The function applies RCU lock internally.
397 template <typename K, typename Func>
398 bool insert_key( const K& key, Func func )
400 const bool bRet = bucket( key ).insert_key( key, func );
407 /// Ensures that the \p key exists in the map
409 The operation performs inserting or changing data with lock-free manner.
411 If the \p key not found in the map, then the new item created from \p key
412 is inserted into the map (note that in this case the \ref key_type should be
413 constructible from type \p K).
414 Otherwise, the functor \p func is called with item found.
415 The functor \p Func may be a function with signature:
417 void func( bool bNew, value_type& item );
422 void operator()( bool bNew, value_type& item );
427 - \p bNew - \p true if the item has been inserted, \p false otherwise
428 - \p item - item of the list
430 The functor may change any fields of the \p item.second that is \ref mapped_type;
431 however, \p func must guarantee that during changing no any other modifications
432 could be made on this item by concurrent threads.
434 You may pass \p func argument by reference using <tt>boost::ref</tt>.
436 The function applies RCU lock internally.
438 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
439 \p second is true if new item has been added or \p false if the item with \p key
440 already is in the list.
442 template <typename K, typename Func>
443 std::pair<bool, bool> ensure( K const& key, Func func )
445 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
446 if ( bRet.first && bRet.second )
451 # ifdef CDS_EMPLACE_SUPPORT
452 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
454 \p key_type should be constructible from type \p K
456 Returns \p true if inserting successful, \p false otherwise.
458 The function applies RCU lock internally.
460 @note This function is available only for compiler that supports
461 variadic template and move semantics
463 template <typename K, typename... Args>
464 bool emplace( K&& key, Args&&... args )
466 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
473 /// Deletes \p key from the map
474 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_val
476 RCU \p synchronize method can be called. RCU should not be locked.
478 Return \p true if \p key is found and deleted, \p false otherwise
480 template <typename K>
481 bool erase( const K& key )
483 const bool bRet = bucket( key ).erase( key );
489 /// Deletes the item from the map using \p pred predicate for searching
491 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_val "erase(K const&)"
492 but \p pred is used for key comparing.
493 \p Less predicate has the interface like \p std::less.
494 \p Less must imply the same element order as the comparator used for building the map.
496 template <typename K, typename Less>
497 bool erase_with( const K& key, Less pred )
499 const bool bRet = bucket( key ).erase_with( key, pred );
505 /// Deletes \p key from the map
506 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_func
508 The function searches an item with key \p key, calls \p f functor
509 and deletes the item. If \p key is not found, the functor is not called.
511 The functor \p Func interface:
514 void operator()(value_type& item) { ... }
517 The functor may be passed by reference using <tt>boost:ref</tt>
519 RCU \p synchronize method can be called. RCU should not be locked.
521 Return \p true if key is found and deleted, \p false otherwise
523 template <typename K, typename Func>
524 bool erase( const K& key, Func f )
526 const bool bRet = bucket( key ).erase( key, f );
532 /// Deletes the item from the map using \p pred predicate for searching
534 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_func "erase(K const&, Func)"
535 but \p pred is used for key comparing.
536 \p Less functor has the interface like \p std::less.
537 \p Less must imply the same element order as the comparator used for building the map.
539 template <typename K, typename Less, typename Func>
540 bool erase_with( const K& key, Less pred, Func f )
542 const bool bRet = bucket( key ).erase_with( key, pred, f );
548 /// Extracts an item from the map
549 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract
550 The function searches an item with key equal to \p key,
551 unlinks it from the map, places item pointer into \p dest argument, and returns \p true.
552 If the item is not found the function return \p false.
554 @note The function does NOT call RCU read-side lock or synchronization,
555 and does NOT dispose the item found. It just excludes the item from the map
556 and returns a pointer to item found.
557 You should lock RCU before calling of the function, and you should synchronize RCU
558 outside the RCU lock to free extracted item
561 #include <cds/urcu/general_buffered.h>
562 #include <cds/container/michael_kvlist_rcu.h>
563 #include <cds/container/michael_map_rcu.h>
565 typedef cds::urcu::gc< general_buffered<> > rcu;
566 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
567 typedef cds::container::MichaelHashMap< rcu, rcu_michael_list, foo_traits > rcu_michael_map;
569 rcu_michael_map theMap;
572 rcu_michael_map::exempt_ptr p;
574 // first, we should lock RCU
575 rcu_michael_map::rcu_lock lock;
577 // Now, you can apply extract function
578 // Note that you must not delete the item found inside the RCU lock
579 if ( theMap.extract( p, 10 )) {
580 // do something with p
585 // We may safely release p here
586 // release() passes the pointer to RCU reclamation cycle
590 template <typename K>
591 bool extract( exempt_ptr& dest, K const& key )
593 if ( bucket( key ).extract( dest, key )) {
600 /// Extracts an item from the map using \p pred predicate for searching
602 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_extract "extract(exempt_ptr&, K const&)"
603 but \p pred is used for key comparing.
604 \p Less functor has the interface like \p std::less.
605 \p pred must imply the same element order as the comparator used for building the map.
607 template <typename K, typename Less>
608 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
610 if ( bucket( key ).extract_with( dest, key, pred )) {
617 /// Finds the key \p key
618 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_cfunc
620 The function searches the item with key equal to \p key and calls the functor \p f for item found.
621 The interface of \p Func functor is:
624 void operator()( value_type& item );
627 where \p item is the item found.
629 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
631 The functor may change \p item.second. Note that the functor is only guarantee
632 that \p item cannot be disposed during functor is executing.
633 The functor does not serialize simultaneous access to the map's \p item. If such access is
634 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
636 The function applies RCU lock internally.
638 The function returns \p true if \p key is found, \p false otherwise.
640 template <typename K, typename Func>
641 bool find( K const& key, Func f ) const
643 return bucket( key ).find( key, f );
646 /// Finds the key \p val using \p pred predicate for searching
648 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_cfunc "find(K const&, Func)"
649 but \p pred is used for key comparing.
650 \p Less functor has the interface like \p std::less.
651 \p Less must imply the same element order as the comparator used for building the map.
653 template <typename K, typename Less, typename Func>
654 bool find_with( K const& key, Less pred, Func f ) const
656 return bucket( key ).find_with( key, pred, f );
659 /// Finds the key \p key
660 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_val
662 The function searches the item with key equal to \p key
663 and returns \p true if it is found, and \p false otherwise.
665 The function applies RCU lock internally.
667 template <typename K>
668 bool find( K const& key ) const
670 return bucket( key ).find( key );
673 /// Finds the key \p val using \p pred predicate for searching
675 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)"
676 but \p pred is used for key comparing.
677 \p Less functor has the interface like \p std::less.
678 \p Less must imply the same element order as the comparator used for building the map.
680 template <typename K, typename Less>
681 bool find_with( K const& key, Less pred ) const
683 return bucket( key ).find_with( key, pred );
686 /// Finds \p key and return the item found
687 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
688 The function searches the item with key equal to \p key and returns the pointer to item found.
689 If \p key is not found it returns \p nullptr.
691 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
693 RCU should be locked before call of this function.
694 Returned item is valid only while RCU is locked:
696 typedef cds::container::MichaelHashMap< your_template_parameters > hash_map;
701 hash_map::rcu_lock lock;
703 hash_map::value_type * = theMap.get( 5 );
708 // Unlock RCU by rcu_lock destructor
709 // pVal can be freed at any time after RCU has been unlocked
713 template <typename K>
714 value_type * get( K const& key ) const
716 return bucket( key ).get( key );
719 /// Finds \p key and return the item found
721 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_get "get(K const&)"
722 but \p pred is used for comparing the keys.
724 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
726 \p pred must imply the same element order as the comparator used for building the map.
728 template <typename K, typename Less>
729 value_type * get_with( K const& key, Less pred ) const
731 return bucket( key ).get_with( key, pred );
734 /// Clears the map (non-atomic)
736 The function erases all items from the map.
738 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
739 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
740 <tt> empty() </tt> may return \p true but the map may contain item(s).
741 Therefore, \p clear may be used only for debugging purposes.
743 RCU \p synchronize method can be called. RCU should not be locked.
747 for ( size_t i = 0; i < bucket_count(); ++i )
748 m_Buckets[i].clear();
749 m_ItemCounter.reset();
752 /// Checks if the map is empty
754 Emptiness is checked by item counting: if item count is zero then the map is empty.
755 Thus, the correct item counting is an important part of the map implementation.
762 /// Returns item count in the map
765 return m_ItemCounter;
768 /// Returns the size of hash table
770 Since MichaelHashMap cannot dynamically extend the hash table size,
771 the value returned is an constant depending on object initialization parameters;
772 see MichaelHashMap::MichaelHashMap for explanation.
774 size_t bucket_count() const
776 return m_nHashBitmask + 1;
779 }} // namespace cds::container
781 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H