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