cds/intrusive/skip_list_nogc.h

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