cds/intrusive/impl/michael_list.h

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