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         guarded_ptr get_with_( Q const& val, Compare cmp )
 847         {
 848             guarded_ptr gp;
 849             if ( find_with_( val, cmp, [&gp](value_type& found, Q const& ) { gp.reset(&found); } ))
 850                 return gp;
 851             return guarded_ptr();
 852         }
 853
 854         template <typename Q, typename Compare, typename Func>
 855         bool erase_( Q const& val, Compare cmp, Func f )
 856         {
 857             position pos;
 858
 859             if ( !find_position( val, pos, cmp, false )) {
 860                 m_Stat.onEraseFailed();
 861                 return false;
 862             }
 863
 864             node_type * pDel = pos.pCur;
 865             typename gc::Guard gDel;
 866             gDel.assign( node_traits::to_value_ptr(pDel));
 867             assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 868
 869             unsigned int nHeight = pDel->height();
 870             if ( try_remove_at( pDel, pos, f )) {
 871                 --m_ItemCounter;
 872                 m_Stat.onRemoveNode( nHeight );
 873                 m_Stat.onEraseSuccess();
 874                 return true;
 875             }
 876
 877             m_Stat.onEraseFailed();
 878             return false;
 879         }
 880
 881         template <typename Q, typename Compare>
 882         guarded_ptr extract_( Q const& val, Compare cmp )
 883         {
 884             position pos;
 885
 886             guarded_ptr gp;
 887             for (;;) {
 888                 if ( !find_position( val, pos, cmp, false )) {
 889                     m_Stat.onExtractFailed();
 890                     return guarded_ptr();
 891                 }
 892
 893                 node_type * pDel = pos.pCur;
 894                 gp.reset( node_traits::to_value_ptr( pDel ));
 895                 assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
 896
 897                 unsigned int nHeight = pDel->height();
 898                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 899                     --m_ItemCounter;
 900                     m_Stat.onRemoveNode( nHeight );
 901                     m_Stat.onExtractSuccess();
 902                     return gp;
 903                 }
 904                 m_Stat.onExtractRetry();
 905             }
 906         }
 907
 908         guarded_ptr extract_min_()
 909         {
 910             position pos;
 911
 912             guarded_ptr gp;
 913             for (;;) {
 914                 if ( !find_min_position( pos )) {
 915                     // The list is empty
 916                     m_Stat.onExtractMinFailed();
 917                     return guarded_ptr();
 918                 }
 919
 920                 node_type * pDel = pos.pCur;
 921
 922                 unsigned int nHeight = pDel->height();
 923                 gp.reset( node_traits::to_value_ptr(pDel));
 924
 925                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 926                     --m_ItemCounter;
 927                     m_Stat.onRemoveNode( nHeight );
 928                     m_Stat.onExtractMinSuccess();
 929                     return gp;
 930                 }
 931
 932                 m_Stat.onExtractMinRetry();
 933             }
 934         }
 935
 936         guarded_ptr extract_max_()
 937         {
 938             position pos;
 939
 940             guarded_ptr gp;
 941             for (;;) {
 942                 if ( !find_max_position( pos )) {
 943                     // The list is empty
 944                     m_Stat.onExtractMaxFailed();
 945                     return guarded_ptr();
 946                 }
 947
 948                 node_type * pDel = pos.pCur;
 949
 950                 unsigned int nHeight = pDel->height();
 951                 gp.reset( node_traits::to_value_ptr(pDel));
 952
 953                 if ( try_remove_at( pDel, pos, [](value_type const&) {} )) {
 954                     --m_ItemCounter;
 955                     m_Stat.onRemoveNode( nHeight );
 956                     m_Stat.onExtractMaxSuccess();
 957                     return gp;
 958                 }
 959
 960                 m_Stat.onExtractMaxRetry();
 961             }
 962         }
 963
 964         void increase_height( unsigned int nHeight )
 965         {
 966             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
 967             if ( nCur < nHeight )
 968                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
 969         }
 970         //@endcond
 971
 972     public:
 973         /// Default constructor
 974         /**
 975             The constructor checks whether the count of guards is enough
 976             for skip-list and may raise an exception if not.
 977         */
 978         SkipListSet()
 979             : m_Head( c_nMaxHeight )
 980             , m_nHeight( c_nMinHeight )
 981         {
 982             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 983
 984             gc::check_available_guards( c_nHazardPtrCount );
 985
 986             // Barrier for head node
 987             atomics::atomic_thread_fence( memory_model::memory_order_release );
 988         }
 989
 990         /// Clears and destructs the skip-list
 991         ~SkipListSet()
 992         {
 993             clear();
 994         }
 995
 996     public:
 997     ///@name Forward iterators (only for debugging purpose)
 998     //@{
 999         /// Iterator type
1000         /**
1001             The forward iterator has some features:
1002             - it has no post-increment operator
1003             - to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
1004               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
1005               may be thrown if the limit of guard count per thread is exceeded.
1006             - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
1007             - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
1008               deleting operations there is no guarantee that you iterate all item in the list.
1009               Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
1010
1011             @warning Use this iterator on the concurrent container for debugging purpose only.
1012
1013             The iterator interface:
1014             \code
1015             class iterator {
1016             public:
1017                 // Default constructor
1018                 iterator();
1019
1020                 // Copy construtor
1021                 iterator( iterator const& src );
1022
1023                 // Dereference operator
1024                 value_type * operator ->() const;
1025
1026                 // Dereference operator
1027                 value_type& operator *() const;
1028
1029                 // Preincrement operator
1030                 iterator& operator ++();
1031
1032                 // Assignment operator
1033                 iterator& operator = (iterator const& src);
1034
1035                 // Equality operators
1036                 bool operator ==(iterator const& i ) const;
1037                 bool operator !=(iterator const& i ) const;
1038             };
1039             \endcode
1040         */
1041         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
1042
1043         /// Const iterator type
1044         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
1045
1046         /// Returns a forward iterator addressing the first element in a set
1047         iterator begin()
1048         {
1049             return iterator( *m_Head.head());
1050         }
1051
1052         /// Returns a forward const iterator addressing the first element in a set
1053         const_iterator begin() const
1054         {
1055             return const_iterator( *m_Head.head());
1056         }
1057         /// Returns a forward const iterator addressing the first element in a set
1058         const_iterator cbegin() const
1059         {
1060             return const_iterator( *m_Head.head());
1061         }
1062
1063         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1064         iterator end()
1065         {
1066             return iterator();
1067         }
1068
1069         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1070         const_iterator end() const
1071         {
1072             return const_iterator();
1073         }
1074         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1075         const_iterator cend() const
1076         {
1077             return const_iterator();
1078         }
1079     //@}
1080
1081     public:
1082         /// Inserts new node
1083         /**
1084             The function inserts \p val in the set if it does not contain
1085             an item with key equal to \p val.
1086
1087             Returns \p true if \p val is placed into the set, \p false otherwise.
1088         */
1089         bool insert( value_type& val )
1090         {
1091             return insert( val, []( value_type& ) {} );
1092         }
1093
1094         /// Inserts new node
1095         /**
1096             This function is intended for derived non-intrusive containers.
1097
1098             The function allows to split creating of new item into two part:
1099             - create item with key only
1100             - insert new item into the set
1101             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1102
1103             The functor signature is:
1104             \code
1105                 void func( value_type& val );
1106             \endcode
1107             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1108             \p val no any other changes could be made on this set's item by concurrent threads.
1109             The user-defined functor is called only if the inserting is success.
1110         */
1111         template <typename Func>
1112         bool insert( value_type& val, Func f )
1113         {
1114             typename gc::Guard gNew;
1115             gNew.assign( &val );
1116
1117             node_type * pNode = node_traits::to_node_ptr( val );
1118             scoped_node_ptr scp( pNode );
1119             unsigned int nHeight = pNode->height();
1120             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1121             bool bTowerMade = false;
1122
1123             position pos;
1124             while ( true )
1125             {
1126                 if ( find_position( val, pos, key_comparator(), true )) {
1127                     // scoped_node_ptr deletes the node tower if we create it
1128                     if ( !bTowerMade )
1129                         scp.release();
1130
1131                     m_Stat.onInsertFailed();
1132                     return false;
1133                 }
1134
1135                 if ( !bTowerOk ) {
1136                     build_node( pNode );
1137                     nHeight = pNode->height();
1138                     bTowerMade =
1139                         bTowerOk = true;
1140                 }
1141
1142                 if ( !insert_at_position( val, pNode, pos, f )) {
1143                     m_Stat.onInsertRetry();
1144                     continue;
1145                 }
1146
1147                 increase_height( nHeight );
1148                 ++m_ItemCounter;
1149                 m_Stat.onAddNode( nHeight );
1150                 m_Stat.onInsertSuccess();
1151                 scp.release();
1152                 return true;
1153             }
1154         }
1155
1156         /// Updates the node
1157         /**
1158             The operation performs inserting or changing data with lock-free manner.
1159
1160             If the item \p val is not found in the set, then \p val is inserted into the set
1161             iff \p bInsert is \p true.
1162             Otherwise, the functor \p func is called with item found.
1163             The functor \p func signature is:
1164             \code
1165                 void func( bool bNew, value_type& item, value_type& val );
1166             \endcode
1167             with arguments:
1168             - \p bNew - \p true if the item has been inserted, \p false otherwise
1169             - \p item - item of the set
1170             - \p val - argument \p val passed into the \p %update() function
1171             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1172             refer to the same thing.
1173
1174             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
1175             i.e. the node has been inserted or updated,
1176             \p second is \p true if new item has been added or \p false if the item with \p key
1177             already exists.
1178
1179             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1180         */
1181         template <typename Func>
1182         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
1183         {
1184             typename gc::Guard gNew;
1185             gNew.assign( &val );
1186
1187             node_type * pNode = node_traits::to_node_ptr( val );
1188             scoped_node_ptr scp( pNode );
1189             unsigned int nHeight = pNode->height();
1190             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1191             bool bTowerMade = false;
1192
1193             position pos;
1194             while ( true )
1195             {
1196                 bool bFound = find_position( val, pos, key_comparator(), true );
1197                 if ( bFound ) {
1198                     // scoped_node_ptr deletes the node tower if we create it before
1199                     if ( !bTowerMade )
1200                         scp.release();
1201
1202                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
1203                     m_Stat.onUpdateExist();
1204                     return std::make_pair( true, false );
1205                 }
1206
1207                 if ( !bInsert ) {
1208                     scp.release();
1209                     return std::make_pair( false, false );
1210                 }
1211
1212                 if ( !bTowerOk ) {
1213                     build_node( pNode );
1214                     nHeight = pNode->height();
1215                     bTowerMade =
1216                         bTowerOk = true;
1217                 }
1218
1219                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1220                     m_Stat.onInsertRetry();
1221                     continue;
1222                 }
1223
1224                 increase_height( nHeight );
1225                 ++m_ItemCounter;
1226                 scp.release();
1227                 m_Stat.onAddNode( nHeight );
1228                 m_Stat.onUpdateNew();
1229                 return std::make_pair( true, true );
1230             }
1231         }
1232         //@cond
1233         template <typename Func>
1234         CDS_DEPRECATED("ensure() is deprecated, use update()")
1235         std::pair<bool, bool> ensure( value_type& val, Func func )
1236         {
1237             return update( val, func, true );
1238         }
1239         //@endcond
1240
1241         /// Unlinks the item \p val from the set
1242         /**
1243             The function searches the item \p val in the set and unlink it from the set
1244             if it is found and is equal to \p val.
1245
1246             Difference between \p erase() and \p %unlink() functions: \p %erase() finds <i>a key</i>
1247             and deletes the item found. \p %unlink() finds an item by key and deletes it
1248             only if \p val is an item of that set, i.e. the pointer to item found
1249             is equal to <tt> &val </tt>.
1250
1251             The \p disposer specified in \p Traits class template parameter is called
1252             by garbage collector \p GC asynchronously.
1253
1254             The function returns \p true if success and \p false otherwise.
1255         */
1256         bool unlink( value_type& val )
1257         {
1258             position pos;
1259
1260             if ( !find_position( val, pos, key_comparator(), false )) {
1261                 m_Stat.onUnlinkFailed();
1262                 return false;
1263             }
1264
1265             node_type * pDel = pos.pCur;
1266             assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1267
1268             unsigned int nHeight = pDel->height();
1269             typename gc::Guard gDel;
1270             gDel.assign( node_traits::to_value_ptr(pDel));
1271
1272             if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {} )) {
1273                 --m_ItemCounter;
1274                 m_Stat.onRemoveNode( nHeight );
1275                 m_Stat.onUnlinkSuccess();
1276                 return true;
1277             }
1278
1279             m_Stat.onUnlinkFailed();
1280             return false;
1281         }
1282
1283         /// Extracts the item from the set with specified \p key
1284         /** \anchor cds_intrusive_SkipListSet_hp_extract
1285             The function searches an item with key equal to \p key in the set,
1286             unlinks it from the set, and returns it as \p guarded_ptr object.
1287             If \p key is not found the function returns an empty guarded pointer.
1288
1289             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1290
1291             The \p disposer specified in \p Traits class template parameter is called automatically
1292             by garbage collector \p GC specified in class' template parameters when returned \p guarded_ptr object
1293             will be destroyed or released.
1294             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1295
1296             Usage:
1297             \code
1298             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1299             skip_list theList;
1300             // ...
1301             {
1302                 skip_list::guarded_ptr gp(theList.extract( 5 ));
1303                 if ( gp ) {
1304                     // Deal with gp
1305                     // ...
1306                 }
1307                 // Destructor of gp releases internal HP guard
1308             }
1309             \endcode
1310         */
1311         template <typename Q>
1312         guarded_ptr extract( Q const& key )
1313         {
1314             return extract_( key, key_comparator());
1315         }
1316
1317         /// Extracts the item from the set with comparing functor \p pred
1318         /**
1319             The function is an analog of \ref cds_intrusive_SkipListSet_hp_extract "extract(Q const&)"
1320             but \p pred predicate is used for key comparing.
1321
1322             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1323             in any order.
1324             \p pred must imply the same element order as the comparator used for building the set.
1325         */
1326         template <typename Q, typename Less>
1327         guarded_ptr extract_with( Q const& key, Less pred )
1328         {
1329             CDS_UNUSED( pred );
1330             return extract_( key, cds::opt::details::make_comparator_from_less<Less>());
1331         }
1332
1333         /// Extracts an item with minimal key from the list
1334         /**
1335             The function searches an item with minimal key, unlinks it, and returns it as \p guarded_ptr object.
1336             If the skip-list is empty the function returns an empty guarded pointer.
1337
1338             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1339             It means that the function gets leftmost item and tries to unlink it.
1340             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1341             So, the function returns the item with minimum key at the moment of list traversing.
1342
1343             The \p disposer specified in \p Traits class template parameter is called
1344             by garbage collector \p GC automatically when returned \p guarded_ptr object
1345             will be destroyed or released.
1346             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1347
1348             Usage:
1349             \code
1350             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1351             skip_list theList;
1352             // ...
1353             {
1354                 skip_list::guarded_ptr gp(theList.extract_min());
1355                 if ( gp ) {
1356                     // Deal with gp
1357                     //...
1358                 }
1359                 // Destructor of gp releases internal HP guard
1360             }
1361             \endcode
1362         */
1363         guarded_ptr extract_min()
1364         {
1365             return extract_min_();
1366         }
1367
1368         /// Extracts an item with maximal key from the list
1369         /**
1370             The function searches an item with maximal key, unlinks it, and returns the pointer to item
1371             as \p guarded_ptr object.
1372             If the skip-list is empty the function returns an empty \p guarded_ptr.
1373
1374             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1375             It means that the function gets rightmost item and tries to unlink it.
1376             During unlinking, a concurrent thread may insert an item with key greater than rightmost item's key.
1377             So, the function returns the item with maximum key at the moment of list traversing.
1378
1379             The \p disposer specified in \p Traits class template parameter is called
1380             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1381             will be destroyed or released.
1382             @note Each \p guarded_ptr object uses the GC's guard that can be limited resource.
1383
1384             Usage:
1385             \code
1386             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits > skip_list;
1387             skip_list theList;
1388             // ...
1389             {
1390                 skip_list::guarded_ptr gp( theList.extract_max( gp ));
1391                 if ( gp ) {
1392                     // Deal with gp
1393                     //...
1394                 }
1395                 // Destructor of gp releases internal HP guard
1396             }
1397             \endcode
1398         */
1399         guarded_ptr extract_max()
1400         {
1401             return extract_max_();
1402         }
1403
1404         /// Deletes the item from the set
1405         /** \anchor cds_intrusive_SkipListSet_hp_erase
1406             The function searches an item with key equal to \p key in the set,
1407             unlinks it from the set, and returns \p true.
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>
1413         bool erase( Q const& key )
1414         {
1415             return erase_( key, key_comparator(), [](value_type const&) {} );
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 "erase(Q const&)"
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>
1428         bool erase_with( Q const& key, Less pred )
1429         {
1430             CDS_UNUSED( pred );
1431             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1432         }
1433
1434         /// Deletes the item from the set
1435         /** \anchor cds_intrusive_SkipListSet_hp_erase_func
1436             The function searches an item with key equal to \p key in the set,
1437             call \p f functor with item found, unlinks it from the set, and returns \p true.
1438             The \ref disposer specified in \p Traits class template parameter is called
1439             by garbage collector \p GC asynchronously.
1440
1441             The \p Func interface is
1442             \code
1443             struct functor {
1444                 void operator()( value_type const& item );
1445             };
1446             \endcode
1447
1448             If the item with key equal to \p key is not found the function return \p false.
1449
1450             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1451         */
1452         template <typename Q, typename Func>
1453         bool erase( Q const& key, Func f )
1454         {
1455             return erase_( key, key_comparator(), f );
1456         }
1457
1458         /// Deletes the item from the set with comparing functor \p pred
1459         /**
1460             The function is an analog of \ref cds_intrusive_SkipListSet_hp_erase_func "erase(Q const&, Func)"
1461             but \p pred predicate is used for key comparing.
1462
1463             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1464             in any order.
1465             \p pred must imply the same element order as the comparator used for building the set.
1466         */
1467         template <typename Q, typename Less, typename Func>
1468         bool erase_with( Q const& key, Less pred, Func f )
1469         {
1470             CDS_UNUSED( pred );
1471             return erase_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1472         }
1473
1474         /// Finds \p key
1475         /** \anchor cds_intrusive_SkipListSet_hp_find_func
1476             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1477             The interface of \p Func functor is:
1478             \code
1479             struct functor {
1480                 void operator()( value_type& item, Q& key );
1481             };
1482             \endcode
1483             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1484
1485             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1486             that \p item cannot be disposed during functor is executing.
1487             The functor does not serialize simultaneous access to the set \p item. If such access is
1488             possible you must provide your own synchronization on item level to exclude unsafe item modifications.
1489
1490             Note the compare functor specified for class \p Traits template parameter
1491             should accept a parameter of type \p Q that can be not the same as \p value_type.
1492
1493             The function returns \p true if \p key is found, \p false otherwise.
1494         */
1495         template <typename Q, typename Func>
1496         bool find( Q& key, Func f )
1497         {
1498             return find_with_( key, key_comparator(), f );
1499         }
1500         //@cond
1501         template <typename Q, typename Func>
1502         bool find( Q const& key, Func f )
1503         {
1504             return find_with_( key, key_comparator(), f );
1505         }
1506         //@endcond
1507
1508         /// Finds the key \p key with \p pred predicate for comparing
1509         /**
1510             The function is an analog of \ref cds_intrusive_SkipListSet_hp_find_func "find(Q&, Func)"
1511             but \p pred is used for key compare.
1512
1513             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1514             in any order.
1515             \p pred must imply the same element order as the comparator used for building the set.
1516         */
1517         template <typename Q, typename Less, typename Func>
1518         bool find_with( Q& key, Less pred, Func f )
1519         {
1520             CDS_UNUSED( pred );
1521             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1522         }
1523         //@cond
1524         template <typename Q, typename Less, typename Func>
1525         bool find_with( Q const& key, Less pred, Func f )
1526         {
1527             CDS_UNUSED( pred );
1528             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1529         }
1530         //@endcond
1531
1532         /// Checks whether the set contains \p key
1533         /**
1534             The function searches the item with key equal to \p key
1535             and returns \p true if it is found, and \p false otherwise.
1536         */
1537         template <typename Q>
1538         bool contains( Q const& key )
1539         {
1540             return find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
1541         }
1542         //@cond
1543         template <typename Q>
1544         CDS_DEPRECATED("deprecated, use contains()")
1545         bool find( Q const& key )
1546         {
1547             return contains( key );
1548         }
1549         //@endcond
1550
1551         /// Checks whether the set contains \p key using \p pred predicate for searching
1552         /**
1553             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1554             \p Less functor has the interface like \p std::less.
1555             \p Less must imply the same element order as the comparator used for building the set.
1556         */
1557         template <typename Q, typename Less>
1558         bool contains( Q const& key, Less pred )
1559         {
1560             CDS_UNUSED( pred );
1561             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1562         }
1563         //@cond
1564         template <typename Q, typename Less>
1565         CDS_DEPRECATED("deprecated, use contains()")
1566         bool find_with( Q const& key, Less pred )
1567         {
1568             return contains( key, pred );
1569         }
1570         //@endcond
1571
1572         /// Finds \p key and return the item found
1573         /** \anchor cds_intrusive_SkipListSet_hp_get
1574             The function searches the item with key equal to \p key
1575             and returns the pointer to the item found as \p guarded_ptr.
1576             If \p key is not found the function returns an empt guarded pointer.
1577
1578             The \p disposer specified in \p Traits class template parameter is called
1579             by garbage collector \p GC asynchronously when returned \ref guarded_ptr object
1580             will be destroyed or released.
1581             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
1582
1583             Usage:
1584             \code
1585             typedef cds::intrusive::SkipListSet< cds::gc::HP, foo, my_traits >  skip_list;
1586             skip_list theList;
1587             // ...
1588             {
1589                 skip_list::guarded_ptr gp(theList.get( 5 ));
1590                 if ( gp ) {
1591                     // Deal with gp
1592                     //...
1593                 }
1594                 // Destructor of guarded_ptr releases internal HP guard
1595             }
1596             \endcode
1597
1598             Note the compare functor specified for class \p Traits template parameter
1599             should accept a parameter of type \p Q that can be not the same as \p value_type.
1600         */
1601         template <typename Q>
1602         guarded_ptr get( Q const& key )
1603         {
1604             return get_with_( key, key_comparator());
1605         }
1606
1607         /// Finds \p key and return the item found
1608         /**
1609             The function is an analog of \ref cds_intrusive_SkipListSet_hp_get "get( Q const&)"
1610             but \p pred is used for comparing the keys.
1611
1612             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1613             in any order.
1614             \p pred must imply the same element order as the comparator used for building the set.
1615         */
1616         template <typename Q, typename Less>
1617         guarded_ptr get_with( Q const& key, Less pred )
1618         {
1619             CDS_UNUSED( pred );
1620             return get_with_( key, cds::opt::details::make_comparator_from_less<Less>());
1621         }
1622
1623         /// Returns item count in the set
1624         /**
1625             The value returned depends on item counter type provided by \p Traits template parameter.
1626             If it is \p atomicity::empty_item_counter this function always returns 0.
1627             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1628             for this purpose.
1629         */
1630         size_t size() const
1631         {
1632             return m_ItemCounter;
1633         }
1634
1635         /// Checks if the set is empty
1636         bool empty() const
1637         {
1638             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1639         }
1640
1641         /// Clears the set (not atomic)
1642         /**
1643             The function unlink all items from the set.
1644             The function is not atomic, i.e., in multi-threaded environment with parallel insertions
1645             this sequence
1646             \code
1647             set.clear();
1648             assert( set.empty());
1649             \endcode
1650             the assertion could be raised.
1651
1652             For each item the \ref disposer will be called after unlinking.
1653         */
1654         void clear()
1655         {
1656             while ( extract_min_());
1657         }
1658
1659         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1660         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1661         {
1662             return c_nMaxHeight;
1663         }
1664
1665         /// Returns const reference to internal statistics
1666         stat const& statistics() const
1667         {
1668             return m_Stat;
1669         }
1670     };
1671
1672 }} // namespace cds::intrusive
1673
1674
1675 #endif // #ifndef CDSLIB_INTRUSIVE_IMPL_SKIP_LIST_H