cds/intrusive/skip_list_nogc.h

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