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