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