cds/intrusive/impl/lazy_list.h

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