cds/intrusive/skip_list_impl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
   4 #define __CDS_INTRUSIVE_SKIP_LIST_IMPL_H
   5
   6 #include <type_traits>
   7 #include <memory>
   8 #include <cds/intrusive/skip_list_base.h>
   9 #include <cds/opt/compare.h>
  10 #include <cds/ref.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( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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
 421 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 422         struct empty_insert_functor {
 423             void operator()( value_type& )
 424             {}
 425         };
 426
 427         struct empty_erase_functor  {
 428             void operator()( value_type const& )
 429             {}
 430         };
 431
 432         struct empty_find_functor {
 433             template <typename Q>
 434             void operator()( value_type& item, Q& val )
 435             {}
 436         };
 437
 438         struct get_functor {
 439             typename gc::Guard& m_guard;
 440
 441             get_functor( typename gc::Guard& gp )
 442                 : m_guard(gp)
 443             {}
 444
 445             template <typename Q>
 446             void operator()( value_type& item, Q& val )
 447             {
 448                 m_guard.assign( &item );
 449             }
 450         };
 451
 452         template <typename Func>
 453         struct insert_at_ensure_functor {
 454             Func m_func;
 455             insert_at_ensure_functor( Func f ) : m_func(f) {}
 456
 457             void operator()( value_type& item )
 458             {
 459                 cds::unref( m_func)( true, item, item );
 460             }
 461         };
 462
 463         struct copy_value_functor {
 464             template <typename Q>
 465             void operator()( Q& dest, value_type const& src ) const
 466             {
 467                 dest = src;
 468             }
 469         };
 470
 471         struct dummy_copy_functor {
 472             template <typename Q>
 473             void operator()( Q&, value_type const&) const {}
 474         };
 475 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 476
 477         //@endcond
 478
 479     protected:
 480         skip_list::details::head_node< node_type >      m_Head  ;   ///< head tower (max height)
 481
 482         item_counter                m_ItemCounter       ;   ///< item counter
 483         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance
 484         CDS_ATOMIC::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level
 485         mutable stat                m_Stat              ;   ///< internal statistics
 486
 487     protected:
 488         //@cond
 489         unsigned int random_level()
 490         {
 491             // Random generator produces a number from range [0..31]
 492             // We need a number from range [1..32]
 493             return m_RandomLevelGen() + 1;
 494         }
 495
 496         template <typename Q>
 497         node_type * build_node( Q v )
 498         {
 499             return node_builder::make_tower( v, m_RandomLevelGen );
 500         }
 501
 502         static value_type * gc_protect( marked_node_ptr p )
 503         {
 504             return node_traits::to_value_ptr( p.ptr() );
 505         }
 506
 507         static void dispose_node( value_type * pVal )
 508         {
 509             assert( pVal != nullptr );
 510             typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
 511             disposer()( pVal );
 512         }
 513
 514         template <typename Q, typename Compare >
 515         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
 516         {
 517             node_type * pPred;
 518             marked_node_ptr pSucc;
 519             marked_node_ptr pCur;
 520
 521             // Hazard pointer array:
 522             //  pPred: [nLevel * 2]
 523             //  pSucc: [nLevel * 2 + 1]
 524
 525         retry:
 526             pPred = m_Head.head();
 527             int nCmp = 1;
 528
 529             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
 530                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
 531                 while ( true ) {
 532                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
 533                     if ( pCur.bits() ) {
 534                         // pCur.bits() means that pPred is logically deleted
 535                         goto retry;
 536                     }
 537
 538                     if ( pCur.ptr() == nullptr ) {
 539                         // end of the list at level nLevel - goto next level
 540                         break;
 541                     }
 542
 543                     // pSucc contains deletion mark for pCur
 544                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 545
 546                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 547                         goto retry;
 548
 549                     if ( pSucc.bits() ) {
 550                         // pCur is marked, i.e. logically deleted.
 551                         marked_node_ptr p( pCur.ptr() );
 552                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 553                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 554                         {
 555                             if ( nLevel == 0 ) {
 556                                 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
 557                                 m_Stat.onEraseWhileFind();
 558                             }
 559                         }
 560                         goto retry;
 561                     }
 562                     else {
 563                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
 564                         if ( nCmp < 0 ) {
 565                             pPred = pCur.ptr();
 566                             pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ) ;   // pPrev guard := cur guard
 567                         }
 568                         else if ( nCmp == 0 && bStopIfFound )
 569                             goto found;
 570                         else
 571                             break;
 572                     }
 573                 }
 574
 575                 // Next level
 576                 pos.pPrev[ nLevel ] = pPred;
 577                 pos.pSucc[ nLevel ] = pCur.ptr();
 578             }
 579
 580             if ( nCmp != 0 )
 581                 return false;
 582
 583         found:
 584             pos.pCur = pCur.ptr();
 585             return pCur.ptr() && nCmp == 0;
 586         }
 587
 588         bool find_min_position( position& pos )
 589         {
 590             node_type * pPred;
 591             marked_node_ptr pSucc;
 592             marked_node_ptr pCur;
 593
 594             // Hazard pointer array:
 595             //  pPred: [nLevel * 2]
 596             //  pSucc: [nLevel * 2 + 1]
 597
 598         retry:
 599             pPred = m_Head.head();
 600
 601             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
 602                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
 603                 pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
 604
 605                 // pCur.bits() means that pPred is logically deleted
 606                 // head cannot be deleted
 607                 assert( pCur.bits() == 0 );
 608
 609                 if ( pCur.ptr() ) {
 610
 611                     // pSucc contains deletion mark for pCur
 612                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 613
 614                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 615                         goto retry;
 616
 617                     if ( pSucc.bits() ) {
 618                         // pCur is marked, i.e. logically deleted.
 619                         marked_node_ptr p( pCur.ptr() );
 620                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 621                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 622                         {
 623                             if ( nLevel == 0 )
 624                                 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
 625                         }
 626                         goto retry;
 627                     }
 628                 }
 629
 630                 // Next level
 631                 pos.pPrev[ nLevel ] = pPred;
 632                 pos.pSucc[ nLevel ] = pCur.ptr();
 633             }
 634
 635             return (pos.pCur = pCur.ptr()) != nullptr;
 636         }
 637
 638         bool find_max_position( position& pos )
 639         {
 640             node_type * pPred;
 641             marked_node_ptr pSucc;
 642             marked_node_ptr pCur;
 643
 644             // Hazard pointer array:
 645             //  pPred: [nLevel * 2]
 646             //  pSucc: [nLevel * 2 + 1]
 647
 648         retry:
 649             pPred = m_Head.head();
 650
 651             for ( int nLevel = static_cast<int>( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) {
 652                 pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ));
 653                 while ( true ) {
 654                     pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect );
 655                     if ( pCur.bits() ) {
 656                         // pCur.bits() means that pPred is logically deleted
 657                         goto retry;
 658                     }
 659
 660                     if ( pCur.ptr() == nullptr ) {
 661                         // end of the list at level nLevel - goto next level
 662                         break;
 663                     }
 664
 665                     // pSucc contains deletion mark for pCur
 666                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 667
 668                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 669                         goto retry;
 670
 671                     if ( pSucc.bits() ) {
 672                         // pCur is marked, i.e. logically deleted.
 673                         marked_node_ptr p( pCur.ptr() );
 674                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 675                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 676                         {
 677                             if ( nLevel == 0 )
 678                                 gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
 679                         }
 680                         goto retry;
 681                     }
 682                     else {
 683                         if ( !pSucc.ptr() )
 684                             break;
 685
 686                         pPred = pCur.ptr();
 687                         pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard
 688                         //pos.guards.copy( nLevel * 2, gCur ) ;   // pPrev guard := gCur
 689                     }
 690                 }
 691
 692                 // Next level
 693                 pos.pPrev[ nLevel ] = pPred;
 694                 pos.pSucc[ nLevel ] = pCur.ptr();
 695             }
 696
 697             return (pos.pCur = pCur.ptr()) != nullptr;
 698         }
 699
 700         template <typename Func>
 701         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 702         {
 703             unsigned int nHeight = pNode->height();
 704
 705             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
 706                 pNode->next(nLevel).store( marked_node_ptr(), memory_model::memory_order_relaxed );
 707
 708             {
 709                 marked_node_ptr p( pos.pSucc[0] );
 710                 pNode->next( 0 ).store( p, memory_model::memory_order_release );
 711                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) ) {
 712                     return false;
 713                 }
 714                 cds::unref( f )( val );
 715             }
 716
 717             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 718                 marked_node_ptr p;
 719                 while ( true ) {
 720                     marked_node_ptr q( pos.pSucc[ nLevel ]);
 721                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
 722                         // pNode has been marked as removed while we are inserting it
 723                         // Stop inserting
 724                         assert( p.bits() );
 725                         m_Stat.onLogicDeleteWhileInsert();
 726                         return true;
 727                     }
 728                     p = q;
 729                     if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) )
 730                         break;
 731
 732                     // Renew insert position
 733                     m_Stat.onRenewInsertPosition();
 734                     if ( !find_position( val, pos, key_comparator(), false )) {
 735                         // The node has been deleted while we are inserting it
 736                         m_Stat.onNotFoundWhileInsert();
 737                         return true;
 738                     }
 739                 }
 740             }
 741             return true;
 742         }
 743
 744         template <typename Func>
 745         bool try_remove_at( node_type * pDel, position& pos, Func f )
 746         {
 747             assert( pDel != nullptr );
 748
 749             marked_node_ptr pSucc;
 750             typename gc::Guard gSucc;
 751
 752             // logical deletion (marking)
 753             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
 754                 while ( true ) {
 755                     pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
 756                     if ( pSucc.bits() || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1,
 757                          memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
 758                     {
 759                         break;
 760                     }
 761                 }
 762             }
 763
 764             while ( true ) {
 765                 pSucc = gSucc.protect( pDel->next(0), gc_protect );
 766                 marked_node_ptr p( pSucc.ptr() );
 767                 if ( pDel->next(0).compare_exchange_strong( p, marked_node_ptr(p.ptr(), 1),
 768                      memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
 769                 {
 770                     cds::unref(f)( *node_traits::to_value_ptr( pDel ));
 771
 772                     // Physical deletion
 773                     // try fast erase
 774                     p = pDel;
 775                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
 776                         pSucc = gSucc.protect( pDel->next(nLevel), gc_protect );
 777                         if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( p, marked_node_ptr(pSucc.ptr()),
 778                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed) )
 779                         {
 780                             // Make slow erase
 781                             find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false );
 782                             m_Stat.onSlowErase();
 783                             return true;
 784                         }
 785                     }
 786
 787                     // Fast erasing success
 788                     gc::retire( node_traits::to_value_ptr( pDel ), dispose_node );
 789                     m_Stat.onFastErase();
 790                     return true;
 791                 }
 792                 else {
 793                     if ( p.bits() ) {
 794                         return false;
 795                     }
 796                 }
 797             }
 798         }
 799
 800         enum finsd_fastpath_result {
 801             find_fastpath_found,
 802             find_fastpath_not_found,
 803             find_fastpath_abort
 804         };
 805         template <typename Q, typename Compare, typename Func>
 806         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f )
 807         {
 808             node_type * pPred;
 809             typename gc::template GuardArray<2>  guards;
 810             marked_node_ptr pCur;
 811             marked_node_ptr pNull;
 812
 813             back_off bkoff;
 814
 815             pPred = m_Head.head();
 816             for ( int nLevel = static_cast<int>( m_nHeight.load(memory_model::memory_order_relaxed) - 1 ); nLevel >= 0; --nLevel ) {
 817                 pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
 818                 if ( pCur == pNull )
 819                     continue;
 820
 821                 while ( pCur != pNull ) {
 822                     if ( pCur.bits() ) {
 823                         unsigned int nAttempt = 0;
 824                         while ( pCur.bits() && nAttempt++ < 16 ) {
 825                             bkoff();
 826                             pCur = guards.protect( 1, pPred->next(nLevel), gc_protect );
 827                         }
 828                         bkoff.reset();
 829
 830                         if ( pCur.bits() ) {
 831                             // Maybe, we are on deleted node sequence
 832                             // Abort searching, try slow-path
 833                             return find_fastpath_abort;
 834                         }
 835                     }
 836
 837                     if ( pCur.ptr() ) {
 838                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
 839                         if ( nCmp < 0 ) {
 840                             guards.copy( 0, 1 );
 841                             pPred = pCur.ptr();
 842                             pCur = guards.protect( 1, pCur->next(nLevel), gc_protect );
 843                         }
 844                         else if ( nCmp == 0 ) {
 845                             // found
 846                             cds::unref(f)( *node_traits::to_value_ptr( pCur.ptr() ), val );
 847                             return find_fastpath_found;
 848                         }
 849                         else // pCur > val - go down
 850                             break;
 851                     }
 852                 }
 853             }
 854
 855             return find_fastpath_not_found;
 856         }
 857
 858         template <typename Q, typename Compare, typename Func>
 859         bool find_slowpath( Q& val, Compare cmp, Func f )
 860         {
 861             position pos;
 862             if ( find_position( val, pos, cmp, true )) {
 863                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 864
 865                 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
 866                 return true;
 867             }
 868             else
 869                 return false;
 870         }
 871
 872         template <typename Q, typename Compare, typename Func>
 873         bool find_with_( Q& val, Compare cmp, Func f )
 874         {
 875             switch ( find_fastpath( val, cmp, f )) {
 876             case find_fastpath_found:
 877                 m_Stat.onFindFastSuccess();
 878                 return true;
 879             case find_fastpath_not_found:
 880                 m_Stat.onFindFastFailed();
 881                 return false;
 882             default:
 883                 break;
 884             }
 885
 886             if ( find_slowpath( val, cmp, f )) {
 887                 m_Stat.onFindSlowSuccess();
 888                 return true;
 889             }
 890
 891             m_Stat.onFindSlowFailed();
 892             return false;
 893         }
 894
 895         template <typename Q, typename Compare>
 896         bool get_with_( typename gc::Guard& guard, Q const& val, Compare cmp )
 897         {
 898 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 899             return find_with_( val, cmp, [&guard](value_type& found, Q const& ) { guard.assign(&found); } );
 900 #       else
 901             get_functor gf(guard);
 902             return find_with_( val, cmp, cds::ref(gf) );
 903 #       endif
 904         }
 905
 906         template <typename Q, typename Compare, typename Func>
 907         bool erase_( Q const& val, Compare cmp, Func f )
 908         {
 909             position pos;
 910
 911             if ( !find_position( val, pos, cmp, false ) ) {
 912                 m_Stat.onEraseFailed();
 913                 return false;
 914             }
 915
 916             node_type * pDel = pos.pCur;
 917             typename gc::Guard gDel;
 918             gDel.assign( node_traits::to_value_ptr(pDel) );
 919             assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 920
 921             unsigned int nHeight = pDel->height();
 922             if ( try_remove_at( pDel, pos, f )) {
 923                 --m_ItemCounter;
 924                 m_Stat.onRemoveNode( nHeight );
 925                 m_Stat.onEraseSuccess();
 926                 return true;
 927             }
 928
 929             m_Stat.onEraseFailed();
 930             return false;
 931         }
 932
 933         template <typename Q, typename Compare>
 934         bool extract_( typename gc::Guard& guard, Q const& val, Compare cmp )
 935         {
 936             position pos;
 937
 938             for (;;) {
 939                 if ( !find_position( val, pos, cmp, false ) ) {
 940                     m_Stat.onExtractFailed();
 941                     return false;
 942                 }
 943
 944                 node_type * pDel = pos.pCur;
 945                 guard.assign( node_traits::to_value_ptr(pDel));
 946                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 947
 948                 unsigned int nHeight = pDel->height();
 949                 if ( try_remove_at( pDel, pos,
 950 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 951                     [](value_type const&) {}
 952 #       else
 953                     empty_erase_functor()
 954 #       endif
 955                     ))
 956                 {
 957                     --m_ItemCounter;
 958                     m_Stat.onRemoveNode( nHeight );
 959                     m_Stat.onExtractSuccess();
 960                     return true;
 961                 }
 962
 963                 m_Stat.onExtractRetry();
 964             }
 965         }
 966
 967         bool extract_min_( typename gc::Guard& gDel )
 968         {
 969             position pos;
 970
 971             for (;;) {
 972                 if ( !find_min_position( pos ) ) {
 973                     // The list is empty
 974                     m_Stat.onExtractMinFailed();
 975                     return false;
 976                 }
 977
 978                 node_type * pDel = pos.pCur;
 979
 980                 unsigned int nHeight = pDel->height();
 981                 gDel.assign( node_traits::to_value_ptr(pDel) );
 982
 983                 if ( try_remove_at( pDel, pos,
 984 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 985                     [](value_type const&) {}
 986 #       else
 987                     empty_erase_functor()
 988 #       endif
 989                     ))
 990                 {
 991                     --m_ItemCounter;
 992                     m_Stat.onRemoveNode( nHeight );
 993                     m_Stat.onExtractMinSuccess();
 994                     return true;
 995                 }
 996
 997                 m_Stat.onExtractMinRetry();
 998             }
 999         }
1000
1001         bool extract_max_( typename gc::Guard& gDel )
1002         {
1003             position pos;
1004
1005             for (;;) {
1006                 if ( !find_max_position( pos ) ) {
1007                     // The list is empty
1008                     m_Stat.onExtractMaxFailed();
1009                     return false;
1010                 }
1011
1012                 node_type * pDel = pos.pCur;
1013
1014                 unsigned int nHeight = pDel->height();
1015                 gDel.assign( node_traits::to_value_ptr(pDel) );
1016
1017                 if ( try_remove_at( pDel, pos,
1018 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1019                     [](value_type const&) {}
1020 #       else
1021                     empty_erase_functor()
1022 #       endif
1023                     ))
1024                 {
1025                     --m_ItemCounter;
1026                     m_Stat.onRemoveNode( nHeight );
1027                     m_Stat.onExtractMaxSuccess();
1028                     return true;
1029                 }
1030
1031                 m_Stat.onExtractMaxRetry();
1032             }
1033         }
1034
1035         void increase_height( unsigned int nHeight )
1036         {
1037             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1038             if ( nCur < nHeight )
1039                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1040         }
1041         //@endcond
1042
1043     public:
1044         /// Default constructor
1045         /**
1046             The constructor checks whether the count of guards is enough
1047             for skip-list and may raise an exception if not.
1048         */
1049         SkipListSet()
1050             : m_Head( c_nMaxHeight )
1051             , m_nHeight( c_nMinHeight )
1052         {
1053             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
1054
1055             gc::check_available_guards( c_nHazardPtrCount );
1056
1057             // Barrier for head node
1058             CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
1059         }
1060
1061         /// Clears and destructs the skip-list
1062         ~SkipListSet()
1063         {
1064             clear();
1065         }
1066
1067     public:
1068         /// Iterator type
1069         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
1070
1071         /// Const iterator type
1072         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
1073
1074         /// Returns a forward iterator addressing the first element in a set
1075         iterator begin()
1076         {
1077             return iterator( *m_Head.head() );
1078         }
1079
1080         /// Returns a forward const iterator addressing the first element in a set
1081         //@{
1082         const_iterator begin() const
1083         {
1084             return const_iterator( *m_Head.head() );
1085         }
1086         const_iterator cbegin()
1087         {
1088             return const_iterator( *m_Head.head() );
1089         }
1090         //@}
1091
1092         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1093         iterator end()
1094         {
1095             return iterator();
1096         }
1097
1098         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1099         //@{
1100         const_iterator end() const
1101         {
1102             return const_iterator();
1103         }
1104         const_iterator cend()
1105         {
1106             return const_iterator();
1107         }
1108         //@}
1109
1110     public:
1111         /// Inserts new node
1112         /**
1113             The function inserts \p val in the set if it does not contain
1114             an item with key equal to \p val.
1115
1116             Returns \p true if \p val is placed into the set, \p false otherwise.
1117         */
1118         bool insert( value_type& val )
1119         {
1120 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1121             return insert( val, []( value_type& ) {} );
1122 #       else
1123             return insert( val, empty_insert_functor() );
1124 #       endif
1125         }
1126
1127         /// Inserts new node
1128         /**
1129             This function is intended for derived non-intrusive containers.
1130
1131             The function allows to split creating of new item into two part:
1132             - create item with key only
1133             - insert new item into the set
1134             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1135
1136             The functor signature is:
1137             \code
1138                 void func( value_type& val );
1139             \endcode
1140             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1141             \p val no any other changes could be made on this set's item by concurrent threads.
1142             The user-defined functor is called only if the inserting is success and may be passed by reference
1143             using <tt>boost::ref</tt>
1144         */
1145         template <typename Func>
1146         bool insert( value_type& val, Func f )
1147         {
1148             typename gc::Guard gNew;
1149             gNew.assign( &val );
1150
1151             node_type * pNode = node_traits::to_node_ptr( val );
1152             scoped_node_ptr scp( pNode );
1153             unsigned int nHeight = pNode->height();
1154             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1155             bool bTowerMade = false;
1156
1157             position pos;
1158             while ( true )
1159             {
1160                 bool bFound = find_position( val, pos, key_comparator(), true );
1161                 if ( bFound ) {
1162                     // scoped_node_ptr deletes the node tower if we create it
1163                     if ( !bTowerMade )
1164                         scp.release();
1165
1166                     m_Stat.onInsertFailed();
1167                     return false;
1168                 }
1169
1170                 if ( !bTowerOk ) {
1171                     build_node( pNode );
1172                     nHeight = pNode->height();
1173                     bTowerMade =
1174                         bTowerOk = true;
1175                 }
1176
1177                 if ( !insert_at_position( val, pNode, pos, f )) {
1178                     m_Stat.onInsertRetry();
1179                     continue;
1180                 }
1181
1182                 increase_height( nHeight );
1183                 ++m_ItemCounter;
1184                 m_Stat.onAddNode( nHeight );
1185                 m_Stat.onInsertSuccess();
1186                 scp.release();
1187                 return true;
1188             }
1189         }
1190
1191         /// Ensures that the \p val exists in the set
1192         /**
1193             The operation performs inserting or changing data with lock-free manner.
1194
1195             If the item \p val is not found in the set, then \p val is inserted into the set.
1196             Otherwise, the functor \p func is called with item found.
1197             The functor signature is:
1198             \code
1199                 void func( bool bNew, value_type& item, value_type& val );
1200             \endcode
1201             with arguments:
1202             - \p bNew - \p true if the item has been inserted, \p false otherwise
1203             - \p item - item of the set
1204             - \p val - argument \p val passed into the \p ensure function
1205             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1206             refer to the same thing.
1207
1208             The functor can change non-key fields of the \p item; however, \p func must guarantee
1209             that during changing no any other modifications could be made on this item by concurrent threads.
1210
1211             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1212
1213             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1214             \p second is \p true if new item has been added or \p false if the item with \p key
1215             already is in the set.
1216         */
1217         template <typename Func>
1218         std::pair<bool, bool> ensure( value_type& val, Func func )
1219         {
1220             typename gc::Guard gNew;
1221             gNew.assign( &val );
1222
1223             node_type * pNode = node_traits::to_node_ptr( val );
1224             scoped_node_ptr scp( pNode );
1225             unsigned int nHeight = pNode->height();
1226             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1227             bool bTowerMade = false;
1228
1229 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
1230             insert_at_ensure_functor<Func> wrapper( func );
1231 #       endif
1232
1233             position pos;
1234             while ( true )
1235             {
1236                 bool bFound = find_position( val, pos, key_comparator(), true );
1237                 if ( bFound ) {
1238                     // scoped_node_ptr deletes the node tower if we create it before
1239                     if ( !bTowerMade )
1240                         scp.release();
1241
1242                     cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
1243                     m_Stat.onEnsureExist();
1244                     return std::make_pair( true, false );
1245                 }
1246
1247                 if ( !bTowerOk ) {
1248                     build_node( pNode );
1249                     nHeight = pNode->height();
1250                     bTowerMade =
1251                         bTowerOk = true;
1252                 }
1253
1254 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1255                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
1256 #       else
1257                 if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
1258 #       endif
1259                 {
1260                     m_Stat.onInsertRetry();
1261                     continue;
1262                 }
1263
1264                 increase_height( nHeight );
1265                 ++m_ItemCounter;
1266                 scp.release();
1267                 m_Stat.onAddNode( nHeight );
1268                 m_Stat.onEnsureNew();
1269                 return std::make_pair( true, true );
1270             }
1271         }
1272
1273         /// Unlinks the item \p val from the set
1274         /**
1275             The function searches the item \p val in the set and unlink it from the set
1276             if it is found and is equal to \p val.
1277
1278             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
1279             and deletes the item found. \p unlink finds an item by key and deletes it
1280             only if \p val is an item of that set, i.e. the pointer to item found
1281             is equal to <tt> &val </tt>.
1282
1283             The \ref disposer specified in \p Traits class template parameter is called
1284             by garbage collector \p GC asynchronously.
1285
1286             The function returns \p true if success and \p false otherwise.
1287         */
1288         bool unlink( value_type& val )
1289         {
1290             position pos;
1291
1292             if ( !find_position( val, pos, key_comparator(), false ) ) {
1293                 m_Stat.onUnlinkFailed();
1294                 return false;
1295             }
1296
1297             node_type * pDel = pos.pCur;
1298             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1299
1300             unsigned int nHeight = pDel->height();
1301             typename gc::Guard gDel;
1302             gDel.assign( node_traits::to_value_ptr(pDel) );
1303
1304             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos,
1305 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1306                 [](value_type const&) {}
1307 #       else
1308                 empty_erase_functor()
1309 #       endif
1310             ))
1311             {
1312                 --m_ItemCounter;
1313                 m_Stat.onRemoveNode( nHeight );
1314                 m_Stat.onUnlinkSuccess();
1315                 return true;
1316             }
1317
1318             m_Stat.onUnlinkFailed();
1319             return false;
1320         }
1321
1322         /// Extracts the item from the set with specified \p key
1323         /** \anchor cds_intrusive_SkipListSet_hp_extract
1324             The function searches an item with key equal to \p key in the set,
1325             unlinks it from the set, and returns it in \p dest parameter.
1326             If the item with key equal to \p key is not found the function returns \p false.
1327
1328             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1329
1330             The \ref disposer specified in \p Traits class template parameter is called automatically
1331             by garbage collector \p GC specified in class' template parameters when returned \ref guarded_ptr object
1332             will be destroyed or released.
1333             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1334
1335             Usage:
1336             \code
1337             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1338             skip_list theList;
1339             // ...
1340             {
1341                 skip_list::guarded_ptr gp;
1342                 theList.extract( gp, 5 );
1343                 // Deal with gp
1344                 // ...
1345
1346                 // Destructor of gp releases internal HP guard
1347             }
1348             \endcode
1349         */
1350         template <typename Q>
1351         bool extract( guarded_ptr& dest, Q const& key )
1352         {
1353             return extract_( dest.guard(), key, key_comparator() );
1354         }
1355
1356         /// Extracts the item from the set with comparing functor \p pred
1357         /**
1358             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1359             but \p pred predicate is used for key comparing.
1360
1361             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1362             in any order.
1363             \p pred must imply the same element order as the comparator used for building the set.
1364         */
1365         template <typename Q, typename Less>
1366         bool extract_with( guarded_ptr& dest, Q const& key, Less pred )
1367         {
1368             return extract_( dest.guard(), key, cds::opt::details::make_comparator_from_less<Less>() );
1369         }
1370
1371         /// Extracts an item with minimal key from the list
1372         /**
1373             The function searches an item with minimal key, unlinks it, and returns the item found in \p dest parameter.
1374             If the skip-list is empty the function returns \p false.
1375
1376             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1377             It means that the function gets leftmost item and tries to unlink it.
1378             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1379             So, the function returns the item with minimum key at the moment of list traversing.
1380
1381             The \ref disposer specified in \p Traits class template parameter is called
1382             by garbage collector \p GC automatically when returned \ref guarded_ptr object
1383             will be destroyed or released.
1384             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1385
1386             Usage:
1387             \code
1388             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1389             skip_list theList;
1390             // ...
1391             {
1392                 skip_list::guarded_ptr gp;
1393                 if ( theList.extract_min( gp )) {
1394                     // Deal with gp
1395                     //...
1396                 }
1397                 // Destructor of gp releases internal HP guard
1398             }
1399             \endcode
1400         */
1401         bool extract_min( guarded_ptr& dest)
1402         {
1403             return extract_min_( dest.guard() );
1404         }
1405
1406         /// Extracts an item with maximal key from the list
1407         /**
1408             The function searches an item with maximal key, unlinks it, and returns the pointer to item found in \p dest parameter.
1409             If the skip-list is empty the function returns empty \p guarded_ptr.
1410
1411             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1412             It means that the function gets rightmost item and tries to unlink it.
1413             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1414             So, the function returns the item with maximum key at the moment of list traversing.
1415
1416             The \ref disposer specified in \p Traits class template parameter is called
1417             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1418             will be destroyed or released.
1419             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1420
1421             Usage:
1422             \code
1423             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1424             skip_list theList;
1425             // ...
1426             {
1427                 skip_list::guarded_ptr gp;
1428                 if ( theList.extract_max( gp )) {
1429                     // Deal with gp
1430                     //...
1431                 }
1432                 // Destructor of gp releases internal HP guard
1433             }
1434             \endcode
1435         */
1436         bool extract_max( guarded_ptr& dest )
1437         {
1438             return extract_max_( dest.guard() );
1439         }
1440
1441         /// Deletes the item from the set
1442         /** \anchor cds_intrusive_SkipListSet_hp_erase
1443             The function searches an item with key equal to \p val in the set,
1444             unlinks it from the set, and returns \p true.
1445             If the item with key equal to \p val is not found the function return \p false.
1446
1447             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1448         */
1449         template <typename Q>
1450         bool erase( Q const& val )
1451         {
1452 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1453             return erase_( val, key_comparator(), [](value_type const&) {} );
1454 #       else
1455             return erase_( val, key_comparator(), empty_erase_functor() );
1456 #       endif
1457         }
1458
1459         /// Deletes the item from the set with comparing functor \p pred
1460         /**
1461             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase "erase(Q const&)"
1462             but \p pred predicate is used for key comparing.
1463
1464             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1465             in any order.
1466             \p pred must imply the same element order as the comparator used for building the set.
1467         */
1468         template <typename Q, typename Less>
1469         bool erase_with( Q const& val, Less pred )
1470         {
1471 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1472             return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1473 #       else
1474             return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_erase_functor() );
1475 #       endif
1476         }
1477
1478         /// Deletes the item from the set
1479         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1480             The function searches an item with key equal to \p val in the set,
1481             call \p f functor with item found, unlinks it from the set, and returns \p true.
1482             The \ref disposer specified in \p Traits class template parameter is called
1483             by garbage collector \p GC asynchronously.
1484
1485             The \p Func interface is
1486             \code
1487             struct functor {
1488                 void operator()( value_type const& item );
1489             };
1490             \endcode
1491             The functor can be passed by reference with <tt>boost:ref</tt>
1492
1493             If the item with key equal to \p val is not found the function return \p false.
1494
1495             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1496         */
1497         template <typename Q, typename Func>
1498         bool erase( Q const& val, Func f )
1499         {
1500             return erase_( val, key_comparator(), f );
1501         }
1502
1503         /// Deletes the item from the set with comparing functor \p pred
1504         /**
1505             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1506             but \p pred predicate is used for key comparing.
1507
1508             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1509             in any order.
1510             \p pred must imply the same element order as the comparator used for building the set.
1511         */
1512         template <typename Q, typename Less, typename Func>
1513         bool erase_with( Q const& val, Less pred, Func f )
1514         {
1515             return erase_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1516         }
1517
1518         /// Finds the key \p val
1519         /** \anchor cds_intrusive_SkipListSet_hp_find_func
1520             The function searches the item with key equal to \p val and calls the functor \p f for item found.
1521             The interface of \p Func functor is:
1522             \code
1523             struct functor {
1524                 void operator()( value_type& item, Q& val );
1525             };
1526             \endcode
1527             where \p item is the item found, \p val is the <tt>find</tt> function argument.
1528
1529             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1530
1531             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1532             that \p item cannot be disposed during functor is executing.
1533             The functor does not serialize simultaneous access to the set \p item. If such access is
1534             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1535
1536             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1537             can modify both arguments.
1538
1539             Note the compare functor specified for class \p Traits template parameter
1540             should accept a parameter of type \p Q that can be not the same as \p value_type.
1541
1542             The function returns \p true if \p val is found, \p false otherwise.
1543         */
1544         template <typename Q, typename Func>
1545         bool find( Q& val, Func f )
1546         {
1547             return find_with_( val, key_comparator(), f );
1548         }
1549
1550         /// Finds the key \p val with \p pred predicate for comparing
1551         /**
1552             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1553             but \p pred is used for key compare.
1554
1555             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1556             in any order.
1557             \p pred must imply the same element order as the comparator used for building the set.
1558         */
1559         template <typename Q, typename Less, typename Func>
1560         bool find_with( Q& val, Less pred, Func f )
1561         {
1562             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1563         }
1564
1565         /// Finds the key \p val
1566         /** \anchor cds_intrusive_SkipListSet_hp_find_cfunc
1567             The function searches the item with key equal to \p val and calls the functor \p f for item found.
1568             The interface of \p Func functor is:
1569             \code
1570             struct functor {
1571                 void operator()( value_type& item, Q const& val );
1572             };
1573             \endcode
1574             where \p item is the item found, \p val is the <tt>find</tt> function argument.
1575
1576             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1577
1578             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1579             that \p item cannot be disposed during functor is executing.
1580             The functor does not serialize simultaneous access to the set \p item. If such access is
1581             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1582
1583             Note the compare functor specified for class \p Traits template parameter
1584             should accept a parameter of type \p Q that can be not the same as \p value_type.
1585
1586             The function returns \p true if \p val is found, \p false otherwise.
1587         */
1588         template <typename Q, typename Func>
1589         bool find( Q const& val, Func f )
1590         {
1591             return find_with_( val, key_comparator(), f );
1592         }
1593
1594         /// Finds the key \p val with \p pred predicate for comparing
1595         /**
1596             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_cfunc "find(Q const&, Func)"
1597             but \p pred is used for key compare.
1598             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1599             in any order.
1600             \p pred must imply the same element order as the comparator used for building the set.
1601         */
1602         template <typename Q, typename Less, typename Func>
1603         bool find_with( Q const& val, Less pred, Func f )
1604         {
1605             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1606         }
1607
1608         /// Finds the key \p val
1609         /** \anchor cds_intrusive_SkipListSet_hp_find_val
1610             The function searches the item with key equal to \p val
1611             and returns \p true if it is found, and \p false otherwise.
1612
1613             Note the compare functor specified for class \p Traits template parameter
1614             should accept a parameter of type \p Q that can be not the same as \p value_type.
1615         */
1616         template <typename Q>
1617         bool find( Q const & val )
1618         {
1619 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1620             return find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
1621 #       else
1622             return find_with_( val, key_comparator(), empty_find_functor() );
1623 #       endif
1624         }
1625
1626         /// Finds the key \p val with comparing functor \p pred
1627         /**
1628             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_val "find(Q const&)"
1629             but \p pred is used for comparing the keys.
1630             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1631             in any order.
1632             \p pred must imply the same element order as the comparator used for building the set.
1633         */
1634         template <typename Q, typename Less>
1635         bool find_with( Q const& val, Less pred )
1636         {
1637 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1638             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1639 #       else
1640             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
1641 #       endif
1642         }
1643
1644         /// Finds the key \p val and return the item found
1645         /** \anchor cds_intrusive_SkipListSet_hp_get
1646             The function searches the item with key equal to \p val
1647             and assigns the item found to guarded pointer \p ptr.
1648             The function returns \p true if \p val is found, and \p false otherwise.
1649             If \p val is not found the \p ptr parameter is not changed.
1650
1651             The \ref disposer specified in \p Traits class template parameter is called
1652             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1653             will be destroyed or released.
1654             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1655
1656             Usage:
1657             \code
1658             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1659             skip_list theList;
1660             // ...
1661             {
1662                 skip_list::guarded_ptr gp;
1663                 if ( theList.get( gp, 5 )) {
1664                     // Deal with gp
1665                     //...
1666                 }
1667                 // Destructor of guarded_ptr releases internal HP guard
1668             }
1669             \endcode
1670
1671             Note the compare functor specified for class \p Traits template parameter
1672             should accept a parameter of type \p Q that can be not the same as \p value_type.
1673         */
1674         template <typename Q>
1675         bool get( guarded_ptr& ptr, Q const& val )
1676         {
1677             return get_with_( ptr.guard(), val, key_comparator() );
1678         }
1679
1680         /// Finds the key \p val and return the item found
1681         /**
1682             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( guarded_ptr& ptr, Q const&)"
1683             but \p pred is used for comparing the keys.
1684
1685             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1686             in any order.
1687             \p pred must imply the same element order as the comparator used for building the set.
1688         */
1689         template <typename Q, typename Less>
1690         bool get_with( guarded_ptr& ptr, Q const& val, Less pred )
1691         {
1692             return get_with_( ptr.guard(), val, cds::opt::details::make_comparator_from_less<Less>() );
1693         }
1694
1695         /// Returns item count in the set
1696         /**
1697             The value returned depends on item counter type provided by \p Traits template parameter.
1698             If it is atomicity::empty_item_counter this function always returns 0.
1699             Therefore, the function is not suitable for checking the set emptiness, use \ref empty
1700             member function for this purpose.
1701         */
1702         size_t size() const
1703         {
1704             return m_ItemCounter;
1705         }
1706
1707         /// Checks if the set is empty
1708         bool empty() const
1709         {
1710             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1711         }
1712
1713         /// Clears the set (non-atomic)
1714         /**
1715             The function unlink all items from the set.
1716             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1717             this sequence
1718             \code
1719             set.clear();
1720             assert( set.empty() );
1721             \endcode
1722             the assertion could be raised.
1723
1724             For each item the \ref disposer will be called after unlinking.
1725         */
1726         void clear()
1727         {
1728             guarded_ptr gp;
1729             while ( extract_min( gp ));
1730         }
1731
1732         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1733         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1734         {
1735             return c_nMaxHeight;
1736         }
1737
1738         /// Returns const reference to internal statistics
1739         stat const& statistics() const
1740         {
1741             return m_Stat;
1742         }
1743
1744     };
1745
1746 }} // namespace cds::intrusive
1747
1748
1749 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H