cds/container/michael_kvlist_rcu.h

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