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         //@cond
1532         // Deprecated, use update().
1533         template <typename Func>
1534         std::pair<bool, bool> ensure( value_type& val, Func func )
1535         {
1536             return update( val, func, true );
1537         }
1538         //@endcond
1539
1540         /// Unlinks the item \p val from the set
1541         /**
1542             The function searches the item \p val in the set and unlink it from the set
1543             if it is found and is equal to \p val.
1544
1545             Difference between \p erase() and \p %unlink() functions: \p erase() finds <i>a key</i>
1546             and deletes the item found. \p %unlink() searches an item by key and deletes it
1547             only if \p val is an item of that set, i.e. the pointer to item found
1548             is equal to <tt> &val </tt>.
1549
1550             RCU \p synchronize method can be called. RCU should not be locked.
1551
1552             The \ref disposer specified in \p Traits class template parameter is called
1553             by garbage collector \p GC asynchronously.
1554
1555             The function returns \p true if success and \p false otherwise.
1556         */
1557         bool unlink( value_type& val )
1558         {
1559             check_deadlock_policy::check();
1560
1561             position pos;
1562             bool bRet;
1563
1564             {
1565                 rcu_lock l;
1566
1567                 if ( !find_position( val, pos, key_comparator(), false ) ) {
1568                     m_Stat.onUnlinkFailed();
1569                     bRet = false;
1570                 }
1571                 else {
1572                     node_type * pDel = pos.pCur;
1573                     assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1574
1575                     unsigned int nHeight = pDel->height();
1576
1577                     if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos, [](value_type const&) {}, false )) {
1578                         --m_ItemCounter;
1579                         m_Stat.onRemoveNode( nHeight );
1580                         m_Stat.onUnlinkSuccess();
1581                         bRet = true;
1582                     }
1583                     else {
1584                         m_Stat.onUnlinkFailed();
1585                         bRet = false;
1586                     }
1587                 }
1588             }
1589
1590             return bRet;
1591         }
1592
1593         /// Extracts the item from the set with specified \p key
1594         /** \anchor cds_intrusive_SkipListSet_rcu_extract
1595             The function searches an item with key equal to \p key in the set,
1596             unlinks it from the set, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item found.
1597             If the item with key equal to \p key is not found the function returns an empty \p exempt_ptr.
1598
1599             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1600
1601             RCU \p synchronize method can be called. RCU should NOT be locked.
1602             The function does not call the disposer for the item found.
1603             The disposer will be implicitly invoked when the returned object is destroyed or when
1604             its \p release() member function is called.
1605             Example:
1606             \code
1607             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1608             skip_list theList;
1609             // ...
1610
1611             typename skip_list::exempt_ptr ep( theList.extract( 5 ));
1612             if ( ep ) {
1613                 // Deal with ep
1614                 //...
1615
1616                 // Dispose returned item.
1617                 ep.release();
1618             }
1619             \endcode
1620         */
1621         template <typename Q>
1622         exempt_ptr extract( Q const& key )
1623         {
1624             return exempt_ptr( do_extract( key ));
1625         }
1626
1627         /// Extracts the item from the set with comparing functor \p pred
1628         /**
1629             The function is an analog of \p extract(Q const&) but \p pred predicate is used for key comparing.
1630             \p Less has the interface like \p std::less.
1631             \p pred must imply the same element order as the comparator used for building the set.
1632         */
1633         template <typename Q, typename Less>
1634         exempt_ptr extract_with( Q const& key, Less pred )
1635         {
1636             return exempt_ptr( do_extract_with( key, pred ));
1637         }
1638
1639         /// Extracts an item with minimal key from the list
1640         /**
1641             The function searches an item with minimal key, unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
1642             If the skip-list is empty the function returns an empty \p exempt_ptr.
1643
1644             RCU \p synchronize method can be called. RCU should NOT be locked.
1645             The function does not call the disposer for the item found.
1646             The disposer will be implicitly invoked when the returned object is destroyed or when
1647             its \p release() member function is manually called.
1648             Example:
1649             \code
1650             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1651             skip_list theList;
1652             // ...
1653
1654             typename skip_list::exempt_ptr ep(theList.extract_min());
1655             if ( ep ) {
1656                 // Deal with ep
1657                 //...
1658
1659                 // Dispose returned item.
1660                 ep.release();
1661             }
1662             \endcode
1663
1664             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1665             It means that the function gets leftmost item and tries to unlink it.
1666             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1667             So, the function returns the item with minimum key at the moment of list traversing.
1668         */
1669         exempt_ptr extract_min()
1670         {
1671             return exempt_ptr( do_extract_min());
1672         }
1673
1674         /// Extracts an item with maximal key from the list
1675         /**
1676             The function searches an item with maximal key, unlinks it, and returns \ref cds::urcu::exempt_ptr "exempt_ptr" pointer to the item.
1677             If the skip-list is empty the function returns an empty \p exempt_ptr.
1678
1679             RCU \p synchronize method can be called. RCU should NOT be locked.
1680             The function does not call the disposer for the item found.
1681             The disposer will be implicitly invoked when the returned object is destroyed or when
1682             its \p release() member function is manually called.
1683             Example:
1684             \code
1685             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1686             skip_list theList;
1687             // ...
1688
1689             typename skip_list::exempt_ptr ep( theList.extract_max() );
1690             if ( ep ) {
1691                 // Deal with ep
1692                 //...
1693                 // Dispose returned item.
1694                 ep.release();
1695             }
1696             \endcode
1697
1698             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1699             It means that the function gets rightmost item and tries to unlink it.
1700             During unlinking, a concurrent thread can insert an item with key greater than rightmost item's key.
1701             So, the function returns the item with maximum key at the moment of list traversing.
1702         */
1703         exempt_ptr extract_max()
1704         {
1705             return exempt_ptr( do_extract_max());
1706         }
1707
1708         /// Deletes the item from the set
1709         /** \anchor cds_intrusive_SkipListSet_rcu_erase
1710             The function searches an item with key equal to \p key in the set,
1711             unlinks it from the set, and returns \p true.
1712             If the item with key equal to \p key is not found the function return \p false.
1713
1714             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1715
1716             RCU \p synchronize method can be called. RCU should not be locked.
1717         */
1718         template <typename Q>
1719         bool erase( const Q& key )
1720         {
1721             return do_erase( key, key_comparator(), [](value_type const&) {} );
1722         }
1723
1724         /// Delete the item from the set with comparing functor \p pred
1725         /**
1726             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase "erase(Q const&)"
1727             but \p pred predicate is used for key comparing.
1728             \p Less has the interface like \p std::less.
1729             \p pred must imply the same element order as the comparator used for building the set.
1730         */
1731         template <typename Q, typename Less>
1732         bool erase_with( const Q& key, Less pred )
1733         {
1734             CDS_UNUSED( pred );
1735             return do_erase( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1736         }
1737
1738         /// Deletes the item from the set
1739         /** \anchor cds_intrusive_SkipListSet_rcu_erase_func
1740             The function searches an item with key equal to \p key in the set,
1741             call \p f functor with item found, unlinks it from the set, and returns \p true.
1742             The \ref disposer specified in \p Traits class template parameter is called
1743             by garbage collector \p GC asynchronously.
1744
1745             The \p Func interface is
1746             \code
1747             struct functor {
1748                 void operator()( value_type const& item );
1749             };
1750             \endcode
1751             If the item with key equal to \p key is not found the function return \p false.
1752
1753             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1754
1755             RCU \p synchronize method can be called. RCU should not be locked.
1756         */
1757         template <typename Q, typename Func>
1758         bool erase( Q const& key, Func f )
1759         {
1760             return do_erase( key, key_comparator(), f );
1761         }
1762
1763         /// Delete the item from the set with comparing functor \p pred
1764         /**
1765             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
1766             but \p pred predicate is used for key comparing.
1767             \p Less has the interface like \p std::less.
1768             \p pred must imply the same element order as the comparator used for building the set.
1769         */
1770         template <typename Q, typename Less, typename Func>
1771         bool erase_with( Q const& key, Less pred, Func f )
1772         {
1773             CDS_UNUSED( pred );
1774             return do_erase( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1775         }
1776
1777         /// Finds \p key
1778         /** @anchor cds_intrusive_SkipListSet_rcu_find_func
1779             The function searches the item with key equal to \p key and calls the functor \p f for item found.
1780             The interface of \p Func functor is:
1781             \code
1782             struct functor {
1783                 void operator()( value_type& item, Q& key );
1784             };
1785             \endcode
1786             where \p item is the item found, \p key is the <tt>find</tt> function argument.
1787
1788             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1789             that \p item cannot be disposed during functor is executing.
1790             The functor does not serialize simultaneous access to the set \p item. If such access is
1791             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1792
1793             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
1794             can modify both arguments.
1795
1796             The function applies RCU lock internally.
1797
1798             The function returns \p true if \p key is found, \p false otherwise.
1799         */
1800         template <typename Q, typename Func>
1801         bool find( Q& key, Func f )
1802         {
1803             return do_find_with( key, key_comparator(), f );
1804         }
1805         //@cond
1806         template <typename Q, typename Func>
1807         bool find( Q const& key, Func f )
1808         {
1809             return do_find_with( key, key_comparator(), f );
1810         }
1811         //@endcond
1812
1813         /// Finds the key \p key with comparing functor \p pred
1814         /**
1815             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
1816             but \p cmp is used for key comparison.
1817             \p Less functor has the interface like \p std::less.
1818             \p cmp must imply the same element order as the comparator used for building the set.
1819         */
1820         template <typename Q, typename Less, typename Func>
1821         bool find_with( Q& key, Less pred, Func f )
1822         {
1823             CDS_UNUSED( pred );
1824             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1825         }
1826         //@cond
1827         template <typename Q, typename Less, typename Func>
1828         bool find_with( Q const& key, Less pred, Func f )
1829         {
1830             CDS_UNUSED( pred );
1831             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), f );
1832         }
1833         //@endcond
1834
1835         /// Checks whether the set contains \p key
1836         /**
1837             The function searches the item with key equal to \p key
1838             and returns \p true if it is found, and \p false otherwise.
1839
1840             The function applies RCU lock internally.
1841         */
1842         template <typename Q>
1843         bool contains( Q const& key )
1844         {
1845             return do_find_with( key, key_comparator(), [](value_type& , Q const& ) {} );
1846         }
1847         //@cond
1848         // Deprecated, use contains()
1849         template <typename Q>
1850         bool find( Q const& key )
1851         {
1852             return contains( key );
1853         }
1854         //@endcond
1855
1856         /// Checks whether the set contains \p key using \p pred predicate for searching
1857         /**
1858             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
1859             \p Less functor has the interface like \p std::less.
1860             \p Less must imply the same element order as the comparator used for building the set.
1861         */
1862         template <typename Q, typename Less>
1863         bool contains( Q const& key, Less pred )
1864         {
1865             CDS_UNUSED( pred );
1866             return do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
1867         }
1868         //@cond
1869         // Deprecated, use contains()
1870         template <typename Q, typename Less>
1871         bool find_with( Q const& key, Less pred )
1872         {
1873             return contains( key, pred );
1874         }
1875         //@endcond
1876
1877         /// Finds \p key and return the item found
1878         /** \anchor cds_intrusive_SkipListSet_rcu_get
1879             The function searches the item with key equal to \p key and returns a \p raw_ptr object pointed to item found.
1880             If \p key is not found it returns empty \p raw_ptr.
1881
1882             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1883
1884             RCU should be locked before call of this function.
1885             Returned item is valid only while RCU is locked:
1886             \code
1887             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1888             skip_list theList;
1889             // ...
1890             typename skip_list::raw_ptr pVal;
1891             {
1892                 // Lock RCU
1893                 skip_list::rcu_lock lock;
1894
1895                 pVal = theList.get( 5 );
1896                 if ( pVal ) {
1897                     // Deal with pVal
1898                     //...
1899                 }
1900             }
1901             // You can manually release pVal after RCU-locked section
1902             pVal.release();
1903             \endcode
1904         */
1905         template <typename Q>
1906         raw_ptr get( Q const& key )
1907         {
1908             assert( gc::is_locked());
1909
1910             position pos;
1911             value_type * pFound;
1912             if ( do_find_with( key, key_comparator(), [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos ))
1913                 return raw_ptr( pFound, raw_ptr_disposer( pos ));
1914             return raw_ptr( raw_ptr_disposer( pos ));
1915         }
1916
1917         /// Finds \p key and return the item found
1918         /**
1919             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_get "get(Q const&)"
1920             but \p pred is used for comparing the keys.
1921
1922             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
1923             in any order.
1924             \p pred must imply the same element order as the comparator used for building the set.
1925         */
1926         template <typename Q, typename Less>
1927         raw_ptr get_with( Q const& key, Less pred )
1928         {
1929             CDS_UNUSED( pred );
1930             assert( gc::is_locked());
1931
1932             value_type * pFound = nullptr;
1933             position pos;
1934             if ( do_find_with( key, cds::opt::details::make_comparator_from_less<Less>(),
1935                 [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos ))
1936             {
1937                 return raw_ptr( pFound, raw_ptr_disposer( pos ));
1938             }
1939             return raw_ptr( raw_ptr_disposer( pos ));
1940         }
1941
1942         /// Returns item count in the set
1943         /**
1944             The value returned depends on item counter type provided by \p Traits template parameter.
1945             For \p atomicity::empty_item_counter the function always returns 0.
1946             Therefore, the function is not suitable for checking the set emptiness, use \p empty()
1947             member function for this purpose.
1948         */
1949         size_t size() const
1950         {
1951             return m_ItemCounter;
1952         }
1953
1954         /// Checks if the set is empty
1955         bool empty() const
1956         {
1957             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1958         }
1959
1960         /// Clears the set (not atomic)
1961         /**
1962             The function unlink all items from the set.
1963             The function is not atomic, thus, in multi-threaded environment with parallel insertions
1964             this sequence
1965             \code
1966             set.clear();
1967             assert( set.empty() );
1968             \endcode
1969             the assertion could be raised.
1970
1971             For each item the \p disposer will be called automatically after unlinking.
1972         */
1973         void clear()
1974         {
1975             exempt_ptr ep;
1976             while ( (ep = extract_min()) );
1977         }
1978
1979         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1980         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1981         {
1982             return c_nMaxHeight;
1983         }
1984
1985         /// Returns const reference to internal statistics
1986         stat const& statistics() const
1987         {
1988             return m_Stat;
1989         }
1990     };
1991
1992 }} // namespace cds::intrusive
1993
1994
1995 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_RCU_H