cds/intrusive/impl/lazy_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_IMPL_LAZY_LIST_H
   4 #define __CDS_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         class auto_lock_position {
 242             position&   m_pos;
 243         public:
 244             auto_lock_position( position& pos )
 245                 : m_pos(pos)
 246             {
 247                 pos.lock();
 248             }
 249             ~auto_lock_position()
 250             {
 251                 m_pos.unlock();
 252             }
 253         };
 254         //@endcond
 255
 256     protected:
 257         //@cond
 258         void link_node( node_type * pNode, node_type * pPred, node_type * pCur )
 259         {
 260             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
 261
 262             pNode->m_pNext.store( marked_node_ptr(pCur), memory_model::memory_order_release );
 263             pPred->m_pNext.store( marked_node_ptr(pNode), memory_model::memory_order_release );
 264         }
 265
 266         void unlink_node( node_type * pPred, node_type * pCur, node_type * pHead )
 267         {
 268             assert( pPred->m_pNext.load(memory_model::memory_order_relaxed).ptr() == pCur );
 269
 270             node_type * pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 271             //pCur->m_pNext.store( marked_node_ptr( pNext, 1), memory_model::memory_order_release) ;   // logically deleting
 272             pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release )    ; // logical removal + back-link for search
 273             pPred->m_pNext.store( marked_node_ptr( pNext ), memory_model::memory_order_release); // physically deleting
 274             //pCur->m_pNext.store( marked_node_ptr( pHead, 1 ), memory_model::memory_order_release )    ; // back-link for search
 275         }
 276
 277         void retire_node( node_type * pNode )
 278         {
 279             assert( pNode != nullptr );
 280             gc::template retire<clean_disposer>( node_traits::to_value_ptr( *pNode ) );
 281         }
 282         //@endcond
 283
 284     protected:
 285         //@cond
 286         template <bool IsConst>
 287         class iterator_type
 288         {
 289             friend class LazyList;
 290
 291         protected:
 292             value_type * m_pNode;
 293             typename gc::Guard  m_Guard;
 294
 295             void next()
 296             {
 297                 assert( m_pNode != nullptr );
 298
 299                 if ( m_pNode ) {
 300                     typename gc::Guard g;
 301                     node_type * pCur = node_traits::to_node_ptr( m_pNode );
 302                     if ( pCur->m_pNext.load( memory_model::memory_order_relaxed ).ptr() != nullptr ) {      // if pCur is not tail node
 303                         node_type * pNext;
 304                         do {
 305                             pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 306                             g.assign( node_traits::to_value_ptr( pNext ));
 307                         } while ( pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed).ptr() );
 308
 309                         m_pNode = m_Guard.assign( g.template get<value_type>() );
 310                     }
 311                 }
 312             }
 313
 314             void skip_deleted()
 315             {
 316                 if ( m_pNode != nullptr ) {
 317                     typename gc::Guard g;
 318                     node_type * pNode = node_traits::to_node_ptr( m_pNode );
 319
 320                     // Dummy tail node could not be marked
 321                     while ( pNode->is_marked() ) {
 322                         node_type * p = pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr();
 323                         g.assign( node_traits::to_value_ptr( p ));
 324                         if ( p == pNode->m_pNext.load(memory_model::memory_order_relaxed).ptr() )
 325                             pNode = p;
 326                     }
 327                     if ( pNode != node_traits::to_node_ptr( m_pNode ) )
 328                         m_pNode = m_Guard.assign( g.template get<value_type>() );
 329                 }
 330             }
 331
 332             iterator_type( node_type * pNode )
 333             {
 334                 m_pNode = m_Guard.assign( node_traits::to_value_ptr( pNode ));
 335                 skip_deleted();
 336             }
 337
 338         public:
 339             typedef typename cds::details::make_const_type<value_type, IsConst>::pointer   value_ptr;
 340             typedef typename cds::details::make_const_type<value_type, IsConst>::reference value_ref;
 341
 342             iterator_type()
 343                 : m_pNode( nullptr )
 344             {}
 345
 346             iterator_type( iterator_type const& src )
 347             {
 348                 if ( src.m_pNode ) {
 349                     m_pNode = m_Guard.assign( src.m_pNode );
 350                 }
 351                 else
 352                     m_pNode = nullptr;
 353             }
 354
 355             value_ptr operator ->() const
 356             {
 357                 return m_pNode;
 358             }
 359
 360             value_ref operator *() const
 361             {
 362                 assert( m_pNode != nullptr );
 363                 return *m_pNode;
 364             }
 365
 366             /// Pre-increment
 367             iterator_type& operator ++()
 368             {
 369                 next();
 370                 skip_deleted();
 371                 return *this;
 372             }
 373
 374             iterator_type& operator = (iterator_type const& src)
 375             {
 376                 m_pNode = src.m_pNode;
 377                 m_Guard.assign( m_pNode );
 378                 return *this;
 379             }
 380
 381             template <bool C>
 382             bool operator ==(iterator_type<C> const& i ) const
 383             {
 384                 return m_pNode == i.m_pNode;
 385             }
 386             template <bool C>
 387             bool operator !=(iterator_type<C> const& i ) const
 388             {
 389                 return m_pNode != i.m_pNode;
 390             }
 391         };
 392         //@endcond
 393
 394     public:
 395         /// Forward iterator
 396         /**
 397             The forward iterator for lazy list has some features:
 398             - it has no post-increment operator
 399             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 400               For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
 401               may be thrown if a limit of guard count per thread is exceeded.
 402             - The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
 403             - Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
 404               deleting operations it is no guarantee that you iterate all item in the list.
 405
 406             Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
 407             for debug purpose only.
 408         */
 409         typedef iterator_type<false>    iterator;
 410         /// Const forward iterator
 411         /**
 412             For iterator's features and requirements see \ref iterator
 413         */
 414         typedef iterator_type<true>     const_iterator;
 415
 416         /// Returns a forward iterator addressing the first element in a list
 417         /**
 418             For empty list \code begin() == end() \endcode
 419         */
 420         iterator begin()
 421         {
 422             iterator it( &m_Head );
 423             ++it        ;   // skip dummy head
 424             return it;
 425         }
 426
 427         /// Returns an iterator that addresses the location succeeding the last element in a list
 428         /**
 429             Do not use the value returned by <tt>end</tt> function to access any item.
 430
 431             The returned value can be used only to control reaching the end of the list.
 432             For empty list \code begin() == end() \endcode
 433         */
 434         iterator end()
 435         {
 436             return iterator( &m_Tail );
 437         }
 438
 439         /// Returns a forward const iterator addressing the first element in a list
 440         //@{
 441         const_iterator begin() const
 442         {
 443             return get_const_begin();
 444         }
 445         const_iterator cbegin() const
 446         {
 447             return get_const_begin();
 448         }
 449         //@}
 450
 451         /// Returns an const iterator that addresses the location succeeding the last element in a list
 452         //@{
 453         const_iterator end() const
 454         {
 455             return get_const_end();
 456         }
 457         const_iterator cend() const
 458         {
 459             return get_const_end();
 460         }
 461         //@}
 462
 463     private:
 464         //@cond
 465         const_iterator get_const_begin() const
 466         {
 467             const_iterator it( const_cast<node_type *>( &m_Head ));
 468             ++it        ;   // skip dummy head
 469             return it;
 470         }
 471         const_iterator get_const_end() const
 472         {
 473             return const_iterator( const_cast<node_type *>(&m_Tail) );
 474         }
 475         //@endcond
 476
 477     public:
 478         /// Default constructor initializes empty list
 479         LazyList()
 480         {
 481             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 482             m_Head.m_pNext.store( marked_node_ptr( &m_Tail ), memory_model::memory_order_relaxed );
 483         }
 484
 485         /// Destroys the list object
 486         ~LazyList()
 487         {
 488             clear();
 489             assert( m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail );
 490             m_Head.m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
 491         }
 492
 493         /// Inserts new node
 494         /**
 495             The function inserts \p val in the list if the list does not contain
 496             an item with key equal to \p val.
 497
 498             Returns \p true if \p val is linked into the list, \p false otherwise.
 499         */
 500         bool insert( value_type& val )
 501         {
 502             return insert_at( &m_Head, val );
 503         }
 504
 505         /// Inserts new node
 506         /**
 507             This function is intended for derived non-intrusive containers.
 508
 509             The function allows to split new item creating into two part:
 510             - create item with key only
 511             - insert new item into the list
 512             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 513
 514             The functor signature is:
 515             \code
 516                 void func( value_type& val );
 517             \endcode
 518             where \p val is the item inserted.
 519             While the functor \p f is called the item \p val is locked so
 520             the functor has an exclusive access to the item.
 521             The user-defined functor is called only if the inserting is success.
 522         */
 523         template <typename Func>
 524         bool insert( value_type& val, Func f )
 525         {
 526             return insert_at( &m_Head, val, f );
 527         }
 528
 529         /// Ensures that the \p item exists in the list
 530         /**
 531             The operation performs inserting or changing data with lock-free manner.
 532
 533             If the item \p val not found in the list, then \p val is inserted into the list.
 534             Otherwise, the functor \p func is called with item found.
 535             The functor signature is:
 536             \code
 537                 void func( bool bNew, value_type& item, value_type& val );
 538             \endcode
 539             with arguments:
 540             - \p bNew - \p true if the item has been inserted, \p false otherwise
 541             - \p item - item of the list
 542             - \p val - argument \p val passed into the \p ensure function
 543             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 544             refer to the same thing.
 545
 546             The functor may change non-key fields of the \p item.
 547             While the functor \p f is working the item \p item is locked,
 548             so \p f has exclusive access to the item.
 549
 550             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 551             \p second is \p true if new item has been added or \p false if the item with \p key
 552             already is in the list.
 553         */
 554         template <typename Func>
 555         std::pair<bool, bool> ensure( value_type& val, Func func )
 556         {
 557             return ensure_at( &m_Head, val, func );
 558         }
 559
 560         /// Unlinks the item \p val from the list
 561         /**
 562             The function searches the item \p val in the list and unlink it from the list
 563             if it is found and it is equal to \p val.
 564
 565             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 566             and deletes the item found. \p unlink finds an item by key and deletes it
 567             only if \p val is an item of that list, i.e. the pointer to item found
 568             is equal to <tt> &val </tt>.
 569
 570             The function returns \p true if success and \p false otherwise.
 571         */
 572         bool unlink( value_type& val )
 573         {
 574             return unlink_at( &m_Head, val );
 575         }
 576
 577         /// Deletes the item from the list
 578         /** \anchor cds_intrusive_LazyList_hp_erase_val
 579             The function searches an item with key equal to \p key in the list,
 580             unlinks it from the list, and returns \p true.
 581             If the item with the key equal to \p key is not found the function return \p false.
 582         */
 583         template <typename Q>
 584         bool erase( Q const& key )
 585         {
 586             return erase_at( &m_Head, key, key_comparator() );
 587         }
 588
 589         /// Deletes the item from the list using \p pred predicate for searching
 590         /**
 591             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
 592             but \p pred is used for key comparing.
 593             \p Less functor has the interface like \p std::less.
 594             \p pred must imply the same element order as the comparator used for building the list.
 595         */
 596         template <typename Q, typename Less>
 597         bool erase_with( Q const& key, Less pred )
 598         {
 599             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 600         }
 601
 602         /// Deletes the item from the list
 603         /** \anchor cds_intrusive_LazyList_hp_erase_func
 604             The function searches an item with key equal to \p key in the list,
 605             call \p func functor with item found, unlinks it from the list, and returns \p true.
 606             The \p Func interface is
 607             \code
 608             struct functor {
 609                 void operator()( value_type const& item );
 610             };
 611             \endcode
 612
 613             If \p key is not found the function return \p false.
 614         */
 615         template <typename Q, typename Func>
 616         bool erase( const Q& key, Func func )
 617         {
 618             return erase_at( &m_Head, key, key_comparator(), func );
 619         }
 620
 621         /// Deletes the item from the list using \p pred predicate for searching
 622         /**
 623             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
 624             but \p pred is used for key comparing.
 625             \p Less functor has the interface like \p std::less.
 626             \p pred must imply the same element order as the comparator used for building the list.
 627         */
 628         template <typename Q, typename Less, typename Func>
 629         bool erase_with( const Q& key, Less pred, Func func )
 630         {
 631             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 632         }
 633
 634         /// Extracts the item from the list with specified \p key
 635         /** \anchor cds_intrusive_LazyList_hp_extract
 636             The function searches an item with key equal to \p key,
 637             unlinks it from the list, and returns it as \p guarded_ptr.
 638             If \p key is not found the function returns an empty guarded pointer.
 639
 640             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 641
 642             The \ref disposer specified in \p Traits class template parameter is called automatically
 643             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
 644             will be destroyed or released.
 645             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 646
 647             Usage:
 648             \code
 649             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 650             ord_list theList;
 651             // ...
 652             {
 653                 ord_list::guarded_ptr gp( theList.extract( 5 ));
 654                 // Deal with gp
 655                 // ...
 656
 657                 // Destructor of gp releases internal HP guard
 658             }
 659             \endcode
 660         */
 661         template <typename Q>
 662         guarded_ptr extract( Q const& key )
 663         {
 664             guarded_ptr gp;
 665             extract_at( &m_Head, gp.guard(), key, key_comparator() );
 666             return gp;
 667         }
 668
 669         /// Extracts the item from the list with comparing functor \p pred
 670         /**
 671             The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
 672             but \p pred predicate is used for key comparing.
 673
 674             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 675             in any order.
 676             \p pred must imply the same element order as the comparator used for building the list.
 677         */
 678         template <typename Q, typename Less>
 679         guarded_ptr extract_with( Q const& key, Less pred )
 680         {
 681             guarded_ptr gp;
 682             extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 683             return gp;
 684         }
 685
 686         /// Finds the key \p key
 687         /** \anchor cds_intrusive_LazyList_hp_find
 688             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 689             The interface of \p Func functor is:
 690             \code
 691             struct functor {
 692                 void operator()( value_type& item, Q& key );
 693             };
 694             \endcode
 695             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 696
 697             The functor may change non-key fields of \p item.
 698             While the functor \p f is calling the item \p item is locked.
 699
 700             The function returns \p true if \p key is found, \p false otherwise.
 701         */
 702         template <typename Q, typename Func>
 703         bool find( Q& key, Func f )
 704         {
 705             return find_at( &m_Head, key, key_comparator(), f );
 706         }
 707         //@cond
 708         template <typename Q, typename Func>
 709         bool find( Q const& key, Func f )
 710         {
 711             return find_at( &m_Head, key, key_comparator(), f );
 712         }
 713         //@endcond
 714
 715         /// Finds the key \p key using \p pred predicate for searching
 716         /**
 717             The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
 718             but \p pred is used for key comparing.
 719             \p Less functor has the interface like \p std::less.
 720             \p pred must imply the same element order as the comparator used for building the list.
 721         */
 722         template <typename Q, typename Less, typename Func>
 723         bool find_with( Q& key, Less pred, Func f )
 724         {
 725             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 726         }
 727         //@cond
 728         template <typename Q, typename Less, typename Func>
 729         bool find_with( Q const& key, Less pred, Func f )
 730         {
 731             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 732         }
 733         //@endcond
 734
 735         /// Finds the key \p key
 736         /** \anchor cds_intrusive_LazyList_hp_find_val
 737             The function searches the item with key equal to \p key
 738             and returns \p true if it is found, and \p false otherwise
 739         */
 740         template <typename Q>
 741         bool find( Q const& key )
 742         {
 743             return find_at( &m_Head, key, key_comparator() );
 744         }
 745
 746         /// Finds \p key using \p pred predicate for searching
 747         /**
 748             The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
 749             but \p pred is used for key comparing.
 750             \p Less functor has the interface like \p std::less.
 751             \p pred must imply the same element order as the comparator used for building the list.
 752         */
 753         template <typename Q, typename Less>
 754         bool find_with( Q const& key, Less pred )
 755         {
 756             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 757         }
 758
 759         /// Finds \p key and return the item found
 760         /** \anchor cds_intrusive_LazyList_hp_get
 761             The function searches the item with key equal to \p key
 762             and returns an guarded pointer to it.
 763             If \p key is not found the function returns an empty guarded pointer.
 764
 765             The \ref disposer specified in \p Traits class template parameter is called
 766             by garbage collector \p GC automatically when returned \p guarded_ptr object
 767             will be destroyed or released.
 768             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 769
 770             Usage:
 771             \code
 772             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 773             ord_list theList;
 774             // ...
 775             {
 776                 ord_list::guarded_ptr gp(theList.get( 5 ));
 777                 if ( gp ) {
 778                     // Deal with gp
 779                     //...
 780                 }
 781                 // Destructor of guarded_ptr releases internal HP guard
 782             }
 783             \endcode
 784
 785             Note the compare functor specified for class \p Traits template parameter
 786             should accept a parameter of type \p Q that can be not the same as \p value_type.
 787         */
 788         template <typename Q>
 789         guarded_ptr get( Q const& key )
 790         {
 791             guarded_ptr gp;
 792             get_at( &m_Head, gp.guard(), key, key_comparator() );
 793             return gp;
 794         }
 795
 796         /// Finds \p key and return the item found
 797         /**
 798             The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
 799             but \p pred is used for comparing the keys.
 800
 801             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 802             in any order.
 803             \p pred must imply the same element order as the comparator used for building the list.
 804         */
 805         template <typename Q, typename Less>
 806         guarded_ptr get_with( Q const& key, Less pred )
 807         {
 808             guarded_ptr gp;
 809             get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 810             return gp;
 811         }
 812
 813         /// Clears the list
 814         void clear()
 815         {
 816             typename gc::Guard guard;
 817             marked_node_ptr h;
 818             while ( !empty() ) {
 819                 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
 820                 guard.assign( node_traits::to_value_ptr( h.ptr() ));
 821                 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
 822                     m_Head.m_Lock.lock();
 823                     h->m_Lock.lock();
 824
 825                     unlink_node( &m_Head, h.ptr(), &m_Head );
 826
 827                     h->m_Lock.unlock();
 828                     m_Head.m_Lock.unlock();
 829
 830                     retire_node( h.ptr() ) ; // free node
 831                 }
 832             }
 833         }
 834
 835         /// Checks if the list is empty
 836         bool empty() const
 837         {
 838             return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
 839         }
 840
 841         /// Returns list's item count
 842         /**
 843             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 844             this function always returns 0.
 845
 846             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 847             is empty. To check list emptyness use \p empty() method.
 848         */
 849         size_t size() const
 850         {
 851             return m_ItemCounter.value();
 852         }
 853
 854     protected:
 855         //@cond
 856         // split-list support
 857         bool insert_aux_node( node_type * pNode )
 858         {
 859             return insert_aux_node( &m_Head, pNode );
 860         }
 861
 862         // split-list support
 863         bool insert_aux_node( node_type * pHead, node_type * pNode )
 864         {
 865             assert( pNode != nullptr );
 866
 867             // Hack: convert node_type to value_type.
 868             // In principle, auxiliary node cannot be reducible to value_type
 869             // We assume that internal comparator can correctly distinguish aux and regular node.
 870             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 871         }
 872
 873         bool insert_at( node_type * pHead, value_type& val )
 874         {
 875             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 876             position pos;
 877             key_comparator  cmp;
 878
 879             while ( true ) {
 880                 search( pHead, val, pos, key_comparator() );
 881                 {
 882                     auto_lock_position alp( pos );
 883                     if ( validate( pos.pPred, pos.pCur )) {
 884                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 885                             // failed: key already in list
 886                             return false;
 887                         }
 888                         else {
 889                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 890                             ++m_ItemCounter;
 891                             return true;
 892                         }
 893                     }
 894                 }
 895             }
 896         }
 897
 898         template <typename Func>
 899         bool insert_at( node_type * pHead, value_type& val, Func f )
 900         {
 901             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 902             position pos;
 903             key_comparator  cmp;
 904
 905             while ( true ) {
 906                 search( pHead, val, pos, key_comparator() );
 907                 {
 908                     auto_lock_position alp( pos );
 909                     if ( validate( pos.pPred, pos.pCur )) {
 910                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 911                             // failed: key already in list
 912                             return false;
 913                         }
 914                         else {
 915                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 916                             f( val );
 917                             ++m_ItemCounter;
 918                             return true;
 919                         }
 920                     }
 921                 }
 922             }
 923         }
 924
 925         template <typename Func>
 926         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 927         {
 928             position pos;
 929             key_comparator  cmp;
 930
 931             while ( true ) {
 932                 search( pHead, val, pos, key_comparator() );
 933                 {
 934                     auto_lock_position alp( pos );
 935                     if ( validate( pos.pPred, pos.pCur )) {
 936                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 937                             // key already in the list
 938
 939                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 940                             return std::make_pair( true, false );
 941                         }
 942                         else {
 943                             // new key
 944                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 945
 946                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 947                             func( true, val, val );
 948                             ++m_ItemCounter;
 949                             return std::make_pair( true, true );
 950                         }
 951                     }
 952                 }
 953             }
 954         }
 955
 956         bool unlink_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                     int nResult = 0;
 965                     {
 966                         auto_lock_position alp( pos );
 967                         if ( validate( pos.pPred, pos.pCur ) ) {
 968                             if ( pos.pCur != &m_Tail
 969                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
 970                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
 971                             {
 972                                 // item found
 973                                 unlink_node( pos.pPred, pos.pCur, pHead );
 974                                 --m_ItemCounter;
 975                                 nResult = 1;
 976                             }
 977                             else
 978                                 nResult = -1;
 979                         }
 980                     }
 981                     if ( nResult ) {
 982                         if ( nResult > 0 ) {
 983                             retire_node( pos.pCur );
 984                             return true;
 985                         }
 986                         return false;
 987                     }
 988                 }
 989             }
 990         }
 991
 992         template <typename Q, typename Compare, typename Func>
 993         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
 994         {
 995             while ( true ) {
 996                 search( pHead, val, pos, cmp );
 997                 {
 998                     int nResult = 0;
 999                     {
1000                         auto_lock_position alp( pos );
1001                         if ( validate( pos.pPred, pos.pCur )) {
1002                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1003                                 // key found
1004                                 unlink_node( pos.pPred, pos.pCur, pHead );
1005                                 f( *node_traits::to_value_ptr( *pos.pCur ) );
1006                                 --m_ItemCounter;
1007                                 nResult = 1;
1008                             }
1009                             else {
1010                                 nResult = -1;
1011                             }
1012                         }
1013                     }
1014                     if ( nResult ) {
1015                         if ( nResult > 0 ) {
1016                             retire_node( pos.pCur );
1017                             return true;
1018                         }
1019                         return false;
1020                     }
1021                 }
1022             }
1023         }
1024
1025         template <typename Q, typename Compare, typename Func>
1026         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1027         {
1028             position pos;
1029             return erase_at( pHead, val, cmp, f, pos );
1030         }
1031
1032         template <typename Q, typename Compare>
1033         bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1034         {
1035             position pos;
1036             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1037         }
1038
1039         template <typename Q, typename Compare>
1040         bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1041         {
1042             position pos;
1043             if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1044                 gp.set( pos.guards.template get<value_type>(position::guard_current_item) );
1045                 return true;
1046             }
1047             return false;
1048         }
1049
1050         template <typename Q, typename Compare, typename Func>
1051         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1052         {
1053             position pos;
1054
1055             search( pHead, val, pos, cmp );
1056             if ( pos.pCur != &m_Tail ) {
1057                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1058                 if ( !pos.pCur->is_marked()
1059                     && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1060                 {
1061                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1062                     return true;
1063                 }
1064             }
1065             return false;
1066         }
1067
1068         template <typename Q, typename Compare>
1069         bool find_at( node_type * pHead, Q const& val, Compare cmp )
1070         {
1071             position pos;
1072
1073             search( pHead, val, pos, cmp );
1074             return pos.pCur != &m_Tail
1075                 && !pos.pCur->is_marked()
1076                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1077         }
1078
1079         template <typename Q, typename Compare>
1080         bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1081         {
1082             position pos;
1083
1084             search( pHead, val, pos, cmp );
1085             if ( pos.pCur != &m_Tail
1086                 && !pos.pCur->is_marked()
1087                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1088             {
1089                 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1090                 return true;
1091             }
1092             return false;
1093         }
1094
1095         //@endcond
1096
1097     protected:
1098         //@cond
1099         template <typename Q, typename Compare>
1100         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1101         {
1102             const node_type * pTail = &m_Tail;
1103
1104             marked_node_ptr pCur( pHead );
1105             marked_node_ptr pPrev( pHead );
1106
1107             back_off        bkoff;
1108
1109             while ( pCur.ptr() != pTail )
1110             {
1111                 if ( pCur.ptr() != pHead ) {
1112                     if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1113                         break;
1114                 }
1115
1116                 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1117                 pPrev = pCur;
1118
1119                 for (;;) {
1120                     pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1121                     pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1122                     if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1123                         break;
1124                     bkoff();
1125                 }
1126                 assert( pCur.ptr() != nullptr );
1127             }
1128
1129             pos.pCur = pCur.ptr();
1130             pos.pPred = pPrev.ptr();
1131         }
1132
1133         static bool validate( node_type * pPred, node_type * pCur )
1134         {
1135             return !pPred->is_marked()
1136                 && !pCur->is_marked()
1137                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1138         }
1139
1140         //@endcond
1141     };
1142 }}  // namespace cds::intrusive
1143
1144 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H