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
  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 ensure()
 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_relaxed );
 461
 462                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).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_release, 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_relaxed );
 529
 530                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).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_release, atomics::memory_order_relaxed ))
 538                         {
 539                             if ( nLevel == 0 )
 540                                 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
 541                         }
 542                         goto retry;
 543                     }
 544                 }
 545
 546                 // Next level
 547                 pos.pPrev[ nLevel ] = pPred;
 548                 pos.pSucc[ nLevel ] = pCur.ptr();
 549             }
 550
 551             return (pos.pCur = pCur.ptr()) != nullptr;
 552         }
 553
 554         bool find_max_position( position& pos )
 555         {
 556             node_type * pPred;
 557             marked_node_ptr pSucc;
 558             marked_node_ptr pCur;
 559
 560             // Hazard pointer array:
 561             //  pPred: [nLevel * 2]
 562             //  pSucc: [nLevel * 2 + 1]
 563
 564         retry:
 565             pPred = m_Head.head();
 566
 567             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
 568                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
 569                 while ( true ) {
 570                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
 571                     if ( pCur.bits() ) {
 572                         // pCur.bits() means that pPred is logically deleted
 573                         goto retry;
 574                     }
 575
 576                     if ( pCur.ptr() == nullptr ) {
 577                         // end of the list at level nLevel - goto next level
 578                         break;
 579                     }
 580
 581                     // pSucc contains deletion mark for pCur
 582                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 583
 584                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 585                         goto retry;
 586
 587                     if ( pSucc.bits() ) {
 588                         // pCur is marked, i.e. logically deleted.
 589                         marked_node_ptr p( pCur.ptr() );
 590                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 591                             memory_model::memory_order_release, atomics::memory_order_relaxed ))
 592                         {
 593                             if ( nLevel == 0 )
 594                                 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
 595                         }
 596                         goto retry;
 597                     }
 598                     else {
 599                         if ( !pSucc.ptr() )
 600                             break;
 601
 602                         pPred = pCur.ptr();
 603                         pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
 604                         //pos.guards.copy( nLevel * 2, gCur ) ;   // pPrev guard := gCur
 605                     }
 606                 }
 607
 608                 // Next level
 609                 pos.pPrev[ nLevel ] = pPred;
 610                 pos.pSucc[ nLevel ] = pCur.ptr();
 611             }
 612
 613             return (pos.pCur = pCur.ptr()) != nullptr;
 614         }
 615
 616         template <typename Func>
 617         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 618         {
 619             unsigned int nHeight = pNode->height();
 620
 621             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
 622                 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
 623
 624             {
 625                 marked_node_ptr p( pos.pSucc[0] );
 626                 pNode->next( 0 ).store( p, memory_model::memory_order_release );
 627                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
 628                     return false;
 629                 }
 630                 f( val );
 631             }
 632
 633             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 634                 marked_node_ptr p;
 635                 while ( true ) {
 636                     marked_node_ptr q( pos.pSucc[ nLevel ]);
 637                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 638                         // pNode has been marked as removed while we are inserting it
 639                         // Stop inserting
 640                         assert( p.bits() );
 641                         m_Stat.onLogicDeleteWhileInsert();
 642                         return true;
 643                     }
 644                     p = q;
 645                     if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
 646                         break;
 647
 648                     // Renew insert position
 649                     m_Stat.onRenewInsertPosition();
 650                     if ( !find_position( val, pos, key_comparator(), false )) {
 651                         // The node has been deleted while we are inserting it
 652                         m_Stat.onNotFoundWhileInsert();
 653                         return true;
 654                     }
 655                 }
 656             }
 657             return true;
 658         }
 659
 660         template <typename Func>
 661         bool try_remove_at( node_type * pDel, position& pos, Func f )
 662         {
 663             assert( pDel != nullptr );
 664
 665             marked_node_ptr pSucc;
 666             typename gc::Guard gSucc;
 667
 668             // logical deletion (marking)
 669             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
 670                 while ( true ) {
 671                     pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
 672                     if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
 673                          memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
 674                     {
 675                         break;
 676                     }
 677                 }
 678             }
 679
 680             while ( true ) {
 681                 pSucc = gSucc.protect( pDel->next(0), gc_protect );
 682                 marked_node_ptr p( pSucc.ptr() );
 683                 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
 684                      memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
 685                 {
 686                     f( *node_traits::to_value_ptr( pDel ));
 687
 688                     // Physical deletion
 689                     // try fast erase
 690                     p = pDel;
 691                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
 692                         pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
 693                         if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
 694                             memory_model::memory_order_release, atomics::memory_order_relaxed) )
 695                         {
 696                             // Make slow erase
 697                             find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
 698                             m_Stat.onSlowErase();
 699                             return true;
 700                         }
 701                     }
 702
 703                     // Fast erasing success
 704                     gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
 705                     m_Stat.onFastErase();
 706                     return true;
 707                 }
 708                 else {
 709                     if ( p.bits() ) {
 710                         return false;
 711                     }
 712                 }
 713             }
 714         }
 715
 716         enum finsd_fastpath_result {
 717             find_fastpath_found,
 718             find_fastpath_not_found,
 719             find_fastpath_abort
 720         };
 721         template <typename Q, typename Compare, typename Func>
 722         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
 723         {
 724             node_type * pPred;
 725             typename gc::template GuardArray<2>  guards;
 726             marked_node_ptr pCur;
 727             marked_node_ptr pNull;
 728
 729             back_off bkoff;
 730
 731             pPred = m_Head.head();
 732             for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
 733                 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
 734                 if ( pCur == pNull )
 735                     continue;
 736
 737                 while ( pCur != pNull ) {
 738                     if ( pCur.bits() ) {
 739                         unsigned int nAttempt = 0;
 740                         while ( pCur.bits() && nAttempt++ < 16 ) {
 741                             bkoff();
 742                             pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
 743                         }
 744                         bkoff.reset();
 745
 746                         if ( pCur.bits() ) {
 747                             // Maybe, we are on deleted node sequence
 748                             // Abort searching, try slow-path
 749                             return find_fastpath_abort;
 750                         }
 751                     }
 752
 753                     if ( pCur.ptr() ) {
 754                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
 755                         if ( nCmp < 0 ) {
 756                             guards.copy( 0, 1 );
 757                             pPred = pCur.ptr();
 758                             pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
 759                         }
 760                         else if ( nCmp == 0 ) {
 761                             // found
 762                             f( *node_traits::to_value_ptr( pCur.ptr() ), val );
 763                             return find_fastpath_found;
 764                         }
 765                         else // pCur > val - go down
 766                             break;
 767                     }
 768                 }
 769             }
 770
 771             return find_fastpath_not_found;
 772         }
 773
 774         template <typename Q, typename Compare, typename Func>
 775         bool find_slowpath( Q& val, Compare cmp, Func f )
 776         {
 777             position pos;
 778             if ( find_position( val, pos, cmp, true )) {
 779                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 780
 781                 f( *node_traits::to_value_ptr( pos.pCur ), val );
 782                 return true;
 783             }
 784             else
 785                 return false;
 786         }
 787
 788         template <typename Q, typename Compare, typename Func>
 789         bool find_with_( Q& val, Compare cmp, Func f )
 790         {
 791             switch ( find_fastpath( val, cmp, f )) {
 792             case find_fastpath_found:
 793                 m_Stat.onFindFastSuccess();
 794                 return true;
 795             case find_fastpath_not_found:
 796                 m_Stat.onFindFastFailed();
 797                 return false;
 798             default:
 799                 break;
 800             }
 801
 802             if ( find_slowpath( val, cmp, f )) {
 803                 m_Stat.onFindSlowSuccess();
 804                 return true;
 805             }
 806
 807             m_Stat.onFindSlowFailed();
 808             return false;
 809         }
 810
 811         template <typename Q, typename Compare>
 812         bool get_with_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 813         {
 814             return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.set(&found); } );
 815         }
 816
 817         template <typename Q, typename Compare, typename Func>
 818         bool erase_( Q const& val, Compare cmp, Func f )
 819         {
 820             position pos;
 821
 822             if ( !find_position( val, pos, cmp, false ) ) {
 823                 m_Stat.onEraseFailed();
 824                 return false;
 825             }
 826
 827             node_type * pDel = pos.pCur;
 828             typename gc::Guard gDel;
 829             gDel.assign( node_traits::to_value_ptr(pDel) );
 830             assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 831
 832             unsigned int nHeight = pDel->height();
 833             if ( try_remove_at( pDel, pos, f )) {
 834                 --m_ItemCounter;
 835                 m_Stat.onRemoveNode( nHeight );
 836                 m_Stat.onEraseSuccess();
 837                 return true;
 838             }
 839
 840             m_Stat.onEraseFailed();
 841             return false;
 842         }
 843
 844         template <typename Q, typename Compare>
 845         bool extract_( typename guarded_ptr::native_guard& guard, Q const& val, Compare cmp )
 846         {
 847             position pos;
 848
 849             for (;;) {
 850                 if ( !find_position( val, pos, cmp, false ) ) {
 851                     m_Stat.onExtractFailed();
 852                     guard.clear();
 853                     return false;
 854                 }
 855
 856                 node_type * pDel = pos.pCur;
 857                 guard.set( 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                 m_Stat.onExtractRetry();
 868             }
 869         }
 870
 871         bool extract_min_( typename guarded_ptr::native_guard& gDel )
 872         {
 873             position pos;
 874
 875             for (;;) {
 876                 if ( !find_min_position( pos ) ) {
 877                     // The list is empty
 878                     m_Stat.onExtractMinFailed();
 879                     gDel.clear();
 880                     return false;
 881                 }
 882
 883                 node_type * pDel = pos.pCur;
 884
 885                 unsigned int nHeight = pDel->height();
 886                 gDel.set( 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 guarded_ptr::native_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                     gDel.clear();
 908                     return false;
 909                 }
 910
 911                 node_type * pDel = pos.pCur;
 912
 913                 unsigned int nHeight = pDel->height();
 914                 gDel.set( node_traits::to_value_ptr(pDel) );
 915
 916                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 917                     --m_ItemCounter;
 918                     m_Stat.onRemoveNode( nHeight );
 919                     m_Stat.onExtractMaxSuccess();
 920                     return true;
 921                 }
 922
 923                 m_Stat.onExtractMaxRetry();
 924             }
 925         }
 926
 927         void increase_height( unsigned int nHeight )
 928         {
 929             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
 930             if ( nCur < nHeight )
 931                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
 932         }
 933         //@endcond
 934
 935     public:
 936         /// Default constructor
 937         /**
 938             The constructor checks whether the count of guards is enough
 939             for skip-list and may raise an exception if not.
 940         */
 941         SkipListSet()
 942             : m_Head( c_nMaxHeight )
 943             , m_nHeight( c_nMinHeight )
 944         {
 945             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 946
 947             gc::check_available_guards( c_nHazardPtrCount );
 948
 949             // Barrier for head node
 950             atomics::atomic_thread_fence( memory_model::memory_order_release );
 951         }
 952
 953         /// Clears and destructs the skip-list
 954         ~SkipListSet()
 955         {
 956             clear();
 957         }
 958
 959     public:
 960         /// Iterator type
 961         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 962
 963         /// Const iterator type
 964         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 965
 966         /// Returns a forward iterator addressing the first element in a set
 967         iterator begin()
 968         {
 969             return iterator( *m_Head.head() );
 970         }
 971
 972         /// Returns a forward const iterator addressing the first element in a set
 973         const_iterator begin() const
 974         {
 975             return const_iterator( *m_Head.head() );
 976         }
 977         /// Returns a forward const iterator addressing the first element in a set
 978         const_iterator cbegin() const
 979         {
 980             return const_iterator( *m_Head.head() );
 981         }
 982
 983         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 984         iterator end()
 985         {
 986             return iterator();
 987         }
 988
 989         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 990         const_iterator end() const
 991         {
 992             return const_iterator();
 993         }
 994         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 995         const_iterator cend() const
 996         {
 997             return const_iterator();
 998         }
 999
1000     public:
1001         /// Inserts new node
1002         /**
1003             The function inserts \p val in the set if it does not contain
1004             an item with key equal to \p val.
1005
1006             Returns \p true if \p val is placed into the set, \p false otherwise.
1007         */
1008         bool insert( value_type& val )
1009         {
1010             return insert( val, []( value_type& ) {} );
1011         }
1012
1013         /// Inserts new node
1014         /**
1015             This function is intended for derived non-intrusive containers.
1016
1017             The function allows to split creating of new item into two part:
1018             - create item with key only
1019             - insert new item into the set
1020             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1021
1022             The functor signature is:
1023             \code
1024                 void func( value_type& val );
1025             \endcode
1026             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1027             \p val no any other changes could be made on this set's item by concurrent threads.
1028             The user-defined functor is called only if the inserting is success.
1029         */
1030         template <typename Func>
1031         bool insert( value_type& val, Func f )
1032         {
1033             typename gc::Guard gNew;
1034             gNew.assign( &val );
1035
1036             node_type * pNode = node_traits::to_node_ptr( val );
1037             scoped_node_ptr scp( pNode );
1038             unsigned int nHeight = pNode->height();
1039             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1040             bool bTowerMade = false;
1041
1042             position pos;
1043             while ( true )
1044             {
1045                 bool bFound = find_position( val, pos, key_comparator(), true );
1046                 if ( bFound ) {
1047                     // scoped_node_ptr deletes the node tower if we create it
1048                     if ( !bTowerMade )
1049                         scp.release();
1050
1051                     m_Stat.onInsertFailed();
1052                     return false;
1053                 }
1054
1055                 if ( !bTowerOk ) {
1056                     build_node( pNode );
1057                     nHeight = pNode->height();
1058                     bTowerMade =
1059                         bTowerOk = true;
1060                 }
1061
1062                 if ( !insert_at_position( val, pNode, pos, f )) {
1063                     m_Stat.onInsertRetry();
1064                     continue;
1065                 }
1066
1067                 increase_height( nHeight );
1068                 ++m_ItemCounter;
1069                 m_Stat.onAddNode( nHeight );
1070                 m_Stat.onInsertSuccess();
1071                 scp.release();
1072                 return true;
1073             }
1074         }
1075
1076         /// Ensures that the \p val exists in the set
1077         /**
1078             The operation performs inserting or changing data with lock-free manner.
1079
1080             If the item \p val is not found in the set, then \p val is inserted into the set.
1081             Otherwise, the functor \p func is called with item found.
1082             The functor signature is:
1083             \code
1084                 void func( bool bNew, value_type& item, value_type& val );
1085             \endcode
1086             with arguments:
1087             - \p bNew - \p true if the item has been inserted, \p false otherwise
1088             - \p item - item of the set
1089             - \p val - argument \p val passed into the \p ensure function
1090             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1091             refer to the same thing.
1092
1093             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1094             \p second is \p true if new item has been added or \p false if the item with \p key
1095             already is in the set.
1096
1097             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1098         */
1099         template <typename Func>
1100         std::pair<bool, bool> ensure( value_type& val, Func func )
1101         {
1102             typename gc::Guard gNew;
1103             gNew.assign( &val );
1104
1105             node_type * pNode = node_traits::to_node_ptr( val );
1106             scoped_node_ptr scp( pNode );
1107             unsigned int nHeight = pNode->height();
1108             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1109             bool bTowerMade = false;
1110
1111             position pos;
1112             while ( true )
1113             {
1114                 bool bFound = find_position( val, pos, key_comparator(), true );
1115                 if ( bFound ) {
1116                     // scoped_node_ptr deletes the node tower if we create it before
1117                     if ( !bTowerMade )
1118                         scp.release();
1119
1120                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
1121                     m_Stat.onEnsureExist();
1122                     return std::make_pair( true, false );
1123                 }
1124
1125                 if ( !bTowerOk ) {
1126                     build_node( pNode );
1127                     nHeight = pNode->height();
1128                     bTowerMade =
1129                         bTowerOk = true;
1130                 }
1131
1132                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1133                     m_Stat.onInsertRetry();
1134                     continue;
1135                 }
1136
1137                 increase_height( nHeight );
1138                 ++m_ItemCounter;
1139                 scp.release();
1140                 m_Stat.onAddNode( nHeight );
1141                 m_Stat.onEnsureNew();
1142                 return std::make_pair( true, true );
1143             }
1144         }
1145
1146         /// Unlinks the item \p val from the set
1147         /**
1148             The function searches the item \p val in the set and unlink it from the set
1149             if it is found and is equal to \p val.
1150
1151             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1152             and deletes the item found. \p %unlink() finds an item by key and deletes it
1153             only if \p val is an item of that set, i.e. the pointer to item found
1154             is equal to <tt> &val </tt>.
1155
1156             The \p disposer specified in \p Traits class template parameter is called
1157             by garbage collector \p GC asynchronously.
1158
1159             The function returns \p true if success and \p false otherwise.
1160         */
1161         bool unlink( value_type& val )
1162         {
1163             position pos;
1164
1165             if ( !find_position( val, pos, key_comparator(), false ) ) {
1166                 m_Stat.onUnlinkFailed();
1167                 return false;
1168             }
1169
1170             node_type * pDel = pos.pCur;
1171             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1172
1173             unsigned int nHeight = pDel->height();
1174             typename gc::Guard gDel;
1175             gDel.assign( node_traits::to_value_ptr(pDel) );
1176
1177             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1178                 --m_ItemCounter;
1179                 m_Stat.onRemoveNode( nHeight );
1180                 m_Stat.onUnlinkSuccess();
1181                 return true;
1182             }
1183
1184             m_Stat.onUnlinkFailed();
1185             return false;
1186         }
1187
1188         /// Extracts the item from the set with specified \p key
1189         /** \anchor cds_intrusive_SkipListSet_hp_extract
1190             The function searches an item with key equal to \p key in the set,
1191             unlinks it from the set, and returns it as \p guarded_ptr object.
1192             If \p key is not found the function returns an empty guarded pointer.
1193
1194             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1195
1196             The \p disposer specified in \p Traits class template parameter is called automatically
1197             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1198             will be destroyed or released.
1199             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1200
1201             Usage:
1202             \code
1203             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1204             skip_list theList;
1205             // ...
1206             {
1207                 skip_list::guarded_ptr gp(theList.extract( 5 ));
1208                 if ( gp ) {
1209                     // Deal with gp
1210                     // ...
1211                 }
1212                 // Destructor of gp releases internal HP guard
1213             }
1214             \endcode
1215         */
1216         template <typename Q>
1217         guarded_ptr extract( Q const& key )
1218         {
1219             guarded_ptr gp;
1220             extract_( gp.guard(), key, key_comparator() );
1221             return gp;
1222         }
1223
1224         /// Extracts the item from the set with comparing functor \p pred
1225         /**
1226             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1227             but \p pred predicate is used for key comparing.
1228
1229             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1230             in any order.
1231             \p pred must imply the same element order as the comparator used for building the set.
1232         */
1233         template <typename Q, typename Less>
1234         guarded_ptr extract_with( Q const& key, Less pred )
1235         {
1236             CDS_UNUSED( pred );
1237             guarded_ptr gp;
1238             extract_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1239             return gp;
1240         }
1241
1242         /// Extracts an item with minimal key from the list
1243         /**
1244             The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1245             If the skip-list is empty the function returns an empty guarded pointer.
1246
1247             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1248             It means that the function gets leftmost item and tries to unlink it.
1249             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1250             So, the function returns the item with minimum key at the moment of list traversing.
1251
1252             The \p disposer specified in \p Traits class template parameter is called
1253             by garbage collector \p GC automatically when returned \p guarded_ptr object
1254             will be destroyed or released.
1255             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1256
1257             Usage:
1258             \code
1259             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1260             skip_list theList;
1261             // ...
1262             {
1263                 skip_list::guarded_ptr gp(theList.extract_min());
1264                 if ( gp ) {
1265                     // Deal with gp
1266                     //...
1267                 }
1268                 // Destructor of gp releases internal HP guard
1269             }
1270             \endcode
1271         */
1272         guarded_ptr extract_min()
1273         {
1274             guarded_ptr gp;
1275             extract_min_( gp.guard() );
1276             return gp;
1277         }
1278
1279         /// Extracts an item with maximal key from the list
1280         /**
1281             The function searches an item with maximal key, unlinks it, and returns the pointer to item
1282             as \p guarded_ptr object.
1283             If the skip-list is empty the function returns an empty \p guarded_ptr.
1284
1285             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1286             It means that the function gets rightmost item and tries to unlink it.
1287             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1288             So, the function returns the item with maximum key at the moment of list traversing.
1289
1290             The \p disposer specified in \p Traits class template parameter is called
1291             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1292             will be destroyed or released.
1293             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1294
1295             Usage:
1296             \code
1297             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1298             skip_list theList;
1299             // ...
1300             {
1301                 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1302                 if ( gp ) {
1303                     // Deal with gp
1304                     //...
1305                 }
1306                 // Destructor of gp releases internal HP guard
1307             }
1308             \endcode
1309         */
1310         guarded_ptr extract_max()
1311         {
1312             guarded_ptr gp;
1313             extract_max_( gp.guard() );
1314             return gp;
1315         }
1316
1317         /// Deletes the item from the set
1318         /** \anchor cds_intrusive_SkipListSet_hp_erase
1319             The function searches an item with key equal to \p key in the set,
1320             unlinks it from the set, and returns \p true.
1321             If the item with key equal to \p key is not found the function return \p false.
1322
1323             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1324         */
1325         template <typename Q>
1326         bool erase( Q const& key )
1327         {
1328             return erase_( key, key_comparator(), [](value_type const&) {} );
1329         }
1330
1331         /// Deletes the item from the set with comparing functor \p pred
1332         /**
1333             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1334             but \p pred predicate is used for key comparing.
1335
1336             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1337             in any order.
1338             \p pred must imply the same element order as the comparator used for building the set.
1339         */
1340         template <typename Q, typename Less>
1341         bool erase_with( Q const& key, Less pred )
1342         {
1343             CDS_UNUSED( pred );
1344             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1345         }
1346
1347         /// Deletes the item from the set
1348         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1349             The function searches an item with key equal to \p key in the set,
1350             call \p f functor with item found, unlinks it from the set, and returns \p true.
1351             The \ref disposer specified in \p Traits class template parameter is called
1352             by garbage collector \p GC asynchronously.
1353
1354             The \p Func interface is
1355             \code
1356             struct functor {
1357                 void operator()( value_type const& item );
1358             };
1359             \endcode
1360
1361             If the item with key equal to \p key is not found the function return \p false.
1362
1363             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1364         */
1365         template <typename Q, typename Func>
1366         bool erase( Q const& key, Func f )
1367         {
1368             return erase_( key, key_comparator(), f );
1369         }
1370
1371         /// Deletes the item from the set with comparing functor \p pred
1372         /**
1373             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1374             but \p pred predicate is used for key comparing.
1375
1376             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1377             in any order.
1378             \p pred must imply the same element order as the comparator used for building the set.
1379         */
1380         template <typename Q, typename Less, typename Func>
1381         bool erase_with( Q const& key, Less pred, Func f )
1382         {
1383             CDS_UNUSED( pred );
1384             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1385         }
1386
1387         /// Finds \p key
1388         /** \anchor cds_intrusive_SkipListSet_hp_find_func
1389             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1390             The interface of \p Func functor is:
1391             \code
1392             struct functor {
1393                 void operator()( value_type& item, Q& key );
1394             };
1395             \endcode
1396             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1397
1398             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1399             that \p item cannot be disposed during functor is executing.
1400             The functor does not serialize simultaneous access to the set \p item. If such access is
1401             possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1402
1403             Note the compare functor specified for class \p Traits template parameter
1404             should accept a parameter of type \p Q that can be not the same as \p value_type.
1405
1406             The function returns \p true if \p key is found, \p false otherwise.
1407         */
1408         template <typename Q, typename Func>
1409         bool find( Q& key, Func f )
1410         {
1411             return find_with_( key, key_comparator(), f );
1412         }
1413         //@cond
1414         template <typename Q, typename Func>
1415         bool find( Q const& key, Func f )
1416         {
1417             return find_with_( key, key_comparator(), f );
1418         }
1419         //@endcond
1420
1421         /// Finds the key \p key with \p pred predicate for comparing
1422         /**
1423             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1424             but \p pred is used for key compare.
1425
1426             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1427             in any order.
1428             \p pred must imply the same element order as the comparator used for building the set.
1429         */
1430         template <typename Q, typename Less, typename Func>
1431         bool find_with( Q& key, Less pred, Func f )
1432         {
1433             CDS_UNUSED( pred );
1434             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1435         }
1436         //@cond
1437         template <typename Q, typename Less, typename Func>
1438         bool find_with( Q const& key, Less pred, Func f )
1439         {
1440             CDS_UNUSED( pred );
1441             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1442         }
1443         //@endcond
1444
1445         /// Finds \p key
1446         /** \anchor cds_intrusive_SkipListSet_hp_find_val
1447             The function searches the item with key equal to \p key
1448             and returns \p true if it is found, and \p false otherwise.
1449
1450             Note the compare functor specified for class \p Traits template parameter
1451             should accept a parameter of type \p Q that can be not the same as \p value_type.
1452         */
1453         template <typename Q>
1454         bool find( Q const& key )
1455         {
1456             return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1457         }
1458
1459         /// Finds \p key with comparing functor \p pred
1460         /**
1461             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1462             but \p pred is used for comparing the keys.
1463             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1464             in any order.
1465             \p pred must imply the same element order as the comparator used for building the set.
1466         */
1467         template <typename Q, typename Less>
1468         bool find_with( Q const& key, Less pred )
1469         {
1470             CDS_UNUSED( pred );
1471             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1472         }
1473
1474         /// Finds \p key and return the item found
1475         /** \anchor cds_intrusive_SkipListSet_hp_get
1476             The function searches the item with key equal to \p key
1477             and returns the pointer to the item found as \p guarded_ptr.
1478             If \p key is not found the function returns an empt guarded pointer.
1479
1480             The \p disposer specified in \p Traits class template parameter is called
1481             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1482             will be destroyed or released.
1483             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1484
1485             Usage:
1486             \code
1487             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1488             skip_list theList;
1489             // ...
1490             {
1491                 skip_list::guarded_ptr gp(theList.get( 5 ));
1492                 if ( gp ) {
1493                     // Deal with gp
1494                     //...
1495                 }
1496                 // Destructor of guarded_ptr releases internal HP guard
1497             }
1498             \endcode
1499
1500             Note the compare functor specified for class \p Traits template parameter
1501             should accept a parameter of type \p Q that can be not the same as \p value_type.
1502         */
1503         template <typename Q>
1504         guarded_ptr get( Q const& key )
1505         {
1506             guarded_ptr gp;
1507             get_with_( gp.guard(), key, key_comparator() );
1508             return gp;
1509         }
1510
1511         /// Finds \p key and return the item found
1512         /**
1513             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1514             but \p pred is used for comparing the keys.
1515
1516             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1517             in any order.
1518             \p pred must imply the same element order as the comparator used for building the set.
1519         */
1520         template <typename Q, typename Less>
1521         guarded_ptr get_with( Q const& key, Less pred )
1522         {
1523             CDS_UNUSED( pred );
1524             guarded_ptr gp;
1525             get_with_( gp.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1526             return gp;
1527         }
1528
1529         /// Returns item count in the set
1530         /**
1531             The value returned depends on item counter type provided by \p Traits template parameter.
1532             If it is \p atomicity::empty_item_counter this function always returns 0.
1533             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1534             for this purpose.
1535         */
1536         size_t size() const
1537         {
1538             return m_ItemCounter;
1539         }
1540
1541         /// Checks if the set is empty
1542         bool empty() const
1543         {
1544             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1545         }
1546
1547         /// Clears the set (not atomic)
1548         /**
1549             The function unlink all items from the set.
1550             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1551             this sequence
1552             \code
1553             set.clear();
1554             assert( set.empty() );
1555             \endcode
1556             the assertion could be raised.
1557
1558             For each item the \ref disposer will be called after unlinking.
1559         */
1560         void clear()
1561         {
1562             guarded_ptr gp;
1563             while ( extract_min_( gp.guard() ));
1564         }
1565
1566         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1567         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1568         {
1569             return c_nMaxHeight;
1570         }
1571
1572         /// Returns const reference to internal statistics
1573         stat const& statistics() const
1574         {
1575             return m_Stat;
1576         }
1577     };
1578
1579 }} // namespace cds::intrusive
1580
1581
1582 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H