cds/intrusive/skip_list_rcu.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_SKIP_LIST_RCU_H
  32 #define CDSLIB_INTRUSIVE_SKIP_LIST_RCU_H
  33
  34 #include <type_traits>
  35 #include <memory>
  36 #include <cds/intrusive/details/skip_list_base.h>
  37 #include <cds/opt/compare.h>
  38 #include <cds/urcu/details/check_deadlock.h>
  39 #include <cds/details/binary_functor_wrapper.h>
  40 #include <cds/urcu/exempt_ptr.h>
  41 #include <cds/urcu/raw_ptr.h>
  42 #include <cds/intrusive/details/raw_ptr_disposer.h>
  43
  44 namespace cds { namespace intrusive {
  45
  46     //@cond
  47     namespace skip_list {
  48
  49         template <class RCU, typename Tag>
  50         class node< cds::urcu::gc< RCU >, Tag >
  51         {
  52         public:
  53             typedef cds::urcu::gc< RCU >    gc; ///< Garbage collector
  54             typedef Tag     tag               ; ///< tag
  55
  56             // Mark bits:
  57             //  bit 0 - the item is logically deleted
  58             //  bit 1 - the item is extracted (only for level 0)
  59             typedef cds::details::marked_ptr<node, 3> marked_ptr;        ///< marked pointer
  60             typedef atomics::atomic< marked_ptr >     atomic_marked_ptr; ///< atomic marked pointer
  61             typedef atomic_marked_ptr                 tower_item_type;
  62
  63         protected:
  64             atomic_marked_ptr       m_pNext;     ///< Next item in bottom-list (list at level 0)
  65         public:
  66             node *                  m_pDelChain; ///< Deleted node chain (local for a thread)
  67 #       ifdef _DEBUG
  68             bool volatile           m_bLinked;
  69             bool volatile           m_bUnlinked;
  70 #       endif
  71         protected:
  72             unsigned int            m_nHeight;   ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
  73             atomic_marked_ptr *     m_arrNext;   ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
  74
  75         public:
  76             /// Constructs a node of height 1 (a bottom-list node)
  77             CDS_CONSTEXPR node()
  78                 : m_pNext( nullptr )
  79                 , m_pDelChain( nullptr )
  80 #       ifdef _DEBUG
  81                 , m_bLinked( false )
  82                 , m_bUnlinked( false )
  83 #       endif
  84                 , m_nHeight(1)
  85                 , m_arrNext( nullptr )
  86             {}
  87
  88 #       ifdef _DEBUG
  89             ~node()
  90             {
  91                 assert( !m_bLinked || m_bUnlinked );
  92             }
  93 #       endif
  94
  95             /// Constructs a node of height \p nHeight
  96             void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
  97             {
  98                 assert( nHeight > 0 );
  99                 assert( (nHeight == 1 && nextTower == nullptr)  // bottom-list node
 100                         || (nHeight > 1 && nextTower != nullptr)   // node at level of more than 0
 101                     );
 102
 103                 m_arrNext = nextTower;
 104                 m_nHeight = nHeight;
 105             }
 106
 107             atomic_marked_ptr * release_tower()
 108             {
 109                 atomic_marked_ptr * pTower = m_arrNext;
 110                 m_arrNext = nullptr;
 111                 m_nHeight = 1;
 112                 return pTower;
 113             }
 114
 115             atomic_marked_ptr * get_tower() const
 116             {
 117                 return m_arrNext;
 118             }
 119
 120             void clear_tower()
 121             {
 122                 for ( unsigned int nLevel = 1; nLevel < m_nHeight; ++nLevel )
 123                     next(nLevel).store( marked_ptr(), atomics::memory_order_relaxed );
 124             }
 125
 126             /// Access to element of next pointer array
 127             atomic_marked_ptr& next( unsigned int nLevel )
 128             {
 129                 assert( nLevel < height() );
 130                 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
 131
 132 #           ifdef CDS_THREAD_SANITIZER_ENABLED
 133                 // TSan false positive: m_arrNext is read-only array
 134                 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
 135                 atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 136                 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
 137                 return r;
 138 #           else
 139                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 140 #           endif
 141             }
 142
 143             /// Access to element of next pointer array (const version)
 144             atomic_marked_ptr const& next( unsigned int nLevel ) const
 145             {
 146                 assert( nLevel < height() );
 147                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
 148
 149 #           ifdef CDS_THREAD_SANITIZER_ENABLED
 150                 // TSan false positive: m_arrNext is read-only array
 151                 CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN;
 152                 atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 153                 CDS_TSAN_ANNOTATE_IGNORE_READS_END;
 154                 return r;
 155 #           else
 156                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 157 #           endif
 158             }
 159
 160             /// Access to element of next pointer array (same as \ref next function)
 161             atomic_marked_ptr& operator[]( unsigned int nLevel )
 162             {
 163                 return next( nLevel );
 164             }
 165
 166             /// Access to element of next pointer array (same as \ref next function)
 167             atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
 168             {
 169                 return next( nLevel );
 170             }
 171
 172             /// Height of the node
 173             unsigned int height() const
 174             {
 175                 return m_nHeight;
 176             }
 177
 178             /// Clears internal links
 179             void clear()
 180             {
 181                 assert( m_arrNext == nullptr );
 182                 m_pNext.store( marked_ptr(), atomics::memory_order_release );
 183                 m_pDelChain = nullptr;
 184             }
 185
 186             bool is_cleared() const
 187             {
 188                 return m_pNext == atomic_marked_ptr()
 189                     && m_arrNext == nullptr
 190                     && m_nHeight <= 1;
 191             }
 192         };
 193     } // namespace skip_list
 194     //@endcond
 195
 196     //@cond
 197     namespace skip_list { namespace details {
 198
 199         template <class RCU, typename NodeTraits, typename BackOff, bool IsConst>
 200         class iterator< cds::urcu::gc< RCU >, NodeTraits, BackOff, IsConst >
 201         {
 202         public:
 203             typedef cds::urcu::gc< RCU >                gc;
 204             typedef NodeTraits                          node_traits;
 205             typedef BackOff                             back_off;
 206             typedef typename node_traits::node_type     node_type;
 207             typedef typename node_traits::value_type    value_type;
 208             static bool const c_isConst = IsConst;
 209
 210             typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type   value_ref;
 211
 212         protected:
 213             typedef typename node_type::marked_ptr          marked_ptr;
 214             typedef typename node_type::atomic_marked_ptr   atomic_marked_ptr;
 215
 216             node_type *             m_pNode;
 217
 218         protected:
 219             void next()
 220             {
 221                 back_off bkoff;
 222
 223                 for (;;) {
 224                     if ( m_pNode->next( m_pNode->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
 225                         // Current node is marked as deleted. So, its next pointer can point to anything
 226                         // In this case we interrupt our iteration and returns end() iterator.
 227                         *this = iterator();
 228                         return;
 229                     }
 230
 231                     marked_ptr p = m_pNode->next(0).load( atomics::memory_order_relaxed );
 232                     node_type * pp = p.ptr();
 233                     if ( p.bits() ) {
 234                         // p is marked as deleted. Spin waiting for physical removal
 235                         bkoff();
 236                         continue;
 237                     }
 238                     else if ( pp && pp->next( pp->height() - 1 ).load( atomics::memory_order_relaxed ).bits() ) {
 239                         // p is marked as deleted. Spin waiting for physical removal
 240                         bkoff();
 241                         continue;
 242                     }
 243
 244                     m_pNode = pp;
 245                     break;
 246                 }
 247             }
 248
 249         public: // for internal use only!!!
 250             iterator( node_type& refHead )
 251                 : m_pNode( nullptr )
 252             {
 253                 back_off bkoff;
 254
 255                 for (;;) {
 256                     marked_ptr p = refHead.next(0).load( atomics::memory_order_relaxed );
 257                     if ( !p.ptr() ) {
 258                         // empty skip-list
 259                         break;
 260                     }
 261
 262                     node_type * pp = p.ptr();
 263                     // Logically deleted node is marked from highest level
 264                     if ( !pp->next( pp->height() - 1 ).load( atomics::memory_order_acquire ).bits() ) {
 265                         m_pNode = pp;
 266                         break;
 267                     }
 268
 269                     bkoff();
 270                 }
 271             }
 272
 273         public:
 274             iterator()
 275                 : m_pNode( nullptr )
 276             {}
 277
 278             iterator( iterator const& s)
 279                 : m_pNode( s.m_pNode )
 280             {}
 281
 282             value_type * operator ->() const
 283             {
 284                 assert( m_pNode != nullptr );
 285                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 286
 287                 return node_traits::to_value_ptr( m_pNode );
 288             }
 289
 290             value_ref operator *() const
 291             {
 292                 assert( m_pNode != nullptr );
 293                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 294
 295                 return *node_traits::to_value_ptr( m_pNode );
 296             }
 297
 298             /// Pre-increment
 299             iterator& operator ++()
 300             {
 301                 next();
 302                 return *this;
 303             }
 304
 305             iterator& operator = (const iterator& src)
 306             {
 307                 m_pNode = src.m_pNode;
 308                 return *this;
 309             }
 310
 311             template <typename Bkoff, bool C>
 312             bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
 313             {
 314                 return m_pNode == i.m_pNode;
 315             }
 316             template <typename Bkoff, bool C>
 317             bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
 318             {
 319                 return !( *this == i );
 320             }
 321         };
 322     }}  // namespace skip_list::details
 323     //@endcond
 324
 325     /// Lock-free skip-list set (template specialization for \ref cds_urcu_desc "RCU")
 326     /** @ingroup cds_intrusive_map
 327         @anchor cds_intrusive_SkipListSet_rcu
 328
 329         The implementation of well-known probabilistic data structure called skip-list
 330         invented by W.Pugh in his papers:
 331             - [1989] W.Pugh Skip Lists: A Probabilistic Alternative to Balanced Trees
 332             - [1990] W.Pugh A Skip List Cookbook
 333
 334         A skip-list is a probabilistic data structure that provides expected logarithmic
 335         time search without the need of rebalance. The skip-list is a collection of sorted
 336         linked list. Nodes are ordered by key. Each node is linked into a subset of the lists.
 337         Each list has a level, ranging from 0 to 32. The bottom-level list contains
 338         all the nodes, and each higher-level list is a sublist of the lower-level lists.
 339         Each node is created with a random top level (with a random height), and belongs
 340         to all lists up to that level. The probability that a node has the height 1 is 1/2.
 341         The probability that a node has the height N is 1/2 ** N (more precisely,
 342         the distribution depends on an random generator provided, but our generators
 343         have this property).
 344
 345         The lock-free variant of skip-list is implemented according to book
 346             - [2008] M.Herlihy, N.Shavit "The Art of Multiprocessor Programming",
 347                 chapter 14.4 "A Lock-Free Concurrent Skiplist".
 348
 349         <b>Template arguments</b>:
 350             - \p RCU - one of \ref cds_urcu_gc "RCU type"
 351             - \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)
 352                 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
 353             - \p Traits - set traits, default is \p skip_list::traits
 354                 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
 355                 instead of \p Traits template argument.
 356
 357         @note Before including <tt><cds/intrusive/skip_list_rcu.h></tt> you should include appropriate RCU header file,
 358         see \ref cds_urcu_gc "RCU type" for list of existing RCU class and corresponding header files.
 359
 360         <b>Iterators</b>
 361
 362         The class supports a forward iterator (\ref iterator and \ref const_iterator).
 363         The iteration is ordered.
 364
 365         You may iterate over skip-list set items only under RCU lock.
 366         Only in this case the iterator is thread-safe since
 367         while RCU is locked any set's item cannot be reclaimed.
 368
 369         @note The requirement of RCU lock during iterating means that any type of modification of the skip list
 370         (i.e. inserting, erasing and so on) is not possible.
 371
 372         @warning The iterator object cannot be passed between threads.
 373
 374         Example how to use skip-list set iterators:
 375         \code
 376         // First, you should include the header for RCU type you have chosen
 377         #include <cds/urcu/general_buffered.h>
 378         #include <cds/intrusive/skip_list_rcu.h>
 379
 380         typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_type;
 381
 382         struct Foo {
 383             // ...
 384         };
 385
 386         // Traits for your skip-list.
 387         // At least, you should define cds::opt::less or cds::opt::compare for Foo struct
 388         struct my_traits: public cds::intrusive::skip_list::traits
 389         {
 390             // ...
 391         };
 392         typedef cds::intrusive::SkipListSet< rcu_type, Foo, my_traits > my_skiplist_set;
 393
 394         my_skiplist_set theSet;
 395
 396         // ...
 397
 398         // Begin iteration
 399         {
 400             // Apply RCU locking manually
 401             typename rcu_type::scoped_lock sl;
 402
 403             for ( auto it = theList.begin(); it != theList.end(); ++it ) {
 404                 // ...
 405             }
 406
 407             // rcu_type::scoped_lock destructor releases RCU lock implicitly
 408         }
 409         \endcode
 410
 411         The iterator class supports the following minimalistic interface:
 412         \code
 413         struct iterator {
 414             // Default ctor
 415             iterator();
 416
 417             // Copy ctor
 418             iterator( iterator const& s);
 419
 420             value_type * operator ->() const;
 421             value_type& operator *() const;
 422
 423             // Pre-increment
 424             iterator& operator ++();
 425
 426             // Copy assignment
 427             iterator& operator = (const iterator& src);
 428
 429             bool operator ==(iterator const& i ) const;
 430             bool operator !=(iterator const& i ) const;
 431         };
 432         \endcode
 433         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
 434
 435         <b>How to use</b>
 436
 437         You should incorporate skip_list::node into your struct \p T and provide
 438         appropriate skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
 439         define a struct based on \p skip_list::traits.
 440
 441         Example for <tt>cds::urcu::general_buffered<></tt> RCU and base hook:
 442         \code
 443         // First, you should include the header for RCU type you have chosen
 444         #include <cds/urcu/general_buffered.h>
 445
 446         // Include RCU skip-list specialization
 447         #include <cds/intrusive/skip_list_rcu.h>
 448
 449         // RCU type typedef
 450         typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_type;
 451
 452         // Data stored in skip list
 453         struct my_data: public cds::intrusive::skip_list::node< rcu_type >
 454         {
 455             // key field
 456             std::string     strKey;
 457
 458             // other data
 459             // ...
 460         };
 461
 462         // my_data compare functor
 463         struct my_data_cmp {
 464             int operator()( const my_data& d1, const my_data& d2 )
 465             {
 466                 return d1.strKey.compare( d2.strKey );
 467             }
 468
 469             int operator()( const my_data& d, const std::string& s )
 470             {
 471                 return d.strKey.compare(s);
 472             }
 473
 474             int operator()( const std::string& s, const my_data& d )
 475             {
 476                 return s.compare( d.strKey );
 477             }
 478         };
 479
 480         // Declare traits
 481         struct my_traits: public cds::intrusive::skip_list::traits
 482         {
 483             typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< rcu_type > >   hook;
 484             typedef my_data_cmp compare;
 485         };
 486
 487         // Declare skip-list set type
 488         typedef cds::intrusive::SkipListSet< rcu_type, my_data, my_traits >     traits_based_set;
 489         \endcode
 490
 491         Equivalent option-based code:
 492         \code
 493         #include <cds/urcu/general_buffered.h>
 494         #include <cds/intrusive/skip_list_rcu.h>
 495
 496         typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_type;
 497
 498         struct my_data {
 499             // see above
 500         };
 501         struct compare {
 502             // see above
 503         };
 504
 505         // Declare option-based skip-list set
 506         typedef cds::intrusive::SkipListSet< rcu_type
 507             ,my_data
 508             , typename cds::intrusive::skip_list::make_traits<
 509                 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< rcu_type > > >
 510                 ,cds::intrusive::opt::compare< my_data_cmp >
 511             >::type
 512         > option_based_set;
 513
 514         \endcode
 515     */
 516     template <
 517         class RCU
 518        ,typename T
 519 #ifdef CDS_DOXYGEN_INVOKED
 520        ,typename Traits = skip_list::traits
 521 #else
 522        ,typename Traits
 523 #endif
 524     >
 525     class SkipListSet< cds::urcu::gc< RCU >, T, Traits >
 526     {
 527     public:
 528         typedef cds::urcu::gc< RCU > gc; ///< Garbage collector
 529         typedef T       value_type;      ///< type of value stored in the skip-list
 530         typedef Traits  traits;          ///< Traits template parameter
 531
 532         typedef typename traits::hook    hook;      ///< hook type
 533         typedef typename hook::node_type node_type; ///< node type
 534
 535 #   ifdef CDS_DOXYGEN_INVOKED
 536         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on \p Traits::compare and \p Traits::less
 537 #   else
 538         typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
 539 #   endif
 540
 541         typedef typename traits::disposer  disposer;   ///< disposer
 542         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits;    ///< node traits
 543
 544         typedef typename traits::item_counter  item_counter;   ///< Item counting policy used
 545         typedef typename traits::memory_model  memory_model;   ///< Memory ordering, see \p cds::opt::memory_model option
 546         typedef typename traits::random_level_generator    random_level_generator;   ///< random level generator
 547         typedef typename traits::allocator     allocator_type; ///< allocator for maintaining array of next pointers of the node
 548         typedef typename traits::back_off      back_off;       ///< Back-off strategy
 549         typedef typename traits::stat          stat;           ///< internal statistics type
 550         typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
 551         typedef typename gc::scoped_lock       rcu_lock;      ///< RCU scoped lock
 552         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions does not require external locking
 553
 554
 555         /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
 556         /**
 557             The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
 558             but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
 559         */
 560         static unsigned int const c_nMaxHeight = std::conditional<
 561             (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
 562             std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
 563             std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
 564         >::type::value;
 565
 566         //@cond
 567         static unsigned int const c_nMinHeight = 5;
 568         //@endcond
 569
 570     protected:
 571         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr ;   ///< Atomic marked node pointer
 572         typedef typename node_type::marked_ptr          marked_node_ptr ;   ///< Node marked pointer
 573
 574     protected:
 575         //@cond
 576         typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
 577
 578         typedef typename std::conditional<
 579             std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
 580             ,intrusive_node_builder
 581             ,typename traits::internal_node_builder
 582         >::type node_builder;
 583
 584         typedef std::unique_ptr< node_type, typename node_builder::node_disposer >    scoped_node_ptr;
 585
 586         static void dispose_node( value_type * pVal )
 587         {
 588             assert( pVal );
 589
 590             typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
 591             disposer()( pVal );
 592         }
 593
 594         struct node_disposer
 595         {
 596             void operator()( value_type * pVal )
 597             {
 598                 dispose_node( pVal );
 599             }
 600         };
 601
 602         static void dispose_chain( node_type * pChain )
 603         {
 604             if ( pChain ) {
 605                 assert( !gc::is_locked() );
 606
 607                 auto f = [&pChain]() -> cds::urcu::retired_ptr {
 608                     node_type * p = pChain;
 609                     if ( p ) {
 610                         pChain = p->m_pDelChain;
 611                         return cds::urcu::make_retired_ptr<node_disposer>( node_traits::to_value_ptr( p ));
 612                     }
 613                     return cds::urcu::make_retired_ptr<node_disposer>( static_cast<value_type *>(nullptr));
 614                 };
 615                 gc::batch_retire(std::ref(f));
 616             }
 617         }
 618
 619         struct position {
 620             node_type *   pPrev[ c_nMaxHeight ];
 621             node_type *   pSucc[ c_nMaxHeight ];
 622             node_type *   pNext[ c_nMaxHeight ];
 623
 624             node_type *   pCur;
 625             node_type *   pDelChain;
 626
 627             position()
 628                 : pDelChain( nullptr )
 629             {}
 630
 631             ~position()
 632             {
 633                 dispose_chain( pDelChain );
 634             }
 635
 636             void dispose( node_type * p )
 637             {
 638                 assert( p != nullptr );
 639                 assert( p->m_pDelChain == nullptr );
 640
 641                 p->m_pDelChain = pDelChain;
 642                 pDelChain = p;
 643             }
 644         };
 645
 646         typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock>   check_deadlock_policy;
 647         //@endcond
 648
 649     protected:
 650         skip_list::details::head_node< node_type > m_Head;   ///< head tower (max height)
 651
 652         item_counter                m_ItemCounter;      ///< item counter
 653         random_level_generator      m_RandomLevelGen;   ///< random level generator instance
 654         atomics::atomic<unsigned int>    m_nHeight;     ///< estimated high level
 655         atomics::atomic<node_type *>     m_pDeferredDelChain ;   ///< Deferred deleted node chain
 656         mutable stat                m_Stat;             ///< internal statistics
 657
 658     protected:
 659         //@cond
 660         unsigned int random_level()
 661         {
 662             // Random generator produces a number from range [0..31]
 663             // We need a number from range [1..32]
 664             return m_RandomLevelGen() + 1;
 665         }
 666
 667         template <typename Q>
 668         node_type * build_node( Q v )
 669         {
 670             return node_builder::make_tower( v, m_RandomLevelGen );
 671         }
 672         //@endcond
 673
 674     public:
 675         using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void >; ///< pointer to extracted node
 676
 677     private:
 678         //@cond
 679         struct chain_disposer {
 680             void operator()( node_type * pChain ) const
 681             {
 682                 dispose_chain( pChain );
 683             }
 684         };
 685         typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer;
 686         //@endcond
 687
 688     public:
 689         /// Result of \p get(), \p get_with() functions - pointer to the node found
 690         typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr;
 691
 692     protected:
 693         //@cond
 694
 695         bool is_extracted( marked_node_ptr const p ) const
 696         {
 697             return (p.bits() & 2) != 0;
 698         }
 699
 700         template <typename Q, typename Compare >
 701         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
 702         {
 703             assert( gc::is_locked() );
 704
 705             node_type * pPred;
 706             marked_node_ptr pSucc;
 707             marked_node_ptr pCur;
 708             int nCmp = 1;
 709
 710         retry:
 711             pPred = m_Head.head();
 712
 713             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 714
 715                 while ( true ) {
 716                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_acquire );
 717                     if ( pCur.bits() ) {
 718                         // pCur.bits() means that pPred is logically deleted
 719                         goto retry;
 720                     }
 721
 722                     if ( pCur.ptr() == nullptr ) {
 723                         // end of the list at level nLevel - goto next level
 724                         break;
 725                     }
 726
 727                     // pSucc contains deletion mark for pCur
 728                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
 729
 730                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
 731                         goto retry;
 732
 733                     if ( pSucc.bits() ) {
 734                         // pCur is marked, i.e. logically deleted.
 735                         marked_node_ptr p( pCur.ptr() );
 736 #                   ifdef _DEBUG
 737                         if ( nLevel == 0 )
 738                             pCur->m_bUnlinked = true;
 739 #                   endif
 740                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 741                              memory_model::memory_order_release, atomics::memory_order_relaxed ))
 742                         {
 743                             if ( nLevel == 0 ) {
 744                                 if ( !is_extracted( pSucc )) {
 745                                     // We cannot free the node at this moment since RCU is locked
 746                                     // Link deleted nodes to a chain to free later
 747                                     pos.dispose( pCur.ptr() );
 748                                     m_Stat.onEraseWhileFind();
 749                                 }
 750                                 else {
 751                                     m_Stat.onExtractWhileFind();
 752                                 }
 753                             }
 754                         }
 755                         goto retry;
 756                     }
 757                     else {
 758                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
 759                         if ( nCmp < 0 )
 760                             pPred = pCur.ptr();
 761                         else if ( nCmp == 0 && bStopIfFound )
 762                             goto found;
 763                         else
 764                             break;
 765                     }
 766                 }
 767
 768                 // Next level
 769                 pos.pPrev[ nLevel ] = pPred;
 770                 pos.pSucc[ nLevel ] = pCur.ptr();
 771             }
 772
 773             if ( nCmp != 0 )
 774                 return false;
 775
 776         found:
 777             pos.pCur = pCur.ptr();
 778             return pCur.ptr() && nCmp == 0;
 779         }
 780
 781         bool find_min_position( position& pos )
 782         {
 783             assert( gc::is_locked() );
 784
 785             node_type * pPred;
 786             marked_node_ptr pSucc;
 787             marked_node_ptr pCur;
 788
 789         retry:
 790             pPred = m_Head.head();
 791
 792             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 793
 794                 pCur = pPred->next( nLevel ).load( memory_model::memory_order_acquire );
 795                 // pCur.bits() means that pPred is logically deleted
 796                 // head cannot be deleted
 797                 assert( pCur.bits() == 0 );
 798
 799                 if ( pCur.ptr() ) {
 800
 801                     // pSucc contains deletion mark for pCur
 802                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
 803
 804                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
 805                         goto retry;
 806
 807                     if ( pSucc.bits() ) {
 808                         // pCur is marked, i.e. logically deleted.
 809 #                   ifdef _DEBUG
 810                         if ( nLevel == 0 )
 811                             pCur->m_bUnlinked = true;
 812 #                   endif
 813                         marked_node_ptr p( pCur.ptr() );
 814                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 815                             memory_model::memory_order_release, atomics::memory_order_relaxed ))
 816                         {
 817                             if ( nLevel == 0 ) {
 818                                 if ( !is_extracted( pSucc )) {
 819                                     // We cannot free the node at this moment since RCU is locked
 820                                     // Link deleted nodes to a chain to free later
 821                                     pos.dispose( pCur.ptr() );
 822                                     m_Stat.onEraseWhileFind();
 823                                 }
 824                                 else {
 825                                     m_Stat.onExtractWhileFind();
 826                                 }
 827                             }
 828                         }
 829                         goto retry;
 830                     }
 831                 }
 832
 833                 // Next level
 834                 pos.pPrev[ nLevel ] = pPred;
 835                 pos.pSucc[ nLevel ] = pCur.ptr();
 836             }
 837             return (pos.pCur = pCur.ptr()) != nullptr;
 838         }
 839
 840         bool find_max_position( position& pos )
 841         {
 842             assert( gc::is_locked() );
 843
 844             node_type * pPred;
 845             marked_node_ptr pSucc;
 846             marked_node_ptr pCur;
 847
 848         retry:
 849             pPred = m_Head.head();
 850
 851             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 852
 853                 while ( true ) {
 854                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_acquire );
 855                     if ( pCur.bits() ) {
 856                         // pCur.bits() means that pPred is logically deleted
 857                         goto retry;
 858                     }
 859
 860                     if ( pCur.ptr() == nullptr ) {
 861                         // end of the list at level nLevel - goto next level
 862                         break;
 863                     }
 864
 865                     // pSucc contains deletion mark for pCur
 866                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire );
 867
 868                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() )
 869                         goto retry;
 870
 871                     if ( pSucc.bits() ) {
 872                         // pCur is marked, i.e. logically deleted.
 873 #                   ifdef _DEBUG
 874                         if ( nLevel == 0 )
 875                             pCur->m_bUnlinked = true;
 876 #                   endif
 877                         marked_node_ptr p( pCur.ptr() );
 878                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 879                             memory_model::memory_order_release, atomics::memory_order_relaxed ))
 880                         {
 881                             if ( nLevel == 0 ) {
 882                                 if ( !is_extracted( pSucc )) {
 883                                     // We cannot free the node at this moment since RCU is locked
 884                                     // Link deleted nodes to a chain to free later
 885                                     pos.dispose( pCur.ptr() );
 886                                     m_Stat.onEraseWhileFind();
 887                                 }
 888                                 else {
 889                                     m_Stat.onExtractWhileFind();
 890                                 }
 891                             }
 892                         }
 893                         goto retry;
 894                     }
 895                     else {
 896                         if ( !pSucc.ptr() )
 897                             break;
 898
 899                         pPred = pCur.ptr();
 900                     }
 901                 }
 902
 903                 // Next level
 904                 pos.pPrev[ nLevel ] = pPred;
 905                 pos.pSucc[ nLevel ] = pCur.ptr();
 906             }
 907
 908             return (pos.pCur = pCur.ptr()) != nullptr;
 909         }
 910
 911         template <typename Func>
 912         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 913         {
 914             assert( gc::is_locked() );
 915
 916             unsigned int nHeight = pNode->height();
 917             pNode->clear_tower();
 918
 919             {
 920                 marked_node_ptr p( pos.pSucc[0] );
 921                 pNode->next( 0 ).store( p, memory_model::memory_order_release );
 922                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 923                     return false;
 924                 }
 925 #       ifdef _DEBUG
 926                 pNode->m_bLinked = true;
 927 #       endif
 928                 f( val );
 929             }
 930
 931             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 932                 marked_node_ptr p;
 933                 while ( true ) {
 934                     marked_node_ptr q( pos.pSucc[ nLevel ]);
 935                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
 936                         // pNode has been marked as removed while we are inserting it
 937                         // Stop inserting
 938                         assert( p.bits() );
 939                         m_Stat.onLogicDeleteWhileInsert();
 940                         return true;
 941                     }
 942                     p = q;
 943                     if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
 944                         break;
 945
 946                     // Renew insert position
 947                     m_Stat.onRenewInsertPosition();
 948                     if ( !find_position( val, pos, key_comparator(), false )) {
 949                         // The node has been deleted while we are inserting it
 950                         m_Stat.onNotFoundWhileInsert();
 951                         return true;
 952                     }
 953                 }
 954             }
 955             return true;
 956         }
 957
 958         template <typename Func>
 959         bool try_remove_at( node_type * pDel, position& pos, Func f, bool bExtract )
 960         {
 961             assert( pDel != nullptr );
 962             assert( gc::is_locked() );
 963
 964             marked_node_ptr pSucc;
 965
 966             // logical deletion (marking)
 967             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
 968                 pSucc = pDel->next(nLevel).load( memory_model::memory_order_relaxed );
 969                 while ( true ) {
 970                     if ( pSucc.bits()
 971                       || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
 972                     {
 973                         break;
 974                     }
 975                 }
 976             }
 977
 978             pSucc = pDel->next(0).load( memory_model::memory_order_relaxed );
 979             while ( true ) {
 980                 if ( pSucc.bits() )
 981                     return false;
 982
 983                 int const nMask = bExtract ? 3 : 1;
 984                 if ( pDel->next(0).compare_exchange_strong( pSucc, pSucc | nMask, memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
 985                 {
 986                     f( *node_traits::to_value_ptr( pDel ));
 987
 988                     // physical deletion
 989                     // try fast erase
 990                     pSucc = pDel;
 991                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
 992                         if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( pSucc,
 993                             marked_node_ptr( pDel->next(nLevel).load(memory_model::memory_order_relaxed).ptr() ),
 994                             memory_model::memory_order_release, atomics::memory_order_relaxed) )
 995                         {
 996                             // Do slow erase
 997                             find_position( *node_traits::to_value_ptr(pDel), pos, key_comparator(), false );
 998                             if ( bExtract )
 999                                 m_Stat.onSlowExtract();
1000                             else
1001                                 m_Stat.onSlowErase();
1002 #                        ifdef _DEBUG
1003                             assert( pDel->m_bUnlinked );
1004 #                        endif
1005                             return true;
1006                         }
1007                     }
1008
1009 #               ifdef _DEBUG
1010                     pDel->m_bUnlinked = true;
1011 #               endif
1012                     if ( !bExtract ) {
1013                         // We cannot free the node at this moment since RCU is locked
1014                         // Link deleted nodes to a chain to free later
1015                         pos.dispose( pDel );
1016                         m_Stat.onFastErase();
1017                     }
1018                     else
1019                         m_Stat.onFastExtract();
1020                     return true;
1021                 }
1022                 m_Stat.onEraseRetry();
1023             }
1024         }
1025
1026         enum finsd_fastpath_result {
1027             find_fastpath_found,
1028             find_fastpath_not_found,
1029             find_fastpath_abort
1030         };
1031         template <typename Q, typename Compare, typename Func>
1032         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f ) const
1033         {
1034             node_type * pPred;
1035             marked_node_ptr pCur;
1036             marked_node_ptr pSucc;
1037             marked_node_ptr pNull;
1038
1039             back_off bkoff;
1040
1041             pPred = m_Head.head();
1042             for ( int nLevel = static_cast<int>(m_nHeight.load(memory_model::memory_order_relaxed) - 1); nLevel >= 0; --nLevel ) {
1043                 pCur = pPred->next(nLevel).load( memory_model::memory_order_acquire );
1044                 if ( pCur == pNull )
1045                     continue;
1046
1047                 while ( pCur != pNull ) {
1048                     if ( pCur.bits() ) {
1049                         // Wait until pCur is removed
1050                         unsigned int nAttempt = 0;
1051                         while ( pCur.bits() && nAttempt++ < 16 ) {
1052                             bkoff();
1053                             pCur = pPred->next(nLevel).load( memory_model::memory_order_acquire );
1054                         }
1055                         bkoff.reset();
1056
1057                         if ( pCur.bits() ) {
1058                             // Maybe, we are on deleted node sequence
1059                             // Abort searching, try slow-path
1060                             return find_fastpath_abort;
1061                         }
1062                     }
1063
1064                     if ( pCur.ptr() ) {
1065                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1066                         if ( nCmp < 0 ) {
1067                             pPred = pCur.ptr();
1068                             pCur = pCur->next(nLevel).load( memory_model::memory_order_acquire );
1069                         }
1070                         else if ( nCmp == 0 ) {
1071                             // found
1072                             f( *node_traits::to_value_ptr( pCur.ptr() ), val );
1073                             return find_fastpath_found;
1074                         }
1075                         else // pCur > val - go down
1076                             break;
1077                     }
1078                 }
1079             }
1080
1081             return find_fastpath_not_found;
1082         }
1083
1084         template <typename Q, typename Compare, typename Func>
1085         bool find_slowpath( Q& val, Compare cmp, Func f, position& pos )
1086         {
1087             if ( find_position( val, pos, cmp, true )) {
1088                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1089
1090                 f( *node_traits::to_value_ptr( pos.pCur ), val );
1091                 return true;
1092             }
1093             else
1094                 return false;
1095         }
1096
1097         template <typename Q, typename Compare, typename Func>
1098         bool do_find_with( Q& val, Compare cmp, Func f )
1099         {
1100             position pos;
1101             return do_find_with( val, cmp, f, pos );
1102         }
1103
1104         template <typename Q, typename Compare, typename Func>
1105         bool do_find_with( Q& val, Compare cmp, Func f, position& pos )
1106         {
1107             bool bRet;
1108
1109             {
1110                 rcu_lock l;
1111
1112                 switch ( find_fastpath( val, cmp, f )) {
1113                 case find_fastpath_found:
1114                     m_Stat.onFindFastSuccess();
1115                     return true;
1116                 case find_fastpath_not_found:
1117                     m_Stat.onFindFastFailed();
1118                     return false;
1119                 default:
1120                     break;
1121                 }
1122
1123                 if ( find_slowpath( val, cmp, f, pos )) {
1124                     m_Stat.onFindSlowSuccess();
1125                     bRet = true;
1126                 }
1127                 else {
1128                     m_Stat.onFindSlowFailed();
1129                     bRet = false;
1130                 }
1131             }
1132             return bRet;
1133         }
1134
1135         template <typename Q, typename Compare, typename Func>
1136         bool do_erase( Q const& val, Compare cmp, Func f )
1137         {
1138             check_deadlock_policy::check();
1139
1140             position pos;
1141             bool bRet;
1142
1143             {
1144                 rcu_lock rcuLock;
1145
1146                 if ( !find_position( val, pos, cmp, false ) ) {
1147                     m_Stat.onEraseFailed();
1148                     bRet = false;
1149                 }
1150                 else {
1151                     node_type * pDel = pos.pCur;
1152                     assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1153
1154                     unsigned int nHeight = pDel->height();
1155                     if ( try_remove_at( pDel, pos, f, false )) {
1156                         --m_ItemCounter;
1157                         m_Stat.onRemoveNode( nHeight );
1158                         m_Stat.onEraseSuccess();
1159                         bRet = true;
1160                     }
1161                     else {
1162                         m_Stat.onEraseFailed();
1163                         bRet = false;
1164                     }
1165                 }
1166             }
1167
1168             return bRet;
1169         }
1170
1171         template <typename Q, typename Compare>
1172         value_type * do_extract_key( Q const& key, Compare cmp, position& pos )
1173         {
1174             // RCU should be locked!!!
1175             assert( gc::is_locked() );
1176
1177             node_type * pDel;
1178
1179             if ( !find_position( key, pos, cmp, false ) ) {
1180                 m_Stat.onExtractFailed();
1181                 pDel = nullptr;
1182             }
1183             else {
1184                 pDel = pos.pCur;
1185                 assert( cmp( *node_traits::to_value_ptr( pDel ), key ) == 0 );
1186
1187                 unsigned int const nHeight = pDel->height();
1188
1189                 if ( try_remove_at( pDel, pos, [](value_type const&) {}, true )) {
1190                     --m_ItemCounter;
1191                     m_Stat.onRemoveNode( nHeight );
1192                     m_Stat.onExtractSuccess();
1193                 }
1194                 else {
1195                     m_Stat.onExtractFailed();
1196                     pDel = nullptr;
1197                 }
1198             }
1199
1200             return pDel ? node_traits::to_value_ptr( pDel ) : nullptr;
1201         }
1202
1203         template <typename Q>
1204         value_type * do_extract( Q const& key )
1205         {
1206             check_deadlock_policy::check();
1207             value_type * pDel = nullptr;
1208             position pos;
1209             {
1210                 rcu_lock l;
1211                 pDel = do_extract_key( key, key_comparator(), pos );
1212             }
1213
1214             return pDel;
1215         }
1216
1217         template <typename Q, typename Less>
1218         value_type * do_extract_with( Q const& key, Less pred )
1219         {
1220             CDS_UNUSED(pred);
1221             check_deadlock_policy::check();
1222             value_type * pDel = nullptr;
1223             position pos;
1224             {
1225                 rcu_lock l;
1226                 pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less<Less>(), pos );
1227             }
1228
1229             return pDel;
1230         }
1231
1232         value_type * do_extract_min()
1233         {
1234             assert( !gc::is_locked() );
1235
1236             position pos;
1237             node_type * pDel;
1238
1239             {
1240                 rcu_lock l;
1241
1242                 if ( !find_min_position( pos ) ) {
1243                     m_Stat.onExtractMinFailed();
1244                     pDel = nullptr;
1245                 }
1246                 else {
1247                     pDel = pos.pCur;
1248                     unsigned int const nHeight = pDel->height();
1249
1250                     if ( try_remove_at( pDel, pos, []( value_type const& ) {}, true ) ) {
1251                         --m_ItemCounter;
1252                         m_Stat.onRemoveNode( nHeight );
1253                         m_Stat.onExtractMinSuccess();
1254                     }
1255                     else {
1256                         m_Stat.onExtractMinFailed();
1257                         pDel = nullptr;
1258                     }
1259                 }
1260             }
1261
1262             return pDel ? node_traits::to_value_ptr( pDel ) : nullptr;
1263         }
1264
1265         value_type * do_extract_max()
1266         {
1267             assert( !gc::is_locked() );
1268
1269             position pos;
1270             node_type * pDel;
1271
1272             {
1273                 rcu_lock l;
1274
1275                 if ( !find_max_position( pos ) ) {
1276                     m_Stat.onExtractMaxFailed();
1277                     pDel = nullptr;
1278                 }
1279                 else {
1280                     pDel = pos.pCur;
1281                     unsigned int const nHeight = pDel->height();
1282
1283                     if ( try_remove_at( pDel, pos, []( value_type const& ) {}, true ) ) {
1284                         --m_ItemCounter;
1285                         m_Stat.onRemoveNode( nHeight );
1286                         m_Stat.onExtractMaxSuccess();
1287                     }
1288                     else {
1289                         m_Stat.onExtractMaxFailed();
1290                         pDel = nullptr;
1291                     }
1292                 }
1293             }
1294
1295             return pDel ? node_traits::to_value_ptr( pDel ) : nullptr;
1296         }
1297
1298         void increase_height( unsigned int nHeight )
1299         {
1300             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1301             if ( nCur < nHeight )
1302                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed );
1303         }
1304         //@endcond
1305
1306     public:
1307         /// Default constructor
1308         SkipListSet()
1309             : m_Head( c_nMaxHeight )
1310             , m_nHeight( c_nMinHeight )
1311             , m_pDeferredDelChain( nullptr )
1312         {
1313             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
1314
1315             // Barrier for head node
1316             atomics::atomic_thread_fence( memory_model::memory_order_release );
1317         }
1318
1319         /// Clears and destructs the skip-list
1320         ~SkipListSet()
1321         {
1322             clear();
1323         }
1324
1325     public:
1326     ///@name Forward iterators (thread-safe under RCU lock)
1327     //@{
1328         /// Forward iterator
1329         /**
1330             The forward iterator has some features:
1331             - it has no post-increment operator
1332             - it depends on iterator of underlying \p OrderedList
1333
1334             You may safely use iterators in multi-threaded environment only under RCU lock.
1335             Otherwise, a crash is possible if another thread deletes the element the iterator points to.
1336         */
1337         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
1338
1339         /// Const iterator type
1340         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
1341
1342         /// Returns a forward iterator addressing the first element in a set
1343         iterator begin()
1344         {
1345             return iterator( *m_Head.head() );
1346         }
1347
1348         /// Returns a forward const iterator addressing the first element in a set
1349         const_iterator begin() const
1350         {
1351             return const_iterator( *m_Head.head() );
1352         }
1353
1354         /// Returns a forward const iterator addressing the first element in a set
1355         const_iterator cbegin() const
1356         {
1357             return const_iterator( *m_Head.head() );
1358         }
1359
1360         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1361         iterator end()
1362         {
1363             return iterator();
1364         }
1365
1366         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1367         const_iterator end() const
1368         {
1369             return const_iterator();
1370         }
1371
1372         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1373         const_iterator cend() const
1374         {
1375             return const_iterator();
1376         }
1377     //@}
1378
1379     public:
1380         /// Inserts new node
1381         /**
1382             The function inserts \p val in the set if it does not contain
1383             an item with key equal to \p val.
1384
1385             The function applies RCU lock internally.
1386
1387             Returns \p true if \p val is placed into the set, \p false otherwise.
1388         */
1389         bool insert( value_type& val )
1390         {
1391             return insert( val, []( value_type& ) {} );
1392         }
1393
1394         /// Inserts new node
1395         /**
1396             This function is intended for derived non-intrusive containers.
1397
1398             The function allows to split creating of new item into two part:
1399             - create item with key only
1400             - insert new item into the set
1401             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1402
1403             The functor signature is:
1404             \code
1405                 void func( value_type& val );
1406             \endcode
1407             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1408             \p val no any other changes could be made on this set's item by concurrent threads.
1409             The user-defined functor is called only if the inserting is success.
1410
1411             RCU \p synchronize method can be called. RCU should not be locked.
1412         */
1413         template <typename Func>
1414         bool insert( value_type& val, Func f )
1415         {
1416             check_deadlock_policy::check();
1417
1418             position pos;
1419             bool bRet;
1420
1421             {
1422                 node_type * pNode = node_traits::to_node_ptr( val );
1423                 scoped_node_ptr scp( pNode );
1424                 unsigned int nHeight = pNode->height();
1425                 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1426                 bool bTowerMade = false;
1427
1428                 rcu_lock rcuLock;
1429
1430                 while ( true )
1431                 {
1432                     bool bFound = find_position( val, pos, key_comparator(), true );
1433                     if ( bFound ) {
1434                         // scoped_node_ptr deletes the node tower if we create it
1435                         if ( !bTowerMade )
1436                             scp.release();
1437
1438                         m_Stat.onInsertFailed();
1439                         bRet = false;
1440                         break;
1441                     }
1442
1443                     if ( !bTowerOk ) {
1444                         build_node( pNode );
1445                         nHeight = pNode->height();
1446                         bTowerMade =
1447                             bTowerOk = true;
1448                     }
1449
1450                     if ( !insert_at_position( val, pNode, pos, f )) {
1451                         m_Stat.onInsertRetry();
1452                         continue;
1453                     }
1454
1455                     increase_height( nHeight );
1456                     ++m_ItemCounter;
1457                     m_Stat.onAddNode( nHeight );
1458                     m_Stat.onInsertSuccess();
1459                     scp.release();
1460                     bRet =  true;
1461                     break;
1462                 }
1463             }
1464
1465             return bRet;
1466         }
1467
1468         /// Updates the node
1469         /**
1470             The operation performs inserting or changing data with lock-free manner.
1471
1472             If the item \p val is not found in the set, then \p val is inserted into the set
1473             iff \p bInsert is \p true.
1474             Otherwise, the functor \p func is called with item found.
1475             The functor signature is:
1476             \code
1477                 void func( bool bNew, value_type& item, value_type& val );
1478             \endcode
1479             with arguments:
1480             - \p bNew - \p true if the item has been inserted, \p false otherwise
1481             - \p item - item of the set
1482             - \p val - argument \p val passed into the \p %update() function
1483             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1484             refer to the same thing.
1485
1486             The functor can change non-key fields of the \p item; however, \p func must guarantee
1487             that during changing no any other modifications could be made on this item by concurrent threads.
1488
1489             RCU \p synchronize method can be called. RCU should not be locked.
1490
1491             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
1492             i.e. the node has been inserted or updated,
1493             \p second is \p true if new item has been added or \p false if the item with \p key
1494             already exists.
1495
1496             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
1497         */
1498         template <typename Func>
1499         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
1500         {
1501             check_deadlock_policy::check();
1502
1503             position pos;
1504             std::pair<bool, bool> bRet( true, false );
1505
1506             {
1507                 node_type * pNode = node_traits::to_node_ptr( val );
1508                 scoped_node_ptr scp( pNode );
1509                 unsigned int nHeight = pNode->height();
1510                 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1511                 bool bTowerMade = false;
1512
1513                 rcu_lock rcuLock;
1514                 while ( true )
1515                 {
1516                     bool bFound = find_position( val, pos, key_comparator(), true );
1517                     if ( bFound ) {
1518                         // scoped_node_ptr deletes the node tower if we create it before
1519                         if ( !bTowerMade )
1520                             scp.release();
1521
1522                         func( false, *node_traits::to_value_ptr(pos.pCur), val );
1523                         m_Stat.onUpdateExist();
1524                         break;
1525                     }
1526
1527                     if ( !bInsert ) {
1528                         scp.release();
1529                         bRet.first = false;
1530                         break;
1531                     }
1532
1533                     if ( !bTowerOk ) {
1534                         build_node( pNode );
1535                         nHeight = pNode->height();
1536                         bTowerMade =
1537                             bTowerOk = true;
1538                     }
1539
1540                     if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
1541                         m_Stat.onInsertRetry();
1542                         continue;
1543                     }
1544
1545                     increase_height( nHeight );
1546                     ++m_ItemCounter;
1547                     scp.release();
1548                     m_Stat.onAddNode( nHeight );
1549                     m_Stat.onUpdateNew();
1550                     bRet.second = true;
1551                     break;
1552                 }
1553             }
1554
1555             return bRet;
1556         }
1557         //@cond
1558         template <typename Func>
1559         CDS_DEPRECATED("ensure() is deprecated, use update()")
1560         std::pair<bool, bool> ensure( value_type& val, Func func )
1561         {
1562             return update( val, func, true );
1563         }
1564         //@endcond
1565
1566         /// Unlinks the item \p val from the set
1567         /**
1568             The function searches the item \p val in the set and unlink it from the set
1569             if it is found and is equal to \p val.
1570
1571             Difference between \p erase() and \p %unlink() functions: \p erase() finds <i>a key</i>
1572             and deletes the item found. \p %unlink() searches an item by key and deletes it
1573             only if \p val is an item of that set, i.e. the pointer to item found
1574             is equal to <tt> &val </tt>.
1575
1576             RCU \p synchronize method can be called. RCU should not be locked.
1577
1578             The \ref disposer specified in \p Traits class template parameter is called
1579             by garbage collector \p GC asynchronously.
1580
1581             The function returns \p true if success and \p false otherwise.
1582         */
1583         bool unlink( value_type& val )
1584         {
1585             check_deadlock_policy::check();
1586
1587             position pos;
1588             bool bRet;
1589
1590             {
1591                 rcu_lock l;
1592
1593                 if ( !find_position( val, pos, key_comparator(), false ) ) {
1594                     m_Stat.onUnlinkFailed();
1595                     bRet = false;
1596                 }
1597                 else {
1598                     node_type * pDel = pos.pCur;
1599                     assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1600
1601                     unsigned int nHeight = pDel->height();
1602
1603                     if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {}, false )) {
1604                         --m_ItemCounter;
1605                         m_Stat.onRemoveNode( nHeight );
1606                         m_Stat.onUnlinkSuccess();
1607                         bRet = true;
1608                     }
1609                     else {
1610                         m_Stat.onUnlinkFailed();
1611                         bRet = false;
1612                     }
1613                 }
1614             }
1615
1616             return bRet;
1617         }
1618
1619         /// Extracts the item from the set with specified \p key
1620         /** \anchor cds_intrusive_SkipListSet_rcu_extract
1621             The function searches an item with key equal to \p key in the set,
1622             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
1623             If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
1624
1625             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1626
1627             RCU \p synchronize method can be called. RCU should NOT be locked.
1628             The function does not call the disposer for the item found.
1629             The disposer will be implicitly invoked when the returned object is destroyed or when
1630             its \p release() member function is called.
1631             Example:
1632             \code
1633             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1634             skip_list theList;
1635             // ...
1636
1637             typename skip_list::exempt_ptr ep( theList.extract( 5 ));
1638             if ( ep ) {
1639                 // Deal with ep
1640                 //...
1641
1642                 // Dispose returned item.
1643                 ep.release();
1644             }
1645             \endcode
1646         */
1647         template <typename Q>
1648         exempt_ptr extract( Q const& key )
1649         {
1650             return exempt_ptr( do_extract( key ));
1651         }
1652
1653         /// Extracts the item from the set with comparing functor \p pred
1654         /**
1655             The function is an analog of \p extract(Q const&) but \p pred predicate is used for key comparing.
1656             \p Less has the interface like \p std::less.
1657             \p pred must imply the same element order as the comparator used for building the set.
1658         */
1659         template <typename Q, typename Less>
1660         exempt_ptr extract_with( Q const& key, Less pred )
1661         {
1662             return exempt_ptr( do_extract_with( key, pred ));
1663         }
1664
1665         /// Extracts an item with minimal key from the list
1666         /**
1667             The function searches an item with minimal key, unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
1668             If the skip-list is empty the function returns an empty \p exempt_ptr.
1669
1670             RCU \p synchronize method can be called. RCU should NOT be locked.
1671             The function does not call the disposer for the item found.
1672             The disposer will be implicitly invoked when the returned object is destroyed or when
1673             its \p release() member function is manually called.
1674             Example:
1675             \code
1676             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1677             skip_list theList;
1678             // ...
1679
1680             typename skip_list::exempt_ptr ep(theList.extract_min());
1681             if ( ep ) {
1682                 // Deal with ep
1683                 //...
1684
1685                 // Dispose returned item.
1686                 ep.release();
1687             }
1688             \endcode
1689
1690             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1691             It means that the function gets leftmost item and tries to unlink it.
1692             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1693             So, the function returns the item with minimum key at the moment of list traversing.
1694         */
1695         exempt_ptr extract_min()
1696         {
1697             return exempt_ptr( do_extract_min());
1698         }
1699
1700         /// Extracts an item with maximal key from the list
1701         /**
1702             The function searches an item with maximal key, unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
1703             If the skip-list is empty the function returns an empty \p exempt_ptr.
1704
1705             RCU \p synchronize method can be called. RCU should NOT be locked.
1706             The function does not call the disposer for the item found.
1707             The disposer will be implicitly invoked when the returned object is destroyed or when
1708             its \p release() member function is manually called.
1709             Example:
1710             \code
1711             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1712             skip_list theList;
1713             // ...
1714
1715             typename skip_list::exempt_ptr ep( theList.extract_max() );
1716             if ( ep ) {
1717                 // Deal with ep
1718                 //...
1719                 // Dispose returned item.
1720                 ep.release();
1721             }
1722             \endcode
1723
1724             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1725             It means that the function gets rightmost item and tries to unlink it.
1726             During unlinking, a concurrent thread can insert an item with key greater than rightmost item's key.
1727             So, the function returns the item with maximum key at the moment of list traversing.
1728         */
1729         exempt_ptr extract_max()
1730         {
1731             return exempt_ptr( do_extract_max());
1732         }
1733
1734         /// Deletes the item from the set
1735         /** \anchor cds_intrusive_SkipListSet_rcu_erase
1736             The function searches an item with key equal to \p key in the set,
1737             unlinks it from the set, and returns \p true.
1738             If the item with key equal to \p key is not found the function return \p false.
1739
1740             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1741
1742             RCU \p synchronize method can be called. RCU should not be locked.
1743         */
1744         template <typename Q>
1745         bool erase( const Q& key )
1746         {
1747             return do_erase( key, key_comparator(), [](value_type const&) {} );
1748         }
1749
1750         /// Delete the item from the set with comparing functor \p pred
1751         /**
1752             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase "erase(Q const&)"
1753             but \p pred predicate is used for key comparing.
1754             \p Less has the interface like \p std::less.
1755             \p pred must imply the same element order as the comparator used for building the set.
1756         */
1757         template <typename Q, typename Less>
1758         bool erase_with( const Q& key, Less pred )
1759         {
1760             CDS_UNUSED( pred );
1761             return do_erase( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1762         }
1763
1764         /// Deletes the item from the set
1765         /** \anchor cds_intrusive_SkipListSet_rcu_erase_func
1766             The function searches an item with key equal to \p key in the set,
1767             call \p f functor with item found, unlinks it from the set, and returns \p true.
1768             The \ref disposer specified in \p Traits class template parameter is called
1769             by garbage collector \p GC asynchronously.
1770
1771             The \p Func interface is
1772             \code
1773             struct functor {
1774                 void operator()( value_type const& item );
1775             };
1776             \endcode
1777             If the item with key equal to \p key is not found the function return \p false.
1778
1779             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1780
1781             RCU \p synchronize method can be called. RCU should not be locked.
1782         */
1783         template <typename Q, typename Func>
1784         bool erase( Q const& key, Func f )
1785         {
1786             return do_erase( key, key_comparator(), f );
1787         }
1788
1789         /// Delete the item from the set with comparing functor \p pred
1790         /**
1791             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
1792             but \p pred predicate is used for key comparing.
1793             \p Less has the interface like \p std::less.
1794             \p pred must imply the same element order as the comparator used for building the set.
1795         */
1796         template <typename Q, typename Less, typename Func>
1797         bool erase_with( Q const& key, Less pred, Func f )
1798         {
1799             CDS_UNUSED( pred );
1800             return do_erase( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1801         }
1802
1803         /// Finds \p key
1804         /** @anchor cds_intrusive_SkipListSet_rcu_find_func
1805             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1806             The interface of \p Func functor is:
1807             \code
1808             struct functor {
1809                 void operator()( value_type& item, Q& key );
1810             };
1811             \endcode
1812             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1813
1814             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1815             that \p item cannot be disposed during functor is executing.
1816             The functor does not serialize simultaneous access to the set \p item. If such access is
1817             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1818
1819             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
1820             can modify both arguments.
1821
1822             The function applies RCU lock internally.
1823
1824             The function returns \p true if \p key is found, \p false otherwise.
1825         */
1826         template <typename Q, typename Func>
1827         bool find( Q& key, Func f )
1828         {
1829             return do_find_with( key, key_comparator(), f );
1830         }
1831         //@cond
1832         template <typename Q, typename Func>
1833         bool find( Q const& key, Func f )
1834         {
1835             return do_find_with( key, key_comparator(), f );
1836         }
1837         //@endcond
1838
1839         /// Finds the key \p key with comparing functor \p pred
1840         /**
1841             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
1842             but \p cmp is used for key comparison.
1843             \p Less functor has the interface like \p std::less.
1844             \p cmp must imply the same element order as the comparator used for building the set.
1845         */
1846         template <typename Q, typename Less, typename Func>
1847         bool find_with( Q& key, Less pred, Func f )
1848         {
1849             CDS_UNUSED( pred );
1850             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1851         }
1852         //@cond
1853         template <typename Q, typename Less, typename Func>
1854         bool find_with( Q const& key, Less pred, Func f )
1855         {
1856             CDS_UNUSED( pred );
1857             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1858         }
1859         //@endcond
1860
1861         /// Checks whether the set contains \p key
1862         /**
1863             The function searches the item with key equal to \p key
1864             and returns \p true if it is found, and \p false otherwise.
1865
1866             The function applies RCU lock internally.
1867         */
1868         template <typename Q>
1869         bool contains( Q const& key )
1870         {
1871             return do_find_with( key, key_comparator(), [](value_type& , Q const& ) {} );
1872         }
1873         //@cond
1874         template <typename Q>
1875         CDS_DEPRECATED("deprecated, use contains()")
1876         bool find( Q const& key )
1877         {
1878             return contains( key );
1879         }
1880         //@endcond
1881
1882         /// Checks whether the set contains \p key using \p pred predicate for searching
1883         /**
1884             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1885             \p Less functor has the interface like \p std::less.
1886             \p Less must imply the same element order as the comparator used for building the set.
1887         */
1888         template <typename Q, typename Less>
1889         bool contains( Q const& key, Less pred )
1890         {
1891             CDS_UNUSED( pred );
1892             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1893         }
1894         //@cond
1895         template <typename Q, typename Less>
1896         CDS_DEPRECATED("deprecated, use contains()")
1897         bool find_with( Q const& key, Less pred )
1898         {
1899             return contains( key, pred );
1900         }
1901         //@endcond
1902
1903         /// Finds \p key and return the item found
1904         /** \anchor cds_intrusive_SkipListSet_rcu_get
1905             The function searches the item with key equal to \p key and returns a \p raw_ptr object pointed to item found.
1906             If \p key is not found it returns empty \p raw_ptr.
1907
1908             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1909
1910             RCU should be locked before call of this function.
1911             Returned item is valid only while RCU is locked:
1912             \code
1913             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1914             skip_list theList;
1915             // ...
1916             typename skip_list::raw_ptr pVal;
1917             {
1918                 // Lock RCU
1919                 skip_list::rcu_lock lock;
1920
1921                 pVal = theList.get( 5 );
1922                 if ( pVal ) {
1923                     // Deal with pVal
1924                     //...
1925                 }
1926             }
1927             // You can manually release pVal after RCU-locked section
1928             pVal.release();
1929             \endcode
1930         */
1931         template <typename Q>
1932         raw_ptr get( Q const& key )
1933         {
1934             assert( gc::is_locked());
1935
1936             position pos;
1937             value_type * pFound;
1938             if ( do_find_with( key, key_comparator(), [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos ))
1939                 return raw_ptr( pFound, raw_ptr_disposer( pos ));
1940             return raw_ptr( raw_ptr_disposer( pos ));
1941         }
1942
1943         /// Finds \p key and return the item found
1944         /**
1945             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_get "get(Q const&)"
1946             but \p pred is used for comparing the keys.
1947
1948             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1949             in any order.
1950             \p pred must imply the same element order as the comparator used for building the set.
1951         */
1952         template <typename Q, typename Less>
1953         raw_ptr get_with( Q const& key, Less pred )
1954         {
1955             CDS_UNUSED( pred );
1956             assert( gc::is_locked());
1957
1958             value_type * pFound = nullptr;
1959             position pos;
1960             if ( do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(),
1961                 [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos ))
1962             {
1963                 return raw_ptr( pFound, raw_ptr_disposer( pos ));
1964             }
1965             return raw_ptr( raw_ptr_disposer( pos ));
1966         }
1967
1968         /// Returns item count in the set
1969         /**
1970             The value returned depends on item counter type provided by \p Traits template parameter.
1971             For \p atomicity::empty_item_counter the function always returns 0.
1972             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1973             member function for this purpose.
1974         */
1975         size_t size() const
1976         {
1977             return m_ItemCounter;
1978         }
1979
1980         /// Checks if the set is empty
1981         bool empty() const
1982         {
1983             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1984         }
1985
1986         /// Clears the set (not atomic)
1987         /**
1988             The function unlink all items from the set.
1989             The function is not atomic, thus, in multi-threaded environment with parallel insertions
1990             this sequence
1991             \code
1992             set.clear();
1993             assert( set.empty() );
1994             \endcode
1995             the assertion could be raised.
1996
1997             For each item the \p disposer will be called automatically after unlinking.
1998         */
1999         void clear()
2000         {
2001             exempt_ptr ep;
2002             while ( (ep = extract_min()) );
2003         }
2004
2005         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
2006         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
2007         {
2008             return c_nMaxHeight;
2009         }
2010
2011         /// Returns const reference to internal statistics
2012         stat const& statistics() const
2013         {
2014             return m_Stat;
2015         }
2016     };
2017
2018 }} // namespace cds::intrusive
2019
2020
2021 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_RCU_H