cds/intrusive/michael_list_impl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H
   4 #define __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H
   5
   6 #include <cds/intrusive/michael_list_base.h>
   7 #include <cds/gc/guarded_ptr.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Michael's lock-free ordered single-linked list
  12     /** @ingroup cds_intrusive_list
  13         \anchor cds_intrusive_MichaelList_hp
  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         Template arguments:
  22         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see michael_list::node).
  23         - \p T - type to be stored in the list. The type must be based on michael_list::node (for michael_list::base_hook)
  24             or it must have a member of type michael_list::node (for michael_list::member_hook).
  25         - \p Traits - type traits. See michael_list::type_traits for explanation.
  26
  27         It is possible to declare option-based list with cds::intrusive::michael_list::make_traits metafunction istead of \p Traits template
  28         argument.
  29
  30         Template argument list \p Options of cds::intrusive::michael_list::make_traits metafunction are:
  31         - opt::hook - hook used. Possible values are: michael_list::base_hook, michael_list::member_hook, michael_list::traits_hook.
  32             If the option is not specified, <tt>michael_list::base_hook<></tt> and gc::HP is used.
  33         - opt::compare - key comparison functor. No default functor is provided.
  34             If the option is not specified, the opt::less is used.
  35         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
  36         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  37         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. Due the nature
  38             of GC schema the disposer may be called asynchronously.
  39         - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link
  40         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  41         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  42             or opt::v::sequential_consistent (sequentially consisnent memory model).
  43
  44         For example, the following traits-based declaration of gc::HP Michael's list
  45         \code
  46         #include <cds/intrusive/michael_list_hp.h>
  47         // Declare item stored in your list
  48         struct item: public cds::intrusive::michael_list::node< cds::gc::HP >
  49         {
  50             int nKey;
  51             // .... other data
  52         };
  53
  54         // Declare comparator for the item
  55         struct my_compare {
  56             int operator()( item const& i1, item const& i2 ) const
  57             {
  58                 return i1.nKey - i2.nKey;
  59             }
  60         };
  61
  62         // Declare type_traits
  63         struct my_traits: public cds::intrusive::michael_list::type_traits
  64         {
  65             typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
  66             typedef my_compare compare;
  67         };
  68
  69         // Declare traits-based list
  70         typedef cds::intrusive::MichaelList< cds::gc::HP, item, my_traits >     traits_based_list;
  71         \endcode
  72
  73         is equivalent for the following option-based list
  74         \code
  75         #include <cds/intrusive/michael_list_hp.h>
  76
  77         // item struct and my_compare are the same
  78
  79         // Declare option-based list
  80         typedef cds::intrusive::MichaelList< cds::gc::HP, item,
  81             typename cds::intrusive::michael_list::make_traits<
  82                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::HP > > >    // hook option
  83                 ,cds::intrusive::opt::compare< my_compare >     // item comparator option
  84             >::type
  85         >     option_based_list;
  86         \endcode
  87
  88         \par Usage
  89         There are different specializations of this template for each garbage collecting schema used.
  90         You should select GC needed and include appropriate .h-file:
  91         - for gc::HP: \code #include <cds/intrusive/michael_list_hp.h> \endcode
  92         - for gc::PTB: \code #include <cds/intrusive/michael_list_ptb.h> \endcode
  93         - for gc::HRC: \code #include <cds/intrusive/michael_list_hrc.h> \endcode
  94         - for \ref cds_urcu_gc "RCU type" - see \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
  95         - for gc::nogc: \code #include <cds/intrusive/michael_list_nogc.h> \endcode
  96             See \ref cds_intrusive_MichaelList_nogc "non-GC MichaelList"
  97
  98         Then, you should incorporate michael_list::node into your struct \p T and provide
  99         appropriate michael_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
 100         define a struct based on michael_list::type_traits.
 101
 102         Example for gc::PTB and base hook:
 103         \code
 104         // Include GC-related Michael's list specialization
 105         #include <cds/intrusive/michael_list_ptb.h>
 106
 107         // Data stored in Michael's list
 108         struct my_data: public cds::intrusive::michael_list::node< cds::gc::PTB >
 109         {
 110             // key field
 111             std::string     strKey;
 112
 113             // other data
 114             // ...
 115         };
 116
 117         // my_data comparing functor
 118         struct my_data_cmp {
 119             int operator()( const my_data& d1, const my_data& d2 )
 120             {
 121                 return d1.strKey.compare( d2.strKey );
 122             }
 123
 124             int operator()( const my_data& d, const std::string& s )
 125             {
 126                 return d.strKey.compare(s);
 127             }
 128
 129             int operator()( const std::string& s, const my_data& d )
 130             {
 131                 return s.compare( d.strKey );
 132             }
 133         };
 134
 135
 136         // Declare type_traits
 137         struct my_traits: public cds::intrusive::michael_list::type_traits
 138         {
 139             typedef cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > >   hook;
 140             typedef my_data_cmp compare;
 141         };
 142
 143         // Declare list type
 144         typedef cds::intrusive::MichaelList< cds::gc::PTB, my_data, my_traits >     traits_based_list;
 145         \endcode
 146
 147         Equivalent option-based code:
 148         \code
 149         // GC-related specialization
 150         #include <cds/intrusive/michael_list_ptb.h>
 151
 152         struct my_data {
 153             // see above
 154         };
 155         struct compare {
 156             // see above
 157         };
 158
 159         // Declare option-based list
 160         typedef cds::intrusive::MichaelList< cds::gc::PTB
 161             ,my_data
 162             , typename cds::intrusive::michael_list::make_traits<
 163                 cds::intrusive::opt::hook< cds::intrusive::michael_list::base_hook< cds::opt::gc< cds::gc::PTB > > >
 164                 ,cds::intrusive::opt::compare< my_data_cmp >
 165             >::type
 166         > option_based_list;
 167
 168         \endcode
 169     */
 170     template <
 171         class GC
 172         ,typename T
 173 #ifdef CDS_DOXYGEN_INVOKED
 174         ,class Traits = michael_list::type_traits
 175 #else
 176         ,class Traits
 177 #endif
 178     >
 179     class MichaelList
 180     {
 181     public:
 182         typedef T       value_type      ;   ///< type of value stored in the list
 183         typedef Traits  options         ;   ///< Traits template parameter
 184
 185         typedef typename options::hook      hook        ;   ///< hook type
 186         typedef typename hook::node_type    node_type   ;   ///< node type
 187
 188 #   ifdef CDS_DOXYGEN_INVOKED
 189         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 190 #   else
 191         typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
 192 #   endif
 193
 194         typedef typename options::disposer  disposer    ;   ///< disposer used
 195         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 196         typedef typename michael_list::get_link_checker< node_type, options::link_checker >::type link_checker   ;   ///< link checker
 197
 198         typedef GC  gc          ;   ///< Garbage collector
 199         typedef typename options::back_off  back_off    ;   ///< back-off strategy
 200         typedef typename options::item_counter item_counter ;   ///< Item counting policy used
 201         typedef typename options::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 202
 203         typedef cds::gc::guarded_ptr< gc, value_type > guarded_ptr; ///< Guarded pointer
 204
 205         //@cond
 206         // Rebind options (split-list support)
 207         template <typename... Options>
 208         struct rebind_options {
 209             typedef MichaelList<
 210                 gc
 211                 , value_type
 212                 , typename cds::opt::make_options< options, Options...>::type
 213             >   type;
 214         };
 215         //@endcond
 216
 217     protected:
 218         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr ;   ///< Atomic node pointer
 219         typedef typename node_type::marked_ptr          marked_node_ptr ;   ///< Node marked pointer
 220
 221         typedef atomic_node_ptr     auxiliary_head      ;   ///< Auxiliary head type (for split-list support)
 222
 223         atomic_node_ptr     m_pHead         ;   ///< Head pointer
 224         item_counter        m_ItemCounter   ;   ///< Item counter
 225
 226         //@cond
 227         /// Position pointer for item search
 228         struct position {
 229             atomic_node_ptr * pPrev ;   ///< Previous node
 230             node_type * pCur        ;   ///< Current node
 231             node_type * pNext       ;   ///< Next node
 232
 233             typename gc::template GuardArray<3> guards  ;   ///< Guards array
 234
 235             enum {
 236                 guard_prev_item,
 237                 guard_current_item,
 238                 guard_next_item
 239             };
 240         };
 241
 242         struct clean_disposer {
 243             void operator()( value_type * p )
 244             {
 245                 michael_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
 246                 disposer()( p );
 247             }
 248         };
 249
 250         //@endcond
 251
 252     protected:
 253         //@cond
 254         void retire_node( node_type * pNode )
 255         {
 256             assert( pNode != nullptr );
 257             gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
 258         }
 259
 260         bool link_node( node_type * pNode, position& pos )
 261         {
 262             assert( pNode != nullptr );
 263             link_checker::is_empty( pNode );
 264
 265             marked_node_ptr cur(pos.pCur);
 266             pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
 267             return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
 268         }
 269
 270         bool unlink_node( position& pos )
 271         {
 272             assert( pos.pPrev != nullptr );
 273             assert( pos.pCur != nullptr );
 274
 275             // Mark the node (logical deleting)
 276             marked_node_ptr next(pos.pNext, 0);
 277             if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 278                 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
 279                 // CAS may be successful here or in other thread that searching something
 280                 marked_node_ptr cur(pos.pCur);
 281                 if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
 282                     retire_node( pos.pCur );
 283                 return true;
 284             }
 285             return false;
 286         }
 287         //@endcond
 288
 289     protected:
 290         //@cond
 291         template <bool IsConst>
 292         class iterator_type
 293         {
 294             friend class MichaelList;
 295
 296         protected:
 297             value_type * m_pNode;
 298             typename gc::Guard  m_Guard;
 299
 300             void next()
 301             {
 302                 if ( m_pNode ) {
 303                     typename gc::Guard g;
 304                     node_type * pCur = node_traits::to_node_ptr( *m_pNode );
 305
 306                     marked_node_ptr pNext;
 307                     do {
 308                         pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
 309                         g.assign( node_traits::to_value_ptr( pNext.ptr() ));
 310                     } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_acquire) );
 311
 312                     if ( pNext.ptr() ) {
 313                         m_pNode = m_Guard.assign( g.template get<value_type>() );
 314                     }
 315                     else {
 316                         m_pNode = nullptr;
 317                         m_Guard.clear();
 318                     }
 319                 }
 320             }
 321
 322             iterator_type( atomic_node_ptr const& pNode )
 323             {
 324                 for (;;) {
 325                     marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
 326                     if ( p.ptr() ) {
 327                         m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
 328                     }
 329                     else {
 330                         m_pNode = nullptr;
 331                         m_Guard.clear();
 332                     }
 333                     if ( p == pNode.load(memory_model::memory_order_acquire) )
 334                         break;
 335                 }
 336             }
 337
 338         public:
 339             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 340             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 341
 342             iterator_type()
 343                 : m_pNode( nullptr )
 344             {}
 345
 346             iterator_type( iterator_type const& src )
 347             {
 348                 if ( src.m_pNode ) {
 349                     m_pNode = m_Guard.assign( src.m_pNode );
 350                 }
 351                 else
 352                     m_pNode = nullptr;
 353             }
 354
 355             value_ptr operator ->() const
 356             {
 357                 return m_pNode;
 358             }
 359
 360             value_ref operator *() const
 361             {
 362                 assert( m_pNode != nullptr );
 363                 return *m_pNode;
 364             }
 365
 366             /// Pre-increment
 367             iterator_type& operator ++()
 368             {
 369                 next();
 370                 return *this;
 371             }
 372
 373             iterator_type& operator = (iterator_type const& src)
 374             {
 375                 m_pNode = src.m_pNode;
 376                 m_Guard.assign( m_pNode );
 377                 return *this;
 378             }
 379
 380             /*
 381             /// Post-increment
 382             void operator ++(int)
 383             {
 384                 next();
 385             }
 386             */
 387
 388             template <bool C>
 389             bool operator ==(iterator_type<C> const& i ) const
 390             {
 391                 return m_pNode == i.m_pNode;
 392             }
 393             template <bool C>
 394             bool operator !=(iterator_type<C> const& i ) const
 395             {
 396                 return m_pNode != i.m_pNode;
 397             }
 398         };
 399         //@endcond
 400
 401     public:
 402         /// Forward iterator
 403         /**
 404             The forward iterator for Michael's list has some features:
 405             - it has no post-increment operator
 406             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 407               For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
 408               may be thrown if a limit of guard count per thread is exceeded.
 409             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 410             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 411               deleting operations it is no guarantee that you iterate all item in the list.
 412
 413             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 414             for debug purpose only.
 415
 416             The iterator interface:
 417             \code
 418             class iterator {
 419             public:
 420                 // Default constructor
 421                 iterator();
 422
 423                 // Copy construtor
 424                 iterator( iterator const& src );
 425
 426                 // Dereference operator
 427                 value_type * operator ->() const;
 428
 429                 // Dereference operator
 430                 value_type& operator *() const;
 431
 432                 // Preincrement operator
 433                 iterator& operator ++();
 434
 435                 // Assignment operator
 436                 iterator& operator = (iterator const& src);
 437
 438                 // Equality operators
 439                 bool operator ==(iterator const& i ) const;
 440                 bool operator !=(iterator const& i ) const;
 441             };
 442             \endcode
 443         */
 444         typedef iterator_type<false>    iterator;
 445         /// Const forward iterator
 446         /**
 447             For iterator's features and requirements see \ref iterator
 448         */
 449         typedef iterator_type<true>     const_iterator;
 450
 451         /// Returns a forward iterator addressing the first element in a list
 452         /**
 453             For empty list \code begin() == end() \endcode
 454         */
 455         iterator begin()
 456         {
 457             return iterator( m_pHead );
 458         }
 459
 460         /// Returns an iterator that addresses the location succeeding the last element in a list
 461         /**
 462             Do not use the value returned by <tt>end</tt> function to access any item.
 463             Internally, <tt>end</tt> returning value equals to \p nullptr.
 464
 465             The returned value can be used only to control reaching the end of the list.
 466             For empty list <tt>begin() == end()</tt>
 467         */
 468         iterator end()
 469         {
 470             return iterator();
 471         }
 472
 473         /// Returns a forward const iterator addressing the first element in a list
 474         const_iterator cbegin()
 475         {
 476             return const_iterator( m_pHead );
 477         }
 478
 479         /// Returns a forward const iterator addressing the first element in a list
 480         const_iterator begin() const
 481         {
 482             return const_iterator( m_pHead );
 483         }
 484
 485         /// Returns an const iterator that addresses the location succeeding the last element in a list
 486         const_iterator end() const
 487         {
 488             return const_iterator();
 489         }
 490
 491         /// Returns an const iterator that addresses the location succeeding the last element in a list
 492         const_iterator cend()
 493         {
 494             return const_iterator();
 495         }
 496
 497     public:
 498         /// Default constructor initializes empty list
 499         MichaelList()
 500             : m_pHead( nullptr )
 501         {
 502             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 503         }
 504
 505         /// Destroys the list object
 506         ~MichaelList()
 507         {
 508             clear();
 509         }
 510
 511         /// Inserts new node
 512         /**
 513             The function inserts \p val in the list if the list does not contain
 514             an item with key equal to \p val.
 515
 516             Returns \p true if \p val is linked into the list, \p false otherwise.
 517         */
 518         bool insert( value_type& val )
 519         {
 520             return insert_at( m_pHead, val );
 521         }
 522
 523         /// Inserts new node
 524         /**
 525             This function is intended for derived non-intrusive containers.
 526
 527             The function allows to split new item creating into two part:
 528             - create item with key only
 529             - insert new item into the list
 530             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 531
 532             The functor signature is:
 533             \code
 534                 void func( value_type& val );
 535             \endcode
 536             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 537             \p val no any other changes could be made on this list's item by concurrent threads.
 538             The user-defined functor is called only if the inserting is success and may be passed by reference
 539             using <tt>boost::ref</tt>.
 540         */
 541         template <typename Func>
 542         bool insert( value_type& val, Func f )
 543         {
 544             return insert_at( m_pHead, val, f );
 545         }
 546
 547         /// Ensures that the \p item exists in the list
 548         /**
 549             The operation performs inserting or changing data with lock-free manner.
 550
 551             If the item \p val not found in the list, then \p val is inserted into the list.
 552             Otherwise, the functor \p func is called with item found.
 553             The functor signature is:
 554             \code
 555                 void func( bool bNew, value_type& item, value_type& val );
 556             \endcode
 557             with arguments:
 558             - \p bNew - \p true if the item has been inserted, \p false otherwise
 559             - \p item - item of the list
 560             - \p val - argument \p val passed into the \p ensure function
 561             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 562             refers to the same thing.
 563
 564             The functor may change non-key fields of the \p item; however, \p func must guarantee
 565             that during changing no any other modifications could be made on this item by concurrent threads.
 566
 567             You may pass \p func argument by reference using <tt>boost::ref</tt> or cds::ref.
 568
 569             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 570             \p second is \p true if new item has been added or \p false if the item with \p key
 571             already is in the list.
 572         */
 573         template <typename Func>
 574         std::pair<bool, bool> ensure( value_type& val, Func func )
 575         {
 576             return ensure_at( m_pHead, val, func );
 577         }
 578
 579         /// Unlinks the item \p val from the list
 580         /**
 581             The function searches the item \p val in the list and unlink it from the list
 582             if it is found and it is equal to \p val.
 583
 584             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 585             and deletes the item found. \p unlink finds an item by key and deletes it
 586             only if \p val is an item of that list, i.e. the pointer to item found
 587             is equal to <tt> &val </tt>.
 588
 589             The function returns \p true if success and \p false otherwise.
 590         */
 591         bool unlink( value_type& val )
 592         {
 593             return unlink_at( m_pHead, val );
 594         }
 595
 596         /// Deletes the item from the list
 597         /** \anchor cds_intrusive_MichaelList_hp_erase_val
 598             The function searches an item with key equal to \p val in the list,
 599             unlinks it from the list, and returns \p true.
 600             If the item with the key equal to \p val is not found the function return \p false.
 601         */
 602         template <typename Q>
 603         bool erase( Q const& val )
 604         {
 605             return erase_at( m_pHead, val, key_comparator() );
 606         }
 607
 608         /// Deletes the item from the list using \p pred predicate for searching
 609         /**
 610             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
 611             but \p pred is used for key comparing.
 612             \p Less functor has the interface like \p std::less.
 613             \p pred must imply the same element order as the comparator used for building the list.
 614         */
 615         template <typename Q, typename Less>
 616         bool erase_with( Q const& val, Less pred )
 617         {
 618             return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>());
 619         }
 620
 621         /// Deletes the item from the list
 622         /** \anchor cds_intrusive_MichaelList_hp_erase_func
 623             The function searches an item with key equal to \p val in the list,
 624             call \p func functor with item found, unlinks it from the list, and returns \p true.
 625             The \p Func interface is
 626             \code
 627             struct functor {
 628                 void operator()( value_type const& item );
 629             };
 630             \endcode
 631             The functor may be passed by reference using <tt>boost:ref</tt>
 632
 633             If the item with the key equal to \p val is not found the function return \p false.
 634         */
 635         template <typename Q, typename Func>
 636         bool erase( Q const& val, Func func )
 637         {
 638             return erase_at( m_pHead, val, key_comparator(), func );
 639         }
 640
 641         /// Deletes the item from the list using \p pred predicate for searching
 642         /**
 643             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
 644             but \p pred is used for key comparing.
 645             \p Less functor has the interface like \p std::less.
 646             \p pred must imply the same element order as the comparator used for building the list.
 647         */
 648         template <typename Q, typename Less, typename Func>
 649         bool erase_with( Q const& val, Less pred, Func f )
 650         {
 651             return erase_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 652         }
 653
 654         /// Extracts the item from the list with specified \p key
 655         /** \anchor cds_intrusive_MichaelList_hp_extract
 656             The function searches an item with key equal to \p key,
 657             unlinks it from the list, and returns it in \p dest parameter.
 658             If the item with key equal to \p key is not found the function returns \p false.
 659
 660             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 661
 662             The \ref disposer specified in \p Traits class template parameter is called automatically
 663             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 664             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 665
 666             Usage:
 667             \code
 668             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 669             ord_list theList;
 670             // ...
 671             {
 672                 ord_list::guarded_ptr gp;
 673                 theList.extract( gp, 5 );
 674                 // Deal with gp
 675                 // ...
 676
 677                 // Destructor of gp releases internal HP guard
 678             }
 679             \endcode
 680         */
 681         template <typename Q>
 682         bool extract( guarded_ptr& dest, Q const& key )
 683         {
 684             return extract_at( m_pHead, dest.guard(), key, key_comparator() );
 685         }
 686
 687         /// Extracts the item using compare functor \p pred
 688         /**
 689             The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
 690             but \p pred predicate is used for key comparing.
 691
 692             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 693             in any order.
 694             \p pred must imply the same element order as the comparator used for building the list.
 695         */
 696         template <typename Q, typename Less>
 697         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 698         {
 699             return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 700         }
 701
 702         /// Finds the key \p val
 703         /** \anchor cds_intrusive_MichaelList_hp_find_func
 704             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 705             The interface of \p Func functor is:
 706             \code
 707             struct functor {
 708                 void operator()( value_type& item, Q& val );
 709             };
 710             \endcode
 711             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 712
 713             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 714
 715             The functor may change non-key fields of \p item. Note that the function is only guarantee
 716             that \p item cannot be disposed during functor is executing.
 717             The function does not serialize simultaneous access to the list \p item. If such access is
 718             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 719
 720             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 721             may modify both arguments.
 722
 723             The function returns \p true if \p val is found, \p false otherwise.
 724         */
 725         template <typename Q, typename Func>
 726         bool find( Q& val, Func f )
 727         {
 728             return find_at( m_pHead, val, key_comparator(), f );
 729         }
 730
 731         /// Finds the key \p val using \p pred predicate for searching
 732         /**
 733             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
 734             but \p pred is used for key comparing.
 735             \p Less functor has the interface like \p std::less.
 736             \p pred must imply the same element order as the comparator used for building the list.
 737         */
 738         template <typename Q, typename Less, typename Func>
 739         bool find_with( Q& val, Less pred, Func f )
 740         {
 741             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 742         }
 743
 744         /// Finds the key \p val
 745         /** \anchor cds_intrusive_MichaelList_hp_find_cfunc
 746             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 747             The interface of \p Func functor is:
 748             \code
 749             struct functor {
 750                 void operator()( value_type& item, Q const& val );
 751             };
 752             \endcode
 753             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 754
 755             You may pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
 756
 757             The functor may change non-key fields of \p item. Note that the function is only guarantee
 758             that \p item cannot be disposed during functor is executing.
 759             The function does not serialize simultaneous access to the list \p item. If such access is
 760             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 761
 762             The function returns \p true if \p val is found, \p false otherwise.
 763         */
 764         template <typename Q, typename Func>
 765         bool find( Q const& val, Func f )
 766         {
 767             return find_at( m_pHead, val, key_comparator(), f );
 768         }
 769
 770         /// Finds the key \p val using \p pred predicate for searching
 771         /**
 772             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_cfunc "find(Q const&, Func)"
 773             but \p pred is used for key comparing.
 774             \p Less functor has the interface like \p std::less.
 775             \p pred must imply the same element order as the comparator used for building the list.
 776         */
 777         template <typename Q, typename Less, typename Func>
 778         bool find_with( Q const& val, Less pred, Func f )
 779         {
 780             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 781         }
 782
 783         /// Finds the key \p val
 784         /** \anchor cds_intrusive_MichaelList_hp_find_val
 785             The function searches the item with key equal to \p val
 786             and returns \p true if it is found, and \p false otherwise
 787         */
 788         template <typename Q>
 789         bool find( Q const & val )
 790         {
 791             return find_at( m_pHead, val, key_comparator() );
 792         }
 793
 794         /// Finds the key \p val using \p pred predicate for searching
 795         /**
 796             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
 797             but \p pred is used for key comparing.
 798             \p Less functor has the interface like \p std::less.
 799             \p pred must imply the same element order as the comparator used for building the list.
 800         */
 801         template <typename Q, typename Less>
 802         bool find_with( Q const& val, Less pred )
 803         {
 804             return find_at( m_pHead, val, cds::opt::details::make_comparator_from_less<Less>() );
 805         }
 806
 807         /// Finds the key \p val and return the item found
 808         /** \anchor cds_intrusive_MichaelList_hp_get
 809             The function searches the item with key equal to \p val
 810             and assigns the item found to guarded pointer \p ptr.
 811             The function returns \p true if \p val is found, and \p false otherwise.
 812             If \p val is not found the \p ptr parameter is not changed.
 813
 814             The \ref disposer specified in \p Traits class template parameter is called
 815             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 816             will be destroyed or released.
 817             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 818
 819             Usage:
 820             \code
 821             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 822             ord_list theList;
 823             // ...
 824             {
 825                 ord_list::guarded_ptr gp;
 826                 if ( theList.get( gp, 5 )) {
 827                     // Deal with gp
 828                     //...
 829                 }
 830                 // Destructor of guarded_ptr releases internal HP guard
 831             }
 832             \endcode
 833
 834             Note the compare functor specified for \p Traits template parameter
 835             should accept a parameter of type \p Q that can be not the same as \p value_type.
 836         */
 837         template <typename Q>
 838         bool get( guarded_ptr& ptr, Q const& val )
 839         {
 840             return get_at( m_pHead, ptr.guard(), val, key_comparator() );
 841         }
 842
 843         /// Finds the key \p val and return the item found
 844         /**
 845             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
 846             but \p pred is used for comparing the keys.
 847
 848             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 849             in any order.
 850             \p pred must imply the same element order as the comparator used for building the list.
 851         */
 852         template <typename Q, typename Less>
 853         bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
 854         {
 855             return get_at( m_pHead, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
 856         }
 857
 858         /// Clears the list
 859         /**
 860             The function unlink all items from the list.
 861         */
 862         void clear()
 863         {
 864             typename gc::Guard guard;
 865             marked_node_ptr head;
 866             while ( true ) {
 867                 head = m_pHead.load(memory_model::memory_order_relaxed);
 868                 if ( head.ptr() )
 869                     guard.assign( node_traits::to_value_ptr( *head.ptr() ));
 870                 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
 871                     if ( head.ptr() == nullptr )
 872                         break;
 873                     value_type& val = *node_traits::to_value_ptr( *head.ptr() );
 874                     unlink( val );
 875                 }
 876             }
 877         }
 878
 879         /// Checks if the list is empty
 880         bool empty() const
 881         {
 882             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 883         }
 884
 885         /// Returns list's item count
 886         /**
 887             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 888             this function always returns 0.
 889
 890             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 891             is empty. To check list emptyness use \ref empty() method.
 892         */
 893         size_t size() const
 894         {
 895             return m_ItemCounter.value();
 896         }
 897
 898     protected:
 899         //@cond
 900         // split-list support
 901         bool insert_aux_node( node_type * pNode )
 902         {
 903             return insert_aux_node( m_pHead, pNode );
 904         }
 905
 906         // split-list support
 907         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 908         {
 909             assert( pNode != nullptr );
 910
 911             // Hack: convert node_type to value_type.
 912             // In principle, auxiliary node can be non-reducible to value_type
 913             // We assume that comparator can correctly distinguish aux and regular node.
 914             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 915         }
 916
 917         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 918         {
 919             node_type * pNode = node_traits::to_node_ptr( val );
 920             link_checker::is_empty( pNode );
 921             position pos;
 922
 923             while ( true ) {
 924                 if ( search( refHead, val, pos, key_comparator() ) )
 925                     return false;
 926
 927                 if ( link_node( pNode, pos ) ) {
 928                     ++m_ItemCounter;
 929                     return true;
 930                 }
 931
 932                 // clear next field
 933                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 934             }
 935         }
 936
 937         template <typename Func>
 938         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 939         {
 940             node_type * pNode = node_traits::to_node_ptr( val );
 941             link_checker::is_empty( pNode );
 942             position pos;
 943
 944             while ( true ) {
 945                 if ( search( refHead, val, pos, key_comparator() ) )
 946                     return false;
 947
 948                 typename gc::Guard guard;
 949                 guard.assign( &val );
 950                 if ( link_node( pNode, pos ) ) {
 951                     cds::unref(f)( val );
 952                     ++m_ItemCounter;
 953                     return true;
 954                 }
 955
 956                 // clear next field
 957                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 958             }
 959         }
 960
 961         template <typename Func>
 962         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 963         {
 964             position pos;
 965
 966             node_type * pNode = node_traits::to_node_ptr( val );
 967             while ( true ) {
 968                 if ( search( refHead, val, pos, key_comparator() ) ) {
 969                     if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
 970                         back_off()();
 971                         continue        ;   // the node found is marked as deleted
 972                     }
 973                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 974
 975                     unref(func)( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 976                     return std::make_pair( true, false );
 977                 }
 978                 else {
 979                     typename gc::Guard guard;
 980                     guard.assign( &val );
 981                     if ( link_node( pNode, pos ) ) {
 982                         ++m_ItemCounter;
 983                         unref(func)( true, val, val );
 984                         return std::make_pair( true, true );
 985                     }
 986                     // clear next field
 987                     pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 988                 }
 989             }
 990         }
 991
 992         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 993         {
 994             position pos;
 995
 996             back_off bkoff;
 997             while ( search( refHead, val, pos, key_comparator() ) ) {
 998                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
 999                     if ( unlink_node( pos ) ) {
1000                         --m_ItemCounter;
1001                         return true;
1002                     }
1003                     else
1004                         bkoff();
1005                 }
1006                 else
1007                     break;
1008             }
1009             return false;
1010         }
1011
1012         template <typename Q, typename Compare, typename Func>
1013         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1014         {
1015             back_off bkoff;
1016             while ( search( refHead, val, pos, cmp )) {
1017                 if ( unlink_node( pos ) ) {
1018                     cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ) );
1019                     --m_ItemCounter;
1020                     return true;
1021                 }
1022                 else
1023                     bkoff();
1024             }
1025             return false;
1026         }
1027
1028         template <typename Q, typename Compare, typename Func>
1029         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1030         {
1031             position pos;
1032             return erase_at( refHead, val, cmp, f, pos );
1033         }
1034
1035         template <typename Q, typename Compare>
1036         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1037         {
1038             position pos;
1039             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1040         }
1041
1042         template <typename Q, typename Compare>
1043         bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
1044         {
1045             position pos;
1046             back_off bkoff;
1047             while ( search( refHead, val, pos, cmp )) {
1048                 if ( unlink_node( pos ) ) {
1049                     dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
1050                     --m_ItemCounter;
1051                     return true;
1052                 }
1053                 else
1054                     bkoff();
1055             }
1056             return false;
1057         }
1058
1059         template <typename Q, typename Compare>
1060         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1061         {
1062             position pos;
1063             return search( refHead, val, pos, cmp );
1064         }
1065
1066         template <typename Q, typename Compare, typename Func>
1067         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1068         {
1069             position pos;
1070             if ( search( refHead, val, pos, cmp )) {
1071                 cds::unref(f)( *node_traits::to_value_ptr( *pos.pCur ), val );
1072                 return true;
1073             }
1074             return false;
1075         }
1076
1077         template <typename Q, typename Compare>
1078         bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1079         {
1080             position pos;
1081             if ( search( refHead, val, pos, cmp )) {
1082                 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1083                 return true;
1084             }
1085             return false;
1086         }
1087
1088         //@endcond
1089
1090     protected:
1091
1092         //@cond
1093         template <typename Q, typename Compare >
1094         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1095         {
1096             atomic_node_ptr * pPrev;
1097             marked_node_ptr pNext;
1098             marked_node_ptr pCur;
1099
1100             back_off        bkoff;
1101
1102 try_again:
1103             pPrev = &refHead;
1104             pNext = nullptr;
1105
1106             pCur = pPrev->load(memory_model::memory_order_relaxed);
1107             pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1108             if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1109                 goto try_again;
1110
1111             while ( true ) {
1112                 if ( pCur.ptr() == nullptr ) {
1113                     pos.pPrev = pPrev;
1114                     pos.pCur = pCur.ptr();
1115                     pos.pNext = pNext.ptr();
1116                     return false;
1117                 }
1118
1119                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1120                 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1121                 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1122                     bkoff();
1123                     goto try_again;
1124                 }
1125
1126                 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1127                     bkoff();
1128                     goto try_again;
1129                 }
1130
1131                 // pNext contains deletion mark for pCur
1132                 if ( pNext.bits() == 1 ) {
1133                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1134                     marked_node_ptr cur( pCur.ptr());
1135                     if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1136                         retire_node( pCur.ptr() );
1137                     }
1138                     else {
1139                         bkoff();
1140                         goto try_again;
1141                     }
1142                 }
1143                 else {
1144                     assert( pCur.ptr() != nullptr );
1145                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1146                     if ( nCmp >= 0 ) {
1147                         pos.pPrev = pPrev;
1148                         pos.pCur = pCur.ptr();
1149                         pos.pNext = pNext.ptr();
1150                         return nCmp == 0;
1151                     }
1152                     pPrev = &( pCur->m_pNext );
1153                     pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1154                 }
1155                 pCur = pNext;
1156                 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1157             }
1158         }
1159         //@endcond
1160     };
1161 }} // namespace cds::intrusive
1162
1163 #endif // #ifndef __CDS_INTRUSIVE_MICHAEL_LIST_IMPL_H