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