cds/intrusive/impl/skip_list.h

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