cds/intrusive/skip_list_rcu.h

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