cds/intrusive/lazy_list_impl.h

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