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.
 541
 542             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 543         */
 544         template <typename Func>
 545         bool insert( value_type& val, Func f )
 546         {
 547             return insert_at( &m_Head, val, f );
 548         }
 549
 550         /// Ensures that the \p item exists in the list
 551         /**
 552             The operation performs inserting or changing data with lock-free manner.
 553
 554             If the item \p val not found in the list, then \p val is inserted into the list.
 555             Otherwise, the functor \p func is called with item found.
 556             The functor signature is:
 557             \code
 558                 void func( bool bNew, value_type& item, value_type& val );
 559             \endcode
 560             with arguments:
 561             - \p bNew - \p true if the item has been inserted, \p false otherwise
 562             - \p item - item of the list
 563             - \p val - argument \p val passed into the \p ensure function
 564             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 565             refer to the same thing.
 566
 567             The functor may change non-key fields of the \p item.
 568             While the functor \p f is working the item \p item is locked.
 569
 570             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 571             \p second is \p true if new item has been added or \p false if the item with \p key
 572             already is in the list.
 573
 574             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 575         */
 576         template <typename Func>
 577         std::pair<bool, bool> ensure( value_type& val, Func func )
 578         {
 579             return ensure_at( &m_Head, val, func );
 580         }
 581
 582         /// Unlinks the item \p val from the list
 583         /**
 584             The function searches the item \p val in the list and unlink it from the list
 585             if it is found and it is equal to \p val.
 586
 587             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
 588             and deletes the item found. \p unlink finds an item by key and deletes it
 589             only if \p val is an item of that list, i.e. the pointer to item found
 590             is equal to <tt> &val </tt>.
 591
 592             The function returns \p true if success and \p false otherwise.
 593         */
 594         bool unlink( value_type& val )
 595         {
 596             return unlink_at( &m_Head, val );
 597         }
 598
 599         /// Deletes the item from the list
 600         /** \anchor cds_intrusive_LazyList_hp_erase_val
 601             The function searches an item with key equal to \p val in the list,
 602             unlinks it from the list, and returns \p true.
 603             If the item with the key equal to \p val is not found the function return \p false.
 604         */
 605         template <typename Q>
 606         bool erase( Q const& val )
 607         {
 608             return erase_at( &m_Head, val, key_comparator() );
 609         }
 610
 611         /// Deletes the item from the list using \p pred predicate for searching
 612         /**
 613             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_val "erase(Q const&)"
 614             but \p pred is used for key comparing.
 615             \p Less functor has the interface like \p std::less.
 616             \p pred must imply the same element order as the comparator used for building the list.
 617         */
 618         template <typename Q, typename Less>
 619         bool erase_with( Q const& val, Less pred )
 620         {
 621             return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
 622         }
 623
 624         /// Deletes the item from the list
 625         /** \anchor cds_intrusive_LazyList_hp_erase_func
 626             The function searches an item with key equal to \p val in the list,
 627             call \p func functor with item found, unlinks it from the list, and returns \p true.
 628             The \p Func interface is
 629             \code
 630             struct functor {
 631                 void operator()( value_type const& item );
 632             };
 633             \endcode
 634             The functor may be passed by reference using <tt>boost:ref</tt>
 635
 636             If the item with the key equal to \p val is not found the function return \p false.
 637         */
 638         template <typename Q, typename Func>
 639         bool erase( const Q& val, Func func )
 640         {
 641             return erase_at( &m_Head, val, key_comparator(), func );
 642         }
 643
 644         /// Deletes the item from the list using \p pred predicate for searching
 645         /**
 646             The function is an analog of \ref cds_intrusive_LazyList_hp_erase_func "erase(Q const&, Func)"
 647             but \p pred is used for key comparing.
 648             \p Less functor has the interface like \p std::less.
 649             \p pred must imply the same element order as the comparator used for building the list.
 650         */
 651         template <typename Q, typename Less, typename Func>
 652         bool erase_with( const Q& val, Less pred, Func func )
 653         {
 654             return erase_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), func );
 655         }
 656
 657         /// Extracts the item from the list with specified \p key
 658         /** \anchor cds_intrusive_LazyList_hp_extract
 659             The function searches an item with key equal to \p key,
 660             unlinks it from the list, and returns it in \p dest parameter.
 661             If the item with key equal to \p key is not found the function returns \p false.
 662
 663             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 664
 665             The \ref disposer specified in \p Traits class template parameter is called automatically
 666             by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
 667             will be destroyed or released.
 668             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 669
 670             Usage:
 671             \code
 672             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 673             ord_list theList;
 674             // ...
 675             {
 676                 ord_list::guarded_ptr gp;
 677                 theList.extract( gp, 5 );
 678                 // Deal with gp
 679                 // ...
 680
 681                 // Destructor of gp releases internal HP guard
 682             }
 683             \endcode
 684         */
 685         template <typename Q>
 686         bool extract( guarded_ptr& dest, Q const& key )
 687         {
 688             return extract_at( &m_Head, dest.guard(), key, key_comparator() );
 689         }
 690
 691         /// Extracts the item from the list with comparing functor \p pred
 692         /**
 693             The function is an analog of \ref cds_intrusive_LazyList_hp_extract "extract(guarded_ptr&, Q const&)"
 694             but \p pred predicate is used for key comparing.
 695
 696             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 697             in any order.
 698             \p pred must imply the same element order as the comparator used for building the list.
 699         */
 700         template <typename Q, typename Less>
 701         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
 702         {
 703             return extract_at( &m_Head, dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
 704         }
 705
 706         /// Finds the key \p val
 707         /** \anchor cds_intrusive_LazyList_hp_find
 708             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 709             The interface of \p Func functor is:
 710             \code
 711             struct functor {
 712                 void operator()( value_type& item, Q& val );
 713             };
 714             \endcode
 715             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 716
 717             You may pass \p f argument by reference using \p std::ref.
 718
 719             The functor may change non-key fields of \p item.
 720             While the functor \p f is calling the item \p item is locked.
 721
 722             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 723             may modify both arguments.
 724
 725             The function returns \p true if \p val is found, \p false otherwise.
 726         */
 727         template <typename Q, typename Func>
 728         bool find( Q& val, Func f )
 729         {
 730             return find_at( &m_Head, val, key_comparator(), f );
 731         }
 732
 733         /// Finds the key \p val using \p pred predicate for searching
 734         /**
 735             The function is an analog of \ref cds_intrusive_LazyList_hp_find "find(Q&, Func)"
 736             but \p pred is used for key comparing.
 737             \p Less functor has the interface like \p std::less.
 738             \p pred must imply the same element order as the comparator used for building the list.
 739         */
 740         template <typename Q, typename Less, typename Func>
 741         bool find_with( Q& val, Less pred, Func f )
 742         {
 743             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 744         }
 745
 746         /// Finds the key \p val
 747         /** \anchor cds_intrusive_LazyList_hp_find_const
 748             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 749             The interface of \p Func functor is:
 750             \code
 751             struct functor {
 752                 void operator()( value_type& item, Q const& val );
 753             };
 754             \endcode
 755             where \p item is the item found, \p val is the \p find function argument.
 756
 757             You may pass \p f argument by reference using \p std::ref.
 758
 759             The functor may change non-key fields of \p item.
 760             While the functor \p f is calling the item \p item is locked.
 761
 762             The function returns \p true if \p val is found, \p false otherwise.
 763         */
 764         template <typename Q, typename Func>
 765         bool find( Q const& val, Func f )
 766         {
 767             return find_at( &m_Head, val, key_comparator(), f );
 768         }
 769
 770         /// Finds the key \p val using \p pred predicate for searching
 771         /**
 772             The function is an analog of \ref cds_intrusive_LazyList_hp_find_const "find(Q const&, Func)"
 773             but \p pred is used for key comparing.
 774             \p Less functor has the interface like \p std::less.
 775             \p pred must imply the same element order as the comparator used for building the list.
 776         */
 777         template <typename Q, typename Less, typename Func>
 778         bool find_with( Q const& val, Less pred, Func f )
 779         {
 780             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>(), f );
 781         }
 782
 783         /// Finds the key \p val
 784         /** \anchor cds_intrusive_LazyList_hp_find_val
 785             The function searches the item with key equal to \p val
 786             and returns \p true if it is found, and \p false otherwise
 787         */
 788         template <typename Q>
 789         bool find( Q const & val )
 790         {
 791             return find_at( &m_Head, val, key_comparator() );
 792         }
 793
 794         /// Finds the key \p val using \p pred predicate for searching
 795         /**
 796             The function is an analog of \ref cds_intrusive_LazyList_hp_find_val "find(Q const&)"
 797             but \p pred is used for key comparing.
 798             \p Less functor has the interface like \p std::less.
 799             \p pred must imply the same element order as the comparator used for building the list.
 800         */
 801         template <typename Q, typename Less>
 802         bool find_with( Q const& val, Less pred )
 803         {
 804             return find_at( &m_Head, val, cds::opt::details::make_comparator_from_less<Less>() );
 805         }
 806
 807         /// Finds the key \p val and return the item found
 808         /** \anchor cds_intrusive_LazyList_hp_get
 809             The function searches the item with key equal to \p val
 810             and assigns the item found to guarded pointer \p ptr.
 811             The function returns \p true if \p val is found, and \p false otherwise.
 812             If \p val is not found the \p ptr parameter is not changed.
 813
 814             The \ref disposer specified in \p Traits class template parameter is called
 815             by garbage collector \p GC automatically when returned \ref guarded_ptr object
 816             will be destroyed or released.
 817             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 818
 819             Usage:
 820             \code
 821             typedef cds::intrusive::LazyList< cds::gc::HP, foo, my_traits >  ord_list;
 822             ord_list theList;
 823             // ...
 824             {
 825                 ord_list::guarded_ptr gp;
 826                 if ( theList.get( gp, 5 )) {
 827                     // Deal with gp
 828                     //...
 829                 }
 830                 // Destructor of guarded_ptr releases internal HP guard
 831             }
 832             \endcode
 833
 834             Note the compare functor specified for class \p Traits template parameter
 835             should accept a parameter of type \p Q that can be not the same as \p value_type.
 836         */
 837         template <typename Q>
 838         bool get( guarded_ptr& ptr, Q const& val )
 839         {
 840             return get_at( &m_Head, ptr.guard(), val, key_comparator() );
 841         }
 842
 843         /// Finds the key \p val and return the item found
 844         /**
 845             The function is an analog of \ref cds_intrusive_LazyList_hp_get "get( guarded_ptr& ptr, Q const&)"
 846             but \p pred is used for comparing the keys.
 847
 848             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 849             in any order.
 850             \p pred must imply the same element order as the comparator used for building the list.
 851         */
 852         template <typename Q, typename Less>
 853         bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
 854         {
 855             return get_at( &m_Head, ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
 856         }
 857
 858         /// Clears the list
 859         /**
 860             The function unlink all items from the list.
 861         */
 862         void clear()
 863         {
 864             typename gc::Guard guard;
 865             marked_node_ptr h;
 866             while ( !empty() ) {
 867                 h = m_Head.m_pNext.load( memory_model::memory_order_relaxed );
 868                 guard.assign( node_traits::to_value_ptr( h.ptr() ));
 869                 if ( m_Head.m_pNext.load(memory_model::memory_order_acquire) == h ) {
 870                     m_Head.m_Lock.lock();
 871                     h->m_Lock.lock();
 872
 873                     unlink_node( &m_Head, h.ptr(), &m_Head );
 874
 875                     h->m_Lock.unlock();
 876                     m_Head.m_Lock.unlock();
 877
 878                     retire_node( h.ptr() ) ; // free node
 879                 }
 880             }
 881         }
 882
 883         /// Checks if the list is empty
 884         bool empty() const
 885         {
 886             return m_Head.m_pNext.load( memory_model::memory_order_relaxed ).ptr() == &m_Tail;
 887         }
 888
 889         /// Returns list's item count
 890         /**
 891             The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
 892             this function always returns 0.
 893
 894             <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the list
 895             is empty. To check list emptyness use \ref empty() method.
 896         */
 897         size_t size() const
 898         {
 899             return m_ItemCounter.value();
 900         }
 901
 902     protected:
 903         //@cond
 904         // split-list support
 905         bool insert_aux_node( node_type * pNode )
 906         {
 907             return insert_aux_node( &m_Head, pNode );
 908         }
 909
 910         // split-list support
 911         bool insert_aux_node( node_type * pHead, node_type * pNode )
 912         {
 913             assert( pNode != nullptr );
 914
 915             // Hack: convert node_type to value_type.
 916             // In principle, auxiliary node can be non-reducible to value_type
 917             // We assume that comparator can correctly distinguish aux and regular node.
 918             return insert_at( pHead, *node_traits::to_value_ptr( pNode ) );
 919         }
 920
 921         bool insert_at( node_type * pHead, value_type& val )
 922         {
 923             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 924             position pos;
 925             key_comparator  cmp;
 926
 927             while ( true ) {
 928                 search( pHead, val, pos, key_comparator() );
 929                 {
 930                     auto_lock_position alp( pos );
 931                     if ( validate( pos.pPred, pos.pCur )) {
 932                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 933                             // failed: key already in list
 934                             return false;
 935                         }
 936                         else {
 937                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 938                             ++m_ItemCounter;
 939                             return true;
 940                         }
 941                     }
 942                 }
 943             }
 944         }
 945
 946         template <typename Func>
 947         bool insert_at( node_type * pHead, value_type& val, Func f )
 948         {
 949             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 950             position pos;
 951             key_comparator  cmp;
 952
 953             while ( true ) {
 954                 search( pHead, val, pos, key_comparator() );
 955                 {
 956                     auto_lock_position alp( pos );
 957                     if ( validate( pos.pPred, pos.pCur )) {
 958                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 959                             // failed: key already in list
 960                             return false;
 961                         }
 962                         else {
 963                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 964                             f( val );
 965                             ++m_ItemCounter;
 966                             return true;
 967                         }
 968                     }
 969                 }
 970             }
 971         }
 972
 973         template <typename Func>
 974         std::pair<bool, bool> ensure_at( node_type * pHead, value_type& val, Func func )
 975         {
 976             position pos;
 977             key_comparator  cmp;
 978
 979             while ( true ) {
 980                 search( pHead, val, pos, key_comparator() );
 981                 {
 982                     auto_lock_position alp( pos );
 983                     if ( validate( pos.pPred, pos.pCur )) {
 984                         if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
 985                             // key already in the list
 986
 987                             func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
 988                             return std::make_pair( true, false );
 989                         }
 990                         else {
 991                             // new key
 992                             link_checker::is_empty( node_traits::to_node_ptr( val ) );
 993
 994                             link_node( node_traits::to_node_ptr( val ), pos.pPred, pos.pCur );
 995                             func( true, val, val );
 996                             ++m_ItemCounter;
 997                             return std::make_pair( true, true );
 998                         }
 999                     }
1000                 }
1001             }
1002         }
1003
1004         bool unlink_at( node_type * pHead, value_type& val )
1005         {
1006             position pos;
1007             key_comparator  cmp;
1008
1009             while ( true ) {
1010                 search( pHead, val, pos, key_comparator() );
1011                 {
1012                     int nResult = 0;
1013                     {
1014                         auto_lock_position alp( pos );
1015                         if ( validate( pos.pPred, pos.pCur ) ) {
1016                             if ( pos.pCur != &m_Tail
1017                                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0
1018                                 && node_traits::to_value_ptr( pos.pCur ) == &val )
1019                             {
1020                                 // item found
1021                                 unlink_node( pos.pPred, pos.pCur, pHead );
1022                                 --m_ItemCounter;
1023                                 nResult = 1;
1024                             }
1025                             else
1026                                 nResult = -1;
1027                         }
1028                     }
1029                     if ( nResult ) {
1030                         if ( nResult > 0 ) {
1031                             retire_node( pos.pCur );
1032                             return true;
1033                         }
1034                         return false;
1035                     }
1036                 }
1037             }
1038         }
1039
1040         template <typename Q, typename Compare, typename Func>
1041         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f, position& pos )
1042         {
1043             while ( true ) {
1044                 search( pHead, val, pos, cmp );
1045                 {
1046                     int nResult = 0;
1047                     {
1048                         auto_lock_position alp( pos );
1049                         if ( validate( pos.pPred, pos.pCur )) {
1050                             if ( pos.pCur != &m_Tail && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 ) {
1051                                 // key found
1052                                 unlink_node( pos.pPred, pos.pCur, pHead );
1053                                 f( *node_traits::to_value_ptr( *pos.pCur ) );
1054                                 --m_ItemCounter;
1055                                 nResult = 1;
1056                             }
1057                             else {
1058                                 nResult = -1;
1059                             }
1060                         }
1061                     }
1062                     if ( nResult ) {
1063                         if ( nResult > 0 ) {
1064                             retire_node( pos.pCur );
1065                             return true;
1066                         }
1067                         return false;
1068                     }
1069                 }
1070             }
1071         }
1072
1073         template <typename Q, typename Compare, typename Func>
1074         bool erase_at( node_type * pHead, const Q& val, Compare cmp, Func f )
1075         {
1076             position pos;
1077             return erase_at( pHead, val, cmp, f, pos );
1078         }
1079
1080         template <typename Q, typename Compare>
1081         bool erase_at( node_type * pHead, const Q& val, Compare cmp )
1082         {
1083             position pos;
1084             return erase_at( pHead, val, cmp, [](value_type const &){}, pos );
1085         }
1086
1087         template <typename Q, typename Compare>
1088         bool extract_at( node_type * pHead, typename gc::Guard& gp, const Q& val, Compare cmp )
1089         {
1090             position pos;
1091             if ( erase_at( pHead, val, cmp, [](value_type const &){}, pos )) {
1092                 gp.assign( pos.guards.template get<value_type>(position::guard_current_item) );
1093                 return true;
1094             }
1095             return false;
1096         }
1097
1098         template <typename Q, typename Compare, typename Func>
1099         bool find_at( node_type * pHead, Q& val, Compare cmp, Func f )
1100         {
1101             position pos;
1102
1103             search( pHead, val, pos, cmp );
1104             if ( pos.pCur != &m_Tail ) {
1105                 std::unique_lock< typename node_type::lock_type> al( pos.pCur->m_Lock );
1106                 if ( !pos.pCur->is_marked()
1107                     && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1108                 {
1109                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
1110                     return true;
1111                 }
1112             }
1113             return false;
1114         }
1115
1116         template <typename Q, typename Compare>
1117         bool find_at( node_type * pHead, Q const& val, Compare cmp )
1118         {
1119             position pos;
1120
1121             search( pHead, val, pos, cmp );
1122             return pos.pCur != &m_Tail
1123                 && !pos.pCur->is_marked()
1124                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0;
1125         }
1126
1127         template <typename Q, typename Compare>
1128         bool get_at( node_type * pHead, typename gc::Guard& gp, Q const& val, Compare cmp )
1129         {
1130             position pos;
1131
1132             search( pHead, val, pos, cmp );
1133             if ( pos.pCur != &m_Tail
1134                 && !pos.pCur->is_marked()
1135                 && cmp( *node_traits::to_value_ptr( *pos.pCur ), val ) == 0 )
1136             {
1137                 gp.assign( pos.guards.template get<value_type>( position::guard_current_item ));
1138                 return true;
1139             }
1140             return false;
1141         }
1142
1143         //@endcond
1144
1145     protected:
1146         //@cond
1147         template <typename Q, typename Compare>
1148         void search( node_type * pHead, const Q& key, position& pos, Compare cmp )
1149         {
1150             const node_type * pTail = &m_Tail;
1151
1152             marked_node_ptr pCur( pHead );
1153             marked_node_ptr pPrev( pHead );
1154
1155             back_off        bkoff;
1156
1157             while ( pCur.ptr() != pTail )
1158             {
1159                 if ( pCur.ptr() != pHead ) {
1160                     if ( cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) >= 0 )
1161                         break;
1162                 }
1163
1164                 pos.guards.copy( position::guard_prev_item, position::guard_current_item );
1165                 pPrev = pCur;
1166
1167                 for (;;) {
1168                     pCur = pPrev->m_pNext.load(memory_model::memory_order_relaxed);
1169                     pos.guards.assign( position::guard_current_item, node_traits::to_value_ptr( pCur.ptr() ));
1170                     if ( pCur == pPrev->m_pNext.load(memory_model::memory_order_acquire) )
1171                         break;
1172                     bkoff();
1173                 }
1174                 assert( pCur.ptr() != nullptr );
1175             }
1176
1177             pos.pCur = pCur.ptr();
1178             pos.pPred = pPrev.ptr();
1179         }
1180
1181         static bool validate( node_type * pPred, node_type * pCur )
1182         {
1183             return !pPred->is_marked()
1184                 && !pCur->is_marked()
1185                 && pPred->m_pNext.load(memory_model::memory_order_relaxed) == pCur;
1186         }
1187
1188         //@endcond
1189     };
1190 }}  // namespace cds::intrusive
1191
1192 #endif // __CDS_INTRUSIVE_IMPL_LAZY_LIST_H