cds/intrusive/impl/lazy_list.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_IMPL_LAZY_LIST_H
  32 #define CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
  33
  34 #include <mutex>        // unique_lock
  35 #include <cds/intrusive/details/lazy_list_base.h>
  36
  37 namespace cds { namespace intrusive {
  38
  39     /// Lazy ordered single-linked list
  40     /** @ingroup cds_intrusive_list
  41         \anchor cds_intrusive_LazyList_hp
  42
  43         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  44         The complexity of searching is <tt>O(N)</tt>.
  45
  46         Source:
  47             - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
  48               "A Lazy Concurrent List-Based Set Algorithm"
  49
  50         The lazy list is based on an optimistic locking scheme for inserts and removes,
  51         eliminating the need to use the equivalent of an atomically markable
  52         reference. It also has a novel wait-free membership \p find operation
  53         that does not need to perform cleanup operations and is more efficient.
  54
  55         Template arguments:
  56         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see lazy_list::node).
  57         - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
  58             or it must have a member of type lazy_list::node (for lazy_list::member_hook).
  59         - \p Traits - type traits. See lazy_list::traits for explanation.
  60             It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction instead of \p Traits template
  61             argument. For example, the following traits-based declaration of \p gc::HP lazy list
  62             \code
  63             #include <cds/intrusive/lazy_list_hp.h>
  64             // Declare item stored in your list
  65             struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
  66             { ... };
  67
  68             // Declare comparator for the item
  69             struct my_compare { ... }
  70
  71             // Declare traits
  72             struct my_traits: public cds::intrusive::lazy_list::traits
  73             {
  74                 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
  75                 typedef my_compare compare;
  76             };
  77
  78             // Declare traits-based list
  79             typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits >     traits_based_list;
  80             \endcode
  81             is equivalent for the following option-based list
  82             \code
  83             #include <cds/intrusive/lazy_list_hp.h>
  84
  85             // item struct and my_compare are the same
  86
  87             // Declare option-based list
  88             typedef cds::intrusive::LazyList< cds::gc::HP, item,
  89                 typename cds::intrusive::lazy_list::make_traits<
  90                     cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > >    // hook option
  91                     ,cds::intrusive::opt::compare< my_compare >     // item comparator option
  92                 >::type
  93             >     option_based_list;
  94             \endcode
  95
  96         \par Usage
  97         There are different specializations of this template for each garbage collecting schema used.
  98         You should select GC needed and include appropriate .h-file:
  99         - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
 100         - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
 101         - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
 102         - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
 103
 104         Then, you should incorporate lazy_list::node into your struct \p T and provide
 105         appropriate \p lazy_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits
 106         a struct based on \p lazy_list::traits should be defined.
 107
 108         Example for gc::DHP and base hook:
 109         \code
 110         // Include GC-related lazy list specialization
 111         #include <cds/intrusive/lazy_list_dhp.h>
 112
 113         // Data stored in lazy list
 114         struct my_data: public cds::intrusive::lazy_list::node< cds::gc::DHP >
 115         {
 116             // key field
 117             std::string     strKey;
 118
 119             // other data
 120             // ...
 121         };
 122
 123         // my_data comparing functor
 124         struct compare {
 125             int operator()( const my_data& d1, const my_data& d2 )
 126             {
 127                 return d1.strKey.compare( d2.strKey );
 128             }
 129
 130             int operator()( const my_data& d, const std::string& s )
 131             {
 132                 return d.strKey.compare(s);
 133             }
 134
 135             int operator()( const std::string& s, const my_data& d )
 136             {
 137                 return s.compare( d.strKey );
 138             }
 139         };
 140
 141         // Declare traits
 142         struct my_traits: public cds::intrusive::lazy_list::traits
 143         {
 144             typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > >   hook;
 145             typedef my_data_cmp compare;
 146         };
 147
 148         // Declare list type
 149         typedef cds::intrusive::LazyList< cds::gc::DHP, my_data, my_traits >     traits_based_list;
 150         \endcode
 151
 152         Equivalent option-based code:
 153         \code
 154         // GC-related specialization
 155         #include <cds/intrusive/lazy_list_dhp.h>
 156
 157         struct my_data {
 158             // see above
 159         };
 160         struct compare {
 161             // see above
 162         };
 163
 164         // Declare option-based list
 165         typedef cds::intrusive::LazyList< cds::gc::DHP
 166             ,my_data
 167             , typename cds::intrusive::lazy_list::make_traits<
 168                 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
 169                 ,cds::intrusive::opt::compare< my_data_cmp >
 170             >::type
 171         > option_based_list;
 172
 173         \endcode
 174     */
 175     template <
 176         class GC
 177         ,typename T
 178 #ifdef CDS_DOXYGEN_INVOKED
 179         ,class Traits = lazy_list::traits
 180 #else
 181         ,class Traits
 182 #endif
 183     >
 184     class LazyList
 185     {
 186     public:
 187         typedef GC     gc;   ///< Garbage collector
 188         typedef T      value_type; ///< type of value stored in the list
 189         typedef Traits traits;     ///< Traits template parameter
 190
 191         typedef typename traits::hook    hook;      ///< hook type
 192         typedef typename hook::node_type node_type; ///< node type
 193
 194 #   ifdef CDS_DOXYGEN_INVOKED
 195         typedef implementation_defined key_comparator;    ///< key comparison functor based on opt::compare and opt::less option setter.
 196 #   else
 197         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 198 #   endif
 199
 200         typedef typename traits::disposer  disposer;   ///< disposer
 201         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
 202         typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
 203
 204         typedef typename traits::back_off     back_off;      ///< back-off strategy
 205         typedef typename traits::item_counter item_counter;  ///< Item counting policy used
 206         typedef typename traits::memory_model memory_model;  ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
 207         typedef typename traits::stat         stat;          ///< Internal statistics
 208
 209         static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
 210
 211         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 212
 213         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
 214
 215         //@cond
 216         // Rebind traits (split-list support)
 217         template <typename... Options>
 218         struct rebind_traits {
 219             typedef LazyList<
 220                 gc
 221                 , value_type
 222                 , typename cds::opt::make_options< traits, Options...>::type
 223             > type;
 224         };
 225         //@endcond
 226
 227     protected:
 228         typedef typename node_type::marked_ptr marked_node_ptr;   ///< Node marked pointer
 229         typedef node_type *     auxiliary_head;   ///< Auxiliary head type (for split-list support)
 230
 231     protected:
 232         //@cond
 233         node_type   m_Head;
 234         node_type   m_Tail;
 235
 236         item_counter    m_ItemCounter;
 237         stat            m_Stat; ///< Internal statistics
 238
 239         struct clean_disposer {
 240             void operator()( value_type * p )
 241             {
 242                 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ));
 243                 disposer()( p );
 244             }
 245         };
 246
 247         /// Position pointer for item search
 248         struct position {
 249             node_type *     pPred; ///< Previous node
 250             node_type *     pCur;  ///< Current node
 251
 252             typename gc::template GuardArray<2> guards; ///< Guards array
 253
 254             enum {
 255                 guard_prev_item,
 256                 guard_current_item
 257             };
 258
 259             /// Locks nodes \p pPred and \p pCur
 260             void lock()
 261             {
 262                 pPred->m_Lock.lock();
 263                 pCur->m_Lock.lock();
 264             }
 265
 266             /// Unlocks nodes \p pPred and \p pCur
 267             void unlock()
 268             {
 269                 pCur->m_Lock.unlock();
 270                 pPred->m_Lock.unlock();
 271             }
 272         };
 273
 274         typedef std::unique_lock< position > scoped_position_lock;
 275         //@endcond
 276
 277     protected:
 278         //@cond
 279         void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
 280         {
 281             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
 282             link_checker::is_empty( pNode );
 283
 284             pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
 285             pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
 286         }
 287
 288         void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
 289         {
 290             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
 291
 292             node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 293             pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release ); // logical removal + back-link for search
 294             pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
 295         }
 296
 297         void retire_node( node_type * pNode )
 298         {
 299             assert( pNode != nullptr );
 300             gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ));
 301         }
 302         //@endcond
 303
 304     protected:
 305         //@cond
 306         template <bool IsConst>
 307         class iterator_type
 308         {
 309             friend class LazyList;
 310
 311         protected:
 312             value_type * m_pNode;
 313             typename gc::Guard  m_Guard;
 314
 315             void next()
 316             {
 317                 assert( m_pNode != nullptr );
 318
 319                 if ( m_pNode ) {
 320                     typename gc::Guard g;
 321                     node_type * pCur = node_traits::to_node_ptr( m_pNode );
 322                     if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) {      // if pCur is not tail node
 323                         node_type * pNext;
 324                         do {
 325                             pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 326                             g.assign( node_traits::to_value_ptr( pNext ));
 327                         } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr());
 328
 329                         m_pNode = m_Guard.assign( g.template get<value_type>());
 330                     }
 331                 }
 332             }
 333
 334             void skip_deleted()
 335             {
 336                 if ( m_pNode != nullptr ) {
 337                     typename gc::Guard g;
 338                     node_type * pNode = node_traits::to_node_ptr( m_pNode );
 339
 340                     // Dummy tail node could not be marked
 341                     while ( pNode->is_marked()) {
 342                         node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 343                         g.assign( node_traits::to_value_ptr( p ));
 344                         if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr())
 345                             pNode = p;
 346                     }
 347                     if ( pNode != node_traits::to_node_ptr( m_pNode ))
 348                         m_pNode = m_Guard.assign( g.template get<value_type>());
 349                 }
 350             }
 351
 352             iterator_type( node_type * pNode )
 353             {
 354                 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
 355                 skip_deleted();
 356             }
 357
 358         public:
 359             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 360             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 361
 362             iterator_type()
 363                 : m_pNode( nullptr )
 364             {}
 365
 366             iterator_type( iterator_type const& src )
 367             {
 368                 if ( src.m_pNode ) {
 369                     m_pNode = m_Guard.assign( src.m_pNode );
 370                 }
 371                 else
 372                     m_pNode = nullptr;
 373             }
 374
 375             value_ptr operator ->() const
 376             {
 377                 return m_pNode;
 378             }
 379
 380             value_ref operator *() const
 381             {
 382                 assert( m_pNode != nullptr );
 383                 return *m_pNode;
 384             }
 385
 386             /// Pre-increment
 387             iterator_type& operator ++()
 388             {
 389                 next();
 390                 skip_deleted();
 391                 return *this;
 392             }
 393
 394             iterator_type& operator = (iterator_type const& src)
 395             {
 396                 m_pNode = src.m_pNode;
 397                 m_Guard.assign( m_pNode );
 398                 return *this;
 399             }
 400
 401             template <bool C>
 402             bool operator ==(iterator_type<C> const& i ) const
 403             {
 404                 return m_pNode == i.m_pNode;
 405             }
 406             template <bool C>
 407             bool operator !=(iterator_type<C> const& i ) const
 408             {
 409                 return m_pNode != i.m_pNode;
 410             }
 411         };
 412         //@endcond
 413
 414     public:
 415     ///@name Forward iterators (only for debugging purpose)
 416     //@{
 417         /// Forward iterator
 418         /**
 419             The forward iterator for lazy list has some features:
 420             - it has no post-increment operator
 421             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 422               For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
 423               may be thrown if a limit of guard count per thread is exceeded.
 424             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 425             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 426               deleting operations it is no guarantee that you iterate all item in the list.
 427               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 428
 429             @warning Use this iterator on the concurrent container for debugging purpose only.
 430         */
 431         typedef iterator_type<false>    iterator;
 432         /// Const forward iterator
 433         /**
 434             For iterator's features and requirements see \ref iterator
 435         */
 436         typedef iterator_type<true>     const_iterator;
 437
 438         /// Returns a forward iterator addressing the first element in a list
 439         /**
 440             For empty list \code begin() == end() \endcode
 441         */
 442         iterator begin()
 443         {
 444             iterator it( &m_Head );
 445             ++it        ;   // skip dummy head
 446             return it;
 447         }
 448
 449         /// Returns an iterator that addresses the location succeeding the last element in a list
 450         /**
 451             Do not use the value returned by <tt>end</tt> function to access any item.
 452
 453             The returned value can be used only to control reaching the end of the list.
 454             For empty list \code begin() == end() \endcode
 455         */
 456         iterator end()
 457         {
 458             return iterator( &m_Tail );
 459         }
 460
 461         /// Returns a forward const iterator addressing the first element in a list
 462         const_iterator begin() const
 463         {
 464             return get_const_begin();
 465         }
 466
 467         /// Returns a forward const iterator addressing the first element in a list
 468         const_iterator cbegin() const
 469         {
 470             return get_const_begin();
 471         }
 472
 473         /// Returns an const iterator that addresses the location succeeding the last element in a list
 474         const_iterator end() const
 475         {
 476             return get_const_end();
 477         }
 478
 479         /// Returns an const iterator that addresses the location succeeding the last element in a list
 480         const_iterator cend() const
 481         {
 482             return get_const_end();
 483         }
 484     //@}
 485
 486     private:
 487         //@cond
 488         const_iterator get_const_begin() const
 489         {
 490             const_iterator it( const_cast<node_type *>( &m_Head ));
 491             ++it        ;   // skip dummy head
 492             return it;
 493         }
 494         const_iterator get_const_end() const
 495         {
 496             return const_iterator( const_cast<node_type *>(&m_Tail));
 497         }
 498         //@endcond
 499
 500     public:
 501         /// Default constructor initializes empty list
 502         LazyList()
 503         {
 504             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
 505         }
 506
 507         //@cond
 508         template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
 509         explicit LazyList( Stat& st )
 510             : m_Stat( st )
 511         {
 512             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
 513         }
 514         //@endcond
 515
 516         /// Destroys the list object
 517         ~LazyList()
 518         {
 519             clear();
 520             assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
 521             m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 522         }
 523
 524         /// Inserts new node
 525         /**
 526             The function inserts \p val in the list if the list does not contain
 527             an item with key equal to \p val.
 528
 529             Returns \p true if \p val is linked into the list, \p false otherwise.
 530         */
 531         bool insert( value_type& val )
 532         {
 533             return insert_at( &m_Head, val );
 534         }
 535
 536         /// Inserts new node
 537         /**
 538             This function is intended for derived non-intrusive containers.
 539
 540             The function allows to split new item creating into two part:
 541             - create item with key only
 542             - insert new item into the list
 543             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 544
 545             The functor signature is:
 546             \code
 547                 void func( value_type& val );
 548             \endcode
 549             where \p val is the item inserted.
 550             While the functor \p f is called the item \p val is locked so
 551             the functor has an exclusive access to the item.
 552             The user-defined functor is called only if the inserting is success.
 553         */
 554         template <typename Func>
 555         bool insert( value_type& val, Func f )
 556         {
 557             return insert_at( &m_Head, val, f );
 558         }
 559
 560         /// Updates the item
 561         /**
 562             The operation performs inserting or changing data with lock-free manner.
 563
 564             If the item \p val not found in the list, then \p val is inserted into the list
 565             iff \p bAllowInsert is \p true.
 566             Otherwise, the functor \p func is called with item found.
 567             The functor signature is:
 568             \code
 569             struct functor {
 570                 void operator()( bool bNew, value_type& item, value_type& val );
 571             };
 572             \endcode
 573             with arguments:
 574             - \p bNew - \p true if the item has been inserted, \p false otherwise
 575             - \p item - item of the list
 576             - \p val - argument \p val passed into the \p update() function
 577             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 578             refer to the same thing.
 579
 580             The functor may change non-key fields of the \p item.
 581             While the functor \p f is working the item \p item is locked,
 582             so \p func has exclusive access to the item.
 583
 584             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successful,
 585             \p second is \p true if new item has been added or \p false if the item with \p key
 586             already is in the list.
 587
 588             The function makes RCU lock internally.
 589         */
 590         template <typename Func>
 591         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 592         {
 593             return update_at( &m_Head, val, func, bAllowInsert );
 594         }
 595         //@cond
 596         template <typename Func>
 597         CDS_DEPRECATED("ensure() is deprecated, use update()")
 598         std::pair<bool, bool> ensure( value_type& val, Func func )
 599         {
 600             return update( val, func, true );
 601         }
 602         //@endcond
 603
 604         /// Unlinks the item \p val from the list
 605         /**
 606             The function searches the item \p val in the list and unlink it from the list
 607             if it is found and it is equal to \p val.
 608
 609             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 610             and deletes the item found. \p unlink finds an item by key and deletes it
 611             only if \p val is an item of that list, i.e. the pointer to item found
 612             is equal to <tt> &val </tt>.
 613
 614             The function returns \p true if success and \p false otherwise.
 615
 616             \p disposer specified in \p Traits is called for unlinked item.
 617         */
 618         bool unlink( value_type& val )
 619         {
 620             return unlink_at( &m_Head, val );
 621         }
 622
 623         /// Deletes the item from the list
 624         /** \anchor cds_intrusive_LazyList_hp_erase_val
 625             The function searches an item with key equal to \p key in the list,
 626             unlinks it from the list, and returns \p true.
 627             If the item with the key equal to \p key is not found the function return \p false.
 628
 629             \p disposer specified in \p Traits is called for deleted item.
 630         */
 631         template <typename Q>
 632         bool erase( Q const& key )
 633         {
 634             return erase_at( &m_Head, key, key_comparator());
 635         }
 636
 637         /// Deletes the item from the list using \p pred predicate for searching
 638         /**
 639             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
 640             but \p pred is used for key comparing.
 641             \p Less functor has the interface like \p std::less.
 642             \p pred must imply the same element order as the comparator used for building the list.
 643
 644             \p disposer specified in \p Traits is called for deleted item.
 645         */
 646         template <typename Q, typename Less>
 647         bool erase_with( Q const& key, Less pred )
 648         {
 649             CDS_UNUSED( pred );
 650             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 651         }
 652
 653         /// Deletes the item from the list
 654         /** \anchor cds_intrusive_LazyList_hp_erase_func
 655             The function searches an item with key equal to \p key in the list,
 656             call \p func functor with item found, unlinks it from the list, and returns \p true.
 657             The \p Func interface is
 658             \code
 659             struct functor {
 660                 void operator()( value_type const& item );
 661             };
 662             \endcode
 663
 664             If \p key is not found the function return \p false.
 665
 666             \p disposer specified in \p Traits is called for deleted item.
 667         */
 668         template <typename Q, typename Func>
 669         bool erase( const Q& key, Func func )
 670         {
 671             return erase_at( &m_Head, key, key_comparator(), func );
 672         }
 673
 674         /// Deletes the item from the list using \p pred predicate for searching
 675         /**
 676             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
 677             but \p pred is used for key comparing.
 678             \p Less functor has the interface like \p std::less.
 679             \p pred must imply the same element order as the comparator used for building the list.
 680
 681             \p disposer specified in \p Traits is called for deleted item.
 682         */
 683         template <typename Q, typename Less, typename Func>
 684         bool erase_with( const Q& key, Less pred, Func func )
 685         {
 686             CDS_UNUSED( pred );
 687             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 688         }
 689
 690         /// Extracts the item from the list with specified \p key
 691         /** \anchor cds_intrusive_LazyList_hp_extract
 692             The function searches an item with key equal to \p key,
 693             unlinks it from the list, and returns it as \p guarded_ptr.
 694             If \p key is not found the function returns an empty guarded pointer.
 695
 696             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 697
 698             The \ref disposer specified in \p Traits class template parameter is called automatically
 699             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
 700             will be destroyed or released.
 701             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 702
 703             Usage:
 704             \code
 705             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 706             ord_list theList;
 707             // ...
 708             {
 709                 ord_list::guarded_ptr gp( theList.extract( 5 ));
 710                 // Deal with gp
 711                 // ...
 712
 713                 // Destructor of gp releases internal HP guard
 714             }
 715             \endcode
 716         */
 717         template <typename Q>
 718         guarded_ptr extract( Q const& key )
 719         {
 720             guarded_ptr gp;
 721             extract_at( &m_Head, gp.guard(), key, key_comparator());
 722             return gp;
 723         }
 724
 725         /// Extracts the item from the list with comparing functor \p pred
 726         /**
 727             The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
 728             but \p pred predicate is used for key comparing.
 729
 730             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 731             in any order.
 732             \p pred must imply the same element order as the comparator used for building the list.
 733         */
 734         template <typename Q, typename Less>
 735         guarded_ptr extract_with( Q const& key, Less pred )
 736         {
 737             CDS_UNUSED( pred );
 738             guarded_ptr gp;
 739             extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
 740             return gp;
 741         }
 742
 743         /// Finds the key \p key
 744         /** \anchor cds_intrusive_LazyList_hp_find
 745             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 746             The interface of \p Func functor is:
 747             \code
 748             struct functor {
 749                 void operator()( value_type& item, Q& key );
 750             };
 751             \endcode
 752             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 753
 754             The functor may change non-key fields of \p item.
 755             While the functor \p f is calling the item \p item is locked.
 756
 757             The function returns \p true if \p key is found, \p false otherwise.
 758         */
 759         template <typename Q, typename Func>
 760         bool find( Q& key, Func f )
 761         {
 762             return find_at( &m_Head, key, key_comparator(), f );
 763         }
 764         //@cond
 765         template <typename Q, typename Func>
 766         bool find( Q const& key, Func f )
 767         {
 768             return find_at( &m_Head, key, key_comparator(), f );
 769         }
 770         //@endcond
 771
 772         /// Finds the key \p key using \p pred predicate for searching
 773         /**
 774             The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
 775             but \p pred is used for key comparing.
 776             \p Less functor has the interface like \p std::less.
 777             \p pred must imply the same element order as the comparator used for building the list.
 778         */
 779         template <typename Q, typename Less, typename Func>
 780         bool find_with( Q& key, Less pred, Func f )
 781         {
 782             CDS_UNUSED( pred );
 783             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 784         }
 785         //@cond
 786         template <typename Q, typename Less, typename Func>
 787         bool find_with( Q const& key, Less pred, Func f )
 788         {
 789             CDS_UNUSED( pred );
 790             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 791         }
 792         //@endcond
 793
 794         /// Checks whether the list contains \p key
 795         /**
 796             The function searches the item with key equal to \p key
 797             and returns \p true if it is found, and \p false otherwise.
 798         */
 799         template <typename Q>
 800         bool contains( Q const& key )
 801         {
 802             return find_at( &m_Head, key, key_comparator());
 803         }
 804         //@cond
 805         template <typename Q>
 806         CDS_DEPRECATED("deprecated, use contains()")
 807         bool find( Q const& key )
 808         {
 809             return contains( key );
 810         }
 811         //@cond
 812
 813         /// Checks whether the map contains \p key using \p pred predicate for searching
 814         /**
 815             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 816             \p Less functor has the interface like \p std::less.
 817             \p Less must imply the same element order as the comparator used for building the list.
 818         */
 819         template <typename Q, typename Less>
 820         bool contains( Q const& key, Less pred )
 821         {
 822             CDS_UNUSED( pred );
 823             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>());
 824         }
 825         //@cond
 826         template <typename Q, typename Less>
 827         CDS_DEPRECATED("deprecated, use contains()")
 828         bool find_with( Q const& key, Less pred )
 829         {
 830             return contains( key, pred );
 831         }
 832         //@endcond
 833
 834         /// Finds \p key and return the item found
 835         /** \anchor cds_intrusive_LazyList_hp_get
 836             The function searches the item with key equal to \p key
 837             and returns an guarded pointer to it.
 838             If \p key is not found the function returns an empty guarded pointer.
 839
 840             The \ref disposer specified in \p Traits class template parameter is called
 841             by garbage collector \p GC automatically when returned \p guarded_ptr object
 842             will be destroyed or released.
 843             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 844
 845             Usage:
 846             \code
 847             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 848             ord_list theList;
 849             // ...
 850             {
 851                 ord_list::guarded_ptr gp(theList.get( 5 ));
 852                 if ( gp ) {
 853                     // Deal with gp
 854                     //...
 855                 }
 856                 // Destructor of guarded_ptr releases internal HP guard
 857             }
 858             \endcode
 859
 860             Note the compare functor specified for class \p Traits template parameter
 861             should accept a parameter of type \p Q that can be not the same as \p value_type.
 862         */
 863         template <typename Q>
 864         guarded_ptr get( Q const& key )
 865         {
 866             guarded_ptr gp;
 867             get_at( &m_Head, gp.guard(), key, key_comparator());
 868             return gp;
 869         }
 870
 871         /// Finds \p key and return the item found
 872         /**
 873             The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
 874             but \p pred is used for comparing the keys.
 875
 876             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 877             in any order.
 878             \p pred must imply the same element order as the comparator used for building the list.
 879         */
 880         template <typename Q, typename Less>
 881         guarded_ptr get_with( Q const& key, Less pred )
 882         {
 883             CDS_UNUSED( pred );
 884             guarded_ptr gp;
 885             get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>());
 886             return gp;
 887         }
 888
 889         /// Clears the list
 890         void clear()
 891         {
 892             typename gc::Guard guard;
 893             marked_node_ptr h;
 894             while ( !empty()) {
 895                 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
 896                 guard.assign( node_traits::to_value_ptr( h.ptr()));
 897                 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
 898                     m_Head.m_Lock.lock();
 899                     h->m_Lock.lock();
 900
 901                     unlink_node( &m_Head, h.ptr(), &m_Head );
 902                     --m_ItemCounter;
 903
 904                     h->m_Lock.unlock();
 905                     m_Head.m_Lock.unlock();
 906
 907                     retire_node( h.ptr()) ; // free node
 908                 }
 909             }
 910         }
 911
 912         /// Checks if the list is empty
 913         bool empty() const
 914         {
 915             return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
 916         }
 917
 918         /// Returns list's item count
 919         /**
 920             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 921             this function always returns 0.
 922
 923             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 924             is empty. To check list emptiness use \p empty() method.
 925         */
 926         size_t size() const
 927         {
 928             return m_ItemCounter.value();
 929         }
 930
 931         /// Returns const reference to internal statistics
 932         stat const& statistics() const
 933         {
 934             return m_Stat;
 935         }
 936
 937     protected:
 938         //@cond
 939         // split-list support
 940         bool insert_aux_node( node_type * pNode )
 941         {
 942             return insert_aux_node( &m_Head, pNode );
 943         }
 944
 945         // split-list support
 946         bool insert_aux_node( node_type * pHead, node_type * pNode )
 947         {
 948             assert( pNode != nullptr );
 949
 950             // Hack: convert node_type to value_type.
 951             // In principle, auxiliary node cannot be reducible to value_type
 952             // We assume that internal comparator can correctly distinguish aux and regular node.
 953             return insert_at( pHead, *node_traits::to_value_ptr( pNode ));
 954         }
 955
 956         bool insert_at( node_type * pHead, value_type& val )
 957         {
 958             position pos;
 959             key_comparator  cmp;
 960
 961             while ( true ) {
 962                 search( pHead, val, pos, key_comparator());
 963                 {
 964                     scoped_position_lock alp( pos );
 965                     if ( validate( pos.pPred, pos.pCur )) {
 966                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 967                             // failed: key already in list
 968                             m_Stat.onInsertFailed();
 969                             return false;
 970                         }
 971                         else {
 972                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 973                             break;
 974                         }
 975                     }
 976                 }
 977
 978                 m_Stat.onInsertRetry();
 979             }
 980
 981             ++m_ItemCounter;
 982             m_Stat.onInsertSuccess();
 983             return true;
 984         }
 985
 986         template <typename Func>
 987         bool insert_at( node_type * pHead, value_type& val, Func f )
 988         {
 989             position pos;
 990             key_comparator  cmp;
 991
 992             while ( true ) {
 993                 search( pHead, val, pos, key_comparator());
 994                 {
 995                     scoped_position_lock alp( pos );
 996                     if ( validate( pos.pPred, pos.pCur )) {
 997                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 998                             // failed: key already in list
 999                             m_Stat.onInsertFailed();
1000                             return false;
1001                         }
1002                         else {
1003                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1004                             f( val );
1005                             break;
1006                         }
1007                     }
1008                 }
1009
1010                 m_Stat.onInsertRetry();
1011             }
1012
1013             ++m_ItemCounter;
1014             m_Stat.onInsertSuccess();
1015             return true;
1016         }
1017
1018         template <typename Func>
1019         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
1020         {
1021             position pos;
1022             key_comparator  cmp;
1023
1024             while ( true ) {
1025                 search( pHead, val, pos, key_comparator());
1026                 {
1027                     scoped_position_lock alp( pos );
1028                     if ( validate( pos.pPred, pos.pCur )) {
1029                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1030                             // key already in the list
1031
1032                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
1033                             m_Stat.onUpdateExisting();
1034                             return std::make_pair( true, false );
1035                         }
1036                         else {
1037                             // new key
1038                             if ( !bAllowInsert ) {
1039                                 m_Stat.onUpdateFailed();
1040                                 return std::make_pair( false, false );
1041                             }
1042
1043                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
1044                             func( true, val, val );
1045                             break;
1046                         }
1047                     }
1048                 }
1049
1050                 m_Stat.onUpdateRetry();
1051             }
1052
1053             ++m_ItemCounter;
1054             m_Stat.onUpdateNew();
1055             return std::make_pair( true, true );
1056         }
1057
1058         bool unlink_at( node_type * pHead, value_type& val )
1059         {
1060             position pos;
1061             key_comparator  cmp;
1062
1063             while ( true ) {
1064                 search( pHead, val, pos, key_comparator());
1065                 {
1066                     int nResult = 0;
1067                     {
1068                         scoped_position_lock alp( pos );
1069                         if ( validate( pos.pPred, pos.pCur )) {
1070                             if ( pos.pCur != &m_Tail
1071                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1072                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
1073                             {
1074                                 // item found
1075                                 unlink_node( pos.pPred, pos.pCur, pHead );
1076                                 nResult = 1;
1077                             }
1078                             else
1079                                 nResult = -1;
1080                         }
1081                     }
1082
1083                     if ( nResult ) {
1084                         if ( nResult > 0 ) {
1085                             --m_ItemCounter;
1086                             retire_node( pos.pCur );
1087                             m_Stat.onEraseSuccess();
1088                             return true;
1089                         }
1090
1091                         m_Stat.onEraseFailed();
1092                         return false;
1093                     }
1094                 }
1095
1096                 m_Stat.onEraseRetry();
1097             }
1098         }
1099
1100         template <typename Q, typename Compare, typename Func>
1101         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1102         {
1103             while ( true ) {
1104                 search( pHead, val, pos, cmp );
1105                 {
1106                     int nResult = 0;
1107                     {
1108                         scoped_position_lock alp( pos );
1109                         if ( validate( pos.pPred, pos.pCur )) {
1110                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1111                                 // key found
1112                                 unlink_node( pos.pPred, pos.pCur, pHead );
1113                                 f( *node_traits::to_value_ptr( *pos.pCur ));
1114                                 nResult = 1;
1115                             }
1116                             else {
1117                                 nResult = -1;
1118                             }
1119                         }
1120                     }
1121                     if ( nResult ) {
1122                         if ( nResult > 0 ) {
1123                             --m_ItemCounter;
1124                             retire_node( pos.pCur );
1125                             m_Stat.onEraseSuccess();
1126                             return true;
1127                         }
1128
1129                         m_Stat.onEraseFailed();
1130                         return false;
1131                     }
1132                 }
1133
1134                 m_Stat.onEraseRetry();
1135             }
1136         }
1137
1138         template <typename Q, typename Compare, typename Func>
1139         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1140         {
1141             position pos;
1142             return erase_at( pHead, val, cmp, f, pos );
1143         }
1144
1145         template <typename Q, typename Compare>
1146         bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1147         {
1148             position pos;
1149             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1150         }
1151
1152         template <typename Q, typename Compare>
1153         bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1154         {
1155             position pos;
1156             if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1157                 gp.set( pos.guards.template get<value_type>(position::guard_current_item));
1158                 return true;
1159             }
1160             return false;
1161         }
1162
1163         template <typename Q, typename Compare, typename Func>
1164         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1165         {
1166             position pos;
1167
1168             search( pHead, val, pos, cmp );
1169             if ( pos.pCur != &m_Tail ) {
1170                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1171                 if ( !pos.pCur->is_marked()
1172                     && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1173                 {
1174                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1175                     m_Stat.onFindSuccess();
1176                     return true;
1177                 }
1178             }
1179
1180             m_Stat.onFindFailed();
1181             return false;
1182         }
1183
1184         template <typename Q, typename Compare>
1185         bool find_at( node_type * pHead, Q const& val, Compare cmp )
1186         {
1187             position pos;
1188
1189             search( pHead, val, pos, cmp );
1190             if ( pos.pCur != &m_Tail && !pos.pCur->is_marked() && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1191                 m_Stat.onFindSuccess();
1192                 return true;
1193             }
1194
1195             m_Stat.onFindFailed();
1196             return false;
1197         }
1198
1199         template <typename Q, typename Compare>
1200         bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1201         {
1202             position pos;
1203
1204             search( pHead, val, pos, cmp );
1205             if ( pos.pCur != &m_Tail
1206                 && !pos.pCur->is_marked()
1207                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1208             {
1209                 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1210                 m_Stat.onFindSuccess();
1211                 return true;
1212             }
1213
1214             m_Stat.onFindFailed();
1215             return false;
1216         }
1217
1218         //@endcond
1219
1220     protected:
1221         //@cond
1222         template <typename Q, typename Compare>
1223         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1224         {
1225             node_type const* pTail = &m_Tail;
1226
1227             marked_node_ptr pCur( pHead );
1228             marked_node_ptr pPrev( pHead );
1229
1230             while ( pCur.ptr() != pTail ) {
1231                 if ( pCur.ptr() != pHead ) {
1232                     if ( cmp( *node_traits::to_value_ptr( *pCur.ptr()), key ) >= 0 )
1233                         break;
1234                 }
1235
1236                 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1237                 pPrev = pCur;
1238
1239                 pCur = pos.guards.protect( position::guard_current_item, pPrev->m_pNext,
1240                     []( marked_node_ptr p ) { return node_traits::to_value_ptr( p.ptr()); }
1241                 );
1242                 assert( pCur.ptr() != nullptr );
1243                 if ( pCur.bits())
1244                     pPrev = pCur = pHead;
1245             }
1246
1247             pos.pCur = pCur.ptr();
1248             pos.pPred = pPrev.ptr();
1249         }
1250
1251         bool validate( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1252         {
1253             if ( validate_link( pPred, pCur )) {
1254                 m_Stat.onValidationSuccess();
1255                 return true;
1256             }
1257
1258             m_Stat.onValidationFailed();
1259             return true;
1260         }
1261
1262         static bool validate_link( node_type * pPred, node_type * pCur ) CDS_NOEXCEPT
1263         {
1264             return !pPred->is_marked()
1265                 && !pCur->is_marked()
1266                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1267         }
1268
1269         //@endcond
1270     };
1271 }}  // namespace cds::intrusive
1272
1273 #endif // CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H