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