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