3 #ifndef __CDS_CONTAINER_LAZY_LIST_RCU_H
4 #define __CDS_CONTAINER_LAZY_LIST_RCU_H
7 #include <cds/container/lazy_list_base.h>
8 #include <cds/intrusive/lazy_list_rcu.h>
9 #include <cds/details/binary_functor_wrapper.h>
10 #include <cds/container/details/make_lazy_list.h>
12 namespace cds { namespace container {
14 /// Lazy ordered list (template specialization for \ref cds_urcu_desc "RCU")
15 /** @ingroup cds_nonintrusive_list
16 \anchor cds_nonintrusive_LazyList_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 - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
23 "A Lazy Concurrent List-Based Set Algorithm"
25 The lazy list is based on an optimistic locking scheme for inserts and removes,
26 eliminating the need to use the equivalent of an atomically markable
27 reference. It also has a novel wait-free membership \p find operation
28 that does not need to perform cleanup operations and is more efficient.
30 It is non-intrusive version of cds::intrusive::LazyList class
33 - \p RCU - one of \ref cds_urcu_gc "RCU type"
34 - \p T - type stored in the list. The type must be default- and copy-constructible.
35 - \p Traits - type traits, default is lazy_list::type_traits
37 The implementation does not divide type \p T into key and value part and
38 may be used as main building block for hash set containers.
39 The key is a function (or a part) of type \p T, and this function is specified by <tt> Traits::compare </tt> functor
40 or <tt> Traits::less </tt> predicate
42 \ref cds_nonintrusive_LazyKVList_rcu "LazyKVList" is a key-value version
43 of lazy non-intrusive list that is closer to the C++ std library approach.
45 @note Before including <tt><cds/container/lazy_list_rcu.h></tt> you should include
46 appropriate RCU header file, see \ref cds_urcu_gc "RCU type" for list
47 of existing RCU class and corresponding header files.
49 It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
50 argument. For example, the following traits-based declaration of gc::HP lazy list
52 #include <cds/urcu/general_instant.h>
53 #include <cds/container/lazy_list_rcu.h>
54 // Declare comparator for the item
56 int operator ()( int i1, int i2 )
62 // Declare type_traits
63 struct my_traits: public cds::container::lazy_list::type_traits
65 typedef my_compare compare;
68 // Declare traits-based list
69 typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_instant<> >, int, my_traits > traits_based_list;
72 is equivalent for the following option-based list
74 #include <cds/urcu/general_instant.h>
75 #include <cds/container/lazy_list_rcu.h>
77 // my_compare is the same
79 // Declare option-based list
80 typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_instant<> >, int,
81 typename cds::container::lazy_list::make_traits<
82 cds::container::opt::compare< my_compare > // item comparator option
87 Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
88 - opt::lock_type - lock type for per-node locking. Default is cds::lock::Spin. Note that <b>each</b> node
89 of the list has member of type \p lock_type, therefore, heavy-weighted locking primitive is not
90 acceptable as candidate for \p lock_type.
91 - opt::compare - key comparison functor. No default functor is provided.
92 If the option is not specified, the opt::less is used.
93 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
94 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
95 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
96 - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
97 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
98 or opt::v::sequential_consistent (sequentially consisnent memory model).
99 - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
104 #ifdef CDS_DOXYGEN_INVOKED
105 typename Traits = lazy_list::type_traits
110 class LazyList< cds::urcu::gc<RCU>, T, Traits >:
111 #ifdef CDS_DOXYGEN_INVOKED
112 protected intrusive::LazyList< cds::urcu::gc<RCU>, T, Traits >
114 protected details::make_lazy_list< cds::urcu::gc<RCU>, T, Traits >::type
118 typedef details::make_lazy_list< cds::urcu::gc<RCU>, T, Traits > maker;
119 typedef typename maker::type base_class;
123 typedef T value_type ; ///< Type of value stored in the list
124 typedef typename base_class::gc gc ; ///< Garbage collector used
125 typedef typename base_class::back_off back_off ; ///< Back-off strategy used
126 typedef typename maker::allocator_type allocator_type ; ///< Allocator type used for allocate/deallocate the nodes
127 typedef typename base_class::item_counter item_counter ; ///< Item counting policy used
128 typedef typename maker::key_comparator key_comparator ; ///< key compare functor
129 typedef typename base_class::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
130 typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< Deadlock checking policy
132 typedef typename gc::scoped_lock rcu_lock ; ///< RCU scoped lock
133 static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
137 typedef typename base_class::value_type node_type;
138 typedef typename maker::cxx_allocator cxx_allocator;
139 typedef typename maker::node_deallocator node_deallocator;
140 typedef typename maker::type_traits::compare intrusive_key_comparator;
142 typedef typename base_class::node_type head_type;
143 # ifndef CDS_CXX11_LAMBDA_SUPPORT
144 typedef typename base_class::empty_erase_functor empty_erase_functor;
149 typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::type_traits::disposer > exempt_ptr; ///< pointer to extracted node
153 static value_type& node_to_value( node_type& n )
157 static value_type const& node_to_value( node_type const& n )
162 # ifndef CDS_CXX11_LAMBDA_SUPPORT
163 template <typename Func>
164 struct insert_functor
168 insert_functor ( Func f )
172 void operator()( node_type& node )
174 cds::unref(m_func)( node_to_value(node) );
178 template <typename Q, typename Func>
179 struct ensure_functor
184 ensure_functor( Q const& arg, Func f )
189 void operator ()( bool bNew, node_type& node, node_type& )
191 cds::unref(m_func)( bNew, node_to_value(node), m_arg );
195 template <typename Func>
200 find_functor( Func f )
204 template <typename Q>
205 void operator ()( node_type& node, Q& val )
207 cds::unref(m_func)( node_to_value(node), val );
211 struct empty_find_functor
213 template <typename Q>
214 void operator ()( node_type& node, Q& val ) const
218 template <typename Func>
223 erase_functor( Func f )
227 void operator()( node_type const& node )
229 cds::unref(m_func)( node_to_value(node) );
232 # endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
237 template <typename Q>
238 static node_type * alloc_node( Q const& v )
240 return cxx_allocator().New( v );
243 # ifdef CDS_EMPLACE_SUPPORT
244 template <typename... Args>
245 static node_type * alloc_node( Args&&... args )
247 return cxx_allocator().MoveNew( std::forward<Args>(args)... );
251 static void free_node( node_type * pNode )
253 cxx_allocator().Delete( pNode );
256 struct node_disposer {
257 void operator()( node_type * pNode )
262 typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
266 return base_class::m_Head;
269 head_type& head() const
271 return const_cast<head_type&>( base_class::m_Head );
276 return base_class::m_Tail;
279 head_type const& tail() const
281 return base_class::m_Tail;
287 template <bool IsConst>
288 class iterator_type: protected base_class::template iterator_type<IsConst>
290 typedef typename base_class::template iterator_type<IsConst> iterator_base;
292 iterator_type( head_type const& pNode )
293 : iterator_base( const_cast<head_type *>( &pNode ))
296 iterator_type( head_type const * pNode )
297 : iterator_base( const_cast<head_type *>( pNode ))
300 friend class LazyList;
303 typedef typename cds::details::make_const_type<value_type, IsConst>::pointer value_ptr;
304 typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
309 iterator_type( iterator_type const& src )
310 : iterator_base( src )
313 value_ptr operator ->() const
315 typename iterator_base::value_ptr p = iterator_base::operator ->();
316 return p ? &(p->m_Value) : nullptr;
319 value_ref operator *() const
321 return (iterator_base::operator *()).m_Value;
325 iterator_type& operator ++()
327 iterator_base::operator ++();
332 bool operator ==(iterator_type<C> const& i ) const
334 return iterator_base::operator ==(i);
337 bool operator !=(iterator_type<C> const& i ) const
339 return iterator_base::operator !=(i);
346 typedef iterator_type<false> iterator;
348 /// Const forward iterator
350 For iterator's features and requirements see \ref iterator
352 typedef iterator_type<true> const_iterator;
354 /// Returns a forward iterator addressing the first element in a list
356 For empty list \code begin() == end() \endcode
360 iterator it( head() );
361 ++it ; // skip dummy head node
365 /// Returns an iterator that addresses the location succeeding the last element in a list
367 Do not use the value returned by <tt>end</tt> function to access any item.
369 The returned value can be used only to control reaching the end of the list.
370 For empty list \code begin() == end() \endcode
374 return iterator( tail() );
377 /// Returns a forward const iterator addressing the first element in a list
379 const_iterator begin() const
381 const_iterator it( head() );
382 ++it ; // skip dummy head node
385 const_iterator cbegin()
387 const_iterator it( head() );
388 ++it ; // skip dummy head node
393 /// Returns an const iterator that addresses the location succeeding the last element in a list
395 const_iterator end() const
397 return const_iterator( tail() );
399 const_iterator cend()
401 return const_iterator( tail() );
406 /// Default constructor
408 Initializes empty list
424 The function creates a node with copy of \p val value
425 and then inserts the node created into the list.
427 The type \p Q should contain as minimum the complete key of the node.
428 The object of \ref value_type should be constructible from \p val of type \p Q.
429 In trivial case, \p Q is equal to \ref value_type.
431 The function makes RCU lock internally.
433 Returns \p true if inserting successful, \p false otherwise.
435 template <typename Q>
436 bool insert( Q const& val )
438 return insert_at( head(), val );
443 This function inserts new node with default-constructed value and then it calls
444 \p func functor with signature
445 \code void func( value_type& itemValue ) ;\endcode
447 The argument \p itemValue of user-defined functor \p func is the reference
448 to the list's item inserted. User-defined functor \p func should guarantee that during changing
449 item's value no any other changes could be made on this list's item by concurrent threads.
450 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
451 and it is called only if the inserting is success.
453 The type \p Q should contain the complete key of the node.
454 The object of \ref value_type should be constructible from \p key of type \p Q.
456 The function allows to split creating of new item into two part:
457 - create item from \p key with initializing key-fields only;
458 - insert new item into the list;
459 - if inserting is successful, initialize non-key fields of item by calling \p f functor
461 This can be useful if complete initialization of object of \p value_type is heavyweight and
462 it is preferable that the initialization should be completed only if inserting is successful.
464 The function makes RCU lock internally.
466 template <typename Q, typename Func>
467 bool insert( Q const& key, Func func )
469 return insert_at( head(), key, func );
472 # ifdef CDS_EMPLACE_SUPPORT
473 /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
475 Returns \p true if inserting successful, \p false otherwise.
477 The function makes RCU lock internally.
479 @note This function is available only for compiler that supports
480 variadic template and move semantics
482 template <typename... Args>
483 bool emplace( Args&&... args )
485 return emplace_at( head(), std::forward<Args>(args)... );
489 /// Ensures that the \p key exists in the list
491 The operation performs inserting or changing data with lock-free manner.
493 If the \p key not found in the list, then the new item created from \p key
494 is inserted into the list. Otherwise, the functor \p func is called with the item found.
495 The functor \p Func should be a function with signature:
497 void func( bool bNew, value_type& item, Q const& val );
502 void operator()( bool bNew, value_type& item, Q const& val );
507 - \p bNew - \p true if the item has been inserted, \p false otherwise
508 - \p item - item of the list
509 - \p val - argument \p key passed into the \p ensure function
511 The functor may change non-key fields of the \p item; however, \p func must guarantee
512 that during changing no any other modifications could be made on this item by concurrent threads.
514 You may pass \p func argument by reference using <tt>boost::ref</tt>.
516 The function applies RCU lock internally.
518 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
519 \p second is true if new item has been added or \p false if the item with \p key
520 already is in the list.
522 template <typename Q, typename Func>
523 std::pair<bool, bool> ensure( Q const& key, Func f )
525 return ensure_at( head(), key, f );
528 /// Deletes \p key from the list
529 /** \anchor cds_nonintrusive_LazyList_rcu_erase
530 Since the key of LazyList's item type \p T is not explicitly specified,
531 template parameter \p Q defines the key type searching in the list.
532 The list item comparator should be able to compare the type \p T of list item
535 RCU \p synchronize method can be called. RCU should not be locked.
537 Return \p true if key is found and deleted, \p false otherwise
539 template <typename Q>
540 bool erase( Q const& key )
542 # ifdef CDS_CXX11_LAMBDA_SUPPORT
543 return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
545 return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
549 /// Deletes the item from the list using \p pred predicate for searching
551 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_erase "erase(Q const&)"
552 but \p pred is used for key comparing.
553 \p Less functor has the interface like \p std::less.
554 \p pred must imply the same element order as the comparator used for building the list.
556 template <typename Q, typename Less>
557 bool erase_with( Q const& key, Less pred )
559 # ifdef CDS_CXX11_LAMBDA_SUPPORT
560 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
562 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), empty_erase_functor() );
566 /// Deletes \p key from the list
567 /** \anchor cds_nonintrusive_LazyList_rcu_erase_func
568 The function searches an item with key \p key, calls \p f functor
569 and deletes the item. If \p key is not found, the functor is not called.
571 The functor \p Func interface:
574 void operator()(value_type const& val) { ... }
577 The functor may be passed by reference with <tt>boost:ref</tt>
579 Since the key of LazyList's item type \p T is not explicitly specified,
580 template parameter \p Q defines the key type searching in the list.
581 The list item comparator should be able to compare the type \p T of list item
584 RCU \p synchronize method can be called. RCU should not be locked.
586 Return \p true if key is found and deleted, \p false otherwise
588 template <typename Q, typename Func>
589 bool erase( Q const& key, Func f )
591 return erase_at( head(), key, intrusive_key_comparator(), f );
594 /// Deletes the item from the list using \p pred predicate for searching
596 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_erase_func "erase(Q const&, Func)"
597 but \p pred is used for key comparing.
598 \p Less functor has the interface like \p std::less.
599 \p pred must imply the same element order as the comparator used for building the list.
601 template <typename Q, typename Less, typename Func>
602 bool erase_with( Q const& key, Less pred, Func f )
604 return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
607 /// Extracts an item from the list
609 @anchor cds_nonintrusive_LazyList_rcu_extract
610 The function searches an item with key equal to \p key in the list,
611 unlinks it from the list, and returns pointer to an item found in \p dest argument.
612 If the item with the key equal to \p key is not found the function returns \p false.
614 @note The function does NOT call RCU read-side lock or synchronization,
615 and does NOT dispose the item found. It just excludes the item from the list
616 and returns a pointer to item found.
617 You should lock RCU before calling this function.
620 #include <cds/urcu/general_buffered.h>
621 #include <cds/container/lazy_list_rcu.h>
623 typedef cds::urcu::gc< general_buffered<> > rcu;
624 typedef cds::container::LazyList< rcu, Foo > rcu_lazy_list;
626 rcu_lazy_list theList;
629 rcu_lazy_list::exempt_ptr p;
631 // first, we should lock RCU
632 rcu_lazy_list::rcu_lock sl;
634 // Now, you can apply extract function
635 // Note that you must not delete the item found inside the RCU lock
636 if ( theList.extract( p, 10 )) {
637 // do something with p
641 // Outside RCU lock section we may safely release extracted pointer.
642 // release() passes the pointer to RCU reclamation cycle.
646 template <typename Q>
647 bool extract( exempt_ptr& dest, Q const& key )
649 dest = extract_at( head(), key, intrusive_key_comparator() );
650 return !dest.empty();
653 /// Extracts an item from the list using \p pred predicate for searching
655 This function is the analog for \ref cds_nonintrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
657 The \p pred is a predicate used for key comparing.
658 \p Less has the interface like \p std::less.
659 \p pred must imply the same element order as \ref key_comparator.
661 template <typename Q, typename Less>
662 bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
664 dest = extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
665 return !dest.empty();
668 /// Finds the key \p key
669 /** \anchor cds_nonintrusive_LazyList_rcu_find_val
670 The function searches the item with key equal to \p key
671 and returns \p true if it is found, and \p false otherwise.
673 The function makes RCU lock internally.
675 template <typename Q>
676 bool find( Q const& key ) const
678 return find_at( head(), key, intrusive_key_comparator() );
681 /// Finds the key \p val using \p pred predicate for searching
683 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_val "find(Q const&)"
684 but \p pred is used for key comparing.
685 \p Less functor has the interface like \p std::less.
686 \p pred must imply the same element order as the comparator used for building the list.
688 template <typename Q, typename Less>
689 bool find_with( Q const& key, Less pred ) const
691 return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
694 /// Finds the key \p val and performs an action with it
695 /** \anchor cds_nonintrusive_LazyList_rcu_find_func
696 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
697 The interface of \p Func functor is:
700 void operator()( value_type& item, Q& val );
703 where \p item is the item found, \p val is the <tt>find</tt> function argument.
705 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
707 The functor may change non-key fields of \p item. Note that the function is only guarantee
708 that \p item cannot be deleted during functor is executing.
709 The function does not serialize simultaneous access to the list \p item. If such access is
710 possible you must provide your own synchronization schema to exclude unsafe item modifications.
712 The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
713 may modify both arguments.
715 The function makes RCU lock internally.
717 The function returns \p true if \p val is found, \p false otherwise.
719 template <typename Q, typename Func>
720 bool find( Q& val, Func f ) const
722 return find_at( head(), val, intrusive_key_comparator(), f );
725 /// Finds the key \p val using \p pred predicate for searching
727 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_func "find(Q&, Func)"
728 but \p pred is used for key comparing.
729 \p Less functor has the interface like \p std::less.
730 \p pred must imply the same element order as the comparator used for building the list.
732 template <typename Q, typename Less, typename Func>
733 bool find_with( Q& val, Less pred, Func f ) const
735 return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
738 /// Finds the key \p val and performs an action with it
739 /** \anchor cds_nonintrusive_LazyList_rcu_find_cfunc
740 The function searches an item with key equal to \p val and calls the functor \p f for the item found.
741 The interface of \p Func functor is:
744 void operator()( value_type& item, Q const& val );
747 where \p item is the item found, \p val is the <tt>find</tt> function argument.
749 You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
751 The function does not serialize simultaneous access to the list \p item. If such access is
752 possible you must provide your own synchronization schema to exclude unsafe item modifications.
754 The function makes RCU lock internally.
756 The function returns \p true if \p val is found, \p false otherwise.
758 template <typename Q, typename Func>
759 bool find( Q const& val, Func f ) const
761 return find_at( head(), val, intrusive_key_comparator(), f );
764 /// Finds the key \p val using \p pred predicate for searching
766 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_cfunc "find(Q const&, Func)"
767 but \p pred is used for key comparing.
768 \p Less functor has the interface like \p std::less.
769 \p pred must imply the same element order as the comparator used for building the list.
771 template <typename Q, typename Less, typename Func>
772 bool find_with( Q const& val, Less pred, Func f ) const
774 return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
777 /// Finds the key \p val and return the item found
778 /** \anchor cds_nonintrusive_LazyList_rcu_get
779 The function searches the item with key equal to \p val and returns the pointer to item found.
780 If \p val is not found it returns \p nullptr.
782 Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
784 RCU should be locked before call of this function.
785 Returned item is valid only while RCU is locked:
787 typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
792 ord_list::rcu_lock lock;
794 foo * pVal = theList.get( 5 );
799 // Unlock RCU by rcu_lock destructor
800 // pVal can be freed at any time after RCU has been unlocked
804 template <typename Q>
805 value_type * get( Q const& val ) const
807 return get_at( head(), val, intrusive_key_comparator());
810 /// Finds the key \p val and return the item found
812 The function is an analog of \ref cds_nonintrusive_LazyList_rcu_get "get(Q const&)"
813 but \p pred is used for comparing the keys.
815 \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
817 \p pred must imply the same element order as the comparator used for building the list.
819 template <typename Q, typename Less>
820 value_type * get_with( Q const& val, Less pred ) const
822 return get_at( head(), val, typename maker::template less_wrapper<Less>::type());
825 /// Checks if the list is empty
828 return base_class::empty();
831 /// Returns list's item count
833 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
834 this function always returns 0.
836 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
837 is empty. To check list emptyness use \ref empty() method.
841 return base_class::size();
846 Post-condition: the list is empty
855 bool insert_node_at( head_type& refHead, node_type * pNode )
857 assert( pNode != nullptr );
858 scoped_node_ptr p( pNode );
860 if ( base_class::insert_at( &refHead, *pNode )) {
868 template <typename Q>
869 bool insert_at( head_type& refHead, Q const& val )
871 return insert_node_at( refHead, alloc_node( val ));
874 # ifdef CDS_EMPLACE_SUPPORT
875 template <typename... Args>
876 bool emplace_at( head_type& refHead, Args&&... args )
878 return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
882 template <typename Q, typename Func>
883 bool insert_at( head_type& refHead, Q const& key, Func f )
885 scoped_node_ptr pNode( alloc_node( key ));
887 # ifdef CDS_CXX11_LAMBDA_SUPPORT
888 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
889 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
890 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
891 value_type& (* n2v)( node_type& ) = node_to_value;
892 if ( base_class::insert_at( &refHead, *pNode, [&f,n2v](node_type& node){ cds::unref(f)( n2v(node) ); } ))
894 if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node_to_value(node) ); } ))
897 insert_functor<Func> wrapper( f );
898 if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
907 template <typename Q, typename Compare, typename Func>
908 bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
910 # ifdef CDS_CXX11_LAMBDA_SUPPORT
911 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
912 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
913 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
914 value_type const& (* n2v)( node_type const& ) = node_to_value;
915 return base_class::erase_at( &refHead, key, cmp, [&f,n2v](node_type const& node){ cds::unref(f)( n2v(node) ); } );
917 return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
920 erase_functor<Func> wrapper( f );
921 return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
925 template <typename Q, typename Compare>
926 node_type * extract_at( head_type& refHead, Q const& key, Compare cmp )
928 return base_class::extract_at( &refHead, key, cmp );
931 template <typename Q, typename Func>
932 std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
934 scoped_node_ptr pNode( alloc_node( key ));
936 # ifdef CDS_CXX11_LAMBDA_SUPPORT
937 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
938 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
939 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
940 value_type& (* n2v)( node_type& ) = node_to_value;
941 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
942 [&f, &key, n2v](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, n2v(node), key ); });
944 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
945 [&f, &key](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, node_to_value(node), key ); });
948 ensure_functor<Q, Func> wrapper( key, f );
949 std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
951 if ( ret.first && ret.second )
957 template <typename Q, typename Compare>
958 bool find_at( head_type& refHead, Q const& key, Compare cmp ) const
960 # ifdef CDS_CXX11_LAMBDA_SUPPORT
961 return base_class::find_at( &refHead, key, cmp, [](node_type&, Q const &) {} );
963 return base_class::find_at( &refHead, key, cmp, empty_find_functor() );
967 template <typename Q, typename Compare, typename Func>
968 bool find_at( head_type& refHead, Q& val, Compare cmp, Func f ) const
970 # ifdef CDS_CXX11_LAMBDA_SUPPORT
971 # ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
972 // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
973 // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
974 value_type& (* n2v)( node_type& ) = node_to_value;
975 return base_class::find_at( &refHead, val, cmp, [&f,n2v](node_type& node, Q& val){ cds::unref(f)( n2v(node), val ); });
977 return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& val){ cds::unref(f)( node_to_value(node), val ); });
980 find_functor<Func> wrapper( f );
981 return base_class::find_at( &refHead, val, cmp, cds::ref(wrapper) );
985 template <typename Q, typename Compare>
986 value_type * get_at( head_type& refHead, Q const& val, Compare cmp ) const
988 node_type * pNode = base_class::get_at( &refHead, val, cmp );
989 return pNode ? &pNode->m_Value : nullptr;
995 }} // namespace cds::container
997 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_RCU_H