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         // Deprecated, use update()
 563         template <typename Func>
 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         /// Finds the \p key
 755         /** \anchor cds_intrusive_MichaelList_hp_find_val
 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 find( Q const& key )
 761         {
 762             return find_at( m_pHead, key, key_comparator() );
 763         }
 764
 765         /// Finds the key \p val using \p pred predicate for searching
 766         /**
 767             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
 768             but \p pred is used for key comparing.
 769             \p Less functor has the interface like \p std::less.
 770             \p pred must imply the same element order as the comparator used for building the list.
 771         */
 772         template <typename Q, typename Less>
 773         bool find_with( Q const& key, Less pred )
 774         {
 775             CDS_UNUSED( pred );
 776             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 777         }
 778
 779         /// Finds the \p key and return the item found
 780         /** \anchor cds_intrusive_MichaelList_hp_get
 781             The function searches the item with key equal to \p key
 782             and returns it as \p guarded_ptr.
 783             If \p key is not found the function returns an empty guarded pointer.
 784
 785             The \ref disposer specified in \p Traits class template parameter is called
 786             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 787             will be destroyed or released.
 788             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 789
 790             Usage:
 791             \code
 792             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 793             ord_list theList;
 794             // ...
 795             {
 796                 ord_list::guarded_ptr gp(theList.get( 5 ));
 797                 if ( gp ) {
 798                     // Deal with gp
 799                     //...
 800                 }
 801                 // Destructor of guarded_ptr releases internal HP guard
 802             }
 803             \endcode
 804
 805             Note the compare functor specified for \p Traits template parameter
 806             should accept a parameter of type \p Q that can be not the same as \p value_type.
 807         */
 808         template <typename Q>
 809         guarded_ptr get( Q const& key )
 810         {
 811             guarded_ptr gp;
 812             get_at( m_pHead, gp.guard(), key, key_comparator() );
 813             return gp;
 814         }
 815
 816         /// Finds the \p key and return the item found
 817         /**
 818             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
 819             but \p pred is used for comparing the keys.
 820
 821             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 822             in any order.
 823             \p pred must imply the same element order as the comparator used for building the list.
 824         */
 825         template <typename Q, typename Less>
 826         guarded_ptr get_with( Q const& key, Less pred )
 827         {
 828             CDS_UNUSED( pred );
 829             guarded_ptr gp;
 830             get_at( m_pHead, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 831             return gp;
 832         }
 833
 834         /// Clears the list
 835         /**
 836             The function unlink all items from the list.
 837         */
 838         void clear()
 839         {
 840             typename gc::Guard guard;
 841             marked_node_ptr head;
 842             while ( true ) {
 843                 head = m_pHead.load(memory_model::memory_order_relaxed);
 844                 if ( head.ptr() )
 845                     guard.assign( node_traits::to_value_ptr( *head.ptr() ));
 846                 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
 847                     if ( head.ptr() == nullptr )
 848                         break;
 849                     value_type& val = *node_traits::to_value_ptr( *head.ptr() );
 850                     unlink( val );
 851                 }
 852             }
 853         }
 854
 855         /// Checks whether the list is empty
 856         bool empty() const
 857         {
 858             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 859         }
 860
 861         /// Returns list's item count
 862         /**
 863             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 864             this function always returns 0.
 865
 866             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 867             is empty. To check list emptyness use \p empty() method.
 868         */
 869         size_t size() const
 870         {
 871             return m_ItemCounter.value();
 872         }
 873
 874     protected:
 875         //@cond
 876         // split-list support
 877         bool insert_aux_node( node_type * pNode )
 878         {
 879             return insert_aux_node( m_pHead, pNode );
 880         }
 881
 882         // split-list support
 883         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 884         {
 885             assert( pNode != nullptr );
 886
 887             // Hack: convert node_type to value_type.
 888             // In principle, auxiliary node can be non-reducible to value_type
 889             // We assume that comparator can correctly distinguish aux and regular node.
 890             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 891         }
 892
 893         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 894         {
 895             node_type * pNode = node_traits::to_node_ptr( val );
 896             link_checker::is_empty( pNode );
 897             position pos;
 898
 899             while ( true ) {
 900                 if ( search( refHead, val, pos, key_comparator() ) )
 901                     return false;
 902
 903                 if ( link_node( pNode, pos ) ) {
 904                     ++m_ItemCounter;
 905                     return true;
 906                 }
 907
 908                 // clear next field
 909                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 910             }
 911         }
 912
 913         template <typename Func>
 914         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 915         {
 916             node_type * pNode = node_traits::to_node_ptr( val );
 917             link_checker::is_empty( pNode );
 918             position pos;
 919
 920             while ( true ) {
 921                 if ( search( refHead, val, pos, key_comparator() ) )
 922                     return false;
 923
 924                 typename gc::Guard guard;
 925                 guard.assign( &val );
 926                 if ( link_node( pNode, pos ) ) {
 927                     f( val );
 928                     ++m_ItemCounter;
 929                     return true;
 930                 }
 931
 932                 // clear next field
 933                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 934             }
 935         }
 936
 937         template <typename Func>
 938         std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
 939         {
 940             position pos;
 941
 942             node_type * pNode = node_traits::to_node_ptr( val );
 943             while ( true ) {
 944                 if ( search( refHead, val, pos, key_comparator() ) ) {
 945                     if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
 946                         back_off()();
 947                         continue        ;   // the node found is marked as deleted
 948                     }
 949                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 950
 951                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 952                     return std::make_pair( true, false );
 953                 }
 954                 else {
 955                     if ( !bInsert )
 956                         return std::make_pair( false, false );
 957
 958                     typename gc::Guard guard;
 959                     guard.assign( &val );
 960                     if ( link_node( pNode, pos ) ) {
 961                         ++m_ItemCounter;
 962                         func( true, val, val );
 963                         return std::make_pair( true, true );
 964                     }
 965                     // clear next field
 966                     pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 967                 }
 968             }
 969         }
 970
 971         template <typename Func>
 972         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 973         {
 974             return update_at( refHead, val, func, true );
 975         }
 976
 977         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 978         {
 979             position pos;
 980
 981             back_off bkoff;
 982             while ( search( refHead, val, pos, key_comparator() ) ) {
 983                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
 984                     if ( unlink_node( pos ) ) {
 985                         --m_ItemCounter;
 986                         return true;
 987                     }
 988                     else
 989                         bkoff();
 990                 }
 991                 else
 992                     break;
 993             }
 994             return false;
 995         }
 996
 997         template <typename Q, typename Compare, typename Func>
 998         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
 999         {
1000             back_off bkoff;
1001             while ( search( refHead, val, pos, cmp )) {
1002                 if ( unlink_node( pos ) ) {
1003                     f( *node_traits::to_value_ptr( *pos.pCur ) );
1004                     --m_ItemCounter;
1005                     return true;
1006                 }
1007                 else
1008                     bkoff();
1009             }
1010             return false;
1011         }
1012
1013         template <typename Q, typename Compare, typename Func>
1014         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1015         {
1016             position pos;
1017             return erase_at( refHead, val, cmp, f, pos );
1018         }
1019
1020         template <typename Q, typename Compare>
1021         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1022         {
1023             position pos;
1024             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1025         }
1026
1027         template <typename Q, typename Compare>
1028         bool extract_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& dest, Q const& val, Compare cmp )
1029         {
1030             position pos;
1031             back_off bkoff;
1032             while ( search( refHead, val, pos, cmp )) {
1033                 if ( unlink_node( pos ) ) {
1034                     dest.set( pos.guards.template get<value_type>( position::guard_current_item ) );
1035                     --m_ItemCounter;
1036                     return true;
1037                 }
1038                 else
1039                     bkoff();
1040             }
1041             return false;
1042         }
1043
1044         template <typename Q, typename Compare>
1045         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1046         {
1047             position pos;
1048             return search( refHead, val, pos, cmp );
1049         }
1050
1051         template <typename Q, typename Compare, typename Func>
1052         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1053         {
1054             position pos;
1055             if ( search( refHead, val, pos, cmp )) {
1056                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1057                 return true;
1058             }
1059             return false;
1060         }
1061
1062         template <typename Q, typename Compare>
1063         bool get_at( atomic_node_ptr& refHead, typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
1064         {
1065             position pos;
1066             if ( search( refHead, val, pos, cmp )) {
1067                 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
1068                 return true;
1069             }
1070             return false;
1071         }
1072
1073         //@endcond
1074
1075     protected:
1076
1077         //@cond
1078         template <typename Q, typename Compare >
1079         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1080         {
1081             atomic_node_ptr * pPrev;
1082             marked_node_ptr pNext;
1083             marked_node_ptr pCur;
1084
1085             back_off        bkoff;
1086
1087         try_again:
1088             pPrev = &refHead;
1089             pNext = nullptr;
1090
1091             pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1092                    [](marked_node_ptr p) -> value_type *
1093                     {
1094                         return node_traits::to_value_ptr( p.ptr() );
1095                     });
1096
1097             while ( true ) {
1098                 if ( pCur.ptr() == nullptr ) {
1099                     pos.pPrev = pPrev;
1100                     pos.pCur = nullptr;
1101                     pos.pNext = nullptr;
1102                     return false;
1103                 }
1104
1105                 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1106                         [](marked_node_ptr p ) -> value_type *
1107                         {
1108                             return node_traits::to_value_ptr( p.ptr() );
1109                         });
1110                 if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) {
1111                     bkoff();
1112                     goto try_again;
1113                 }
1114
1115                 // pNext contains deletion mark for pCur
1116                 if ( pNext.bits() == 1 ) {
1117                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1118                     marked_node_ptr cur( pCur.ptr());
1119                     if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
1120                         retire_node( pCur.ptr() );
1121                     }
1122                     else {
1123                         bkoff();
1124                         goto try_again;
1125                     }
1126                 }
1127                 else {
1128                     assert( pCur.ptr() != nullptr );
1129                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1130                     if ( nCmp >= 0 ) {
1131                         pos.pPrev = pPrev;
1132                         pos.pCur = pCur.ptr();
1133                         pos.pNext = pNext.ptr();
1134                         return nCmp == 0;
1135                     }
1136                     pPrev = &( pCur->m_pNext );
1137                     pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1138                 }
1139                 pCur = pNext;
1140                 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1141             }
1142         }
1143         //@endcond
1144     };
1145 }} // namespace cds::intrusive
1146
1147 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H