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 <memory>
   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>
  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         template <typename... Args>
 244         static node_type * alloc_node( Args&&... args )
 245         {
 246             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 247         }
 248
 249         static void free_node( node_type * pNode )
 250         {
 251             cxx_allocator().Delete( pNode );
 252         }
 253
 254         struct node_disposer {
 255             void operator()( node_type * pNode )
 256             {
 257                 free_node( pNode );
 258             }
 259         };
 260         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 261
 262         head_type& head()
 263         {
 264             return base_class::m_Head;
 265         }
 266
 267         head_type& head() const
 268         {
 269             return const_cast<head_type&>( base_class::m_Head );
 270         }
 271
 272         head_type& tail()
 273         {
 274             return base_class::m_Tail;
 275         }
 276
 277         head_type const&  tail() const
 278         {
 279             return base_class::m_Tail;
 280         }
 281         //@endcond
 282
 283     protected:
 284                 //@cond
 285         template <bool IsConst>
 286         class iterator_type: protected base_class::template iterator_type<IsConst>
 287         {
 288             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 289
 290             iterator_type( head_type const& pNode )
 291                 : iterator_base( const_cast<head_type *>( &pNode ))
 292             {}
 293
 294             iterator_type( head_type const * pNode )
 295                 : iterator_base( const_cast<head_type *>( pNode ))
 296             {}
 297
 298             friend class LazyList;
 299
 300         public:
 301             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 302             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 303
 304             iterator_type()
 305             {}
 306
 307             iterator_type( iterator_type const& src )
 308                 : iterator_base( src )
 309             {}
 310
 311             value_ptr operator ->() const
 312             {
 313                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 314                 return p ? &(p->m_Value) : nullptr;
 315             }
 316
 317             value_ref operator *() const
 318             {
 319                 return (iterator_base::operator *()).m_Value;
 320             }
 321
 322             /// Pre-increment
 323             iterator_type& operator ++()
 324             {
 325                 iterator_base::operator ++();
 326                 return *this;
 327             }
 328
 329             template <bool C>
 330             bool operator ==(iterator_type<C> const& i ) const
 331             {
 332                 return iterator_base::operator ==(i);
 333             }
 334             template <bool C>
 335             bool operator !=(iterator_type<C> const& i ) const
 336             {
 337                 return iterator_base::operator !=(i);
 338             }
 339         };
 340         //@endcond
 341
 342     public:
 343         /// Forward iterator
 344         typedef iterator_type<false>    iterator;
 345
 346         /// Const forward iterator
 347         /**
 348             For iterator's features and requirements see \ref iterator
 349         */
 350         typedef iterator_type<true>     const_iterator;
 351
 352         /// Returns a forward iterator addressing the first element in a list
 353         /**
 354             For empty list \code begin() == end() \endcode
 355         */
 356         iterator begin()
 357         {
 358             iterator it( head() );
 359             ++it        ;   // skip dummy head node
 360             return it;
 361         }
 362
 363         /// Returns an iterator that addresses the location succeeding the last element in a list
 364         /**
 365             Do not use the value returned by <tt>end</tt> function to access any item.
 366
 367             The returned value can be used only to control reaching the end of the list.
 368             For empty list \code begin() == end() \endcode
 369         */
 370         iterator end()
 371         {
 372             return iterator( tail() );
 373         }
 374
 375         /// Returns a forward const iterator addressing the first element in a list
 376         //@{
 377         const_iterator begin() const
 378         {
 379             const_iterator it( head() );
 380             ++it        ;   // skip dummy head node
 381             return it;
 382         }
 383         const_iterator cbegin()
 384         {
 385             const_iterator it( head() );
 386             ++it        ;   // skip dummy head node
 387             return it;
 388         }
 389         //@}
 390
 391         /// Returns an const iterator that addresses the location succeeding the last element in a list
 392         //@{
 393         const_iterator end() const
 394         {
 395             return const_iterator( tail() );
 396         }
 397         const_iterator cend()
 398         {
 399             return const_iterator( tail() );
 400         }
 401         //@}
 402
 403     public:
 404         /// Default constructor
 405         /**
 406             Initializes empty list
 407         */
 408         LazyList()
 409         {}
 410
 411         /// List desctructor
 412         /**
 413             Clears the list
 414         */
 415         ~LazyList()
 416         {
 417             clear();
 418         }
 419
 420         /// Inserts new node
 421         /**
 422             The function creates a node with copy of \p val value
 423             and then inserts the node created into the list.
 424
 425             The type \p Q should contain as minimum the complete key of the node.
 426             The object of \ref value_type should be constructible from \p val of type \p Q.
 427             In trivial case, \p Q is equal to \ref value_type.
 428
 429             The function makes RCU lock internally.
 430
 431             Returns \p true if inserting successful, \p false otherwise.
 432         */
 433         template <typename Q>
 434         bool insert( Q const& val )
 435         {
 436             return insert_at( head(), val );
 437         }
 438
 439         /// Inserts new node
 440         /**
 441             This function inserts new node with default-constructed value and then it calls
 442             \p func functor with signature
 443             \code void func( value_type& itemValue ) ;\endcode
 444
 445             The argument \p itemValue of user-defined functor \p func is the reference
 446             to the list's item inserted. User-defined functor \p func should guarantee that during changing
 447             item's value no any other changes could be made on this list's item by concurrent threads.
 448             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 449             and it is called only if the inserting is success.
 450
 451             The type \p Q should contain the complete key of the node.
 452             The object of \ref value_type should be constructible from \p key of type \p Q.
 453
 454             The function allows to split creating of new item into two part:
 455             - create item from \p key with initializing key-fields only;
 456             - insert new item into the list;
 457             - if inserting is successful, initialize non-key fields of item by calling \p f functor
 458
 459             This can be useful if complete initialization of object of \p value_type is heavyweight and
 460             it is preferable that the initialization should be completed only if inserting is successful.
 461
 462             The function makes RCU lock internally.
 463         */
 464         template <typename Q, typename Func>
 465         bool insert( Q const& key, Func func )
 466         {
 467             return insert_at( head(), key, func );
 468         }
 469
 470         /// Inserts data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
 471         /**
 472             Returns \p true if inserting successful, \p false otherwise.
 473
 474             The function makes RCU lock internally.
 475         */
 476         template <typename... Args>
 477         bool emplace( Args&&... args )
 478         {
 479             return emplace_at( head(), std::forward<Args>(args)... );
 480         }
 481
 482         /// Ensures that the \p key exists in the list
 483         /**
 484             The operation performs inserting or changing data with lock-free manner.
 485
 486             If the \p key not found in the list, then the new item created from \p key
 487             is inserted into the list. Otherwise, the functor \p func is called with the item found.
 488             The functor \p Func should be a function with signature:
 489             \code
 490                 void func( bool bNew, value_type& item, Q const& val );
 491             \endcode
 492             or a functor:
 493             \code
 494                 struct my_functor {
 495                     void operator()( bool bNew, value_type& item, Q const& val );
 496                 };
 497             \endcode
 498
 499             with arguments:
 500             - \p bNew - \p true if the item has been inserted, \p false otherwise
 501             - \p item - item of the list
 502             - \p val - argument \p key passed into the \p ensure function
 503
 504             The functor may change non-key fields of the \p item; however, \p func must guarantee
 505             that during changing no any other modifications could be made on this item by concurrent threads.
 506
 507             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 508
 509             The function applies RCU lock internally.
 510
 511             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 512             \p second is true if new item has been added or \p false if the item with \p key
 513             already is in the list.
 514         */
 515         template <typename Q, typename Func>
 516         std::pair<bool, bool> ensure( Q const& key, Func f )
 517         {
 518             return ensure_at( head(), key, f );
 519         }
 520
 521         /// Deletes \p key from the list
 522         /** \anchor cds_nonintrusive_LazyList_rcu_erase
 523             Since the key of LazyList's item type \p T is not explicitly specified,
 524             template parameter \p Q defines the key type searching in the list.
 525             The list item comparator should be able to compare the type \p T of list item
 526             and the type \p Q.
 527
 528             RCU \p synchronize method can be called. RCU should not be locked.
 529
 530             Return \p true if key is found and deleted, \p false otherwise
 531         */
 532         template <typename Q>
 533         bool erase( Q const& key )
 534         {
 535 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 536             return erase_at( head(), key, intrusive_key_comparator(), [](value_type const&){} );
 537 #       else
 538             return erase_at( head(), key, intrusive_key_comparator(), empty_erase_functor() );
 539 #       endif
 540         }
 541
 542         /// Deletes the item from the list using \p pred predicate for searching
 543         /**
 544             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_erase "erase(Q const&)"
 545             but \p pred is used for key comparing.
 546             \p Less functor has the interface like \p std::less.
 547             \p pred must imply the same element order as the comparator used for building the list.
 548         */
 549         template <typename Q, typename Less>
 550         bool erase_with( Q const& key, Less pred )
 551         {
 552 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 553             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), [](value_type const&){} );
 554 #       else
 555             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), empty_erase_functor() );
 556 #       endif
 557         }
 558
 559         /// Deletes \p key from the list
 560         /** \anchor cds_nonintrusive_LazyList_rcu_erase_func
 561             The function searches an item with key \p key, calls \p f functor
 562             and deletes the item. If \p key is not found, the functor is not called.
 563
 564             The functor \p Func interface:
 565             \code
 566             struct extractor {
 567                 void operator()(value_type const& val) { ... }
 568             };
 569             \endcode
 570             The functor may be passed by reference with <tt>boost:ref</tt>
 571
 572             Since the key of LazyList's item type \p T is not explicitly specified,
 573             template parameter \p Q defines the key type searching in the list.
 574             The list item comparator should be able to compare the type \p T of list item
 575             and the type \p Q.
 576
 577             RCU \p synchronize method can be called. RCU should not be locked.
 578
 579             Return \p true if key is found and deleted, \p false otherwise
 580         */
 581         template <typename Q, typename Func>
 582         bool erase( Q const& key, Func f )
 583         {
 584             return erase_at( head(), key, intrusive_key_comparator(), f );
 585         }
 586
 587         /// Deletes the item from the list using \p pred predicate for searching
 588         /**
 589             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_erase_func "erase(Q const&, Func)"
 590             but \p pred is used for key comparing.
 591             \p Less functor has the interface like \p std::less.
 592             \p pred must imply the same element order as the comparator used for building the list.
 593         */
 594         template <typename Q, typename Less, typename Func>
 595         bool erase_with( Q const& key, Less pred, Func f )
 596         {
 597             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
 598         }
 599
 600         /// Extracts an item from the list
 601         /**
 602         @anchor cds_nonintrusive_LazyList_rcu_extract
 603             The function searches an item with key equal to \p key in the list,
 604             unlinks it from the list, and returns pointer to an item found in \p dest argument.
 605             If the item with the key equal to \p key is not found the function returns \p false.
 606
 607             @note The function does NOT call RCU read-side lock or synchronization,
 608             and does NOT dispose the item found. It just excludes the item from the list
 609             and returns a pointer to item found.
 610             You should lock RCU before calling this function.
 611
 612             \code
 613             #include <cds/urcu/general_buffered.h>
 614             #include <cds/container/lazy_list_rcu.h>
 615
 616             typedef cds::urcu::gc< general_buffered<> > rcu;
 617             typedef cds::container::LazyList< rcu, Foo > rcu_lazy_list;
 618
 619             rcu_lazy_list theList;
 620             // ...
 621
 622             rcu_lazy_list::exempt_ptr p;
 623             {
 624                 // first, we should lock RCU
 625                 rcu_lazy_list::rcu_lock sl;
 626
 627                 // Now, you can apply extract function
 628                 // Note that you must not delete the item found inside the RCU lock
 629                 if ( theList.extract( p, 10 )) {
 630                     // do something with p
 631                     ...
 632                 }
 633             }
 634             // Outside RCU lock section we may safely release extracted pointer.
 635             // release() passes the pointer to RCU reclamation cycle.
 636             p.release();
 637             \endcode
 638         */
 639         template <typename Q>
 640         bool extract( exempt_ptr& dest, Q const& key )
 641         {
 642             dest = extract_at( head(), key, intrusive_key_comparator() );
 643             return !dest.empty();
 644         }
 645
 646         /// Extracts an item from the list using \p pred predicate for searching
 647         /**
 648             This function is the analog for \ref cds_nonintrusive_LazyList_rcu_extract "extract(exempt_ptr&, Q const&)".
 649
 650             The \p pred is a predicate used for key comparing.
 651             \p Less has the interface like \p std::less.
 652             \p pred must imply the same element order as \ref key_comparator.
 653         */
 654         template <typename Q, typename Less>
 655         bool extract_with( exempt_ptr& dest, Q const& key, Less pred )
 656         {
 657             dest = extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 658             return !dest.empty();
 659         }
 660
 661         /// Finds the key \p key
 662         /** \anchor cds_nonintrusive_LazyList_rcu_find_val
 663             The function searches the item with key equal to \p key
 664             and returns \p true if it is found, and \p false otherwise.
 665
 666             The function makes RCU lock internally.
 667         */
 668         template <typename Q>
 669         bool find( Q const& key ) const
 670         {
 671             return find_at( head(), key, intrusive_key_comparator() );
 672         }
 673
 674         /// Finds the key \p val using \p pred predicate for searching
 675         /**
 676             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_val "find(Q const&)"
 677             but \p pred is used for key comparing.
 678             \p Less functor has the interface like \p std::less.
 679             \p pred must imply the same element order as the comparator used for building the list.
 680         */
 681         template <typename Q, typename Less>
 682         bool find_with( Q const& key, Less pred ) const
 683         {
 684             return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 685         }
 686
 687         /// Finds the key \p val and performs an action with it
 688         /** \anchor cds_nonintrusive_LazyList_rcu_find_func
 689             The function searches an item with key equal to \p val and calls the functor \p f for the item found.
 690             The interface of \p Func functor is:
 691             \code
 692             struct functor {
 693                 void operator()( value_type& item, Q& val );
 694             };
 695             \endcode
 696             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 697
 698             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 699
 700             The functor may change non-key fields of \p item. Note that the function is only guarantee
 701             that \p item cannot be deleted during functor is executing.
 702             The function does not serialize simultaneous access to the list \p item. If such access is
 703             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 704
 705             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 706             may modify both arguments.
 707
 708             The function makes RCU lock internally.
 709
 710             The function returns \p true if \p val is found, \p false otherwise.
 711         */
 712         template <typename Q, typename Func>
 713         bool find( Q& val, Func f ) const
 714         {
 715             return find_at( head(), val, intrusive_key_comparator(), f );
 716         }
 717
 718         /// Finds the key \p val using \p pred predicate for searching
 719         /**
 720             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_func "find(Q&, Func)"
 721             but \p pred is used for key comparing.
 722             \p Less functor has the interface like \p std::less.
 723             \p pred must imply the same element order as the comparator used for building the list.
 724         */
 725         template <typename Q, typename Less, typename Func>
 726         bool find_with( Q& val, Less pred, Func f ) const
 727         {
 728             return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
 729         }
 730
 731         /// Finds the key \p val and performs an action with it
 732         /** \anchor cds_nonintrusive_LazyList_rcu_find_cfunc
 733             The function searches an item with key equal to \p val and calls the functor \p f for the item found.
 734             The interface of \p Func functor is:
 735             \code
 736             struct functor {
 737                 void operator()( value_type& item, Q const& val );
 738             };
 739             \endcode
 740             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 741
 742             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 743
 744             The function does not serialize simultaneous access to the list \p item. If such access is
 745             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 746
 747             The function makes RCU lock internally.
 748
 749             The function returns \p true if \p val is found, \p false otherwise.
 750         */
 751         template <typename Q, typename Func>
 752         bool find( Q const& val, Func f ) const
 753         {
 754             return find_at( head(), val, intrusive_key_comparator(), f );
 755         }
 756
 757         /// Finds the key \p val using \p pred predicate for searching
 758         /**
 759             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_find_cfunc "find(Q const&, Func)"
 760             but \p pred is used for key comparing.
 761             \p Less functor has the interface like \p std::less.
 762             \p pred must imply the same element order as the comparator used for building the list.
 763         */
 764         template <typename Q, typename Less, typename Func>
 765         bool find_with( Q const& val, Less pred, Func f ) const
 766         {
 767             return find_at( head(), val, typename maker::template less_wrapper<Less>::type(), f );
 768         }
 769
 770         /// Finds the key \p val and return the item found
 771         /** \anchor cds_nonintrusive_LazyList_rcu_get
 772             The function searches the item with key equal to \p val and returns the pointer to item found.
 773             If \p val is not found it returns \p nullptr.
 774
 775             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 776
 777             RCU should be locked before call of this function.
 778             Returned item is valid only while RCU is locked:
 779             \code
 780             typedef cds::container::LazyList< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > ord_list;
 781             ord_list theList;
 782             // ...
 783             {
 784                 // Lock RCU
 785                 ord_list::rcu_lock lock;
 786
 787                 foo * pVal = theList.get( 5 );
 788                 if ( pVal ) {
 789                     // Deal with pVal
 790                     //...
 791                 }
 792                 // Unlock RCU by rcu_lock destructor
 793                 // pVal can be freed at any time after RCU has been unlocked
 794             }
 795             \endcode
 796         */
 797         template <typename Q>
 798         value_type * get( Q const& val ) const
 799         {
 800             return get_at( head(), val, intrusive_key_comparator());
 801         }
 802
 803         /// Finds the key \p val and return the item found
 804         /**
 805             The function is an analog of \ref cds_nonintrusive_LazyList_rcu_get "get(Q const&)"
 806             but \p pred is used for comparing the keys.
 807
 808             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 809             in any order.
 810             \p pred must imply the same element order as the comparator used for building the list.
 811         */
 812         template <typename Q, typename Less>
 813         value_type * get_with( Q const& val, Less pred ) const
 814         {
 815             return get_at( head(), val, typename maker::template less_wrapper<Less>::type());
 816         }
 817
 818         /// Checks if the list is empty
 819         bool empty() const
 820         {
 821             return base_class::empty();
 822         }
 823
 824         /// Returns list's item count
 825         /**
 826             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 827             this function always returns 0.
 828
 829             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 830             is empty. To check list emptyness use \ref empty() method.
 831         */
 832         size_t size() const
 833         {
 834             return base_class::size();
 835         }
 836
 837         /// Clears the list
 838         /**
 839             Post-condition: the list is empty
 840         */
 841         void clear()
 842         {
 843             base_class::clear();
 844         }
 845
 846     protected:
 847         //@cond
 848         bool insert_node_at( head_type& refHead, node_type * pNode )
 849         {
 850             assert( pNode != nullptr );
 851             scoped_node_ptr p( pNode );
 852
 853             if ( base_class::insert_at( &refHead, *pNode )) {
 854                 p.release();
 855                 return true;
 856             }
 857
 858             return false;
 859         }
 860
 861         template <typename Q>
 862         bool insert_at( head_type& refHead, Q const& val )
 863         {
 864             return insert_node_at( refHead, alloc_node( val ));
 865         }
 866
 867         template <typename... Args>
 868         bool emplace_at( head_type& refHead, Args&&... args )
 869         {
 870             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 871         }
 872
 873         template <typename Q, typename Func>
 874         bool insert_at( head_type& refHead, Q const& key, Func f )
 875         {
 876             scoped_node_ptr pNode( alloc_node( key ));
 877
 878 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 879 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 880             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 881             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 882             value_type& (* n2v)( node_type& ) = node_to_value;
 883             if ( base_class::insert_at( &refHead, *pNode, [&f,n2v](node_type& node){ cds::unref(f)( n2v(node) ); } ))
 884 #       else
 885             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node_to_value(node) ); } ))
 886 #       endif
 887 #   else
 888             insert_functor<Func>  wrapper( f );
 889             if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
 890 #   endif
 891             {
 892                 pNode.release();
 893                 return true;
 894             }
 895             return false;
 896         }
 897
 898         template <typename Q, typename Compare, typename Func>
 899         bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
 900         {
 901 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 902 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 903             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 904             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 905             value_type const& (* n2v)( node_type const& ) = node_to_value;
 906             return base_class::erase_at( &refHead, key, cmp, [&f,n2v](node_type const& node){ cds::unref(f)( n2v(node) ); } );
 907 #       else
 908             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ cds::unref(f)( node_to_value(node) ); } );
 909 #       endif
 910 #   else
 911             erase_functor<Func> wrapper( f );
 912             return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
 913 #   endif
 914         }
 915
 916         template <typename Q, typename Compare>
 917         node_type * extract_at( head_type& refHead, Q const& key, Compare cmp )
 918         {
 919             return base_class::extract_at( &refHead, key, cmp );
 920         }
 921
 922         template <typename Q, typename Func>
 923         std::pair<bool, bool> ensure_at( head_type& refHead, Q const& key, Func f )
 924         {
 925             scoped_node_ptr pNode( alloc_node( key ));
 926
 927 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 928 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 929             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 930             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 931             value_type& (* n2v)( node_type& ) = node_to_value;
 932             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 933                 [&f, &key, n2v](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, n2v(node), key ); });
 934 #       else
 935             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 936                 [&f, &key](bool bNew, node_type& node, node_type&){cds::unref(f)( bNew, node_to_value(node), key ); });
 937 #       endif
 938 #   else
 939             ensure_functor<Q, Func> wrapper( key, f );
 940             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
 941 #   endif
 942             if ( ret.first && ret.second )
 943                 pNode.release();
 944
 945             return ret;
 946         }
 947
 948         template <typename Q, typename Compare>
 949         bool find_at( head_type& refHead, Q const& key, Compare cmp ) const
 950         {
 951 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 952             return base_class::find_at( &refHead, key, cmp, [](node_type&, Q const &) {} );
 953 #       else
 954             return base_class::find_at( &refHead, key, cmp, empty_find_functor() );
 955 #       endif
 956         }
 957
 958         template <typename Q, typename Compare, typename Func>
 959         bool find_at( head_type& refHead, Q& val, Compare cmp, Func f ) const
 960         {
 961 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 962 #       ifdef CDS_BUG_STATIC_MEMBER_IN_LAMBDA
 963             // GCC 4.5-4.7: node_to_value is unaccessible from lambda,
 964             // like as MichaelList::node_to_value that requires to capture *this* despite on node_to_value is static function
 965             value_type& (* n2v)( node_type& ) = node_to_value;
 966             return base_class::find_at( &refHead, val, cmp, [&f,n2v](node_type& node, Q& val){ cds::unref(f)( n2v(node), val ); });
 967 #       else
 968             return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& val){ cds::unref(f)( node_to_value(node), val ); });
 969 #       endif
 970 #   else
 971             find_functor<Func>  wrapper( f );
 972             return base_class::find_at( &refHead, val, cmp, cds::ref(wrapper) );
 973 #   endif
 974         }
 975
 976         template <typename Q, typename Compare>
 977         value_type * get_at( head_type& refHead, Q const& val, Compare cmp ) const
 978         {
 979             node_type * pNode = base_class::get_at( &refHead, val, cmp );
 980             return pNode ? &pNode->m_Value : nullptr;
 981         }
 982
 983         //@endcond
 984     };
 985
 986 }} // namespace cds::container
 987
 988 #endif // #ifndef __CDS_CONTAINER_LAZY_LIST_RCU_H