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