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