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