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 <cds/gc/nogc.h>
   7 #include <cds/intrusive/skip_list_base.h>
   8 #include <cds/details/std/type_traits.h>
   9 #include <cds/details/std/memory.h>
  10 #include <cds/opt/compare.h>
  11 #include <cds/ref.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 CDS_ATOMIC::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 NULL
  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, CDS_ATOMIC::memory_order_release );
 107             }
 108
 109             bool is_cleared() const
 110             {
 111                 return m_pNext.load( CDS_ATOMIC::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( CDS_ATOMIC::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( CDS_ATOMIC::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 NULL 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 #   ifndef CDS_CXX11_LAMBDA_SUPPORT
 414         struct empty_insert_functor {
 415             void operator()( value_type& )
 416             {}
 417         };
 418
 419         struct empty_find_functor {
 420             template <typename Q>
 421             void operator()( value_type& item, Q& val )
 422             {}
 423         };
 424
 425         template <typename Func>
 426         struct insert_at_ensure_functor {
 427             Func m_func;
 428             insert_at_ensure_functor( Func f ) : m_func(f) {}
 429
 430             void operator()( value_type& item )
 431             {
 432                 cds::unref( m_func)( true, item, item );
 433             }
 434         };
 435
 436 #   endif // ifndef CDS_CXX11_LAMBDA_SUPPORT
 437
 438         class head_node: public node_type
 439         {
 440             typename node_type::atomic_ptr   m_Tower[c_nMaxHeight];
 441
 442         public:
 443             head_node( unsigned int nHeight )
 444             {
 445                 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 446                     m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
 447
 448                 node_type::make_tower( nHeight, m_Tower );
 449             }
 450
 451             node_type * head() const
 452             {
 453                 return const_cast<node_type *>( static_cast<node_type const *>(this));
 454             }
 455
 456             void clear()
 457             {
 458                 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 459                     m_Tower[i].store( nullptr, CDS_ATOMIC::memory_order_relaxed );
 460                 node_type::m_pNext.store( nullptr, CDS_ATOMIC::memory_order_relaxed );
 461             }
 462         };
 463         //@endcond
 464
 465     protected:
 466         head_node                   m_Head  ;   ///< head tower (max height)
 467
 468         item_counter                m_ItemCounter       ;   ///< item counter
 469         random_level_generator      m_RandomLevelGen    ;   ///< random level generator instance
 470         CDS_ATOMIC::atomic<unsigned int>    m_nHeight   ;   ///< estimated high level
 471         mutable stat                m_Stat              ;   ///< internal statistics
 472
 473     protected:
 474         //@cond
 475         unsigned int random_level()
 476         {
 477             // Random generator produces a number from range [0..31]
 478             // We need a number from range [1..32]
 479             return m_RandomLevelGen() + 1;
 480         }
 481
 482         template <typename Q>
 483         node_type * build_node( Q v )
 484         {
 485             return node_builder::make_tower( v, m_RandomLevelGen );
 486         }
 487
 488         static void dispose_node( node_type * pNode )
 489         {
 490             assert( pNode != nullptr );
 491             typename node_builder::node_disposer()( pNode );
 492             disposer()( node_traits::to_value_ptr( pNode ));
 493         }
 494
 495         template <typename Q, typename Compare >
 496         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
 497         {
 498             node_type * pPred;
 499             node_type * pSucc;
 500             node_type * pCur = nullptr;
 501
 502             int nCmp = 1;
 503
 504             unsigned int nHeight = c_nMaxHeight;
 505         retry:
 506             if ( !bStrictSearch )
 507                 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
 508             pPred = m_Head.head();
 509
 510             for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
 511                 while ( true ) {
 512                     pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 513
 514                     if ( !pCur ) {
 515                         // end of the list at level nLevel - goto next level
 516                         break;
 517                     }
 518
 519                     pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
 520
 521                     if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
 522                         || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
 523                     {
 524                         goto retry;
 525                     }
 526
 527                     nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
 528                     if ( nCmp < 0 )
 529                         pPred = pCur;
 530                     else if ( nCmp == 0 && bStopIfFound )
 531                         goto found;
 532                     else
 533                         break;
 534                 }
 535
 536                 pos.pPrev[ nLevel ] = pPred;
 537                 pos.pSucc[ nLevel ] = pCur;
 538             }
 539
 540             if ( nCmp != 0 )
 541                 return false;
 542
 543         found:
 544             pos.pCur = pCur;
 545             return pCur && nCmp == 0;
 546         }
 547
 548         template <typename Func>
 549         bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
 550         {
 551             unsigned int nHeight = pNode->height();
 552
 553             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
 554                 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
 555
 556             {
 557                 node_type * p = pos.pSucc[0];
 558                 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
 559                 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
 560                     return false;
 561                 }
 562                 cds::unref( f )( val );
 563             }
 564
 565             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
 566                 node_type * p = nullptr;
 567                 while ( true ) {
 568                     node_type * q = pos.pSucc[ nLevel ];
 569
 570                     if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
 571                         p = q;
 572                         if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
 573                             break;
 574                     }
 575
 576                     // Renew insert position
 577                     find_position( val, pos, key_comparator(), false, true );
 578                 }
 579             }
 580             return true;
 581         }
 582
 583         template <typename Q, typename Compare, typename Func>
 584         node_type * find_with_( Q& val, Compare cmp, Func f ) const
 585         {
 586             position pos;
 587             if ( find_position( val, pos, cmp, true, false )) {
 588                 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
 589
 590                 cds::unref(f)( *node_traits::to_value_ptr( pos.pCur ), val );
 591
 592                 m_Stat.onFindFastSuccess();
 593                 return pos.pCur;
 594             }
 595             else {
 596                 m_Stat.onFindFastFailed();
 597                 return nullptr;
 598             }
 599         }
 600
 601         void increase_height( unsigned int nHeight )
 602         {
 603             unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
 604             while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed ) );
 605         }
 606         //@endcond
 607
 608     public:
 609         /// Default constructor
 610         /**
 611             The constructor checks whether the count of guards is enough
 612             for skip-list and may raise an exception if not.
 613         */
 614         SkipListSet()
 615             : m_Head( c_nMaxHeight )
 616             , m_nHeight( c_nMinHeight )
 617         {
 618             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
 619
 620             // Barrier for head node
 621             CDS_ATOMIC::atomic_thread_fence( memory_model::memory_order_release );
 622         }
 623
 624         /// Clears and destructs the skip-list
 625         ~SkipListSet()
 626         {
 627             clear();
 628         }
 629
 630     public:
 631         /// Iterator type
 632         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 633
 634         /// Const iterator type
 635         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 636
 637         /// Returns a forward iterator addressing the first element in a set
 638         iterator begin()
 639         {
 640             return iterator( *m_Head.head() );
 641         }
 642
 643         /// Returns a forward const iterator addressing the first element in a set
 644         //@{
 645         const_iterator begin() const
 646         {
 647             return const_iterator( *m_Head.head() );
 648         }
 649         const_iterator cbegin()
 650         {
 651             return const_iterator( *m_Head.head() );
 652         }
 653         //@}
 654
 655         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 656         iterator end()
 657         {
 658             return iterator();
 659         }
 660
 661         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 662         //@{
 663         const_iterator end() const
 664         {
 665             return const_iterator();
 666         }
 667         const_iterator cend()
 668         {
 669             return const_iterator();
 670         }
 671         //@}
 672
 673     protected:
 674         //@cond
 675         iterator nonconst_end() const
 676         {
 677             return iterator();
 678         }
 679         //@endcond
 680
 681     public:
 682         /// Inserts new node
 683         /**
 684             The function inserts \p val in the set if it does not contain
 685             an item with key equal to \p val.
 686
 687             Returns \p true if \p val is placed into the set, \p false otherwise.
 688         */
 689         bool insert( value_type& val )
 690         {
 691             node_type * pNode = node_traits::to_node_ptr( val );
 692             scoped_node_ptr scp( pNode );
 693             unsigned int nHeight = pNode->height();
 694             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 695             bool bTowerMade = false;
 696
 697             position pos;
 698             while ( true )
 699             {
 700                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 701                 if ( bFound ) {
 702                     // scoped_node_ptr deletes the node tower if we create it
 703                     if ( !bTowerMade )
 704                         scp.release();
 705
 706                     m_Stat.onInsertFailed();
 707                     return false;
 708                 }
 709
 710                 if ( !bTowerOk ) {
 711                     build_node( pNode );
 712                     nHeight = pNode->height();
 713                     bTowerMade =
 714                         bTowerOk = true;
 715                 }
 716
 717 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
 718                 if ( !insert_at_position( val, pNode, pos, empty_insert_functor() ))
 719 #       else
 720                 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} ))
 721 #       endif
 722                 {
 723                     m_Stat.onInsertRetry();
 724                     continue;
 725                 }
 726
 727                 increase_height( nHeight );
 728                 ++m_ItemCounter;
 729                 m_Stat.onAddNode( nHeight );
 730                 m_Stat.onInsertSuccess();
 731                 scp.release();
 732                 return true;
 733             }
 734         }
 735
 736         /// Ensures that the \p val exists in the set
 737         /**
 738             The operation performs inserting or changing data with lock-free manner.
 739
 740             If the item \p val is not found in the set, then \p val is inserted into the set.
 741             Otherwise, the functor \p func is called with item found.
 742             The functor signature is:
 743             \code
 744                 void func( bool bNew, value_type& item, value_type& val );
 745             \endcode
 746             with arguments:
 747             - \p bNew - \p true if the item has been inserted, \p false otherwise
 748             - \p item - item of the set
 749             - \p val - argument \p val passed into the \p ensure function
 750             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 751             refer to the same thing.
 752
 753             The functor can change non-key fields of the \p item; however, \p func must guarantee
 754             that during changing no any other modifications could be made on this item by concurrent threads.
 755
 756             You can pass \p func argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 757
 758             Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
 759             \p second is \p true if new item has been added or \p false if the item with \p key
 760             already is in the set.
 761         */
 762         template <typename Func>
 763         std::pair<bool, bool> ensure( value_type& val, Func func )
 764         {
 765             node_type * pNode = node_traits::to_node_ptr( val );
 766             scoped_node_ptr scp( pNode );
 767             unsigned int nHeight = pNode->height();
 768             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 769             bool bTowerMade = false;
 770
 771 #       ifndef CDS_CXX11_LAMBDA_SUPPORT
 772             insert_at_ensure_functor<Func> wrapper( func );
 773 #       endif
 774
 775             position pos;
 776             while ( true )
 777             {
 778                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 779                 if ( bFound ) {
 780                     // scoped_node_ptr deletes the node tower if we create it before
 781                     if ( !bTowerMade )
 782                         scp.release();
 783
 784                     cds::unref(func)( false, *node_traits::to_value_ptr(pos.pCur), val );
 785                     m_Stat.onEnsureExist();
 786                     return std::make_pair( true, false );
 787                 }
 788
 789                 if ( !bTowerOk ) {
 790                     build_node( pNode );
 791                     nHeight = pNode->height();
 792                     bTowerMade =
 793                         bTowerOk = true;
 794                 }
 795
 796 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 797                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { cds::unref(func)( true, item, item ); }))
 798 #       else
 799                 if ( !insert_at_position( val, pNode, pos, cds::ref(wrapper) ))
 800 #       endif
 801                 {
 802                     m_Stat.onInsertRetry();
 803                     continue;
 804                 }
 805
 806                 increase_height( nHeight );
 807                 ++m_ItemCounter;
 808                 scp.release();
 809                 m_Stat.onAddNode( nHeight );
 810                 m_Stat.onEnsureNew();
 811                 return std::make_pair( true, true );
 812             }
 813         }
 814
 815         /// Finds the key \p val
 816         /** \anchor cds_intrusive_SkipListSet_nogc_find_func
 817             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 818             The interface of \p Func functor is:
 819             \code
 820             struct functor {
 821                 void operator()( value_type& item, Q& val );
 822             };
 823             \endcode
 824             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 825
 826             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 827
 828             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 829             that \p item cannot be disposed during functor is executing.
 830             The functor does not serialize simultaneous access to the set \p item. If such access is
 831             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 832
 833             The \p val argument is non-const since it can be used as \p f functor destination i.e., the functor
 834             can modify both arguments.
 835
 836             Note the hash functor specified for class \p Traits template parameter
 837             should accept a parameter of type \p Q that can be not the same as \p value_type.
 838
 839             The function returns \p true if \p val is found, \p false otherwise.
 840         */
 841         template <typename Q, typename Func>
 842         bool find( Q& val, Func f ) const
 843         {
 844             return find_with_( val, key_comparator(), f ) != nullptr;
 845         }
 846
 847         /// Finds the key \p val using \p pred predicate for comparing
 848         /**
 849             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
 850             but \p pred predicate is used for key compare.
 851             \p Less has the interface like \p std::less.
 852             \p pred must imply the same element order as the comparator used for building the set.
 853         */
 854         template <typename Q, typename Less, typename Func>
 855         bool find_with( Q& val, Less pred, Func f ) const
 856         {
 857             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 858         }
 859
 860         /// Finds the key \p val
 861         /** \anchor cds_intrusive_SkipListSet_nogc_find_cfunc
 862             The function searches the item with key equal to \p val and calls the functor \p f for item found.
 863             The interface of \p Func functor is:
 864             \code
 865             struct functor {
 866                 void operator()( value_type& item, Q const& val );
 867             };
 868             \endcode
 869             where \p item is the item found, \p val is the <tt>find</tt> function argument.
 870
 871             You can pass \p f argument by value or by reference using <tt>boost::ref</tt> or cds::ref.
 872
 873             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 874             that \p item cannot be disposed during functor is executing.
 875             The functor does not serialize simultaneous access to the set \p item. If such access is
 876             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 877
 878             Note the hash functor specified for class \p Traits template parameter
 879             should accept a parameter of type \p Q that can be not the same as \p value_type.
 880
 881             The function returns \p true if \p val is found, \p false otherwise.
 882         */
 883         template <typename Q, typename Func>
 884         bool find( Q const& val, Func f ) const
 885         {
 886             return find_with_( val, key_comparator(), f ) != nullptr;
 887         }
 888
 889         /// Finds the key \p val using \p pred predicate for comparing
 890         /**
 891             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_cfunc "find(Q const&, Func)"
 892             but \p pred predicate is used for key compare.
 893             \p Less has the interface like \p std::less.
 894             \p pred must imply the same element order as the comparator used for building the set.
 895         */
 896         template <typename Q, typename Less, typename Func>
 897         bool find_with( Q const& val, Less pred, Func f ) const
 898         {
 899             return find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 900         }
 901
 902         /// Finds the key \p val
 903         /** \anchor cds_intrusive_SkipListSet_nogc_find_val
 904             The function searches the item with key equal to \p val
 905             and returns \p true if it is found, and \p false otherwise.
 906
 907             Note the hash functor specified for class \p Traits template parameter
 908             should accept a parameter of type \p Q that can be not the same as \p value_type.
 909         */
 910         template <typename Q>
 911         value_type * find( Q const& val ) const
 912         {
 913             node_type * pNode =
 914 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 915                 find_with_( val, key_comparator(), [](value_type& , Q const& ) {} );
 916 #       else
 917                 find_with_( val, key_comparator(), empty_find_functor() );
 918 #       endif
 919             if ( pNode )
 920                 return node_traits::to_value_ptr( pNode );
 921             return nullptr;
 922         }
 923
 924         /// Finds the key \p val using \p pred predicate for comparing
 925         /**
 926             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
 927             but \p pred predicate is used for key compare.
 928             \p Less has the interface like \p std::less.
 929             \p pred must imply the same element order as the comparator used for building the set.
 930         */
 931         template <typename Q, typename Less>
 932         value_type * find_with( Q const& val, Less pred ) const
 933         {
 934             node_type * pNode =
 935 #       ifdef CDS_CXX11_LAMBDA_SUPPORT
 936                 find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
 937 #       else
 938                 find_with_( val, cds::opt::details::make_comparator_from_less<Less>(), empty_find_functor() );
 939 #       endif
 940             if ( pNode )
 941                 return node_traits::to_value_ptr( pNode );
 942             return nullptr;
 943         }
 944
 945         /// Gets minimum key from the set
 946         /**
 947             If the set is empty the function returns \p NULL
 948         */
 949         value_type * get_min() const
 950         {
 951             return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
 952         }
 953
 954         /// Gets maximum key from the set
 955         /**
 956             The function returns \p NULL if the set is empty
 957         */
 958         value_type * get_max() const
 959         {
 960             node_type * pPred;
 961
 962             unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
 963             pPred = m_Head.head();
 964
 965             for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
 966                 while ( true ) {
 967                     node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 968
 969                     if ( !pCur ) {
 970                         // end of the list at level nLevel - goto next level
 971                         break;
 972                     }
 973                     pPred = pCur;
 974                 }
 975             }
 976             return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
 977         }
 978
 979         /// Clears the set (non-atomic)
 980         /**
 981             The function is not atomic.
 982             Finding and/or inserting is prohibited while clearing.
 983             Otherwise an unpredictable result may be encountered.
 984             Thus, \p clear() may be used only for debugging purposes.
 985         */
 986         void clear()
 987         {
 988             node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
 989             m_Head.clear();
 990             m_ItemCounter.reset();
 991             m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
 992
 993             while ( pNode ) {
 994                 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
 995                 dispose_node( pNode );
 996                 pNode = pNext;
 997             }
 998         }
 999
1000         /// Returns item count in the set
1001         /**
1002             The value returned depends on item counter type provided by \p Traits template parameter.
1003             If it is atomicity::empty_item_counter this function always returns 0.
1004             The function is not suitable for checking the set emptiness, use \ref empty
1005             member function for this purpose.
1006         */
1007         size_t size() const
1008         {
1009             return m_ItemCounter;
1010         }
1011
1012         /// Checks if the set is empty
1013         bool empty() const
1014         {
1015             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
1016         }
1017
1018         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
1019         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
1020         {
1021             return c_nMaxHeight;
1022         }
1023
1024         /// Returns const reference to internal statistics
1025         stat const& statistics() const
1026         {
1027             return m_Stat;
1028         }
1029     };
1030
1031 }} // namespace cds::intrusive
1032
1033
1034 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_IMPL_H