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