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