cds/intrusive/impl/skip_list.h

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