3 #ifndef __CDS_CONTAINER_IMPL_MICHAEL_LIST_H
4 #define __CDS_CONTAINER_IMPL_MICHAEL_LIST_H
7 #include <cds/container/details/guarded_ptr_cast.h>
9 namespace cds { namespace container {
11 /// Michael's ordered list
12 /** @ingroup cds_nonintrusive_list
13 \anchor cds_nonintrusive_MichaelList_gc
15 Usually, ordered single-linked list is used as a building block for the hash table implementation.
16 The complexity of searching is <tt>O(N)</tt>.
19 - [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
21 This class is non-intrusive version of cds::intrusive::MichaelList class
24 - \p GC - garbage collector used
25 - \p T - type stored in the list. The type must be default- and copy-constructible.
26 - \p Traits - type traits, default is michael_list::type_traits
28 Unlike standard container, this implementation does not divide type \p T into key and value part and
29 may be used as a main building block for hash set algorithms.
30 The key is a function (or a part) of type \p T, and this function is specified by <tt>Traits::compare</tt> functor
31 or <tt>Traits::less</tt> predicate
33 MichaelKVList is a key-value version of Michael's non-intrusive list that is closer to the C++ std library approach.
35 It is possible to declare option-based list with cds::container::michael_list::make_traits metafunction istead of \p Traits template
36 argument. For example, the following traits-based declaration of gc::HP Michael's list
38 #include <cds/container/michael_list_hp.h>
39 // Declare comparator for the item
41 int operator ()( int i1, int i2 )
47 // Declare type_traits
48 struct my_traits: public cds::container::michael_list::type_traits
50 typedef my_compare compare;
53 // Declare traits-based list
54 typedef cds::container::MichaelList< cds::gc::HP, int, my_traits > traits_based_list;
57 is equivalent for the following option-based list
59 #include <cds/container/michael_list_hp.h>
61 // my_compare is the same
63 // Declare option-based list
64 typedef cds::container::MichaelList< cds::gc::HP, int,
65 typename cds::container::michael_list::make_traits<
66 cds::container::opt::compare< my_compare > // item comparator option
71 Template argument list \p Options of cds::container::michael_list::make_traits metafunction are:
72 - opt::compare - key comparison functor. No default functor is provided.
73 If the option is not specified, the opt::less is used.
74 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
75 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
76 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
77 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
78 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
79 or opt::v::sequential_consistent (sequentially consisnent memory model).
82 There are different specializations of this template for each garbage collecting schema used.
83 You should include appropriate .h-file depending on GC you are using:
84 - for gc::HP: \code #include <cds/container/michael_list_hp.h> \endcode
85 - for gc::DHP: \code #include <cds/container/michael_list_dhp.h> \endcode
86 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/michael_list_rcu.h> \endcode
87 - for gc::nogc: \code #include <cds/container/michael_list_nogc.h> \endcode
92 #ifdef CDS_DOXYGEN_INVOKED
93 typename Traits = michael_list::type_traits
99 #ifdef CDS_DOXYGEN_INVOKED
100 protected intrusive::MichaelList< GC, T, Traits >
102 protected details::make_michael_list< GC, T, Traits >::type
106 typedef details::make_michael_list< GC, T, Traits > options;
107 typedef typename options::type base_class;
111 typedef T value_type ; ///< Type of value stored in the list
112 typedef typename base_class::gc gc ; ///< Garbage collector used
113 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
114 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
115 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
116 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
117 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
121 typedef typename base_class::value_type node_type;
122 typedef typename options::cxx_allocator cxx_allocator;
123 typedef typename options::node_deallocator node_deallocator;
124 typedef typename options::type_traits::compare intrusive_key_comparator;
126 typedef typename base_class::atomic_node_ptr head_type;
131 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
135 static value_type& node_to_value( node_type& n )
139 static value_type const& node_to_value( node_type const& n )
147 template <typename Q>
148 static node_type * alloc_node( Q const& v )
150 return cxx_allocator().New( v );
153 template <typename... Args>
154 static node_type * alloc_node( Args&&... args )
156 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
159 static void free_node( node_type * pNode )
161 cxx_allocator().Delete( pNode );
164 struct node_disposer {
165 void operator()( node_type * pNode )
170 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
174 return base_class::m_pHead;
177 head_type const& head() const
179 return base_class::m_pHead;
185 template <bool IsConst>
186 class iterator_type: protected base_class::template iterator_type<IsConst>
188 typedef typename base_class::template iterator_type<IsConst> iterator_base;
190 iterator_type( head_type const& pNode )
191 : iterator_base( pNode )
194 friend class MichaelList;
197 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
198 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
203 iterator_type( iterator_type const& src )
204 : iterator_base( src )
207 value_ptr operator ->() const
209 typename iterator_base::value_ptr p = iterator_base::operator ->();
210 return p ? &(p->m_Value) : nullptr;
213 value_ref operator *() const
215 return (iterator_base::operator *()).m_Value;
219 iterator_type& operator ++()
221 iterator_base::operator ++();
226 bool operator ==(iterator_type<C> const& i ) const
228 return iterator_base::operator ==(i);
231 bool operator !=(iterator_type<C> const& i ) const
233 return iterator_base::operator !=(i);
241 The forward iterator for Michael's list has some features:
242 - it has no post-increment operator
243 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
244 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
245 may be thrown if a limit of guard count per thread is exceeded.
246 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
247 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
248 deleting operations it is no guarantee that you iterate all item in the list.
250 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
251 for debug purpose only.
253 typedef iterator_type<false> iterator;
255 /// Const forward iterator
257 For iterator's features and requirements see \ref iterator
259 typedef iterator_type<true> const_iterator;
261 /// Returns a forward iterator addressing the first element in a list
263 For empty list \code begin() == end() \endcode
267 return iterator( head() );
270 /// Returns an iterator that addresses the location succeeding the last element in a list
272 Do not use the value returned by <tt>end</tt> function to access any item.
273 Internally, <tt>end</tt> returning value equals to \p nullptr.
275 The returned value can be used only to control reaching the end of the list.
276 For empty list \code begin() == end() \endcode
283 /// Returns a forward const iterator addressing the first element in a list
285 const_iterator begin() const
287 return const_iterator( head() );
289 const_iterator cbegin()
291 return const_iterator( head() );
295 /// Returns an const iterator that addresses the location succeeding the last element in a list
297 const_iterator end() const
299 return const_iterator();
301 const_iterator cend()
303 return const_iterator();
308 /// Default constructor
310 Initialize empty list
326 The function creates a node with copy of \p val value
327 and then inserts the node created into the list.
329 The type \p Q should contain as minimum the complete key of the node.
330 The object of \ref value_type should be constructible from \p val of type \p Q.
331 In trivial case, \p Q is equal to \ref value_type.
333 Returns \p true if inserting successful, \p false otherwise.
335 template <typename Q>
336 bool insert( Q const& val )
338 return insert_at( head(), val );
343 This function inserts new node with default-constructed value and then it calls
344 \p func functor with signature
345 \code void func( value_type& itemValue ) ;\endcode
347 The argument \p itemValue of user-defined functor \p func is the reference
348 to the list's item inserted. User-defined functor \p func should guarantee that during changing
349 item's value no any other changes could be made on this list's item by concurrent threads.
350 The user-defined functor can be passed by reference using \p std::ref
351 and it is called only if the inserting is success.
353 The type \p Q should contain the complete key of the node.
354 The object of \ref value_type should be constructible from \p key of type \p Q.
356 The function allows to split creating of new item into two part:
357 - create item from \p key with initializing key-fields only;
358 - insert new item into the list;
359 - if inserting is successful, initialize non-key fields of item by calling \p f functor
361 This can be useful if complete initialization of object of \p value_type is heavyweight and
362 it is preferable that the initialization should be completed only if inserting is successful.
364 template <typename Q, typename Func>
365 bool insert( Q const& key, Func func )
367 return insert_at( head(), key, func );
370 /// Ensures that the \p key exists in the list
372 The operation performs inserting or changing data with lock-free manner.
374 If the \p key not found in the list, then the new item created from \p key
375 is inserted into the list. Otherwise, the functor \p func is called with the item found.
376 The functor \p Func should be a function with signature:
378 void func( bool bNew, value_type& item, const Q& val );
383 void operator()( bool bNew, value_type& item, const Q& val );
388 - \p bNew - \p true if the item has been inserted, \p false otherwise
389 - \p item - item of the list
390 - \p val - argument \p key passed into the \p ensure function
392 The functor may change non-key fields of the \p item; however, \p func must guarantee
393 that during changing no any other modifications could be made on this item by concurrent threads.
395 You may pass \p func argument by reference by \p std::ref
397 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
398 \p second is true if new item has been added or \p false if the item with \p key
399 already is in the list.
401 template <typename Q, typename Func>
402 std::pair<bool, bool> ensure( Q const& key, Func f )
404 return ensure_at( head(), key, f );
407 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
409 Returns \p true if inserting successful, \p false otherwise.
411 template <typename... Args>
412 bool emplace( Args&&... args )
414 return emplace_at( head(), std::forward<Args>(args)... );
417 /// Delete \p key from the list
418 /** \anchor cds_nonintrusive_MichealList_hp_erase_val
419 Since the key of MichaelList's item type \p T is not explicitly specified,
420 template parameter \p Q defines the key type searching in the list.
421 The list item comparator should be able to compare the type \p T of list item
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_hp_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_hp_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 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_hp_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 the item from the list with specified \p key
487 /** \anchor cds_nonintrusive_MichaelList_hp_extract
488 The function searches an item with key equal to \p key,
489 unlinks it from the list, and returns it in \p dest parameter.
490 If the item with key equal to \p key is not found the function returns \p false.
492 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
494 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
498 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
502 ord_list::guarded_ptr gp;
503 theList.extract( gp, 5 );
507 // Destructor of gp releases internal HP guard and frees the item
511 template <typename Q>
512 bool extract( guarded_ptr& dest, Q const& key )
514 return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
517 /// Extracts the item from the list with comparing functor \p pred
519 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
520 but \p pred predicate is used for key comparing.
522 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
524 \p pred must imply the same element order as the comparator used for building the list.
526 template <typename Q, typename Less>
527 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
529 return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
532 /// Find the key \p key
533 /** \anchor cds_nonintrusive_MichaelList_hp_find_val
534 The function searches the item with key equal to \p key
535 and returns \p true if it is found, and \p false otherwise
537 template <typename Q>
538 bool find( Q const& key )
540 return find_at( head(), key, intrusive_key_comparator() );
543 /// Finds the key \p val using \p pred predicate for searching
545 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_val "find(Q const&)"
546 but \p pred is used for key comparing.
547 \p Less functor has the interface like \p std::less.
548 \p pred must imply the same element order as the comparator used for building the list.
550 template <typename Q, typename Less>
551 bool find_with( Q const& key, Less pred )
553 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
556 /// Find the key \p val and perform an action with it
557 /** \anchor cds_nonintrusive_MichaelList_hp_find_func
558 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
559 The interface of \p Func functor is:
562 void operator()( value_type& item, Q& val );
565 where \p item is the item found, \p val is the <tt>find</tt> function argument.
567 You may pass \p f argument by reference using \p std::ref
569 The functor may change non-key fields of \p item. Note that the function is only guarantee
570 that \p item cannot be deleted during functor is executing.
571 The function does not serialize simultaneous access to the list \p item. If such access is
572 possible you must provide your own synchronization schema to exclude unsafe item modifications.
574 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
575 may modify both arguments.
577 The function returns \p true if \p val is found, \p false otherwise.
579 template <typename Q, typename Func>
580 bool find( Q& val, Func f )
582 return find_at( head(), val, intrusive_key_comparator(), f );
585 /// Finds the key \p val using \p pred predicate for searching
587 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_func "find(Q&, Func)"
588 but \p pred is used for key comparing.
589 \p Less functor has the interface like \p std::less.
590 \p pred must imply the same element order as the comparator used for building the list.
592 template <typename Q, typename Less, typename Func>
593 bool find_with( Q& val, Less pred, Func f )
595 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
598 /// Find the key \p val and perform an action with it
599 /** \anchor cds_nonintrusive_MichaelList_hp_find_cfunc
600 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
601 The interface of \p Func functor is:
604 void operator()( value_type& item, Q const& val );
607 where \p item is the item found, \p val is the <tt>find</tt> function argument.
609 You may pass \p f argument by reference using \p std::ref
611 The functor may change non-key fields of \p item. Note that the function is only guarantee
612 that \p item cannot be deleted during functor is executing.
613 The function does not serialize simultaneous access to the list \p item. If such access is
614 possible you must provide your own synchronization schema to exclude unsafe item modifications.
616 The function returns \p true if \p val is found, \p false otherwise.
618 template <typename Q, typename Func>
619 bool find( Q const& val, Func f )
621 return find_at( head(), val, intrusive_key_comparator(), f );
624 /// Finds the key \p val using \p pred predicate for searching
626 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_cfunc "find(Q&, Func)"
627 but \p pred is used for key comparing.
628 \p Less functor has the interface like \p std::less.
629 \p pred must imply the same element order as the comparator used for building the list.
631 template <typename Q, typename Less, typename Func>
632 bool find_with( Q const& val, Less pred, Func f )
634 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
637 /// Finds the key \p val and return the item found
638 /** \anchor cds_nonintrusive_MichaelList_hp_get
639 The function searches the item with key equal to \p val
640 and assigns the item found to guarded pointer \p ptr.
641 The function returns \p true if \p val is found, and \p false otherwise.
642 If \p val is not found the \p ptr parameter is not changed.
644 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
648 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
652 ord_list::guarded_ptr gp;
653 if ( theList.get( gp, 5 )) {
657 // Destructor of guarded_ptr releases internal HP guard and frees the item
661 Note the compare functor specified for class \p Traits template parameter
662 should accept a parameter of type \p Q that can be not the same as \p value_type.
664 template <typename Q>
665 bool get( guarded_ptr& ptr, Q const& val )
667 return get_at( head(), ptr.guard(), val, intrusive_key_comparator() );
670 /// Finds the key \p val and return the item found
672 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
673 but \p pred is used for comparing the keys.
675 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
677 \p pred must imply the same element order as the comparator used for building the list.
679 template <typename Q, typename Less>
680 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
682 return get_at( head(), ptr.guard(), val, typename options::template less_wrapper<Less>::type() );
685 /// Check if the list is empty
688 return base_class::empty();
691 /// Returns list's item count
693 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
694 this function always returns 0.
696 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
697 is empty. To check list emptyness use \ref empty() method.
701 return base_class::size();
706 Post-condition: the list is empty
715 bool insert_node_at( head_type& refHead, node_type * pNode )
718 scoped_node_ptr p(pNode);
719 if ( base_class::insert_at( refHead, *pNode )) {
727 template <typename Q>
728 bool insert_at( head_type& refHead, Q const& val )
730 return insert_node_at( refHead, alloc_node( val ));
733 template <typename Q, typename Func>
734 bool insert_at( head_type& refHead, Q const& key, Func f )
736 scoped_node_ptr pNode( alloc_node( key ));
738 if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { f( node_to_value(node) ); } )) {
745 template <typename... Args>
746 bool emplace_at( head_type& refHead, Args&&... args )
748 return insert_node_at( refHead, alloc_node( std::forward<Args>(args) ... ));
751 template <typename Q, typename Compare, typename Func>
752 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
754 return base_class::erase_at( refHead, key, cmp, [&f](node_type const& node){ f( node_to_value(node) ); } );
757 template <typename Q, typename Compare>
758 bool extract_at( head_type& refHead, typename gc::Guard& dest, Q const& key, Compare cmp )
760 return base_class::extract_at( refHead, dest, key, cmp );
763 template <typename Q, typename Func>
764 std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
766 scoped_node_ptr pNode( alloc_node( key ));
768 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
769 [&f, &key](bool bNew, node_type& node, node_type&){ f( bNew, node_to_value(node), key ); });
770 if ( ret.first && ret.second )
776 template <typename Q, typename Compare>
777 bool find_at( head_type& refHead, Q const& key, Compare cmp )
779 return base_class::find_at( refHead, key, cmp );
782 template <typename Q, typename Compare, typename Func>
783 bool find_at( head_type& refHead, Q& val, Compare cmp, Func f )
785 return base_class::find_at( refHead, val, cmp, [&f](node_type& node, Q& v){ f( node_to_value(node), v ); });
788 template <typename Q, typename Compare>
789 bool get_at( head_type& refHead, typename gc::Guard& guard, Q const& key, Compare cmp )
791 return base_class::get_at( refHead, guard, key, cmp );
797 }} // namespace cds::container
799 #endif // #ifndef __CDS_CONTAINER_IMPL_MICHAEL_LIST_H