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