cds/intrusive/michael_list_nogc.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_MICHAEL_LIST_NOGC_H
  32 #define CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H
  33
  34 #include <cds/intrusive/details/michael_list_base.h>
  35 #include <cds/gc/nogc.h>
  36 #include <cds/details/make_const_type.h>
  37
  38 namespace cds { namespace intrusive {
  39
  40     namespace michael_list {
  41         /// Michael list node
  42         /**
  43             Template parameters:
  44             - Tag - a tag used to distinguish between different implementation
  45         */
  46         template <typename Tag>
  47         struct node<gc::nogc, Tag>
  48         {
  49             typedef gc::nogc        gc  ;   ///< Garbage collector
  50             typedef Tag             tag ;   ///< tag
  51
  52             typedef atomics::atomic< node * >   atomic_ptr  ;    ///< atomic marked pointer
  53
  54             atomic_ptr m_pNext ; ///< pointer to the next node in the container
  55
  56             node()
  57                 : m_pNext( nullptr )
  58             {}
  59         };
  60     }   // namespace michael_list
  61
  62     /// Michael's lock-free ordered single-linked list (template specialization for gc::nogc)
  63     /** @ingroup cds_intrusive_list
  64         \anchor cds_intrusive_MichaelList_nogc
  65
  66         This specialization is intended for so-called append-only usage when no item
  67         reclamation may be performed. The class does not support item removal.
  68
  69         See \ref cds_intrusive_MichaelList_hp "MichaelList" for description of template parameters.
  70     */
  71     template < typename T,
  72 #ifdef CDS_DOXYGEN_INVOKED
  73         class Traits = michael_list::traits
  74 #else
  75         class Traits
  76 #endif
  77     >
  78     class MichaelList<gc::nogc, T, Traits>
  79     {
  80     public:
  81         typedef gc::nogc gc;   ///< Garbage collector
  82         typedef T       value_type; ///< type of value to be stored in the queue
  83         typedef Traits  traits;     ///< List traits
  84
  85         typedef typename traits::hook     hook;      ///< hook type
  86         typedef typename hook::node_type  node_type; ///< node type
  87
  88 #   ifdef CDS_DOXYGEN_INVOKED
  89         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
  90 #   else
  91         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
  92 #   endif
  93
  94         typedef typename traits::disposer  disposer;   ///< disposer used
  95         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
  96         typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
  97
  98         typedef typename traits::back_off     back_off;     ///< back-off strategy
  99         typedef typename traits::item_counter item_counter; ///< Item counting policy used
 100         typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
 101         typedef typename traits::stat         stat;         ///< Internal statistics
 102
 103         //@cond
 104         static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
 105
 106         // Rebind traits (split-list support)
 107         template <typename... Options>
 108         struct rebind_traits {
 109             typedef MichaelList<
 110                 gc
 111                 , value_type
 112                 , typename cds::opt::make_options< traits, Options...>::type
 113             >   type;
 114         };
 115
 116         // Stat selector
 117         template <typename Stat>
 118         using select_stat_wrapper = michael_list::select_stat_wrapper< Stat >;
 119         //@endcond
 120
 121     protected:
 122         typedef typename node_type::atomic_ptr   atomic_node_ptr ;   ///< Atomic node pointer
 123         typedef atomic_node_ptr     auxiliary_head      ;   ///< Auxiliary head type (for split-list support)
 124
 125         atomic_node_ptr     m_pHead;        ///< Head pointer
 126         item_counter        m_ItemCounter;  ///< Item counter
 127         stat                m_Stat;         ///< Internal statistics
 128
 129         //@cond
 130         /// Position pointer for item search
 131         struct position {
 132             atomic_node_ptr * pPrev ;   ///< Previous node
 133             node_type * pCur        ;   ///< Current node
 134             node_type * pNext       ;   ///< Next node
 135         };
 136         //@endcond
 137
 138     protected:
 139         //@cond
 140         static void clear_links( node_type * pNode )
 141         {
 142             pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
 143         }
 144
 145         template <class Disposer>
 146         static void dispose_node( node_type * pNode, Disposer disp )
 147         {
 148             clear_links( pNode );
 149             disp( node_traits::to_value_ptr( *pNode ));
 150         }
 151
 152         template <class Disposer>
 153         static void dispose_value( value_type& val, Disposer disp )
 154         {
 155             dispose_node( node_traits::to_node_ptr( val ), disp );
 156         }
 157
 158         static bool link_node( node_type * pNode, position& pos )
 159         {
 160             assert( pNode != nullptr );
 161             link_checker::is_empty( pNode );
 162
 163             pNode->m_pNext.store( pos.pCur, memory_model::memory_order_relaxed );
 164             if ( cds_likely( pos.pPrev->compare_exchange_strong( pos.pCur, pNode, memory_model::memory_order_release, atomics::memory_order_relaxed )))
 165                 return true;
 166
 167             pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 168             return false;
 169         }
 170         //@endcond
 171
 172     protected:
 173         //@cond
 174         template <bool IsConst>
 175         class iterator_type
 176         {
 177             friend class MichaelList;
 178             value_type * m_pNode;
 179
 180             void next()
 181             {
 182                 if ( m_pNode ) {
 183                     node_type * pNode = node_traits::to_node_ptr( *m_pNode )->m_pNext.load(memory_model::memory_order_acquire);
 184                     if ( pNode )
 185                         m_pNode = node_traits::to_value_ptr( *pNode );
 186                     else
 187                         m_pNode = nullptr;
 188                 }
 189             }
 190
 191         protected:
 192             explicit iterator_type( node_type * pNode)
 193             {
 194                 if ( pNode )
 195                     m_pNode = node_traits::to_value_ptr( *pNode );
 196                 else
 197                     m_pNode = nullptr;
 198             }
 199             explicit iterator_type( atomic_node_ptr const& refNode)
 200             {
 201                 node_type * pNode = refNode.load(memory_model::memory_order_relaxed);
 202                 if ( pNode )
 203                     m_pNode = node_traits::to_value_ptr( *pNode );
 204                 else
 205                     m_pNode = nullptr;
 206             }
 207
 208         public:
 209             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 210             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 211
 212             iterator_type()
 213                 : m_pNode( nullptr )
 214             {}
 215
 216             iterator_type( const iterator_type& src )
 217                 : m_pNode( src.m_pNode )
 218             {}
 219
 220             value_ptr operator ->() const
 221             {
 222                 return m_pNode;
 223             }
 224
 225             value_ref operator *() const
 226             {
 227                 assert( m_pNode != nullptr );
 228                 return *m_pNode;
 229             }
 230
 231             /// Pre-increment
 232             iterator_type& operator ++()
 233             {
 234                 next();
 235                 return *this;
 236             }
 237
 238             /// Post-increment
 239             iterator_type operator ++(int)
 240             {
 241                 iterator_type i(*this);
 242                 next();
 243                 return i;
 244             }
 245
 246             iterator_type& operator = (const iterator_type& src)
 247             {
 248                 m_pNode = src.m_pNode;
 249                 return *this;
 250             }
 251
 252             template <bool C>
 253             bool operator ==(iterator_type<C> const& i ) const
 254             {
 255                 return m_pNode == i.m_pNode;
 256             }
 257             template <bool C>
 258             bool operator !=(iterator_type<C> const& i ) const
 259             {
 260                 return m_pNode != i.m_pNode;
 261             }
 262         };
 263         //@endcond
 264
 265     public:
 266         /// Forward iterator
 267         typedef iterator_type<false>    iterator;
 268         /// Const forward iterator
 269         typedef iterator_type<true>     const_iterator;
 270
 271         /// Returns a forward iterator addressing the first element in a list
 272         /**
 273             For empty list \code begin() == end() \endcode
 274         */
 275         iterator begin()
 276         {
 277             return iterator(m_pHead.load(memory_model::memory_order_relaxed) );
 278         }
 279
 280         /// Returns an iterator that addresses the location succeeding the last element in a list
 281         /**
 282             Do not use the value returned by <tt>end</tt> function to access any item.
 283             Internally, <tt>end</tt> returning value equals to \p nullptr.
 284
 285             The returned value can be used only to control reaching the end of the list.
 286             For empty list \code begin() == end() \endcode
 287         */
 288         iterator end()
 289         {
 290             return iterator();
 291         }
 292
 293         /// Returns a forward const iterator addressing the first element in a list
 294         const_iterator begin() const
 295         {
 296             return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
 297         }
 298         /// Returns a forward const iterator addressing the first element in a list
 299         const_iterator cbegin() const
 300         {
 301             return const_iterator(m_pHead.load(memory_model::memory_order_relaxed) );
 302         }
 303
 304         /// Returns an const iterator that addresses the location succeeding the last element in a list
 305         const_iterator end() const
 306         {
 307             return const_iterator();
 308         }
 309         /// Returns an const iterator that addresses the location succeeding the last element in a list
 310         const_iterator cend() const
 311         {
 312             return const_iterator();
 313         }
 314
 315     public:
 316         /// Default constructor initializes empty list
 317         MichaelList()
 318             : m_pHead( nullptr )
 319         {}
 320
 321         //@cond
 322         template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
 323         explicit MichaelList( Stat& st )
 324             : m_pHead( nullptr )
 325             , m_Stat( st )
 326         {}
 327         //@endcond
 328
 329         /// Destroys the list objects
 330         ~MichaelList()
 331         {
 332             clear();
 333         }
 334
 335         /// Inserts new node
 336         /**
 337             The function inserts \p val in the list if the list does not contain
 338             an item with key equal to \p val.
 339
 340             Returns \p true if \p val is linked into the list, \p false otherwise.
 341         */
 342         bool insert( value_type& val )
 343         {
 344             return insert_at( m_pHead, val );
 345         }
 346
 347         /// Updates the item
 348         /**
 349             The operation performs inserting or changing data with lock-free manner.
 350
 351             If the item \p val not found in the list, then \p val is inserted into the list
 352             iff \p bAllowInsert is \p true.
 353             Otherwise, the functor \p func is called with item found.
 354             The functor signature is:
 355             \code
 356             struct functor {
 357                 void operator()( bool bNew, value_type& item, value_type& val );
 358             };
 359             \endcode
 360             with arguments:
 361             - \p bNew - \p true if the item has been inserted, \p false otherwise
 362             - \p item - item of the list
 363             - \p val - argument \p val passed into the \p update() function
 364             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 365             refer to the same thing.
 366
 367             The functor may change non-key fields of the \p item; however, \p func must guarantee
 368             that during changing no any other modifications could be made on this item by concurrent threads.
 369
 370             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successful,
 371             \p second is \p true if new item has been added or \p false if the item with \p key
 372             already is in the list.
 373         */
 374         template <typename Func>
 375         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 376         {
 377             return update_at( m_pHead, val, func, bAllowInsert );
 378         }
 379         //@cond
 380         template <typename Func>
 381         CDS_DEPRECATED("ensure() is deprecated, use update()")
 382         std::pair<bool, bool> ensure( value_type& val, Func func )
 383         {
 384             return update( val, func );
 385         }
 386         //@endcond
 387
 388         /// Finds the key \p val
 389         /** \anchor cds_intrusive_MichaelList_nogc_find_func
 390             The function searches the item with key equal to \p key
 391             and calls the functor \p f for item found.
 392             The interface of \p Func functor is:
 393             \code
 394             struct functor {
 395                 void operator()( value_type& item, Q& key );
 396             };
 397             \endcode
 398             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 399
 400             The functor can change non-key fields of \p item.
 401             The function \p find does not serialize simultaneous access to the list \p item. If such access is
 402             possible you must provide your own synchronization schema to exclude unsafe item modifications.
 403
 404             The function returns \p true if \p val is found, \p false otherwise.
 405         */
 406         template <typename Q, typename Func>
 407         bool find( Q& key, Func f )
 408         {
 409             return find_at( m_pHead, key, key_comparator(), f );
 410         }
 411         //@cond
 412         template <typename Q, typename Func>
 413         bool find( Q const& key, Func f )
 414         {
 415             return find_at( m_pHead, key, key_comparator(), f );
 416         }
 417         //@endcond
 418
 419         /// Finds the key \p key using \p pred predicate for searching
 420         /**
 421             The function is an analog of \ref cds_intrusive_MichaelList_nogc_find_func "find(Q&, Func)"
 422             but \p pred is used for key comparing.
 423             \p Less functor has the interface like \p std::less.
 424             \p pred must imply the same element order as the comparator used for building the list.
 425         */
 426         template <typename Q, typename Less, typename Func>
 427         bool find_with( Q& key, Less pred, Func f )
 428         {
 429             CDS_UNUSED( pred );
 430             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 431         }
 432         //@cond
 433         template <typename Q, typename Less, typename Func>
 434         bool find_with( Q const& key, Less pred, Func f )
 435         {
 436             CDS_UNUSED( pred );
 437             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 438         }
 439         //@endcond
 440
 441         /// Checks whether the list contains \p key
 442         /**
 443             The function searches the item with key equal to \p key
 444             and returns \p true if it is found, and \p false otherwise.
 445         */
 446         template <typename Q>
 447         value_type * contains( Q const& key )
 448         {
 449             return find_at( m_pHead, key, key_comparator() );
 450         }
 451         //@cond
 452         template <typename Q>
 453         CDS_DEPRECATED("deprecated, use contains()")
 454         value_type * find( Q const& key )
 455         {
 456             return contains( key );
 457         }
 458         //@endcond
 459
 460         /// Checks whether the map contains \p key using \p pred predicate for searching
 461         /**
 462             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 463             \p Less functor has the interface like \p std::less.
 464             \p Less must imply the same element order as the comparator used for building the list.
 465         */
 466         template <typename Q, typename Less>
 467         value_type * contains( Q const& key, Less pred )
 468         {
 469             CDS_UNUSED( pred );
 470             return find_at( m_pHead, key, cds::opt::details::make_comparator_from_less<Less>());
 471         }
 472         //@cond
 473         template <typename Q, typename Less>
 474         CDS_DEPRECATED("deprecated, use contains()")
 475         value_type * find_with( Q const& key, Less pred )
 476         {
 477             return contains( key, pred );
 478         }
 479         //@endcond
 480
 481         /// Clears the list
 482         /**
 483             The function unlink all items from the list.
 484
 485             For each unlinked item the item disposer \p disp is called after unlinking.
 486         */
 487         template <typename Disposer>
 488         void clear( Disposer disp )
 489         {
 490             node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
 491             do {} while ( cds_unlikely( !m_pHead.compare_exchange_weak( pHead, nullptr, memory_model::memory_order_relaxed )));
 492
 493             while ( pHead ) {
 494                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 495                 dispose_node( pHead, disp );
 496                 pHead = p;
 497                 --m_ItemCounter;
 498             }
 499         }
 500
 501         /// Clears the list using default disposer
 502         /**
 503             The function clears the list using default (provided in class template) disposer functor.
 504         */
 505         void clear()
 506         {
 507             clear( disposer() );
 508         }
 509
 510         /// Checks if the list is empty
 511         bool empty() const
 512         {
 513             return m_pHead.load( memory_model::memory_order_relaxed ) == nullptr;
 514         }
 515
 516         /// Returns list's item count
 517         /**
 518             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 519             this function always returns 0.
 520
 521             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 522             is empty. To check list emptyness use \p empty() method.
 523         */
 524         size_t size() const
 525         {
 526             return m_ItemCounter.value();
 527         }
 528
 529         /// Returns const reference to internal statistics
 530         stat const& statistics() const
 531         {
 532             return m_Stat;
 533         }
 534
 535     protected:
 536         //@cond
 537         // split-list support
 538         bool insert_aux_node( node_type * pNode )
 539         {
 540             return insert_aux_node( m_pHead, pNode );
 541         }
 542
 543         // split-list support
 544         bool insert_aux_node( atomic_node_ptr& refHead, node_type * pNode )
 545         {
 546             assert( pNode != nullptr );
 547
 548             // Hack: convert node_type to value_type.
 549             // In principle, auxiliary node can be non-reducible to value_type
 550             // We assume that comparator can correctly distinguish aux and regular node.
 551             return insert_at( refHead, *node_traits::to_value_ptr( pNode ) );
 552         }
 553
 554         bool insert_at( atomic_node_ptr& refHead, value_type& val )
 555         {
 556             position pos;
 557
 558             while ( true ) {
 559                 if ( search( refHead, val, key_comparator(), pos )) {
 560                     m_Stat.onInsertFailed();
 561                     return false;
 562                 }
 563
 564                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 565                     ++m_ItemCounter;
 566                     m_Stat.onInsertSuccess();
 567                     return true;
 568                 }
 569
 570                 m_Stat.onInsertRetry();
 571             }
 572         }
 573
 574         iterator insert_at_( atomic_node_ptr& refHead, value_type& val )
 575         {
 576             if ( insert_at( refHead, val ))
 577                 return iterator( node_traits::to_node_ptr( val ));
 578             return end();
 579         }
 580
 581         template <typename Func>
 582         std::pair<iterator, bool> update_at_( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
 583         {
 584             position pos;
 585
 586             while ( true ) {
 587                 if ( search( refHead, val, key_comparator(), pos ) ) {
 588                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 589
 590                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 591                     m_Stat.onUpdateExisting();
 592                     return std::make_pair( iterator( pos.pCur ), false );
 593                 }
 594                 else {
 595                     if ( !bAllowInsert ) {
 596                         m_Stat.onUpdateFailed();
 597                         return std::make_pair( end(), false );
 598                     }
 599
 600                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
 601                         ++m_ItemCounter;
 602                         func( true, val , val );
 603                         m_Stat.onUpdateNew();
 604                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 605                     }
 606                 }
 607
 608                 m_Stat.onUpdateRetry();
 609             }
 610         }
 611
 612         template <typename Func>
 613         std::pair<bool, bool> update_at( atomic_node_ptr& refHead, value_type& val, Func func, bool bAllowInsert )
 614         {
 615             std::pair<iterator, bool> ret = update_at_( refHead, val, func, bAllowInsert );
 616             return std::make_pair( ret.first != end(), ret.second );
 617         }
 618
 619         template <typename Q, typename Compare, typename Func>
 620         bool find_at( atomic_node_ptr& refHead, Q& val, Compare cmp, Func f )
 621         {
 622             position pos;
 623
 624             if ( search( refHead, val, cmp, pos ) ) {
 625                 assert( pos.pCur != nullptr );
 626                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
 627                 m_Stat.onFindSuccess();
 628                 return true;
 629             }
 630
 631             m_Stat.onFindFailed();
 632             return false;
 633         }
 634
 635         template <typename Q, typename Compare>
 636         value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 637         {
 638             iterator it = find_at_( refHead, val, cmp );
 639             if ( it != end() ) {
 640                 m_Stat.onFindSuccess();
 641                 return &*it;
 642             }
 643
 644             m_Stat.onFindFailed();
 645             return nullptr;
 646         }
 647
 648         template <typename Q, typename Compare>
 649         iterator find_at_( atomic_node_ptr& refHead, Q const& val, Compare cmp )
 650         {
 651             position pos;
 652
 653             if ( search( refHead, val, cmp, pos ) ) {
 654                 assert( pos.pCur != nullptr );
 655                 m_Stat.onFindSuccess();
 656                 return iterator( pos.pCur );
 657             }
 658
 659             m_Stat.onFindFailed();
 660             return end();
 661         }
 662
 663         //@endcond
 664
 665     protected:
 666
 667         //@cond
 668         template <typename Q, typename Compare >
 669         bool search( atomic_node_ptr& refHead, const Q& val, Compare cmp, position& pos )
 670         {
 671             atomic_node_ptr * pPrev;
 672             node_type * pNext;
 673             node_type * pCur;
 674
 675             back_off        bkoff;
 676
 677         try_again:
 678             pPrev = &refHead;
 679             pCur = pPrev->load(memory_model::memory_order_acquire);
 680             pNext = nullptr;
 681
 682             while ( true ) {
 683                 if ( !pCur ) {
 684                     pos.pPrev = pPrev;
 685                     pos.pCur = pCur;
 686                     pos.pNext = pNext;
 687                     return false;
 688                 }
 689
 690                 pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
 691                 if ( cds_unlikely( pCur->m_pNext.load(memory_model::memory_order_acquire) != pNext )) {
 692                     bkoff();
 693                     goto try_again;
 694                 }
 695
 696                 if ( cds_unlikely( pPrev->load(memory_model::memory_order_acquire) != pCur )) {
 697                     bkoff();
 698                     goto try_again;
 699                 }
 700
 701                 assert( pCur != nullptr );
 702                 int nCmp = cmp( *node_traits::to_value_ptr( *pCur ), val );
 703                 if ( nCmp >= 0 ) {
 704                     pos.pPrev = pPrev;
 705                     pos.pCur = pCur;
 706                     pos.pNext = pNext;
 707                     return nCmp == 0;
 708                 }
 709                 pPrev = &( pCur->m_pNext );
 710                 pCur = pNext;
 711             }
 712         }
 713
 714         // for split-list
 715         template <typename Predicate>
 716         void erase_for( Predicate pred )
 717         {
 718             node_type * pPred = nullptr;
 719             node_type * pHead = m_pHead.load( memory_model::memory_order_relaxed );
 720             while ( pHead ) {
 721                 node_type * p = pHead->m_pNext.load( memory_model::memory_order_relaxed );
 722                 if ( pred( *node_traits::to_value_ptr( pHead ))) {
 723                     assert( pPred != nullptr );
 724                     pPred->m_pNext.store( p, memory_model::memory_order_relaxed );
 725                     dispose_node( pHead, disposer());
 726                 }
 727                 else
 728                     pPred = pHead;
 729                 pHead = p;
 730             }
 731         }
 732         //@endcond
 733     };
 734
 735 }}  // namespace cds::intrusive
 736
 737 #endif  // #ifndef CDSLIB_INTRUSIVE_MICHAEL_LIST_NOGC_H