cds/intrusive/impl/skip_list.h

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