cds/container/lazy_kvlist_rcu.h

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