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