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 cds::gc::guarded_ptr< gc, 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()
 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()
 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             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 477         }
 478
 479         /// Deletes \p key from the list
 480         /** \anchor cds_nonintrusive_LazyKVList_hp_erase_func
 481             The function searches an item with key \p key, calls \p f functor with item found
 482             and deletes it. If \p key is not found, the functor is not called.
 483
 484             The functor \p Func interface:
 485             \code
 486             struct extractor {
 487                 void operator()(value_type& val) { ... }
 488             };
 489             \endcode
 490             The functor may be passed by reference with <tt>boost:ref</tt>
 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             return erase_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
 511         }
 512
 513         /// Extracts the item from the list with specified \p key
 514         /** \anchor cds_nonintrusive_LazyKVList_hp_extract
 515             The function searches an item with key equal to \p key,
 516             unlinks it from the list, and returns it in \p dest parameter.
 517             If the item with key equal to \p key is not found the function returns \p false.
 518
 519             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 520
 521             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 522
 523             Usage:
 524             \code
 525             typedef cds::container::LazyKVList< cds::gc::HP, int, foo, my_traits >  ord_list;
 526             ord_list theList;
 527             // ...
 528             {
 529                 ord_list::guarded_ptr gp;
 530                 theList.extract( gp, 5 );
 531                 // Deal with gp
 532                 // ...
 533
 534                 // Destructor of gp releases internal HP guard and frees the item
 535             }
 536             \endcode
 537         */
 538         template <typename K>
 539         bool extract( guarded_ptr& dest, K const& key )
 540         {
 541             return extract_at( head(), dest.guard(), key, intrusive_key_comparator() );
 542         }
 543
 544         /// Extracts the item from the list with comparing functor \p pred
 545         /**
 546             The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_extract "extract(guarded_ptr&, K const&)"
 547             but \p pred predicate is used for key comparing.
 548
 549             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 550             in any order.
 551             \p pred must imply the same element order as the comparator used for building the list.
 552         */
 553         template <typename K, typename Less>
 554         bool extract_with( guarded_ptr& dest, K const& key, Less pred )
 555         {
 556             return extract_at( head(), dest.guard(), key, typename maker::template less_wrapper<Less>::type() );
 557         }
 558
 559         /// Finds the key \p key
 560         /** \anchor cds_nonintrusive_LazyKVList_hp_find_val
 561             The function searches the item with key equal to \p key
 562             and returns \p true if it is found, and \p false otherwise
 563         */
 564         template <typename Q>
 565         bool find( Q const& key )
 566         {
 567             return find_at( head(), key, intrusive_key_comparator() );
 568         }
 569
 570         /// Finds the key \p val using \p pred predicate for searching
 571         /**
 572             The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_find_val "find(Q const&)"
 573             but \p pred is used for key comparing.
 574             \p Less functor has the interface like \p std::less.
 575             \p pred must imply the same element order as the comparator used for building the list.
 576         */
 577         template <typename Q, typename Less>
 578         bool find_with( Q const& key, Less pred )
 579         {
 580             return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
 581         }
 582
 583         /// Finds the key \p key and performs an action with it
 584         /** \anchor cds_nonintrusive_LazyKVList_hp_find_func
 585             The function searches an item with key equal to \p key and calls the functor \p f for the item found.
 586             The interface of \p Func functor is:
 587             \code
 588             struct functor {
 589                 void operator()( value_type& item );
 590             };
 591             \endcode
 592             where \p item is the item found.
 593
 594             You may pass \p f argument by reference using \p std::ref.
 595
 596             The functor may change <tt>item.second</tt> that is reference to value of node.
 597             Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
 598             The function does not serialize simultaneous access to the list \p item. If such access is
 599             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 600
 601             The function returns \p true if \p key is found, \p false otherwise.
 602         */
 603         template <typename Q, typename Func>
 604         bool find( Q const& key, Func f )
 605         {
 606             return find_at( head(), key, intrusive_key_comparator(), f );
 607         }
 608
 609         /// Finds the key \p val using \p pred predicate for searching
 610         /**
 611             The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_find_func "find(Q&, Func)"
 612             but \p pred is used for key comparing.
 613             \p Less functor has the interface like \p std::less.
 614             \p pred must imply the same element order as the comparator used for building the list.
 615         */
 616         template <typename Q, typename Less, typename Func>
 617         bool find_with( Q const& key, Less pred, Func f )
 618         {
 619             return find_at( head(), key, typename maker::template less_wrapper<Less>::type(), f );
 620         }
 621
 622         /// Finds \p key and return the item found
 623         /** \anchor cds_nonintrusive_LazyKVList_hp_get
 624             The function searches the item with key equal to \p key
 625             and assigns the item found to guarded pointer \p ptr.
 626             The function returns \p true if \p key is found, and \p false otherwise.
 627             If \p key is not found the \p ptr parameter is not changed.
 628
 629             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 630
 631             Usage:
 632             \code
 633             typedef cds::container::LazyKVList< cds::gc::HP, int, foo, my_traits >  ord_list;
 634             ord_list theList;
 635             // ...
 636             {
 637                 ord_list::guarded_ptr gp;
 638                 if ( theList.get( gp, 5 )) {
 639                     // Deal with gp
 640                     //...
 641                 }
 642                 // Destructor of guarded_ptr releases internal HP guard and frees the item
 643             }
 644             \endcode
 645
 646             Note the compare functor specified for class \p Traits template parameter
 647             should accept a parameter of type \p K that can be not the same as \p key_type.
 648         */
 649         template <typename K>
 650         bool get( guarded_ptr& ptr, K const& key )
 651         {
 652             return get_at( head(), ptr.guard(), key, intrusive_key_comparator() );
 653         }
 654
 655         /// Finds the key \p val and return the item found
 656         /**
 657             The function is an analog of \ref cds_nonintrusive_LazyKVList_hp_get "get(guarded_ptr& ptr, K const&)"
 658             but \p pred is used for comparing the keys.
 659
 660             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 661             in any order.
 662             \p pred must imply the same element order as the comparator used for building the list.
 663         */
 664         template <typename K, typename Less>
 665         bool get_with( guarded_ptr& ptr, K const& key, Less pred )
 666         {
 667             return get_at( head(), ptr.guard(), key, typename maker::template less_wrapper<Less>::type() );
 668         }
 669
 670         /// Checks if the list is empty
 671         bool empty() const
 672         {
 673             return base_class::empty();
 674         }
 675
 676         /// Returns list's item count
 677         /**
 678             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 679             this function always returns 0.
 680
 681             @note Even if you use real item counter and it returns 0, this fact is not mean that the list
 682             is empty. To check list emptyness use \ref empty() method.
 683         */
 684         size_t size() const
 685         {
 686             return base_class::size();
 687         }
 688
 689         /// Clears the list
 690         void clear()
 691         {
 692             base_class::clear();
 693         }
 694
 695     protected:
 696         //@cond
 697         bool insert_node_at( head_type& refHead, node_type * pNode )
 698         {
 699             assert( pNode != nullptr );
 700             scoped_node_ptr p( pNode );
 701
 702             if ( base_class::insert_at( &refHead, *p )) {
 703                 p.release();
 704                 return true;
 705             }
 706
 707             return false;
 708         }
 709
 710         template <typename K>
 711         bool insert_at( head_type& refHead, const K& key )
 712         {
 713             return insert_node_at( refHead, alloc_node( key ));
 714         }
 715
 716         template <typename K, typename V>
 717         bool insert_at( head_type& refHead, const K& key, const V& val )
 718         {
 719             return insert_node_at( refHead, alloc_node( key, val ));
 720         }
 721
 722         template <typename K, typename Func>
 723         bool insert_key_at( head_type& refHead, const K& key, Func f )
 724         {
 725             scoped_node_ptr pNode( alloc_node( key ));
 726
 727             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); } )) {
 728                 pNode.release();
 729                 return true;
 730             }
 731             return false;
 732         }
 733
 734         template <typename... Args>
 735         bool emplace_at( head_type& refHead, Args&&... args )
 736         {
 737             return insert_node_at( refHead, alloc_node( std::forward<Args>(args)... ));
 738         }
 739
 740         template <typename K, typename Compare>
 741         bool erase_at( head_type& refHead, K const& key, Compare cmp )
 742         {
 743             return base_class::erase_at( &refHead, key, cmp );
 744         }
 745
 746         template <typename K, typename Compare, typename Func>
 747         bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
 748         {
 749             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const & node){f( const_cast<value_type&>(node.m_Data)); });
 750         }
 751
 752         template <typename K, typename Compare>
 753         bool extract_at( head_type& refHead, typename gc::Guard& dest, K const& key, Compare cmp )
 754         {
 755             return base_class::extract_at( &refHead, dest, key, cmp );
 756         }
 757
 758         template <typename K, typename Func>
 759         std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
 760         {
 761             scoped_node_ptr pNode( alloc_node( key ));
 762
 763             std::pair<bool, bool> ret = base_class::ensure_at( &refHead, *pNode,
 764                 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); });
 765             if ( ret.first && ret.second )
 766                 pNode.release();
 767
 768             return ret;
 769         }
 770
 771         template <typename K, typename Compare>
 772         bool find_at( head_type& refHead, K const& key, Compare cmp )
 773         {
 774             return base_class::find_at( &refHead, key, cmp );
 775         }
 776
 777         template <typename K, typename Compare, typename Func>
 778         bool find_at( head_type& refHead, K& key, Compare cmp, Func f )
 779         {
 780             return base_class::find_at( &refHead, key, cmp, [&f]( node_type& node, K& ){ f( node.m_Data ); });
 781         }
 782
 783         template <typename K, typename Compare>
 784         bool get_at( head_type& refHead, typename gc::Guard& guard, K const& key, Compare cmp )
 785         {
 786             return base_class::get_at( &refHead, guard, key, cmp );
 787         }
 788
 789         //@endcond
 790     };
 791
 792 }}  // namespace cds::container
 793
 794 #endif  // #ifndef __CDS_CONTAINER_IMPL_LAZY_KVLIST_H