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