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