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