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