cds/intrusive/lazy_list_nogc.h

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