cds/container/lazy_list_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_LAZY_LIST_RCU_H
   4 #define __CDS_CONTAINER_LAZY_LIST_RCU_H
   5
   6 #include <cds/container/lazy_list_base.h>
   7 #include <cds/intrusive/lazy_list_rcu.h>
   8 #include <cds/details/binary_functor_wrapper.h>
   9 #include <cds/details/std/memory.h>
  10 #include <cds/container/details/make_lazy_list.h>
  11
  12 namespace cds { namespace container {
  13
  14     /// Lazy ordered list (template specialization for \ref cds_urcu_desc "RCU")
  15     /** @ingroup cds_nonintrusive_list
  16         \anchor cds_nonintrusive_LazyList_rcu
  17
  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>.
  20
  21         Source:
  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"
  24
  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.
  29
  30         It is non-intrusive version of cds::intrusive::LazyList class
  31
  32         Template arguments:
  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
  36
  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
  41
  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.
  44
  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.
  48
  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
  51         \code
  52         #include <cds/urcu/general_instant.h>
  53         #include <cds/container/lazy_list_rcu.h>
  54         // Declare comparator for the item
  55         struct my_compare {
  56             int operator ()( int i1, int i2 )
  57             {
  58                 return i1 - i2;
  59             }
  60         };
  61
  62         // Declare type_traits
  63         struct my_traits: public cds::container::lazy_list::type_traits
  64         {
  65             typedef my_compare compare;
  66         };
  67
  68         // Declare traits-based list
  69         typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_instant<> >, int, my_traits >     traits_based_list;
  70         \endcode
  71
  72         is equivalent for the following option-based list
  73         \code
  74         #include <cds/urcu/general_instant.h>
  75         #include <cds/container/lazy_list_rcu.h>
  76
  77         // my_compare is the same
  78
  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
  83             >::type
  84         >     option_based_list;
  85         \endcode
  86
  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
 100     */
 101     template <
 102         typename RCU,
 103         typename T,
 104 #ifdef CDS_DOXYGEN_INVOKED
 105         typename Traits = lazy_list::type_traits
 106 #else
 107         typename Traits
 108 #endif
 109     >
 110     class LazyList< cds::urcu::gc<RCU>, T, Traits >:
 111 #ifdef CDS_DOXYGEN_INVOKED
 112         protected intrusive::LazyList< cds::urcu::gc<RCU>, T, Traits >
 113 #else
 114         protected details::make_lazy_list< cds::urcu::gc<RCU>, T, Traits >::type
 115 #endif
 116     {
 117         //@cond
 118         typedef details::make_lazy_list< cds::urcu::gc<RCU>, T, Traits > maker;
 119         typedef typename maker::type  base_class;
 120         //@endcond
 121
 122     public:
 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
 131
 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
 134
 135     protected:
 136         //@cond
 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;
 141
 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;
 145 #   endif
 146         //@endcond
 147
 148     public:
 149         typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::type_traits::disposer > exempt_ptr; ///< pointer to extracted node
 150
 151     private:
 152         //@cond
 153         static value_type& node_to_value( node_type& n )
 154         {
 155             return n.m_Value;
 156         }
 157         static value_type const& node_to_value( node_type const& n )
 158         {
 159             return n.m_Value;
 160         }
 161
 162 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 163         template <typename Func>
 164         struct insert_functor
 165         {
 166             Func        m_func;
 167
 168             insert_functor ( Func f )
 169                 : m_func(f)
 170             {}
 171
 172             void operator()( node_type& node )
 173             {
 174                 cds::unref(m_func)( node_to_value(node) );
 175             }
 176         };
 177
 178         template <typename Q, typename Func>
 179         struct ensure_functor
 180         {
 181             Func        m_func;
 182             Q const&    m_arg;
 183
 184             ensure_functor( Q const& arg, Func f )
 185                 : m_func(f)
 186                 , m_arg( arg )
 187             {}
 188
 189             void operator ()( bool bNew, node_type& node, node_type& )
 190             {
 191                 cds::unref(m_func)( bNew, node_to_value(node), m_arg );
 192             }
 193         };
 194
 195         template <typename Func>
 196         struct find_functor
 197         {
 198             Func    m_func;
 199
 200             find_functor( Func f )
 201                 : m_func(f)
 202             {}
 203
 204             template <typename Q>
 205             void operator ()( node_type& node, Q& val )
 206             {
 207                 cds::unref(m_func)( node_to_value(node), val );
 208             }
 209         };
 210
 211         struct empty_find_functor
 212         {
 213             template <typename Q>
 214             void operator ()( node_type& node, Q& val ) const
 215             {}
 216         };
 217
 218         template <typename Func>
 219         struct erase_functor
 220         {
 221             Func        m_func;
 222
 223             erase_functor( Func f )
 224                 : m_func(f)
 225             {}
 226
 227             void operator()( node_type const& node )
 228             {
 229                 cds::unref(m_func)( node_to_value(node) );
 230             }
 231         };
 232 #   endif   // ifndef CDS_CXX11_LAMBDA_SUPPORT
 233         //@endcond
 234
 235     protected:
 236         //@cond
 237         template <typename Q>
 238         static node_type * alloc_node( Q const& v )
 239         {
 240             return cxx_allocator().New( v );
 241         }
 242
 243 #   ifdef CDS_EMPLACE_SUPPORT
 244         template <typename... Args>
 245         static node_type * alloc_node( Args&&... args )
 246         {
 247             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 248         }
 249 #   endif
 250
 251         static void free_node( node_type * pNode )
 252         {
 253             cxx_allocator().Delete( pNode );
 254         }
 255
 256         struct node_disposer {
 257             void operator()( node_type * pNode )
 258             {
 259                 free_node( pNode );
 260             }
 261         };
 262         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 263
 264         head_type& head()
 265         {
 266             return base_class::m_Head;
 267         }
 268
 269         head_type& head() const
 270         {
 271             return const_cast<head_type&>( base_class::m_Head );
 272         }
 273
 274         head_type& tail()
 275         {
 276             return base_class::m_Tail;
 277         }
 278
 279         head_type const&  tail() const
 280         {
 281             return base_class::m_Tail;
 282         }
 283         //@endcond
 284
 285     protected:
 286                 //@cond
 287         template <bool IsConst>
 288         class iterator_type: protected base_class::template iterator_type<IsConst>
 289         {
 290             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 291
 292             iterator_type( head_type const& pNode )
 293                 : iterator_base( const_cast<head_type *>( &pNode ))
 294             {}
 295
 296             iterator_type( head_type const * pNode )
 297                 : iterator_base( const_cast<head_type *>( pNode ))
 298             {}
 299
 300             friend class LazyList;
 301
 302         public:
 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;
 305
 306             iterator_type()
 307             {}
 308
 309             iterator_type( iterator_type const& src )
 310                 : iterator_base( src )
 311             {}
 312
 313             value_ptr operator ->() const
 314             {
 315                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 316                 return p ? &(p->m_Value) : nullptr;
 317             }
 318
 319             value_ref operator *() const
 320             {
 321                 return (iterator_base::operator *()).m_Value;
 322             }
 323
 324             /// Pre-increment
 325             iterator_type& operator ++()
 326             {
 327                 iterator_base::operator ++();
 328                 return *this;
 329             }
 330
 331             template <bool C>
 332             bool operator ==(iterator_type<C> const& i ) const
 333             {
 334                 return iterator_base::operator ==(i);
 335             }
 336             template <bool C>
 337             bool operator !=(iterator_type<C> const& i ) const
 338             {
 339                 return iterator_base::operator !=(i);
 340             }
 341         };
 342         //@endcond
 343
 344     public:
 345         /// Forward iterator
 346         typedef iterator_type<false>    iterator;
 347
 348         /// Const forward iterator
 349         /**
 350             For iterator's features and requirements see \ref iterator
 351         */
 352         typedef iterator_type<true>     const_iterator;
 353
 354         /// Returns a forward iterator addressing the first element in a list
 355         /**
 356             For empty list \code begin() == end() \endcode
 357         */
 358         iterator begin()
 359         {
 360             iterator it( head() );
 361             ++it        ;   // skip dummy head node
 362             return it;
 363         }
 364
 365         /// Returns an iterator that addresses the location succeeding the last element in a list
 366         /**
 367             Do not use the value returned by <tt>end</tt> function to access any item.
 368
 369             The returned value can be used only to control reaching the end of the list.
 370             For empty list \code begin() == end() \endcode
 371         */
 372         iterator end()
 373         {
 374             return iterator( tail() );
 375         }
 376
 377         /// Returns a forward const iterator addressing the first element in a list
 378         //@{
 379         const_iterator begin() const
 380         {
 381             const_iterator it( head() );
 382             ++it        ;   // skip dummy head node
 383             return it;
 384         }
 385         const_iterator cbegin()
 386         {
 387             const_iterator it( head() );
 388             ++it        ;   // skip dummy head node
 389             return it;
 390         }
 391         //@}
 392
 393         /// Returns an const iterator that addresses the location succeeding the last element in a list
 394         //@{
 395         const_iterator end() const
 396         {
 397             return const_iterator( tail() );
 398         }
 399         const_iterator cend()
 400         {
 401             return const_iterator( tail() );
 402         }
 403         //@}
 404
 405     public:
 406         /// Default constructor
 407         /**
 408             Initializes empty list
 409         */
 410         LazyList()
 411         {}
 412
 413         /// List desctructor
 414         /**
 415             Clears the list
 416         */
 417         ~LazyList()
 418         {
 419             clear();
 420         }
 421
 422         /// Inserts new node
 423         /**
 424             The function creates a node with copy of \p val value
 425             and then inserts the node created into the list.
 426
 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.
 430
 431             The function makes RCU lock internally.
 432
 433             Returns \p true if inserting successful, \p false otherwise.
 434         */
 435         template <typename Q>
 436         bool insert( Q const& val )
 437         {
 438             return insert_at( head(), val );
 439         }
 440
 441         /// Inserts new node
 442         /**
 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
 446
 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.
 452
 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.
 455
 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
 460
 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.
 463
 464             The function makes RCU lock internally.
 465         */
 466         template <typename Q, typename Func>
 467         bool insert( Q const& key, Func func )
 468         {
 469             return insert_at( head(), key, func );
 470         }
 471
 472 #   ifdef CDS_EMPLACE_SUPPORT
 473         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 474         /**
 475             Returns \p true if inserting successful, \p false otherwise.
 476
 477             The function makes RCU lock internally.
 478
 479             @note This function is available only for compiler that supports
 480             variadic template and move semantics
 481         */
 482         template <typename... Args>
 483         bool emplace( Args&&... args )
 484         {
 485             return emplace_at( head(), std::forward<Args>(args)... );
 486         }
 487 #   endif
 488
 489         /// Ensures that the \p key exists in the list
 490         /**
 491             The operation performs inserting or changing data with lock-free manner.
 492
 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:
 496             \code
 497                 void func( bool bNew, value_type& item, Q const& val );
 498             \endcode
 499             or a functor:
 500             \code
 501                 struct my_functor {
 502                     void operator()( bool bNew, value_type& item, Q const& val );
 503                 };
 504             \endcode
 505
 506             with arguments:
 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
 510
 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.
 513
 514             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 515
 516             The function applies RCU lock internally.
 517
 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.
 521         */
 522         template <typename Q, typename Func>
 523         std::pair<bool, bool> ensure( Q const& key, Func f )
 524         {
 525             return ensure_at( head(), key, f );
 526         }
 527
 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
 533             and the type \p Q.
 534
 535             RCU \p synchronize method can be called. RCU should not be locked.
 536
 537             Return \p true if key is found and deleted, \p false otherwise
 538         */
 539         template <typename Q>
 540         bool erase( Q const& key )
 541         {
 542 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 543             return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
 544 #       else
 545             return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
 546 #       endif
 547         }
 548
 549         /// Deletes the item from the list using \p pred predicate for searching
 550         /**
 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.
 555         */
 556         template <typename Q, typename Less>
 557         bool erase_with( Q const& key, Less pred )
 558         {
 559 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 560             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
 561 #       else
 562             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), empty_erase_functor() );
 563 #       endif
 564         }
 565
 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.
 570
 571             The functor \p Func interface:
 572             \code
 573             struct extractor {
 574                 void operator()(value_type const& val) { ... }
 575             };
 576             \endcode
 577             The functor may be passed by reference with <tt>boost:ref</tt>
 578
 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
 582             and the type \p Q.
 583
 584             RCU \p synchronize method can be called. RCU should not be locked.
 585
 586             Return \p true if key is found and deleted, \p false otherwise
 587         */
 588         template <typename Q, typename Func>
 589         bool erase( Q const& key, Func f )
 590         {
 591             return erase_at( head(), key, intrusive_key_comparator(), f );
 592         }
 593
 594         /// Deletes the item from the list using \p pred predicate for searching
 595         /**
 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.
 600         */
 601         template <typename Q, typename Less, typename Func>
 602         bool erase_with( Q const& key, Less pred, Func f )
 603         {
 604             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
 605         }
 606
 607         /// Extracts an item from the list
 608         /**
 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.
 613
 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.
 618
 619             \code
 620             #include <cds/urcu/general_buffered.h>
 621             #include <cds/container/lazy_list_rcu.h>
 622
 623             typedef cds::urcu::gc< general_buffered<> > rcu;
 624             typedef cds::container::LazyList< rcu, Foo > rcu_lazy_list;
 625
 626             rcu_lazy_list theList;
 627             // ...
 628
 629             rcu_lazy_list::exempt_ptr p;
 630             {
 631                 // first, we should lock RCU
 632                 rcu_lazy_list::rcu_lock sl;
 633
 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
 638                     ...
 639                 }
 640             }
 641             // Outside RCU lock section we may safely release extracted pointer.
 642             // release() passes the pointer to RCU reclamation cycle.
 643             p.release();
 644             \endcode
 645         */
 646         template <typename Q>
 647         bool extract( exempt_ptr& dest, Q const& key )
 648         {
 649             dest = extract_at( head(), key, intrusive_key_comparator() );
 650             return !dest.empty();
 651         }
 652
 653         /// Extracts an item from the list using \p pred predicate for searching
 654         /**
 655             This function is the analog for \ref cds_nonintrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
 656
 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.
 660         */
 661         template <typename Q, typename Less>
 662         bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
 663         {
 664             dest = extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 665             return !dest.empty();
 666         }
 667
 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.
 672
 673             The function makes RCU lock internally.
 674         */
 675         template <typename Q>
 676         bool find( Q const& key ) const
 677         {
 678             return find_at( head(), key, intrusive_key_comparator() );
 679         }
 680
 681         /// Finds the key \p val using \p pred predicate for searching
 682         /**
 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.
 687         */
 688         template <typename Q, typename Less>
 689         bool find_with( Q const& key, Less pred ) const
 690         {
 691             return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 692         }
 693
 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:
 698             \code
 699             struct functor {
 700                 void operator()( value_type& item, Q& val );
 701             };
 702             \endcode
 703             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 704
 705             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 706
 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.
 711
 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.
 714
 715             The function makes RCU lock internally.
 716
 717             The function returns \p true if \p val is found, \p false otherwise.
 718         */
 719         template <typename Q, typename Func>
 720         bool find( Q& val, Func f ) const
 721         {
 722             return find_at( head(), val, intrusive_key_comparator(), f );
 723         }
 724
 725         /// Finds the key \p val using \p pred predicate for searching
 726         /**
 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.
 731         */
 732         template <typename Q, typename Less, typename Func>
 733         bool find_with( Q& val, Less pred, Func f ) const
 734         {
 735             return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
 736         }
 737
 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:
 742             \code
 743             struct functor {
 744                 void operator()( value_type& item, Q const& val );
 745             };
 746             \endcode
 747             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 748
 749             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 750
 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.
 753
 754             The function makes RCU lock internally.
 755
 756             The function returns \p true if \p val is found, \p false otherwise.
 757         */
 758         template <typename Q, typename Func>
 759         bool find( Q const& val, Func f ) const
 760         {
 761             return find_at( head(), val, intrusive_key_comparator(), f );
 762         }
 763
 764         /// Finds the key \p val using \p pred predicate for searching
 765         /**
 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.
 770         */
 771         template <typename Q, typename Less, typename Func>
 772         bool find_with( Q const& val, Less pred, Func f ) const
 773         {
 774             return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
 775         }
 776
 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 NULL.
 781
 782             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 783
 784             RCU should be locked before call of this function.
 785             Returned item is valid only while RCU is locked:
 786             \code
 787             typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 788             ord_list theList;
 789             // ...
 790             {
 791                 // Lock RCU
 792                 ord_list::rcu_lock lock;
 793
 794                 foo * pVal = theList.get( 5 );
 795                 if ( pVal ) {
 796                     // Deal with pVal
 797                     //...
 798                 }
 799                 // Unlock RCU by rcu_lock destructor
 800                 // pVal can be freed at any time after RCU has been unlocked
 801             }
 802             \endcode
 803         */
 804         template <typename Q>
 805         value_type * get( Q const& val ) const
 806         {
 807             return get_at( head(), val, intrusive_key_comparator());
 808         }
 809
 810         /// Finds the key \p val and return the item found
 811         /**
 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.
 814
 815             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 816             in any order.
 817             \p pred must imply the same element order as the comparator used for building the list.
 818         */
 819         template <typename Q, typename Less>
 820         value_type * get_with( Q const& val, Less pred ) const
 821         {
 822             return get_at( head(), val, typename maker::template less_wrapper<Less>::type());
 823         }
 824
 825         /// Checks if the list is empty
 826         bool empty() const
 827         {
 828             return base_class::empty();
 829         }
 830
 831         /// Returns list's item count
 832         /**
 833             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 834             this function always returns 0.
 835
 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.
 838         */
 839         size_t size() const
 840         {
 841             return base_class::size();
 842         }
 843
 844         /// Clears the list
 845         /**
 846             Post-condition: the list is empty
 847         */
 848         void clear()
 849         {
 850             base_class::clear();
 851         }
 852
 853     protected:
 854         //@cond
 855         bool insert_node_at( head_type& refHead, node_type * pNode )
 856         {
 857             assert( pNode != nullptr );
 858             scoped_node_ptr p( pNode );
 859
 860             if ( base_class::insert_at( &refHead, *pNode )) {
 861                 p.release();
 862                 return true;
 863             }
 864
 865             return false;
 866         }
 867
 868         template <typename Q>
 869         bool insert_at( head_type& refHead, Q const& val )
 870         {
 871             return insert_node_at( refHead, alloc_node( val ));
 872         }
 873
 874 #   ifdef CDS_EMPLACE_SUPPORT
 875         template <typename... Args>
 876         bool emplace_at( head_type& refHead, Args&&... args )
 877         {
 878             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 879         }
 880 #   endif
 881
 882         template <typename Q, typename Func>
 883         bool insert_at( head_type& refHead, Q const& key, Func f )
 884         {
 885             scoped_node_ptr pNode( alloc_node( key ));
 886
 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) ); } ))
 893 #       else
 894             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node_to_value(node) ); } ))
 895 #       endif
 896 #   else
 897             insert_functor<Func>  wrapper( f );
 898             if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
 899 #   endif
 900             {
 901                 pNode.release();
 902                 return true;
 903             }
 904             return false;
 905         }
 906
 907         template <typename Q, typename Compare, typename Func>
 908         bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
 909         {
 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) ); } );
 916 #       else
 917             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
 918 #       endif
 919 #   else
 920             erase_functor<Func> wrapper( f );
 921             return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
 922 #   endif
 923         }
 924
 925         template <typename Q, typename Compare>
 926         node_type * extract_at( head_type& refHead, Q const& key, Compare cmp )
 927         {
 928             return base_class::extract_at( &refHead, key, cmp );
 929         }
 930
 931         template <typename Q, typename Func>
 932         std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
 933         {
 934             scoped_node_ptr pNode( alloc_node( key ));
 935
 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 ); });
 943 #       else
 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 ); });
 946 #       endif
 947 #   else
 948             ensure_functor<Q, Func> wrapper( key, f );
 949             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
 950 #   endif
 951             if ( ret.first && ret.second )
 952                 pNode.release();
 953
 954             return ret;
 955         }
 956
 957         template <typename Q, typename Compare>
 958         bool find_at( head_type& refHead, Q const& key, Compare cmp ) const
 959         {
 960 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 961             return base_class::find_at( &refHead, key, cmp, [](node_type&, Q const &) {} );
 962 #       else
 963             return base_class::find_at( &refHead, key, cmp, empty_find_functor() );
 964 #       endif
 965         }
 966
 967         template <typename Q, typename Compare, typename Func>
 968         bool find_at( head_type& refHead, Q& val, Compare cmp, Func f ) const
 969         {
 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 ); });
 976 #       else
 977             return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& val){ cds::unref(f)( node_to_value(node), val ); });
 978 #       endif
 979 #   else
 980             find_functor<Func>  wrapper( f );
 981             return base_class::find_at( &refHead, val, cmp, cds::ref(wrapper) );
 982 #   endif
 983         }
 984
 985         template <typename Q, typename Compare>
 986         value_type * get_at( head_type& refHead, Q const& val, Compare cmp ) const
 987         {
 988             node_type * pNode = base_class::get_at( &refHead, val, cmp );
 989             return pNode ? &pNode->m_Value : nullptr;
 990         }
 991
 992         //@endcond
 993     };
 994
 995 }} // namespace cds::container
 996
 997 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_RCU_H