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 cds::gc::guarded_ptr< gc, 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 gc::Guard& guard, Q const& val, Compare cmp )
 813         {
 814             return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&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 gc::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                     return false;
 853                 }
 854
 855                 node_type * pDel = pos.pCur;
 856                 guard.assign( node_traits::to_value_ptr(pDel));
 857                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 858
 859                 unsigned int nHeight = pDel->height();
 860                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 861                     --m_ItemCounter;
 862                     m_Stat.onRemoveNode( nHeight );
 863                     m_Stat.onExtractSuccess();
 864                     return true;
 865                 }
 866
 867                 m_Stat.onExtractRetry();
 868             }
 869         }
 870
 871         bool extract_min_( typename gc::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                     return false;
 880                 }
 881
 882                 node_type * pDel = pos.pCur;
 883
 884                 unsigned int nHeight = pDel->height();
 885                 gDel.assign( node_traits::to_value_ptr(pDel) );
 886
 887                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 888                     --m_ItemCounter;
 889                     m_Stat.onRemoveNode( nHeight );
 890                     m_Stat.onExtractMinSuccess();
 891                     return true;
 892                 }
 893
 894                 m_Stat.onExtractMinRetry();
 895             }
 896         }
 897
 898         bool extract_max_( typename gc::Guard& gDel )
 899         {
 900             position pos;
 901
 902             for (;;) {
 903                 if ( !find_max_position( pos ) ) {
 904                     // The list is empty
 905                     m_Stat.onExtractMaxFailed();
 906                     return false;
 907                 }
 908
 909                 node_type * pDel = pos.pCur;
 910
 911                 unsigned int nHeight = pDel->height();
 912                 gDel.assign( node_traits::to_value_ptr(pDel) );
 913
 914                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 915                     --m_ItemCounter;
 916                     m_Stat.onRemoveNode( nHeight );
 917                     m_Stat.onExtractMaxSuccess();
 918                     return true;
 919                 }
 920
 921                 m_Stat.onExtractMaxRetry();
 922             }
 923         }
 924
 925         void increase_height( unsigned int nHeight )
 926         {
 927             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
 928             if ( nCur < nHeight )
 929                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
 930         }
 931         //@endcond
 932
 933     public:
 934         /// Default constructor
 935         /**
 936             The constructor checks whether the count of guards is enough
 937             for skip-list and may raise an exception if not.
 938         */
 939         SkipListSet()
 940             : m_Head( c_nMaxHeight )
 941             , m_nHeight( c_nMinHeight )
 942         {
 943             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 944
 945             gc::check_available_guards( c_nHazardPtrCount );
 946
 947             // Barrier for head node
 948             atomics::atomic_thread_fence( memory_model::memory_order_release );
 949         }
 950
 951         /// Clears and destructs the skip-list
 952         ~SkipListSet()
 953         {
 954             clear();
 955         }
 956
 957     public:
 958         /// Iterator type
 959         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 960
 961         /// Const iterator type
 962         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 963
 964         /// Returns a forward iterator addressing the first element in a set
 965         iterator begin()
 966         {
 967             return iterator( *m_Head.head() );
 968         }
 969
 970         /// Returns a forward const iterator addressing the first element in a set
 971         const_iterator begin() const
 972         {
 973             return const_iterator( *m_Head.head() );
 974         }
 975         /// Returns a forward const iterator addressing the first element in a set
 976         const_iterator cbegin() const
 977         {
 978             return const_iterator( *m_Head.head() );
 979         }
 980
 981         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 982         iterator end()
 983         {
 984             return iterator();
 985         }
 986
 987         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 988         const_iterator end() const
 989         {
 990             return const_iterator();
 991         }
 992         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 993         const_iterator cend() const
 994         {
 995             return const_iterator();
 996         }
 997
 998     public:
 999         /// Inserts new node
1000         /**
1001             The function inserts \p val in the set if it does not contain
1002             an item with key equal to \p val.
1003
1004             Returns \p true if \p val is placed into the set, \p false otherwise.
1005         */
1006         bool insert( value_type& val )
1007         {
1008             return insert( val, []( value_type& ) {} );
1009         }
1010
1011         /// Inserts new node
1012         /**
1013             This function is intended for derived non-intrusive containers.
1014
1015             The function allows to split creating of new item into two part:
1016             - create item with key only
1017             - insert new item into the set
1018             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1019
1020             The functor signature is:
1021             \code
1022                 void func( value_type& val );
1023             \endcode
1024             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1025             \p val no any other changes could be made on this set's item by concurrent threads.
1026             The user-defined functor is called only if the inserting is success.
1027         */
1028         template <typename Func>
1029         bool insert( value_type& val, Func f )
1030         {
1031             typename gc::Guard gNew;
1032             gNew.assign( &val );
1033
1034             node_type * pNode = node_traits::to_node_ptr( val );
1035             scoped_node_ptr scp( pNode );
1036             unsigned int nHeight = pNode->height();
1037             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1038             bool bTowerMade = false;
1039
1040             position pos;
1041             while ( true )
1042             {
1043                 bool bFound = find_position( val, pos, key_comparator(), true );
1044                 if ( bFound ) {
1045                     // scoped_node_ptr deletes the node tower if we create it
1046                     if ( !bTowerMade )
1047                         scp.release();
1048
1049                     m_Stat.onInsertFailed();
1050                     return false;
1051                 }
1052
1053                 if ( !bTowerOk ) {
1054                     build_node( pNode );
1055                     nHeight = pNode->height();
1056                     bTowerMade =
1057                         bTowerOk = true;
1058                 }
1059
1060                 if ( !insert_at_position( val, pNode, pos, f )) {
1061                     m_Stat.onInsertRetry();
1062                     continue;
1063                 }
1064
1065                 increase_height( nHeight );
1066                 ++m_ItemCounter;
1067                 m_Stat.onAddNode( nHeight );
1068                 m_Stat.onInsertSuccess();
1069                 scp.release();
1070                 return true;
1071             }
1072         }
1073
1074         /// Ensures that the \p val exists in the set
1075         /**
1076             The operation performs inserting or changing data with lock-free manner.
1077
1078             If the item \p val is not found in the set, then \p val is inserted into the set.
1079             Otherwise, the functor \p func is called with item found.
1080             The functor signature is:
1081             \code
1082                 void func( bool bNew, value_type& item, value_type& val );
1083             \endcode
1084             with arguments:
1085             - \p bNew - \p true if the item has been inserted, \p false otherwise
1086             - \p item - item of the set
1087             - \p val - argument \p val passed into the \p ensure function
1088             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1089             refer to the same thing.
1090
1091             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1092             \p second is \p true if new item has been added or \p false if the item with \p key
1093             already is in the set.
1094
1095             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1096         */
1097         template <typename Func>
1098         std::pair<bool, bool> ensure( value_type& val, Func func )
1099         {
1100             typename gc::Guard gNew;
1101             gNew.assign( &val );
1102
1103             node_type * pNode = node_traits::to_node_ptr( val );
1104             scoped_node_ptr scp( pNode );
1105             unsigned int nHeight = pNode->height();
1106             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1107             bool bTowerMade = false;
1108
1109             position pos;
1110             while ( true )
1111             {
1112                 bool bFound = find_position( val, pos, key_comparator(), true );
1113                 if ( bFound ) {
1114                     // scoped_node_ptr deletes the node tower if we create it before
1115                     if ( !bTowerMade )
1116                         scp.release();
1117
1118                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
1119                     m_Stat.onEnsureExist();
1120                     return std::make_pair( true, false );
1121                 }
1122
1123                 if ( !bTowerOk ) {
1124                     build_node( pNode );
1125                     nHeight = pNode->height();
1126                     bTowerMade =
1127                         bTowerOk = true;
1128                 }
1129
1130                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1131                     m_Stat.onInsertRetry();
1132                     continue;
1133                 }
1134
1135                 increase_height( nHeight );
1136                 ++m_ItemCounter;
1137                 scp.release();
1138                 m_Stat.onAddNode( nHeight );
1139                 m_Stat.onEnsureNew();
1140                 return std::make_pair( true, true );
1141             }
1142         }
1143
1144         /// Unlinks the item \p val from the set
1145         /**
1146             The function searches the item \p val in the set and unlink it from the set
1147             if it is found and is equal to \p val.
1148
1149             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1150             and deletes the item found. \p %unlink() finds an item by key and deletes it
1151             only if \p val is an item of that set, i.e. the pointer to item found
1152             is equal to <tt> &val </tt>.
1153
1154             The \p disposer specified in \p Traits class template parameter is called
1155             by garbage collector \p GC asynchronously.
1156
1157             The function returns \p true if success and \p false otherwise.
1158         */
1159         bool unlink( value_type& val )
1160         {
1161             position pos;
1162
1163             if ( !find_position( val, pos, key_comparator(), false ) ) {
1164                 m_Stat.onUnlinkFailed();
1165                 return false;
1166             }
1167
1168             node_type * pDel = pos.pCur;
1169             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1170
1171             unsigned int nHeight = pDel->height();
1172             typename gc::Guard gDel;
1173             gDel.assign( node_traits::to_value_ptr(pDel) );
1174
1175             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1176                 --m_ItemCounter;
1177                 m_Stat.onRemoveNode( nHeight );
1178                 m_Stat.onUnlinkSuccess();
1179                 return true;
1180             }
1181
1182             m_Stat.onUnlinkFailed();
1183             return false;
1184         }
1185
1186         /// Extracts the item from the set with specified \p key
1187         /** \anchor cds_intrusive_SkipListSet_hp_extract
1188             The function searches an item with key equal to \p key in the set,
1189             unlinks it from the set, and returns it in \p dest parameter.
1190             If the item with key equal to \p key is not found the function returns \p false.
1191
1192             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1193
1194             The \ref disposer specified in \p Traits class template parameter is called automatically
1195             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1196             will be destroyed or released.
1197             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1198
1199             Usage:
1200             \code
1201             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1202             skip_list theList;
1203             // ...
1204             {
1205                 skip_list::guarded_ptr gp;
1206                 theList.extract( gp, 5 );
1207                 // Deal with gp
1208                 // ...
1209
1210                 // Destructor of gp releases internal HP guard
1211             }
1212             \endcode
1213         */
1214         template <typename Q>
1215         bool extract( guarded_ptr& dest, Q const& key )
1216         {
1217             return extract_( dest.guard(), key, key_comparator() );
1218         }
1219
1220         /// Extracts the item from the set with comparing functor \p pred
1221         /**
1222             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1223             but \p pred predicate is used for key comparing.
1224
1225             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1226             in any order.
1227             \p pred must imply the same element order as the comparator used for building the set.
1228         */
1229         template <typename Q, typename Less>
1230         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1231         {
1232             CDS_UNUSED( pred );
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             CDS_UNUSED( pred );
1333             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1334         }
1335
1336         /// Deletes the item from the set
1337         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1338             The function searches an item with key equal to \p key in the set,
1339             call \p f functor with item found, unlinks it from the set, and returns \p true.
1340             The \ref disposer specified in \p Traits class template parameter is called
1341             by garbage collector \p GC asynchronously.
1342
1343             The \p Func interface is
1344             \code
1345             struct functor {
1346                 void operator()( value_type const& item );
1347             };
1348             \endcode
1349
1350             If the item with key equal to \p key is not found the function return \p false.
1351
1352             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1353         */
1354         template <typename Q, typename Func>
1355         bool erase( Q const& key, Func f )
1356         {
1357             return erase_( key, key_comparator(), f );
1358         }
1359
1360         /// Deletes the item from the set with comparing functor \p pred
1361         /**
1362             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1363             but \p pred predicate is used for key comparing.
1364
1365             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1366             in any order.
1367             \p pred must imply the same element order as the comparator used for building the set.
1368         */
1369         template <typename Q, typename Less, typename Func>
1370         bool erase_with( Q const& key, Less pred, Func f )
1371         {
1372             CDS_UNUSED( pred );
1373             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1374         }
1375
1376         /// Finds \p key
1377         /** \anchor cds_intrusive_SkipListSet_hp_find_func
1378             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1379             The interface of \p Func functor is:
1380             \code
1381             struct functor {
1382                 void operator()( value_type& item, Q& key );
1383             };
1384             \endcode
1385             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1386
1387             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1388             that \p item cannot be disposed during functor is executing.
1389             The functor does not serialize simultaneous access to the set \p item. If such access is
1390             possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1391
1392             Note the compare functor specified for class \p Traits template parameter
1393             should accept a parameter of type \p Q that can be not the same as \p value_type.
1394
1395             The function returns \p true if \p key is found, \p false otherwise.
1396         */
1397         template <typename Q, typename Func>
1398         bool find( Q& key, Func f )
1399         {
1400             return find_with_( key, key_comparator(), f );
1401         }
1402         //@cond
1403         template <typename Q, typename Func>
1404         bool find( Q const& key, Func f )
1405         {
1406             return find_with_( key, key_comparator(), f );
1407         }
1408         //@endcond
1409
1410         /// Finds the key \p key with \p pred predicate for comparing
1411         /**
1412             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1413             but \p pred is used for key compare.
1414
1415             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1416             in any order.
1417             \p pred must imply the same element order as the comparator used for building the set.
1418         */
1419         template <typename Q, typename Less, typename Func>
1420         bool find_with( Q& key, Less pred, Func f )
1421         {
1422             CDS_UNUSED( pred );
1423             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1424         }
1425         //@cond
1426         template <typename Q, typename Less, typename Func>
1427         bool find_with( Q const& key, Less pred, Func f )
1428         {
1429             CDS_UNUSED( pred );
1430             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1431         }
1432         //@endcond
1433
1434         /// Finds \p key
1435         /** \anchor cds_intrusive_SkipListSet_hp_find_val
1436             The function searches the item with key equal to \p key
1437             and returns \p true if it is found, and \p false otherwise.
1438
1439             Note the compare functor specified for class \p Traits template parameter
1440             should accept a parameter of type \p Q that can be not the same as \p value_type.
1441         */
1442         template <typename Q>
1443         bool find( Q const& key )
1444         {
1445             return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1446         }
1447
1448         /// Finds \p key with comparing functor \p pred
1449         /**
1450             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1451             but \p pred is used for comparing the keys.
1452             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1453             in any order.
1454             \p pred must imply the same element order as the comparator used for building the set.
1455         */
1456         template <typename Q, typename Less>
1457         bool find_with( Q const& key, Less pred )
1458         {
1459             CDS_UNUSED( pred );
1460             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1461         }
1462
1463         /// Finds \p key and return the item found
1464         /** \anchor cds_intrusive_SkipListSet_hp_get
1465             The function searches the item with key equal to \p key
1466             and assigns the item found to guarded pointer \p ptr.
1467             The function returns \p true if \p key is found, and \p false otherwise.
1468             If \p key is not found the \p ptr parameter is not changed.
1469
1470             The \ref disposer specified in \p Traits class template parameter is called
1471             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1472             will be destroyed or released.
1473             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1474
1475             Usage:
1476             \code
1477             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1478             skip_list theList;
1479             // ...
1480             {
1481                 skip_list::guarded_ptr gp;
1482                 if ( theList.get( gp, 5 )) {
1483                     // Deal with gp
1484                     //...
1485                 }
1486                 // Destructor of guarded_ptr releases internal HP guard
1487             }
1488             \endcode
1489
1490             Note the compare functor specified for class \p Traits template parameter
1491             should accept a parameter of type \p Q that can be not the same as \p value_type.
1492         */
1493         template <typename Q>
1494         bool get( guarded_ptr& ptr, Q const& key )
1495         {
1496             return get_with_( ptr.guard(), key, key_comparator() );
1497         }
1498
1499         /// Finds \p key and return the item found
1500         /**
1501             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1502             but \p pred is used for comparing the keys.
1503
1504             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1505             in any order.
1506             \p pred must imply the same element order as the comparator used for building the set.
1507         */
1508         template <typename Q, typename Less>
1509         bool get_with( guarded_ptr& ptr, Q const& key, Less pred )
1510         {
1511             CDS_UNUSED( pred );
1512             return get_with_( ptr.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1513         }
1514
1515         /// Returns item count in the set
1516         /**
1517             The value returned depends on item counter type provided by \p Traits template parameter.
1518             If it is \p atomicity::empty_item_counter this function always returns 0.
1519             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1520             for this purpose.
1521         */
1522         size_t size() const
1523         {
1524             return m_ItemCounter;
1525         }
1526
1527         /// Checks if the set is empty
1528         bool empty() const
1529         {
1530             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1531         }
1532
1533         /// Clears the set (not atomic)
1534         /**
1535             The function unlink all items from the set.
1536             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1537             this sequence
1538             \code
1539             set.clear();
1540             assert( set.empty() );
1541             \endcode
1542             the assertion could be raised.
1543
1544             For each item the \ref disposer will be called after unlinking.
1545         */
1546         void clear()
1547         {
1548             guarded_ptr gp;
1549             while ( extract_min( gp ));
1550         }
1551
1552         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1553         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1554         {
1555             return c_nMaxHeight;
1556         }
1557
1558         /// Returns const reference to internal statistics
1559         stat const& statistics() const
1560         {
1561             return m_Stat;
1562         }
1563     };
1564
1565 }} // namespace cds::intrusive
1566
1567
1568 #endif // #ifndef __CDS_INTRUSIVE_IMPL_SKIP_LIST_H