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