cds/intrusive/impl/lazy_list.h

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