cds/intrusive/impl/michael_list.h

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