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 template <typename... Args>
223 static node_type * alloc_node( Args&&... args )
225 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
228 static void free_node( node_type * pNode )
230 cxx_allocator().Delete( pNode );
233 struct node_disposer {
234 void operator()( node_type * pNode )
239 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
243 return base_class::m_pHead;
246 head_type const& head() const
248 return base_class::m_pHead;
254 template <bool IsConst>
255 class iterator_type: protected base_class::template iterator_type<IsConst>
257 typedef typename base_class::template iterator_type<IsConst> iterator_base;
259 iterator_type( head_type const& pNode )
260 : iterator_base( pNode )
263 friend class MichaelList;
266 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
267 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
272 iterator_type( iterator_type const& src )
273 : iterator_base( src )
276 value_ptr operator ->() const
278 typename iterator_base::value_ptr p = iterator_base::operator ->();
279 return p ? &(p->m_Value) : nullptr;
282 value_ref operator *() const
284 return (iterator_base::operator *()).m_Value;
288 iterator_type& operator ++()
290 iterator_base::operator ++();
295 bool operator ==(iterator_type<C> const& i ) const
297 return iterator_base::operator ==(i);
300 bool operator !=(iterator_type<C> const& i ) const
302 return iterator_base::operator !=(i);
310 The forward iterator for Michael's list has some features:
311 - it has no post-increment operator
312 - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
313 For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
314 may be thrown if a limit of guard count per thread is exceeded.
315 - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
316 - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
317 deleting operations it is no guarantee that you iterate all item in the list.
319 Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
320 for debug purpose only.
322 typedef iterator_type<false> iterator;
324 /// Const forward iterator
326 For iterator's features and requirements see \ref iterator
328 typedef iterator_type<true> const_iterator;
330 /// Returns a forward iterator addressing the first element in a list
332 For empty list \code begin() == end() \endcode
336 return iterator( head() );
339 /// Returns an iterator that addresses the location succeeding the last element in a list
341 Do not use the value returned by <tt>end</tt> function to access any item.
342 Internally, <tt>end</tt> returning value equals to \p nullptr.
344 The returned value can be used only to control reaching the end of the list.
345 For empty list \code begin() == end() \endcode
352 /// Returns a forward const iterator addressing the first element in a list
354 const_iterator begin() const
356 return const_iterator( head() );
358 const_iterator cbegin()
360 return const_iterator( head() );
364 /// Returns an const iterator that addresses the location succeeding the last element in a list
366 const_iterator end() const
368 return const_iterator();
370 const_iterator cend()
372 return const_iterator();
377 /// Default constructor
379 Initialize empty list
395 The function creates a node with copy of \p val value
396 and then inserts the node created into the list.
398 The type \p Q should contain as minimum the complete key of the node.
399 The object of \ref value_type should be constructible from \p val of type \p Q.
400 In trivial case, \p Q is equal to \ref value_type.
402 Returns \p true if inserting successful, \p false otherwise.
404 template <typename Q>
405 bool insert( Q const& val )
407 return insert_at( head(), val );
412 This function inserts new node with default-constructed value and then it calls
413 \p func functor with signature
414 \code void func( value_type& itemValue ) ;\endcode
416 The argument \p itemValue of user-defined functor \p func is the reference
417 to the list's item inserted. User-defined functor \p func should guarantee that during changing
418 item's value no any other changes could be made on this list's item by concurrent threads.
419 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
420 and it is called only if the inserting is success.
422 The type \p Q should contain the complete key of the node.
423 The object of \ref value_type should be constructible from \p key of type \p Q.
425 The function allows to split creating of new item into two part:
426 - create item from \p key with initializing key-fields only;
427 - insert new item into the list;
428 - if inserting is successful, initialize non-key fields of item by calling \p f functor
430 This can be useful if complete initialization of object of \p value_type is heavyweight and
431 it is preferable that the initialization should be completed only if inserting is successful.
433 template <typename Q, typename Func>
434 bool insert( Q const& key, Func func )
436 return insert_at( head(), key, func );
439 /// Ensures that the \p key exists in the list
441 The operation performs inserting or changing data with lock-free manner.
443 If the \p key not found in the list, then the new item created from \p key
444 is inserted into the list. Otherwise, the functor \p func is called with the item found.
445 The functor \p Func should be a function with signature:
447 void func( bool bNew, value_type& item, const Q& val );
452 void operator()( bool bNew, value_type& item, const Q& val );
457 - \p bNew - \p true if the item has been inserted, \p false otherwise
458 - \p item - item of the list
459 - \p val - argument \p key passed into the \p ensure function
461 The functor may change non-key fields of the \p item; however, \p func must guarantee
462 that during changing no any other modifications could be made on this item by concurrent threads.
464 You may pass \p func argument by reference using <tt>boost::ref</tt>.
466 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
467 \p second is true if new item has been added or \p false if the item with \p key
468 already is in the list.
470 template <typename Q, typename Func>
471 std::pair<bool, bool> ensure( Q const& key, Func f )
473 return ensure_at( head(), key, f );
476 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
478 Returns \p true if inserting successful, \p false otherwise.
480 template <typename... Args>
481 bool emplace( Args&&... args )
483 return emplace_at( head(), std::forward<Args>(args)... );
486 /// Delete \p key from the list
487 /** \anchor cds_nonintrusive_MichealList_hp_erase_val
488 Since the key of MichaelList's item type \p T is not explicitly specified,
489 template parameter \p Q defines the key type searching in the list.
490 The list item comparator should be able to compare the type \p T of list item
493 Return \p true if key is found and deleted, \p false otherwise
495 template <typename Q>
496 bool erase( Q const& key )
498 # ifdef CDS_CXX11_LAMBDA_SUPPORT
499 return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
501 return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
505 /// Deletes the item from the list using \p pred predicate for searching
507 The function is an analog of \ref cds_nonintrusive_MichealList_hp_erase_val "erase(Q const&)"
508 but \p pred is used for key comparing.
509 \p Less functor has the interface like \p std::less.
510 \p pred must imply the same element order as the comparator used for building the list.
512 template <typename Q, typename Less>
513 bool erase_with( Q const& key, Less pred )
515 # ifdef CDS_CXX11_LAMBDA_SUPPORT
516 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), [](value_type const&){} );
518 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), empty_erase_functor() );
522 /// Deletes \p key from the list
523 /** \anchor cds_nonintrusive_MichaelList_hp_erase_func
524 The function searches an item with key \p key, calls \p f functor with item found
525 and deletes it. If \p key is not found, the functor is not called.
527 The functor \p Func interface:
530 void operator()(const value_type& val) { ... }
533 The functor may be passed by reference with <tt>boost:ref</tt>
535 Since the key of MichaelList's item type \p T is not explicitly specified,
536 template parameter \p Q defines the key type searching in the list.
537 The list item comparator should be able to compare the type \p T of list item
540 Return \p true if key is found and deleted, \p false otherwise
544 template <typename Q, typename Func>
545 bool erase( Q const& key, Func f )
547 return erase_at( head(), key, intrusive_key_comparator(), f );
550 /// Deletes the item from the list using \p pred predicate for searching
552 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
553 but \p pred is used for key comparing.
554 \p Less functor has the interface like \p std::less.
555 \p pred must imply the same element order as the comparator used for building the list.
557 template <typename Q, typename Less, typename Func>
558 bool erase_with( Q const& key, Less pred, Func f )
560 return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
563 /// Extracts the item from the list with specified \p key
564 /** \anchor cds_nonintrusive_MichaelList_hp_extract
565 The function searches an item with key equal to \p key,
566 unlinks it from the list, and returns it in \p dest parameter.
567 If the item with key equal to \p key is not found the function returns \p false.
569 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
571 @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
575 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
579 ord_list::guarded_ptr gp;
580 theList.extract( gp, 5 );
584 // Destructor of gp releases internal HP guard and frees the item
588 template <typename Q>
589 bool extract( guarded_ptr& dest, Q const& key )
591 return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
594 /// Extracts the item from the list with comparing functor \p pred
596 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
597 but \p pred predicate is used for key comparing.
599 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
601 \p pred must imply the same element order as the comparator used for building the list.
603 template <typename Q, typename Less>
604 bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
606 return extract_at( head(), dest.guard(), key, typename options::template less_wrapper<Less>::type() );
609 /// Find the key \p key
610 /** \anchor cds_nonintrusive_MichaelList_hp_find_val
611 The function searches the item with key equal to \p key
612 and returns \p true if it is found, and \p false otherwise
614 template <typename Q>
615 bool find( Q const& key )
617 return find_at( head(), key, intrusive_key_comparator() );
620 /// Finds the key \p val using \p pred predicate for searching
622 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_val "find(Q const&)"
623 but \p pred is used for key comparing.
624 \p Less functor has the interface like \p std::less.
625 \p pred must imply the same element order as the comparator used for building the list.
627 template <typename Q, typename Less>
628 bool find_with( Q const& key, Less pred )
630 return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
633 /// Find the key \p val and perform an action with it
634 /** \anchor cds_nonintrusive_MichaelList_hp_find_func
635 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
636 The interface of \p Func functor is:
639 void operator()( value_type& item, Q& val );
642 where \p item is the item found, \p val is the <tt>find</tt> function argument.
644 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
646 The functor may change non-key fields of \p item. Note that the function is only guarantee
647 that \p item cannot be deleted during functor is executing.
648 The function does not serialize simultaneous access to the list \p item. If such access is
649 possible you must provide your own synchronization schema to exclude unsafe item modifications.
651 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
652 may modify both arguments.
654 The function returns \p true if \p val is found, \p false otherwise.
656 template <typename Q, typename Func>
657 bool find( Q& val, Func f )
659 return find_at( head(), val, intrusive_key_comparator(), f );
662 /// Finds the key \p val using \p pred predicate for searching
664 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_func "find(Q&, Func)"
665 but \p pred is used for key comparing.
666 \p Less functor has the interface like \p std::less.
667 \p pred must imply the same element order as the comparator used for building the list.
669 template <typename Q, typename Less, typename Func>
670 bool find_with( Q& val, Less pred, Func f )
672 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
675 /// Find the key \p val and perform an action with it
676 /** \anchor cds_nonintrusive_MichaelList_hp_find_cfunc
677 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
678 The interface of \p Func functor is:
681 void operator()( value_type& item, Q const& val );
684 where \p item is the item found, \p val is the <tt>find</tt> function argument.
686 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
688 The functor may change non-key fields of \p item. Note that the function is only guarantee
689 that \p item cannot be deleted during functor is executing.
690 The function does not serialize simultaneous access to the list \p item. If such access is
691 possible you must provide your own synchronization schema to exclude unsafe item modifications.
693 The function returns \p true if \p val is found, \p false otherwise.
695 template <typename Q, typename Func>
696 bool find( Q const& val, Func f )
698 return find_at( head(), val, intrusive_key_comparator(), f );
701 /// Finds the key \p val using \p pred predicate for searching
703 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_find_cfunc "find(Q&, Func)"
704 but \p pred is used for key comparing.
705 \p Less functor has the interface like \p std::less.
706 \p pred must imply the same element order as the comparator used for building the list.
708 template <typename Q, typename Less, typename Func>
709 bool find_with( Q const& val, Less pred, Func f )
711 return find_at( head(), val, typename options::template less_wrapper<Less>::type(), f );
714 /// Finds the key \p val and return the item found
715 /** \anchor cds_nonintrusive_MichaelList_hp_get
716 The function searches the item with key equal to \p val
717 and assigns the item found to guarded pointer \p ptr.
718 The function returns \p true if \p val is found, and \p false otherwise.
719 If \p val is not found the \p ptr parameter is not changed.
721 @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
725 typedef cds::container::MichaelList< cds::gc::HP, foo, my_traits > ord_list;
729 ord_list::guarded_ptr gp;
730 if ( theList.get( gp, 5 )) {
734 // Destructor of guarded_ptr releases internal HP guard and frees the item
738 Note the compare functor specified for class \p Traits template parameter
739 should accept a parameter of type \p Q that can be not the same as \p value_type.
741 template <typename Q>
742 bool get( guarded_ptr& ptr, Q const& val )
744 return get_at( head(), ptr.guard(), val, intrusive_key_comparator() );
747 /// Finds the key \p val and return the item found
749 The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
750 but \p pred is used for comparing the keys.
752 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
754 \p pred must imply the same element order as the comparator used for building the list.
756 template <typename Q, typename Less>
757 bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
759 return get_at( head(), ptr.guard(), val, typename options::template less_wrapper<Less>::type() );
762 /// Check if the list is empty
765 return base_class::empty();
768 /// Returns list's item count
770 The value returned depends on opt::item_counter option. For atomics::empty_item_counter,
771 this function always returns 0.
773 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
774 is empty. To check list emptyness use \ref empty() method.
778 return base_class::size();
783 Post-condition: the list is empty
792 bool insert_node_at( head_type& refHead, node_type * pNode )
795 scoped_node_ptr p(pNode);
796 if ( base_class::insert_at( refHead, *pNode )) {
804 template <typename Q>
805 bool insert_at( head_type& refHead, Q const& val )
807 return insert_node_at( refHead, alloc_node( val ));
810 template <typename Q, typename Func>
811 bool insert_at( head_type& refHead, Q const& key, Func f )
813 scoped_node_ptr pNode( alloc_node( key ));
815 # ifdef CDS_CXX11_LAMBDA_SUPPORT
816 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
817 // GCC 4.5,4.6,4.7: node_to_value is unaccessible from lambda,
818 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
819 value_type& (* n2v)( node_type& ) = node_to_value;
820 if ( base_class::insert_at( refHead, *pNode, [&f, n2v]( node_type& node ) { cds::unref(f)( n2v(node) ); } ))
822 if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { cds::unref(f)( node_to_value(node) ); } ))
825 insert_functor<Func> wrapper( f );
826 if ( base_class::insert_at( refHead, *pNode, cds::ref(wrapper) ))
835 template <typename... Args>
836 bool emplace_at( head_type& refHead, Args&&... args )
838 return insert_node_at( refHead, alloc_node( std::forward<Args>(args) ... ));
841 template <typename Q, typename Compare, typename Func>
842 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
844 # ifdef CDS_CXX11_LAMBDA_SUPPORT
845 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
846 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
847 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
848 value_type const& (* n2v)( node_type const& ) = node_to_value;
849 return base_class::erase_at( refHead, key, cmp, [&f,n2v](node_type const& node){ cds::unref(f)( n2v(node) ); } );
851 return base_class::erase_at( refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
854 erase_functor<Func> wrapper( f );
855 return base_class::erase_at( refHead, key, cmp, cds::ref(wrapper) );
859 template <typename Q, typename Compare>
860 bool extract_at( head_type& refHead, typename gc::Guard& dest, Q const& key, Compare cmp )
862 return base_class::extract_at( refHead, dest, key, cmp );
865 template <typename Q, typename Func>
866 std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
868 scoped_node_ptr pNode( alloc_node( key ));
870 # ifdef CDS_CXX11_LAMBDA_SUPPORT
871 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
872 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
873 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
874 value_type& (* n2v)( node_type& ) = node_to_value;
875 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
876 [&f, &key, n2v](bool bNew, node_type& node, node_type&){ cds::unref(f)( bNew, n2v(node), key ); });
878 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
879 [&f, &key](bool bNew, node_type& node, node_type&){ cds::unref(f)( bNew, node_to_value(node), key ); });
882 ensure_functor<Q, Func> wrapper( key, f );
883 std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, cds::ref(wrapper));
885 if ( ret.first && ret.second )
891 template <typename Q, typename Compare>
892 bool find_at( head_type& refHead, Q const& key, Compare cmp )
894 return base_class::find_at( refHead, key, cmp );
897 template <typename Q, typename Compare, typename Func>
898 bool find_at( head_type& refHead, Q& val, Compare cmp, Func f )
900 # ifdef CDS_CXX11_LAMBDA_SUPPORT
901 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
902 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
903 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
904 value_type& (* n2v)( node_type& ) = node_to_value;
905 return base_class::find_at( refHead, val, cmp, [&f, n2v](node_type& node, Q& v){ cds::unref(f)( n2v(node), v ); });
907 return base_class::find_at( refHead, val, cmp, [&f](node_type& node, Q& v){ cds::unref(f)( node_to_value(node), v ); });
910 find_functor<Func> wrapper( f );
911 return base_class::find_at( refHead, val, cmp, cds::ref(wrapper) );
915 template <typename Q, typename Compare>
916 bool get_at( head_type& refHead, typename gc::Guard& guard, Q const& key, Compare cmp )
918 return base_class::get_at( refHead, guard, key, cmp );
924 }} // namespace cds::container
926 #endif // #ifndef __CDS_CONTAINER_MICHAEL_LIST_IMPL_H