cds/intrusive/impl/michael_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H
   4 #define __CDS_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 cds::gc::guarded_ptr< gc, 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_relaxed );
 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_release, 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         /// Ensures that the \p val exists in the list
 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             Otherwise, the functor \p func is called with item found.
 534             The functor signature is:
 535             \code
 536                 void func( bool bNew, value_type& item, value_type& val );
 537             \endcode
 538             with arguments:
 539             - \p bNew - \p true if the item has been inserted, \p false otherwise
 540             - \p item - item of the list
 541             - \p val - argument \p val passed into the \p ensure function
 542             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 543             refers to the same thing.
 544
 545             The functor may change non-key fields of the \p item; however, \p func must guarantee
 546             that during changing no any other modifications could be made on this item by concurrent threads.
 547
 548             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 549             \p second is \p true if new item has been added or \p false if the item with \p key
 550             already is in the list.
 551
 552             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 553         */
 554         template <typename Func>
 555         std::pair<bool, bool> ensure( value_type& val, Func func )
 556         {
 557             return ensure_at( m_pHead, val, func );
 558         }
 559
 560         /// Unlinks the item \p val from the list
 561         /**
 562             The function searches the item \p val in the list and unlinks it from the list
 563             if it is found and it is equal to \p val.
 564
 565             Difference between \p erase() and \p %unlink(): \p %erase() finds <i>a key</i>
 566             and deletes the item found. \p %unlink() finds an item by key and deletes it
 567             only if \p val is an item of the list, i.e. the pointer to item found
 568             is equal to <tt> &val </tt>.
 569
 570             The function returns \p true if success and \p false otherwise.
 571         */
 572         bool unlink( value_type& val )
 573         {
 574             return unlink_at( m_pHead, val );
 575         }
 576
 577         /// Deletes the item from the list
 578         /** \anchor cds_intrusive_MichaelList_hp_erase_val
 579             The function searches an item with key equal to \p key in the list,
 580             unlinks it from the list, and returns \p true.
 581             If \p key is not found the function return \p false.
 582         */
 583         template <typename Q>
 584         bool erase( Q const& key )
 585         {
 586             return erase_at( m_pHead, key, key_comparator() );
 587         }
 588
 589         /// Deletes the item from the list using \p pred predicate for searching
 590         /**
 591             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_val "erase(Q const&)"
 592             but \p pred is used for key comparing.
 593             \p Less functor has the interface like \p std::less.
 594             \p pred must imply the same element order as the comparator used for building the list.
 595         */
 596         template <typename Q, typename Less>
 597         bool erase_with( Q const& key, Less pred )
 598         {
 599             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 600         }
 601
 602         /// Deletes the item from the list
 603         /** \anchor cds_intrusive_MichaelList_hp_erase_func
 604             The function searches an item with key equal to \p key in the list,
 605             call \p func functor with item found, unlinks it from the list, and returns \p true.
 606             The \p Func interface is
 607             \code
 608             struct functor {
 609                 void operator()( value_type const& item );
 610             };
 611             \endcode
 612             If \p key is not found the function return \p false, \p func is not called.
 613         */
 614         template <typename Q, typename Func>
 615         bool erase( Q const& key, Func func )
 616         {
 617             return erase_at( m_pHead, key, key_comparator(), func );
 618         }
 619
 620         /// Deletes the item from the list using \p pred predicate for searching
 621         /**
 622             The function is an analog of \ref cds_intrusive_MichaelList_hp_erase_func "erase(Q const&, Func)"
 623             but \p pred is used for key comparing.
 624             \p Less functor has the interface like \p std::less.
 625             \p pred must imply the same element order as the comparator used for building the list.
 626         */
 627         template <typename Q, typename Less, typename Func>
 628         bool erase_with( Q const& key, Less pred, Func f )
 629         {
 630             return erase_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 631         }
 632
 633         /// Extracts the item from the list with specified \p key
 634         /** \anchor cds_intrusive_MichaelList_hp_extract
 635             The function searches an item with key equal to \p key,
 636             unlinks it from the list, and returns it in \p dest parameter.
 637             If the item with key equal to \p key is not found the function returns \p false.
 638
 639             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 640
 641             The \ref disposer specified in \p Traits class template parameter is called automatically
 642             by garbage collector \p GC when returned \ref guarded_ptr object will be destroyed or released.
 643             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 644
 645             Usage:
 646             \code
 647             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 648             ord_list theList;
 649             // ...
 650             {
 651                 ord_list::guarded_ptr gp;
 652                 theList.extract( gp, 5 );
 653                 // Deal with gp
 654                 // ...
 655
 656                 // Destructor of gp releases internal HP guard
 657             }
 658             \endcode
 659         */
 660         template <typename Q>
 661         bool extract( guarded_ptr& dest, Q const& key )
 662         {
 663             return extract_at( m_pHead, dest.guard(), key, key_comparator() );
 664         }
 665
 666         /// Extracts the item using compare functor \p pred
 667         /**
 668             The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(guarded_ptr&, Q const&)"
 669             but \p pred predicate is used for key comparing.
 670
 671             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 672             in any order.
 673             \p pred must imply the same element order as the comparator used for building the list.
 674         */
 675         template <typename Q, typename Less>
 676         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 677         {
 678             return extract_at( m_pHead, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 679         }
 680
 681         /// Finds \p key in the list
 682         /** \anchor cds_intrusive_MichaelList_hp_find_func
 683             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 684             The interface of \p Func functor is:
 685             \code
 686             struct functor {
 687                 void operator()( value_type& item, Q& key );
 688             };
 689             \endcode
 690             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 691
 692             The functor may change non-key fields of \p item. Note that the function is only guarantee
 693             that \p item cannot be disposed during functor is executing.
 694             The function does not serialize simultaneous access to the \p item. If such access is
 695             possible you must provide your own synchronization schema to keep out unsafe item modifications.
 696
 697             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 698             may modify both arguments.
 699
 700             The function returns \p true if \p val is found, \p false otherwise.
 701         */
 702         template <typename Q, typename Func>
 703         bool find( Q& key, Func f )
 704         {
 705             return find_at( m_pHead, key, key_comparator(), f );
 706         }
 707         //@cond
 708         template <typename Q, typename Func>
 709         bool find( Q const& key, Func f )
 710         {
 711             return find_at( m_pHead, key, key_comparator(), f );
 712         }
 713         //@endcond
 714
 715         /// Finds the \p key using \p pred predicate for searching
 716         /**
 717             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
 718             but \p pred is used for key comparing.
 719             \p Less functor has the interface like \p std::less.
 720             \p pred must imply the same element order as the comparator used for building the list.
 721         */
 722         template <typename Q, typename Less, typename Func>
 723         bool find_with( Q& key, Less pred, Func f )
 724         {
 725             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 726         }
 727         //@cond
 728         template <typename Q, typename Less, typename Func>
 729         bool find_with( Q const& key, Less pred, Func f )
 730         {
 731             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 732         }
 733         //@endcond
 734
 735         /// Finds the \p key
 736         /** \anchor cds_intrusive_MichaelList_hp_find_val
 737             The function searches the item with key equal to \p key
 738             and returns \p true if it is found, and \p false otherwise
 739         */
 740         template <typename Q>
 741         bool find( Q const& key )
 742         {
 743             return find_at( m_pHead, key, key_comparator() );
 744         }
 745
 746         /// Finds the key \p val using \p pred predicate for searching
 747         /**
 748             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_val "find(Q const&)"
 749             but \p pred is used for key comparing.
 750             \p Less functor has the interface like \p std::less.
 751             \p pred must imply the same element order as the comparator used for building the list.
 752         */
 753         template <typename Q, typename Less>
 754         bool find_with( Q const& key, Less pred )
 755         {
 756             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>() );
 757         }
 758
 759         /// Finds the \p key and return the item found
 760         /** \anchor cds_intrusive_MichaelList_hp_get
 761             The function searches the item with key equal to \p key
 762             and assigns the item found to guarded pointer \p ptr.
 763             The function returns \p true if \p key is found, and \p false otherwise.
 764             If \p key is not found the \p ptr parameter is not changed.
 765
 766             The \ref disposer specified in \p Traits class template parameter is called
 767             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 768             will be destroyed or released.
 769             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 770
 771             Usage:
 772             \code
 773             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 774             ord_list theList;
 775             // ...
 776             {
 777                 ord_list::guarded_ptr gp;
 778                 if ( theList.get( gp, 5 )) {
 779                     // Deal with gp
 780                     //...
 781                 }
 782                 // Destructor of guarded_ptr releases internal HP guard
 783             }
 784             \endcode
 785
 786             Note the compare functor specified for \p Traits template parameter
 787             should accept a parameter of type \p Q that can be not the same as \p value_type.
 788         */
 789         template <typename Q>
 790         bool get( guarded_ptr& ptr, Q const& key )
 791         {
 792             return get_at( m_pHead, ptr.guard(), key, key_comparator() );
 793         }
 794
 795         /// Finds the \p key and return the item found
 796         /**
 797             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( guarded_ptr& ptr, Q const&)"
 798             but \p pred is used for comparing the keys.
 799
 800             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 801             in any order.
 802             \p pred must imply the same element order as the comparator used for building the list.
 803         */
 804         template <typename Q, typename Less>
 805         bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
 806         {
 807             return get_at( m_pHead, ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 808         }
 809
 810         /// Clears the list
 811         /**
 812             The function unlink all items from the list.
 813         */
 814         void clear()
 815         {
 816             typename gc::Guard guard;
 817             marked_node_ptr head;
 818             while ( true ) {
 819                 head = m_pHead.load(memory_model::memory_order_relaxed);
 820                 if ( head.ptr() )
 821                     guard.assign( node_traits::to_value_ptr( *head.ptr() ));
 822                 if ( m_pHead.load(memory_model::memory_order_acquire) == head ) {
 823                     if ( head.ptr() == nullptr )
 824                         break;
 825                     value_type& val = *node_traits::to_value_ptr( *head.ptr() );
 826                     unlink( val );
 827                 }
 828             }
 829         }
 830
 831         /// Checks whether the list is empty
 832         bool empty() const
 833         {
 834             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 835         }
 836
 837         /// Returns list's item count
 838         /**
 839             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 840             this function always returns 0.
 841
 842             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 843             is empty. To check list emptyness use \p empty() method.
 844         */
 845         size_t size() const
 846         {
 847             return m_ItemCounter.value();
 848         }
 849
 850     protected:
 851         //@cond
 852         // split-list support
 853         bool insert_aux_node( node_type * pNode )
 854         {
 855             return insert_aux_node( m_pHead, pNode );
 856         }
 857
 858         // split-list support
 859         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 860         {
 861             assert( pNode != nullptr );
 862
 863             // Hack: convert node_type to value_type.
 864             // In principle, auxiliary node can be non-reducible to value_type
 865             // We assume that comparator can correctly distinguish aux and regular node.
 866             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 867         }
 868
 869         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 870         {
 871             node_type * pNode = node_traits::to_node_ptr( val );
 872             link_checker::is_empty( pNode );
 873             position pos;
 874
 875             while ( true ) {
 876                 if ( search( refHead, val, pos, key_comparator() ) )
 877                     return false;
 878
 879                 if ( link_node( pNode, pos ) ) {
 880                     ++m_ItemCounter;
 881                     return true;
 882                 }
 883
 884                 // clear next field
 885                 pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 886             }
 887         }
 888
 889         template <typename Func>
 890         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 891         {
 892             node_type * pNode = node_traits::to_node_ptr( val );
 893             link_checker::is_empty( pNode );
 894             position pos;
 895
 896             while ( true ) {
 897                 if ( search( refHead, val, pos, key_comparator() ) )
 898                     return false;
 899
 900                 typename gc::Guard guard;
 901                 guard.assign( &val );
 902                 if ( link_node( pNode, pos ) ) {
 903                     f( val );
 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         std::pair<bool, bool> ensure_at( atomic_node_ptr& refHead, value_type& val, Func func )
 915         {
 916             position pos;
 917
 918             node_type * pNode = node_traits::to_node_ptr( val );
 919             while ( true ) {
 920                 if ( search( refHead, val, pos, key_comparator() ) ) {
 921                     if ( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits() ) {
 922                         back_off()();
 923                         continue        ;   // the node found is marked as deleted
 924                     }
 925                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 926
 927                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 928                     return std::make_pair( true, false );
 929                 }
 930                 else {
 931                     typename gc::Guard guard;
 932                     guard.assign( &val );
 933                     if ( link_node( pNode, pos ) ) {
 934                         ++m_ItemCounter;
 935                         func( true, val, val );
 936                         return std::make_pair( true, true );
 937                     }
 938                     // clear next field
 939                     pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 940                 }
 941             }
 942         }
 943
 944         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
 945         {
 946             position pos;
 947
 948             back_off bkoff;
 949             while ( search( refHead, val, pos, key_comparator() ) ) {
 950                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
 951                     if ( unlink_node( pos ) ) {
 952                         --m_ItemCounter;
 953                         return true;
 954                     }
 955                     else
 956                         bkoff();
 957                 }
 958                 else
 959                     break;
 960             }
 961             return false;
 962         }
 963
 964         template <typename Q, typename Compare, typename Func>
 965         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
 966         {
 967             back_off bkoff;
 968             while ( search( refHead, val, pos, cmp )) {
 969                 if ( unlink_node( pos ) ) {
 970                     f( *node_traits::to_value_ptr( *pos.pCur ) );
 971                     --m_ItemCounter;
 972                     return true;
 973                 }
 974                 else
 975                     bkoff();
 976             }
 977             return false;
 978         }
 979
 980         template <typename Q, typename Compare, typename Func>
 981         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
 982         {
 983             position pos;
 984             return erase_at( refHead, val, cmp, f, pos );
 985         }
 986
 987         template <typename Q, typename Compare>
 988         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 989         {
 990             position pos;
 991             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
 992         }
 993
 994         template <typename Q, typename Compare>
 995         bool extract_at( atomic_node_ptr& refHead, typename gc::Guard& dest, Q const& val, Compare cmp )
 996         {
 997             position pos;
 998             back_off bkoff;
 999             while ( search( refHead, val, pos, cmp )) {
1000                 if ( unlink_node( pos ) ) {
1001                     dest.assign( pos.guards.template get<value_type>( position::guard_current_item ) );
1002                     --m_ItemCounter;
1003                     return true;
1004                 }
1005                 else
1006                     bkoff();
1007             }
1008             return false;
1009         }
1010
1011         template <typename Q, typename Compare>
1012         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1013         {
1014             position pos;
1015             return search( refHead, val, pos, cmp );
1016         }
1017
1018         template <typename Q, typename Compare, typename Func>
1019         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1020         {
1021             position pos;
1022             if ( search( refHead, val, pos, cmp )) {
1023                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1024                 return true;
1025             }
1026             return false;
1027         }
1028
1029         template <typename Q, typename Compare>
1030         bool get_at( atomic_node_ptr& refHead, typename gc::Guard& guard, Q const& val, Compare cmp )
1031         {
1032             position pos;
1033             if ( search( refHead, val, pos, cmp )) {
1034                 guard.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1035                 return true;
1036             }
1037             return false;
1038         }
1039
1040         //@endcond
1041
1042     protected:
1043
1044         //@cond
1045         template <typename Q, typename Compare >
1046         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1047         {
1048             atomic_node_ptr * pPrev;
1049             marked_node_ptr pNext;
1050             marked_node_ptr pCur;
1051
1052             back_off        bkoff;
1053
1054 try_again:
1055             pPrev = &refHead;
1056             pNext = nullptr;
1057
1058             pCur = pPrev->load(memory_model::memory_order_relaxed);
1059             pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ) );
1060             if ( pPrev->load(memory_model::memory_order_acquire) != pCur.ptr() )
1061                 goto try_again;
1062
1063             while ( true ) {
1064                 if ( pCur.ptr() == nullptr ) {
1065                     pos.pPrev = pPrev;
1066                     pos.pCur = pCur.ptr();
1067                     pos.pNext = pNext.ptr();
1068                     return false;
1069                 }
1070
1071                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
1072                 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
1073                 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
1074                     bkoff();
1075                     goto try_again;
1076                 }
1077
1078                 if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
1079                     bkoff();
1080                     goto try_again;
1081                 }
1082
1083                 // pNext contains deletion mark for pCur
1084                 if ( pNext.bits() == 1 ) {
1085                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1086                     marked_node_ptr cur( pCur.ptr());
1087                     if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
1088                         retire_node( pCur.ptr() );
1089                     }
1090                     else {
1091                         bkoff();
1092                         goto try_again;
1093                     }
1094                 }
1095                 else {
1096                     assert( pCur.ptr() != nullptr );
1097                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1098                     if ( nCmp >= 0 ) {
1099                         pos.pPrev = pPrev;
1100                         pos.pCur = pCur.ptr();
1101                         pos.pNext = pNext.ptr();
1102                         return nCmp == 0;
1103                     }
1104                     pPrev = &( pCur->m_pNext );
1105                     pos.guards.assign( position::guard_prev_item, node_traits::to_value_ptr( pCur.ptr() ) );
1106                 }
1107                 pCur = pNext;
1108                 pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1109             }
1110         }
1111         //@endcond
1112     };
1113 }} // namespace cds::intrusive
1114
1115 #endif // #ifndef __CDS_INTRUSIVE_IMPL_MICHAEL_LIST_H