cds/intrusive/impl/lazy_list.h

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