cds/intrusive/skip_list_rcu.h

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