cds/intrusive/skip_list_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
   4 #define __CDS_INTRUSIVE_SKIP_LIST_NOGC_H
   5
   6 #include <type_traits>
   7 #include <memory>
   8 #include <functional>   // ref
   9 #include <cds/gc/nogc.h>
  10 #include <cds/intrusive/details/skip_list_base.h>
  11 #include <cds/opt/compare.h>
  12 #include <cds/details/binary_functor_wrapper.h>
  13
  14 namespace cds { namespace intrusive {
  15
  16     //@cond
  17     namespace skip_list {
  18         template <typename Tag>
  19         class node< cds::gc::nogc, Tag >
  20         {
  21         public:
  22             typedef cds::gc::nogc   gc          ;   ///< Garbage collector
  23             typedef Tag             tag         ;   ///< tag
  24
  25             typedef atomics::atomic<node * > atomic_ptr;
  26             typedef atomic_ptr                  tower_item_type;
  27
  28         protected:
  29             atomic_ptr      m_pNext     ;   ///< Next item in bottom-list (list at level 0)
  30             unsigned int    m_nHeight   ;   ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
  31             atomic_ptr *    m_arrNext   ;   ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
  32
  33         public:
  34             /// Constructs a node of height 1 (a bottom-list node)
  35             node()
  36                 : m_pNext( nullptr )
  37                 , m_nHeight(1)
  38                 , m_arrNext( nullptr )
  39             {}
  40
  41             /// Constructs a node of height \p nHeight
  42             void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
  43             {
  44                 assert( nHeight > 0 );
  45                 assert( (nHeight == 1 && nextTower == nullptr)  // bottom-list node
  46                         || (nHeight > 1 && nextTower != nullptr)   // node at level of more than 0
  47                     );
  48
  49                 m_arrNext = nextTower;
  50                 m_nHeight = nHeight;
  51             }
  52
  53             atomic_ptr * release_tower()
  54             {
  55                 atomic_ptr * pTower = m_arrNext;
  56                 m_arrNext = nullptr;
  57                 m_nHeight = 1;
  58                 return pTower;
  59             }
  60
  61             atomic_ptr * get_tower() const
  62             {
  63                 return m_arrNext;
  64             }
  65
  66             /// Access to element of next pointer array
  67             atomic_ptr& next( unsigned int nLevel )
  68             {
  69                 assert( nLevel < height() );
  70                 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
  71
  72                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  73             }
  74
  75             /// Access to element of next pointer array (const version)
  76             atomic_ptr const& next( unsigned int nLevel ) const
  77             {
  78                 assert( nLevel < height() );
  79                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
  80
  81                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  82             }
  83
  84             /// Access to element of next pointer array (same as \ref next function)
  85             atomic_ptr& operator[]( unsigned int nLevel )
  86             {
  87                 return next( nLevel );
  88             }
  89
  90             /// Access to element of next pointer array (same as \ref next function)
  91             atomic_ptr const& operator[]( unsigned int nLevel ) const
  92             {
  93                 return next( nLevel );
  94             }
  95
  96             /// Height of the node
  97             unsigned int height() const
  98             {
  99                 return m_nHeight;
 100             }
 101
 102             /// Clears internal links
 103             void clear()
 104             {
 105                 assert( m_arrNext == nullptr );
 106                 m_pNext.store( nullptr, atomics::memory_order_release );
 107             }
 108
 109             bool is_cleared() const
 110             {
 111                 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
 112                     && m_arrNext == nullptr
 113                     && m_nHeight <= 1
 114 ;
 115             }
 116         };
 117     } // namespace skip_list
 118
 119     namespace skip_list { namespace details {
 120
 121         template <typename NodeTraits, typename BackOff, bool IsConst>
 122         class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
 123         {
 124         public:
 125             typedef cds::gc::nogc                       gc;
 126             typedef NodeTraits                          node_traits;
 127             typedef BackOff                             back_off;
 128             typedef typename node_traits::node_type     node_type;
 129             typedef typename node_traits::value_type    value_type;
 130             static bool const c_isConst = IsConst;
 131
 132             typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type   value_ref;
 133
 134         protected:
 135             typedef typename node_type::atomic_ptr   atomic_ptr;
 136             node_type *             m_pNode;
 137
 138         public: // for internal use only!!!
 139             iterator( node_type& refHead )
 140                 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
 141             {}
 142
 143             static iterator from_node( node_type * pNode )
 144             {
 145                 iterator it;
 146                 it.m_pNode = pNode;
 147                 return it;
 148             }
 149
 150         public:
 151             iterator()
 152                 : m_pNode( nullptr )
 153             {}
 154
 155             iterator( iterator const& s)
 156                 : m_pNode( s.m_pNode )
 157             {}
 158
 159             value_type * operator ->() const
 160             {
 161                 assert( m_pNode != nullptr );
 162                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 163
 164                 return node_traits::to_value_ptr( m_pNode );
 165             }
 166
 167             value_ref operator *() const
 168             {
 169                 assert( m_pNode != nullptr );
 170                 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
 171
 172                 return *node_traits::to_value_ptr( m_pNode );
 173             }
 174
 175             /// Pre-increment
 176             iterator& operator ++()
 177             {
 178                 if ( m_pNode )
 179                     m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
 180                 return *this;
 181             }
 182
 183             iterator& operator = (const iterator& src)
 184             {
 185                 m_pNode = src.m_pNode;
 186                 return *this;
 187             }
 188
 189             template <typename Bkoff, bool C>
 190             bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
 191             {
 192                 return m_pNode == i.m_pNode;
 193             }
 194             template <typename Bkoff, bool C>
 195             bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
 196             {
 197                 return !( *this == i );
 198             }
 199         };
 200     }}  // namespace skip_list::details
 201     //@endcond
 202
 203     /// Lock-free skip-list set (template specialization for gc::nogc)
 204     /** @ingroup cds_intrusive_map
 205         @anchor cds_intrusive_SkipListSet_nogc
 206
 207         This specialization is intended for so-called persistent usage when no item
 208         reclamation may be performed. The class does not support deleting of list item.
 209
 210         See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
 211
 212         <b>Template arguments</b> :
 213         - \p T - type to be stored in the set. The type must be based on skip_list::node (for skip_list::base_hook)
 214             or it must have a member of type skip_list::node (for skip_list::member_hook).
 215         - \p Traits - type traits. See skip_list::type_traits for explanation.
 216
 217         It is possible to declare option-based list with cds::intrusive::skip_list::make_traits metafunction istead of \p Traits template
 218         argument.
 219         Template argument list \p Options of cds::intrusive::skip_list::make_traits metafunction are:
 220         - opt::hook - hook used. Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
 221             If the option is not specified, <tt>skip_list::base_hook<></tt> and gc::HP is used.
 222         - opt::compare - key comparison functor. No default functor is provided.
 223             If the option is not specified, the opt::less is used.
 224         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 225         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
 226         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
 227             or opt::v::sequential_consistent (sequentially consisnent memory model).
 228         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
 229             user-provided one. See skip_list::random_level_generator option description for explanation.
 230             Default is \p %skip_list::turbo_pascal.
 231         - opt::allocator - although the skip-list is an intrusive container,
 232             an allocator should be provided to maintain variable randomly-calculated height of the node
 233             since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
 234             for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
 235         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
 236         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
 237         - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer.
 238             The disposer is used only in object destructor and in \ref clear function.
 239
 240         <b>Iterators</b>
 241
 242         The class supports a forward iterator (\ref iterator and \ref const_iterator).
 243         The iteration is ordered.
 244
 245         The iterator class supports the following minimalistic interface:
 246         \code
 247         struct iterator {
 248             // Default ctor
 249             iterator();
 250
 251             // Copy ctor
 252             iterator( iterator const& s);
 253
 254             value_type * operator ->() const;
 255             value_type& operator *() const;
 256
 257             // Pre-increment
 258             iterator& operator ++();
 259
 260             // Copy assignment
 261             iterator& operator = (const iterator& src);
 262
 263             bool operator ==(iterator const& i ) const;
 264             bool operator !=(iterator const& i ) const;
 265         };
 266         \endcode
 267         Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
 268
 269         <b>How to use</b>
 270
 271         You should incorporate skip_list::node into your struct \p T and provide
 272         appropriate skip_list::type_traits::hook in your \p Traits template parameters. Usually, for \p Traits you
 273         define a struct based on skip_list::type_traits.
 274
 275         Example for base hook:
 276         \code
 277         #include <cds/intrusive/skip_list_nogc.h>
 278
 279         // Data stored in skip list
 280         struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
 281         {
 282             // key field
 283             std::string     strKey;
 284
 285             // other data
 286             // ...
 287         };
 288
 289         // my_data compare functor
 290         struct my_data_cmp {
 291             int operator()( const my_data& d1, const my_data& d2 )
 292             {
 293                 return d1.strKey.compare( d2.strKey );
 294             }
 295
 296             int operator()( const my_data& d, const std::string& s )
 297             {
 298                 return d.strKey.compare(s);
 299             }
 300
 301             int operator()( const std::string& s, const my_data& d )
 302             {
 303                 return s.compare( d.strKey );
 304             }
 305         };
 306
 307
 308         // Declare type_traits
 309         struct my_traits: public cds::intrusive::skip_list::type_traits
 310         {
 311             typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > >   hook;
 312             typedef my_data_cmp compare;
 313         };
 314
 315         // Declare skip-list set type
 316         typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits >     traits_based_set;
 317         \endcode
 318
 319         Equivalent option-based code:
 320         \code
 321         // GC-related specialization
 322         #include <cds/intrusive/skip_list_nogc.h>
 323
 324         struct my_data {
 325             // see above
 326         };
 327         struct compare {
 328             // see above
 329         };
 330
 331         // Declare option-based skip-list set
 332         typedef cds::intrusive::SkipListSet< cds::gc::nogc
 333             ,my_data
 334             , typename cds::intrusive::skip_list::make_traits<
 335                 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
 336                 ,cds::intrusive::opt::compare< my_data_cmp >
 337             >::type
 338         > option_based_set;
 339
 340         \endcode
 341
 342     */
 343     template <
 344        typename T
 345 #ifdef CDS_DOXYGEN_INVOKED
 346        ,typename Traits = skip_list::type_traits
 347 #else
 348        ,typename Traits
 349 #endif
 350     >
 351     class SkipListSet< cds::gc::nogc, T, Traits >
 352     {
 353     public:
 354         typedef T       value_type      ;   ///< type of value stored in the skip-list
 355         typedef Traits  options         ;   ///< Traits template parameter
 356
 357         typedef typename options::hook      hook        ;   ///< hook type
 358         typedef typename hook::node_type    node_type   ;   ///< node type
 359
 360 #   ifdef CDS_DOXYGEN_INVOKED
 361         typedef implementation_defined key_comparator  ;    ///< key comparison functor based on opt::compare and opt::less option setter.
 362 #   else
 363         typedef typename opt::details::make_comparator< value_type, options >::type key_comparator;
 364 #   endif
 365         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
 366
 367         typedef cds::gc::nogc  gc          ;   ///< No garbage collector is used
 368         typedef typename options::item_counter  item_counter ;   ///< Item counting policy used
 369         typedef typename options::memory_model  memory_model;   ///< Memory ordering. See cds::opt::memory_model option
 370         typedef typename options::random_level_generator    random_level_generator  ;   ///< random level generator
 371         typedef typename options::allocator     allocator_type  ;   ///< allocator for maintaining array of next pointers of the node
 372         typedef typename options::back_off      back_off    ;   ///< Back-off trategy
 373         typedef typename options::stat          stat        ;   ///< internal statistics type
 374         typedef typename options::disposer      disposer    ;   ///< disposer used
 375
 376         /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
 377         /**
 378             The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
 379             but it should be no more than 32 (\ref skip_list::c_nHeightLimit).
 380         */
 381         static unsigned int const c_nMaxHeight = std::conditional<
 382             (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
 383             std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
 384             std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
 385         >::type::value;
 386
 387         //@cond
 388         static unsigned int const c_nMinHeight = 3;
 389         //@endcond
 390
 391     protected:
 392         typedef typename node_type::atomic_ptr   atomic_node_ptr ;   ///< Atomic node pointer
 393
 394     protected:
 395         //@cond
 396         typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
 397
 398         typedef typename std::conditional<
 399             std::is_same< typename options::internal_node_builder, cds::opt::none >::value
 400             ,intrusive_node_builder
 401             ,typename options::internal_node_builder
 402         >::type node_builder;
 403
 404         typedef std::unique_ptr< node_type, typename node_builder::node_disposer >    scoped_node_ptr;
 405
 406         struct position {
 407             node_type *   pPrev[ c_nMaxHeight ];
 408             node_type *   pSucc[ c_nMaxHeight ];
 409
 410             node_type *   pCur;
 411         };
 412
 413         class head_node: public node_type
 414         {
 415             typename node_type::atomic_ptr   m_Tower[c_nMaxHeight];
 416
 417         public:
 418             head_node( unsigned int nHeight )
 419             {
 420                 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 421                     m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
 422
 423                 node_type::make_tower( nHeight, m_Tower );
 424             }
 425
 426             node_type * head() const
 427             {
 428                 return const_cast<node_type *>( static_cast<node_type const *>(this));
 429             }
 430
 431             void clear()
 432             {
 433                 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 434                     m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
 435                 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
 436             }
 437         };
 438         //@endcond
 439
 440     protected:
 441         head_node                   m_Head  ;   ///< head tower (max height)
 442
 443         item_counter                m_ItemCounter       ;   ///< item counter
 444         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance
 445         atomics::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level
 446         mutable stat                m_Stat              ;   ///< internal statistics
 447
 448     protected:
 449         //@cond
 450         unsigned int random_level()
 451         {
 452             // Random generator produces a number from range [0..31]
 453             // We need a number from range [1..32]
 454             return m_RandomLevelGen() + 1;
 455         }
 456
 457         template <typename Q>
 458         node_type * build_node( Q v )
 459         {
 460             return node_builder::make_tower( v, m_RandomLevelGen );
 461         }
 462
 463         static void dispose_node( node_type * pNode )
 464         {
 465             assert( pNode != nullptr );
 466             typename node_builder::node_disposer()( pNode );
 467             disposer()( node_traits::to_value_ptr( pNode ));
 468         }
 469
 470         template <typename Q, typename Compare >
 471         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
 472         {
 473             node_type * pPred;
 474             node_type * pSucc;
 475             node_type * pCur = nullptr;
 476
 477             int nCmp = 1;
 478
 479             unsigned int nHeight = c_nMaxHeight;
 480         retry:
 481             if ( !bStrictSearch )
 482                 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
 483             pPred = m_Head.head();
 484
 485             for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
 486                 while ( true ) {
 487                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 488
 489                     if ( !pCur ) {
 490                         // end of the list at level nLevel - goto next level
 491                         break;
 492                     }
 493
 494                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 495
 496                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
 497                         || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
 498                     {
 499                         goto retry;
 500                     }
 501
 502                     nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
 503                     if ( nCmp < 0 )
 504                         pPred = pCur;
 505                     else if ( nCmp == 0 && bStopIfFound )
 506                         goto found;
 507                     else
 508                         break;
 509                 }
 510
 511                 pos.pPrev[ nLevel ] = pPred;
 512                 pos.pSucc[ nLevel ] = pCur;
 513             }
 514
 515             if ( nCmp != 0 )
 516                 return false;
 517
 518         found:
 519             pos.pCur = pCur;
 520             return pCur && nCmp == 0;
 521         }
 522
 523         template <typename Func>
 524         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 525         {
 526             unsigned int nHeight = pNode->height();
 527
 528             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
 529                 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
 530
 531             {
 532                 node_type * p = pos.pSucc[0];
 533                 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
 534                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
 535                     return false;
 536                 }
 537                 f( val );
 538             }
 539
 540             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 541                 node_type * p = nullptr;
 542                 while ( true ) {
 543                     node_type * q = pos.pSucc[ nLevel ];
 544
 545                     if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
 546                         p = q;
 547                         if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
 548                             break;
 549                     }
 550
 551                     // Renew insert position
 552                     find_position( val, pos, key_comparator(), false, true );
 553                 }
 554             }
 555             return true;
 556         }
 557
 558         template <typename Q, typename Compare, typename Func>
 559         node_type * find_with_( Q& val, Compare cmp, Func f ) const
 560         {
 561             position pos;
 562             if ( find_position( val, pos, cmp, true, false )) {
 563                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 564
 565                 f( *node_traits::to_value_ptr( pos.pCur ), val );
 566
 567                 m_Stat.onFindFastSuccess();
 568                 return pos.pCur;
 569             }
 570             else {
 571                 m_Stat.onFindFastFailed();
 572                 return nullptr;
 573             }
 574         }
 575
 576         void increase_height( unsigned int nHeight )
 577         {
 578             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
 579             while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
 580         }
 581         //@endcond
 582
 583     public:
 584         /// Default constructor
 585         /**
 586             The constructor checks whether the count of guards is enough
 587             for skip-list and may raise an exception if not.
 588         */
 589         SkipListSet()
 590             : m_Head( c_nMaxHeight )
 591             , m_nHeight( c_nMinHeight )
 592         {
 593             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 594
 595             // Barrier for head node
 596             atomics::atomic_thread_fence( memory_model::memory_order_release );
 597         }
 598
 599         /// Clears and destructs the skip-list
 600         ~SkipListSet()
 601         {
 602             clear();
 603         }
 604
 605     public:
 606         /// Iterator type
 607         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 608
 609         /// Const iterator type
 610         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 611
 612         /// Returns a forward iterator addressing the first element in a set
 613         iterator begin()
 614         {
 615             return iterator( *m_Head.head() );
 616         }
 617
 618         /// Returns a forward const iterator addressing the first element in a set
 619         //@{
 620         const_iterator begin() const
 621         {
 622             return const_iterator( *m_Head.head() );
 623         }
 624         const_iterator cbegin() const
 625         {
 626             return const_iterator( *m_Head.head() );
 627         }
 628         //@}
 629
 630         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 631         iterator end()
 632         {
 633             return iterator();
 634         }
 635
 636         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 637         //@{
 638         const_iterator end() const
 639         {
 640             return const_iterator();
 641         }
 642         const_iterator cend() const
 643         {
 644             return const_iterator();
 645         }
 646         //@}
 647
 648     protected:
 649         //@cond
 650         iterator nonconst_end() const
 651         {
 652             return iterator();
 653         }
 654         //@endcond
 655
 656     public:
 657         /// Inserts new node
 658         /**
 659             The function inserts \p val in the set if it does not contain
 660             an item with key equal to \p val.
 661
 662             Returns \p true if \p val is placed into the set, \p false otherwise.
 663         */
 664         bool insert( value_type& val )
 665         {
 666             node_type * pNode = node_traits::to_node_ptr( val );
 667             scoped_node_ptr scp( pNode );
 668             unsigned int nHeight = pNode->height();
 669             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 670             bool bTowerMade = false;
 671
 672             position pos;
 673             while ( true )
 674             {
 675                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 676                 if ( bFound ) {
 677                     // scoped_node_ptr deletes the node tower if we create it
 678                     if ( !bTowerMade )
 679                         scp.release();
 680
 681                     m_Stat.onInsertFailed();
 682                     return false;
 683                 }
 684
 685                 if ( !bTowerOk ) {
 686                     build_node( pNode );
 687                     nHeight = pNode->height();
 688                     bTowerMade =
 689                         bTowerOk = true;
 690                 }
 691
 692                 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
 693                     m_Stat.onInsertRetry();
 694                     continue;
 695                 }
 696
 697                 increase_height( nHeight );
 698                 ++m_ItemCounter;
 699                 m_Stat.onAddNode( nHeight );
 700                 m_Stat.onInsertSuccess();
 701                 scp.release();
 702                 return true;
 703             }
 704         }
 705
 706         /// Ensures that the \p val exists in the set
 707         /**
 708             The operation performs inserting or changing data with lock-free manner.
 709
 710             If the item \p val is not found in the set, then \p val is inserted into the set.
 711             Otherwise, the functor \p func is called with item found.
 712             The functor signature is:
 713             \code
 714                 void func( bool bNew, value_type& item, value_type& val );
 715             \endcode
 716             with arguments:
 717             - \p bNew - \p true if the item has been inserted, \p false otherwise
 718             - \p item - item of the set
 719             - \p val - argument \p val passed into the \p ensure function
 720             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 721             refer to the same thing.
 722
 723             The functor can change non-key fields of the \p item; however, \p func must guarantee
 724             that during changing no any other modifications could be made on this item by concurrent threads.
 725
 726             You can pass \p func argument by value or by reference using \p std::ref.
 727
 728             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 729             \p second is \p true if new item has been added or \p false if the item with \p key
 730             already is in the set.
 731         */
 732         template <typename Func>
 733         std::pair<bool, bool> ensure( value_type& val, Func func )
 734         {
 735             node_type * pNode = node_traits::to_node_ptr( val );
 736             scoped_node_ptr scp( pNode );
 737             unsigned int nHeight = pNode->height();
 738             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 739             bool bTowerMade = false;
 740
 741             position pos;
 742             while ( true )
 743             {
 744                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 745                 if ( bFound ) {
 746                     // scoped_node_ptr deletes the node tower if we create it before
 747                     if ( !bTowerMade )
 748                         scp.release();
 749
 750                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
 751                     m_Stat.onEnsureExist();
 752                     return std::make_pair( true, false );
 753                 }
 754
 755                 if ( !bTowerOk ) {
 756                     build_node( pNode );
 757                     nHeight = pNode->height();
 758                     bTowerMade =
 759                         bTowerOk = true;
 760                 }
 761
 762                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
 763                     m_Stat.onInsertRetry();
 764                     continue;
 765                 }
 766
 767                 increase_height( nHeight );
 768                 ++m_ItemCounter;
 769                 scp.release();
 770                 m_Stat.onAddNode( nHeight );
 771                 m_Stat.onEnsureNew();
 772                 return std::make_pair( true, true );
 773             }
 774         }
 775
 776         /// Finds the key \p val
 777         /** \anchor cds_intrusive_SkipListSet_nogc_find_func
 778             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 779             The interface of \p Func functor is:
 780             \code
 781             struct functor {
 782                 void operator()( value_type& item, Q& val );
 783             };
 784             \endcode
 785             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 786
 787             You can pass \p f argument by value or by reference using \p std::ref.
 788
 789             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 790             that \p item cannot be disposed during functor is executing.
 791             The functor does not serialize simultaneous access to the set \p item. If such access is
 792             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 793
 794             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 795             can modify both arguments.
 796
 797             Note the hash functor specified for class \p Traits template parameter
 798             should accept a parameter of type \p Q that can be not the same as \p value_type.
 799
 800             The function returns \p true if \p val is found, \p false otherwise.
 801         */
 802         template <typename Q, typename Func>
 803         bool find( Q& val, Func f ) const
 804         {
 805             return find_with_( val, key_comparator(), f ) != nullptr;
 806         }
 807
 808         /// Finds the key \p val using \p pred predicate for comparing
 809         /**
 810             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
 811             but \p pred predicate is used for key compare.
 812             \p Less has the interface like \p std::less.
 813             \p pred must imply the same element order as the comparator used for building the set.
 814         */
 815         template <typename Q, typename Less, typename Func>
 816         bool find_with( Q& val, Less pred, Func f ) const
 817         {
 818             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 819         }
 820
 821         /// Finds the key \p val
 822         /** \anchor cds_intrusive_SkipListSet_nogc_find_cfunc
 823             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 824             The interface of \p Func functor is:
 825             \code
 826             struct functor {
 827                 void operator()( value_type& item, Q const& val );
 828             };
 829             \endcode
 830             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 831
 832             You can pass \p f argument by value or by reference using \p std::ref.
 833
 834             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 835             that \p item cannot be disposed during functor is executing.
 836             The functor does not serialize simultaneous access to the set \p item. If such access is
 837             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 838
 839             Note the hash functor specified for class \p Traits template parameter
 840             should accept a parameter of type \p Q that can be not the same as \p value_type.
 841
 842             The function returns \p true if \p val is found, \p false otherwise.
 843         */
 844         template <typename Q, typename Func>
 845         bool find( Q const& val, Func f ) const
 846         {
 847             return find_with_( val, key_comparator(), f ) != nullptr;
 848         }
 849
 850         /// Finds the key \p val using \p pred predicate for comparing
 851         /**
 852             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_cfunc "find(Q const&, Func)"
 853             but \p pred predicate is used for key compare.
 854             \p Less has the interface like \p std::less.
 855             \p pred must imply the same element order as the comparator used for building the set.
 856         */
 857         template <typename Q, typename Less, typename Func>
 858         bool find_with( Q const& val, Less pred, Func f ) const
 859         {
 860             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 861         }
 862
 863         /// Finds the key \p val
 864         /** \anchor cds_intrusive_SkipListSet_nogc_find_val
 865             The function searches the item with key equal to \p val
 866             and returns \p true if it is found, and \p false otherwise.
 867
 868             Note the hash functor specified for class \p Traits template parameter
 869             should accept a parameter of type \p Q that can be not the same as \p value_type.
 870         */
 871         template <typename Q>
 872         value_type * find( Q const& val ) const
 873         {
 874             node_type * pNode = find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
 875             if ( pNode )
 876                 return node_traits::to_value_ptr( pNode );
 877             return nullptr;
 878         }
 879
 880         /// Finds the key \p val using \p pred predicate for comparing
 881         /**
 882             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
 883             but \p pred predicate is used for key compare.
 884             \p Less has the interface like \p std::less.
 885             \p pred must imply the same element order as the comparator used for building the set.
 886         */
 887         template <typename Q, typename Less>
 888         value_type * find_with( Q const& val, Less pred ) const
 889         {
 890             node_type * pNode = find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
 891             if ( pNode )
 892                 return node_traits::to_value_ptr( pNode );
 893             return nullptr;
 894         }
 895
 896         /// Gets minimum key from the set
 897         /**
 898             If the set is empty the function returns \p nullptr
 899         */
 900         value_type * get_min() const
 901         {
 902             return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
 903         }
 904
 905         /// Gets maximum key from the set
 906         /**
 907             The function returns \p nullptr if the set is empty
 908         */
 909         value_type * get_max() const
 910         {
 911             node_type * pPred;
 912
 913             unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
 914             pPred = m_Head.head();
 915
 916             for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
 917                 while ( true ) {
 918                     node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 919
 920                     if ( !pCur ) {
 921                         // end of the list at level nLevel - goto next level
 922                         break;
 923                     }
 924                     pPred = pCur;
 925                 }
 926             }
 927             return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
 928         }
 929
 930         /// Clears the set (non-atomic)
 931         /**
 932             The function is not atomic.
 933             Finding and/or inserting is prohibited while clearing.
 934             Otherwise an unpredictable result may be encountered.
 935             Thus, \p clear() may be used only for debugging purposes.
 936         */
 937         void clear()
 938         {
 939             node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
 940             m_Head.clear();
 941             m_ItemCounter.reset();
 942             m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
 943
 944             while ( pNode ) {
 945                 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
 946                 dispose_node( pNode );
 947                 pNode = pNext;
 948             }
 949         }
 950
 951         /// Returns item count in the set
 952         /**
 953             The value returned depends on item counter type provided by \p Traits template parameter.
 954             If it is atomicity::empty_item_counter this function always returns 0.
 955             The function is not suitable for checking the set emptiness, use \ref empty
 956             member function for this purpose.
 957         */
 958         size_t size() const
 959         {
 960             return m_ItemCounter;
 961         }
 962
 963         /// Checks if the set is empty
 964         bool empty() const
 965         {
 966             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
 967         }
 968
 969         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 970         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 971         {
 972             return c_nMaxHeight;
 973         }
 974
 975         /// Returns const reference to internal statistics
 976         stat const& statistics() const
 977         {
 978             return m_Stat;
 979         }
 980     };
 981
 982 }} // namespace cds::intrusive
 983
 984
 985 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H