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             return extract_at( m_pHead, key, key_comparator());
 736         }
 737
 738         /// Extracts the item using compare functor \p pred
 739         /**
 740             The function is an analog of \ref cds_intrusive_MichaelList_hp_extract "extract(Q const&)"
 741             but \p pred predicate is used for key comparing.
 742
 743             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 744             in any order.
 745             \p pred must imply the same element order as the comparator used for building the list.
 746         */
 747         template <typename Q, typename Less>
 748         guarded_ptr extract_with( Q const& key, Less pred )
 749         {
 750             CDS_UNUSED( pred );
 751             return extract_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 752         }
 753
 754         /// Finds \p key in the list
 755         /** \anchor cds_intrusive_MichaelList_hp_find_func
 756             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 757             The interface of \p Func functor is:
 758             \code
 759             struct functor {
 760                 void operator()( value_type& item, Q& key );
 761             };
 762             \endcode
 763             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 764
 765             The functor may change non-key fields of \p item. Note that the function is only guarantee
 766             that \p item cannot be disposed during functor is executing.
 767             The function does not serialize simultaneous access to the \p item. If such access is
 768             possible you must provide your own synchronization schema to keep out unsafe item modifications.
 769
 770             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 771             may modify both arguments.
 772
 773             The function returns \p true if \p val is found, \p false otherwise.
 774         */
 775         template <typename Q, typename Func>
 776         bool find( Q& key, Func f )
 777         {
 778             return find_at( m_pHead, key, key_comparator(), f );
 779         }
 780         //@cond
 781         template <typename Q, typename Func>
 782         bool find( Q const& key, Func f )
 783         {
 784             return find_at( m_pHead, key, key_comparator(), f );
 785         }
 786         //@endcond
 787
 788         /// Finds the \p key using \p pred predicate for searching
 789         /**
 790             The function is an analog of \ref cds_intrusive_MichaelList_hp_find_func "find(Q&, Func)"
 791             but \p pred is used for key comparing.
 792             \p Less functor has the interface like \p std::less.
 793             \p pred must imply the same element order as the comparator used for building the list.
 794         */
 795         template <typename Q, typename Less, typename Func>
 796         bool find_with( Q& key, Less pred, Func f )
 797         {
 798             CDS_UNUSED( pred );
 799             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 800         }
 801         //@cond
 802         template <typename Q, typename Less, typename Func>
 803         bool find_with( Q const& key, Less pred, Func f )
 804         {
 805             CDS_UNUSED( pred );
 806             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 807         }
 808         //@endcond
 809
 810         /// Checks whether the list contains \p key
 811         /**
 812             The function searches the item with key equal to \p key
 813             and returns \p true if it is found, and \p false otherwise.
 814         */
 815         template <typename Q>
 816         bool contains( Q const& key )
 817         {
 818             return find_at( m_pHead, key, key_comparator());
 819         }
 820         //@cond
 821         template <typename Q>
 822         CDS_DEPRECATED("deprecated, use contains()")
 823         bool find( Q const& key )
 824         {
 825             return contains( key );
 826         }
 827         //@endcond
 828
 829         /// Checks whether the list contains \p key using \p pred predicate for searching
 830         /**
 831             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 832             \p Less functor has the interface like \p std::less.
 833             \p Less must imply the same element order as the comparator used for building the list.
 834         */
 835         template <typename Q, typename Less>
 836         bool contains( Q const& key, Less pred )
 837         {
 838             CDS_UNUSED( pred );
 839             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 840         }
 841         //@cond
 842         template <typename Q, typename Less>
 843         CDS_DEPRECATED("deprecated, use contains()")
 844         bool find_with( Q const& key, Less pred )
 845         {
 846             return contains( key, pred );
 847         }
 848         //@endcond
 849
 850         /// Finds the \p key and return the item found
 851         /** \anchor cds_intrusive_MichaelList_hp_get
 852             The function searches the item with key equal to \p key
 853             and returns it as \p guarded_ptr.
 854             If \p key is not found the function returns an empty guarded pointer.
 855
 856             The \ref disposer specified in \p Traits class template parameter is called
 857             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 858             will be destroyed or released.
 859             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 860
 861             Usage:
 862             \code
 863             typedef cds::intrusive::MichaelList< cds::gc::HP, foo, my_traits >  ord_list;
 864             ord_list theList;
 865             // ...
 866             {
 867                 ord_list::guarded_ptr gp(theList.get( 5 ));
 868                 if ( gp ) {
 869                     // Deal with gp
 870                     //...
 871                 }
 872                 // Destructor of guarded_ptr releases internal HP guard
 873             }
 874             \endcode
 875
 876             Note the compare functor specified for \p Traits template parameter
 877             should accept a parameter of type \p Q that can be not the same as \p value_type.
 878         */
 879         template <typename Q>
 880         guarded_ptr get( Q const& key )
 881         {
 882             return get_at( m_pHead, key, key_comparator());
 883         }
 884
 885         /// Finds the \p key and return the item found
 886         /**
 887             The function is an analog of \ref cds_intrusive_MichaelList_hp_get "get( Q const&)"
 888             but \p pred is used for comparing the keys.
 889
 890             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 891             in any order.
 892             \p pred must imply the same element order as the comparator used for building the list.
 893         */
 894         template <typename Q, typename Less>
 895         guarded_ptr get_with( Q const& key, Less pred )
 896         {
 897             CDS_UNUSED( pred );
 898             return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 899         }
 900
 901         /// Clears the list
 902         /**
 903             The function unlink all items from the list.
 904         */
 905         void clear()
 906         {
 907             typename gc::Guard guard;
 908             marked_node_ptr head;
 909             while ( true ) {
 910                 head = m_pHead.load(memory_model::memory_order_relaxed);
 911                 if ( head.ptr())
 912                     guard.assign( node_traits::to_value_ptr( *head.ptr()));
 913                 if ( cds_likely( m_pHead.load(memory_model::memory_order_acquire) == head )) {
 914                     if ( head.ptr() == nullptr )
 915                         break;
 916                     value_type& val = *node_traits::to_value_ptr( *head.ptr());
 917                     unlink( val );
 918                 }
 919             }
 920         }
 921
 922         /// Checks whether the list is empty
 923         bool empty() const
 924         {
 925             return m_pHead.load( memory_model::memory_order_relaxed ).all() == nullptr;
 926         }
 927
 928         /// Returns list's item count
 929         /**
 930             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 931             this function always returns 0.
 932
 933             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 934             is empty. To check list emptiness use \p empty() method.
 935         */
 936         size_t size() const
 937         {
 938             return m_ItemCounter.value();
 939         }
 940
 941         /// Returns const reference to internal statistics
 942         stat const& statistics() const
 943         {
 944             return m_Stat;
 945         }
 946
 947     protected:
 948         //@cond
 949         // split-list support
 950         bool insert_aux_node( node_type * pNode )
 951         {
 952             return insert_aux_node( m_pHead, pNode );
 953         }
 954
 955         // split-list support
 956         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 957         {
 958             assert( pNode != nullptr );
 959
 960             // Hack: convert node_type to value_type.
 961             // In principle, auxiliary node can be non-reducible to value_type
 962             // We assume that comparator can correctly distinguish aux and regular node.
 963             return insert_at( refHead, *node_traits::to_value_ptr( pNode ));
 964         }
 965
 966         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 967         {
 968             node_type * pNode = node_traits::to_node_ptr( val );
 969             position pos;
 970
 971             while ( true ) {
 972                 if ( search( refHead, val, pos, key_comparator())) {
 973                     m_Stat.onInsertFailed();
 974                     return false;
 975                 }
 976
 977                 if ( link_node( pNode, pos )) {
 978                     ++m_ItemCounter;
 979                     m_Stat.onInsertSuccess();
 980                     return true;
 981                 }
 982
 983                 m_Stat.onInsertRetry();
 984             }
 985         }
 986
 987         template <typename Func>
 988         bool insert_at( atomic_node_ptr& refHead, value_type& val, Func f )
 989         {
 990             node_type * pNode = node_traits::to_node_ptr( val );
 991             position pos;
 992
 993             while ( true ) {
 994                 if ( search( refHead, val, pos, key_comparator())) {
 995                     m_Stat.onInsertFailed();
 996                     return false;
 997                 }
 998
 999                 typename gc::Guard guard;
1000                 guard.assign( &val );
1001                 if ( link_node( pNode, pos )) {
1002                     f( val );
1003                     ++m_ItemCounter;
1004                     m_Stat.onInsertSuccess();
1005                     return true;
1006                 }
1007
1008                 m_Stat.onInsertRetry();
1009             }
1010         }
1011
1012         template <typename Func>
1013         std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bInsert )
1014         {
1015             position pos;
1016
1017             node_type * pNode = node_traits::to_node_ptr( val );
1018             while ( true ) {
1019                 if ( search( refHead, val, pos, key_comparator())) {
1020                     if ( cds_unlikely( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits())) {
1021                         back_off()();
1022                         m_Stat.onUpdateMarked();
1023                         continue;       // the node found is marked as deleted
1024                     }
1025                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
1026
1027                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1028                     m_Stat.onUpdateExisting();
1029                     return std::make_pair( true, false );
1030                 }
1031                 else {
1032                     if ( !bInsert ) {
1033                         m_Stat.onUpdateFailed();
1034                         return std::make_pair( false, false );
1035                     }
1036
1037                     typename gc::Guard guard;
1038                     guard.assign( &val );
1039                     if ( link_node( pNode, pos )) {
1040                         ++m_ItemCounter;
1041                         func( true, val, val );
1042                         m_Stat.onUpdateNew();
1043                         return std::make_pair( true, true );
1044                     }
1045                 }
1046
1047                 m_Stat.onUpdateRetry();
1048             }
1049         }
1050
1051         bool unlink_at( atomic_node_ptr& refHead, value_type& val )
1052         {
1053             position pos;
1054
1055             back_off bkoff;
1056             while ( search( refHead, val, pos, key_comparator())) {
1057                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
1058                     if ( unlink_node( pos )) {
1059                         --m_ItemCounter;
1060                         m_Stat.onEraseSuccess();
1061                         return true;
1062                     }
1063                     else
1064                         bkoff();
1065                 }
1066                 else {
1067                     m_Stat.onUpdateFailed();
1068                     break;
1069                 }
1070
1071                 m_Stat.onEraseRetry();
1072             }
1073
1074             m_Stat.onEraseFailed();
1075             return false;
1076         }
1077
1078         template <typename Q, typename Compare, typename Func>
1079         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f, position& pos )
1080         {
1081             back_off bkoff;
1082             while ( search( refHead, val, pos, cmp )) {
1083                 if ( unlink_node( pos )) {
1084                     f( *node_traits::to_value_ptr( *pos.pCur ));
1085                     --m_ItemCounter;
1086                     m_Stat.onEraseSuccess();
1087                     return true;
1088                 }
1089                 else
1090                     bkoff();
1091
1092                 m_Stat.onEraseRetry();
1093             }
1094
1095             m_Stat.onEraseFailed();
1096             return false;
1097         }
1098
1099         template <typename Q, typename Compare, typename Func>
1100         bool erase_at( atomic_node_ptr& refHead, const Q& val, Compare cmp, Func f )
1101         {
1102             position pos;
1103             return erase_at( refHead, val, cmp, f, pos );
1104         }
1105
1106         template <typename Q, typename Compare>
1107         bool erase_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1108         {
1109             position pos;
1110             return erase_at( refHead, val, cmp, [](value_type const&){}, pos );
1111         }
1112
1113         template <typename Q, typename Compare>
1114         guarded_ptr extract_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1115         {
1116             position pos;
1117             back_off bkoff;
1118             while ( search( refHead, val, pos, cmp )) {
1119                 if ( unlink_node( pos )) {
1120                     --m_ItemCounter;
1121                     m_Stat.onEraseSuccess();
1122                     return guarded_ptr( pos.guards.release( position::guard_current_item ));
1123                 }
1124                 else
1125                     bkoff();
1126                 m_Stat.onEraseRetry();
1127             }
1128
1129             m_Stat.onEraseFailed();
1130             return guarded_ptr();
1131         }
1132
1133         template <typename Q, typename Compare>
1134         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1135         {
1136             position pos;
1137             if ( search( refHead, val, pos, cmp )) {
1138                 m_Stat.onFindSuccess();
1139                 return true;
1140             }
1141
1142             m_Stat.onFindFailed();
1143             return false;
1144         }
1145
1146         template <typename Q, typename Compare, typename Func>
1147         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
1148         {
1149             position pos;
1150             if ( search( refHead, val, pos, cmp )) {
1151                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
1152                 m_Stat.onFindSuccess();
1153                 return true;
1154             }
1155
1156             m_Stat.onFindFailed();
1157             return false;
1158         }
1159
1160         template <typename Q, typename Compare>
1161         guarded_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
1162         {
1163             position pos;
1164             if ( search( refHead, val, pos, cmp )) {
1165                 m_Stat.onFindSuccess();
1166                 return guarded_ptr( pos.guards.release( position::guard_current_item ));
1167             }
1168
1169             m_Stat.onFindFailed();
1170             return guarded_ptr();
1171         }
1172
1173         // split-list support
1174         template <typename Predicate>
1175         void destroy( Predicate /*pred*/ )
1176         {
1177             clear();
1178         }
1179
1180         //@endcond
1181
1182     protected:
1183
1184         //@cond
1185         template <typename Q, typename Compare >
1186         bool search( atomic_node_ptr& refHead, const Q& val, position& pos, Compare cmp )
1187         {
1188             atomic_node_ptr * pPrev;
1189             marked_node_ptr pNext;
1190             marked_node_ptr pCur;
1191
1192             back_off        bkoff;
1193
1194         try_again:
1195             pPrev = &refHead;
1196             pNext = nullptr;
1197
1198             pCur = pos.guards.protect( position::guard_current_item, *pPrev,
1199                    [](marked_node_ptr p) -> value_type *
1200                     {
1201                         return node_traits::to_value_ptr( p.ptr());
1202                     });
1203
1204             while ( true ) {
1205                 if ( pCur.ptr() == nullptr ) {
1206                     pos.pPrev = pPrev;
1207                     pos.pCur = nullptr;
1208                     pos.pNext = nullptr;
1209                     return false;
1210                 }
1211
1212                 pNext = pos.guards.protect( position::guard_next_item, pCur->m_pNext,
1213                         [](marked_node_ptr p ) -> value_type *
1214                         {
1215                             return node_traits::to_value_ptr( p.ptr());
1216                         });
1217                 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr())) {
1218                     bkoff();
1219                     goto try_again;
1220                 }
1221
1222                 // pNext contains deletion mark for pCur
1223                 if ( pNext.bits() == 1 ) {
1224                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
1225                     marked_node_ptr cur( pCur.ptr());
1226                     if ( cds_unlikely( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
1227                         retire_node( pCur.ptr());
1228                         m_Stat.onHelpingSuccess();
1229                     }
1230                     else {
1231                         bkoff();
1232                         m_Stat.onHelpingFailed();
1233                         goto try_again;
1234                     }
1235                 }
1236                 else {
1237                     assert( pCur.ptr() != nullptr );
1238                     int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1239                     if ( nCmp >= 0 ) {
1240                         pos.pPrev = pPrev;
1241                         pos.pCur = pCur.ptr();
1242                         pos.pNext = pNext.ptr();
1243                         return nCmp == 0;
1244                     }
1245                     pPrev = &( pCur->m_pNext );
1246                     pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1247                 }
1248                 pCur = pNext;
1249                 pos.guards.copy( position::guard_current_item, position::guard_next_item );
1250             }
1251         }
1252         //@endcond
1253     };
1254 }} // namespace cds::intrusive
1255
1256 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_MICHAEL_LIST_H