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             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur );
 205
 206             pNode->m_pNext.store( pCur, memory_model::memory_order_release );
 207             pPred->m_pNext.store( pNode, memory_model::memory_order_release );
 208         }
 209         //@endcond
 210
 211     protected:
 212         //@cond
 213         template <bool IsConst>
 214         class iterator_type
 215         {
 216             friend class LazyList;
 217
 218         protected:
 219             value_type * m_pNode;
 220
 221             void next()
 222             {
 223                 assert( m_pNode != nullptr );
 224
 225                 node_type * pNode = node_traits::to_node_ptr( m_pNode );
 226                 node_type * pNext = pNode->m_pNext.load(memory_model::memory_order_relaxed);
 227                 if ( pNext != nullptr )
 228                     m_pNode = node_traits::to_value_ptr( pNext );
 229             }
 230
 231             iterator_type( node_type * pNode )
 232             {
 233                 m_pNode = node_traits::to_value_ptr( pNode );
 234             }
 235
 236         public:
 237             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 238             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 239
 240             iterator_type()
 241                 : m_pNode( nullptr )
 242             {}
 243
 244             iterator_type( const iterator_type& src )
 245                 : m_pNode( src.m_pNode )
 246             {}
 247
 248             value_ptr operator ->() const
 249             {
 250                 return m_pNode;
 251             }
 252
 253             value_ref operator *() const
 254             {
 255                 assert( m_pNode != nullptr );
 256                 return *m_pNode;
 257             }
 258
 259             /// Pre-increment
 260             iterator_type& operator ++()
 261             {
 262                 next();
 263                 return *this;
 264             }
 265
 266             /// Post-increment
 267             iterator_type operator ++(int)
 268             {
 269                 iterator_type i(*this);
 270                 next();
 271                 return i;
 272             }
 273
 274             iterator_type& operator = (const iterator_type& src)
 275             {
 276                 m_pNode = src.m_pNode;
 277                 return *this;
 278             }
 279
 280             template <bool C>
 281             bool operator ==(iterator_type<C> const& i ) const
 282             {
 283                 return m_pNode == i.m_pNode;
 284             }
 285             template <bool C>
 286             bool operator !=(iterator_type<C> const& i ) const
 287             {
 288                 return m_pNode != i.m_pNode;
 289             }
 290         };
 291         //@endcond
 292
 293     public:
 294         /// Forward iterator
 295         typedef iterator_type<false>    iterator;
 296         /// Const forward iterator
 297         typedef iterator_type<true>     const_iterator;
 298
 299         /// Returns a forward iterator addressing the first element in a list
 300         /**
 301             For empty list \code begin() == end() \endcode
 302         */
 303         iterator begin()
 304         {
 305             iterator it( &m_Head );
 306             ++it        ;   // skip dummy head
 307             return it;
 308         }
 309
 310         /// Returns an iterator that addresses the location succeeding the last element in a list
 311         /**
 312             Do not use the value returned by <tt>end</tt> function to access any item.
 313
 314             The returned value can be used only to control reaching the end of the list.
 315             For empty list \code begin() == end() \endcode
 316         */
 317         iterator end()
 318         {
 319             return iterator( &m_Tail );
 320         }
 321
 322         /// Returns a forward const iterator addressing the first element in a list
 323         const_iterator begin() const
 324         {
 325             return cbegin();
 326         }
 327         /// Returns a forward const iterator addressing the first element in a list
 328         const_iterator cbegin() const
 329         {
 330             const_iterator it( const_cast<node_type *>(&m_Head) );
 331             ++it;   // skip dummy head
 332             return it;
 333         }
 334
 335         /// Returns an const iterator that addresses the location succeeding the last element in a list
 336         const_iterator end() const
 337         {
 338             return cend();
 339         }
 340         /// Returns an const iterator that addresses the location succeeding the last element in a list
 341         const_iterator cend() const
 342         {
 343             return const_iterator( const_cast<node_type *>(&m_Tail) );
 344         }
 345
 346     public:
 347         /// Default constructor initializes empty list
 348         LazyList()
 349         {
 350             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 351             m_Head.m_pNext.store( &m_Tail, memory_model::memory_order_relaxed );
 352         }
 353
 354         /// Destroys the list object
 355         ~LazyList()
 356         {
 357             clear();
 358             assert( m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail );
 359             m_Head.m_pNext.store( nullptr, memory_model::memory_order_relaxed );
 360         }
 361
 362         /// Inserts new node
 363         /**
 364             The function inserts \p val in the list if the list does not contain
 365             an item with key equal to \p val.
 366
 367             Returns \p true if \p val is linked into the list, \p false otherwise.
 368         */
 369         bool insert( value_type& val )
 370         {
 371             return insert_at( &m_Head, val );
 372         }
 373
 374         /// Updates the item
 375         /**
 376             The operation performs inserting or changing data with lock-free manner.
 377
 378             If the item \p val not found in the list, then \p val is inserted into the list
 379             iff \p bAllowInsert is \p true.
 380             Otherwise, the functor \p func is called with item found.
 381             The functor signature is:
 382             \code
 383             struct functor {
 384                 void operator()( bool bNew, value_type& item, value_type& val );
 385             };
 386             \endcode
 387             with arguments:
 388             - \p bNew - \p true if the item has been inserted, \p false otherwise
 389             - \p item - item of the list
 390             - \p val - argument \p val passed into the \p update() function
 391             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 392             refer to the same thing.
 393
 394             The functor may change non-key fields of the \p item.
 395             While the functor \p f is calling the item \p item is locked.
 396
 397             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successfull,
 398             \p second is \p true if new item has been added or \p false if the item with \p key
 399             already is in the list.
 400         */
 401         template <typename Func>
 402         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 403         {
 404             return update_at( &m_Head, val, func, bAllowInsert );
 405         }
 406         //@cond
 407         template <typename Func>
 408         CDS_DEPRECATED("ensure() is deprecated, use update()")
 409         std::pair<bool, bool> ensure( value_type& val, Func func )
 410         {
 411             return update( val, func, true );
 412         }
 413         //@endcond
 414
 415         /// Finds the key \p key
 416         /** \anchor cds_intrusive_LazyList_nogc_find_func
 417             The function searches the item with key equal to \p key
 418             and calls the functor \p f for item found.
 419             The interface of \p Func functor is:
 420             \code
 421             struct functor {
 422                 void operator()( value_type& item, Q& key );
 423             };
 424             \endcode
 425             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 426
 427             The functor may change non-key fields of \p item.
 428             While the functor \p f is calling the item found \p item is locked.
 429
 430             The function returns \p true if \p key is found, \p false otherwise.
 431         */
 432         template <typename Q, typename Func>
 433         bool find( Q& key, Func f )
 434         {
 435             return find_at( &m_Head, key, key_comparator(), f );
 436         }
 437         //@cond
 438         template <typename Q, typename Func>
 439         bool find( Q const& key, Func f )
 440         {
 441             return find_at( &m_Head, key, key_comparator(), f );
 442         }
 443         //@endcond
 444
 445         /// Finds the key \p key using \p less predicate for searching. Disabled for unordered lists.
 446         /**
 447             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 448             but \p pred is used for key comparing.
 449             \p Less functor has the interface like \p std::less.
 450             \p pred must imply the same element order as the comparator used for building the list.
 451         */
 452         template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
 453         typename std::enable_if<Sort, bool>::type find_with( Q& key, Less less, Func f )
 454         {
 455             CDS_UNUSED( less );
 456             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 457         }
 458
 459         /// Finds the key \p key using \p equal predicate for searching. Disabled for ordered lists.
 460         /**
 461             The function is an analog of \ref cds_intrusive_LazyList_nogc_find_func "find(Q&, Func)"
 462             but \p equal is used for key comparing.
 463             \p Equal functor has the interface like \p std::equal_to.
 464         */
 465         template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
 466         typename std::enable_if<!Sort, bool>::type find_with( Q& key, Equal equal, Func f )
 467         {
 468             CDS_UNUSED( equal );
 469             return find_at( &m_Head, key, equal, f );
 470         }
 471         //@cond
 472         template <typename Q, typename Less, typename Func, bool Sort = c_bSort>
 473         typename std::enable_if<Sort, bool>::type find_with( Q const& key, Less pred, Func f )
 474         {
 475             CDS_UNUSED( pred );
 476             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 477         }
 478
 479         template <typename Q, typename Equal, typename Func, bool Sort = c_bSort>
 480         typename std::enable_if<!Sort, bool>::type find_with( Q const& key, Equal equal, Func f )
 481         {
 482             CDS_UNUSED( equal );
 483             return find_at( &m_Head, key, equal, f );
 484         }
 485         //@endcond
 486
 487         /// Checks whether the list contains \p key
 488         /**
 489             The function searches the item with key equal to \p key
 490             and returns \p true if it is found, and \p false otherwise.
 491         */
 492         template <typename Q>
 493         value_type * contains( Q const& key )
 494         {
 495             return find_at( &m_Head, key, key_comparator() );
 496         }
 497         //@cond
 498         template <typename Q>
 499         CDS_DEPRECATED("deprecated, use contains()")
 500         value_type * find( Q const& key )
 501         {
 502             return contains( key );
 503         }
 504         //@endcond
 505
 506         /// Checks whether the map contains \p key using \p pred predicate for searching (ordered list version)
 507         /**
 508             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 509             \p Less functor has the interface like \p std::less.
 510             \p Less must imply the same element order as the comparator used for building the list.
 511         */
 512         template <typename Q, typename Less, bool Sort = c_bSort>
 513         typename std::enable_if<Sort, value_type *>::type contains( Q const& key, Less pred )
 514         {
 515             CDS_UNUSED( pred );
 516             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 517         }
 518         //@cond
 519         template <typename Q, typename Less, bool Sort = c_bSort>
 520         CDS_DEPRECATED("deprecated, use contains()")
 521         typename std::enable_if<Sort, value_type *>::type find_with( Q const& key, Less pred )
 522         {
 523             return contains( key, pred );
 524         }
 525         //@endcond
 526
 527         /// Checks whether the map contains \p key using \p equal predicate for searching (unordered list version)
 528         /**
 529             The function is an analog of <tt>contains( key )</tt> but \p equal is used for key comparing.
 530             \p Equal functor has the interface like \p std::equal_to.
 531         */
 532         template <typename Q, typename Equal, bool Sort = c_bSort>
 533         typename std::enable_if<!Sort, value_type *>::type contains( Q const& key, Equal equal )
 534         {
 535             return find_at( &m_Head, key, equal );
 536         }
 537         //@cond
 538         template <typename Q, typename Equal, bool Sort = c_bSort>
 539         CDS_DEPRECATED("deprecated, use contains()")
 540         typename std::enable_if<!Sort, value_type *>::type find_with( Q const& key, Equal equal )
 541         {
 542             return contains( key, equal );
 543         }
 544         //@endcond
 545
 546         /// Clears the list
 547         /**
 548             The function unlink all items from the list.
 549             For each unlinked item the item disposer \p disp is called after unlinking.
 550
 551             This function is not thread-safe.
 552         */
 553         template <typename Disposer>
 554         void clear( Disposer disp )
 555         {
 556             node_type * pHead = m_Head.m_pNext.exchange( &m_Tail, memory_model::memory_order_release );
 557
 558             while ( pHead != &m_Tail ) {
 559                 node_type * p = pHead->m_pNext.load(memory_model::memory_order_relaxed);
 560                 dispose_node( pHead, disp );
 561                 pHead = p;
 562             }
 563         }
 564
 565         /// Clears the list using default disposer
 566         /**
 567             The function clears the list using default (provided in class template) disposer functor.
 568         */
 569         void clear()
 570         {
 571             clear( disposer() );
 572         }
 573
 574         /// Checks if the list is empty
 575         bool empty() const
 576         {
 577             return m_Head.m_pNext.load(memory_model::memory_order_relaxed) == &m_Tail;
 578         }
 579
 580         /// Returns list's item count
 581         /**
 582             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 583             this function always returns 0.
 584
 585             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 586             is empty. To check list emptyness use \ref empty() method.
 587         */
 588         size_t size() const
 589         {
 590             return m_ItemCounter.value();
 591         }
 592
 593     protected:
 594         //@cond
 595         // split-list support
 596         bool insert_aux_node( node_type * pNode )
 597         {
 598             return insert_aux_node( &m_Head, pNode );
 599         }
 600
 601         // split-list support
 602         bool insert_aux_node( node_type * pHead, node_type * pNode )
 603         {
 604             assert( pHead != nullptr );
 605             assert( pNode != nullptr );
 606
 607             // Hack: convert node_type to value_type.
 608             // In principle, auxiliary node can be non-reducible to value_type
 609             // We assume that comparator can correctly distinguish aux and regular node.
 610             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 611         }
 612
 613         bool insert_at( node_type * pHead, value_type& val )
 614         {
 615             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 616             position pos;
 617             key_comparator pred;
 618
 619             while ( true ) {
 620                 search( pHead, val, pos, pred );
 621                 {
 622                     auto_lock_position alp( pos );
 623                     if ( validate( pos.pPred, pos.pCur )) {
 624                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) ) {
 625                             // failed: key already in list
 626                             return false;
 627                         }
 628                         else {
 629                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 630                             ++m_ItemCounter;
 631                             return true;
 632                         }
 633                     }
 634                 }
 635             }
 636         }
 637
 638         iterator insert_at_( node_type * pHead, value_type& val )
 639         {
 640             if ( insert_at( pHead, val ))
 641                 return iterator( node_traits::to_node_ptr( val ));
 642             return end();
 643         }
 644
 645
 646         template <typename Func>
 647         std::pair<iterator, bool> update_at_( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 648         {
 649             position pos;
 650             key_comparator pred;
 651
 652             while ( true ) {
 653                 search( pHead, val, pos, pred );
 654                 {
 655                     auto_lock_position alp( pos );
 656                     if ( validate( pos.pPred, pos.pCur )) {
 657                         if ( pos.pCur != &m_Tail && equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred )) {
 658                             // key already in the list
 659
 660                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 661                             return std::make_pair( iterator( pos.pCur ), false );
 662                         }
 663                         else {
 664                             // new key
 665                             if ( !bAllowInsert )
 666                                 return std::make_pair( end(), false );
 667
 668                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 669
 670                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 671                             func( true, val, val );
 672                             ++m_ItemCounter;
 673                             return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
 674                         }
 675                     }
 676                 }
 677             }
 678         }
 679
 680         template <typename Func>
 681         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 682         {
 683             std::pair<iterator, bool> ret = update_at_( pHead, val, func, bAllowInsert );
 684             return std::make_pair( ret.first != end(), ret.second );
 685         }
 686
 687         template <typename Q, typename Pred, typename Func>
 688         bool find_at( node_type * pHead, Q& val, Pred pred, Func f )
 689         {
 690             position pos;
 691
 692             search( pHead, val, pos, pred );
 693             if ( pos.pCur != &m_Tail ) {
 694                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
 695                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ) )
 696                 {
 697                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
 698                     return true;
 699                 }
 700             }
 701             return false;
 702         }
 703
 704         template <typename Q, typename Pred>
 705         value_type * find_at( node_type * pHead, Q& val, Pred pred)
 706         {
 707             iterator it = find_at_( pHead, val, pred );
 708             if ( it != end() )
 709                 return &*it;
 710             return nullptr;
 711         }
 712
 713         template <typename Q, typename Pred>
 714         iterator find_at_( node_type * pHead, Q& val, Pred pred)
 715         {
 716             position pos;
 717
 718             search( pHead, val, pos, pred );
 719             if ( pos.pCur != &m_Tail ) {
 720                 if ( equal( *node_traits::to_value_ptr( *pos.pCur ), val, pred ))
 721                     return iterator( pos.pCur );
 722             }
 723             return end();
 724         }
 725
 726         //@endcond
 727
 728     protected:
 729         //@cond
 730         template <typename Q, typename Equal, bool Sort = c_bSort>
 731         typename std::enable_if<!Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Equal eq )
 732         {
 733             const node_type * pTail = &m_Tail;
 734
 735             node_type * pCur = pHead;
 736             node_type * pPrev = pHead;
 737
 738             while ( pCur != pTail && ( pCur == pHead || !equal( *node_traits::to_value_ptr( *pCur ), key, eq ) )) {
 739                 pPrev = pCur;
 740                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 741             }
 742
 743             pos.pCur = pCur;
 744             pos.pPred = pPrev;
 745         }
 746
 747         template <typename Q, typename Compare, bool Sort = c_bSort>
 748         typename std::enable_if<Sort, void>::type search( node_type * pHead, const Q& key, position& pos, Compare cmp )
 749         {
 750             const node_type * pTail = &m_Tail;
 751
 752             node_type * pCur = pHead;
 753             node_type * pPrev = pHead;
 754
 755             while ( pCur != pTail && ( pCur == pHead || cmp( *node_traits::to_value_ptr( *pCur ), key ) < 0 )) {
 756                 pPrev = pCur;
 757                 pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
 758             }
 759
 760             pos.pCur = pCur;
 761             pos.pPred = pPrev;
 762         }
 763
 764         template <typename L, typename R, typename Equal, bool Sort = c_bSort>
 765         static typename std::enable_if<!Sort, bool>::type equal( L const& l, R const& r, Equal eq )
 766         {
 767             return eq(l, r);
 768         }
 769
 770         template <typename L, typename R, typename Compare, bool Sort = c_bSort>
 771         static typename std::enable_if<Sort, bool>::type equal( L const& l, R const& r, Compare cmp )
 772         {
 773             return cmp(l, r) == 0;
 774         }
 775
 776         static bool validate( node_type * pPred, node_type * pCur )
 777         {
 778             return pPred->m_pNext.load(memory_model::memory_order_acquire) == pCur;
 779         }
 780
 781         //@endcond
 782     };
 783
 784 }}  // namespace cds::intrusive
 785
 786 #endif  // #ifndef CDSLIB_INTRUSIVE_LAZY_LIST_NOGC_H