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