cds/intrusive/skip_list_rcu.h

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