cds/container/michael_list_impl.h

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