cds/intrusive/impl/lazy_list.h

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