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 <cds/intrusive/skip_list_base.h>
   7 #include <cds/details/std/type_traits.h>
   8 #include <cds/details/std/memory.h>
   9 #include <cds/opt/compare.h>
  10 #include <cds/ref.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 CDS_ATOMIC::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 NULL
  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(), CDS_ATOMIC::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(), CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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 NULL 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
 601 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 602         struct empty_insert_functor {
 603             void operator()( value_type& )
 604             {}
 605         };
 606
 607         struct empty_erase_functor  {
 608             void operator()( value_type const& )
 609             {}
 610         };
 611
 612         struct empty_find_functor {
 613             template <typename Q>
 614             void operator()( value_type& item, Q& val )
 615             {}
 616         };
 617
 618         struct get_functor {
 619             value_type *    pFound;
 620
 621             template <typename Q>
 622             void operator()( value_type& item, Q& val )
 623             {
 624                 pFound = &item;
 625             }
 626         };
 627
 628         template <typename Func>
 629         struct insert_at_ensure_functor {
 630             Func m_func;
 631             insert_at_ensure_functor( Func f ) : m_func(f) {}
 632
 633             void operator()( value_type& item )
 634             {
 635                 cds::unref( m_func)( true, item, item );
 636             }
 637         };
 638
 639         struct copy_value_functor {
 640             template <typename Q>
 641             void operator()( Q& dest, value_type const& src ) const
 642             {
 643                 dest = src;
 644             }
 645         };
 646
 647 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 648
 649         //@endcond
 650
 651     protected:
 652         skip_list::details::head_node< node_type >      m_Head  ;   ///< head tower (max height)
 653
 654         item_counter                m_ItemCounter       ;   ///< item counter
 655         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance
 656         CDS_ATOMIC::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level
 657         CDS_ATOMIC::atomic<node_type *>     m_pDeferredDelChain ;   ///< Deferred deleted node chain
 658         mutable stat                m_Stat              ;   ///< internal statistics
 659
 660     protected:
 661         //@cond
 662         unsigned int random_level()
 663         {
 664             // Random generator produces a number from range [0..31]
 665             // We need a number from range [1..32]
 666             return m_RandomLevelGen() + 1;
 667         }
 668
 669         template <typename Q>
 670         node_type * build_node( Q v )
 671         {
 672             return node_builder::make_tower( v, m_RandomLevelGen );
 673         }
 674
 675         static void dispose_node( value_type * pVal )
 676         {
 677             assert( pVal != NULL );
 678
 679             typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) );
 680             disposer()( pVal );
 681         }
 682
 683         struct node_disposer
 684         {
 685             void operator()( value_type * pVal )
 686             {
 687                 dispose_node( pVal );
 688             }
 689         };
 690         //@endcond
 691
 692     public:
 693         typedef cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void > exempt_ptr ; ///< pointer to extracted node
 694
 695     protected:
 696         //@cond
 697
 698         bool is_extracted( marked_node_ptr const p ) const
 699         {
 700             return (p.bits() & 2) != 0;
 701         }
 702
 703         template <typename Q, typename Compare >
 704         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
 705         {
 706             assert( gc::is_locked() );
 707
 708             node_type * pPred;
 709             marked_node_ptr pSucc;
 710             marked_node_ptr pCur;
 711             int nCmp = 1;
 712
 713         retry:
 714             pPred = m_Head.head();
 715
 716             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 717
 718                 while ( true ) {
 719                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 720                     if ( pCur.bits() ) {
 721                         // pCur.bits() means that pPred is logically deleted
 722                         goto retry;
 723                     }
 724
 725                     if ( pCur.ptr() == nullptr ) {
 726                         // end of the list at level nLevel - goto next level
 727                         break;
 728                     }
 729
 730                     // pSucc contains deletion mark for pCur
 731                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 732
 733                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 734                         goto retry;
 735
 736                     if ( pSucc.bits() ) {
 737                         // pCur is marked, i.e. logically deleted.
 738                         marked_node_ptr p( pCur.ptr() );
 739                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 740                              memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 741                         {
 742                             if ( nLevel == 0 ) {
 743 #                       ifdef _DEBUG
 744                                 pCur->m_bUnlinked = true;
 745 #                       endif
 746
 747                                 if ( !is_extracted( pSucc )) {
 748                                     // We cannot free the node at this moment since RCU is locked
 749                                     // Link deleted nodes to a chain to free later
 750                                     link_for_remove( pos, pCur.ptr() );
 751                                     m_Stat.onEraseWhileFind();
 752                                 }
 753                                 else {
 754                                     m_Stat.onExtractWhileFind();
 755                                 }
 756                             }
 757                         }
 758                         goto retry;
 759                     }
 760                     else {
 761                         nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val );
 762                         if ( nCmp < 0 )
 763                             pPred = pCur.ptr();
 764                         else if ( nCmp == 0 && bStopIfFound )
 765                             goto found;
 766                         else
 767                             break;
 768                     }
 769                 }
 770
 771                 // Next level
 772                 pos.pPrev[ nLevel ] = pPred;
 773                 pos.pSucc[ nLevel ] = pCur.ptr();
 774             }
 775
 776             if ( nCmp != 0 )
 777                 return false;
 778
 779         found:
 780             pos.pCur = pCur.ptr();
 781             return pCur.ptr() && nCmp == 0;
 782         }
 783
 784         bool find_min_position( position& pos )
 785         {
 786             assert( gc::is_locked() );
 787
 788             node_type * pPred;
 789             marked_node_ptr pSucc;
 790             marked_node_ptr pCur;
 791
 792         retry:
 793             pPred = m_Head.head();
 794
 795             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 796
 797                 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 798                 // pCur.bits() means that pPred is logically deleted
 799                 // head cannot be deleted
 800                 assert( pCur.bits() == 0 );
 801
 802                 if ( pCur.ptr() ) {
 803
 804                     // pSucc contains deletion mark for pCur
 805                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 806
 807                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 808                         goto retry;
 809
 810                     if ( pSucc.bits() ) {
 811                         // pCur is marked, i.e. logically deleted.
 812                         marked_node_ptr p( pCur.ptr() );
 813                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 814                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 815                         {
 816                             if ( nLevel == 0 ) {
 817 #                       ifdef _DEBUG
 818                                 pCur->m_bUnlinked = true;
 819 #                       endif
 820
 821                                 if ( !is_extracted( pSucc )) {
 822                                     // We cannot free the node at this moment since RCU is locked
 823                                     // Link deleted nodes to a chain to free later
 824                                     link_for_remove( pos, pCur.ptr() );
 825                                     m_Stat.onEraseWhileFind();
 826                                 }
 827                                 else {
 828                                     m_Stat.onExtractWhileFind();
 829                                 }
 830                             }
 831                         }
 832                         goto retry;
 833                     }
 834                 }
 835
 836                 // Next level
 837                 pos.pPrev[ nLevel ] = pPred;
 838                 pos.pSucc[ nLevel ] = pCur.ptr();
 839             }
 840             return (pos.pCur = pCur.ptr()) != nullptr;
 841         }
 842
 843         bool find_max_position( position& pos )
 844         {
 845             assert( gc::is_locked() );
 846
 847             node_type * pPred;
 848             marked_node_ptr pSucc;
 849             marked_node_ptr pCur;
 850
 851 retry:
 852             pPred = m_Head.head();
 853
 854             for ( int nLevel = static_cast<int>(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) {
 855
 856                 while ( true ) {
 857                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 858                     if ( pCur.bits() ) {
 859                         // pCur.bits() means that pPred is logically deleted
 860                         goto retry;
 861                     }
 862
 863                     if ( pCur.ptr() == nullptr ) {
 864                         // end of the list at level nLevel - goto next level
 865                         break;
 866                     }
 867
 868                     // pSucc contains deletion mark for pCur
 869                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 870
 871                     if ( pPred->next( nLevel ).load( memory_model::memory_order_relaxed ).all() != pCur.ptr() )
 872                         goto retry;
 873
 874                     if ( pSucc.bits() ) {
 875                         // pCur is marked, i.e. logically deleted.
 876                         marked_node_ptr p( pCur.ptr() );
 877                         if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
 878                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
 879                         {
 880                             if ( nLevel == 0 ) {
 881 #                       ifdef _DEBUG
 882                                 pCur->m_bUnlinked = true;
 883 #                       endif
 884
 885                                 if ( !is_extracted( pSucc )) {
 886                                     // We cannot free the node at this moment since RCU is locked
 887                                     // Link deleted nodes to a chain to free later
 888                                     link_for_remove( pos, pCur.ptr() );
 889                                     m_Stat.onEraseWhileFind();
 890                                 }
 891                                 else {
 892                                     m_Stat.onExtractWhileFind();
 893                                 }
 894                             }
 895                         }
 896                         goto retry;
 897                     }
 898                     else {
 899                         if ( !pSucc.ptr() )
 900                             break;
 901
 902                         pPred = pCur.ptr();
 903                     }
 904                 }
 905
 906                 // Next level
 907                 pos.pPrev[ nLevel ] = pPred;
 908                 pos.pSucc[ nLevel ] = pCur.ptr();
 909             }
 910
 911             return (pos.pCur = pCur.ptr()) != nullptr;
 912         }
 913
 914         template <typename Func>
 915         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 916         {
 917             assert( gc::is_locked() );
 918
 919             unsigned int nHeight = pNode->height();
 920             pNode->clear_tower();
 921
 922             {
 923                 marked_node_ptr p( pos.pSucc[0] );
 924                 pNode->next( 0 ).store( p, memory_model::memory_order_release );
 925                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) {
 926                     return false;
 927                 }
 928 #       ifdef _DEBUG
 929                 pNode->m_bLinked = true;
 930 #       endif
 931                 cds::unref( f )( val );
 932             }
 933
 934             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 935                 marked_node_ptr p;
 936                 while ( true ) {
 937                     marked_node_ptr q( pos.pSucc[ nLevel ]);
 938                     if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed )) {
 939                         // pNode has been marked as removed while we are inserting it
 940                         // Stop inserting
 941                         assert( p.bits() );
 942                         m_Stat.onLogicDeleteWhileInsert();
 943                         return true;
 944                     }
 945                     p = q;
 946                     if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ) )
 947                         break;
 948
 949                     // Renew insert position
 950                     m_Stat.onRenewInsertPosition();
 951                     if ( !find_position( val, pos, key_comparator(), false )) {
 952                         // The node has been deleted while we are inserting it
 953                         m_Stat.onNotFoundWhileInsert();
 954                         return true;
 955                     }
 956                 }
 957             }
 958             return true;
 959         }
 960
 961         static void link_for_remove( position& pos, node_type * pDel )
 962         {
 963             assert( pDel->m_pDelChain == nullptr );
 964
 965             pDel->m_pDelChain = pos.pDelChain;
 966             pos.pDelChain = pDel;
 967         }
 968
 969         template <typename Func>
 970         bool try_remove_at( node_type * pDel, position& pos, Func f, bool bExtract )
 971         {
 972             assert( pDel != nullptr );
 973             assert( gc::is_locked() );
 974
 975             marked_node_ptr pSucc;
 976
 977             // logical deletion (marking)
 978             for ( unsigned int nLevel = pDel->height() - 1; nLevel > 0; --nLevel ) {
 979                 pSucc = pDel->next(nLevel).load( memory_model::memory_order_relaxed );
 980                 while ( true ) {
 981                     if ( pSucc.bits()
 982                       || pDel->next(nLevel).compare_exchange_weak( pSucc, pSucc | 1, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
 983                     {
 984                         break;
 985                     }
 986                 }
 987             }
 988
 989             pSucc = pDel->next(0).load( memory_model::memory_order_relaxed );
 990             while ( true ) {
 991                 if ( pSucc.bits() )
 992                     return false;
 993
 994                 int const nMask = bExtract ? 3 : 1;
 995                 if ( pDel->next(0).compare_exchange_strong( pSucc, pSucc | nMask, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ))
 996                 {
 997                     cds::unref(f)( *node_traits::to_value_ptr( pDel ));
 998
 999                     // physical deletion
1000                     // try fast erase
1001                     pSucc = pDel;
1002                     for ( int nLevel = static_cast<int>( pDel->height() - 1 ); nLevel >= 0; --nLevel ) {
1003                         if ( !pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( pSucc,
1004                             marked_node_ptr( pDel->next(nLevel).load(memory_model::memory_order_relaxed).ptr() ),
1005                             memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed) )
1006                         {
1007                             // Do slow erase
1008                             find_position( *node_traits::to_value_ptr(pDel), pos, key_comparator(), false );
1009                             if ( bExtract )
1010                                 m_Stat.onSlowExtract();
1011                             else
1012                                 m_Stat.onSlowErase();
1013 #                        ifdef _DEBUG
1014                             assert( pDel->m_bUnlinked );
1015 #                        endif
1016                             return true;
1017                         }
1018                     }
1019
1020 #               ifdef _DEBUG
1021                     pDel->m_bUnlinked = true;
1022 #               endif
1023                     if ( !bExtract ) {
1024                         // We cannot free the node at this moment since RCU is locked
1025                         // Link deleted nodes to a chain to free later
1026                         link_for_remove( pos, pDel );
1027                         m_Stat.onFastErase();
1028                     }
1029                     else
1030                         m_Stat.onFastExtract();
1031
1032                     return true;
1033                 }
1034             }
1035         }
1036
1037         enum finsd_fastpath_result {
1038             find_fastpath_found,
1039             find_fastpath_not_found,
1040             find_fastpath_abort
1041         };
1042         template <typename Q, typename Compare, typename Func>
1043         finsd_fastpath_result find_fastpath( Q& val, Compare cmp, Func f ) const
1044         {
1045             node_type * pPred;
1046             marked_node_ptr pCur;
1047             marked_node_ptr pSucc;
1048             marked_node_ptr pNull;
1049
1050             back_off bkoff;
1051
1052             pPred = m_Head.head();
1053             for ( int nLevel = static_cast<int>(m_nHeight.load(memory_model::memory_order_relaxed) - 1); nLevel >= 0; --nLevel ) {
1054                 pCur = pPred->next(nLevel).load( memory_model::memory_order_acquire );
1055                 if ( pCur == pNull )
1056                     continue;
1057
1058                 while ( pCur != pNull ) {
1059                     if ( pCur.bits() ) {
1060                         // Wait until pCur is removed
1061                         unsigned int nAttempt = 0;
1062                         while ( pCur.bits() && nAttempt++ < 16 ) {
1063                             bkoff();
1064                             pCur = pPred->next(nLevel).load( memory_model::memory_order_acquire );
1065                         }
1066                         bkoff.reset();
1067
1068                         if ( pCur.bits() ) {
1069                             // Maybe, we are on deleted node sequence
1070                             // Abort searching, try slow-path
1071                             return find_fastpath_abort;
1072                         }
1073                     }
1074
1075                     if ( pCur.ptr() ) {
1076                         int nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val );
1077                         if ( nCmp < 0 ) {
1078                             pPred = pCur.ptr();
1079                             pCur = pCur->next(nLevel).load( memory_model::memory_order_acquire );
1080                         }
1081                         else if ( nCmp == 0 ) {
1082                             // found
1083                             cds::unref(f)( *node_traits::to_value_ptr( pCur.ptr() ), val );
1084                             return find_fastpath_found;
1085                         }
1086                         else // pCur > val - go down
1087                             break;
1088                     }
1089                 }
1090             }
1091
1092             return find_fastpath_not_found;
1093         }
1094
1095         template <typename Q, typename Compare, typename Func>
1096         bool find_slowpath( Q& val, Compare cmp, Func f, position& pos )
1097         {
1098             if ( find_position( val, pos, cmp, true )) {
1099                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
1100
1101                 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
1102                 return true;
1103             }
1104             else
1105                 return false;
1106         }
1107
1108         template <typename Q, typename Compare, typename Func>
1109         bool do_find_with( Q& val, Compare cmp, Func f )
1110         {
1111             position pos;
1112             bool bRet;
1113
1114             rcu_lock l;
1115
1116             switch ( find_fastpath( val, cmp, f )) {
1117             case find_fastpath_found:
1118                 m_Stat.onFindFastSuccess();
1119                 return true;
1120             case find_fastpath_not_found:
1121                 m_Stat.onFindFastFailed();
1122                 return false;
1123             default:
1124                 break;
1125             }
1126
1127             if ( find_slowpath( val, cmp, f, pos )) {
1128                 m_Stat.onFindSlowSuccess();
1129                 bRet = true;
1130             }
1131             else {
1132                 m_Stat.onFindSlowFailed();
1133                 bRet = false;
1134             }
1135
1136             defer_chain( pos );
1137
1138             return bRet;
1139         }
1140
1141         template <typename Q, typename Compare, typename Func>
1142         bool do_erase( Q const& val, Compare cmp, Func f )
1143         {
1144             check_deadlock_policy::check();
1145
1146             position pos;
1147             bool bRet;
1148
1149             {
1150                 rcu_lock rcuLock;
1151
1152                 if ( !find_position( val, pos, cmp, false ) ) {
1153                     m_Stat.onEraseFailed();
1154                     bRet = false;
1155                 }
1156                 else {
1157                     node_type * pDel = pos.pCur;
1158                     assert( cmp( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1159
1160                     unsigned int nHeight = pDel->height();
1161                     if ( try_remove_at( pDel, pos, f, false )) {
1162                         --m_ItemCounter;
1163                         m_Stat.onRemoveNode( nHeight );
1164                         m_Stat.onEraseSuccess();
1165                         bRet = true;
1166                     }
1167                     else {
1168                         m_Stat.onEraseFailed();
1169                         bRet = false;
1170                     }
1171                 }
1172             }
1173
1174             dispose_chain( pos );
1175             return bRet;
1176         }
1177
1178         template <typename Q, typename Compare>
1179         value_type * do_extract_key( Q const& key, Compare cmp )
1180         {
1181             // RCU should be locked!!!
1182             assert( gc::is_locked() );
1183
1184             position pos;
1185             node_type * pDel;
1186
1187             if ( !find_position( key, pos, cmp, false ) ) {
1188                 m_Stat.onExtractFailed();
1189                 pDel = nullptr;
1190             }
1191             else {
1192                 pDel = pos.pCur;
1193                 assert( cmp( *node_traits::to_value_ptr( pDel ), key ) == 0 );
1194
1195                 unsigned int const nHeight = pDel->height();
1196
1197                 if ( try_remove_at( pDel, pos,
1198 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1199                     [](value_type const&) {}
1200 #       else
1201                     empty_erase_functor()
1202 #       endif
1203                     , true ))
1204                 {
1205                     --m_ItemCounter;
1206                     m_Stat.onRemoveNode( nHeight );
1207                     m_Stat.onExtractSuccess();
1208                 }
1209                 else {
1210                     m_Stat.onExtractFailed();
1211                     pDel = nullptr;
1212                 }
1213             }
1214
1215             defer_chain( pos );
1216             return pDel ? node_traits::to_value_ptr( pDel ) : nullptr;
1217         }
1218
1219         template <typename ExemptPtr, typename Q>
1220         bool do_extract( ExemptPtr& result, Q const& key )
1221         {
1222             check_deadlock_policy::check();
1223
1224             bool bReturn;
1225             {
1226                 rcu_lock l;
1227                 value_type * pDel = do_extract_key( key, key_comparator() );
1228                 bReturn = pDel != nullptr;
1229                 if ( bReturn )
1230                     result = pDel;
1231             }
1232
1233             dispose_deferred();
1234             return bReturn;
1235         }
1236
1237         template <typename ExemptPtr, typename Q, typename Less>
1238         bool do_extract_with( ExemptPtr& result, Q const& key, Less pred )
1239         {
1240             check_deadlock_policy::check();
1241
1242             bool bReturn;
1243             {
1244                 rcu_lock l;
1245                 value_type * pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less<Less>() );
1246                 bReturn = pDel != nullptr;
1247                 if ( bReturn )
1248                     result = pDel;
1249             }
1250
1251             dispose_deferred();
1252             return bReturn;
1253         }
1254
1255         node_type * do_extract_min()
1256         {
1257             assert( gc::is_locked() );
1258
1259             position pos;
1260             node_type * pDel;
1261
1262             if ( !find_min_position( pos ) ) {
1263                 m_Stat.onExtractMinFailed();
1264                 pDel = nullptr;
1265             }
1266             else {
1267                 pDel = pos.pCur;
1268                 unsigned int const nHeight = pDel->height();
1269
1270                 if ( try_remove_at( pDel, pos,
1271 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1272                     [](value_type const&) {}
1273 #       else
1274                     empty_erase_functor()
1275 #       endif
1276                     , true ))
1277                 {
1278                     --m_ItemCounter;
1279                     m_Stat.onRemoveNode( nHeight );
1280                     m_Stat.onExtractMinSuccess();
1281                 }
1282                 else {
1283                     m_Stat.onExtractMinFailed();
1284                     pDel = nullptr;
1285                 }
1286             }
1287
1288             defer_chain( pos );
1289             return pDel;
1290         }
1291
1292         template <typename ExemptPtr>
1293         bool do_extract_min( ExemptPtr& result )
1294         {
1295             check_deadlock_policy::check();
1296
1297             bool bReturn;
1298             {
1299                 rcu_lock l;
1300                 node_type * pDel = do_extract_min();
1301                 bReturn = pDel != nullptr;
1302                 if ( bReturn )
1303                     result = node_traits::to_value_ptr(pDel);
1304             }
1305
1306             dispose_deferred();
1307             return bReturn;
1308         }
1309
1310         node_type * do_extract_max()
1311         {
1312             assert( gc::is_locked() );
1313
1314             position pos;
1315             node_type * pDel;
1316
1317             if ( !find_max_position( pos ) ) {
1318                 m_Stat.onExtractMaxFailed();
1319                 pDel = nullptr;
1320             }
1321             else {
1322                 pDel = pos.pCur;
1323                 unsigned int const nHeight = pDel->height();
1324
1325                 if ( try_remove_at( pDel, pos,
1326 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1327                     [](value_type const&) {}
1328 #       else
1329                     empty_erase_functor()
1330 #       endif
1331                     , true ))
1332                 {
1333                     --m_ItemCounter;
1334                     m_Stat.onRemoveNode( nHeight );
1335                     m_Stat.onExtractMaxSuccess();
1336                 }
1337                 else {
1338                     m_Stat.onExtractMaxFailed();
1339                     pDel = nullptr;
1340                 }
1341             }
1342
1343             defer_chain( pos );
1344             return pDel;
1345         }
1346
1347         template <typename ExemptPtr>
1348         bool do_extract_max( ExemptPtr& result )
1349         {
1350             check_deadlock_policy::check();
1351
1352             bool bReturn;
1353             {
1354                 rcu_lock l;
1355                 node_type * pDel = do_extract_max();
1356                 bReturn = pDel != nullptr;
1357                 if ( bReturn )
1358                     result = node_traits::to_value_ptr(pDel);
1359             }
1360
1361             dispose_deferred();
1362             return bReturn;
1363         }
1364
1365         void increase_height( unsigned int nHeight )
1366         {
1367             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
1368             if ( nCur < nHeight )
1369                 m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
1370         }
1371
1372         class deferred_list_iterator
1373         {
1374             node_type * pCur;
1375         public:
1376             explicit deferred_list_iterator( node_type * p )
1377                 : pCur(p)
1378             {}
1379             deferred_list_iterator()
1380                 : pCur( nullptr )
1381             {}
1382
1383             cds::urcu::retired_ptr operator *() const
1384             {
1385                 return cds::urcu::retired_ptr( node_traits::to_value_ptr(pCur), dispose_node );
1386             }
1387
1388             void operator ++()
1389             {
1390                 pCur = pCur->m_pDelChain;
1391             }
1392
1393             bool operator ==( deferred_list_iterator const& i ) const
1394             {
1395                 return pCur == i.pCur;
1396             }
1397             bool operator !=( deferred_list_iterator const& i ) const
1398             {
1399                 return !operator ==( i );
1400             }
1401         };
1402
1403         void dispose_chain( node_type * pHead )
1404         {
1405             // RCU should NOT be locked
1406             check_deadlock_policy::check();
1407
1408             gc::batch_retire( deferred_list_iterator( pHead ), deferred_list_iterator() );
1409         }
1410
1411         void dispose_chain( position& pos )
1412         {
1413             // RCU should NOT be locked
1414             check_deadlock_policy::check();
1415
1416             // Delete local chain
1417             if ( pos.pDelChain ) {
1418                 dispose_chain( pos.pDelChain );
1419                 pos.pDelChain = nullptr;
1420             }
1421
1422             // Delete deferred chain
1423             dispose_deferred();
1424         }
1425
1426         void dispose_deferred()
1427         {
1428             dispose_chain( m_pDeferredDelChain.exchange( nullptr, memory_model::memory_order_acq_rel ) );
1429         }
1430
1431         void defer_chain( position& pos )
1432         {
1433             if ( pos.pDelChain ) {
1434                 node_type * pHead = pos.pDelChain;
1435                 node_type * pTail = pHead;
1436                 while ( pTail->m_pDelChain )
1437                     pTail = pTail->m_pDelChain;
1438
1439                 node_type * pDeferList = m_pDeferredDelChain.load( memory_model::memory_order_relaxed );
1440                 do {
1441                     pTail->m_pDelChain = pDeferList;
1442                 } while ( !m_pDeferredDelChain.compare_exchange_weak( pDeferList, pHead, memory_model::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed ));
1443
1444                 pos.pDelChain = nullptr;
1445             }
1446         }
1447
1448         //@endcond
1449
1450     public:
1451         /// Default constructor
1452         SkipListSet()
1453             : m_Head( c_nMaxHeight )
1454             , m_nHeight( c_nMinHeight )
1455             , m_pDeferredDelChain( nullptr )
1456         {
1457             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
1458
1459             // Barrier for head node
1460             CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
1461         }
1462
1463         /// Clears and destructs the skip-list
1464         ~SkipListSet()
1465         {
1466             clear();
1467         }
1468
1469     public:
1470         /// Iterator type
1471         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
1472
1473         /// Const iterator type
1474         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
1475
1476         /// Returns a forward iterator addressing the first element in a set
1477         iterator begin()
1478         {
1479             return iterator( *m_Head.head() );
1480         }
1481
1482         /// Returns a forward const iterator addressing the first element in a set
1483         const_iterator begin() const
1484         {
1485             return const_iterator( *m_Head.head() );
1486         }
1487
1488         /// Returns a forward const iterator addressing the first element in a set
1489         const_iterator cbegin()
1490         {
1491             return const_iterator( *m_Head.head() );
1492         }
1493
1494         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
1495         iterator end()
1496         {
1497             return iterator();
1498         }
1499
1500         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1501         const_iterator end() const
1502         {
1503             return const_iterator();
1504         }
1505
1506         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
1507         const_iterator cend()
1508         {
1509             return const_iterator();
1510         }
1511
1512     public:
1513         /// Inserts new node
1514         /**
1515             The function inserts \p val in the set if it does not contain
1516             an item with key equal to \p val.
1517
1518             The function applies RCU lock internally.
1519
1520             Returns \p true if \p val is placed into the set, \p false otherwise.
1521         */
1522         bool insert( value_type& val )
1523         {
1524 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1525             return insert( val, []( value_type& ) {} );
1526 #       else
1527             return insert( val, empty_insert_functor() );
1528 #       endif
1529         }
1530
1531         /// Inserts new node
1532         /**
1533             This function is intended for derived non-intrusive containers.
1534
1535             The function allows to split creating of new item into two part:
1536             - create item with key only
1537             - insert new item into the set
1538             - if inserting is success, calls  \p f functor to initialize value-field of \p val.
1539
1540             The functor signature is:
1541             \code
1542                 void func( value_type& val );
1543             \endcode
1544             where \p val is the item inserted. User-defined functor \p f should guarantee that during changing
1545             \p val no any other changes could be made on this set's item by concurrent threads.
1546             The user-defined functor is called only if the inserting is success and may be passed by reference
1547             using <tt>boost::ref</tt>
1548
1549             RCU \p synchronize method can be called. RCU should not be locked.
1550         */
1551         template <typename Func>
1552         bool insert( value_type& val, Func f )
1553         {
1554             check_deadlock_policy::check();
1555
1556             position pos;
1557             bool bRet;
1558
1559             {
1560                 node_type * pNode = node_traits::to_node_ptr( val );
1561                 scoped_node_ptr scp( pNode );
1562                 unsigned int nHeight = pNode->height();
1563                 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1564                 bool bTowerMade = false;
1565
1566                 rcu_lock rcuLock;
1567
1568                 while ( true )
1569                 {
1570                     bool bFound = find_position( val, pos, key_comparator(), true );
1571                     if ( bFound ) {
1572                         // scoped_node_ptr deletes the node tower if we create it
1573                         if ( !bTowerMade )
1574                             scp.release();
1575
1576                         m_Stat.onInsertFailed();
1577                         bRet = false;
1578                         break;
1579                     }
1580
1581                     if ( !bTowerOk ) {
1582                         build_node( pNode );
1583                         nHeight = pNode->height();
1584                         bTowerMade =
1585                             bTowerOk = true;
1586                     }
1587
1588                     if ( !insert_at_position( val, pNode, pos, f )) {
1589                         m_Stat.onInsertRetry();
1590                         continue;
1591                     }
1592
1593                     increase_height( nHeight );
1594                     ++m_ItemCounter;
1595                     m_Stat.onAddNode( nHeight );
1596                     m_Stat.onInsertSuccess();
1597                     scp.release();
1598                     bRet =  true;
1599                     break;
1600                 }
1601             }
1602
1603             dispose_chain( pos );
1604
1605             return bRet;
1606         }
1607
1608         /// Ensures that the \p val exists in the set
1609         /**
1610             The operation performs inserting or changing data with lock-free manner.
1611
1612             If the item \p val is not found in the set, then \p val is inserted into the set.
1613             Otherwise, the functor \p func is called with item found.
1614             The functor signature is:
1615             \code
1616                 void func( bool bNew, value_type& item, value_type& val );
1617             \endcode
1618             with arguments:
1619             - \p bNew - \p true if the item has been inserted, \p false otherwise
1620             - \p item - item of the set
1621             - \p val - argument \p val passed into the \p ensure function
1622             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
1623             refer to the same thing.
1624
1625             The functor can change non-key fields of the \p item; however, \p func must guarantee
1626             that during changing no any other modifications could be made on this item by concurrent threads.
1627
1628             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1629
1630             RCU \p synchronize method can be called. RCU should not be locked.
1631
1632             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
1633             \p second is \p true if new item has been added or \p false if the item with \p key
1634             already is in the set.
1635         */
1636         template <typename Func>
1637         std::pair<bool, bool> ensure( value_type& val, Func func )
1638         {
1639             check_deadlock_policy::check();
1640
1641             position pos;
1642             std::pair<bool, bool> bRet( true, false );
1643
1644             {
1645                 node_type * pNode = node_traits::to_node_ptr( val );
1646                 scoped_node_ptr scp( pNode );
1647                 unsigned int nHeight = pNode->height();
1648                 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
1649                 bool bTowerMade = false;
1650
1651 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
1652                 insert_at_ensure_functor<Func> wrapper( func );
1653 #       endif
1654
1655                 rcu_lock rcuLock;
1656                 while ( true )
1657                 {
1658                     bool bFound = find_position( val, pos, key_comparator(), true );
1659                     if ( bFound ) {
1660                         // scoped_node_ptr deletes the node tower if we create it before
1661                         if ( !bTowerMade )
1662                             scp.release();
1663
1664                         cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
1665                         m_Stat.onEnsureExist();
1666                         break;
1667                     }
1668
1669                     if ( !bTowerOk ) {
1670                         build_node( pNode );
1671                         nHeight = pNode->height();
1672                         bTowerMade =
1673                             bTowerOk = true;
1674                     }
1675
1676 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1677                     if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
1678 #       else
1679                     if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
1680 #       endif
1681                     {
1682                         m_Stat.onInsertRetry();
1683                         continue;
1684                     }
1685
1686                     increase_height( nHeight );
1687                     ++m_ItemCounter;
1688                     scp.release();
1689                     m_Stat.onAddNode( nHeight );
1690                     m_Stat.onEnsureNew();
1691                     bRet.second = true;
1692                     break;
1693                 }
1694             }
1695
1696             dispose_chain( pos );
1697
1698             return bRet;
1699         }
1700
1701         /// Unlinks the item \p val from the set
1702         /**
1703             The function searches the item \p val in the set and unlink it from the set
1704             if it is found and is equal to \p val.
1705
1706             Difference between \ref erase and \p unlink functions: \p erase finds <i>a key</i>
1707             and deletes the item found. \p unlink finds an item by key and deletes it
1708             only if \p val is an item of that set, i.e. the pointer to item found
1709             is equal to <tt> &val </tt>.
1710
1711             RCU \p synchronize method can be called. RCU should not be locked.
1712
1713             The \ref disposer specified in \p Traits class template parameter is called
1714             by garbage collector \p GC asynchronously.
1715
1716             The function returns \p true if success and \p false otherwise.
1717         */
1718         bool unlink( value_type& val )
1719         {
1720             check_deadlock_policy::check();
1721
1722             position pos;
1723             bool bRet;
1724
1725             {
1726                 rcu_lock rcuLock;
1727
1728                 if ( !find_position( val, pos, key_comparator(), false ) ) {
1729                     m_Stat.onUnlinkFailed();
1730                     bRet = false;
1731                 }
1732                 else {
1733                     node_type * pDel = pos.pCur;
1734                     assert( key_comparator()( *node_traits::to_value_ptr( pDel ), val ) == 0 );
1735
1736                     unsigned int nHeight = pDel->height();
1737
1738                     if ( node_traits::to_value_ptr( pDel ) == &val && try_remove_at( pDel, pos,
1739 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1740                         [](value_type const&) {}
1741 #       else
1742                         empty_erase_functor()
1743 #       endif
1744                         , false ))
1745                     {
1746                         --m_ItemCounter;
1747                         m_Stat.onRemoveNode( nHeight );
1748                         m_Stat.onUnlinkSuccess();
1749                         bRet = true;
1750                     }
1751                     else {
1752                         m_Stat.onUnlinkFailed();
1753                         bRet = false;
1754                     }
1755                 }
1756             }
1757
1758             dispose_chain( pos );
1759
1760             return bRet;
1761         }
1762
1763         /// Extracts the item from the set with specified \p key
1764         /** \anchor cds_intrusive_SkipListSet_rcu_extract
1765             The function searches an item with key equal to \p key in the set,
1766             unlinks it from the set, places it to \p result parameter, and returns \p true.
1767             If the item with key equal to \p key is not found the function returns \p false.
1768
1769             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1770
1771             RCU \p synchronize method can be called. RCU should NOT be locked.
1772             The function does not call the disposer for the item found.
1773             The disposer will be implicitly invoked when \p result object is destroyed or when
1774             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1775             @note Before reusing \p result object you should call its \p release() method.
1776             Example:
1777             \code
1778             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1779             skip_list theList;
1780             // ...
1781
1782             typename skip_list::exempt_ptr ep;
1783             if ( theList.extract( ep, 5 ) ) {
1784                 // Deal with ep
1785                 //...
1786
1787                 // Dispose returned item.
1788                 ep.release();
1789             }
1790             \endcode
1791         */
1792         template <typename Q>
1793         bool extract( exempt_ptr& result, Q const& key )
1794         {
1795             return do_extract( result, key );
1796         }
1797
1798         /// Extracts the item from the set with comparing functor \p pred
1799         /**
1800             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_extract "extract(exempt_ptr&, Q const&)"
1801             but \p pred predicate is used for key comparing.
1802             \p Less has the interface like \p std::less.
1803             \p pred must imply the same element order as the comparator used for building the set.
1804         */
1805         template <typename Q, typename Less>
1806         bool extract_with( exempt_ptr& result, Q const& key, Less pred )
1807         {
1808             return do_extract_with( result, key, pred );
1809         }
1810
1811         /// Extracts an item with minimal key from the list
1812         /**
1813             The function searches an item with minimal key, unlinks it, and returns the item found in \p result parameter.
1814             If the skip-list is empty the function returns \p false.
1815
1816             RCU \p synchronize method can be called. RCU should NOT be locked.
1817             The function does not call the disposer for the item found.
1818             The disposer will be implicitly invoked when \p result object is destroyed or when
1819             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1820             @note Before reusing \p result object you should call its \p release() method.
1821             Example:
1822             \code
1823             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1824             skip_list theList;
1825             // ...
1826
1827             typename skip_list::exempt_ptr ep;
1828             if ( theList.extract_min(ep)) {
1829                 // Deal with ep
1830                 //...
1831
1832                 // Dispose returned item.
1833                 ep.release();
1834             }
1835             \endcode
1836
1837             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> minimum key.
1838             It means that the function gets leftmost item and tries to unlink it.
1839             During unlinking, a concurrent thread may insert an item with key less than leftmost item's key.
1840             So, the function returns the item with minimum key at the moment of list traversing.
1841         */
1842         bool extract_min( exempt_ptr& result )
1843         {
1844             return do_extract_min( result );
1845         }
1846
1847         /// Extracts an item with maximal key from the list
1848         /**
1849             The function searches an item with maximal key, unlinks it, and returns the item found in \p result parameter.
1850             If the skip-list is empty the function returns \p false.
1851
1852             RCU \p synchronize method can be called. RCU should NOT be locked.
1853             The function does not call the disposer for the item found.
1854             The disposer will be implicitly invoked when \p result object is destroyed or when
1855             <tt>result.release()</tt> is called, see cds::urcu::exempt_ptr for explanation.
1856             @note Before reusing \p result object you should call its \p release() method.
1857             Example:
1858             \code
1859             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
1860             skip_list theList;
1861             // ...
1862
1863             typename skip_list::exempt_ptr ep;
1864             if ( theList.extract_max(ep) ) {
1865                 // Deal with ep
1866                 //...
1867                 // Dispose returned item.
1868                 ep.release();
1869             }
1870             \endcode
1871
1872             @note Due the concurrent nature of the list, the function extracts <i>nearly</i> maximal key.
1873             It means that the function gets rightmost item and tries to unlink it.
1874             During unlinking, a concurrent thread can insert an item with key greater than rightmost item's key.
1875             So, the function returns the item with maximum key at the moment of list traversing.
1876         */
1877         bool extract_max( exempt_ptr& result )
1878         {
1879             return do_extract_max( result );
1880         }
1881
1882         /// Deletes the item from the set
1883         /** \anchor cds_intrusive_SkipListSet_rcu_erase
1884             The function searches an item with key equal to \p val in the set,
1885             unlinks it from the set, and returns \p true.
1886             If the item with key equal to \p val is not found the function return \p false.
1887
1888             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1889
1890             RCU \p synchronize method can be called. RCU should not be locked.
1891         */
1892         template <typename Q>
1893         bool erase( const Q& val )
1894         {
1895 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1896             return do_erase( val, key_comparator(), [](value_type const&) {} );
1897 #       else
1898             return do_erase( val, key_comparator(), empty_erase_functor() );
1899 #       endif
1900         }
1901
1902         /// Delete the item from the set with comparing functor \p pred
1903         /**
1904             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase "erase(Q const&)"
1905             but \p pred predicate is used for key comparing.
1906             \p Less has the interface like \p std::less.
1907             \p pred must imply the same element order as the comparator used for building the set.
1908         */
1909         template <typename Q, typename Less>
1910         bool erase_with( const Q& val, Less pred )
1911         {
1912 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
1913             return do_erase( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type const&) {} );
1914 #       else
1915             return do_erase( val, cds::opt::details::make_comparator_from_less<Less>(), empty_erase_functor() );
1916 #       endif
1917         }
1918
1919         /// Deletes the item from the set
1920         /** \anchor cds_intrusive_SkipListSet_rcu_erase_func
1921             The function searches an item with key equal to \p val in the set,
1922             call \p f functor with item found, unlinks it from the set, and returns \p true.
1923             The \ref disposer specified in \p Traits class template parameter is called
1924             by garbage collector \p GC asynchronously.
1925
1926             The \p Func interface is
1927             \code
1928             struct functor {
1929                 void operator()( value_type const& item );
1930             };
1931             \endcode
1932             The functor can be passed by reference with <tt>boost:ref</tt>
1933
1934             If the item with key equal to \p val is not found the function return \p false.
1935
1936             Note the hash functor should accept a parameter of type \p Q that can be not the same as \p value_type.
1937
1938             RCU \p synchronize method can be called. RCU should not be locked.
1939         */
1940         template <typename Q, typename Func>
1941         bool erase( Q const& val, Func f )
1942         {
1943             return do_erase( val, key_comparator(), f );
1944         }
1945
1946         /// Delete the item from the set with comparing functor \p pred
1947         /**
1948             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_erase_func "erase(Q const&, Func)"
1949             but \p pred predicate is used for key comparing.
1950             \p Less has the interface like \p std::less.
1951             \p pred must imply the same element order as the comparator used for building the set.
1952         */
1953         template <typename Q, typename Less, typename Func>
1954         bool erase_with( Q const& val, Less pred, Func f )
1955         {
1956             return do_erase( val, cds::opt::details::make_comparator_from_less<Less>(), f );
1957         }
1958
1959         /// Finds the key \p val
1960         /** @anchor cds_intrusive_SkipListSet_rcu_find_func
1961             The function searches the item with key equal to \p val and calls the functor \p f for item found.
1962             The interface of \p Func functor is:
1963             \code
1964             struct functor {
1965                 void operator()( value_type& item, Q& val );
1966             };
1967             \endcode
1968             where \p item is the item found, \p val is the <tt>find</tt> function argument.
1969
1970             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
1971
1972             The functor can change non-key fields of \p item. Note that the functor is only guarantee
1973             that \p item cannot be disposed during functor is executing.
1974             The functor does not serialize simultaneous access to the set \p item. If such access is
1975             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
1976
1977             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
1978             can modify both arguments.
1979
1980             The function applies RCU lock internally.
1981
1982             The function returns \p true if \p val is found, \p false otherwise.
1983         */
1984         template <typename Q, typename Func>
1985         bool find( Q& val, Func f )
1986         {
1987             return do_find_with( val, key_comparator(), f );
1988         }
1989
1990         /// Finds the key \p val with comparing functor \p pred
1991         /**
1992             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_find_func "find(Q&, Func)"
1993             but \p cmp is used for key comparison.
1994             \p Less functor has the interface like \p std::less.
1995             \p cmp must imply the same element order as the comparator used for building the set.
1996         */
1997         template <typename Q, typename Less, typename Func>
1998         bool find_with( Q& val, Less pred, Func f )
1999         {
2000             return do_find_with( val, cds::opt::details::make_comparator_from_less<Less>(), f );
2001         }
2002
2003         /// Finds the key \p val
2004         /** @anchor cds_intrusive_SkipListSet_rcu_find_cfunc
2005             The function searches the item with key equal to \p val and calls the functor \p f for item found.
2006             The interface of \p Func functor is:
2007             \code
2008             struct functor {
2009                 void operator()( value_type& item, Q const& val );
2010             };
2011             \endcode
2012             where \p item is the item found, \p val is the <tt>find</tt> function argument.
2013
2014             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
2015
2016             The functor can change non-key fields of \p item. Note that the functor is only guarantee
2017             that \p item cannot be disposed during functor is executing.
2018             The functor does not serialize simultaneous access to the set \p item. If such access is
2019             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
2020
2021             The function applies RCU lock internally.
2022
2023             The function returns \p true if \p val is found, \p false otherwise.
2024         */
2025         template <typename Q, typename Func>
2026         bool find( Q const& val, Func f )
2027         {
2028             return do_find_with( val, key_comparator(), f );
2029         }
2030
2031         /// Finds the key \p val with comparing functor \p pred
2032         /**
2033             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_find_cfunc "find(Q const&, Func)"
2034             but \p cmp is used for key comparison.
2035             \p Less functor has the interface like \p std::less.
2036             \p cmp must imply the same element order as the comparator used for building the set.
2037         */
2038         template <typename Q, typename Less, typename Func>
2039         bool find_with( Q const& val, Less pred, Func f )
2040         {
2041             return do_find_with( val, cds::opt::details::make_comparator_from_less<Less>(), f );
2042         }
2043
2044         /// Finds the key \p val
2045         /** @anchor cds_intrusive_SkipListSet_rcu_find_val
2046             The function searches the item with key equal to \p val
2047             and returns \p true if it is found, and \p false otherwise.
2048
2049             The function applies RCU lock internally.
2050         */
2051         template <typename Q>
2052         bool find( Q const& val )
2053         {
2054 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
2055             return do_find_with( val, key_comparator(), [](value_type& , Q const& ) {} );
2056 #       else
2057             return do_find_with( val, key_comparator(), empty_find_functor() );
2058 #       endif
2059         }
2060
2061         /// Finds the key \p val with comparing functor \p pred
2062         /**
2063             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_find_val "find(Q const&)"
2064             but \p pred is used for key compare.
2065             \p Less functor has the interface like \p std::less.
2066             \p pred must imply the same element order as the comparator used for building the set.
2067         */
2068         template <typename Q, typename Less>
2069         bool find_with( Q const& val, Less pred )
2070         {
2071             return do_find_with( val, cds::opt::details::make_comparator_from_less<Less>(),
2072 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
2073                 [](value_type& , Q const& ) {}
2074 #       else
2075                 empty_find_functor()
2076 #       endif
2077             );
2078         }
2079
2080         /// Finds the key \p val and return the item found
2081         /** \anchor cds_intrusive_SkipListSet_rcu_get
2082             The function searches the item with key equal to \p val and returns the pointer to item found.
2083             If \p val is not found it returns \p NULL.
2084
2085             Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type.
2086
2087             RCU should be locked before call of this function.
2088             Returned item is valid only while RCU is locked:
2089             \code
2090             typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list;
2091             skip_list theList;
2092             // ...
2093             {
2094                 // Lock RCU
2095                 skip_list::rcu_lock lock;
2096
2097                 foo * pVal = theList.get( 5 );
2098                 if ( pVal ) {
2099                     // Deal with pVal
2100                     //...
2101                 }
2102             }
2103             // Unlock RCU by rcu_lock destructor
2104             // pVal can be retired by disposer at any time after RCU has been unlocked
2105             \endcode
2106
2107             After RCU unlocking the \p %force_dispose member function can be called manually,
2108             see \ref force_dispose for explanation.
2109         */
2110         template <typename Q>
2111         value_type * get( Q const& val )
2112         {
2113             assert( gc::is_locked());
2114
2115 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
2116             value_type * pFound;
2117             return do_find_with( val, key_comparator(), [&pFound](value_type& found, Q const& ) { pFound = &found; } )
2118                 ? pFound : nullptr;
2119 #       else
2120             get_functor gf;
2121             return do_find_with( val, key_comparator(), cds::ref(gf) )
2122                 ? gf.pFound : nullptr;
2123 #       endif
2124         }
2125
2126         /// Finds the key \p val and return the item found
2127         /**
2128             The function is an analog of \ref cds_intrusive_SkipListSet_rcu_get "get(Q const&)"
2129             but \p pred is used for comparing the keys.
2130
2131             \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
2132             in any order.
2133             \p pred must imply the same element order as the comparator used for building the set.
2134         */
2135         template <typename Q, typename Less>
2136         value_type * get_with( Q const& val, Less pred )
2137         {
2138             assert( gc::is_locked());
2139
2140 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
2141             value_type * pFound;
2142             return do_find_with( val, cds::opt::details::make_comparator_from_less<Less>(),
2143                 [&pFound](value_type& found, Q const& ) { pFound = &found; } )
2144                 ? pFound : nullptr;
2145 #       else
2146             get_functor gf;
2147             return do_find_with( val, cds::opt::details::make_comparator_from_less<Less>(), cds::ref(gf) )
2148                 ? gf.pFound : nullptr;
2149 #       endif
2150         }
2151
2152         /// Returns item count in the set
2153         /**
2154             The value returned depends on item counter type provided by \p Traits template parameter.
2155             If it is atomicity::empty_item_counter this function always returns 0.
2156             Therefore, the function is not suitable for checking the set emptiness, use \ref empty
2157             member function for this purpose.
2158         */
2159         size_t size() const
2160         {
2161             return m_ItemCounter;
2162         }
2163
2164         /// Checks if the set is empty
2165         bool empty() const
2166         {
2167             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
2168         }
2169
2170         /// Clears the set (non-atomic)
2171         /**
2172             The function unlink all items from the set.
2173             The function is not atomic, thus, in multi-threaded environment with parallel insertions
2174             this sequence
2175             \code
2176             set.clear();
2177             assert( set.empty() );
2178             \endcode
2179             the assertion could be raised.
2180
2181             For each item the \ref disposer will be called automatically after unlinking.
2182         */
2183         void clear()
2184         {
2185             exempt_ptr ep;
2186             while ( extract_min(ep) )
2187                 ep.release();
2188         }
2189
2190         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
2191         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
2192         {
2193             return c_nMaxHeight;
2194         }
2195
2196         /// Returns const reference to internal statistics
2197         stat const& statistics() const
2198         {
2199             return m_Stat;
2200         }
2201
2202         /// Clears internal list of ready-to-remove items passing it to RCU reclamation cycle
2203         /** @anchor cds_intrusive_SkipListSet_rcu_force_dispose
2204             Skip list has complex multi-step algorithm for removing an item. In fact, when you
2205             remove the item it is just marked as removed that is enough for the success of your operation.
2206             Actual removing can take place in the future, in another call or even in another thread.
2207             Inside RCU lock the removed item cannot be passed to RCU reclamation cycle
2208             since it can lead to deadlock. To solve this problem, the current skip list implementation
2209             has internal list of items which is ready to remove but is not yet passed to RCU reclamation.
2210             Usually, this list will be passed to RCU reclamation in the next suitable call of skip list member function.
2211             In some cases we want to pass it to RCU reclamation immediately after RCU unlocking.
2212             This function provides such opportunity: it checks whether the RCU is not locked and if it is true
2213             the function passes the internal ready-to-remove list to RCU reclamation cycle.
2214
2215             The RCU \p synchronize can be called.
2216         */
2217         void force_dispose()
2218         {
2219             if ( !gc::is_locked() )
2220                 dispose_deferred();
2221         }
2222     };
2223
2224 }} // namespace cds::intrusive
2225
2226
2227 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_RCU_H