3 #ifndef __CDS_CONTAINER_MICHAEL_LIST_RCU_H
4 #define __CDS_CONTAINER_MICHAEL_LIST_RCU_H
7 #include <cds/container/details/michael_list_base.h>
8 #include <cds/intrusive/michael_list_rcu.h>
9 #include <cds/container/details/make_michael_list.h>
10 #include <cds/details/binary_functor_wrapper.h>
12 namespace cds { namespace container {
14 /// Michael's ordered list (template specialization for \ref cds_urcu_desc "RCU")
15 /** @ingroup cds_nonintrusive_list
16 \anchor cds_nonintrusive_MichaelList_rcu
18 Usually, ordered single-linked list is used as a building block for the hash table implementation.
19 The complexity of searching is <tt>O(N)</tt>.
22 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
24 This class is non-intrusive version of \ref cds_intrusive_MichaelList_rcu "cds::intrusive::MichaelList" RCU specialization.
27 - \p RCU - one of \ref cds_urcu_gc "RCU type"
28 - \p T - type stored in the list. The type must be default- and copy-constructible.
29 - \p Traits - type traits, default is michael_list::type_traits
31 The implementation does not divide type \p T into key and value part and
32 may be used as a main building block for hash set containers.
33 The key is a function (or a part) of type \p T, and this function is specified by <tt>Traits::compare</tt> functor
34 or <tt>Traits::less</tt> predicate.
36 \ref cds_nonintrusive_MichaelKVList_rcu "MichaelKVList" is a key-value version of Michael's
37 non-intrusive list that is closer to the C++ std library approach.
39 @note Before including <tt><cds/container/michael_list_rcu.h></tt> you should include appropriate RCU header file,
40 see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
42 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
43 argument. For example, the following traits-based declaration of Michael's list
46 #include <cds/urcu/general_buffered.h>
47 #include <cds/container/michael_list_rcu.h>
48 // Declare comparator for the item
50 int operator ()( int i1, int i2 )
56 // Declare type_traits
57 struct my_traits: public cds::container::michael_list::type_traits
59 typedef my_compare compare;
62 // Declare traits-based list
63 typedef cds::container::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, my_traits > traits_based_list;
66 is equivalent for the following option-based list
68 #include <cds/urcu/general_buffered.h>
69 #include <cds/container/michael_list_rcu.h>
71 // my_compare is the same
73 // Declare option-based list
74 typedef cds::container::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, int,
75 typename cds::container::michael_list::make_traits<
76 cds::container::opt::compare< my_compare > // item comparator option
81 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
82 - opt::compare - key comparison functor. No default functor is provided.
83 If the option is not specified, the opt::less is used.
84 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
85 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
86 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
87 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
88 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
89 or opt::v::sequential_consistent (sequentially consisnent memory model).
90 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
95 #ifdef CDS_DOXYGEN_INVOKED
96 typename Traits = michael_list::type_traits
101 class MichaelList< cds::urcu::gc<RCU>, T, Traits > :
102 #ifdef CDS_DOXYGEN_INVOKED
103 protected intrusive::MichaelList< cds::urcu::gc<RCU>, T, Traits >
105 protected details::make_michael_list< cds::urcu::gc<RCU>, T, Traits >::type
109 typedef details::make_michael_list< cds::urcu::gc<RCU>, T, Traits > options;
110 typedef typename options::type base_class;
114 typedef T value_type ; ///< Type of value stored in the list
115 typedef typename base_class::gc gc ; ///< RCU schema used
116 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
117 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
118 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
119 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
120 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
121 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
123 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
124 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
128 typedef typename base_class::value_type node_type;
129 typedef typename options::cxx_allocator cxx_allocator;
130 typedef typename options::node_deallocator node_deallocator;
131 typedef typename options::type_traits::compare intrusive_key_comparator;
133 typedef typename base_class::atomic_node_ptr head_type;
137 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer > exempt_ptr; ///< pointer to extracted node
141 static value_type& node_to_value( node_type& n )
145 static value_type const& node_to_value( node_type const& n )
153 template <typename Q>
154 static node_type * alloc_node( Q const& v )
156 return cxx_allocator().New( v );
159 template <typename... Args>
160 static node_type * alloc_node( Args&&... args )
162 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
165 static void free_node( node_type * pNode )
167 cxx_allocator().Delete( pNode );
170 struct node_disposer {
171 void operator()( node_type * pNode )
176 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
180 return base_class::m_pHead;
183 head_type& head() const
185 return const_cast<head_type&>( base_class::m_pHead );
191 template <bool IsConst>
192 class iterator_type: protected base_class::template iterator_type<IsConst>
194 typedef typename base_class::template iterator_type<IsConst> iterator_base;
196 iterator_type( head_type const& pNode )
197 : iterator_base( pNode )
200 friend class MichaelList;
203 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
204 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
209 iterator_type( iterator_type const& src )
210 : iterator_base( src )
213 value_ptr operator ->() const
215 typename iterator_base::value_ptr p = iterator_base::operator ->();
216 return p ? &(p->m_Value) : nullptr;
219 value_ref operator *() const
221 return (iterator_base::operator *()).m_Value;
225 iterator_type& operator ++()
227 iterator_base::operator ++();
232 bool operator ==(iterator_type<C> const& i ) const
234 return iterator_base::operator ==(i);
237 bool operator !=(iterator_type<C> const& i ) const
239 return iterator_base::operator !=(i);
246 typedef iterator_type<false> iterator;
248 /// Const forward iterator
249 typedef iterator_type<true> const_iterator;
251 /// Returns a forward iterator addressing the first element in a list
253 For empty list \code begin() == end() \endcode
257 return iterator( head() );
260 /// Returns an iterator that addresses the location succeeding the last element in a list
262 Do not use the value returned by <tt>end</tt> function to access any item.
263 Internally, <tt>end</tt> returning value equals to \p nullptr.
265 The returned value can be used only to control reaching the end of the list.
266 For empty list \code begin() == end() \endcode
273 /// Returns a forward const iterator addressing the first element in a list
275 const_iterator begin() const
277 return const_iterator( head() );
279 const_iterator cbegin()
281 return const_iterator( head() );
285 /// Returns an const iterator that addresses the location succeeding the last element in a list
287 const_iterator end() const
289 return const_iterator();
291 const_iterator cend()
293 return const_iterator();
298 /// Default constructor
300 Initialize empty list
316 The function creates a node with copy of \p val value
317 and then inserts the node created into the list.
319 The type \p Q should contain as minimum the complete key of the node.
320 The object of \ref value_type should be constructible from \p val of type \p Q.
321 In trivial case, \p Q is equal to \ref value_type.
323 The function makes RCU lock internally.
325 Returns \p true if inserting successful, \p false otherwise.
327 template <typename Q>
328 bool insert( Q const& val )
330 return insert_at( head(), val );
335 This function inserts new node with default-constructed value and then it calls
336 \p func functor with signature
337 \code void func( value_type& itemValue ) ;\endcode
339 The argument \p itemValue of user-defined functor \p func is the reference
340 to the list's item inserted. User-defined functor \p func should guarantee that during changing
341 item's value no any other changes could be made on this list's item by concurrent threads.
342 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
343 and it is called only if the inserting is success.
345 The type \p Q should contain the complete key of the node.
346 The object of \ref value_type should be constructible from \p key of type \p Q.
348 The function allows to split creating of new item into two part:
349 - create item from \p key with initializing key-fields only;
350 - insert new item into the list;
351 - if inserting is successful, initialize non-key fields of item by calling \p f functor
353 This can be useful if complete initialization of object of \p value_type is heavyweight and
354 it is preferable that the initialization should be completed only if inserting is successful.
356 The function makes RCU lock internally.
358 template <typename Q, typename Func>
359 bool insert( Q const& key, Func func )
361 return insert_at( head(), key, func );
364 /// Ensures that the \p key exists in the list
366 The operation performs inserting or changing data with lock-free manner.
368 If the \p key not found in the list, then the new item created from \p key
369 is inserted into the list. Otherwise, the functor \p func is called with the item found.
370 The functor \p Func should be a function with signature:
372 void func( bool bNew, value_type& item, const Q& val );
377 void operator()( bool bNew, value_type& item, const Q& val );
382 - \p bNew - \p true if the item has been inserted, \p false otherwise
383 - \p item - item of the list
384 - \p val - argument \p key passed into the \p ensure function
386 The functor may change non-key fields of the \p item; however, \p func must guarantee
387 that during changing no any other modifications could be made on this item by concurrent threads.
389 You may pass \p func argument by reference using <tt>boost::ref</tt>.
391 The function makes RCU lock internally.
393 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
394 \p second is true if new item has been added or \p false if the item with \p key
395 already is in the list.
397 template <typename Q, typename Func>
398 std::pair<bool, bool> ensure( Q const& key, Func f )
400 return ensure_at( head(), key, f );
403 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
405 Returns \p true if inserting successful, \p false otherwise.
407 The function makes RCU lock internally.
409 template <typename... Args>
410 bool emplace( Args&&... args )
412 return emplace_at( head(), std::forward<Args>(args)... );
415 /// Deletes \p key from the list
416 /** \anchor cds_nonintrusive_MichealList_rcu_erase_val
417 Since the key of MichaelList's item type \p T is not explicitly specified,
418 template parameter \p Q defines the key type searching in the list.
419 The list item comparator should be able to compare the type \p T of list item
420 and the value \p key of type \p Q.
422 RCU \p synchronize method can be called. RCU should not be locked.
424 Return \p true if key is found and deleted, \p false otherwise
426 template <typename Q>
427 bool erase( Q const& key )
429 return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
432 /// Deletes the item from the list using \p pred predicate for searching
434 The function is an analog of \ref cds_nonintrusive_MichealList_rcu_erase_val "erase(Q const&)"
435 but \p pred is used for key comparing.
436 \p Less functor has the interface like \p std::less.
437 \p pred must imply the same element order as the comparator used for building the list.
439 template <typename Q, typename Less>
440 bool erase_with( Q const& key, Less pred )
442 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), [](value_type const&){} );
445 /// Deletes \p key from the list
446 /** \anchor cds_nonintrusive_MichaelList_rcu_erase_func
447 The function searches an item with key \p key, calls \p f functor with item found
448 and deletes it. If \p key is not found, the functor is not called.
450 The functor \p Func interface:
453 void operator()(const value_type& val) { ... }
456 The functor may be passed by reference with <tt>boost:ref</tt>
458 Since the key of MichaelList's item type \p T is not explicitly specified,
459 template parameter \p Q defines the key type searching in the list.
460 The list item comparator should be able to compare the type \p T of list item
463 RCU \p synchronize method can be called. RCU should not be locked.
465 Return \p true if key is found and deleted, \p false otherwise
467 template <typename Q, typename Func>
468 bool erase( Q const& key, Func f )
470 return erase_at( head(), key, intrusive_key_comparator(), f );
473 /// Deletes the item from the list using \p pred predicate for searching
475 The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_erase_func "erase(Q const&, Func)"
476 but \p pred is used for key comparing.
477 \p Less functor has the interface like \p std::less.
478 \p pred must imply the same element order as the comparator used for building the list.
480 template <typename Q, typename Less, typename Func>
481 bool erase_with( Q const& key, Less pred, Func f )
483 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
486 /// Extracts an item from the list
488 @anchor cds_nonintrusive_MichaelList_rcu_extract
489 The function searches an item with key equal to \p val in the list,
490 unlinks it from the list, and returns pointer to an item found in \p dest argument.
491 If the item with the key equal to \p val is not found the function returns \p false.
493 @note The function does NOT call RCU read-side lock or synchronization,
494 and does NOT dispose the item found. It just excludes the item from the list
495 and returns a pointer to item found.
496 You should lock RCU before calling this function.
499 #include <cds/urcu/general_buffered.h>
500 #include <cds/container/michael_list_rcu.h>
502 typedef cds::urcu::gc< general_buffered<> > rcu;
503 typedef cds::container::MichaelList< rcu, Foo > rcu_michael_list;
505 rcu_michael_list theList;
508 rcu_michael_list::exempt_ptr p;
510 // first, we should lock RCU
513 // Now, you can apply extract function
514 // Note that you must not delete the item found inside the RCU lock
515 if ( theList.extract( p, 10 )) {
516 // do something with p
520 // Outside RCU lock section we may safely release extracted pointer.
521 // release() passes the pointer to RCU reclamation cycle.
525 template <typename Q>
526 bool extract( exempt_ptr& dest, Q const& val )
528 dest = extract_at( head(), val, intrusive_key_comparator() );
529 return !dest.empty();
532 /// Extracts an item from the list using \p pred predicate for searching
534 This function is the analog for \ref cds_nonintrusive_MichaelList_rcu_extract "extract(exempt_ptr&, Q const&)".
536 The \p pred is a predicate used for key comparing.
537 \p Less has the interface like \p std::less.
538 \p pred must imply the same element order as \ref key_comparator.
540 template <typename Q, typename Less>
541 bool extract_with( exempt_ptr& dest, Q const& val, Less pred )
543 dest = extract_at( head(), val, typename options::template less_wrapper<Less>::type() );
544 return !dest.empty();
547 /// Finds the key \p key
548 /** \anchor cds_nonintrusive_MichaelList_rcu_find_val
549 The function searches the item with key equal to \p key
550 and returns \p true if it is found, and \p false otherwise.
552 The function makes RCU lock internally.
554 template <typename Q>
555 bool find( Q const& key ) const
557 return find_at( head(), key, intrusive_key_comparator() );
560 /// Finds the key \p val using \p pred predicate for searching
562 The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_find_val "find(Q const&)"
563 but \p pred is used for key comparing.
564 \p Less functor has the interface like \p std::less.
565 \p pred must imply the same element order as the comparator used for building the list.
567 template <typename Q, typename Less>
568 bool find_with( Q const& key, Less pred ) const
570 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
573 /// Finds the key \p val and performs an action with it
574 /** \anchor cds_nonintrusive_MichaelList_rcu_find_func
575 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
576 The interface of \p Func functor is:
579 void operator()( value_type& item, Q& val );
582 where \p item is the item found, \p val is the <tt>find</tt> function argument.
584 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
586 The functor may change non-key fields of \p item. Note that the function is only guarantee
587 that \p item cannot be deleted during functor is executing.
588 The function does not serialize simultaneous access to the list \p item. If such access is
589 possible you must provide your own synchronization schema to exclude unsafe item modifications.
591 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
592 may modify both arguments.
594 The function makes RCU lock internally.
596 The function returns \p true if \p val is found, \p false otherwise.
598 template <typename Q, typename Func>
599 bool find( Q& val, Func f ) const
601 return find_at( head(), val, intrusive_key_comparator(), f );
604 /// Finds the key \p val using \p pred predicate for searching
606 The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_find_func "find(Q&, Func)"
607 but \p pred is used for key comparing.
608 \p Less functor has the interface like \p std::less.
609 \p pred must imply the same element order as the comparator used for building the list.
611 template <typename Q, typename Less, typename Func>
612 bool find_with( Q& val, Less pred, Func f ) const
614 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
617 /// Finds the key \p val and performs an action with it
618 /** \anchor cds_nonintrusive_MichaelList_rcu_find_cfunc
619 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
620 The interface of \p Func functor is:
623 void operator()( value_type& item, Q const& val );
626 where \p item is the item found, \p val is the <tt>find</tt> function argument.
628 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
630 The functor may change non-key fields of \p item. Note that the function is only guarantee
631 that \p item cannot be deleted during functor is executing.
632 The function does not serialize simultaneous access to the list \p item. If such access is
633 possible you must provide your own synchronization schema to exclude unsafe item modifications.
635 The function makes RCU lock internally.
637 The function returns \p true if \p val is found, \p false otherwise.
639 template <typename Q, typename Func>
640 bool find( Q const& val, Func f ) const
642 return find_at( head(), val, intrusive_key_comparator(), f );
645 /// Finds the key \p val using \p pred predicate for searching
647 The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_find_cfunc "find(Q&, Func)"
648 but \p pred is used for key comparing.
649 \p Less functor has the interface like \p std::less.
650 \p pred must imply the same element order as the comparator used for building the list.
652 template <typename Q, typename Less, typename Func>
653 bool find_with( Q const& val, Less pred, Func f ) const
655 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
658 /// Finds the key \p val and return the item found
659 /** \anchor cds_nonintrusive_MichaelList_rcu_get
660 The function searches the item with key equal to \p val and returns the pointer to item found.
661 If \p val is not found it returns \p nullptr.
663 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
665 RCU should be locked before call of this function.
666 Returned item is valid only while RCU is locked:
668 typedef cds::container::MichaelList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
673 ord_list::rcu_lock lock;
675 foo * pVal = theList.get( 5 );
680 // Unlock RCU by rcu_lock destructor
681 // pVal can be freed at any time after RCU has been unlocked
685 template <typename Q>
686 value_type * get( Q const& val ) const
688 return get_at( head(), val, intrusive_key_comparator());
691 /// Finds the key \p val and return the item found
693 The function is an analog of \ref cds_nonintrusive_MichaelList_rcu_get "get(Q const&)"
694 but \p pred is used for comparing the keys.
696 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
698 \p pred must imply the same element order as the comparator used for building the list.
700 template <typename Q, typename Less>
701 value_type * get_with( Q const& val, Less pred ) const
703 return get_at( head(), val, typename options::template less_wrapper<Less>::type());
706 /// Checks if the list is empty
709 return base_class::empty();
712 /// Returns list's item count
714 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
715 this function always returns 0.
717 <b>Warning</b>: even if you use a real item counter and it returns 0, this fact is not mean that the list
718 is empty. To check list emptyness use \ref empty() method.
722 return base_class::size();
727 Post-condition: the list is empty
736 bool insert_node_at( head_type& refHead, node_type * pNode )
739 scoped_node_ptr p(pNode);
740 if ( base_class::insert_at( refHead, *pNode )) {
748 template <typename Q>
749 bool insert_at( head_type& refHead, Q const& val )
751 return insert_node_at( refHead, alloc_node( val ));
754 template <typename Q, typename Func>
755 bool insert_at( head_type& refHead, Q const& key, Func f )
757 scoped_node_ptr pNode( alloc_node( key ));
759 if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { cds::unref(f)( node_to_value(node) ); } )) {
766 template <typename... Args>
767 bool emplace_at( head_type& refHead, Args&&... args )
769 return insert_node_at( refHead, alloc_node( std::forward<Args>(args) ... ));
772 template <typename Q, typename Compare, typename Func>
773 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
775 return base_class::erase_at( refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
778 template <typename Q, typename Func>
779 std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
781 scoped_node_ptr pNode( alloc_node( key ));
783 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
784 [&f, &key](bool bNew, node_type& node, node_type&){ cds::unref(f)( bNew, node_to_value(node), key ); });
785 if ( ret.first && ret.second )
791 template <typename Q, typename Compare>
792 node_type * extract_at( head_type& refHead, Q const& key, Compare cmp )
794 return base_class::extract_at( refHead, key, cmp );
797 template <typename Q, typename Compare>
798 bool find_at( head_type& refHead, Q const& key, Compare cmp ) const
800 return base_class::find_at( refHead, key, cmp, [](node_type&, Q const &) {} );
803 template <typename Q, typename Compare, typename Func>
804 bool find_at( head_type& refHead, Q& val, Compare cmp, Func f ) const
806 return base_class::find_at( refHead, val, cmp, [&f](node_type& node, Q& v){ cds::unref(f)( node_to_value(node), v ); });
809 template <typename Q, typename Compare>
810 value_type * get_at( head_type& refHead, Q const& val, Compare cmp ) const
812 node_type * pNode = base_class::get_at( refHead, val, cmp );
813 return pNode ? &pNode->m_Value : nullptr;
819 }} // namespace cds::container
821 #endif // #ifndef __CDS_CONTAINER_MICHAEL_LIST_RCU_H