2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H
32 #define CDSLIB_CONTAINER_MICHAEL_SET_RCU_H
34 #include <cds/container/details/michael_set_base.h>
35 #include <cds/details/allocator.h>
37 namespace cds { namespace container {
39 /// Michael's hash set (template specialization for \ref cds_urcu_desc "RCU")
40 /** @ingroup cds_nonintrusive_set
41 \anchor cds_nonintrusive_MichaelHashSet_rcu
44 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
46 Michael's hash table algorithm is based on lock-free ordered list and it is very simple.
47 The main structure is an array \p T of size \p M. Each element in \p T is basically a pointer
48 to a hash bucket, implemented as a singly linked list. The array of buckets cannot be dynamically expanded.
49 However, each bucket may contain unbounded number of items.
51 Template parameters are:
52 - \p RCU - one of \ref cds_urcu_gc "RCU type"
53 - \p OrderedList - ordered list implementation used as the bucket for hash set, for example,
54 \ref cds_nonintrusive_MichaelList_rcu "MichaelList".
55 The ordered list implementation specifies the type \p T stored in the hash-set,
56 the comparison functor for the type \p T and other features specific for
58 - \p Traits - set traits, default is michael_set::traits.
59 Instead of defining \p Traits struct you may use option-based syntax with michael_set::make_traits metafunction.
61 About hash functor see \ref cds_nonintrusive_MichaelHashSet_hash_functor "MichaelSet hash functor".
65 Suppose, we have the following type \p Foo that we want to store in your \p %MichaelHashSet:
68 int nKey ; // key field
69 int nVal ; // value field
73 To use \p %MichaelHashSet for \p Foo values, you should first choose suitable ordered list class
74 that will be used as a bucket for the set. We will cds::urcu::general_buffered<> RCU type and
75 MichaelList as a bucket type.
76 You should include RCU-related header file (<tt>cds/urcu/general_buffered.h</tt> in this example)
77 before including <tt>cds/container/michael_set_rcu.h</tt>.
78 Also, for ordered list we should develop a comparator for our \p Foo struct.
80 #include <cds/urcu/general_buffered.h>
81 #include <cds/container/michael_list_rcu.h>
82 #include <cds/container/michael_set_rcu.h>
84 namespace cc = cds::container;
88 int operator ()(Foo const& v1, Foo const& v2 ) const
90 if ( std::less( v1.nKey, v2.nKey ))
92 return std::less(v2.nKey, v1.nKey) ? 1 : 0;
97 typedef cc::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, Foo,
98 typename cc::michael_list::make_traits<
99 cc::opt::compare< Foo_cmp > // item comparator option
103 // Hash functor for Foo
105 size_t operator ()( int i ) const
107 return std::hash( i );
109 size_t operator()( Foo const& i ) const
111 return std::hash( i.nKey );
116 // Note that \p RCU template parameter of ordered list must be equal \p RCU for the set.
117 typedef cc::MichaelHashSet< cds::urcu::gc< cds::urcu::general_buffered<> >, bucket_list,
118 cc::michael_set::make_traits<
119 cc::opt::hash< foo_hash >
129 #ifdef CDS_DOXYGEN_INVOKED
130 class Traits = michael_set::traits
135 class MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
138 typedef cds::urcu::gc< RCU > gc; ///< RCU used as garbage collector
139 typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation
140 typedef Traits traits; ///< Set traits
142 typedef typename bucket_type::value_type value_type; ///< type of value to be stored in the list
143 typedef typename bucket_type::key_comparator key_comparator; ///< key comparing functor
145 /// Hash functor for \ref value_type and all its derivatives that you use
146 typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
147 typedef typename traits::item_counter item_counter; ///< Item counter type
149 typedef typename bucket_type::rcu_lock rcu_lock; ///< RCU scoped lock
150 typedef typename bucket_type::exempt_ptr exempt_ptr; ///< pointer to extracted node
151 typedef typename bucket_type::raw_ptr raw_ptr; ///< Return type of \p get() member function and its derivatives
152 /// Group of \p extract_xxx functions require external locking if underlying ordered list requires that
153 static CDS_CONSTEXPR const bool c_bExtractLockExternal = bucket_type::c_bExtractLockExternal;
157 class internal_bucket_type: public bucket_type
159 typedef bucket_type base_class;
161 using base_class::node_type;
162 using base_class::alloc_node;
163 using base_class::insert_node;
164 using base_class::node_to_value;
167 /// Bucket table allocator
168 typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator > bucket_table_allocator;
173 item_counter m_ItemCounter; ///< Item counter
174 hash m_HashFunctor; ///< Hash functor
175 internal_bucket_type * m_Buckets; ///< bucket table
179 const size_t m_nHashBitmask;
184 /// Calculates hash value of \p key
185 template <typename Q>
186 size_t hash_value( Q const& key ) const
188 return m_HashFunctor( key ) & m_nHashBitmask;
191 /// Returns the bucket (ordered list) for \p key
192 template <typename Q>
193 internal_bucket_type& bucket( Q const& key )
195 return m_Buckets[ hash_value( key ) ];
197 template <typename Q>
198 internal_bucket_type const& bucket( Q const& key ) const
200 return m_Buckets[ hash_value( key ) ];
204 ///@name Forward iterators (thread-safe under RCU lock)
208 The forward iterator for Michael's set is based on \p OrderedList forward iterator and has some features:
209 - it has no post-increment operator
210 - it iterates items in unordered fashion
212 You may safely use iterators in multi-threaded environment only under RCU lock.
213 Otherwise, a crash is possible if another thread deletes the element the iterator points to.
215 The iterator interface:
219 // Default constructor
223 iterator( iterator const& src );
225 // Dereference operator
226 value_type * operator ->() const;
228 // Dereference operator
229 value_type& operator *() const;
231 // Preincrement operator
232 iterator& operator ++();
234 // Assignment operator
235 iterator& operator = (iterator const& src);
237 // Equality operators
238 bool operator ==(iterator const& i ) const;
239 bool operator !=(iterator const& i ) const;
243 typedef michael_set::details::iterator< bucket_type, false > iterator;
245 /// Const forward iterator
246 typedef michael_set::details::iterator< bucket_type, true > const_iterator;
248 /// Returns a forward iterator addressing the first element in a set
250 For empty set \code begin() == end() \endcode
254 return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
257 /// Returns an iterator that addresses the location succeeding the last element in a set
259 Do not use the value returned by <tt>end</tt> function to access any item.
260 The returned value can be used only to control reaching the end of the set.
261 For empty set \code begin() == end() \endcode
265 return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
268 /// Returns a forward const iterator addressing the first element in a set
269 const_iterator begin() const
271 return get_const_begin();
274 /// Returns a forward const iterator addressing the first element in a set
275 const_iterator cbegin() const
277 return get_const_begin();
280 /// Returns an const iterator that addresses the location succeeding the last element in a set
281 const_iterator end() const
283 return get_const_end();
286 /// Returns an const iterator that addresses the location succeeding the last element in a set
287 const_iterator cend() const
289 return get_const_end();
295 const_iterator get_const_begin() const
297 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
299 const_iterator get_const_end() const
301 return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
306 /// Initialize hash set
308 The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
309 when you create an object.
310 \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
311 Remember, since the bucket implementation is an ordered list, searching in the bucket is linear [<tt>O(nLoadFactor)</tt>].
313 The ctor defines hash table size as rounding <tt>nMaxItemCount / nLoadFactor</tt> up to nearest power of two.
316 size_t nMaxItemCount, ///< estimation of max item count in the hash set
317 size_t nLoadFactor ///< load factor: estimation of max number of items in the bucket
318 ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
320 // GC and OrderedList::gc must be the same
321 static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
323 static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
324 "atomicity::empty_item_counter is not allowed as a item counter");
326 m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
329 /// Clears hash set and destroys it
333 bucket_table_allocator().Delete( m_Buckets, bucket_count() );
338 The function creates a node with copy of \p val value
339 and then inserts the node created into the set.
341 The type \p Q should contain as minimum the complete key for the node.
342 The object of \ref value_type should be constructible from a value of type \p Q.
343 In trivial case, \p Q is equal to \ref value_type.
345 The function applies RCU lock internally.
347 Returns \p true if \p val is inserted into the set, \p false otherwise.
349 template <typename Q>
350 bool insert( Q const& val )
352 const bool bRet = bucket( val ).insert( val );
360 The function allows to split creating of new item into two part:
361 - create item with key only
362 - insert new item into the set
363 - if inserting is success, calls \p f functor to initialize value-fields of \p val.
365 The functor signature is:
367 void func( value_type& val );
369 where \p val is the item inserted.
370 The user-defined functor is called only if the inserting is success.
372 The function applies RCU lock internally.
374 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
375 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
378 template <typename Q, typename Func>
379 bool insert( Q const& val, Func f )
381 const bool bRet = bucket( val ).insert( val, f );
387 /// Ensures that the item exists in the set
389 The operation performs inserting or changing data with lock-free manner.
391 If the \p val key not found in the set, then the new item created from \p val
392 is inserted into the set. Otherwise, the functor \p func is called with the item found.
393 The functor \p Func signature is:
396 void operator()( bool bNew, value_type& item, const Q& val );
401 - \p bNew - \p true if the item has been inserted, \p false otherwise
402 - \p item - item of the set
403 - \p val - argument \p key passed into the \p ensure function
405 The functor may change non-key fields of the \p item.
407 The function applies RCU lock internally.
409 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
410 \p second is true if new item has been added or \p false if the item with \p key
411 already is in the set.
413 @warning For \ref cds_nonintrusive_MichaelList_rcu "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
414 \ref cds_nonintrusive_LazyList_rcu "LazyList" provides exclusive access to inserted item and does not require any node-level
417 /// Updates the element
419 The operation performs inserting or changing data with lock-free manner.
421 If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
422 Otherwise, the functor \p func is called with item found.
423 The functor signature is:
426 void operator()( bool bNew, value_type& item, Q const& val );
430 - \p bNew - \p true if the item has been inserted, \p false otherwise
431 - \p item - item of the set
432 - \p val - argument \p val passed into the \p %update() function
434 The functor may change non-key fields of the \p item.
436 The function applies RCU lock internally.
438 Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successfull,
439 \p second is \p true if new item has been added or \p false if the item with \p key
440 already is in the set.
442 @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
443 \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
446 template <typename Q, typename Func>
447 std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert = true )
449 std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowInsert );
454 template <typename Q, typename Func>
455 CDS_DEPRECATED("ensure() is deprecated, use update()")
456 std::pair<bool, bool> ensure( const Q& val, Func func )
458 return update( val, func, true );
462 /// Inserts data of type \p value_type created from \p args
464 Returns \p true if inserting successful, \p false otherwise.
466 The function applies RCU lock internally.
468 template <typename... Args>
469 bool emplace( Args&&... args )
471 typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward<Args>( args )... );
472 bool bRet = bucket( internal_bucket_type::node_to_value( *pNode ) ).insert_node( pNode );
478 /// Deletes \p key from the set
479 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_val
481 Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
482 template parameter \p Q defines the key type searching in the list.
483 The set item comparator should be able to compare the type \p value_type
486 RCU \p synchronize method can be called. RCU should not be locked.
488 Return \p true if key is found and deleted, \p false otherwise
490 template <typename Q>
491 bool erase( Q const& key )
493 const bool bRet = bucket( key ).erase( key );
499 /// Deletes the item from the set using \p pred predicate for searching
501 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_val "erase(Q const&)"
502 but \p pred is used for key comparing.
503 \p Less functor has the interface like \p std::less.
504 \p Less must imply the same element order as the comparator used for building the set.
506 template <typename Q, typename Less>
507 bool erase_with( Q const& key, Less pred )
509 const bool bRet = bucket( key ).erase_with( key, pred );
515 /// Deletes \p key from the set
516 /** \anchor cds_nonintrusive_MichealSet_rcu_erase_func
518 The function searches an item with key \p key, calls \p f functor
519 and deletes the item. If \p key is not found, the functor is not called.
521 The functor \p Func interface:
524 void operator()(value_type const& val);
528 Since the key of %MichaelHashSet's \p value_type is not explicitly specified,
529 template parameter \p Q defines the key type searching in the list.
530 The list item comparator should be able to compare the type \p T of list item
533 RCU \p synchronize method can be called. RCU should not be locked.
535 Return \p true if key is found and deleted, \p false otherwise
537 template <typename Q, typename Func>
538 bool erase( Q const& key, Func f )
540 const bool bRet = bucket( key ).erase( key, f );
546 /// Deletes the item from the set using \p pred predicate for searching
548 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_erase_func "erase(Q const&, Func)"
549 but \p pred is used for key comparing.
550 \p Less functor has the interface like \p std::less.
551 \p Less must imply the same element order as the comparator used for building the set.
553 template <typename Q, typename Less, typename Func>
554 bool erase_with( Q const& key, Less pred, Func f )
556 const bool bRet = bucket( key ).erase_with( key, pred, f );
562 /// Extracts an item from the set
563 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_extract
564 The function searches an item with key equal to \p key in the set,
565 unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
566 If the item with the key equal to \p key is not found the function return an empty \p exempt_ptr.
568 The function just excludes the item from the set and returns a pointer to item found.
569 Depends on \p bucket_type you should or should not lock RCU before calling of this function:
570 - for the set based on \ref cds_nonintrusive_MichaelList_rcu "MichaelList" RCU should not be locked
571 - for the set based on \ref cds_nonintrusive_LazyList_rcu "LazyList" RCU should be locked
572 See ordered list implementation for details.
575 #include <cds/urcu/general_buffered.h>
576 #include <cds/container/michael_list_rcu.h>
577 #include <cds/container/michael_set_rcu.h>
579 typedef cds::urcu::gc< general_buffered<> > rcu;
580 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
581 typedef cds::container::MichaelHashSet< rcu, rcu_michael_list, foo_traits > rcu_michael_set;
583 rcu_michael_set theSet;
586 typename rcu_michael_set::exempt_ptr p;
588 // For MichaelList we should not lock RCU
590 // Note that you must not delete the item found inside the RCU lock
591 p = theSet.extract( 10 );
593 // do something with p
597 // We may safely release p here
598 // release() passes the pointer to RCU reclamation cycle
602 template <typename Q>
603 exempt_ptr extract( Q const& key )
605 exempt_ptr p = bucket( key ).extract( key );
611 /// Extracts an item from the set using \p pred predicate for searching
613 The function is an analog of \p extract(Q const&) but \p pred is used for key comparing.
614 \p Less functor has the interface like \p std::less.
615 \p pred must imply the same element order as the comparator used for building the set.
617 template <typename Q, typename Less>
618 exempt_ptr extract_with( Q const& key, Less pred )
620 exempt_ptr p = bucket( key ).extract_with( key, pred );
626 /// Finds the key \p key
627 /** \anchor cds_nonintrusive_MichealSet_rcu_find_func
629 The function searches the item with key equal to \p key and calls the functor \p f for item found.
630 The interface of \p Func functor is:
633 void operator()( value_type& item, Q& key );
636 where \p item is the item found, \p key is the <tt>find</tt> function argument.
638 The functor may change non-key fields of \p item. Note that the functor is only guarantee
639 that \p item cannot be disposed during functor is executing.
640 The functor does not serialize simultaneous access to the set's \p item. If such access is
641 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
643 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
644 can modify both arguments.
646 Note the hash functor specified for class \p Traits template parameter
647 should accept a parameter of type \p Q that may be not the same as \p value_type.
649 The function applies RCU lock internally.
651 The function returns \p true if \p key is found, \p false otherwise.
653 template <typename Q, typename Func>
654 bool find( Q& key, Func f )
656 return bucket( key ).find( key, f );
659 template <typename Q, typename Func>
660 bool find( Q const& key, Func f )
662 return bucket( key ).find( key, f );
666 /// Finds the key \p key using \p pred predicate for searching
668 The function is an analog of \ref cds_nonintrusive_MichealSet_rcu_find_func "find(Q&, Func)"
669 but \p pred is used for key comparing.
670 \p Less functor has the interface like \p std::less.
671 \p Less must imply the same element order as the comparator used for building the set.
673 template <typename Q, typename Less, typename Func>
674 bool find_with( Q& key, Less pred, Func f )
676 return bucket( key ).find_with( key, pred, f );
679 template <typename Q, typename Less, typename Func>
680 bool find_with( Q const& key, Less pred, Func f )
682 return bucket( key ).find_with( key, pred, f );
686 /// Checks whether the set contains \p key
689 The function searches the item with key equal to \p key
690 and returns \p true if the key is found, and \p false otherwise.
692 Note the hash functor specified for class \p Traits template parameter
693 should accept a parameter of type \p Q that can be not the same as \p value_type.
695 template <typename Q>
696 bool contains( Q const& key )
698 return bucket( key ).contains( key );
701 template <typename Q>
702 CDS_DEPRECATED("use contains()")
703 bool find( Q const& key )
705 return contains( key );
709 /// Checks whether the set contains \p key using \p pred predicate for searching
711 The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
712 \p Less functor has the interface like \p std::less.
713 \p Less must imply the same element order as the comparator used for building the set.
715 template <typename Q, typename Less>
716 bool contains( Q const& key, Less pred )
718 return bucket( key ).contains( key, pred );
721 template <typename Q, typename Less>
722 CDS_DEPRECATED("use contains()")
723 bool find_with( Q const& key, Less pred )
725 return contains( key, pred );
729 /// Finds the key \p key and return the item found
730 /** \anchor cds_nonintrusive_MichaelHashSet_rcu_get
731 The function searches the item with key equal to \p key and returns the pointer to item found.
732 If \p key is not found it returns \p nullptr.
733 Note the type of returned value depends on underlying \p bucket_type.
734 For details, see documentation of ordered list you use.
736 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
738 RCU should be locked before call of this function.
739 Returned item is valid only while RCU is locked:
741 typedef cds::container::MichaelHashSet< your_template_parameters > hash_set;
743 typename hash_set::raw_ptr gp;
747 hash_set::rcu_lock lock;
749 gp = theSet.get( 5 );
754 // Unlock RCU by rcu_lock destructor
755 // gp can be reclaimed at any time after RCU has been unlocked
759 template <typename Q>
760 raw_ptr get( Q const& key )
762 return bucket( key ).get( key );
765 /// Finds the key \p key and return the item found
767 The function is an analog of \ref cds_nonintrusive_MichaelHashSet_rcu_get "get(Q const&)"
768 but \p pred is used for comparing the keys.
770 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
772 \p pred must imply the same element order as the comparator used for building the set.
774 template <typename Q, typename Less>
775 raw_ptr get_with( Q const& key, Less pred )
777 return bucket( key ).get_with( key, pred );
780 /// Clears the set (not atomic)
783 for ( size_t i = 0; i < bucket_count(); ++i )
784 m_Buckets[i].clear();
785 m_ItemCounter.reset();
788 /// Checks if the set is empty
790 Emptiness is checked by item counting: if item count is zero then the set is empty.
791 Thus, the correct item counting feature is an important part of Michael's set implementation.
798 /// Returns item count in the set
801 return m_ItemCounter;
804 /// Returns the size of hash table
806 Since \p %MichaelHashSet cannot dynamically extend the hash table size,
807 the value returned is an constant depending on object initialization parameters;
808 see MichaelHashSet::MichaelHashSet for explanation.
810 size_t bucket_count() const
812 return m_nHashBitmask + 1;
816 }} // namespace cds::container
818 #endif // ifndef CDSLIB_CONTAINER_MICHAEL_SET_RCU_H