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