cds/container/lazy_kvlist_rcu.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H
   4 #define __CDS_CONTAINER_LAZY_KVLIST_RCU_H
   5
   6 #include <cds/container/lazy_list_base.h>
   7 #include <cds/intrusive/lazy_list_rcu.h>
   8 #include <cds/container/details/make_lazy_kvlist.h>
   9 #include <cds/ref.h>
  10 #include <cds/details/functor_wrapper.h>
  11 #include <cds/details/std/memory.h>
  12
  13 namespace cds { namespace container {
  14
  15     /// Lazy ordered list (key-value pair), template specialization for \ref cds_urcu_desc "RCU"
  16     /** @ingroup cds_nonintrusive_list
  17         \anchor cds_nonintrusive_LazyKVList_rcu
  18
  19         This is key-value variation of non-intrusive LazyList.
  20         Like standard container, this implementation split a value stored into two part -
  21         constant key and alterable value.
  22
  23         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  24         The complexity of searching is <tt>O(N)</tt>.
  25
  26         Template arguments:
  27         - \p RCU - one of \ref cds_urcu_gc "RCU type"
  28         - \p Key - key type of an item stored in the list. It should be copy-constructible
  29         - \p Value - value type stored in the list
  30         - \p Traits - type traits, default is lazy_list::type_traits
  31
  32         It is possible to declare option-based list with cds::container::lazy_list::make_traits metafunction istead of \p Traits template
  33         argument. For example, the following traits-based declaration of gc::HP lazy list
  34         @note Before including <tt><cds/container/lazy_kvlist_rcu.h></tt> you should include appropriate RCU header file,
  35         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
  36         \code
  37         #include <cds/urcu/general_threaded.h>
  38         #include <cds/container/lazy_kvlist_rcu.h>
  39         // Declare comparator for the item
  40         struct my_compare {
  41             int operator ()( int i1, int i2 )
  42             {
  43                 return i1 - i2;
  44             }
  45         };
  46
  47         // Declare type_traits
  48         struct my_traits: public cds::container::lazy_list::type_traits
  49         {
  50             typedef my_compare compare;
  51         };
  52
  53         // Declare traits-based list
  54         typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int, my_traits >     traits_based_list;
  55         \endcode
  56
  57         is equivalent for the following option-based list
  58         \code
  59         #include <cds/urcu/general_threaded.h>
  60         #include <cds/container/lazy_kvlist_rcu.h>
  61
  62         // my_compare is the same
  63
  64         // Declare option-based list
  65         typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_threaded<> >, int, int,
  66             typename cds::container::lazy_list::make_traits<
  67                 cds::container::opt::compare< my_compare >     // item comparator option
  68             >::type
  69         >     option_based_list;
  70         \endcode
  71
  72         Template argument list \p Options of cds::container::lazy_list::make_traits metafunction are:
  73         - opt::compare - key comparison functor. No default functor is provided.
  74             If the option is not specified, the opt::less is used.
  75         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  76         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::empty is used.
  77         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  78         - opt::allocator - the allocator used for creating and freeing list's item. Default is \ref CDS_DEFAULT_ALLOCATOR macro.
  79         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  80             or opt::v::sequential_consistent (sequentially consisnent memory model).
  81         - opt::rcu_check_deadlock - a deadlock checking policy. Default is opt::v::rcu_throw_deadlock
  82     */
  83     template <
  84         typename RCU,
  85         typename Key,
  86         typename Value,
  87 #ifdef CDS_DOXYGEN_INVOKED
  88         typename Traits = lazy_list::type_traits
  89 #else
  90         typename Traits
  91 #endif
  92     >
  93     class LazyKVList< cds::urcu::gc<RCU>, Key, Value, Traits >:
  94 #ifdef CDS_DOXYGEN_INVOKED
  95         protected intrusive::LazyList< cds::urcu::gc<RCU>, implementation_defined, Traits >
  96 #else
  97         protected details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits >::type
  98 #endif
  99     {
 100         //@cond
 101         typedef details::make_lazy_kvlist< cds::urcu::gc<RCU>, Key, Value, Traits > options;
 102         typedef typename options::type  base_class;
 103         //@endcond
 104
 105     public:
 106 #ifdef CDS_DOXYGEN_INVOKED
 107         typedef Key                                 key_type        ;   ///< Key type
 108         typedef Value                               mapped_type     ;   ///< Type of value stored in the list
 109         typedef std::pair<key_type const, mapped_type> value_type   ;   ///< key/value pair stored in the list
 110 #else
 111         typedef typename options::key_type          key_type;
 112         typedef typename options::value_type        mapped_type;
 113         typedef typename options::pair_type         value_type;
 114 #endif
 115
 116         typedef typename base_class::gc             gc              ;   ///< Garbage collector used
 117         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
 118         typedef typename options::allocator_type    allocator_type  ;   ///< Allocator type used for allocate/deallocate the nodes
 119         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
 120         typedef typename options::key_comparator    key_comparator  ;   ///< key comparison functor
 121         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
 122         typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
 123
 124         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
 125         static CDS_CONSTEXPR_CONST bool c_bExtractLockExternal = base_class::c_bExtractLockExternal; ///< Group of \p extract_xxx functions require external locking
 126
 127     protected:
 128         //@cond
 129         typedef typename base_class::value_type     node_type;
 130         typedef typename options::cxx_allocator     cxx_allocator;
 131         typedef typename options::node_deallocator  node_deallocator;
 132         typedef typename options::type_traits::compare  intrusive_key_comparator;
 133
 134         typedef typename base_class::node_type      head_type;
 135         //@endcond
 136
 137     public:
 138         /// pointer to extracted node
 139         typedef cds::urcu::exempt_ptr< gc, node_type, value_type, typename options::type_traits::disposer,
 140             cds::urcu::details::conventional_exempt_pair_cast<node_type, value_type>
 141         > exempt_ptr;
 142
 143     private:
 144         //@cond
 145 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 146         template <typename Func>
 147         class insert_functor: protected cds::details::functor_wrapper<Func>
 148         {
 149             typedef cds::details::functor_wrapper<Func> base_class;
 150         public:
 151             insert_functor ( Func f )
 152                 : base_class( f )
 153             {}
 154
 155             void operator()( node_type& node )
 156             {
 157                 base_class::get()( node.m_Data );
 158             }
 159         };
 160
 161         template <typename Func>
 162         class ensure_functor: protected cds::details::functor_wrapper<Func>
 163         {
 164             typedef cds::details::functor_wrapper<Func> base_class;
 165         public:
 166             ensure_functor( Func f )
 167                 : base_class(f)
 168             {}
 169
 170             void operator ()( bool bNew, node_type& node, node_type& )
 171             {
 172                 base_class::get()( bNew, node.m_Data );
 173             }
 174         };
 175
 176         template <typename Func>
 177         class find_functor: protected cds::details::functor_wrapper<Func>
 178         {
 179             typedef cds::details::functor_wrapper<Func> base_class;
 180         public:
 181             find_functor( Func f )
 182                 : base_class(f)
 183             {}
 184
 185             template <typename Q>
 186             void operator ()( node_type& node, Q&  )
 187             {
 188                 base_class::get()( node.m_Data );
 189             }
 190         };
 191
 192         struct empty_find_functor
 193         {
 194             template <typename Q>
 195             void operator ()( node_type& node, Q& val ) const
 196             {}
 197         };
 198
 199         template <typename Func>
 200         struct erase_functor
 201         {
 202             Func m_func;
 203
 204             erase_functor( Func f )
 205                 : m_func( f )
 206             {}
 207
 208             void operator ()( node_type const & node )
 209             {
 210                 cds::unref(m_func)( const_cast<value_type&>(node.m_Data) );
 211             }
 212         };
 213 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 214         //@endcond
 215
 216     protected:
 217         //@cond
 218         template <typename K>
 219         static node_type * alloc_node(const K& key)
 220         {
 221             return cxx_allocator().New( key );
 222         }
 223
 224         template <typename K, typename V>
 225         static node_type * alloc_node( const K& key, const V& val )
 226         {
 227             return cxx_allocator().New( key, val );
 228         }
 229
 230 #ifdef CDS_EMPLACE_SUPPORT
 231         template <typename... Args>
 232         static node_type * alloc_node( Args&&... args )
 233         {
 234             return cxx_allocator().MoveNew( std::forward<Args>(args)... );
 235         }
 236 #endif
 237
 238         static void free_node( node_type * pNode )
 239         {
 240             cxx_allocator().Delete( pNode );
 241         }
 242
 243         struct node_disposer {
 244             void operator()( node_type * pNode )
 245             {
 246                 free_node( pNode );
 247             }
 248         };
 249         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 250
 251         head_type& head()
 252         {
 253             return base_class::m_Head;
 254         }
 255
 256         head_type& head() const
 257         {
 258             return const_cast<head_type&>( base_class::m_Head );
 259         }
 260
 261         head_type& tail()
 262         {
 263             return base_class::m_Tail;
 264         }
 265
 266         head_type& tail() const
 267         {
 268             return const_cast<head_type&>( base_class::m_Tail );
 269         }
 270
 271         //@endcond
 272
 273     protected:
 274         //@cond
 275         template <bool IsConst>
 276         class iterator_type: protected base_class::template iterator_type<IsConst>
 277         {
 278             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 279
 280             iterator_type( head_type const& pNode )
 281                 : iterator_base( const_cast<head_type *>(&pNode) )
 282             {}
 283             iterator_type( head_type const * pNode )
 284                 : iterator_base( const_cast<head_type *>(pNode) )
 285             {}
 286
 287             friend class LazyKVList;
 288
 289         public:
 290             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 291             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 292
 293             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 294             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 295
 296             iterator_type()
 297             {}
 298
 299             iterator_type( iterator_type const& src )
 300                 : iterator_base( src )
 301             {}
 302
 303             key_type const& key() const
 304             {
 305                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 306                 assert( p != null_ptr<typename iterator_base::value_ptr>() );
 307                 return p->m_Data.first;
 308             }
 309
 310             value_ref val() const
 311             {
 312                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 313                 assert( p != null_ptr<typename iterator_base::value_ptr>() );
 314                 return p->m_Data.second;
 315             }
 316
 317             pair_ptr operator ->() const
 318             {
 319                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 320                 return p ? &(p->m_Data) : null_ptr<pair_ptr>();
 321             }
 322
 323             pair_ref operator *() const
 324             {
 325                 typename iterator_base::value_ref p = iterator_base::operator *();
 326                 return p.m_Data;
 327             }
 328
 329             /// Pre-increment
 330             iterator_type& operator ++()
 331             {
 332                 iterator_base::operator ++();
 333                 return *this;
 334             }
 335
 336             template <bool C>
 337             bool operator ==(iterator_type<C> const& i ) const
 338             {
 339                 return iterator_base::operator ==(i);
 340             }
 341             template <bool C>
 342             bool operator !=(iterator_type<C> const& i ) const
 343             {
 344                 return iterator_base::operator !=(i);
 345             }
 346         };
 347         //@endcond
 348
 349     public:
 350         /// Forward iterator
 351         typedef iterator_type<false>    iterator;
 352
 353         /// Const forward iterator
 354         typedef iterator_type<true>     const_iterator;
 355
 356         /// Returns a forward iterator addressing the first element in a list
 357         /**
 358             For empty list \code begin() == end() \endcode
 359         */
 360         iterator begin()
 361         {
 362             iterator it( head() );
 363             ++it ;  // skip dummy head
 364             return it;
 365         }
 366
 367         /// Returns an iterator that addresses the location succeeding the last element in a list
 368         /**
 369             Do not use the value returned by <tt>end</tt> function to access any item.
 370             Internally, <tt>end</tt> returning value pointing to dummy tail node.
 371
 372             The returned value can be used only to control reaching the end of the list.
 373             For empty list \code begin() == end() \endcode
 374         */
 375         iterator end()
 376         {
 377             return iterator( tail() );
 378         }
 379
 380         /// Returns a forward const iterator addressing the first element in a list
 381         //@{
 382         const_iterator begin() const
 383         {
 384             const_iterator it( head() );
 385             ++it;   // skip dummy head
 386             return it;
 387         }
 388         const_iterator cbegin()
 389         {
 390             const_iterator it( head() );
 391             ++it;   // skip dummy head
 392             return it;
 393         }
 394         //@}
 395
 396         /// Returns an const iterator that addresses the location succeeding the last element in a list
 397         //@{
 398         const_iterator end() const
 399         {
 400             return const_iterator( tail());
 401         }
 402         const_iterator cend()
 403         {
 404             return const_iterator( tail());
 405         }
 406         //@}
 407
 408     public:
 409         /// Default constructor
 410         /**
 411             Initializes empty list
 412         */
 413         LazyKVList()
 414         {}
 415
 416         /// List destructor
 417         /**
 418             Clears the list
 419         */
 420         ~LazyKVList()
 421         {
 422             clear();
 423         }
 424
 425         /// Inserts new node with key and default value
 426         /**
 427             The function creates a node with \p key and default value, and then inserts the node created into the list.
 428
 429             Preconditions:
 430             - The \ref key_type should be constructible from value of type \p K.
 431                 In trivial case, \p K is equal to \ref key_type.
 432             - The \ref mapped_type should be default-constructible.
 433
 434             The function makes RCU lock internally.
 435
 436             Returns \p true if inserting successful, \p false otherwise.
 437         */
 438         template <typename K>
 439         bool insert( const K& key )
 440         {
 441             return insert_at( head(), key );
 442         }
 443
 444         /// Inserts new node with a key and a value
 445         /**
 446             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 447
 448             Preconditions:
 449             - The \ref key_type should be constructible from \p key of type \p K.
 450             - The \ref mapped_type should be constructible from \p val of type \p V.
 451
 452             The function makes RCU lock internally.
 453
 454             Returns \p true if inserting successful, \p false otherwise.
 455         */
 456         template <typename K, typename V>
 457         bool insert( const K& key, const V& val )
 458         {
 459             return insert_at( head(), key, val );
 460         }
 461
 462         /// Inserts new node and initializes it by a functor
 463         /**
 464             This function inserts new node with key \p key and if inserting is successful then it calls
 465             \p func functor with signature
 466             \code
 467                 struct functor {
 468                     void operator()( value_type& item );
 469                 };
 470             \endcode
 471
 472             The argument \p item of user-defined functor \p func is the reference
 473             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 474             User-defined functor \p func should guarantee that during changing item's value no any other changes
 475             could be made on this list's item by concurrent threads.
 476             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 477             and it is called only if inserting is successful.
 478
 479             The key_type should be constructible from value of type \p K.
 480
 481             The function allows to split creating of new item into two part:
 482             - create item from \p key;
 483             - insert new item into the list;
 484             - if inserting is successful, initialize the value of item by calling \p func functor
 485
 486             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 487             it is preferable that the initialization should be completed only if inserting is successful.
 488
 489             The function makes RCU lock internally.
 490         */
 491         template <typename K, typename Func>
 492         bool insert_key( const K& key, Func func )
 493         {
 494             return insert_key_at( head(), key, func );
 495         }
 496
 497 #   ifdef CDS_EMPLACE_SUPPORT
 498         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 499         /**
 500             Returns \p true if inserting successful, \p false otherwise.
 501
 502             The function makes RCU lock internally.
 503
 504             @note This function is available only for compiler that supports
 505             variadic template and move semantics
 506         */
 507         template <typename... Args>
 508         bool emplace( Args&&... args )
 509         {
 510             return emplace_at( head(), std::forward<Args>(args)... );
 511         }
 512 #   endif
 513
 514         /// Ensures that the \p key exists in the list
 515         /**
 516             The operation performs inserting or changing data with lock-free manner.
 517
 518             If the \p key not found in the list, then the new item created from \p key
 519             is inserted into the list (note that in this case the \ref key_type should be
 520             copy-constructible from type \p K).
 521             Otherwise, the functor \p func is called with item found.
 522             The functor \p Func may be a function with signature:
 523             \code
 524                 void func( bool bNew, value_type& item );
 525             \endcode
 526             or a functor:
 527             \code
 528                 struct my_functor {
 529                     void operator()( bool bNew, value_type& item );
 530                 };
 531             \endcode
 532
 533             with arguments:
 534             - \p bNew - \p true if the item has been inserted, \p false otherwise
 535             - \p item - item of the list
 536
 537             The functor may change any fields of the \p item.second that is \ref mapped_type;
 538             however, \p func must guarantee that during changing no any other modifications
 539             could be made on this item by concurrent threads.
 540
 541             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 542
 543             The function makes RCU lock internally.
 544
 545             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 546             \p second is true if new item has been added or \p false if the item with \p key
 547             already is in the list.
 548         */
 549         template <typename K, typename Func>
 550         std::pair<bool, bool> ensure( const K& key, Func f )
 551         {
 552             return ensure_at( head(), key, f );
 553         }
 554
 555         /// Deletes \p key from the list
 556         /** \anchor cds_nonintrusive_LazyKVList_rcu_erase
 557
 558             RCU \p synchronize method can be called. RCU should not be locked.
 559
 560             Returns \p true if \p key is found and has been deleted, \p false otherwise
 561         */
 562         template <typename K>
 563         bool erase( K const& key )
 564         {
 565             return erase_at( head(), key, intrusive_key_comparator() );
 566         }
 567
 568         /// Deletes the item from the list using \p pred predicate for searching
 569         /**
 570             The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase "erase(K const&)"
 571             but \p pred is used for key comparing.
 572             \p Less functor has the interface like \p std::less.
 573             \p pred must imply the same element order as the comparator used for building the list.
 574         */
 575         template <typename K, typename Less>
 576         bool erase_with( K const& key, Less pred )
 577         {
 578             return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
 579         }
 580
 581         /// Deletes \p key from the list
 582         /** \anchor cds_nonintrusive_LazyKVList_rcu_erase_func
 583             The function searches an item with key \p key, calls \p f functor
 584             and deletes the item. If \p key is not found, the functor is not called.
 585
 586             The functor \p Func interface:
 587             \code
 588             struct extractor {
 589                 void operator()(value_type& val) { ... }
 590             };
 591             \endcode
 592             The functor may be passed by reference with <tt>boost:ref</tt>
 593
 594             RCU \p synchronize method can be called. RCU should not be locked.
 595
 596             Returns \p true if key is found and deleted, \p false otherwise
 597         */
 598         template <typename K, typename Func>
 599         bool erase( K const& key, Func f )
 600         {
 601             return erase_at( head(), key, intrusive_key_comparator(), f );
 602         }
 603
 604         /// Deletes the item from the list using \p pred predicate for searching
 605         /**
 606             The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_erase_func "erase(K const&, Func)"
 607             but \p pred is used for key comparing.
 608             \p Less functor has the interface like \p std::less.
 609             \p pred must imply the same element order as the comparator used for building the list.
 610         */
 611         template <typename K, typename Less, typename Func>
 612         bool erase_with( K const& key, Less pred, Func f )
 613         {
 614             return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
 615         }
 616
 617         /// Extracts an item from the list
 618         /**
 619         @anchor cds_nonintrusive_LazyKVList_rcu_extract
 620             The function searches an item with key equal to \p key in the list,
 621             unlinks it from the list, and returns pointer to an item found in \p dest argument.
 622             If \p key is not found the function returns \p false.
 623
 624             @note The function does NOT call RCU read-side lock or synchronization,
 625             and does NOT dispose the item found. It just excludes the item from the list
 626             and returns a pointer to item found.
 627             You should lock RCU before calling this function.
 628
 629             \code
 630             #include <cds/urcu/general_buffered.h>
 631             #include <cds/container/lazy_kvlist_rcu.h>
 632
 633             typedef cds::urcu::gc< general_buffered<> > rcu;
 634             typedef cds::container::LazyKVList< rcu, int, Foo > rcu_lazy_list;
 635
 636             rcu_lazy_list theList;
 637             // ...
 638
 639             rcu_lazy_list::exempt_ptr p;
 640             {
 641                 // first, we should lock RCU
 642                 rcu_lazy_list::rcu_lock sl;
 643
 644                 // Now, you can apply extract function
 645                 // Note that you must not delete the item found inside the RCU lock
 646                 if ( theList.extract( p, 10 )) {
 647                     // do something with p
 648                     ...
 649                 }
 650             }
 651             // Outside RCU lock section we may safely release extracted pointer.
 652             // release() passes the pointer to RCU reclamation cycle.
 653             p.release();
 654             \endcode
 655         */
 656         template <typename K>
 657         bool extract( exempt_ptr& dest, K const& key )
 658         {
 659             dest = extract_at( head(), key, intrusive_key_comparator() );
 660             return !dest.empty();
 661         }
 662
 663         /// Extracts an item from the list using \p pred predicate for searching
 664         /**
 665             This function is the analog for \ref cds_nonintrusive_LazyKVList_rcu_extract "extract(exempt_ptr&, K const&)".
 666             The \p pred is a predicate used for key comparing.
 667             \p Less has the interface like \p std::less.
 668             \p pred must imply the same element order as \ref key_comparator.
 669         */
 670         template <typename K, typename Less>
 671         bool extract_with( exempt_ptr& dest, K const& key, Less pred )
 672         {
 673             dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
 674             return !dest.empty();
 675         }
 676
 677         /// Finds the key \p key
 678         /** \anchor cds_nonintrusive_LazyKVList_rcu_find_val
 679             The function searches the item with key equal to \p key
 680             and returns \p true if it is found, and \p false otherwise
 681
 682             The function applies RCU lock internally.
 683         */
 684         template <typename Q>
 685         bool find( Q const& key ) const
 686         {
 687             return find_at( head(), key, intrusive_key_comparator() );
 688         }
 689
 690         /// Finds the key \p val using \p pred predicate for searching
 691         /**
 692             The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_val "find(Q const&)"
 693             but \p pred is used for key comparing.
 694             \p Less functor has the interface like \p std::less.
 695             \p pred must imply the same element order as the comparator used for building the list.
 696         */
 697         template <typename Q, typename Less>
 698         bool find_with( Q const& key, Less pred ) const
 699         {
 700             return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
 701         }
 702
 703         /// Finds the key \p key and performs an action with it
 704         /** \anchor cds_nonintrusive_LazyKVList_rcu_find_func
 705             The function searches an item with key equal to \p key and calls the functor \p f for the item found.
 706             The interface of \p Func functor is:
 707             \code
 708             struct functor {
 709                 void operator()( value_type& item );
 710             };
 711             \endcode
 712             where \p item is the item found.
 713
 714             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 715
 716             The functor may change <tt>item.second</tt> that is reference to value of node.
 717             Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
 718             The function does not serialize simultaneous access to the list \p item. If such access is
 719             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 720
 721             The function applies RCU lock internally.
 722
 723             The function returns \p true if \p key is found, \p false otherwise.
 724         */
 725         template <typename Q, typename Func>
 726         bool find( Q const& key, Func f ) const
 727         {
 728             return find_at( head(), key, intrusive_key_comparator(), f );
 729         }
 730
 731         /// Finds the key \p val using \p pred predicate for searching
 732         /**
 733             The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_find_func "find(Q const&, Func)"
 734             but \p pred is used for key comparing.
 735             \p Less functor has the interface like \p std::less.
 736             \p pred must imply the same element order as the comparator used for building the list.
 737         */
 738         template <typename Q, typename Less, typename Func>
 739         bool find_with( Q const& key, Less pred, Func f ) const
 740         {
 741             return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
 742         }
 743
 744         /// Finds \p key and return the item found
 745         /** \anchor cds_nonintrusive_LazyKVList_rcu_get
 746             The function searches the item with \p key and returns the pointer to item found.
 747             If \p key is not found it returns \p NULL.
 748
 749             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 750
 751             RCU should be locked before call of this function.
 752             Returned item is valid only while RCU is locked:
 753             \code
 754             typedef cds::container::LazyKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
 755             ord_list theList;
 756             // ...
 757             {
 758                 // Lock RCU
 759                 ord_list::rcu_lock lock;
 760
 761                 ord_list::value_type * pVal = theList.get( 5 );
 762                 if ( pVal ) {
 763                     // Deal with pVal
 764                     //...
 765                 }
 766                 // Unlock RCU by rcu_lock destructor
 767                 // pVal can be freed at any time after RCU has been unlocked
 768             }
 769             \endcode
 770         */
 771         template <typename K>
 772         value_type * get( K const& key ) const
 773         {
 774             return get_at( head(), key, intrusive_key_comparator());
 775         }
 776
 777         /// Finds \p key and return the item found
 778         /**
 779             The function is an analog of \ref cds_nonintrusive_LazyKVList_rcu_get "get(K const&)"
 780             but \p pred is used for comparing the keys.
 781
 782             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 783             in any order.
 784             \p pred must imply the same element order as the comparator used for building the list.
 785         */
 786         template <typename K, typename Less>
 787         value_type * get_with( K const& key, Less pred ) const
 788         {
 789             return get_at( head(), key, typename options::template less_wrapper<Less>::type());
 790         }
 791
 792         /// Checks if the list is empty
 793         bool empty() const
 794         {
 795             return base_class::empty();
 796         }
 797
 798         /// Returns list's item count
 799         /**
 800             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 801             this function always returns 0.
 802
 803             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 804             is empty. To check list emptyness use \ref empty() method.
 805         */
 806         size_t size() const
 807         {
 808             return base_class::size();
 809         }
 810
 811         /// Clears the list
 812         /**
 813             Post-condition: the list is empty
 814         */
 815         void clear()
 816         {
 817             base_class::clear();
 818         }
 819
 820     protected:
 821         //@cond
 822         bool insert_node_at( head_type& refHead, node_type * pNode )
 823         {
 824             assert( pNode != null_ptr<node_type *>() );
 825             scoped_node_ptr p( pNode );
 826
 827             if ( base_class::insert_at( &refHead, *p )) {
 828                 p.release();
 829                 return true;
 830             }
 831
 832             return false;
 833         }
 834
 835         template <typename K>
 836         bool insert_at( head_type& refHead, const K& key )
 837         {
 838             return insert_node_at( refHead, alloc_node( key ));
 839         }
 840
 841         template <typename K, typename V>
 842         bool insert_at( head_type& refHead, const K& key, const V& val )
 843         {
 844             return insert_node_at( refHead, alloc_node( key, val ));
 845         }
 846
 847         template <typename K, typename Func>
 848         bool insert_key_at( head_type& refHead, const K& key, Func f )
 849         {
 850             scoped_node_ptr pNode( alloc_node( key ));
 851
 852 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 853             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); } ))
 854 #   else
 855             insert_functor<Func>  wrapper( f );
 856             if ( base_class::insert_at( &refHead, *pNode, cds::ref(wrapper) ))
 857 #   endif
 858             {
 859                 pNode.release();
 860                 return true;
 861             }
 862             return false;
 863         }
 864
 865 #   ifdef CDS_EMPLACE_SUPPORT
 866         template <typename... Args>
 867         bool emplace_at( head_type& refHead, Args&&... args )
 868         {
 869             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 870         }
 871 #   endif
 872
 873         template <typename K, typename Compare>
 874         bool erase_at( head_type& refHead, K const& key, Compare cmp )
 875         {
 876             return base_class::erase_at( &refHead, key, cmp );
 877         }
 878
 879         template <typename K, typename Compare, typename Func>
 880         bool erase_at( head_type& refHead, K const & key, Compare cmp, Func f )
 881         {
 882 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 883             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){cds::unref(f)( const_cast<value_type&>(node.m_Data)); });
 884 #   else
 885             erase_functor<Func> wrapper( f );
 886             return base_class::erase_at( &refHead, key, cmp, cds::ref(wrapper) );
 887 #   endif
 888         }
 889
 890         template <typename K, typename Func>
 891         std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
 892         {
 893             scoped_node_ptr pNode( alloc_node( key ));
 894
 895 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 896             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 897                 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
 898 #   else
 899             ensure_functor<Func> wrapper( f );
 900             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode, cds::ref(wrapper));
 901 #   endif
 902             if ( ret.first && ret.second )
 903                 pNode.release();
 904
 905             return ret;
 906         }
 907
 908         template <typename K, typename Compare>
 909         node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
 910         {
 911             return base_class::extract_at( &refHead, key, cmp );
 912         }
 913
 914         template <typename K, typename Compare>
 915         bool find_at( head_type& refHead, K const& key, Compare cmp ) const
 916         {
 917 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 918             return base_class::find_at( &refHead, key, cmp, [](node_type&, K const&) {} );
 919 #       else
 920             return base_class::find_at( &refHead, key, cmp, empty_find_functor() );
 921 #       endif
 922         }
 923
 924         template <typename K, typename Compare, typename Func>
 925         bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
 926         {
 927 #   ifdef CDS_CXX11_LAMBDA_SUPPORT
 928             return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ cds::unref(f)( node.m_Data ); });
 929 #   else
 930             find_functor<Func>  wrapper( f );
 931             return base_class::find_at( &refHead, key, cmp, cds::ref(wrapper) );
 932 #   endif
 933         }
 934
 935         template <typename K, typename Compare>
 936         value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
 937         {
 938             node_type * pNode = base_class::get_at( &refHead, val, cmp );
 939             return pNode ? &pNode->m_Data : null_ptr<value_type *>();
 940         }
 941
 942         //@endcond
 943     };
 944
 945 }}  // namespace cds::container
 946
 947 #endif  // #ifndef __CDS_CONTAINER_LAZY_KVLIST_RCU_H