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