cds/intrusive/impl/skip_list.h

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