cds/container/impl/lazy_kvlist.h

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