cds/intrusive/impl/lazy_list.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
   4 #define CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H
   5
   6 #include <mutex>        // unique_lock
   7 #include <cds/intrusive/details/lazy_list_base.h>
   8
   9 namespace cds { namespace intrusive {
  10
  11     /// Lazy ordered single-linked list
  12     /** @ingroup cds_intrusive_list
  13         \anchor cds_intrusive_LazyList_hp
  14
  15         Usually, ordered single-linked list is used as a building block for the hash table implementation.
  16         The complexity of searching is <tt>O(N)</tt>.
  17
  18         Source:
  19             - [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit
  20               "A Lazy Concurrent List-Based Set Algorithm"
  21
  22         The lazy list is based on an optimistic locking scheme for inserts and removes,
  23         eliminating the need to use the equivalent of an atomically markable
  24         reference. It also has a novel wait-free membership \p find operation
  25         that does not need to perform cleanup operations and is more efficient.
  26
  27         Template arguments:
  28         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T (see lazy_list::node).
  29         - \p T - type to be stored in the list. The type must be based on lazy_list::node (for lazy_list::base_hook)
  30             or it must have a member of type lazy_list::node (for lazy_list::member_hook).
  31         - \p Traits - type traits. See lazy_list::traits for explanation.
  32             It is possible to declare option-based list with cds::intrusive::lazy_list::make_traits metafunction istead of \p Traits template
  33             argument. For example, the following traits-based declaration of \p gc::HP lazy list
  34             \code
  35             #include <cds/intrusive/lazy_list_hp.h>
  36             // Declare item stored in your list
  37             struct item: public cds::intrusive::lazy_list::node< cds::gc::HP >
  38             { ... };
  39
  40             // Declare comparator for the item
  41             struct my_compare { ... }
  42
  43             // Declare traits
  44             struct my_traits: public cds::intrusive::lazy_list::traits
  45             {
  46                 typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
  47                 typedef my_compare compare;
  48             };
  49
  50             // Declare traits-based list
  51             typedef cds::intrusive::LazyList< cds::gc::HP, item, my_traits >     traits_based_list;
  52             \endcode
  53             is equivalent for the following option-based list
  54             \code
  55             #include <cds/intrusive/lazy_list_hp.h>
  56
  57             // item struct and my_compare are the same
  58
  59             // Declare option-based list
  60             typedef cds::intrusive::LazyList< cds::gc::HP, item,
  61                 typename cds::intrusive::lazy_list::make_traits<
  62                     cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::HP > > >    // hook option
  63                     ,cds::intrusive::opt::compare< my_compare >     // item comparator option
  64                 >::type
  65             >     option_based_list;
  66             \endcode
  67
  68         \par Usage
  69         There are different specializations of this template for each garbage collecting schema used.
  70         You should select GC needed and include appropriate .h-file:
  71         - for gc::HP: \code #include <cds/intrusive/lazy_list_hp.h> \endcode
  72         - for gc::DHP: \code #include <cds/intrusive/lazy_list_dhp.h> \endcode
  73         - for gc::nogc: \code #include <cds/intrusive/lazy_list_nogc.h> \endcode
  74         - for \ref cds_urcu_type "RCU" - see \ref cds_intrusive_LazyList_rcu "LazyList RCU specialization"
  75
  76         Then, you should incorporate lazy_list::node into your struct \p T and provide
  77         appropriate \p lazy_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits
  78         a struct based on \p lazy_list::traits should be defined.
  79
  80         Example for gc::DHP and base hook:
  81         \code
  82         // Include GC-related lazy list specialization
  83         #include <cds/intrusive/lazy_list_dhp.h>
  84
  85         // Data stored in lazy list
  86         struct my_data: public cds::intrusive::lazy_list::node< cds::gc::DHP >
  87         {
  88             // key field
  89             std::string     strKey;
  90
  91             // other data
  92             // ...
  93         };
  94
  95         // my_data comparing functor
  96         struct compare {
  97             int operator()( const my_data& d1, const my_data& d2 )
  98             {
  99                 return d1.strKey.compare( d2.strKey );
 100             }
 101
 102             int operator()( const my_data& d, const std::string& s )
 103             {
 104                 return d.strKey.compare(s);
 105             }
 106
 107             int operator()( const std::string& s, const my_data& d )
 108             {
 109                 return s.compare( d.strKey );
 110             }
 111         };
 112
 113         // Declare traits
 114         struct my_traits: public cds::intrusive::lazy_list::traits
 115         {
 116             typedef cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > >   hook;
 117             typedef my_data_cmp compare;
 118         };
 119
 120         // Declare list type
 121         typedef cds::intrusive::LazyList< cds::gc::DHP, my_data, my_traits >     traits_based_list;
 122         \endcode
 123
 124         Equivalent option-based code:
 125         \code
 126         // GC-related specialization
 127         #include <cds/intrusive/lazy_list_dhp.h>
 128
 129         struct my_data {
 130             // see above
 131         };
 132         struct compare {
 133             // see above
 134         };
 135
 136         // Declare option-based list
 137         typedef cds::intrusive::LazyList< cds::gc::DHP
 138             ,my_data
 139             , typename cds::intrusive::lazy_list::make_traits<
 140                 cds::intrusive::opt::hook< cds::intrusive::lazy_list::base_hook< cds::opt::gc< cds::gc::DHP > > >
 141                 ,cds::intrusive::opt::compare< my_data_cmp >
 142             >::type
 143         > option_based_list;
 144
 145         \endcode
 146     */
 147     template <
 148         class GC
 149         ,typename T
 150 #ifdef CDS_DOXYGEN_INVOKED
 151         ,class Traits = lazy_list::traits
 152 #else
 153         ,class Traits
 154 #endif
 155     >
 156     class LazyList
 157     {
 158     public:
 159         typedef GC     gc;   ///< Garbage collector
 160         typedef T      value_type; ///< type of value stored in the list
 161         typedef Traits traits;     ///< Traits template parameter
 162
 163         typedef typename traits::hook    hook;      ///< hook type
 164         typedef typename hook::node_type node_type; ///< node type
 165
 166 #   ifdef CDS_DOXYGEN_INVOKED
 167         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 168 #   else
 169         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 170 #   endif
 171
 172         typedef typename traits::disposer  disposer;   ///< disposer
 173         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
 174         typedef typename lazy_list::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
 175
 176         typedef typename traits::back_off  back_off    ;   ///< back-off strategy
 177         typedef typename traits::item_counter item_counter ;   ///< Item counting policy used
 178         typedef typename traits::memory_model  memory_model;   ///< C++ memory ordering (see \p lazy_list::traits::memory_model)
 179
 180         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 181
 182         //@cond
 183         // Rebind traits (split-list support)
 184         template <typename... Options>
 185         struct rebind_traits {
 186             typedef LazyList<
 187                 gc
 188                 , value_type
 189                 , typename cds::opt::make_options< traits, Options...>::type
 190             >   type;
 191         };
 192         //@endcond
 193
 194     protected:
 195         typedef typename node_type::marked_ptr marked_node_ptr;   ///< Node marked pointer
 196         typedef node_type *     auxiliary_head;   ///< Auxiliary head type (for split-list support)
 197
 198     protected:
 199         //@cond
 200         node_type   m_Head;
 201         node_type   m_Tail;
 202
 203         item_counter    m_ItemCounter   ;   ///< Item counter
 204
 205         //@cond
 206         struct clean_disposer {
 207             void operator()( value_type * p )
 208             {
 209                 lazy_list::node_cleaner<gc, node_type, memory_model>()( node_traits::to_node_ptr( p ) );
 210                 disposer()( p );
 211             }
 212         };
 213
 214         /// Position pointer for item search
 215         struct position {
 216             node_type *     pPred   ;    ///< Previous node
 217             node_type *     pCur    ;    ///< Current node
 218
 219             typename gc::template GuardArray<2> guards  ;   ///< Guards array
 220
 221             enum {
 222                 guard_prev_item,
 223                 guard_current_item
 224             };
 225
 226             /// Locks nodes \p pPred and \p pCur
 227             void lock()
 228             {
 229                 pPred->m_Lock.lock();
 230                 pCur->m_Lock.lock();
 231             }
 232
 233             /// Unlocks nodes \p pPred and \p pCur
 234             void unlock()
 235             {
 236                 pCur->m_Lock.unlock();
 237                 pPred->m_Lock.unlock();
 238             }
 239         };
 240
 241         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         /// Updates the item
 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             iff \p bAllowInsert is \p true.
 535             Otherwise, the functor \p func is called with item found.
 536             The functor signature is:
 537             \code
 538             struct functor {
 539                 void operator()( bool bNew, value_type& item, value_type& val );
 540             };
 541             \endcode
 542             with arguments:
 543             - \p bNew - \p true if the item has been inserted, \p false otherwise
 544             - \p item - item of the list
 545             - \p val - argument \p val passed into the \p update() function
 546             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 547             refer to the same thing.
 548
 549             The functor may change non-key fields of the \p item.
 550             While the functor \p f is working the item \p item is locked,
 551             so \p func has exclusive access to the item.
 552
 553             Returns <tt> std::pair<bool, bool>  </tt> where \p first is \p true if operation is successfull,
 554             \p second is \p true if new item has been added or \p false if the item with \p key
 555             already is in the list.
 556
 557             The function makes RCU lock internally.
 558         */
 559         template <typename Func>
 560         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
 561         {
 562             return update_at( &m_Head, val, func, bAllowInsert );
 563         }
 564         //@cond
 565         // Deprecated, use update()
 566         template <typename Func>
 567         std::pair<bool, bool> ensure( value_type& val, Func func )
 568         {
 569             return update( val, func, true );
 570         }
 571         //@endcond
 572
 573         /// Unlinks the item \p val from the list
 574         /**
 575             The function searches the item \p val in the list and unlink it from the list
 576             if it is found and it is equal to \p val.
 577
 578             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 579             and deletes the item found. \p unlink finds an item by key and deletes it
 580             only if \p val is an item of that list, i.e. the pointer to item found
 581             is equal to <tt> &val </tt>.
 582
 583             The function returns \p true if success and \p false otherwise.
 584         */
 585         bool unlink( value_type& val )
 586         {
 587             return unlink_at( &m_Head, val );
 588         }
 589
 590         /// Deletes the item from the list
 591         /** \anchor cds_intrusive_LazyList_hp_erase_val
 592             The function searches an item with key equal to \p key in the list,
 593             unlinks it from the list, and returns \p true.
 594             If the item with the key equal to \p key is not found the function return \p false.
 595         */
 596         template <typename Q>
 597         bool erase( Q const& key )
 598         {
 599             return erase_at( &m_Head, key, key_comparator() );
 600         }
 601
 602         /// Deletes the item from the list using \p pred predicate for searching
 603         /**
 604             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
 605             but \p pred is used for key comparing.
 606             \p Less functor has the interface like \p std::less.
 607             \p pred must imply the same element order as the comparator used for building the list.
 608         */
 609         template <typename Q, typename Less>
 610         bool erase_with( Q const& key, Less pred )
 611         {
 612             CDS_UNUSED( pred );
 613             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 614         }
 615
 616         /// Deletes the item from the list
 617         /** \anchor cds_intrusive_LazyList_hp_erase_func
 618             The function searches an item with key equal to \p key in the list,
 619             call \p func functor with item found, unlinks it from the list, and returns \p true.
 620             The \p Func interface is
 621             \code
 622             struct functor {
 623                 void operator()( value_type const& item );
 624             };
 625             \endcode
 626
 627             If \p key is not found the function return \p false.
 628         */
 629         template <typename Q, typename Func>
 630         bool erase( const Q& key, Func func )
 631         {
 632             return erase_at( &m_Head, key, key_comparator(), func );
 633         }
 634
 635         /// Deletes the item from the list using \p pred predicate for searching
 636         /**
 637             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
 638             but \p pred is used for key comparing.
 639             \p Less functor has the interface like \p std::less.
 640             \p pred must imply the same element order as the comparator used for building the list.
 641         */
 642         template <typename Q, typename Less, typename Func>
 643         bool erase_with( const Q& key, Less pred, Func func )
 644         {
 645             CDS_UNUSED( pred );
 646             return erase_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), func );
 647         }
 648
 649         /// Extracts the item from the list with specified \p key
 650         /** \anchor cds_intrusive_LazyList_hp_extract
 651             The function searches an item with key equal to \p key,
 652             unlinks it from the list, and returns it as \p guarded_ptr.
 653             If \p key is not found the function returns an empty guarded pointer.
 654
 655             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 656
 657             The \ref disposer specified in \p Traits class template parameter is called automatically
 658             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
 659             will be destroyed or released.
 660             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 661
 662             Usage:
 663             \code
 664             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 665             ord_list theList;
 666             // ...
 667             {
 668                 ord_list::guarded_ptr gp( theList.extract( 5 ));
 669                 // Deal with gp
 670                 // ...
 671
 672                 // Destructor of gp releases internal HP guard
 673             }
 674             \endcode
 675         */
 676         template <typename Q>
 677         guarded_ptr extract( Q const& key )
 678         {
 679             guarded_ptr gp;
 680             extract_at( &m_Head, gp.guard(), key, key_comparator() );
 681             return gp;
 682         }
 683
 684         /// Extracts the item from the list with comparing functor \p pred
 685         /**
 686             The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(Q const&)"
 687             but \p pred predicate is used for key comparing.
 688
 689             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 690             in any order.
 691             \p pred must imply the same element order as the comparator used for building the list.
 692         */
 693         template <typename Q, typename Less>
 694         guarded_ptr extract_with( Q const& key, Less pred )
 695         {
 696             CDS_UNUSED( pred );
 697             guarded_ptr gp;
 698             extract_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 699             return gp;
 700         }
 701
 702         /// Finds the key \p key
 703         /** \anchor cds_intrusive_LazyList_hp_find
 704             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 705             The interface of \p Func functor is:
 706             \code
 707             struct functor {
 708                 void operator()( value_type& item, Q& key );
 709             };
 710             \endcode
 711             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 712
 713             The functor may change non-key fields of \p item.
 714             While the functor \p f is calling the item \p item is locked.
 715
 716             The function returns \p true if \p key is found, \p false otherwise.
 717         */
 718         template <typename Q, typename Func>
 719         bool find( Q& key, Func f )
 720         {
 721             return find_at( &m_Head, key, key_comparator(), f );
 722         }
 723         //@cond
 724         template <typename Q, typename Func>
 725         bool find( Q const& key, Func f )
 726         {
 727             return find_at( &m_Head, key, key_comparator(), f );
 728         }
 729         //@endcond
 730
 731         /// Finds the key \p key using \p pred predicate for searching
 732         /**
 733             The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
 734             but \p pred is used for key comparing.
 735             \p Less functor has the interface like \p std::less.
 736             \p pred must imply the same element order as the comparator used for building the list.
 737         */
 738         template <typename Q, typename Less, typename Func>
 739         bool find_with( Q& key, Less pred, Func f )
 740         {
 741             CDS_UNUSED( pred );
 742             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 743         }
 744         //@cond
 745         template <typename Q, typename Less, typename Func>
 746         bool find_with( Q const& key, Less pred, Func f )
 747         {
 748             CDS_UNUSED( pred );
 749             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>(), f );
 750         }
 751         //@endcond
 752
 753         /// Checks whether the list contains \p key
 754         /**
 755             The function searches the item with key equal to \p key
 756             and returns \p true if it is found, and \p false otherwise.
 757         */
 758         template <typename Q>
 759         bool contains( Q const& key )
 760         {
 761             return find_at( &m_Head, key, key_comparator() );
 762         }
 763         //@cond
 764         // Deprecated, use contains()
 765         template <typename Q>
 766         bool find( Q const& key )
 767         {
 768             return contains( key );
 769         }
 770         //@cond
 771
 772         /// Checks whether the map contains \p key using \p pred predicate for searching
 773         /**
 774             The function is an analog of <tt>contains( key )</tt> but \p pred is used for key comparing.
 775             \p Less functor has the interface like \p std::less.
 776             \p Less must imply the same element order as the comparator used for building the list.
 777         */
 778         template <typename Q, typename Less>
 779         bool contains( Q const& key, Less pred )
 780         {
 781             CDS_UNUSED( pred );
 782             return find_at( &m_Head, key, cds::opt::details::make_comparator_from_less<Less>() );
 783         }
 784         //@cond
 785         // Deprecated, use contains()
 786         template <typename Q, typename Less>
 787         bool find_with( Q const& key, Less pred )
 788         {
 789             return contains( key, pred );
 790         }
 791         //@endcond
 792
 793         /// Finds \p key and return the item found
 794         /** \anchor cds_intrusive_LazyList_hp_get
 795             The function searches the item with key equal to \p key
 796             and returns an guarded pointer to it.
 797             If \p key is not found the function returns an empty guarded pointer.
 798
 799             The \ref disposer specified in \p Traits class template parameter is called
 800             by garbage collector \p GC automatically when returned \p guarded_ptr object
 801             will be destroyed or released.
 802             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 803
 804             Usage:
 805             \code
 806             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 807             ord_list theList;
 808             // ...
 809             {
 810                 ord_list::guarded_ptr gp(theList.get( 5 ));
 811                 if ( gp ) {
 812                     // Deal with gp
 813                     //...
 814                 }
 815                 // Destructor of guarded_ptr releases internal HP guard
 816             }
 817             \endcode
 818
 819             Note the compare functor specified for class \p Traits template parameter
 820             should accept a parameter of type \p Q that can be not the same as \p value_type.
 821         */
 822         template <typename Q>
 823         guarded_ptr get( Q const& key )
 824         {
 825             guarded_ptr gp;
 826             get_at( &m_Head, gp.guard(), key, key_comparator() );
 827             return gp;
 828         }
 829
 830         /// Finds \p key and return the item found
 831         /**
 832             The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( Q const&)"
 833             but \p pred is used for comparing the keys.
 834
 835             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 836             in any order.
 837             \p pred must imply the same element order as the comparator used for building the list.
 838         */
 839         template <typename Q, typename Less>
 840         guarded_ptr get_with( Q const& key, Less pred )
 841         {
 842             CDS_UNUSED( pred );
 843             guarded_ptr gp;
 844             get_at( &m_Head, gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 845             return gp;
 846         }
 847
 848         /// Clears the list
 849         void clear()
 850         {
 851             typename gc::Guard guard;
 852             marked_node_ptr h;
 853             while ( !empty() ) {
 854                 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
 855                 guard.assign( node_traits::to_value_ptr( h.ptr() ));
 856                 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
 857                     m_Head.m_Lock.lock();
 858                     h->m_Lock.lock();
 859
 860                     unlink_node( &m_Head, h.ptr(), &m_Head );
 861
 862                     h->m_Lock.unlock();
 863                     m_Head.m_Lock.unlock();
 864
 865                     retire_node( h.ptr() ) ; // free node
 866                 }
 867             }
 868         }
 869
 870         /// Checks if the list is empty
 871         bool empty() const
 872         {
 873             return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
 874         }
 875
 876         /// Returns list's item count
 877         /**
 878             The value returned depends on item counter provided by \p Traits. For \p atomicity::empty_item_counter,
 879             this function always returns 0.
 880
 881             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
 882             is empty. To check list emptyness use \p empty() method.
 883         */
 884         size_t size() const
 885         {
 886             return m_ItemCounter.value();
 887         }
 888
 889     protected:
 890         //@cond
 891         // split-list support
 892         bool insert_aux_node( node_type * pNode )
 893         {
 894             return insert_aux_node( &m_Head, pNode );
 895         }
 896
 897         // split-list support
 898         bool insert_aux_node( node_type * pHead, node_type * pNode )
 899         {
 900             assert( pNode != nullptr );
 901
 902             // Hack: convert node_type to value_type.
 903             // In principle, auxiliary node cannot be reducible to value_type
 904             // We assume that internal comparator can correctly distinguish aux and regular node.
 905             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 906         }
 907
 908         bool insert_at( node_type * pHead, value_type& val )
 909         {
 910             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 911             position pos;
 912             key_comparator  cmp;
 913
 914             while ( true ) {
 915                 search( pHead, val, pos, key_comparator() );
 916                 {
 917                     auto_lock_position alp( pos );
 918                     if ( validate( pos.pPred, pos.pCur )) {
 919                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 920                             // failed: key already in list
 921                             return false;
 922                         }
 923                         else {
 924                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 925                             ++m_ItemCounter;
 926                             return true;
 927                         }
 928                     }
 929                 }
 930             }
 931         }
 932
 933         template <typename Func>
 934         bool insert_at( node_type * pHead, value_type& val, Func f )
 935         {
 936             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 937             position pos;
 938             key_comparator  cmp;
 939
 940             while ( true ) {
 941                 search( pHead, val, pos, key_comparator() );
 942                 {
 943                     auto_lock_position alp( pos );
 944                     if ( validate( pos.pPred, pos.pCur )) {
 945                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 946                             // failed: key already in list
 947                             return false;
 948                         }
 949                         else {
 950                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 951                             f( val );
 952                             ++m_ItemCounter;
 953                             return true;
 954                         }
 955                     }
 956                 }
 957             }
 958         }
 959
 960         template <typename Func>
 961         std::pair<bool, bool> update_at( node_type * pHead, value_type& val, Func func, bool bAllowInsert )
 962         {
 963             position pos;
 964             key_comparator  cmp;
 965
 966             while ( true ) {
 967                 search( pHead, val, pos, key_comparator() );
 968                 {
 969                     auto_lock_position alp( pos );
 970                     if ( validate( pos.pPred, pos.pCur )) {
 971                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 972                             // key already in the list
 973
 974                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 975                             return std::make_pair( true, false );
 976                         }
 977                         else {
 978                             // new key
 979                             if ( !bAllowInsert )
 980                                 return std::make_pair( false, false );
 981
 982                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 983
 984                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 985                             func( true, val, val );
 986                             ++m_ItemCounter;
 987                             return std::make_pair( true, true );
 988                         }
 989                     }
 990                 }
 991             }
 992         }
 993
 994         bool unlink_at( node_type * pHead, value_type& val )
 995         {
 996             position pos;
 997             key_comparator  cmp;
 998
 999             while ( true ) {
1000                 search( pHead, val, pos, key_comparator() );
1001                 {
1002                     int nResult = 0;
1003                     {
1004                         auto_lock_position alp( pos );
1005                         if ( validate( pos.pPred, pos.pCur ) ) {
1006                             if ( pos.pCur != &m_Tail
1007                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1008                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
1009                             {
1010                                 // item found
1011                                 unlink_node( pos.pPred, pos.pCur, pHead );
1012                                 --m_ItemCounter;
1013                                 nResult = 1;
1014                             }
1015                             else
1016                                 nResult = -1;
1017                         }
1018                     }
1019                     if ( nResult ) {
1020                         if ( nResult > 0 ) {
1021                             retire_node( pos.pCur );
1022                             return true;
1023                         }
1024                         return false;
1025                     }
1026                 }
1027             }
1028         }
1029
1030         template <typename Q, typename Compare, typename Func>
1031         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1032         {
1033             while ( true ) {
1034                 search( pHead, val, pos, cmp );
1035                 {
1036                     int nResult = 0;
1037                     {
1038                         auto_lock_position alp( pos );
1039                         if ( validate( pos.pPred, pos.pCur )) {
1040                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1041                                 // key found
1042                                 unlink_node( pos.pPred, pos.pCur, pHead );
1043                                 f( *node_traits::to_value_ptr( *pos.pCur ) );
1044                                 --m_ItemCounter;
1045                                 nResult = 1;
1046                             }
1047                             else {
1048                                 nResult = -1;
1049                             }
1050                         }
1051                     }
1052                     if ( nResult ) {
1053                         if ( nResult > 0 ) {
1054                             retire_node( pos.pCur );
1055                             return true;
1056                         }
1057                         return false;
1058                     }
1059                 }
1060             }
1061         }
1062
1063         template <typename Q, typename Compare, typename Func>
1064         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1065         {
1066             position pos;
1067             return erase_at( pHead, val, cmp, f, pos );
1068         }
1069
1070         template <typename Q, typename Compare>
1071         bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1072         {
1073             position pos;
1074             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1075         }
1076
1077         template <typename Q, typename Compare>
1078         bool extract_at( node_type * pHead, typename guarded_ptr::native_guard& gp, const Q& val, Compare cmp )
1079         {
1080             position pos;
1081             if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1082                 gp.set( pos.guards.template get<value_type>(position::guard_current_item) );
1083                 return true;
1084             }
1085             return false;
1086         }
1087
1088         template <typename Q, typename Compare, typename Func>
1089         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1090         {
1091             position pos;
1092
1093             search( pHead, val, pos, cmp );
1094             if ( pos.pCur != &m_Tail ) {
1095                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1096                 if ( !pos.pCur->is_marked()
1097                     && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1098                 {
1099                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1100                     return true;
1101                 }
1102             }
1103             return false;
1104         }
1105
1106         template <typename Q, typename Compare>
1107         bool find_at( node_type * pHead, Q const& val, Compare cmp )
1108         {
1109             position pos;
1110
1111             search( pHead, val, pos, cmp );
1112             return pos.pCur != &m_Tail
1113                 && !pos.pCur->is_marked()
1114                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1115         }
1116
1117         template <typename Q, typename Compare>
1118         bool get_at( node_type * pHead, typename guarded_ptr::native_guard& gp, Q const& val, Compare cmp )
1119         {
1120             position pos;
1121
1122             search( pHead, val, pos, cmp );
1123             if ( pos.pCur != &m_Tail
1124                 && !pos.pCur->is_marked()
1125                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1126             {
1127                 gp.set( pos.guards.template get<value_type>( position::guard_current_item ));
1128                 return true;
1129             }
1130             return false;
1131         }
1132
1133         //@endcond
1134
1135     protected:
1136         //@cond
1137         template <typename Q, typename Compare>
1138         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1139         {
1140             const node_type * pTail = &m_Tail;
1141
1142             marked_node_ptr pCur( pHead );
1143             marked_node_ptr pPrev( pHead );
1144
1145             back_off        bkoff;
1146
1147             while ( pCur.ptr() != pTail )
1148             {
1149                 if ( pCur.ptr() != pHead ) {
1150                     if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1151                         break;
1152                 }
1153
1154                 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1155                 pPrev = pCur;
1156
1157                 for (;;) {
1158                     pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1159                     pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1160                     if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1161                         break;
1162                     bkoff();
1163                 }
1164                 assert( pCur.ptr() != nullptr );
1165             }
1166
1167             pos.pCur = pCur.ptr();
1168             pos.pPred = pPrev.ptr();
1169         }
1170
1171         static bool validate( node_type * pPred, node_type * pCur )
1172         {
1173             return !pPred->is_marked()
1174                 && !pCur->is_marked()
1175                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1176         }
1177
1178         //@endcond
1179     };
1180 }}  // namespace cds::intrusive
1181
1182 #endif // CDSLIB_INTRUSIVE_IMPL_LAZY_LIST_H