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