cds/container/michael_list_rcu.h

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