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 <cds/container/michael_list_base.h>
   7 #include <cds/intrusive/michael_list_rcu.h>
   8 #include <cds/container/details/make_michael_kvlist.h>
   9 #include <cds/ref.h>
  10 #include <cds/details/functor_wrapper.h>
  11 #include <cds/details/std/memory.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 #   ifdef CDS_EMPLACE_SUPPORT
 232         template <typename K, typename... Args>
 233         static node_type * alloc_node( K&& key, Args&&... args )
 234         {
 235             return cxx_allocator().MoveNew( std::forward<K>(key), std::forward<Args>(args)...);
 236         }
 237 #   endif
 238
 239         static void free_node( node_type * pNode )
 240         {
 241             cxx_allocator().Delete( pNode );
 242         }
 243
 244         struct node_disposer {
 245             void operator()( node_type * pNode )
 246             {
 247                 free_node( pNode );
 248             }
 249         };
 250         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
 251
 252         head_type& head()
 253         {
 254             return base_class::m_pHead;
 255         }
 256
 257         head_type& head() const
 258         {
 259             return const_cast<head_type&>( base_class::m_pHead );
 260         }
 261         //@endcond
 262
 263     protected:
 264         //@cond
 265         template <bool IsConst>
 266         class iterator_type: protected base_class::template iterator_type<IsConst>
 267         {
 268             typedef typename base_class::template iterator_type<IsConst>    iterator_base;
 269
 270             iterator_type( head_type const& pNode )
 271                 : iterator_base( pNode )
 272             {}
 273
 274             friend class MichaelKVList;
 275
 276         public:
 277             typedef typename cds::details::make_const_type<mapped_type, IsConst>::reference  value_ref;
 278             typedef typename cds::details::make_const_type<mapped_type, IsConst>::pointer    value_ptr;
 279
 280             typedef typename cds::details::make_const_type<value_type,  IsConst>::reference  pair_ref;
 281             typedef typename cds::details::make_const_type<value_type,  IsConst>::pointer    pair_ptr;
 282
 283             iterator_type()
 284             {}
 285
 286             iterator_type( iterator_type const& src )
 287                 : iterator_base( src )
 288             {}
 289
 290             key_type const& key() const
 291             {
 292                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 293                 assert( p != null_ptr<typename iterator_base::value_ptr>() );
 294                 return p->m_Data.first;
 295             }
 296
 297             pair_ptr operator ->() const
 298             {
 299                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 300                 return p ? &(p->m_Data) : null_ptr<pair_ptr>();
 301             }
 302
 303             pair_ref operator *() const
 304             {
 305                 typename iterator_base::value_ref p = iterator_base::operator *();
 306                 return p.m_Data;
 307             }
 308
 309             value_ref val() const
 310             {
 311                 typename iterator_base::value_ptr p = iterator_base::operator ->();
 312                 assert( p != null_ptr<typename iterator_base::value_ptr>() );
 313                 return p->m_Data.second;
 314             }
 315
 316             /// Pre-increment
 317             iterator_type& operator ++()
 318             {
 319                 iterator_base::operator ++();
 320                 return *this;
 321             }
 322
 323             template <bool C>
 324             bool operator ==(iterator_type<C> const& i ) const
 325             {
 326                 return iterator_base::operator ==(i);
 327             }
 328             template <bool C>
 329             bool operator !=(iterator_type<C> const& i ) const
 330             {
 331                 return iterator_base::operator !=(i);
 332             }
 333         };
 334         //@endcond
 335
 336     public:
 337         /// Forward iterator
 338         typedef iterator_type<false>    iterator;
 339
 340         /// Const forward iterator
 341         typedef iterator_type<true>     const_iterator;
 342
 343         /// Returns a forward iterator addressing the first element in a list
 344         /**
 345             For empty list \code begin() == end() \endcode
 346         */
 347         iterator begin()
 348         {
 349             return iterator( head() );
 350         }
 351
 352         /// Returns an iterator that addresses the location succeeding the last element in a list
 353         /**
 354             Do not use the value returned by <tt>end</tt> function to access any item.
 355             Internally, <tt>end</tt> returning value equals to <tt>NULL</tt>.
 356
 357             The returned value can be used only to control reaching the end of the list.
 358             For empty list \code begin() == end() \endcode
 359         */
 360         iterator end()
 361         {
 362             return iterator();
 363         }
 364
 365         /// Returns a forward const iterator addressing the first element in a list
 366         //@{
 367         const_iterator begin() const
 368         {
 369             return const_iterator( head() );
 370         }
 371         const_iterator cbegin()
 372         {
 373             return const_iterator( head() );
 374         }
 375         //@}
 376
 377         /// Returns an const iterator that addresses the location succeeding the last element in a list
 378         //@{
 379         const_iterator end() const
 380         {
 381             return const_iterator();
 382         }
 383         const_iterator cend()
 384         {
 385             return const_iterator();
 386         }
 387         //@}
 388
 389     public:
 390         /// Default constructor
 391         /**
 392             Initializes empty list
 393         */
 394         MichaelKVList()
 395         {}
 396
 397         /// List desctructor
 398         /**
 399             Clears the list
 400         */
 401         ~MichaelKVList()
 402         {
 403             clear();
 404         }
 405
 406         /// Inserts new node with key and default value
 407         /**
 408             The function creates a node with \p key and default value, and then inserts the node created into the list.
 409
 410             Preconditions:
 411             - The \ref key_type should be constructible from value of type \p K.
 412                 In trivial case, \p K is equal to \ref key_type.
 413             - The \ref mapped_type should be default-constructible.
 414
 415             The function makes RCU lock internally.
 416
 417             Returns \p true if inserting successful, \p false otherwise.
 418         */
 419         template <typename K>
 420         bool insert( const K& key )
 421         {
 422             return insert_at( head(), key );
 423         }
 424
 425         /// Inserts new node with a key and a value
 426         /**
 427             The function creates a node with \p key and value \p val, and then inserts the node created into the list.
 428
 429             Preconditions:
 430             - The \ref key_type should be constructible from \p key of type \p K.
 431             - The \ref mapped_type should be constructible from \p val of type \p V.
 432
 433             The function makes RCU lock internally.
 434
 435             Returns \p true if inserting successful, \p false otherwise.
 436         */
 437         template <typename K, typename V>
 438         bool insert( const K& key, const V& val )
 439         {
 440             return insert_at( head(), key, val );
 441         }
 442
 443         /// Inserts new node and initialize it by a functor
 444         /**
 445             This function inserts new node with key \p key and if inserting is successful then it calls
 446             \p func functor with signature
 447             \code
 448                 struct functor {
 449                     void operator()( value_type& item );
 450                 };
 451             \endcode
 452
 453             The argument \p item of user-defined functor \p func is the reference
 454             to the list's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 455             User-defined functor \p func should guarantee that during changing item's value no any other changes
 456             could be made on this list's item by concurrent threads.
 457             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 458             and it is called only if inserting is successful.
 459
 460             The key_type should be constructible from value of type \p K.
 461
 462             The function allows to split creating of new item into two part:
 463             - create item from \p key;
 464             - insert new item into the list;
 465             - if inserting is successful, initialize the value of item by calling \p func functor
 466
 467             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 468             it is preferable that the initialization should be completed only if inserting is successful.
 469
 470             The function makes RCU lock internally.
 471         */
 472         template <typename K, typename Func>
 473         bool insert_key( const K& key, Func func )
 474         {
 475             return insert_key_at( head(), key, func );
 476         }
 477
 478         /// Ensures that the \p key exists in the list
 479         /**
 480             The operation performs inserting or changing data with lock-free manner.
 481
 482             If the \p key not found in the list, then the new item created from \p key
 483             is inserted into the list (note that in this case the \ref key_type should be
 484             copy-constructible from type \p K).
 485             Otherwise, the functor \p func is called with item found.
 486             The functor \p Func may be a function with signature:
 487             \code
 488                 void func( bool bNew, value_type& item );
 489             \endcode
 490             or a functor:
 491             \code
 492                 struct my_functor {
 493                     void operator()( bool bNew, value_type& item );
 494                 };
 495             \endcode
 496
 497             with arguments:
 498             - \p bNew - \p true if the item has been inserted, \p false otherwise
 499             - \p item - item of the list
 500
 501             The functor may change any fields of the \p item.second that is \ref mapped_type;
 502             however, \p func must guarantee that during changing no any other modifications
 503             could be made on this item by concurrent threads.
 504
 505             You may pass \p func argument by reference using <tt>boost::ref</tt>.
 506
 507             The function makes RCU lock internally.
 508
 509             Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
 510             \p second is true if new item has been added or \p false if the item with \p key
 511             already is in the list.
 512         */
 513         template <typename K, typename Func>
 514         std::pair<bool, bool> ensure( const K& key, Func f )
 515         {
 516             return ensure_at( head(), key, f );
 517         }
 518
 519 #   ifdef CDS_EMPLACE_SUPPORT
 520         /// Inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 521         /**
 522             Returns \p true if inserting successful, \p false otherwise.
 523
 524             The function makes RCU lock internally.
 525
 526             @note This function is available only for compiler that supports
 527             variadic template and move semantics
 528         */
 529         template <typename K, typename... Args>
 530         bool emplace( K&& key, Args&&... args )
 531         {
 532             return emplace_at( head(), std::forward<K>(key), std::forward<Args>(args)... );
 533         }
 534 #   endif
 535
 536         /// Deletes \p key from the list
 537         /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase
 538
 539             RCU \p synchronize method can be called. RCU should not be locked.
 540
 541             Returns \p true if \p key is found and has been deleted, \p false otherwise
 542         */
 543         template <typename K>
 544         bool erase( K const& key )
 545         {
 546             return erase_at( head(), key, intrusive_key_comparator() );
 547         }
 548
 549         /// Deletes the item from the list using \p pred predicate for searching
 550         /**
 551             The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase "erase(K const&)"
 552             but \p pred is used for key comparing.
 553             \p Less functor has the interface like \p std::less.
 554             \p pred must imply the same element order as the comparator used for building the list.
 555         */
 556         template <typename K, typename Less>
 557         bool erase_with( K const& key, Less pred )
 558         {
 559             return erase_at( head(), key, typename options::template less_wrapper<Less>::type() );
 560         }
 561
 562         /// Deletes \p key from the list
 563         /** \anchor cds_nonintrusive_MichaelKVList_rcu_erase_func
 564             The function searches an item with key \p key, calls \p f functor
 565             and deletes the item. If \p key is not found, the functor is not called.
 566
 567             The functor \p Func interface:
 568             \code
 569             struct extractor {
 570                 void operator()(value_type& val) { ... }
 571             };
 572             \endcode
 573             The functor may be passed by reference with <tt>boost:ref</tt>
 574
 575             RCU \p synchronize method can be called. RCU should not be locked.
 576
 577             Return \p true if key is found and deleted, \p false otherwise
 578
 579             See also: \ref erase
 580         */
 581         template <typename K, typename Func>
 582         bool erase( K const& key, Func f )
 583         {
 584             return erase_at( head(), key, intrusive_key_comparator(), f );
 585         }
 586
 587         /// Deletes the item from the list using \p pred predicate for searching
 588         /**
 589             The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_erase_func "erase(K const&, Func)"
 590             but \p pred is used for key comparing.
 591             \p Less functor has the interface like \p std::less.
 592             \p pred must imply the same element order as the comparator used for building the list.
 593         */
 594         template <typename K, typename Less, typename Func>
 595         bool erase_with( K const& key, Less pred, Func f )
 596         {
 597             return erase_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
 598         }
 599
 600         /// Extracts an item from the list
 601         /**
 602         @anchor cds_nonintrusive_MichaelKVList_rcu_extract
 603             The function searches an item with key equal to \p key in the list,
 604             unlinks it from the list, and returns pointer to an item found in \p dest argument.
 605             If \p key is not found the function returns \p false.
 606
 607             @note The function does NOT call RCU read-side lock or synchronization,
 608             and does NOT dispose the item found. It just excludes the item from the list
 609             and returns a pointer to item found.
 610             You should lock RCU before calling this function.
 611
 612             \code
 613             #include <cds/urcu/general_buffered.h>
 614             #include <cds/container/michael_kvlist_rcu.h>
 615
 616             typedef cds::urcu::gc< general_buffered<> > rcu;
 617             typedef cds::container::MichaelKVList< rcu, int, Foo > rcu_michael_list;
 618
 619             rcu_michael_list theList;
 620             // ...
 621
 622             rcu_michael_list::exempt_ptr p;
 623             {
 624                 // first, we should lock RCU
 625                 rcu_michael_list::rcu_lock sl;
 626
 627                 // Now, you can apply extract function
 628                 // Note that you must not delete the item found inside the RCU lock
 629                 if ( theList.extract( p, 10 )) {
 630                     // do something with p
 631                     ...
 632                 }
 633             }
 634             // Outside RCU lock section we may safely release extracted pointer.
 635             // release() passes the pointer to RCU reclamation cycle.
 636             p.release();
 637             \endcode
 638         */
 639         template <typename K>
 640         bool extract( exempt_ptr& dest, K const& key )
 641         {
 642             dest = extract_at( head(), key, intrusive_key_comparator() );
 643             return !dest.empty();
 644         }
 645
 646         /// Extracts an item from the list using \p pred predicate for searching
 647         /**
 648             This function is the analog for \ref cds_nonintrusive_MichaelKVList_rcu_extract "extract(exempt_ptr&, K const&)".
 649             The \p pred is a predicate used for key comparing.
 650             \p Less has the interface like \p std::less.
 651             \p pred must imply the same element order as \ref key_comparator.
 652         */
 653         template <typename K, typename Less>
 654         bool extract_with( exempt_ptr& dest, K const& key, Less pred )
 655         {
 656             dest = extract_at( head(), key, typename options::template less_wrapper<Less>::type() );
 657             return !dest.empty();
 658         }
 659
 660         /// Finds the key \p key
 661         /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_val
 662
 663             The function searches the item with key equal to \p key
 664             and returns \p true if it is found, and \p false otherwise
 665
 666             The function makes RCU lock internally.
 667         */
 668         template <typename Q>
 669         bool find( Q const& key ) const
 670         {
 671             return find_at( head(), key, intrusive_key_comparator() );
 672         }
 673
 674         /// Finds the key \p val using \p pred predicate for searching
 675         /**
 676             The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_val "find(Q const&)"
 677             but \p pred is used for key comparing.
 678             \p Less functor has the interface like \p std::less.
 679             \p pred must imply the same element order as the comparator used for building the list.
 680         */
 681         template <typename Q, typename Less>
 682         bool find_with( Q const& key, Less pred ) const
 683         {
 684             return find_at( head(), key, typename options::template less_wrapper<Less>::type() );
 685         }
 686
 687         /// Finds the key \p key and performs an action with it
 688         /** \anchor cds_nonintrusive_MichaelKVList_rcu_find_func
 689             The function searches an item with key equal to \p key and calls the functor \p f for the item found.
 690             The interface of \p Func functor is:
 691             \code
 692             struct functor {
 693                 void operator()( value_type& item );
 694             };
 695             \endcode
 696             where \p item is the item found.
 697
 698             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 699
 700             The functor may change <tt>item.second</tt> that is reference to value of node.
 701             Note that the function is only guarantee that \p item cannot be deleted during functor is executing.
 702             The function does not serialize simultaneous access to the list \p item. If such access is
 703             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 704
 705             The function makes RCU lock internally.
 706
 707             The function returns \p true if \p key is found, \p false otherwise.
 708         */
 709         template <typename Q, typename Func>
 710         bool find( Q const& key, Func f ) const
 711         {
 712             return find_at( head(), key, intrusive_key_comparator(), f );
 713         }
 714
 715         /// Finds the key \p val using \p pred predicate for searching
 716         /**
 717             The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_find_func "find(Q const&, Func)"
 718             but \p pred is used for key comparing.
 719             \p Less functor has the interface like \p std::less.
 720             \p pred must imply the same element order as the comparator used for building the list.
 721         */
 722         template <typename Q, typename Less, typename Func>
 723         bool find_with( Q const& key, Less pred, Func f ) const
 724         {
 725             return find_at( head(), key, typename options::template less_wrapper<Less>::type(), f );
 726         }
 727
 728         /// Finds \p key and return the item found
 729         /** \anchor cds_nonintrusive_MichaelKVList_rcu_get
 730             The function searches the item with \p key and returns the pointer to item found.
 731             If \p key is not found it returns \p NULL.
 732
 733             Note the compare functor should accept a parameter of type \p K that can be not the same as \p key_type.
 734
 735             RCU should be locked before call of this function.
 736             Returned item is valid only while RCU is locked:
 737             \code
 738             typedef cds::container::MichaelKVList< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > ord_list;
 739             ord_list theList;
 740             // ...
 741             {
 742                 // Lock RCU
 743                 ord_list::rcu_lock lock;
 744
 745                 ord_list::value_type * pVal = theList.get( 5 );
 746                 if ( pVal ) {
 747                     // Deal with pVal
 748                     //...
 749                 }
 750                 // Unlock RCU by rcu_lock destructor
 751                 // pVal can be freed at any time after RCU has been unlocked
 752             }
 753             \endcode
 754         */
 755         template <typename K>
 756         value_type * get( K const& key ) const
 757         {
 758             return get_at( head(), key, intrusive_key_comparator());
 759         }
 760
 761         /// Finds \p key and return the item found
 762         /**
 763             The function is an analog of \ref cds_nonintrusive_MichaelKVList_rcu_get "get(K const&)"
 764             but \p pred is used for comparing the keys.
 765
 766             \p Less functor has the semantics like \p std::less but should take arguments of type \ref key_type and \p K
 767             in any order.
 768             \p pred must imply the same element order as the comparator used for building the list.
 769         */
 770         template <typename K, typename Less>
 771         value_type * get_with( K const& key, Less pred ) const
 772         {
 773             return get_at( head(), key, typename options::template less_wrapper<Less>::type());
 774         }
 775
 776         /// Checks if the list is empty
 777         bool empty() const
 778         {
 779             return base_class::empty();
 780         }
 781
 782         /// Returns list's item count
 783         /**
 784             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 785             this function always returns 0.
 786
 787             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 788             is empty. To check list emptyness use \ref empty() method.
 789         */
 790         size_t size() const
 791         {
 792             return base_class::size();
 793         }
 794
 795         /// Clears the list
 796         /**
 797             Post-condition: the list is empty
 798         */
 799         void clear()
 800         {
 801             base_class::clear();
 802         }
 803
 804     protected:
 805         //@cond
 806         bool insert_node_at( head_type& refHead, node_type * pNode )
 807         {
 808             assert( pNode != null_ptr<node_type *>() );
 809             scoped_node_ptr p( pNode );
 810             if ( base_class::insert_at( refHead, *pNode )) {
 811                 p.release();
 812                 return true;
 813             }
 814             return false;
 815         }
 816
 817         template <typename K>
 818         bool insert_at( head_type& refHead, const K& key )
 819         {
 820             return insert_node_at( refHead, alloc_node( key ));
 821         }
 822
 823         template <typename K, typename V>
 824         bool insert_at( head_type& refHead, const K& key, const V& val )
 825         {
 826             return insert_node_at( refHead, alloc_node( key, val ));
 827         }
 828
 829         template <typename K, typename Func>
 830         bool insert_key_at( head_type& refHead, const K& key, Func f )
 831         {
 832             scoped_node_ptr pNode( alloc_node( key ));
 833
 834 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 835             if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ cds::unref(f)( node.m_Data ); }))
 836 #       else
 837             insert_functor<Func>  wrapper( f );
 838             if ( base_class::insert_at( refHead, *pNode, cds::ref(wrapper) ))
 839 #       endif
 840             {
 841                 pNode.release();
 842                 return true;
 843             }
 844             return false;
 845         }
 846
 847 #   ifdef CDS_EMPLACE_SUPPORT
 848         template <typename K, typename... Args>
 849         bool emplace_at( head_type& refHead, K&& key, Args&&... args )
 850         {
 851             return insert_node_at( refHead, alloc_node( std::forward<K>(key), std::forward<Args>(args)... ));
 852         }
 853 #   endif
 854
 855         template <typename K, typename Func>
 856         std::pair<bool, bool> ensure_at( head_type& refHead, const K& key, Func f )
 857         {
 858             scoped_node_ptr pNode( alloc_node( key ));
 859
 860 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 861             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode,
 862                 [&f]( bool bNew, node_type& node, node_type& ){ cds::unref(f)( bNew, node.m_Data ); });
 863 #       else
 864             ensure_functor<Func> wrapper( f );
 865             std::pair<bool, bool> ret = base_class::ensure_at( refHead, *pNode, cds::ref(wrapper));
 866 #       endif
 867             if ( ret.first && ret.second )
 868                 pNode.release();
 869
 870             return ret;
 871         }
 872
 873         template <typename K, typename Compare>
 874         bool erase_at( head_type& refHead, K const& key, Compare cmp )
 875         {
 876             return base_class::erase_at( refHead, key, cmp );
 877         }
 878
 879         template <typename K, typename Compare, typename Func>
 880         bool erase_at( head_type& refHead, K const& key, Compare cmp, Func f )
 881         {
 882 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 883             return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ cds::unref(f)( const_cast<value_type&>(node.m_Data)); });
 884 #       else
 885             erase_functor<Func> wrapper( f );
 886             return base_class::erase_at( refHead, key, cmp, cds::ref(wrapper) );
 887 #       endif
 888         }
 889
 890         template <typename K, typename Compare>
 891         node_type * extract_at( head_type& refHead, K const& key, Compare cmp )
 892         {
 893             return base_class::extract_at( refHead, key, cmp );
 894         }
 895
 896         template <typename K, typename Compare>
 897         bool find_at( head_type& refHead, K const& key, Compare cmp ) const
 898         {
 899 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 900             return base_class::find_at( refHead, key, cmp, [](node_type&, K const&) {} );
 901 #       else
 902             return base_class::find_at( refHead, key, cmp, empty_find_functor() );
 903 #       endif
 904         }
 905
 906         template <typename K, typename Compare, typename Func>
 907         bool find_at( head_type& refHead, K& key, Compare cmp, Func f ) const
 908         {
 909 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 910             return base_class::find_at( refHead, key, cmp, [&f](node_type& node, K const&){ cds::unref(f)( node.m_Data ); });
 911 #       else
 912             find_functor<Func>  wrapper( f );
 913             return base_class::find_at( refHead, key, cmp, cds::ref(wrapper) );
 914 #       endif
 915         }
 916
 917         template <typename K, typename Compare>
 918         value_type * get_at( head_type& refHead, K const& val, Compare cmp ) const
 919         {
 920             node_type * pNode = base_class::get_at( refHead, val, cmp );
 921             return pNode ? &pNode->m_Data : null_ptr<value_type *>();
 922         }
 923
 924         //@endcond
 925     };
 926
 927 }}  // namespace cds::container
 928
 929 #endif  // #ifndef __CDS_CONTAINER_MICHAEL_KVLIST_RCU_H