cds/container/michael_kvlist_rcu.h

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