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