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                     }
 295                     else {
 296                         m_pNode = nullptr;
 297                         m_Guard.clear();
 298                     }
 299                 }
 300             }
 301
 302             iterator_type( atomic_node_ptr const& pNode )
 303             {
 304                 for (;;) {
 305                     marked_node_ptr p = pNode.load(memory_model::memory_order_relaxed);
 306                     if ( p.ptr() ) {
 307                         m_pNode = m_Guard.assign( node_traits::to_value_ptr( p.ptr() ) );
 308                     }
 309                     else {
 310                         m_pNode = nullptr;
 311                         m_Guard.clear();
 312                     }
 313                     if ( p == pNode.load(memory_model::memory_order_acquire) )
 314                         break;
 315                 }
 316             }
 317
 318         public:
 319             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 320             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 321
 322             iterator_type()
 323                 : m_pNode( nullptr )
 324             {}
 325
 326             iterator_type( iterator_type const& src )
 327             {
 328                 if ( src.m_pNode ) {
 329                     m_pNode = m_Guard.assign( src.m_pNode );
 330                 }
 331                 else
 332                     m_pNode = nullptr;
 333             }
 334
 335             value_ptr operator ->() const
 336             {
 337                 return m_pNode;
 338             }
 339
 340             value_ref operator *() const
 341             {
 342                 assert( m_pNode != nullptr );
 343                 return *m_pNode;
 344             }
 345
 346             /// Pre-increment
 347             iterator_type& operator ++()
 348             {
 349                 next();
 350                 return *this;
 351             }
 352
 353             iterator_type& operator = (iterator_type const& src)
 354             {
 355                 m_pNode = src.m_pNode;
 356                 m_Guard.assign( m_pNode );
 357                 return *this;
 358             }
 359
 360             /*
 361             /// Post-increment
 362             void operator ++(int)
 363             {
 364                 next();
 365             }
 366             */
 367
 368             template <bool C>
 369             bool operator ==(iterator_type<C> const& i ) const
 370             {
 371                 return m_pNode == i.m_pNode;
 372             }
 373             template <bool C>
 374             bool operator !=(iterator_type<C> const& i ) const
 375             {
 376                 return m_pNode != i.m_pNode;
 377             }
 378         };
 379         //@endcond
 380
 381     public:
 382         /// Forward iterator
 383         /**
 384             The forward iterator for Michael's list has some features:
 385             - it has no post-increment operator
 386             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 387               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
 388               may be thrown if the limit of guard count per thread is exceeded.
 389             - The iterator cannot be moved across thread boundary since it contains thread-private GC's guard.
 390             - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
 391               deleting operations there is no guarantee that you iterate all item in the list.
 392
 393             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 394             for debug purpose only.
 395
 396             The iterator interface:
 397             \code
 398             class iterator {
 399             public:
 400                 // Default constructor
 401                 iterator();
 402
 403                 // Copy construtor
 404                 iterator( iterator const& src );
 405
 406                 // Dereference operator
 407                 value_type * operator ->() const;
 408
 409                 // Dereference operator
 410                 value_type& operator *() const;
 411
 412                 // Preincrement operator
 413                 iterator& operator ++();
 414
 415                 // Assignment operator
 416                 iterator& operator = (iterator const& src);
 417
 418                 // Equality operators
 419                 bool operator ==(iterator const& i ) const;
 420                 bool operator !=(iterator const& i ) const;
 421             };
 422             \endcode
 423         */
 424         typedef iterator_type<false>    iterator;
 425         /// Const forward iterator
 426         /**
 427             For iterator's features and requirements see \ref iterator
 428         */
 429         typedef iterator_type<true>     const_iterator;
 430
 431         /// Returns a forward iterator addressing the first element in a list
 432         /**
 433             For empty list \code begin() == end() \endcode
 434         */
 435         iterator begin()
 436         {
 437             return iterator( m_pHead );
 438         }
 439
 440         /// Returns an iterator that addresses the location succeeding the last element in a list
 441         /**
 442             Do not use the value returned by <tt>end</tt> function to access any item.
 443             Internally, <tt>end</tt> returning value equals to \p nullptr.
 444
 445             The returned value can be used only to control reaching the end of the list.
 446             For empty list <tt>begin() == end()</tt>
 447         */
 448         iterator end()
 449         {
 450             return iterator();
 451         }
 452
 453         /// Returns a forward const iterator addressing the first element in a list
 454         const_iterator cbegin() const
 455         {
 456             return const_iterator( m_pHead );
 457         }
 458
 459         /// Returns a forward const iterator addressing the first element in a list
 460         const_iterator begin() const
 461         {
 462             return const_iterator( m_pHead );
 463         }
 464
 465         /// Returns an const iterator that addresses the location succeeding the last element in a list
 466         const_iterator end() const
 467         {
 468             return const_iterator();
 469         }
 470
 471         /// Returns an const iterator that addresses the location succeeding the last element in a list
 472         const_iterator cend() const
 473         {
 474             return const_iterator();
 475         }
 476
 477     public:
 478         /// Default constructor initializes empty list
 479         MichaelList()
 480             : m_pHead( nullptr )
 481         {
 482             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 483         }
 484
 485         /// Destroys the list object
 486         ~MichaelList()
 487         {
 488             clear();
 489         }
 490
 491         /// Inserts new node
 492         /**
 493             The function inserts \p val into the list if the list does not contain
 494             an item with key equal to \p val.
 495
 496             Returns \p true if \p val has been linked to the list, \p false otherwise.
 497         */
 498         bool insert( value_type& val )
 499         {
 500             return insert_at( m_pHead, val );
 501         }
 502
 503         /// Inserts new node
 504         /**
 505             This function is intended for derived non-intrusive containers.
 506
 507             The function allows to split new item creating into two part:
 508             - create item with key only
 509             - insert new item into the list
 510             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 511
 512             The functor signature is:
 513             \code
 514                 void func( value_type& val );
 515             \endcode
 516             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 517             \p val no any other changes could be made on this list's item by concurrent threads.
 518             The user-defined functor is called only if the inserting is success.
 519
 520             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 521         */
 522         template <typename Func>
 523         bool insert( value_type& val, Func f )
 524         {
 525             return insert_at( m_pHead, val, f );
 526         }
 527
 528         /// Updates the node
 529         /**
 530             The operation performs inserting or changing data with lock-free manner.
 531
 532             If the item \p val is not found in the list, then \p val is inserted
 533             iff \p bInsert is \p true.
 534             Otherwise, the functor \p func is called with item found.
 535             The functor signature is:
 536             \code
 537                 void func( bool bNew, value_type& item, value_type& val );
 538             \endcode
 539             with arguments:
 540             - \p bNew - \p true if the item has been inserted, \p false otherwise
 541             - \p item - item of the list
 542             - \p val - argument \p val passed into the \p update() function
 543             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 544             refers to the same thing.
 545
 546             The functor may change non-key fields of the \p item; however, \p func must guarantee
 547             that during changing no any other modifications could be made on this item by concurrent threads.
 548
 549             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 550             \p second is \p true if new item has been added or \p false if the item with \p key
 551             already is in the list.
 552
 553             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 554         */
 555         template <typename Func>
 556         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
 557         {
 558             return update_at( m_pHead, val, func, bInsert );
 559         }
 560
 561         //@cond
 562         template <typename Func>
 563         CDS_DEPRECATED("ensure() is deprecated, use update()")
 564         std::pair<bool, bool> ensure( value_type& val, Func func )
 565         {
 566             return update( val, func, true );
 567         }
 568         //@endcond
 569
 570         /// Unlinks the item \p val from the list
 571         /**
 572             The function searches the item \p val in the list and unlinks it from the list
 573             if it is found and it is equal to \p val.
 574
 575             Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
 576             and deletes the item found. \p %unlink() finds an item by key and deletes it
 577             only if \p val is an item of the list, i.e. the pointer to item found
 578             is equal to <tt> &val </tt>.
 579
 580             The function returns \p true if success and \p false otherwise.
 581         */
 582         bool unlink( value_type& val )
 583         {
 584             return unlink_at( m_pHead, val );
 585         }
 586
 587         /// Deletes the item from the list
 588         /** \anchor cds_intrusive_MichaelList_hp_erase_val
 589             The function searches an item with key equal to \p key in the list,
 590             unlinks it from the list, and returns \p true.
 591             If \p key is not found the function return \p false.
 592         */
 593         template <typename Q>
 594         bool erase( Q const& key )
 595         {
 596             return erase_at( m_pHead, key, key_comparator() );
 597         }
 598
 599         /// Deletes the item from the list using \p pred predicate for searching
 600         /**
 601             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
 602             but \p pred is used for key comparing.
 603             \p Less functor has the interface like \p std::less.
 604             \p pred must imply the same element order as the comparator used for building the list.
 605         */
 606         template <typename Q, typename Less>
 607         bool erase_with( Q const& key, Less pred )
 608         {
 609             CDS_UNUSED( pred );
 610             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 611         }
 612
 613         /// Deletes the item from the list
 614         /** \anchor cds_intrusive_MichaelList_hp_erase_func
 615             The function searches an item with key equal to \p key in the list,
 616             call \p func functor with item found, unlinks it from the list, and returns \p true.
 617             The \p Func interface is
 618             \code
 619             struct functor {
 620                 void operator()( value_type const& item );
 621             };
 622             \endcode
 623             If \p key is not found the function return \p false, \p func is not called.
 624         */
 625         template <typename Q, typename Func>
 626         bool erase( Q const& key, Func func )
 627         {
 628             return erase_at( m_pHead, key, key_comparator(), func );
 629         }
 630
 631         /// Deletes the item from the list using \p pred predicate for searching
 632         /**
 633             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
 634             but \p pred is used for key comparing.
 635             \p Less functor has the interface like \p std::less.
 636             \p pred must imply the same element order as the comparator used for building the list.
 637         */
 638         template <typename Q, typename Less, typename Func>
 639         bool erase_with( Q const& key, Less pred, Func f )
 640         {
 641             CDS_UNUSED( pred );
 642             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 643         }
 644
 645         /// Extracts the item from the list with specified \p key
 646         /** \anchor cds_intrusive_MichaelList_hp_extract
 647             The function searches an item with key equal to \p key,
 648             unlinks it from the list, and returns it as \p guarded_ptr.
 649             If \p key is not found returns an empty guarded pointer.
 650
 651             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 652
 653             The \ref disposer specified in \p Traits class template parameter is called automatically
 654             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 655             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 656
 657             Usage:
 658             \code
 659             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 660             ord_list theList;
 661             // ...
 662             {
 663                 ord_list::guarded_ptr gp(theList.extract( 5 ));
 664                 if ( gp ) {
 665                     // Deal with gp
 666                     // ...
 667                 }
 668                 // Destructor of gp releases internal HP guard
 669             }
 670             \endcode
 671         */
 672         template <typename Q>
 673         guarded_ptr extract( Q const& key )
 674         {
 675             guarded_ptr gp;
 676             extract_at( m_pHead, gp.guard(), key, key_comparator() );
 677             return gp;
 678         }
 679
 680         /// Extracts the item using compare functor \p pred
 681         /**
 682             The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
 683             but \p pred predicate is used for key comparing.
 684
 685             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 686             in any order.
 687             \p pred must imply the same element order as the comparator used for building the list.
 688         */
 689         template <typename Q, typename Less>
 690         guarded_ptr extract_with( Q const& key, Less pred )
 691         {
 692             CDS_UNUSED( pred );
 693             guarded_ptr gp;
 694             extract_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 695             return gp;
 696         }
 697
 698         /// Finds \p key in the list
 699         /** \anchor cds_intrusive_MichaelList_hp_find_func
 700             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 701             The interface of \p Func functor is:
 702             \code
 703             struct functor {
 704                 void operator()( value_type& item, Q& key );
 705             };
 706             \endcode
 707             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 708
 709             The functor may change non-key fields of \p item. Note that the function is only guarantee
 710             that \p item cannot be disposed during functor is executing.
 711             The function does not serialize simultaneous access to the \p item. If such access is
 712             possible you must provide your own synchronization schema to keep out unsafe item modifications.
 713
 714             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 715             may modify both arguments.
 716
 717             The function returns \p true if \p val is found, \p false otherwise.
 718         */
 719         template <typename Q, typename Func>
 720         bool find( Q& key, Func f )
 721         {
 722             return find_at( m_pHead, key, key_comparator(), f );
 723         }
 724         //@cond
 725         template <typename Q, typename Func>
 726         bool find( Q const& key, Func f )
 727         {
 728             return find_at( m_pHead, key, key_comparator(), f );
 729         }
 730         //@endcond
 731
 732         /// Finds the \p key using \p pred predicate for searching
 733         /**
 734             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
 735             but \p pred is used for key comparing.
 736             \p Less functor has the interface like \p std::less.
 737             \p pred must imply the same element order as the comparator used for building the list.
 738         */
 739         template <typename Q, typename Less, typename Func>
 740         bool find_with( Q& key, Less pred, Func f )
 741         {
 742             CDS_UNUSED( pred );
 743             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 744         }
 745         //@cond
 746         template <typename Q, typename Less, typename Func>
 747         bool find_with( Q const& key, Less pred, Func f )
 748         {
 749             CDS_UNUSED( pred );
 750             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 751         }
 752         //@endcond
 753
 754         /// Checks whether the list contains \p key
 755         /**
 756             The function searches the item with key equal to \p key
 757             and returns \p true if it is found, and \p false otherwise.
 758         */
 759         template <typename Q>
 760         bool contains( Q const& key )
 761         {
 762             return find_at( m_pHead, key, key_comparator() );
 763         }
 764         //@cond
 765         template <typename Q>
 766         CDS_DEPRECATED("deprecated, use contains()")
 767         bool find( Q const& key )
 768         {
 769             return contains( key );
 770         }
 771         //@endcond
 772
 773         /// Checks whether the list contains \p key using \p pred predicate for searching
 774         /**
 775             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 776             \p Less functor has the interface like \p std::less.
 777             \p Less must imply the same element order as the comparator used for building the list.
 778         */
 779         template <typename Q, typename Less>
 780         bool contains( Q const& key, Less pred )
 781         {
 782             CDS_UNUSED( pred );
 783             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 784         }
 785         //@cond
 786         template <typename Q, typename Less>
 787         CDS_DEPRECATED("deprecated, use contains()")
 788         bool find_with( Q const& key, Less pred )
 789         {
 790             return contains( key, pred );
 791         }
 792         //@endcond
 793
 794         /// Finds the \p key and return the item found
 795         /** \anchor cds_intrusive_MichaelList_hp_get
 796             The function searches the item with key equal to \p key
 797             and returns it as \p guarded_ptr.
 798             If \p key is not found the function returns an empty guarded pointer.
 799
 800             The \ref disposer specified in \p Traits class template parameter is called
 801             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 802             will be destroyed or released.
 803             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 804
 805             Usage:
 806             \code
 807             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 808             ord_list theList;
 809             // ...
 810             {
 811                 ord_list::guarded_ptr gp(theList.get( 5 ));
 812                 if ( gp ) {
 813                     // Deal with gp
 814                     //...
 815                 }
 816                 // Destructor of guarded_ptr releases internal HP guard
 817             }
 818             \endcode
 819
 820             Note the compare functor specified for \p Traits template parameter
 821             should accept a parameter of type \p Q that can be not the same as \p value_type.
 822         */
 823         template <typename Q>
 824         guarded_ptr get( Q const& key )
 825         {
 826             guarded_ptr gp;
 827             get_at( m_pHead, gp.guard(), key, key_comparator() );
 828             return gp;
 829         }
 830
 831         /// Finds the \p key and return the item found
 832         /**
 833             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
 834             but \p pred is used for comparing the keys.
 835
 836             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 837             in any order.
 838             \p pred must imply the same element order as the comparator used for building the list.
 839         */
 840         template <typename Q, typename Less>
 841         guarded_ptr get_with( Q const& key, Less pred )
 842         {
 843             CDS_UNUSED( pred );
 844             guarded_ptr gp;
 845             get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 846             return gp;
 847         }
 848
 849         /// Clears the list
 850         /**
 851             The function unlink all items from the list.
 852         */
 853         void clear()
 854         {
 855             typename gc::Guard guard;
 856             marked_node_ptr head;
 857             while ( true ) {
 858                 head = m_pHead.load(memory_model::memory_order_relaxed);
 859                 if ( head.ptr() )
 860                     guard.assign( node_traits::to_value_ptr( *head.ptr() ));
 861                 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
 862                     if ( head.ptr() == nullptr )
 863                         break;
 864                     value_type& val = *node_traits::to_value_ptr( *head.ptr() );
 865                     unlink( val );
 866                 }
 867             }
 868         }
 869
 870         /// Checks whether the list is empty
 871         bool empty() const
 872         {
 873             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 874         }
 875
 876         /// Returns list's item count
 877         /**
 878             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 879             this function always returns 0.
 880
 881             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 882             is empty. To check list emptyness use \p empty() method.
 883         */
 884         size_t size() const
 885         {
 886             return m_ItemCounter.value();
 887         }
 888
 889     protected:
 890         //@cond
 891         // split-list support
 892         bool insert_aux_node( node_type * pNode )
 893         {
 894             return insert_aux_node( m_pHead, pNode );
 895         }
 896
 897         // split-list support
 898         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 899         {
 900             assert( pNode != nullptr );
 901
 902             // Hack: convert node_type to value_type.
 903             // In principle, auxiliary node can be non-reducible to value_type
 904             // We assume that comparator can correctly distinguish aux and regular node.
 905             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 906         }
 907
 908         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 909         {
 910             node_type * pNode = node_traits::to_node_ptr( val );
 911             link_checker::is_empty( pNode );
 912             position pos;
 913
 914             while ( true ) {
 915                 if ( search( refHead, val, pos, key_comparator() ) )
 916                     return false;
 917
 918                 if ( link_node( pNode, pos ) ) {
 919                     ++m_ItemCounter;
 920                     return true;
 921                 }
 922
 923                 // clear next field
 924                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 925             }
 926         }
 927
 928         template <typename Func>
 929         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 930         {
 931             node_type * pNode = node_traits::to_node_ptr( val );
 932             link_checker::is_empty( pNode );
 933             position pos;
 934
 935             while ( true ) {
 936                 if ( search( refHead, val, pos, key_comparator() ) )
 937                     return false;
 938
 939                 typename gc::Guard guard;
 940                 guard.assign( &val );
 941                 if ( link_node( pNode, pos ) ) {
 942                     f( val );
 943                     ++m_ItemCounter;
 944                     return true;
 945                 }
 946
 947                 // clear next field
 948                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 949             }
 950         }
 951
 952         template <typename Func>
 953         std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
 954         {
 955             position pos;
 956
 957             node_type * pNode = node_traits::to_node_ptr( val );
 958             while ( true ) {
 959                 if ( search( refHead, val, pos, key_comparator() ) ) {
 960                     if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
 961                         back_off()();
 962                         continue        ;   // the node found is marked as deleted
 963                     }
 964                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 965
 966                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 967                     return std::make_pair( true, false );
 968                 }
 969                 else {
 970                     if ( !bInsert )
 971                         return std::make_pair( false, false );
 972
 973                     typename gc::Guard guard;
 974                     guard.assign( &val );
 975                     if ( link_node( pNode, pos ) ) {
 976                         ++m_ItemCounter;
 977                         func( true, val, val );
 978                         return std::make_pair( true, true );
 979                     }
 980                     // clear next field
 981                     pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 982                 }
 983             }
 984         }
 985
 986         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 987         {
 988             position pos;
 989
 990             back_off bkoff;
 991             while ( search( refHead, val, pos, key_comparator() ) ) {
 992                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
 993                     if ( unlink_node( pos ) ) {
 994                         --m_ItemCounter;
 995                         return true;
 996                     }
 997                     else
 998                         bkoff();
 999                 }
1000                 else
1001                     break;
1002             }
1003             return false;
1004         }
1005
1006         template <typename Q, typename Compare, typename Func>
1007         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1008         {
1009             back_off bkoff;
1010             while ( search( refHead, val, pos, cmp )) {
1011                 if ( unlink_node( pos ) ) {
1012                     f( *node_traits::to_value_ptr( *pos.pCur ) );
1013                     --m_ItemCounter;
1014                     return true;
1015                 }
1016                 else
1017                     bkoff();
1018             }
1019             return false;
1020         }
1021
1022         template <typename Q, typename Compare, typename Func>
1023         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1024         {
1025             position pos;
1026             return erase_at( refHead, val, cmp, f, pos );
1027         }
1028
1029         template <typename Q, typename Compare>
1030         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1031         {
1032             position pos;
1033             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1034         }
1035
1036         template <typename Q, typename Compare>
1037         bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1038         {
1039             position pos;
1040             back_off bkoff;
1041             while ( search( refHead, val, pos, cmp )) {
1042                 if ( unlink_node( pos ) ) {
1043                     dest.set( pos.guards.template get<value_type>( position::guard_current_item ) );
1044                     --m_ItemCounter;
1045                     return true;
1046                 }
1047                 else
1048                     bkoff();
1049             }
1050             return false;
1051         }
1052
1053         template <typename Q, typename Compare>
1054         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1055         {
1056             position pos;
1057             return search( refHead, val, pos, cmp );
1058         }
1059
1060         template <typename Q, typename Compare, typename Func>
1061         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1062         {
1063             position pos;
1064             if ( search( refHead, val, pos, cmp )) {
1065                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1066                 return true;
1067             }
1068             return false;
1069         }
1070
1071         template <typename Q, typename Compare>
1072         bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1073         {
1074             position pos;
1075             if ( search( refHead, val, pos, cmp )) {
1076                 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1077                 return true;
1078             }
1079             return false;
1080         }
1081
1082         //@endcond
1083
1084     protected:
1085
1086         //@cond
1087         template <typename Q, typename Compare >
1088         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1089         {
1090             atomic_node_ptr * pPrev;
1091             marked_node_ptr pNext;
1092             marked_node_ptr pCur;
1093
1094             back_off        bkoff;
1095
1096         try_again:
1097             pPrev = &refHead;
1098             pNext = nullptr;
1099
1100             pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1101                    [](marked_node_ptr p) -> value_type *
1102                     {
1103                         return node_traits::to_value_ptr( p.ptr() );
1104                     });
1105
1106             while ( true ) {
1107                 if ( pCur.ptr() == nullptr ) {
1108                     pos.pPrev = pPrev;
1109                     pos.pCur = nullptr;
1110                     pos.pNext = nullptr;
1111                     return false;
1112                 }
1113
1114                 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1115                         [](marked_node_ptr p ) -> value_type *
1116                         {
1117                             return node_traits::to_value_ptr( p.ptr() );
1118                         });
1119                 if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) {
1120                     bkoff();
1121                     goto try_again;
1122                 }
1123
1124                 // pNext contains deletion mark for pCur
1125                 if ( pNext.bits() == 1 ) {
1126                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1127                     marked_node_ptr cur( pCur.ptr());
1128                     if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1129                         retire_node( pCur.ptr() );
1130                     }
1131                     else {
1132                         bkoff();
1133                         goto try_again;
1134                     }
1135                 }
1136                 else {
1137                     assert( pCur.ptr() != nullptr );
1138                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1139                     if ( nCmp >= 0 ) {
1140                         pos.pPrev = pPrev;
1141                         pos.pCur = pCur.ptr();
1142                         pos.pNext = pNext.ptr();
1143                         return nCmp == 0;
1144                     }
1145                     pPrev = &( pCur->m_pNext );
1146                     pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1147                 }
1148                 pCur = pNext;
1149                 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1150             }
1151         }
1152         //@endcond
1153     };
1154 }} // namespace cds::intrusive
1155
1156 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H