cds/intrusive/impl/skip_list.h

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