cds/intrusive/impl/skip_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_SKIP_LIST_H
  32 #define CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H
  33
  34 #include <type_traits>
  35 #include <memory>
  36 #include <functional>   // ref
  37 #include <cds/intrusive/details/skip_list_base.h>
  38 #include <cds/opt/compare.h>
  39 #include <cds/details/binary_functor_wrapper.h>
  40
  41 namespace cds { namespace intrusive {
  42
  43     //@cond
  44     namespace skip_list { namespace details {
  45
  46         template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
  47         class iterator {
  48         public:
  49             typedef GC                                  gc;
  50             typedef NodeTraits                          node_traits;
  51             typedef BackOff                             back_off;
  52             typedef typename node_traits::node_type     node_type;
  53             typedef typename node_traits::value_type    value_type;
  54             static CDS_CONSTEXPR bool const c_isConst = IsConst;
  55
  56             typedef typename std::conditional< c_isConst, value_type const&, value_type&>::type   value_ref;
  57
  58         protected:
  59             typedef typename node_type::marked_ptr          marked_ptr;
  60             typedef typename node_type::atomic_marked_ptr   atomic_marked_ptr;
  61
  62             typename gc::Guard      m_guard;
  63             node_type *             m_pNode;
  64
  65         protected:
  66             static value_type * gc_protect( marked_ptr p )
  67             {
  68                 return node_traits::to_value_ptr( p.ptr());
  69             }
  70
  71             void next()
  72             {
  73                 typename gc::Guard g;
  74                 g.copy( m_guard );
  75                 back_off bkoff;
  76
  77                 for (;;) {
  78                     if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
  79                         // Current node is marked as deleted. So, its next pointer can point to anything
  80                         // In this case we interrupt our iteration and returns end() iterator.
  81                         *this = iterator();
  82                         return;
  83                     }
  84
  85                     marked_ptr p = m_guard.protect( (*m_pNode)[0], gc_protect );
  86                     node_type * pp = p.ptr();
  87                     if ( p.bits()) {
  88                         // p is marked as deleted. Spin waiting for physical removal
  89                         bkoff();
  90                         continue;
  91                     }
  92                     else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits()) {
  93                         // p is marked as deleted. Spin waiting for physical removal
  94                         bkoff();
  95                         continue;
  96                     }
  97
  98                     m_pNode = pp;
  99                     break;
 100                 }
 101             }
 102
 103         public: // for internal use only!!!
 104             iterator( node_type& refHead )
 105                 : m_pNode( nullptr )
 106             {
 107                 back_off bkoff;
 108
 109                 for (;;) {
 110                     marked_ptr p = m_guard.protect( refHead[0], gc_protect );
 111                     if ( !p.ptr()) {
 112                         // empty skip-list
 113                         m_guard.clear();
 114                         break;
 115                     }
 116
 117                     node_type * pp = p.ptr();
 118                     // Logically deleted node is marked from highest level
 119                     if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits()) {
 120                         m_pNode = pp;
 121                         break;
 122                     }
 123
 124                     bkoff();
 125                 }
 126             }
 127
 128         public:
 129             iterator()
 130                 : m_pNode( nullptr )
 131             {}
 132
 133             iterator( iterator const& s)
 134                 : m_pNode( s.m_pNode )
 135             {
 136                 m_guard.assign( node_traits::to_value_ptr(m_pNode));
 137             }
 138
 139             value_type * operator ->() const
 140             {
 141                 assert( m_pNode != nullptr );
 142                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 143
 144                 return node_traits::to_value_ptr( m_pNode );
 145             }
 146
 147             value_ref operator *() const
 148             {
 149                 assert( m_pNode != nullptr );
 150                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 151
 152                 return *node_traits::to_value_ptr( m_pNode );
 153             }
 154
 155             /// Pre-increment
 156             iterator& operator ++()
 157             {
 158                 next();
 159                 return *this;
 160             }
 161
 162             iterator& operator =(const iterator& src)
 163             {
 164                 m_pNode = src.m_pNode;
 165                 m_guard.copy( src.m_guard );
 166                 return *this;
 167             }
 168
 169             template <typename Bkoff, bool C>
 170             bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
 171             {
 172                 return m_pNode == i.m_pNode;
 173             }
 174             template <typename Bkoff, bool C>
 175             bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
 176             {
 177                 return !( *this == i );
 178             }
 179         };
 180     }}  // namespace skip_list::details
 181     //@endcond
 182
 183     /// Lock-free skip-list set
 184     /** @ingroup cds_intrusive_map
 185         @anchor cds_intrusive_SkipListSet_hp
 186
 187         The implementation of well-known probabilistic data structure called skip-list
 188         invented by W.Pugh in his papers:
 189             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
 190             - [1990] W.Pugh A Skip List Cookbook
 191
 192         A skip-list is a probabilistic data structure that provides expected logarithmic
 193         time search without the need of rebalance. The skip-list is a collection of sorted
 194         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
 195         Each list has a level, ranging from 0 to 32. The bottom-level list contains
 196         all the nodes, and each higher-level list is a sublist of the lower-level lists.
 197         Each node is created with a random top level (with a random height), and belongs
 198         to all lists up to that level. The probability that a node has the height 1 is 1/2.
 199         The probability that a node has the height N is 1/2 ** N (more precisely,
 200         the distribution depends on an random generator provided, but our generators
 201         have this property).
 202
 203         The lock-free variant of skip-list is implemented according to book
 204             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
 205                 chapter 14.4 "A Lock-Free Concurrent Skiplist".
 206
 207         <b>Template arguments</b>:
 208             - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for item type \p T, see \p skip_list::node.
 209             - \p T - type to be stored in the list. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
 210                 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
 211             - \p Traits - skip-list traits, default is \p skip_list::traits.
 212                 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction istead of \p Traits
 213                 template argument.
 214
 215         @warning The skip-list requires up to 67 hazard pointers that may be critical for some GCs for which
 216             the guard count is limited (like as \p gc::HP). Those GCs should be explicitly initialized with
 217             hazard pointer enough: \code cds::gc::HP myhp( 67 ) \endcode. Otherwise an run-time exception may be raised
 218             when you try to create skip-list object.
 219
 220         There are several specializations of \p %SkipListSet for each \p GC. You should include:
 221         - <tt><cds/intrusive/skip_list_hp.h></tt> for \p gc::HP garbage collector
 222         - <tt><cds/intrusive/skip_list_dhp.h></tt> for \p gc::DHP garbage collector
 223         - <tt><cds/intrusive/skip_list_nogc.h></tt> for \ref cds_intrusive_SkipListSet_nogc for append-only set
 224         - <tt><cds/intrusive/skip_list_rcu.h></tt> for \ref cds_intrusive_SkipListSet_rcu "RCU type"
 225
 226         <b>Iterators</b>
 227
 228         The class supports a forward iterator (\ref iterator and \ref const_iterator).
 229         The iteration is ordered.
 230         The iterator object is thread-safe: the element pointed by the iterator object is guarded,
 231         so, the element cannot be reclaimed while the iterator object is alive.
 232         However, passing an iterator object between threads is dangerous.
 233
 234         @warning Due to concurrent nature of skip-list set it is not guarantee that you can iterate
 235         all elements in the set: any concurrent deletion can exclude the element
 236         pointed by the iterator from the set, and your iteration can be terminated
 237         before end of the set. Therefore, such iteration is more suitable for debugging purpose only
 238
 239         Remember, each iterator object requires 2 additional hazard pointers, that may be
 240         a limited resource for \p GC like as \p gc::HP (for \p gc::DHP the count of
 241         guards is unlimited).
 242
 243         The iterator class supports the following minimalistic interface:
 244         \code
 245         struct iterator {
 246             // Default ctor
 247             iterator();
 248
 249             // Copy ctor
 250             iterator( iterator const& s);
 251
 252             value_type * operator ->() const;
 253             value_type& operator *() const;
 254
 255             // Pre-increment
 256             iterator& operator ++();
 257
 258             // Copy assignment
 259             iterator& operator = (const iterator& src);
 260
 261             bool operator ==(iterator const& i ) const;
 262             bool operator !=(iterator const& i ) const;
 263         };
 264         \endcode
 265         Note, the iterator object returned by \p end(), \p cend() member functions points to \p nullptr and should not be dereferenced.
 266
 267         <b>How to use</b>
 268
 269         You should incorporate \p skip_list::node into your struct \p T and provide
 270         appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
 271         define a struct based on \p skip_list::traits.
 272
 273         Example for \p gc::HP and base hook:
 274         \code
 275         // Include GC-related skip-list specialization
 276         #include <cds/intrusive/skip_list_hp.h>
 277
 278         // Data stored in skip list
 279         struct my_data: public cds::intrusive::skip_list::node< cds::gc::HP >
 280         {
 281             // key field
 282             std::string     strKey;
 283
 284             // other data
 285             // ...
 286         };
 287
 288         // my_data compare functor
 289         struct my_data_cmp {
 290             int operator()( const my_data& d1, const my_data& d2 )
 291             {
 292                 return d1.strKey.compare( d2.strKey );
 293             }
 294
 295             int operator()( const my_data& d, const std::string& s )
 296             {
 297                 return d.strKey.compare(s);
 298             }
 299
 300             int operator()( const std::string& s, const my_data& d )
 301             {
 302                 return s.compare( d.strKey );
 303             }
 304         };
 305
 306
 307         // Declare your traits
 308         struct my_traits: public cds::intrusive::skip_list::traits
 309         {
 310             typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > >   hook;
 311             typedef my_data_cmp compare;
 312         };
 313
 314         // Declare skip-list set type
 315         typedef cds::intrusive::SkipListSet< cds::gc::HP, my_data, my_traits >     traits_based_set;
 316         \endcode
 317
 318         Equivalent option-based code:
 319         \code
 320         // GC-related specialization
 321         #include <cds/intrusive/skip_list_hp.h>
 322
 323         struct my_data {
 324             // see above
 325         };
 326         struct compare {
 327             // see above
 328         };
 329
 330         // Declare option-based skip-list set
 331         typedef cds::intrusive::SkipListSet< cds::gc::HP
 332             ,my_data
 333             , typename cds::intrusive::skip_list::make_traits<
 334                 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::HP > > >
 335                 ,cds::intrusive::opt::compare< my_data_cmp >
 336             >::type
 337         > option_based_set;
 338
 339         \endcode
 340     */
 341     template <
 342         class GC
 343        ,typename T
 344 #ifdef CDS_DOXYGEN_INVOKED
 345        ,typename Traits = skip_list::traits
 346 #else
 347        ,typename Traits
 348 #endif
 349     >
 350     class SkipListSet
 351     {
 352     public:
 353         typedef GC      gc;         ///< Garbage collector
 354         typedef T       value_type; ///< type of value stored in the skip-list
 355         typedef Traits  traits;     ///< Traits template parameter
 356
 357         typedef typename traits::hook    hook;      ///< hook type
 358         typedef typename hook::node_type node_type; ///< node type
 359
 360 #   ifdef CDS_DOXYGEN_INVOKED
 361         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 362 #   else
 363         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 364 #   endif
 365
 366         typedef typename traits::disposer  disposer;   ///< item disposer
 367         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
 368
 369         typedef typename traits::item_counter  item_counter;   ///< Item counting policy
 370         typedef typename traits::memory_model  memory_model;   ///< Memory ordering, see \p cds::opt::memory_model option
 371         typedef typename traits::random_level_generator random_level_generator; ///< random level generator
 372         typedef typename traits::allocator     allocator_type;   ///< allocator for maintaining array of next pointers of the node
 373         typedef typename traits::back_off      back_off;   ///< Back-off strategy
 374         typedef typename traits::stat          stat;       ///< internal statistics type
 375
 376     public:
 377         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 378
 379         /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
 380         /**
 381             The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
 382             but it should be no more than 32 (\p skip_list::c_nHeightLimit).
 383         */
 384         static unsigned int const c_nMaxHeight = std::conditional<
 385             (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
 386             std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
 387             std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
 388         >::type::value;
 389
 390         //@cond
 391         static unsigned int const c_nMinHeight = 5;
 392         //@endcond
 393
 394         // c_nMaxHeight * 2 - pPred/pSucc guards
 395         // + 1 - for erase, unlink
 396         // + 1 - for clear
 397         // + 1 - for help_remove()
 398         static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list
 399
 400     protected:
 401         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr;   ///< Atomic marked node pointer
 402         typedef typename node_type::marked_ptr          marked_node_ptr;   ///< Node marked pointer
 403
 404     protected:
 405         //@cond
 406         typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
 407
 408         typedef typename std::conditional<
 409             std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
 410             ,intrusive_node_builder
 411             ,typename traits::internal_node_builder
 412         >::type node_builder;
 413
 414         typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
 415
 416         struct position {
 417             node_type *   pPrev[ c_nMaxHeight ];
 418             node_type *   pSucc[ c_nMaxHeight ];
 419
 420             typename gc::template GuardArray< c_nMaxHeight * 2 > guards;   ///< Guards array for pPrev/pSucc
 421             node_type *   pCur;   // guarded by one of guards
 422         };
 423         //@endcond
 424
 425     public:
 426         /// Default constructor
 427         /**
 428             The constructor checks whether the count of guards is enough
 429             for skip-list and may raise an exception if not.
 430         */
 431         SkipListSet()
 432             : m_Head( c_nMaxHeight )
 433             , m_nHeight( c_nMinHeight )
 434         {
 435             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 436
 437             gc::check_available_guards( c_nHazardPtrCount );
 438
 439             // Barrier for head node
 440             atomics::atomic_thread_fence( memory_model::memory_order_release );
 441         }
 442
 443         /// Clears and destructs the skip-list
 444         ~SkipListSet()
 445         {
 446             destroy();
 447         }
 448
 449     public:
 450     ///@name Forward iterators (only for debugging purpose)
 451     //@{
 452         /// Iterator type
 453         /**
 454             The forward iterator has some features:
 455             - it has no post-increment operator
 456             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
 457               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
 458               may be thrown if the limit of guard count per thread is exceeded.
 459             - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
 460             - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
 461               deleting operations there is no guarantee that you iterate all item in the list.
 462               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 463
 464             @warning Use this iterator on the concurrent container for debugging purpose only.
 465
 466             The iterator interface:
 467             \code
 468             class iterator {
 469             public:
 470                 // Default constructor
 471                 iterator();
 472
 473                 // Copy construtor
 474                 iterator( iterator const& src );
 475
 476                 // Dereference operator
 477                 value_type * operator ->() const;
 478
 479                 // Dereference operator
 480                 value_type& operator *() const;
 481
 482                 // Preincrement operator
 483                 iterator& operator ++();
 484
 485                 // Assignment operator
 486                 iterator& operator = (iterator const& src);
 487
 488                 // Equality operators
 489                 bool operator ==(iterator const& i ) const;
 490                 bool operator !=(iterator const& i ) const;
 491             };
 492             \endcode
 493         */
 494         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 495
 496         /// Const iterator type
 497         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 498
 499         /// Returns a forward iterator addressing the first element in a set
 500         iterator begin()
 501         {
 502             return iterator( *m_Head.head());
 503         }
 504
 505         /// Returns a forward const iterator addressing the first element in a set
 506         const_iterator begin() const
 507         {
 508             return const_iterator( *m_Head.head());
 509         }
 510         /// Returns a forward const iterator addressing the first element in a set
 511         const_iterator cbegin() const
 512         {
 513             return const_iterator( *m_Head.head());
 514         }
 515
 516         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 517         iterator end()
 518         {
 519             return iterator();
 520         }
 521
 522         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 523         const_iterator end() const
 524         {
 525             return const_iterator();
 526         }
 527         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 528         const_iterator cend() const
 529         {
 530             return const_iterator();
 531         }
 532     //@}
 533
 534     public:
 535         /// Inserts new node
 536         /**
 537             The function inserts \p val in the set if it does not contain
 538             an item with key equal to \p val.
 539
 540             Returns \p true if \p val is placed into the set, \p false otherwise.
 541         */
 542         bool insert( value_type& val )
 543         {
 544             return insert( val, []( value_type& ) {} );
 545         }
 546
 547         /// Inserts new node
 548         /**
 549             This function is intended for derived non-intrusive containers.
 550
 551             The function allows to split creating of new item into two part:
 552             - create item with key only
 553             - insert new item into the set
 554             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
 555
 556             The functor signature is:
 557             \code
 558                 void func( value_type& val );
 559             \endcode
 560             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
 561             \p val no any other changes could be made on this set's item by concurrent threads.
 562             The user-defined functor is called only if the inserting is success.
 563         */
 564         template <typename Func>
 565         bool insert( value_type& val, Func f )
 566         {
 567             typename gc::Guard gNew;
 568             gNew.assign( &val );
 569
 570             node_type * pNode = node_traits::to_node_ptr( val );
 571             scoped_node_ptr scp( pNode );
 572             unsigned int nHeight = pNode->height();
 573             bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
 574             bool bTowerMade = false;
 575
 576             position pos;
 577             while ( true )
 578             {
 579                 if ( find_position( val, pos, key_comparator(), true )) {
 580                     // scoped_node_ptr deletes the node tower if we create it
 581                     if ( !bTowerMade )
 582                         scp.release();
 583
 584                     m_Stat.onInsertFailed();
 585                     return false;
 586                 }
 587
 588                 if ( !bTowerOk ) {
 589                     build_node( pNode );
 590                     nHeight = pNode->height();
 591                     bTowerMade = pNode->has_tower();
 592                     bTowerOk = true;
 593                 }
 594
 595                 if ( !insert_at_position( val, pNode, pos, f )) {
 596                     m_Stat.onInsertRetry();
 597                     continue;
 598                 }
 599
 600                 increase_height( nHeight );
 601                 ++m_ItemCounter;
 602                 m_Stat.onAddNode( nHeight );
 603                 m_Stat.onInsertSuccess();
 604                 scp.release();
 605                 return true;
 606             }
 607         }
 608
 609         /// Updates the node
 610         /**
 611             The operation performs inserting or changing data with lock-free manner.
 612
 613             If the item \p val is not found in the set, then \p val is inserted into the set
 614             iff \p bInsert is \p true.
 615             Otherwise, the functor \p func is called with item found.
 616             The functor \p func signature is:
 617             \code
 618                 void func( bool bNew, value_type& item, value_type& val );
 619             \endcode
 620             with arguments:
 621             - \p bNew - \p true if the item has been inserted, \p false otherwise
 622             - \p item - item of the set
 623             - \p val - argument \p val passed into the \p %update() function
 624             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 625             refer to the same thing.
 626
 627             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 628             i.e. the node has been inserted or updated,
 629             \p second is \p true if new item has been added or \p false if the item with \p key
 630             already exists.
 631
 632             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 633         */
 634         template <typename Func>
 635         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
 636         {
 637             typename gc::Guard gNew;
 638             gNew.assign( &val );
 639
 640             node_type * pNode = node_traits::to_node_ptr( val );
 641             scoped_node_ptr scp( pNode );
 642             unsigned int nHeight = pNode->height();
 643             bool bTowerOk = pNode->has_tower();
 644             bool bTowerMade = false;
 645
 646             position pos;
 647             while ( true )
 648             {
 649                 bool bFound = find_position( val, pos, key_comparator(), true );
 650                 if ( bFound ) {
 651                     // scoped_node_ptr deletes the node tower if we create it before
 652                     if ( !bTowerMade )
 653                         scp.release();
 654
 655                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
 656                     m_Stat.onUpdateExist();
 657                     return std::make_pair( true, false );
 658                 }
 659
 660                 if ( !bInsert ) {
 661                     scp.release();
 662                     return std::make_pair( false, false );
 663                 }
 664
 665                 if ( !bTowerOk ) {
 666                     build_node( pNode );
 667                     nHeight = pNode->height();
 668                     bTowerMade = pNode->has_tower();
 669                     bTowerOk = true;
 670                 }
 671
 672                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
 673                     m_Stat.onInsertRetry();
 674                     continue;
 675                 }
 676
 677                 increase_height( nHeight );
 678                 ++m_ItemCounter;
 679                 scp.release();
 680                 m_Stat.onAddNode( nHeight );
 681                 m_Stat.onUpdateNew();
 682                 return std::make_pair( true, true );
 683             }
 684         }
 685         //@cond
 686         template <typename Func>
 687         CDS_DEPRECATED("ensure() is deprecated, use update()")
 688         std::pair<bool, bool> ensure( value_type& val, Func func )
 689         {
 690             return update( val, func, true );
 691         }
 692         //@endcond
 693
 694         /// Unlinks the item \p val from the set
 695         /**
 696             The function searches the item \p val in the set and unlink it from the set
 697             if it is found and is equal to \p val.
 698
 699             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
 700             and deletes the item found. \p %unlink() finds an item by key and deletes it
 701             only if \p val is an item of that set, i.e. the pointer to item found
 702             is equal to <tt> &val </tt>.
 703
 704             The \p disposer specified in \p Traits class template parameter is called
 705             by garbage collector \p GC asynchronously.
 706
 707             The function returns \p true if success and \p false otherwise.
 708         */
 709         bool unlink( value_type& val )
 710         {
 711             position pos;
 712
 713             if ( !find_position( val, pos, key_comparator(), false )) {
 714                 m_Stat.onUnlinkFailed();
 715                 return false;
 716             }
 717
 718             node_type * pDel = pos.pCur;
 719             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 720
 721             unsigned int nHeight = pDel->height();
 722             typename gc::Guard gDel;
 723             gDel.assign( node_traits::to_value_ptr(pDel));
 724
 725             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
 726                 --m_ItemCounter;
 727                 m_Stat.onRemoveNode( nHeight );
 728                 m_Stat.onUnlinkSuccess();
 729                 return true;
 730             }
 731
 732             m_Stat.onUnlinkFailed();
 733             return false;
 734         }
 735
 736         /// Extracts the item from the set with specified \p key
 737         /** \anchor cds_intrusive_SkipListSet_hp_extract
 738             The function searches an item with key equal to \p key in the set,
 739             unlinks it from the set, and returns it as \p guarded_ptr object.
 740             If \p key is not found the function returns an empty guarded pointer.
 741
 742             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 743
 744             The \p disposer specified in \p Traits class template parameter is called automatically
 745             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
 746             will be destroyed or released.
 747             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 748
 749             Usage:
 750             \code
 751             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 752             skip_list theList;
 753             // ...
 754             {
 755                 skip_list::guarded_ptr gp(theList.extract( 5 ));
 756                 if ( gp ) {
 757                     // Deal with gp
 758                     // ...
 759                 }
 760                 // Destructor of gp releases internal HP guard
 761             }
 762             \endcode
 763         */
 764         template <typename Q>
 765         guarded_ptr extract( Q const& key )
 766         {
 767             return extract_( key, key_comparator());
 768         }
 769
 770         /// Extracts the item from the set with comparing functor \p pred
 771         /**
 772             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
 773             but \p pred predicate is used for key comparing.
 774
 775             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 776             in any order.
 777             \p pred must imply the same element order as the comparator used for building the set.
 778         */
 779         template <typename Q, typename Less>
 780         guarded_ptr extract_with( Q const& key, Less pred )
 781         {
 782             CDS_UNUSED( pred );
 783             return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
 784         }
 785
 786         /// Extracts an item with minimal key from the list
 787         /**
 788             The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
 789             If the skip-list is empty the function returns an empty guarded pointer.
 790
 791             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
 792             It means that the function gets leftmost item and tries to unlink it.
 793             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
 794             So, the function returns the item with minimum key at the moment of list traversing.
 795
 796             The \p disposer specified in \p Traits class template parameter is called
 797             by garbage collector \p GC automatically when returned \p guarded_ptr object
 798             will be destroyed or released.
 799             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 800
 801             Usage:
 802             \code
 803             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
 804             skip_list theList;
 805             // ...
 806             {
 807                 skip_list::guarded_ptr gp(theList.extract_min());
 808                 if ( gp ) {
 809                     // Deal with gp
 810                     //...
 811                 }
 812                 // Destructor of gp releases internal HP guard
 813             }
 814             \endcode
 815         */
 816         guarded_ptr extract_min()
 817         {
 818             return extract_min_();
 819         }
 820
 821         /// Extracts an item with maximal key from the list
 822         /**
 823             The function searches an item with maximal key, unlinks it, and returns the pointer to item
 824             as \p guarded_ptr object.
 825             If the skip-list is empty the function returns an empty \p guarded_ptr.
 826
 827             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
 828             It means that the function gets rightmost item and tries to unlink it.
 829             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
 830             So, the function returns the item with maximum key at the moment of list traversing.
 831
 832             The \p disposer specified in \p Traits class template parameter is called
 833             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
 834             will be destroyed or released.
 835             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
 836
 837             Usage:
 838             \code
 839             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
 840             skip_list theList;
 841             // ...
 842             {
 843                 skip_list::guarded_ptr gp( theList.extract_max( gp ));
 844                 if ( gp ) {
 845                     // Deal with gp
 846                     //...
 847                 }
 848                 // Destructor of gp releases internal HP guard
 849             }
 850             \endcode
 851         */
 852         guarded_ptr extract_max()
 853         {
 854             return extract_max_();
 855         }
 856
 857         /// Deletes the item from the set
 858         /** \anchor cds_intrusive_SkipListSet_hp_erase
 859             The function searches an item with key equal to \p key in the set,
 860             unlinks it from the set, and returns \p true.
 861             If the item with key equal to \p key is not found the function return \p false.
 862
 863             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 864         */
 865         template <typename Q>
 866         bool erase( Q const& key )
 867         {
 868             return erase_( key, key_comparator(), [](value_type const&) {} );
 869         }
 870
 871         /// Deletes the item from the set with comparing functor \p pred
 872         /**
 873             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
 874             but \p pred predicate is used for key comparing.
 875
 876             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 877             in any order.
 878             \p pred must imply the same element order as the comparator used for building the set.
 879         */
 880         template <typename Q, typename Less>
 881         bool erase_with( Q const& key, Less pred )
 882         {
 883             CDS_UNUSED( pred );
 884             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
 885         }
 886
 887         /// Deletes the item from the set
 888         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
 889             The function searches an item with key equal to \p key in the set,
 890             call \p f functor with item found, unlinks it from the set, and returns \p true.
 891             The \ref disposer specified in \p Traits class template parameter is called
 892             by garbage collector \p GC asynchronously.
 893
 894             The \p Func interface is
 895             \code
 896             struct functor {
 897                 void operator()( value_type const& item );
 898             };
 899             \endcode
 900
 901             If the item with key equal to \p key is not found the function return \p false.
 902
 903             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
 904         */
 905         template <typename Q, typename Func>
 906         bool erase( Q const& key, Func f )
 907         {
 908             return erase_( key, key_comparator(), f );
 909         }
 910
 911         /// Deletes the item from the set with comparing functor \p pred
 912         /**
 913             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
 914             but \p pred predicate is used for key comparing.
 915
 916             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 917             in any order.
 918             \p pred must imply the same element order as the comparator used for building the set.
 919         */
 920         template <typename Q, typename Less, typename Func>
 921         bool erase_with( Q const& key, Less pred, Func f )
 922         {
 923             CDS_UNUSED( pred );
 924             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 925         }
 926
 927         /// Finds \p key
 928         /** \anchor cds_intrusive_SkipListSet_hp_find_func
 929             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 930             The interface of \p Func functor is:
 931             \code
 932             struct functor {
 933                 void operator()( value_type& item, Q& key );
 934             };
 935             \endcode
 936             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 937
 938             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 939             that \p item cannot be disposed during functor is executing.
 940             The functor does not serialize simultaneous access to the set \p item. If such access is
 941             possible you must provide your own synchronization on item level to exclude unsafe item modifications.
 942
 943             Note the compare functor specified for class \p Traits template parameter
 944             should accept a parameter of type \p Q that can be not the same as \p value_type.
 945
 946             The function returns \p true if \p key is found, \p false otherwise.
 947         */
 948         template <typename Q, typename Func>
 949         bool find( Q& key, Func f )
 950         {
 951             return find_with_( key, key_comparator(), f );
 952         }
 953         //@cond
 954         template <typename Q, typename Func>
 955         bool find( Q const& key, Func f )
 956         {
 957             return find_with_( key, key_comparator(), f );
 958         }
 959         //@endcond
 960
 961         /// Finds the key \p key with \p pred predicate for comparing
 962         /**
 963             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
 964             but \p pred is used for key compare.
 965
 966             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
 967             in any order.
 968             \p pred must imply the same element order as the comparator used for building the set.
 969         */
 970         template <typename Q, typename Less, typename Func>
 971         bool find_with( Q& key, Less pred, Func f )
 972         {
 973             CDS_UNUSED( pred );
 974             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 975         }
 976         //@cond
 977         template <typename Q, typename Less, typename Func>
 978         bool find_with( Q const& key, Less pred, Func f )
 979         {
 980             CDS_UNUSED( pred );
 981             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
 982         }
 983         //@endcond
 984
 985         /// Checks whether the set contains \p key
 986         /**
 987             The function searches the item with key equal to \p key
 988             and returns \p true if it is found, and \p false otherwise.
 989         */
 990         template <typename Q>
 991         bool contains( Q const& key )
 992         {
 993             return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
 994         }
 995         //@cond
 996         template <typename Q>
 997         CDS_DEPRECATED("deprecated, use contains()")
 998         bool find( Q const& key )
 999         {
1000             return contains( key );
1001         }
1002         //@endcond
1003
1004         /// Checks whether the set contains \p key using \p pred predicate for searching
1005         /**
1006             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1007             \p Less functor has the interface like \p std::less.
1008             \p Less must imply the same element order as the comparator used for building the set.
1009         */
1010         template <typename Q, typename Less>
1011         bool contains( Q const& key, Less pred )
1012         {
1013             CDS_UNUSED( pred );
1014             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1015         }
1016         //@cond
1017         template <typename Q, typename Less>
1018         CDS_DEPRECATED("deprecated, use contains()")
1019         bool find_with( Q const& key, Less pred )
1020         {
1021             return contains( key, pred );
1022         }
1023         //@endcond
1024
1025         /// Finds \p key and return the item found
1026         /** \anchor cds_intrusive_SkipListSet_hp_get
1027             The function searches the item with key equal to \p key
1028             and returns the pointer to the item found as \p guarded_ptr.
1029             If \p key is not found the function returns an empt guarded pointer.
1030
1031             The \p disposer specified in \p Traits class template parameter is called
1032             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1033             will be destroyed or released.
1034             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1035
1036             Usage:
1037             \code
1038             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1039             skip_list theList;
1040             // ...
1041             {
1042                 skip_list::guarded_ptr gp(theList.get( 5 ));
1043                 if ( gp ) {
1044                     // Deal with gp
1045                     //...
1046                 }
1047                 // Destructor of guarded_ptr releases internal HP guard
1048             }
1049             \endcode
1050
1051             Note the compare functor specified for class \p Traits template parameter
1052             should accept a parameter of type \p Q that can be not the same as \p value_type.
1053         */
1054         template <typename Q>
1055         guarded_ptr get( Q const& key )
1056         {
1057             return get_with_( key, key_comparator());
1058         }
1059
1060         /// Finds \p key and return the item found
1061         /**
1062             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1063             but \p pred is used for comparing the keys.
1064
1065             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1066             in any order.
1067             \p pred must imply the same element order as the comparator used for building the set.
1068         */
1069         template <typename Q, typename Less>
1070         guarded_ptr get_with( Q const& key, Less pred )
1071         {
1072             CDS_UNUSED( pred );
1073             return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
1074         }
1075
1076         /// Returns item count in the set
1077         /**
1078             The value returned depends on item counter type provided by \p Traits template parameter.
1079             If it is \p atomicity::empty_item_counter this function always returns 0.
1080             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1081             for this purpose.
1082         */
1083         size_t size() const
1084         {
1085             return m_ItemCounter;
1086         }
1087
1088         /// Checks if the set is empty
1089         bool empty() const
1090         {
1091             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1092         }
1093
1094         /// Clears the set (not atomic)
1095         /**
1096             The function unlink all items from the set.
1097             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1098             this sequence
1099             \code
1100             set.clear();
1101             assert( set.empty());
1102             \endcode
1103             the assertion could be raised.
1104
1105             For each item the \ref disposer will be called after unlinking.
1106         */
1107         void clear()
1108         {
1109             while ( extract_min_());
1110         }
1111
1112         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1113         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1114         {
1115             return c_nMaxHeight;
1116         }
1117
1118         /// Returns const reference to internal statistics
1119         stat const& statistics() const
1120         {
1121             return m_Stat;
1122         }
1123
1124     protected:
1125         //@cond
1126         unsigned int random_level()
1127         {
1128             // Random generator produces a number from range [0..31]
1129             // We need a number from range [1..32]
1130             return m_RandomLevelGen() + 1;
1131         }
1132
1133         template <typename Q>
1134         node_type * build_node( Q v )
1135         {
1136             return node_builder::make_tower( v, m_RandomLevelGen );
1137         }
1138
1139         static value_type * gc_protect( marked_node_ptr p )
1140         {
1141             return node_traits::to_value_ptr( p.ptr() );
1142         }
1143
1144         static void dispose_node( value_type * pVal )
1145         {
1146             assert( pVal != nullptr );
1147             typename node_builder::node_disposer()( node_traits::to_node_ptr( pVal ) );
1148             disposer()( pVal );
1149         }
1150
1151         void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc )
1152         {
1153             marked_node_ptr p( pCur.ptr() );
1154
1155             if ( pCur->is_upper_level( nLevel )) {
1156                 typename gc::Guard hp;
1157                 if ( hp.protect( pCur->next( nLevel ), gc_protect ) == pSucc &&
1158                      pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
1159                         memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1160                 {
1161                     if ( pCur->level_unlinked() ) {
1162                         gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
1163                         m_Stat.onEraseWhileFind();
1164                     }
1165                 }
1166             }
1167         }
1168
1169         template <typename Q, typename Compare >
1170         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
1171         {
1172             node_type * pPred;
1173             marked_node_ptr pSucc;
1174             marked_node_ptr pCur;
1175
1176             // Hazard pointer array:
1177             //  pPred: [nLevel * 2]
1178             //  pSucc: [nLevel * 2 + 1]
1179
1180         retry:
1181             pPred = m_Head.head();
1182             int nCmp = 1;
1183
1184             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1185                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1186                 while ( true ) {
1187                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1188                     if ( pCur.bits() ) {
1189                         // pCur.bits() means that pPred is logically deleted
1190                         goto retry;
1191                     }
1192
1193                     if ( pCur.ptr() == nullptr ) {
1194                         // end of list at level nLevel - goto next level
1195                         break;
1196                     }
1197
1198                     // pSucc contains deletion mark for pCur
1199                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1200
1201                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1202                         goto retry;
1203
1204                     if ( pSucc.bits() ) {
1205                         // pCur is marked, i.e. logically deleted
1206                         // try to help deleting pCur
1207                         help_remove( nLevel, pPred, pCur, pSucc );
1208                         goto retry;
1209                     }
1210                     else {
1211                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1212                         if ( nCmp < 0 ) {
1213                             pPred = pCur.ptr();
1214                             pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );   // pPrev guard := cur guard
1215                         }
1216                         else if ( nCmp == 0 && bStopIfFound )
1217                             goto found;
1218                         else
1219                             break;
1220                     }
1221                 }
1222
1223                 // Next level
1224                 pos.pPrev[nLevel] = pPred;
1225                 pos.pSucc[nLevel] = pCur.ptr();
1226             }
1227
1228             if ( nCmp != 0 )
1229                 return false;
1230
1231         found:
1232             pos.pCur = pCur.ptr();
1233             return pCur.ptr() && nCmp == 0;
1234         }
1235
1236         bool find_min_position( position& pos )
1237         {
1238             node_type * pPred;
1239             marked_node_ptr pSucc;
1240             marked_node_ptr pCur;
1241
1242             // Hazard pointer array:
1243             //  pPred: [nLevel * 2]
1244             //  pSucc: [nLevel * 2 + 1]
1245
1246         retry:
1247             pPred = m_Head.head();
1248
1249             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1250                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1251                 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1252
1253                 // pCur.bits() means that pPred is logically deleted
1254                 // head cannot be deleted
1255                 assert( pCur.bits() == 0 );
1256
1257                 if ( pCur.ptr() ) {
1258
1259                     // pSucc contains deletion mark for pCur
1260                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1261
1262                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1263                         goto retry;
1264
1265                     if ( pSucc.bits() ) {
1266                         // pCur is marked, i.e. logically deleted.
1267                         // try to help deleting pCur
1268                         help_remove( nLevel, pPred, pCur, pSucc );
1269                         goto retry;
1270                     }
1271                 }
1272
1273                 // Next level
1274                 pos.pPrev[nLevel] = pPred;
1275                 pos.pSucc[nLevel] = pCur.ptr();
1276             }
1277
1278             return ( pos.pCur = pCur.ptr() ) != nullptr;
1279         }
1280
1281         bool find_max_position( position& pos )
1282         {
1283             node_type * pPred;
1284             marked_node_ptr pSucc;
1285             marked_node_ptr pCur;
1286
1287             // Hazard pointer array:
1288             //  pPred: [nLevel * 2]
1289             //  pSucc: [nLevel * 2 + 1]
1290
1291         retry:
1292             pPred = m_Head.head();
1293
1294             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
1295                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) );
1296                 while ( true ) {
1297                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
1298                     if ( pCur.bits() ) {
1299                         // pCur.bits() means that pPred is logically deleted
1300                         goto retry;
1301                     }
1302
1303                     if ( pCur.ptr() == nullptr ) {
1304                         // end of the list at level nLevel - goto next level
1305                         break;
1306                     }
1307
1308                     // pSucc contains deletion mark for pCur
1309                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
1310
1311                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
1312                         goto retry;
1313
1314                     if ( pSucc.bits() ) {
1315                         // pCur is marked, i.e. logically deleted.
1316                         // try to help deleting pCur
1317                         help_remove( nLevel, pPred, pCur, pSucc );
1318                         goto retry;
1319                     }
1320                     else {
1321                         if ( !pSucc.ptr() )
1322                             break;
1323
1324                         pPred = pCur.ptr();
1325                         pos.guards.copy( nLevel * 2, nLevel * 2 + 1 );
1326                     }
1327                 }
1328
1329                 // Next level
1330                 pos.pPrev[nLevel] = pPred;
1331                 pos.pSucc[nLevel] = pCur.ptr();
1332             }
1333
1334             return ( pos.pCur = pCur.ptr() ) != nullptr;
1335         }
1336
1337         template <typename Func>
1338         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
1339         {
1340             unsigned int const nHeight = pNode->height();
1341
1342             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
1343                 pNode->next( nLevel ).store( marked_node_ptr(), memory_model::memory_order_relaxed );
1344
1345             // Insert at level 0
1346             {
1347                 marked_node_ptr p( pos.pSucc[0] );
1348                 pNode->next( 0 ).store( p, memory_model::memory_order_relaxed );
1349                 if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
1350                     return false;
1351
1352                 f( val );
1353             }
1354
1355             // Insert at level 1..max
1356             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
1357                 marked_node_ptr p;
1358                 while ( true ) {
1359                     marked_node_ptr pSucc( pos.pSucc[nLevel] );
1360
1361                     // Set pNode->next
1362                     // pNode->next must be null but can have a "logical deleted" flag if another thread is removing pNode right now
1363                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc,
1364                         memory_model::memory_order_acq_rel, atomics::memory_order_acquire ) )
1365                     {
1366                         // pNode has been marked as removed while we are inserting it
1367                         // Stop inserting
1368                         assert( p.bits() != 0 );
1369                         if ( pNode->level_unlinked( nHeight - nLevel ))
1370                             gc::retire( &val, dispose_node );
1371                         m_Stat.onLogicDeleteWhileInsert();
1372                         return true;
1373                     }
1374                     p = pSucc;
1375
1376                     // Link pNode into the list at nLevel
1377                     if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( pSucc, marked_node_ptr( pNode ),
1378                         memory_model::memory_order_release, atomics::memory_order_relaxed ))
1379                     {
1380                         // go to next level
1381                         break;
1382                     }
1383
1384                     // Renew insert position
1385                     m_Stat.onRenewInsertPosition();
1386                     if ( !find_position( val, pos, key_comparator(), false )) {
1387                         // The node has been deleted while we are inserting it
1388                         m_Stat.onNotFoundWhileInsert();
1389                         return true;
1390                     }
1391                 }
1392             }
1393             return true;
1394         }
1395
1396         template <typename Func>
1397         bool try_remove_at( node_type * pDel, position& pos, Func f )
1398         {
1399             assert( pDel != nullptr );
1400
1401             marked_node_ptr pSucc;
1402             back_off bkoff;
1403
1404             // logical deletion (marking)
1405             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
1406                 pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1407                 if ( pSucc.bits() == 0 ) {
1408                     bkoff.reset();
1409                     while ( !( pDel->next( nLevel ).compare_exchange_weak( pSucc, pSucc | 1,
1410                         memory_model::memory_order_release, atomics::memory_order_acquire )
1411                         || pSucc.bits() != 0 ))
1412                     {
1413                         bkoff();
1414                         m_Stat.onMarkFailed();
1415                     }
1416                 }
1417             }
1418
1419             marked_node_ptr p( pDel->next( 0 ).load( memory_model::memory_order_relaxed ).ptr());
1420             while ( true ) {
1421                 if ( pDel->next( 0 ).compare_exchange_strong( p, p | 1, memory_model::memory_order_release, atomics::memory_order_acquire ))
1422                 {
1423                     f( *node_traits::to_value_ptr( pDel ) );
1424
1425                     // Physical deletion
1426                     // try fast erase
1427                     p = pDel;
1428
1429                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
1430
1431                         pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed );
1432                         if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
1433                             memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
1434                         {
1435                             pDel->level_unlinked();
1436                         }
1437                         else {
1438                             // Make slow erase
1439                             find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
1440                             m_Stat.onSlowErase();
1441                             return true;
1442                         }
1443                     }
1444
1445                     // Fast erasing success
1446                     gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
1447                     m_Stat.onFastErase();
1448                     return true;
1449                 }
1450                 else if ( p.bits()) {
1451                     // Another thread is deleting pDel right now
1452                     m_Stat.onEraseContention();
1453                     return false;
1454                 }
1455                 m_Stat.onEraseRetry();
1456                 bkoff();
1457             }
1458         }
1459
1460         enum finsd_fastpath_result {
1461             find_fastpath_found,
1462             find_fastpath_not_found,
1463             find_fastpath_abort
1464         };
1465         template <typename Q, typename Compare, typename Func>
1466         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
1467         {
1468             node_type * pPred;
1469             marked_node_ptr pCur;
1470             marked_node_ptr pNull;
1471
1472             // guard array:
1473             // 0 - pPred on level N
1474             // 1 - pCur on level N
1475             typename gc::template GuardArray<2> guards;
1476             back_off bkoff;
1477             unsigned attempt = 0;
1478
1479         try_again:
1480             pPred = m_Head.head();
1481             for ( int nLevel = static_cast<int>( m_nHeight.load( memory_model::memory_order_relaxed ) - 1 ); nLevel >= 0; --nLevel ) {
1482                 pCur = guards.protect( 1, pPred->next( nLevel ), gc_protect );
1483
1484                 while ( pCur != pNull ) {
1485                     if ( pCur.bits() ) {
1486                         // pPred is being removed
1487                         if ( ++attempt < 4 ) {
1488                             bkoff();
1489                             goto try_again;
1490                         }
1491
1492                         return find_fastpath_abort;
1493                     }
1494
1495                     if ( pCur.ptr() ) {
1496                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
1497                         if ( nCmp < 0 ) {
1498                             guards.copy( 0, 1 );
1499                             pPred = pCur.ptr();
1500                             pCur = guards.protect( 1, pCur->next( nLevel ), gc_protect );
1501                         }
1502                         else if ( nCmp == 0 ) {
1503                             // found
1504                             f( *node_traits::to_value_ptr( pCur.ptr() ), val );
1505                             return find_fastpath_found;
1506                         }
1507                         else {
1508                             // pCur > val - go down
1509                             break;
1510                         }
1511                     }
1512                 }
1513             }
1514
1515             return find_fastpath_not_found;
1516         }
1517
1518         template <typename Q, typename Compare, typename Func>
1519         bool find_slowpath( Q& val, Compare cmp, Func f )
1520         {
1521             position pos;
1522             if ( find_position( val, pos, cmp, true ) ) {
1523                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1524
1525                 f( *node_traits::to_value_ptr( pos.pCur ), val );
1526                 return true;
1527             }
1528             else
1529                 return false;
1530         }
1531
1532         template <typename Q, typename Compare, typename Func>
1533         bool find_with_( Q& val, Compare cmp, Func f )
1534         {
1535             switch ( find_fastpath( val, cmp, f ) ) {
1536             case find_fastpath_found:
1537                 m_Stat.onFindFastSuccess();
1538                 return true;
1539             case find_fastpath_not_found:
1540                 m_Stat.onFindFastFailed();
1541                 return false;
1542             default:
1543                 break;
1544             }
1545
1546             if ( find_slowpath( val, cmp, f ) ) {
1547                 m_Stat.onFindSlowSuccess();
1548                 return true;
1549             }
1550
1551             m_Stat.onFindSlowFailed();
1552             return false;
1553         }
1554
1555         template <typename Q, typename Compare>
1556         guarded_ptr get_with_( Q const& val, Compare cmp )
1557         {
1558             guarded_ptr gp;
1559             if ( find_with_( val, cmp, [&gp]( value_type& found, Q const& ) { gp.reset( &found ); } ) )
1560                 return gp;
1561             return guarded_ptr();
1562         }
1563
1564         template <typename Q, typename Compare, typename Func>
1565         bool erase_( Q const& val, Compare cmp, Func f )
1566         {
1567             position pos;
1568
1569             if ( !find_position( val, pos, cmp, false ) ) {
1570                 m_Stat.onEraseFailed();
1571                 return false;
1572             }
1573
1574             node_type * pDel = pos.pCur;
1575             typename gc::Guard gDel;
1576             gDel.assign( node_traits::to_value_ptr( pDel ) );
1577             assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1578
1579             unsigned int nHeight = pDel->height();
1580             if ( try_remove_at( pDel, pos, f ) ) {
1581                 --m_ItemCounter;
1582                 m_Stat.onRemoveNode( nHeight );
1583                 m_Stat.onEraseSuccess();
1584                 return true;
1585             }
1586
1587             m_Stat.onEraseFailed();
1588             return false;
1589         }
1590
1591         template <typename Q, typename Compare>
1592         guarded_ptr extract_( Q const& val, Compare cmp )
1593         {
1594             position pos;
1595
1596             guarded_ptr gp;
1597             for (;;) {
1598                 if ( !find_position( val, pos, cmp, false ) ) {
1599                     m_Stat.onExtractFailed();
1600                     return guarded_ptr();
1601                 }
1602
1603                 node_type * pDel = pos.pCur;
1604                 gp.reset( node_traits::to_value_ptr( pDel ) );
1605                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1606
1607                 unsigned int nHeight = pDel->height();
1608                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1609                     --m_ItemCounter;
1610                     m_Stat.onRemoveNode( nHeight );
1611                     m_Stat.onExtractSuccess();
1612                     return gp;
1613                 }
1614                 m_Stat.onExtractRetry();
1615             }
1616         }
1617
1618         guarded_ptr extract_min_()
1619         {
1620             position pos;
1621
1622             guarded_ptr gp;
1623             for ( ;;) {
1624                 if ( !find_min_position( pos ) ) {
1625                     // The list is empty
1626                     m_Stat.onExtractMinFailed();
1627                     return guarded_ptr();
1628                 }
1629
1630                 node_type * pDel = pos.pCur;
1631
1632                 unsigned int nHeight = pDel->height();
1633                 gp.reset( node_traits::to_value_ptr( pDel ) );
1634
1635                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1636                     --m_ItemCounter;
1637                     m_Stat.onRemoveNode( nHeight );
1638                     m_Stat.onExtractMinSuccess();
1639                     return gp;
1640                 }
1641
1642                 m_Stat.onExtractMinRetry();
1643             }
1644         }
1645
1646         guarded_ptr extract_max_()
1647         {
1648             position pos;
1649
1650             guarded_ptr gp;
1651             for ( ;;) {
1652                 if ( !find_max_position( pos ) ) {
1653                     // The list is empty
1654                     m_Stat.onExtractMaxFailed();
1655                     return guarded_ptr();
1656                 }
1657
1658                 node_type * pDel = pos.pCur;
1659
1660                 unsigned int nHeight = pDel->height();
1661                 gp.reset( node_traits::to_value_ptr( pDel ) );
1662
1663                 if ( try_remove_at( pDel, pos, []( value_type const& ) {} ) ) {
1664                     --m_ItemCounter;
1665                     m_Stat.onRemoveNode( nHeight );
1666                     m_Stat.onExtractMaxSuccess();
1667                     return gp;
1668                 }
1669
1670                 m_Stat.onExtractMaxRetry();
1671             }
1672         }
1673
1674         void increase_height( unsigned int nHeight )
1675         {
1676             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1677             if ( nCur < nHeight )
1678                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
1679         }
1680
1681         void destroy()
1682         {
1683             node_type* p = m_Head.head()->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1684             while ( p ) {
1685                 node_type* pNext = p->next( 0 ).load( atomics::memory_order_relaxed ).ptr();
1686                 dispose_node( node_traits::to_value_ptr( p ));
1687                 p = pNext;
1688             }
1689         }
1690
1691         //@endcond
1692
1693     private:
1694         //@cond
1695         skip_list::details::head_node< node_type > m_Head;   ///< head tower (max height)
1696
1697         item_counter                m_ItemCounter;    ///< item counter
1698         random_level_generator      m_RandomLevelGen; ///< random level generator instance
1699         atomics::atomic<unsigned int> m_nHeight;      ///< estimated high level
1700         mutable stat                m_Stat;           ///< internal statistics
1701         //@endcond
1702     };
1703
1704 }} // namespace cds::intrusive
1705
1706
1707 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H