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         /// Updates the item
 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             iff \p bAllowInsert is \p true.
 352             Otherwise, the functor \p func is called with item found.
 353             The functor signature is:
 354             \code
 355             struct functor {
 356                 void operator()( bool bNew, value_type& item, value_type& val );
 357             };
 358             \endcode
 359             with arguments:
 360             - \p bNew - \p true if the item has been inserted, \p false otherwise
 361             - \p item - item of the list
 362             - \p val - argument \p val passed into the \p update() function
 363             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 364             refer to the same thing.
 365
 366             The functor may change non-key fields of the \p item.
 367             While the functor \p f is calling the item \p item is locked.
 368
 369             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successfull,
 370             \p second is \p true if new item has been added or \p false if the item with \p key
 371             already is in the list.
 372         */
 373         template <typename Func>
 374         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 375         {
 376             return update_at( &m_Head, val, func, bAllowInsert );
 377         }
 378         //@cond
 379         // Deprecated, use update()
 380         template <typename Func>
 381         std::pair<bool, bool> ensure( value_type& val, Func func )
 382         {
 383             return update( val, func, true );
 384         }
 385         //@endcond
 386
 387         /// Finds the key \p key
 388         /** \anchor cds_intrusive_LazyList_nogc_find_func
 389             The function searches the item with key equal to \p key
 390             and calls the functor \p f for item found.
 391             The interface of \p Func functor is:
 392             \code
 393             struct functor {
 394                 void operator()( value_type& item, Q& key );
 395             };
 396             \endcode
 397             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 398
 399             The functor may change non-key fields of \p item.
 400             While the functor \p f is calling the item found \p item is locked.
 401
 402             The function returns \p true if \p key is found, \p false otherwise.
 403         */
 404         template <typename Q, typename Func>
 405         bool find( Q& key, Func f )
 406         {
 407             return find_at( &m_Head, key, key_comparator(), f );
 408         }
 409         //@cond
 410         template <typename Q, typename Func>
 411         bool find( Q const& key, Func f )
 412         {
 413             return find_at( &m_Head, key, key_comparator(), f );
 414         }
 415         //@endcond
 416
 417         /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
 418         /**
 419             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 420             but \p pred is used for key comparing.
 421             \p Less functor has the interface like \p std::less.
 422             \p pred must imply the same element order as the comparator used for building the list.
 423         */
 424         template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
 425         typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
 426         {
 427             CDS_UNUSED( less );
 428             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 429         }
 430
 431         /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
 432         /**
 433             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 434             but \p equal is used for key comparing.
 435             \p Equal functor has the interface like \p std::equal_to.
 436         */
 437         template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
 438         typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal equal, Func f )
 439         {
 440             CDS_UNUSED( equal );
 441             return find_at( &m_Head, key, equal, f );
 442         }
 443         //@cond
 444         template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
 445         typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
 446         {
 447             CDS_UNUSED( pred );
 448             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 449         }
 450
 451         template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
 452         typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal equal, Func f )
 453         {
 454             CDS_UNUSED( equal );
 455             return find_at( &m_Head, key, equal, f );
 456         }
 457         //@endcond
 458
 459         /// Checks whether the list contains \p key
 460         /**
 461             The function searches the item with key equal to \p key
 462             and returns \p true if it is found, and \p false otherwise.
 463         */
 464         template <typename Q>
 465         value_type * contains( Q const& key )
 466         {
 467             return find_at( &m_Head, key, key_comparator() );
 468         }
 469         //@cond
 470         // Deprecated, use contains()
 471         template <typename Q>
 472         value_type * find( Q const& key )
 473         {
 474             return contains( key );
 475         }
 476         //@endcond
 477
 478         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 479         /**
 480             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 481             \p Less functor has the interface like \p std::less.
 482             \p Less must imply the same element order as the comparator used for building the list.
 483         */
 484         template <typename Q, typename Less, bool Sort = c_bSort>
 485         typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
 486         {
 487             CDS_UNUSED( pred );
 488             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 489         }
 490         //@cond
 491         // Deprecated, use contains()
 492         template <typename Q, typename Less, bool Sort = c_bSort>
 493         typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
 494         {
 495             return contains( key, pred );
 496         }
 497         //@endcond
 498
 499         /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
 500         /**
 501             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 502             \p Equal functor has the interface like \p std::equal_to.
 503         */
 504         template <typename Q, typename Equal, bool Sort = c_bSort>
 505         typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal equal )
 506         {
 507             return find_at( &m_Head, key, equal );
 508         }
 509         //@cond
 510         // Deprecated, use contains()
 511         template <typename Q, typename Equal, bool Sort = c_bSort>
 512         typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal equal )
 513         {
 514             return contains( key, equal );
 515         }
 516         //@endcond
 517
 518         /// Clears the list
 519         /**
 520             The function unlink all items from the list.
 521             For each unlinked item the item disposer \p disp is called after unlinking.
 522
 523             This function is not thread-safe.
 524         */
 525         template <typename Disposer>
 526         void clear( Disposer disp )
 527         {
 528             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 529
 530             while ( pHead != &m_Tail ) {
 531                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 532                 dispose_node( pHead, disp );
 533                 pHead = p;
 534             }
 535         }
 536
 537         /// Clears the list using default disposer
 538         /**
 539             The function clears the list using default (provided in class template) disposer functor.
 540         */
 541         void clear()
 542         {
 543             clear( disposer() );
 544         }
 545
 546         /// Checks if the list is empty
 547         bool empty() const
 548         {
 549             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 550         }
 551
 552         /// Returns list's item count
 553         /**
 554             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 555             this function always returns 0.
 556
 557             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 558             is empty. To check list emptyness use \ref empty() method.
 559         */
 560         size_t size() const
 561         {
 562             return m_ItemCounter.value();
 563         }
 564
 565     protected:
 566         //@cond
 567         // split-list support
 568         bool insert_aux_node( node_type * pNode )
 569         {
 570             return insert_aux_node( &m_Head, pNode );
 571         }
 572
 573         // split-list support
 574         bool insert_aux_node( node_type * pHead, node_type * pNode )
 575         {
 576             assert( pHead != nullptr );
 577             assert( pNode != nullptr );
 578
 579             // Hack: convert node_type to value_type.
 580             // In principle, auxiliary node can be non-reducible to value_type
 581             // We assume that comparator can correctly distinguish aux and regular node.
 582             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 583         }
 584
 585         bool insert_at( node_type * pHead, value_type& val )
 586         {
 587             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 588             position pos;
 589             key_comparator pred;
 590
 591             while ( true ) {
 592                 search( pHead, val, pos, pred );
 593                 {
 594                     auto_lock_position alp( pos );
 595                     if ( validate( pos.pPred, pos.pCur )) {
 596                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
 597                             // failed: key already in list
 598                             return false;
 599                         }
 600                         else {
 601                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 602                             ++m_ItemCounter;
 603                             return true;
 604                         }
 605                     }
 606                 }
 607             }
 608         }
 609
 610         iterator insert_at_( node_type * pHead, value_type& val )
 611         {
 612             if ( insert_at( pHead, val ))
 613                 return iterator( node_traits::to_node_ptr( val ));
 614             return end();
 615         }
 616
 617
 618         template <typename Func>
 619         std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 620         {
 621             position pos;
 622             key_comparator pred;
 623
 624             while ( true ) {
 625                 search( pHead, val, pos, pred );
 626                 {
 627                     auto_lock_position alp( pos );
 628                     if ( validate( pos.pPred, pos.pCur )) {
 629                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
 630                             // key already in the list
 631
 632                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 633                             return std::make_pair( iterator( pos.pCur ), false );
 634                         }
 635                         else {
 636                             // new key
 637                             if ( !bAllowInsert )
 638                                 return std::make_pair( end(), false );
 639
 640                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 641
 642                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 643                             func( true, val, val );
 644                             ++m_ItemCounter;
 645                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 646                         }
 647                     }
 648                 }
 649             }
 650         }
 651
 652         template <typename Func>
 653         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 654         {
 655             std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
 656             return std::make_pair( ret.first != end(), ret.second );
 657         }
 658
 659         template <typename Q, typename Pred, typename Func>
 660         bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
 661         {
 662             position pos;
 663
 664             search( pHead, val, pos, pred );
 665             if ( pos.pCur != &m_Tail ) {
 666                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 667                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
 668                 {
 669                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 670                     return true;
 671                 }
 672             }
 673             return false;
 674         }
 675
 676         template <typename Q, typename Pred>
 677         value_type * find_at( node_type * pHead, Q& val, Pred pred)
 678         {
 679             iterator it = find_at_( pHead, val, pred );
 680             if ( it != end() )
 681                 return &*it;
 682             return nullptr;
 683         }
 684
 685         template <typename Q, typename Pred>
 686         iterator find_at_( node_type * pHead, Q& val, Pred pred)
 687         {
 688             position pos;
 689
 690             search( pHead, val, pos, pred );
 691             if ( pos.pCur != &m_Tail ) {
 692                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ))
 693                     return iterator( pos.pCur );
 694             }
 695             return end();
 696         }
 697
 698         //@endcond
 699
 700     protected:
 701         //@cond
 702         template <typename Q, typename Equal, bool Sort = c_bSort>
 703         typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
 704         {
 705             const node_type * pTail = &m_Tail;
 706
 707             node_type * pCur = pHead;
 708             node_type * pPrev = pHead;
 709
 710             while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
 711                 pPrev = pCur;
 712                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 713             }
 714
 715             pos.pCur = pCur;
 716             pos.pPred = pPrev;
 717         }
 718
 719         template <typename Q, typename Compare, bool Sort = c_bSort>
 720         typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 721         {
 722             const node_type * pTail = &m_Tail;
 723
 724             node_type * pCur = pHead;
 725             node_type * pPrev = pHead;
 726
 727             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 728                 pPrev = pCur;
 729                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 730             }
 731
 732             pos.pCur = pCur;
 733             pos.pPred = pPrev;
 734         }
 735
 736         template <typename L, typename R, typename Equal, bool Sort = c_bSort>
 737         static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
 738         {
 739             return eq(l, r);
 740         }
 741
 742         template <typename L, typename R, typename Compare, bool Sort = c_bSort>
 743         static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
 744         {
 745             return cmp(l, r) == 0;
 746         }
 747
 748         static bool validate( node_type * pPred, node_type * pCur )
 749         {
 750             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 751         }
 752
 753         //@endcond
 754     };
 755
 756 }}  // namespace cds::intrusive
 757
 758 #endif  // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H