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