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