cds/intrusive/impl/lazy_list.h

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