cds/intrusive/impl/skip_list.h

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