3 #ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H
4 #define CDSLIB_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;
77 /// Type of \p get() member function return value
78 typedef typename bucket_type::raw_ptr raw_ptr;
81 item_counter m_ItemCounter; ///< Item counter
82 hash m_HashFunctor; ///< Hash functor
83 bucket_type * m_Buckets; ///< bucket table
87 const size_t m_nHashBitmask;
92 /// Calculates hash value of \p key
94 size_t hash_value( Q const& key ) const
96 return m_HashFunctor( key ) & m_nHashBitmask;
99 /// Returns the bucket (ordered list) for \p key
100 template <typename Q>
101 bucket_type& bucket( Q const& key )
103 return m_Buckets[ hash_value( key ) ];
105 template <typename Q>
106 bucket_type const& bucket( Q const& key ) const
108 return m_Buckets[ hash_value( key ) ];
114 \p IsConst - constness boolean flag
116 The forward iterator for Michael's map is based on \p OrderedList forward iterator and has the following features:
117 - it has no post-increment operator, only pre-increment
118 - it iterates items in unordered fashion
119 - The iterator cannot be moved across thread boundary since it may contain GC's guard that is thread-private GC data.
120 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
121 deleting operations it is no guarantee that you iterate all item in the map.
123 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator for the concurrent container
124 for debug purpose only.
126 template <bool IsConst>
127 class iterator_type: private cds::intrusive::michael_set::details::iterator< bucket_type, IsConst >
130 typedef cds::intrusive::michael_set::details::iterator< bucket_type, IsConst > base_class;
131 friend class MichaelHashMap;
136 //typedef typename base_class::bucket_type bucket_type;
137 typedef typename base_class::bucket_ptr bucket_ptr;
138 typedef typename base_class::list_iterator list_iterator;
140 //typedef typename bucket_type::key_type key_type;
144 /// Value pointer type (const for const_iterator)
145 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::pointer value_ptr;
146 /// Value reference type (const for const_iterator)
147 typedef typename cds::details::make_const_type<typename MichaelHashMap::mapped_type, IsConst>::reference value_ref;
149 /// Key-value pair pointer type (const for const_iterator)
150 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::pointer pair_ptr;
151 /// Key-value pair reference type (const for const_iterator)
152 typedef typename cds::details::make_const_type<typename MichaelHashMap::value_type, IsConst>::reference pair_ref;
156 iterator_type( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
157 : base_class( it, pFirst, pLast )
168 iterator_type( const iterator_type& src )
172 /// Dereference operator
173 pair_ptr operator ->() const
175 assert( base_class::m_pCurBucket != nullptr );
176 return base_class::m_itList.operator ->();
179 /// Dereference operator
180 pair_ref operator *() const
182 assert( base_class::m_pCurBucket != nullptr );
183 return base_class::m_itList.operator *();
187 iterator_type& operator ++()
189 base_class::operator++();
193 /// Assignment operator
194 iterator_type& operator = (const iterator_type& src)
196 base_class::operator =(src);
200 /// Returns current bucket (debug function)
201 bucket_ptr bucket() const
203 return base_class::bucket();
206 /// Equality operator
208 bool operator ==(iterator_type<C> const& i )
210 return base_class::operator ==( i );
212 /// Equality operator
214 bool operator !=(iterator_type<C> const& i )
216 return !( *this == i );
222 typedef iterator_type< false > iterator;
224 /// Const forward iterator
225 typedef iterator_type< true > const_iterator;
227 /// Returns a forward iterator addressing the first element in a map
229 For empty map \code begin() == end() \endcode
233 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
236 /// Returns an iterator that addresses the location succeeding the last element in a map
238 Do not use the value returned by <tt>end</tt> function to access any item.
239 The returned value can be used only to control reaching the end of the map.
240 For empty map \code begin() == end() \endcode
244 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
247 /// Returns a forward const iterator addressing the first element in a map
249 const_iterator begin() const
251 return get_const_begin();
253 const_iterator cbegin() const
255 return get_const_begin();
259 /// Returns an const iterator that addresses the location succeeding the last element in a map
261 const_iterator end() const
263 return get_const_end();
265 const_iterator cend() const
267 return get_const_end();
273 const_iterator get_const_begin() const
275 return const_iterator( const_cast<bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
277 const_iterator get_const_end() const
279 return const_iterator( const_cast<bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
284 /// Initializes the map
286 The Michael's hash map is non-expandable container. You should point the average count of items \p nMaxItemCount
287 when you create an object.
288 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
289 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
290 Note, that many popular STL hash map implementation uses load factor 1.
292 The ctor defines hash table size as rounding <tt>nMacItemCount / nLoadFactor</tt> up to nearest power of two.
295 size_t nMaxItemCount, ///< estimation of max item count in the hash map
296 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
297 ) : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
299 // GC and OrderedList::gc must be the same
300 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
302 // atomicity::empty_item_counter is not allowed as a item counter
303 static_assert( !std::is_same<item_counter, cds::atomicity::empty_item_counter>::value,
304 "cds::atomicity::empty_item_counter is not allowed as a item counter");
306 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
309 /// Clears hash map and destroys it
313 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
316 /// Inserts new node with key and default value
318 The function creates a node with \p key and default value, and then inserts the node created into the map.
321 - The \p key_type should be constructible from value of type \p K.
322 In trivial case, \p K is equal to \ref key_type.
323 - The \p mapped_type should be default-constructible.
325 The function applies RCU lock internally.
327 Returns \p true if inserting successful, \p false otherwise.
329 template <typename K>
330 bool insert( const K& key )
332 const bool bRet = bucket( key ).insert( key );
340 The function creates a node with copy of \p val value
341 and then inserts the node created into the map.
344 - The \p key_type should be constructible from \p key of type \p K.
345 - The \p mapped_type should be constructible from \p val of type \p V.
347 The function applies RCU lock internally.
349 Returns \p true if \p val is inserted into the map, \p false otherwise.
351 template <typename K, typename V>
352 bool insert( K const& key, V const& val )
354 const bool bRet = bucket( key ).insert( key, val );
360 /// Inserts new node and initialize it by a functor
362 This function inserts new node with key \p key and if inserting is successful then it calls
363 \p func functor with signature
366 void operator()( value_type& item );
370 The argument \p item of user-defined functor \p func is the reference
371 to the map's item inserted:
372 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
373 - <tt>item.second</tt> is a reference to item's value that may be changed.
375 The user-defined functor is called only if inserting is successful.
377 The key_type should be constructible from value of type \p K.
379 The function allows to split creating of new item into two part:
380 - create item from \p key;
381 - insert new item into the map;
382 - if inserting is successful, initialize the value of item by calling \p func functor
384 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
385 it is preferable that the initialization should be completed only if inserting is successful.
387 The function applies RCU lock internally.
389 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
390 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
393 template <typename K, typename Func>
394 bool insert_with( const K& key, Func func )
396 const bool bRet = bucket( key ).insert_with( key, func );
402 /// Updates data by \p key
404 The operation performs inserting or replacing the element with lock-free manner.
406 If the \p key not found in the map, then the new item created from \p key
407 will be inserted into the map iff \p bAllowInsert is \p true.
408 (note that in this case the \ref key_type should be constructible from type \p K).
409 Otherwise, if \p key is found, the functor \p func is called with item found.
411 The functor \p Func signature is:
414 void operator()( bool bNew, value_type& item );
418 - \p bNew - \p true if the item has been inserted, \p false otherwise
419 - \p item - the item found or inserted
421 The functor may change any fields of the \p item.second that is \p mapped_type.
423 The function applies RCU lock internally.
425 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
426 \p second is true if new item has been added or \p false if the item with \p key
429 @warning For \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
430 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" provides exclusive access to inserted item and does not require any node-level
433 template <typename K, typename Func>
434 std::pair<bool, bool> update( K const& key, Func func, bool bAllowInsert = true )
436 std::pair<bool, bool> bRet = bucket( key ).update( key, func, bAllowInsert );
442 template <typename K, typename Func>
443 CDS_DEPRECATED("ensure() is deprecated, use update()")
444 std::pair<bool, bool> ensure( K const& key, Func func )
446 return update( key, func, true );
450 /// For key \p key inserts data of type \p mapped_type created from \p args
452 \p key_type should be constructible from type \p K
454 Returns \p true if inserting successful, \p false otherwise.
456 template <typename K, typename... Args>
457 bool emplace( K&& key, Args&&... args )
459 const bool bRet = bucket( key ).emplace( std::forward<K>(key), std::forward<Args>(args)... );
465 /// Deletes \p key from the map
466 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_val
468 RCU \p synchronize method can be called. RCU should not be locked.
470 Return \p true if \p key is found and deleted, \p false otherwise
472 template <typename K>
473 bool erase( const K& key )
475 const bool bRet = bucket( key ).erase( key );
481 /// Deletes the item from the map using \p pred predicate for searching
483 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_val "erase(K const&)"
484 but \p pred is used for key comparing.
485 \p Less predicate has the interface like \p std::less.
486 \p Less must imply the same element order as the comparator used for building the map.
488 template <typename K, typename Less>
489 bool erase_with( const K& key, Less pred )
491 const bool bRet = bucket( key ).erase_with( key, pred );
497 /// Deletes \p key from the map
498 /** \anchor cds_nonintrusive_MichaelMap_rcu_erase_func
500 The function searches an item with key \p key, calls \p f functor
501 and deletes the item. If \p key is not found, the functor is not called.
503 The functor \p Func interface:
506 void operator()(value_type& item) { ... }
510 RCU \p synchronize method can be called. RCU should not be locked.
512 Return \p true if key is found and deleted, \p false otherwise
514 template <typename K, typename Func>
515 bool erase( const K& key, Func f )
517 const bool bRet = bucket( key ).erase( key, f );
523 /// Deletes the item from the map using \p pred predicate for searching
525 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_erase_func "erase(K const&, Func)"
526 but \p pred is used for key comparing.
527 \p Less functor has the interface like \p std::less.
528 \p Less must imply the same element order as the comparator used for building the map.
530 template <typename K, typename Less, typename Func>
531 bool erase_with( const K& key, Less pred, Func f )
533 const bool bRet = bucket( key ).erase_with( key, pred, f );
539 /// Extracts an item from the map
540 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_extract
541 The function searches an item with key equal to \p key,
542 unlinks it from the map, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
543 If the item is not found the function return an empty \p exempt_ptr.
545 The function just excludes the key from the map and returns a pointer to item found.
546 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
547 - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
548 - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
549 See ordered list implementation for details.
552 #include <cds/urcu/general_buffered.h>
553 #include <cds/container/michael_kvlist_rcu.h>
554 #include <cds/container/michael_map_rcu.h>
556 typedef cds::urcu::gc< general_buffered<> > rcu;
557 typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
558 typedef cds::container::MichaelHashMap< rcu, rcu_michael_list, foo_traits > rcu_michael_map;
560 rcu_michael_map theMap;
563 rcu_michael_map::exempt_ptr p;
565 // For MichaelList we should not lock RCU
567 // Note that you must not delete the item found inside the RCU lock
568 p = theMap.extract( 10 );
570 // do something with p
574 // We may safely release p here
575 // release() passes the pointer to RCU reclamation cycle
579 template <typename K>
580 exempt_ptr extract( K const& key )
582 exempt_ptr p = bucket( key ).extract( key );
588 /// Extracts an item from the map using \p pred predicate for searching
590 The function is an analog of \p extract(K const&) but \p pred is used for key comparing.
591 \p Less functor has the interface like \p std::less.
592 \p pred must imply the same element order as the comparator used for building the map.
594 template <typename K, typename Less>
595 exempt_ptr extract_with( K const& key, Less pred )
597 exempt_ptr p = bucket( key ).extract_with( key, pred );
603 /// Finds the key \p key
604 /** \anchor cds_nonintrusive_MichaelMap_rcu_find_cfunc
606 The function searches the item with key equal to \p key and calls the functor \p f for item found.
607 The interface of \p Func functor is:
610 void operator()( value_type& item );
613 where \p item is the item found.
615 The functor may change \p item.second. Note that the functor is only guarantee
616 that \p item cannot be disposed during functor is executing.
617 The functor does not serialize simultaneous access to the map's \p item. If such access is
618 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
620 The function applies RCU lock internally.
622 The function returns \p true if \p key is found, \p false otherwise.
624 template <typename K, typename Func>
625 bool find( K const& key, Func f )
627 return bucket( key ).find( key, f );
630 /// Finds the key \p val using \p pred predicate for searching
632 The function is an analog of \ref cds_nonintrusive_MichaelMap_rcu_find_cfunc "find(K const&, Func)"
633 but \p pred is used for key comparing.
634 \p Less functor has the interface like \p std::less.
635 \p Less must imply the same element order as the comparator used for building the map.
637 template <typename K, typename Less, typename Func>
638 bool find_with( K const& key, Less pred, Func f )
640 return bucket( key ).find_with( key, pred, f );
643 /// Checks whether the map contains \p key
645 The function searches the item with key equal to \p key
646 and returns \p true if it is found, and \p false otherwise.
648 The function applies RCU lock internally.
650 template <typename K>
651 bool contains( K const& key )
653 return bucket( key ).contains( key );
656 template <typename K>
657 CDS_DEPRECATED("deprecated, use contains()")
658 bool find( K const& key )
660 return bucket( key ).contains( key );
664 /// Checks whether the map contains \p key using \p pred predicate for searching
666 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
667 \p Less functor has the interface like \p std::less.
668 \p Less must imply the same element order as the comparator used for building the map.
670 template <typename K, typename Less>
671 bool contains( K const& key, Less pred )
673 return bucket( key ).contains( key, pred );
676 template <typename K, typename Less>
677 CDS_DEPRECATED("deprecated, use contains()")
678 bool find_with( K const& key, Less pred )
680 return bucket( key ).contains( key, pred );
684 /// Finds \p key and return the item found
685 /** \anchor cds_nonintrusive_MichaelHashMap_rcu_get
686 The function searches the item with key equal to \p key and returns the pointer to item found.
687 If \p key is not found it returns \p nullptr.
688 Note the type of returned value depends on underlying \p bucket_type.
689 For details, see documentation of ordered list you use.
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;
699 typename hash_map::raw_ptr gp;
702 hash_map::rcu_lock lock;
704 gp = theMap.get( 5 );
709 // Unlock RCU by rcu_lock destructor
710 // gp can be reclaimed at any time after RCU has been unlocked
714 template <typename K>
715 raw_ptr get( K const& key )
717 return bucket( key ).get( key );
720 /// Finds \p key and return the item found
722 The function is an analog of \ref cds_nonintrusive_MichaelHashMap_rcu_get "get(K const&)"
723 but \p pred is used for comparing the keys.
725 \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
727 \p pred must imply the same element order as the comparator used for building the map.
729 template <typename K, typename Less>
730 raw_ptr get_with( K const& key, Less pred )
732 return bucket( key ).get_with( key, pred );
735 /// Clears the map (not atomic)
737 The function erases all items from the map.
739 The function is not atomic. It cleans up each bucket and then resets the item counter to zero.
740 If there are a thread that performs insertion while \p clear is working the result is undefined in general case:
741 <tt> empty() </tt> may return \p true but the map may contain item(s).
742 Therefore, \p clear may be used only for debugging purposes.
744 RCU \p synchronize method can be called. RCU should not be locked.
748 for ( size_t i = 0; i < bucket_count(); ++i )
749 m_Buckets[i].clear();
750 m_ItemCounter.reset();
753 /// Checks if the map is empty
755 Emptiness is checked by item counting: if item count is zero then the map is empty.
756 Thus, the correct item counting is an important part of the map implementation.
763 /// Returns item count in the map
766 return m_ItemCounter;
769 /// Returns the size of hash table
771 Since \p %MichaelHashMap cannot dynamically extend the hash table size,
772 the value returned is an constant depending on object initialization parameters;
773 see \p MichaelHashMap::MichaelHashMap for explanation.
775 size_t bucket_count() const
777 return m_nHashBitmask + 1;
780 }} // namespace cds::container
782 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_MAP_RCU_H