3 #ifndef __CDS_CONTAINER_MICHAEL_LIST_IMPL_H
4 #define __CDS_CONTAINER_MICHAEL_LIST_IMPL_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::PTB: \code #include <cds/container/michael_list_ptb.h> \endcode
86 - for gc::HRC: \code #include <cds/container/michael_list_hrc.h> \endcode
87 - for \ref cds_urcu_desc "RCU": \code #include <cds/container/michael_list_rcu.h> \endcode
88 - for gc::nogc: \code #include <cds/container/michael_list_nogc.h> \endcode
93 #ifdef CDS_DOXYGEN_INVOKED
94 typename Traits = michael_list::type_traits
100 #ifdef CDS_DOXYGEN_INVOKED
101 protected intrusive::MichaelList< GC, T, Traits >
103 protected details::make_michael_list< GC, T, Traits >::type
107 typedef details::make_michael_list< GC, T, Traits > options;
108 typedef typename options::type base_class;
112 typedef T value_type ; ///< Type of value stored in the list
113 typedef typename base_class::gc gc ; ///< Garbage collector used
114 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
115 typedef typename options::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
116 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
117 typedef typename options::key_comparator key_comparator ; ///< key comparison functor
118 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
122 typedef typename base_class::value_type node_type;
123 typedef typename options::cxx_allocator cxx_allocator;
124 typedef typename options::node_deallocator node_deallocator;
125 typedef typename options::type_traits::compare intrusive_key_comparator;
127 typedef typename base_class::atomic_node_ptr head_type;
128 # ifndef CDS_CXX11_LAMBDA_SUPPORT
129 typedef typename base_class::empty_erase_functor empty_erase_functor;
135 typedef cds::gc::guarded_ptr< gc, node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
139 static value_type& node_to_value( node_type& n )
143 static value_type const& node_to_value( node_type const& n )
148 # ifndef CDS_CXX11_LAMBDA_SUPPORT
149 template <typename Func>
150 struct insert_functor
154 insert_functor ( Func f )
158 void operator()( node_type& node )
160 cds::unref(m_func)( node_to_value(node) );
164 template <typename Q, typename Func>
165 struct ensure_functor
170 ensure_functor( Q const& arg, Func f )
175 void operator ()( bool bNew, node_type& node, node_type& )
177 cds::unref(m_func)( bNew, node_to_value(node), m_arg );
181 template <typename Func>
186 find_functor( Func f )
190 template <typename Q>
191 void operator ()( node_type& node, Q& val )
193 cds::unref(m_func)( node_to_value(node), val );
197 template <typename Func>
202 erase_functor( Func f )
206 void operator()( node_type const& node )
208 cds::unref(m_func)( node_to_value(node) );
211 #endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
216 template <typename Q>
217 static node_type * alloc_node( Q const& v )
219 return cxx_allocator().New( v );
222 # ifdef CDS_EMPLACE_SUPPORT
223 template <typename... Args>
224 static node_type * alloc_node( Args&&... args )
226 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
230 static void free_node( node_type * pNode )
232 cxx_allocator().Delete( pNode );
235 struct node_disposer {
236 void operator()( node_type * pNode )
241 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
245 return base_class::m_pHead;
248 head_type const& head() const
250 return base_class::m_pHead;
256 template <bool IsConst>
257 class iterator_type: protected base_class::template iterator_type<IsConst>
259 typedef typename base_class::template iterator_type<IsConst> iterator_base;
261 iterator_type( head_type const& pNode )
262 : iterator_base( pNode )
265 friend class MichaelList;
268 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
269 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
274 iterator_type( iterator_type const& src )
275 : iterator_base( src )
278 value_ptr operator ->() const
280 typename iterator_base::value_ptr p = iterator_base::operator ->();
281 return p ? &(p->m_Value) : reinterpret_cast<value_ptr>(NULL);
284 value_ref operator *() const
286 return (iterator_base::operator *()).m_Value;
290 iterator_type& operator ++()
292 iterator_base::operator ++();
297 bool operator ==(iterator_type<C> const& i ) const
299 return iterator_base::operator ==(i);
302 bool operator !=(iterator_type<C> const& i ) const
304 return iterator_base::operator !=(i);
312 The forward iterator for Michael's list has some features:
313 - it has no post-increment operator
314 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
315 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
316 may be thrown if a limit of guard count per thread is exceeded.
317 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
318 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
319 deleting operations it is no guarantee that you iterate all item in the list.
321 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
322 for debug purpose only.
324 typedef iterator_type<false> iterator;
326 /// Const forward iterator
328 For iterator's features and requirements see \ref iterator
330 typedef iterator_type<true> const_iterator;
332 /// Returns a forward iterator addressing the first element in a list
334 For empty list \code begin() == end() \endcode
338 return iterator( head() );
341 /// Returns an iterator that addresses the location succeeding the last element in a list
343 Do not use the value returned by <tt>end</tt> function to access any item.
344 Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
346 The returned value can be used only to control reaching the end of the list.
347 For empty list \code begin() == end() \endcode
354 /// Returns a forward const iterator addressing the first element in a list
356 const_iterator begin() const
358 return const_iterator( head() );
360 const_iterator cbegin()
362 return const_iterator( head() );
366 /// Returns an const iterator that addresses the location succeeding the last element in a list
368 const_iterator end() const
370 return const_iterator();
372 const_iterator cend()
374 return const_iterator();
379 /// Default constructor
381 Initialize empty list
397 The function creates a node with copy of \p val value
398 and then inserts the node created into the list.
400 The type \p Q should contain as minimum the complete key of the node.
401 The object of \ref value_type should be constructible from \p val of type \p Q.
402 In trivial case, \p Q is equal to \ref value_type.
404 Returns \p true if inserting successful, \p false otherwise.
406 template <typename Q>
407 bool insert( Q const& val )
409 return insert_at( head(), val );
414 This function inserts new node with default-constructed value and then it calls
415 \p func functor with signature
416 \code void func( value_type& itemValue ) ;\endcode
418 The argument \p itemValue of user-defined functor \p func is the reference
419 to the list's item inserted. User-defined functor \p func should guarantee that during changing
420 item's value no any other changes could be made on this list's item by concurrent threads.
421 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
422 and it is called only if the inserting is success.
424 The type \p Q should contain the complete key of the node.
425 The object of \ref value_type should be constructible from \p key of type \p Q.
427 The function allows to split creating of new item into two part:
428 - create item from \p key with initializing key-fields only;
429 - insert new item into the list;
430 - if inserting is successful, initialize non-key fields of item by calling \p f functor
432 This can be useful if complete initialization of object of \p value_type is heavyweight and
433 it is preferable that the initialization should be completed only if inserting is successful.
435 template <typename Q, typename Func>
436 bool insert( Q const& key, Func func )
438 return insert_at( head(), key, func );
441 /// Ensures that the \p key exists in the list
443 The operation performs inserting or changing data with lock-free manner.
445 If the \p key not found in the list, then the new item created from \p key
446 is inserted into the list. Otherwise, the functor \p func is called with the item found.
447 The functor \p Func should be a function with signature:
449 void func( bool bNew, value_type& item, const Q& val );
454 void operator()( bool bNew, value_type& item, const Q& val );
459 - \p bNew - \p true if the item has been inserted, \p false otherwise
460 - \p item - item of the list
461 - \p val - argument \p key passed into the \p ensure function
463 The functor may change non-key fields of the \p item; however, \p func must guarantee
464 that during changing no any other modifications could be made on this item by concurrent threads.
466 You may pass \p func argument by reference using <tt>boost::ref</tt>.
468 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
469 \p second is true if new item has been added or \p false if the item with \p key
470 already is in the list.
472 template <typename Q, typename Func>
473 std::pair<bool, bool> ensure( Q const& key, Func f )
475 return ensure_at( head(), key, f );
478 # ifdef CDS_EMPLACE_SUPPORT
479 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
481 Returns \p true if inserting successful, \p false otherwise.
483 This function is available only for compiler that supports
484 variadic template and move semantics
486 template <typename... Args>
487 bool emplace( Args&&... args )
489 return emplace_at( head(), std::forward<Args>(args)... );
493 /// Delete \p key from the list
494 /** \anchor cds_nonintrusive_MichealList_hp_erase_val
495 Since the key of MichaelList's item type \p T is not explicitly specified,
496 template parameter \p Q defines the key type searching in the list.
497 The list item comparator should be able to compare the type \p T of list item
500 Return \p true if key is found and deleted, \p false otherwise
502 template <typename Q>
503 bool erase( Q const& key )
505 # ifdef CDS_CXX11_LAMBDA_SUPPORT
506 return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
508 return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
512 /// Deletes the item from the list using \p pred predicate for searching
514 The function is an analog of \ref cds_nonintrusive_MichealList_hp_erase_val "erase(Q const&)"
515 but \p pred is used for key comparing.
516 \p Less functor has the interface like \p std::less.
517 \p pred must imply the same element order as the comparator used for building the list.
519 template <typename Q, typename Less>
520 bool erase_with( Q const& key, Less pred )
522 # ifdef CDS_CXX11_LAMBDA_SUPPORT
523 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), [](value_type const&){} );
525 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), empty_erase_functor() );
529 /// Deletes \p key from the list
530 /** \anchor cds_nonintrusive_MichaelList_hp_erase_func
531 The function searches an item with key \p key, calls \p f functor with item found
532 and deletes it. If \p key is not found, the functor is not called.
534 The functor \p Func interface:
537 void operator()(const value_type& val) { ... }
540 The functor may be passed by reference with <tt>boost:ref</tt>
542 Since the key of MichaelList's item type \p T is not explicitly specified,
543 template parameter \p Q defines the key type searching in the list.
544 The list item comparator should be able to compare the type \p T of list item
547 Return \p true if key is found and deleted, \p false otherwise
551 template <typename Q, typename Func>
552 bool erase( Q const& key, Func f )
554 return erase_at( head(), key, intrusive_key_comparator(), f );
557 /// Deletes the item from the list using \p pred predicate for searching
559 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
560 but \p pred is used for key comparing.
561 \p Less functor has the interface like \p std::less.
562 \p pred must imply the same element order as the comparator used for building the list.
564 template <typename Q, typename Less, typename Func>
565 bool erase_with( Q const& key, Less pred, Func f )
567 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
570 /// Extracts the item from the list with specified \p key
571 /** \anchor cds_nonintrusive_MichaelList_hp_extract
572 The function searches an item with key equal to \p key,
573 unlinks it from the list, and returns it in \p dest parameter.
574 If the item with key equal to \p key is not found the function returns \p false.
576 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
578 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
582 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
586 ord_list::guarded_ptr gp;
587 theList.extract( gp, 5 );
591 // Destructor of gp releases internal HP guard and frees the item
595 template <typename Q>
596 bool extract( guarded_ptr& dest, Q const& key )
598 return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
601 /// Extracts the item from the list with comparing functor \p pred
603 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
604 but \p pred predicate is used for key comparing.
606 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
608 \p pred must imply the same element order as the comparator used for building the list.
610 template <typename Q, typename Less>
611 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
613 return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
616 /// Find the key \p key
617 /** \anchor cds_nonintrusive_MichaelList_hp_find_val
618 The function searches the item with key equal to \p key
619 and returns \p true if it is found, and \p false otherwise
621 template <typename Q>
622 bool find( Q const& key )
624 return find_at( head(), key, intrusive_key_comparator() );
627 /// Finds the key \p val using \p pred predicate for searching
629 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_val "find(Q const&)"
630 but \p pred is used for key comparing.
631 \p Less functor has the interface like \p std::less.
632 \p pred must imply the same element order as the comparator used for building the list.
634 template <typename Q, typename Less>
635 bool find_with( Q const& key, Less pred )
637 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
640 /// Find the key \p val and perform an action with it
641 /** \anchor cds_nonintrusive_MichaelList_hp_find_func
642 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
643 The interface of \p Func functor is:
646 void operator()( value_type& item, Q& val );
649 where \p item is the item found, \p val is the <tt>find</tt> function argument.
651 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
653 The functor may change non-key fields of \p item. Note that the function is only guarantee
654 that \p item cannot be deleted during functor is executing.
655 The function does not serialize simultaneous access to the list \p item. If such access is
656 possible you must provide your own synchronization schema to exclude unsafe item modifications.
658 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
659 may modify both arguments.
661 The function returns \p true if \p val is found, \p false otherwise.
663 template <typename Q, typename Func>
664 bool find( Q& val, Func f )
666 return find_at( head(), val, intrusive_key_comparator(), f );
669 /// Finds the key \p val using \p pred predicate for searching
671 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_func "find(Q&, Func)"
672 but \p pred is used for key comparing.
673 \p Less functor has the interface like \p std::less.
674 \p pred must imply the same element order as the comparator used for building the list.
676 template <typename Q, typename Less, typename Func>
677 bool find_with( Q& val, Less pred, Func f )
679 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
682 /// Find the key \p val and perform an action with it
683 /** \anchor cds_nonintrusive_MichaelList_hp_find_cfunc
684 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
685 The interface of \p Func functor is:
688 void operator()( value_type& item, Q const& val );
691 where \p item is the item found, \p val is the <tt>find</tt> function argument.
693 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
695 The functor may change non-key fields of \p item. Note that the function is only guarantee
696 that \p item cannot be deleted during functor is executing.
697 The function does not serialize simultaneous access to the list \p item. If such access is
698 possible you must provide your own synchronization schema to exclude unsafe item modifications.
700 The function returns \p true if \p val is found, \p false otherwise.
702 template <typename Q, typename Func>
703 bool find( Q const& val, Func f )
705 return find_at( head(), val, intrusive_key_comparator(), f );
708 /// Finds the key \p val using \p pred predicate for searching
710 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_cfunc "find(Q&, Func)"
711 but \p pred is used for key comparing.
712 \p Less functor has the interface like \p std::less.
713 \p pred must imply the same element order as the comparator used for building the list.
715 template <typename Q, typename Less, typename Func>
716 bool find_with( Q const& val, Less pred, Func f )
718 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
721 /// Finds the key \p val and return the item found
722 /** \anchor cds_nonintrusive_MichaelList_hp_get
723 The function searches the item with key equal to \p val
724 and assigns the item found to guarded pointer \p ptr.
725 The function returns \p true if \p val is found, and \p false otherwise.
726 If \p val is not found the \p ptr parameter is not changed.
728 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
732 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
736 ord_list::guarded_ptr gp;
737 if ( theList.get( gp, 5 )) {
741 // Destructor of guarded_ptr releases internal HP guard and frees the item
745 Note the compare functor specified for class \p Traits template parameter
746 should accept a parameter of type \p Q that can be not the same as \p value_type.
748 template <typename Q>
749 bool get( guarded_ptr& ptr, Q const& val )
751 return get_at( head(), ptr.guard(), val, intrusive_key_comparator() );
754 /// Finds the key \p val and return the item found
756 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
757 but \p pred is used for comparing the keys.
759 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
761 \p pred must imply the same element order as the comparator used for building the list.
763 template <typename Q, typename Less>
764 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
766 return get_at( head(), ptr.guard(), val, typename options::template less_wrapper<Less>::type() );
769 /// Check if the list is empty
772 return base_class::empty();
775 /// Returns list's item count
777 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
778 this function always returns 0.
780 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
781 is empty. To check list emptyness use \ref empty() method.
785 return base_class::size();
790 Post-condition: the list is empty
799 bool insert_node_at( head_type& refHead, node_type * pNode )
801 assert( pNode != NULL );
802 scoped_node_ptr p(pNode);
803 if ( base_class::insert_at( refHead, *pNode )) {
811 template <typename Q>
812 bool insert_at( head_type& refHead, Q const& val )
814 return insert_node_at( refHead, alloc_node( val ));
817 template <typename Q, typename Func>
818 bool insert_at( head_type& refHead, Q const& key, Func f )
820 scoped_node_ptr pNode( alloc_node( key ));
822 # ifdef CDS_CXX11_LAMBDA_SUPPORT
823 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
824 // GCC 4.5,4.6,4.7: node_to_value is unaccessible from lambda,
825 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
826 value_type& (* n2v)( node_type& ) = node_to_value;
827 if ( base_class::insert_at( refHead, *pNode, [&f, n2v]( node_type& node ) { cds::unref(f)( n2v(node) ); } ))
829 if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { cds::unref(f)( node_to_value(node) ); } ))
832 insert_functor<Func> wrapper( f );
833 if ( base_class::insert_at( refHead, *pNode, cds::ref(wrapper) ))
842 # ifdef CDS_EMPLACE_SUPPORT
843 template <typename... Args>
844 bool emplace_at( head_type& refHead, Args&&... args )
846 return insert_node_at( refHead, alloc_node( std::forward<Args>(args) ... ));
850 template <typename Q, typename Compare, typename Func>
851 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
853 # ifdef CDS_CXX11_LAMBDA_SUPPORT
854 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
855 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
856 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
857 value_type const& (* n2v)( node_type const& ) = node_to_value;
858 return base_class::erase_at( refHead, key, cmp, [&f,n2v](node_type const& node){ cds::unref(f)( n2v(node) ); } );
860 return base_class::erase_at( refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
863 erase_functor<Func> wrapper( f );
864 return base_class::erase_at( refHead, key, cmp, cds::ref(wrapper) );
868 template <typename Q, typename Compare>
869 bool extract_at( head_type& refHead, typename gc::Guard& dest, Q const& key, Compare cmp )
871 return base_class::extract_at( refHead, dest, key, cmp );
874 template <typename Q, typename Func>
875 std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
877 scoped_node_ptr pNode( alloc_node( key ));
879 # ifdef CDS_CXX11_LAMBDA_SUPPORT
880 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
881 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
882 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
883 value_type& (* n2v)( node_type& ) = node_to_value;
884 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
885 [&f, &key, n2v](bool bNew, node_type& node, node_type&){ cds::unref(f)( bNew, n2v(node), key ); });
887 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
888 [&f, &key](bool bNew, node_type& node, node_type&){ cds::unref(f)( bNew, node_to_value(node), key ); });
891 ensure_functor<Q, Func> wrapper( key, f );
892 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, cds::ref(wrapper));
894 if ( ret.first && ret.second )
900 template <typename Q, typename Compare>
901 bool find_at( head_type& refHead, Q const& key, Compare cmp )
903 return base_class::find_at( refHead, key, cmp );
906 template <typename Q, typename Compare, typename Func>
907 bool find_at( head_type& refHead, Q& val, Compare cmp, Func f )
909 # ifdef CDS_CXX11_LAMBDA_SUPPORT
910 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
911 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
912 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
913 value_type& (* n2v)( node_type& ) = node_to_value;
914 return base_class::find_at( refHead, val, cmp, [&f, n2v](node_type& node, Q& v){ cds::unref(f)( n2v(node), v ); });
916 return base_class::find_at( refHead, val, cmp, [&f](node_type& node, Q& v){ cds::unref(f)( node_to_value(node), v ); });
919 find_functor<Func> wrapper( f );
920 return base_class::find_at( refHead, val, cmp, cds::ref(wrapper) );
924 template <typename Q, typename Compare>
925 bool get_at( head_type& refHead, typename gc::Guard& guard, Q const& key, Compare cmp )
927 return base_class::get_at( refHead, guard, key, cmp );
933 }} // namespace cds::container
935 #endif // #ifndef __CDS_CONTAINER_MICHAEL_LIST_IMPL_H