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