3 #ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_MAP_RCU_H
6 #include <cds/container/details/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, \p 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 - map traits, default is \p michael_map::traits.
30 Instead of defining \p Traits struct you may use option-based syntax with \p michael_map::make_traits metafunction
32 Many of the class function take a key argument of type \p K that in general is not \p key_type.
33 \p key_type and an argument of template type \p K must meet the following requirements:
34 - \p key_type should be constructible from value of type \p K;
35 - the hash functor should be able to calculate correct hash value from argument \p key of type \p K:
36 <tt> hash( key_type(key) ) == hash( key ) </tt>
37 - values of type \p key_type and \p K should be comparable
41 The tips about how to use Michael's map see \ref cds_nonintrusive_MichaelHashMap_how_touse "MichaelHashMap".
42 Remember, that you should include RCU-related header file (for example, <tt>cds/urcu/general_buffered.h</tt>)
43 before including <tt>cds/container/michael_map_rcu.h</tt>.
48 #ifdef CDS_DOXYGEN_INVOKED
49 class Traits = michael_map::traits
54 class MichaelHashMap< cds::urcu::gc< RCU >, OrderedList, Traits >
57 typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector
58 typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
59 typedef Traits traits; ///< Map traits
61 typedef typename bucket_type::key_type key_type ; ///< key type
62 typedef typename bucket_type::mapped_type mapped_type ; ///< value type
63 typedef typename bucket_type::value_type value_type ; ///< key/value pair stored in the list
64 typedef typename bucket_type::key_comparator key_comparator ; ///< key comparison functor
66 /// Hash functor for \ref key_type and all its derivatives that you use
67 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
68 typedef typename traits::item_counter item_counter; ///< Item counter type
70 /// Bucket table allocator
71 typedef cds::details::Allocator< bucket_type, typename traits::allocator > bucket_table_allocator;
73 typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock
74 typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
75 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
76 static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
79 item_counter m_ItemCounter; ///< Item counter
80 hash m_HashFunctor; ///< Hash functor
81 bucket_type * m_Buckets; ///< bucket table
85 const size_t m_nHashBitmask;
90 /// Calculates hash value of \p key
92 size_t hash_value( Q const& key ) const
94 return m_HashFunctor( key ) & m_nHashBitmask;
97 /// Returns the bucket (ordered list) for \p key
99 bucket_type& bucket( Q const& key )
101 return m_Buckets[ hash_value( key ) ];
103 template <typename Q>
104 bucket_type const& bucket( Q const& key ) const
106 return m_Buckets[ hash_value( key ) ];
112 \p IsConst - constness boolean flag
114 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features:
115 - it has no post-increment operator, only pre-increment
116 - it iterates items in unordered fashion
117 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
118 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
119 deleting operations it is no guarantee that you iterate all item in the map.
121 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
122 for debug purpose only.
124 template <bool IsConst>
125 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
128 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
129 friend class MichaelHashMap;
134 //typedef typename base_class::bucket_type bucket_type;
135 typedef typename base_class::bucket_ptr bucket_ptr;
136 typedef typename base_class::list_iterator list_iterator;
138 //typedef typename bucket_type::key_type key_type;
142 /// Value pointer type (const for const_iterator)
143 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
144 /// Value reference type (const for const_iterator)
145 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
147 /// Key-value pair pointer type (const for const_iterator)
148 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
149 /// Key-value pair reference type (const for const_iterator)
150 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
154 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
155 : base_class( it, pFirst, pLast )
166 iterator_type( const iterator_type& src )
170 /// Dereference operator
171 pair_ptr operator ->() const
173 assert( base_class::m_pCurBucket != nullptr );
174 return base_class::m_itList.operator ->();
177 /// Dereference operator
178 pair_ref operator *() const
180 assert( base_class::m_pCurBucket != nullptr );
181 return base_class::m_itList.operator *();
185 iterator_type& operator ++()
187 base_class::operator++();
191 /// Assignment operator
192 iterator_type& operator = (const iterator_type& src)
194 base_class::operator =(src);
198 /// Returns current bucket (debug function)
199 bucket_ptr bucket() const
201 return base_class::bucket();
204 /// Equality operator
206 bool operator ==(iterator_type<C> const& i )
208 return base_class::operator ==( i );
210 /// Equality operator
212 bool operator !=(iterator_type<C> const& i )
214 return !( *this == i );
220 typedef iterator_type< false > iterator;
222 /// Const forward iterator
223 typedef iterator_type< true > const_iterator;
225 /// Returns a forward iterator addressing the first element in a map
227 For empty map \code begin() == end() \endcode
231 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
234 /// Returns an iterator that addresses the location succeeding the last element in a map
236 Do not use the value returned by <tt>end</tt> function to access any item.
237 The returned value can be used only to control reaching the end of the map.
238 For empty map \code begin() == end() \endcode
242 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
245 /// Returns a forward const iterator addressing the first element in a map
247 const_iterator begin() const
249 return get_const_begin();
251 const_iterator cbegin() const
253 return get_const_begin();
257 /// Returns an const iterator that addresses the location succeeding the last element in a map
259 const_iterator end() const
261 return get_const_end();
263 const_iterator cend() const
265 return get_const_end();
271 const_iterator get_const_begin() const
273 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
275 const_iterator get_const_end() const
277 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
282 /// Initializes the map
283 /** @copydetails cds_nonintrusive_MichaelHashMap_hp_ctor
286 size_t nMaxItemCount, ///< estimation of max item count in the hash map
287 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
288 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
290 // GC and OrderedList::gc must be the same
291 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
293 // atomicity::empty_item_counter is not allowed as a item counter
294 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
295 "cds::atomicity::empty_item_counter is not allowed as a item counter");
297 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
300 /// Clears hash map and destroys it
304 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
307 /// Inserts new node with key and default value
309 The function creates a node with \p key and default value, and then inserts the node created into the map.
312 - The \p key_type should be constructible from value of type \p K.
313 In trivial case, \p K is equal to \ref key_type.
314 - The \p mapped_type should be default-constructible.
316 The function applies RCU lock internally.
318 Returns \p true if inserting successful, \p false otherwise.
320 template <typename K>
321 bool insert( const K& key )
323 const bool bRet = bucket( key ).insert( key );
331 The function creates a node with copy of \p val value
332 and then inserts the node created into the map.
335 - The \p key_type should be constructible from \p key of type \p K.
336 - The \p mapped_type should be constructible from \p val of type \p V.
338 The function applies RCU lock internally.
340 Returns \p true if \p val is inserted into the map, \p false otherwise.
342 template <typename K, typename V>
343 bool insert( K const& key, V const& val )
345 const bool bRet = bucket( key ).insert( key, val );
351 /// Inserts new node and initialize it by a functor
353 This function inserts new node with key \p key and if inserting is successful then it calls
354 \p func functor with signature
357 void operator()( value_type& item );
361 The argument \p item of user-defined functor \p func is the reference
362 to the map's item inserted:
363 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
364 - <tt>item.second</tt> is a reference to item's value that may be changed.
366 The user-defined functor is called only if inserting is successful.
368 The key_type should be constructible from value of type \p K.
370 The function allows to split creating of new item into two part:
371 - create item from \p key;
372 - insert new item into the map;
373 - if inserting is successful, initialize the value of item by calling \p func functor
375 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
376 it is preferable that the initialization should be completed only if inserting is successful.
378 The function applies RCU lock internally.
380 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
381 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
384 template <typename K, typename Func>
385 bool insert_key( const K& key, Func func )
387 const bool bRet = bucket( key ).insert_key( key, func );
394 /// Ensures that the \p key exists in the map
396 The operation performs inserting or changing data with lock-free manner.
398 If the \p key not found in the map, then the new item created from \p key
399 is inserted into the map (note that in this case the \ref key_type should be
400 constructible from type \p K).
401 Otherwise, the functor \p func is called with item found.
402 The functor \p Func may be a function with signature:
404 void func( bool bNew, value_type& item );
409 void operator()( bool bNew, value_type& item );
414 - \p bNew - \p true if the item has been inserted, \p false otherwise
415 - \p item - item of the list
417 The functor may change any fields of the \p item.second that is \ref mapped_type.
419 The function applies RCU lock internally.
421 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
422 \p second is true if new item has been added or \p false if the item with \p key
423 already is in the list.
425 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
426 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
429 template <typename K, typename Func>
430 std::pair<bool, bool> ensure( K const& key, Func func )
432 std::pair<bool, bool> bRet = bucket( key ).ensure( key, func );
433 if ( bRet.first && bRet.second )
438 /// For key \p key inserts data of type \p mapped_type created from \p args
440 \p key_type should be constructible from type \p K
442 Returns \p true if inserting successful, \p false otherwise.
444 template <typename K, typename... Args>
445 bool emplace( K&& key, Args&&... args )
447 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
453 /// Deletes \p key from the map
454 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_val
456 RCU \p synchronize method can be called. RCU should not be locked.
458 Return \p true if \p key is found and deleted, \p false otherwise
460 template <typename K>
461 bool erase( const K& key )
463 const bool bRet = bucket( key ).erase( key );
469 /// Deletes the item from the map using \p pred predicate for searching
471 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_val "erase(K const&)"
472 but \p pred is used for key comparing.
473 \p Less predicate has the interface like \p std::less.
474 \p Less must imply the same element order as the comparator used for building the map.
476 template <typename K, typename Less>
477 bool erase_with( const K& key, Less pred )
479 const bool bRet = bucket( key ).erase_with( key, pred );
485 /// Deletes \p key from the map
486 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_func
488 The function searches an item with key \p key, calls \p f functor
489 and deletes the item. If \p key is not found, the functor is not called.
491 The functor \p Func interface:
494 void operator()(value_type& item) { ... }
497 The functor may be passed by reference using <tt>boost:ref</tt>
499 RCU \p synchronize method can be called. RCU should not be locked.
501 Return \p true if key is found and deleted, \p false otherwise
503 template <typename K, typename Func>
504 bool erase( const K& key, Func f )
506 const bool bRet = bucket( key ).erase( key, f );
512 /// Deletes the item from the map using \p pred predicate for searching
514 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_func "erase(K const&, Func)"
515 but \p pred is used for key comparing.
516 \p Less functor has the interface like \p std::less.
517 \p Less must imply the same element order as the comparator used for building the map.
519 template <typename K, typename Less, typename Func>
520 bool erase_with( const K& key, Less pred, Func f )
522 const bool bRet = bucket( key ).erase_with( key, pred, f );
528 /// Extracts an item from the map
529 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract
530 The function searches an item with key equal to \p key,
531 unlinks it from the map, places item pointer into \p dest argument, and returns \p true.
532 If the item is not found the function return \p false.
534 @note The function does NOT call RCU read-side lock or synchronization,
535 and does NOT dispose the item found. It just excludes the item from the map
536 and returns a pointer to item found.
537 You should lock RCU before calling of the function, and you should synchronize RCU
538 outside the RCU lock to free extracted item
541 #include <cds/urcu/general_buffered.h>
542 #include <cds/container/michael_kvlist_rcu.h>
543 #include <cds/container/michael_map_rcu.h>
545 typedef cds::urcu::gc< general_buffered<> > rcu;
546 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
547 typedef cds::container::MichaelHashMap< rcu, rcu_michael_list, foo_traits > rcu_michael_map;
549 rcu_michael_map theMap;
552 rcu_michael_map::exempt_ptr p;
554 // first, we should lock RCU
555 rcu_michael_map::rcu_lock lock;
557 // Now, you can apply extract function
558 // Note that you must not delete the item found inside the RCU lock
559 if ( theMap.extract( p, 10 )) {
560 // do something with p
565 // We may safely release p here
566 // release() passes the pointer to RCU reclamation cycle
570 template <typename K>
571 bool extract( exempt_ptr& dest, K const& key )
573 if ( bucket( key ).extract( dest, key )) {
580 /// Extracts an item from the map using \p pred predicate for searching
582 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_extract "extract(exempt_ptr&, K const&)"
583 but \p pred is used for key comparing.
584 \p Less functor has the interface like \p std::less.
585 \p pred must imply the same element order as the comparator used for building the map.
587 template <typename K, typename Less>
588 bool extract_with( exempt_ptr& dest, K const& key, Less pred )
590 if ( bucket( key ).extract_with( dest, key, pred )) {
597 /// Finds the key \p key
598 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_cfunc
600 The function searches the item with key equal to \p key and calls the functor \p f for item found.
601 The interface of \p Func functor is:
604 void operator()( value_type& item );
607 where \p item is the item found.
609 The functor may change \p item.second. Note that the functor is only guarantee
610 that \p item cannot be disposed during functor is executing.
611 The functor does not serialize simultaneous access to the map's \p item. If such access is
612 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
614 The function applies RCU lock internally.
616 The function returns \p true if \p key is found, \p false otherwise.
618 template <typename K, typename Func>
619 bool find( K const& key, Func f ) const
621 return bucket( key ).find( key, f );
624 /// Finds the key \p val using \p pred predicate for searching
626 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_cfunc "find(K const&, Func)"
627 but \p pred is used for key comparing.
628 \p Less functor has the interface like \p std::less.
629 \p Less must imply the same element order as the comparator used for building the map.
631 template <typename K, typename Less, typename Func>
632 bool find_with( K const& key, Less pred, Func f ) const
634 return bucket( key ).find_with( key, pred, f );
637 /// Finds the key \p key
638 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_val
640 The function searches the item with key equal to \p key
641 and returns \p true if it is found, and \p false otherwise.
643 The function applies RCU lock internally.
645 template <typename K>
646 bool find( K const& key ) const
648 return bucket( key ).find( key );
651 /// Finds the key \p val using \p pred predicate for searching
653 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_val "find(K const&)"
654 but \p pred is used for key comparing.
655 \p Less functor has the interface like \p std::less.
656 \p Less must imply the same element order as the comparator used for building the map.
658 template <typename K, typename Less>
659 bool find_with( K const& key, Less pred ) const
661 return bucket( key ).find_with( key, pred );
664 /// Finds \p key and return the item found
665 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
666 The function searches the item with key equal to \p key and returns the pointer to item found.
667 If \p key is not found it returns \p nullptr.
669 Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
671 RCU should be locked before call of this function.
672 Returned item is valid only while RCU is locked:
674 typedef cds::container::MichaelHashMap< your_template_parameters > hash_map;
679 hash_map::rcu_lock lock;
681 hash_map::value_type * = theMap.get( 5 );
686 // Unlock RCU by rcu_lock destructor
687 // pVal can be freed at any time after RCU has been unlocked
691 template <typename K>
692 value_type * get( K const& key ) const
694 return bucket( key ).get( key );
697 /// Finds \p key and return the item found
699 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_get "get(K const&)"
700 but \p pred is used for comparing the keys.
702 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
704 \p pred must imply the same element order as the comparator used for building the map.
706 template <typename K, typename Less>
707 value_type * get_with( K const& key, Less pred ) const
709 return bucket( key ).get_with( key, pred );
712 /// Clears the map (not atomic)
714 The function erases all items from the map.
716 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
717 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
718 <tt> empty() </tt> may return \p true but the map may contain item(s).
719 Therefore, \p clear may be used only for debugging purposes.
721 RCU \p synchronize method can be called. RCU should not be locked.
725 for ( size_t i = 0; i < bucket_count(); ++i )
726 m_Buckets[i].clear();
727 m_ItemCounter.reset();
730 /// Checks if the map is empty
732 Emptiness is checked by item counting: if item count is zero then the map is empty.
733 Thus, the correct item counting is an important part of the map implementation.
740 /// Returns item count in the map
743 return m_ItemCounter;
746 /// Returns the size of hash table
748 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
749 the value returned is an constant depending on object initialization parameters;
750 see \p MichaelHashMap::MichaelHashMap for explanation.
752 size_t bucket_count() const
754 return m_nHashBitmask + 1;
757 }} // namespace cds::container
759 #endif // ifndef __CDS_CONTAINER_MICHAEL_MAP_RCU_H