cds/container/lazy_kvlist_rcu.h

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