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-2017
   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         random_level_generator      m_RandomLevelGen; ///< random level generator instance
 449         atomics::atomic<unsigned int>    m_nHeight;   ///< estimated high level
 450         item_counter                m_ItemCounter;    ///< item counter
 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     ///@name Forward iterators
 612     //@{
 613         /// Forward iterator
 614         /**
 615             The forward iterator for a split-list has some features:
 616             - it has no post-increment operator
 617             - it depends on iterator of underlying \p OrderedList
 618         */
 619         typedef skip_list::details::iterator< gc, node_traits, back_off, false >  iterator;
 620
 621         /// Const iterator type
 622         typedef skip_list::details::iterator< gc, node_traits, back_off, true >   const_iterator;
 623
 624         /// Returns a forward iterator addressing the first element in a set
 625         iterator begin()
 626         {
 627             return iterator( *m_Head.head());
 628         }
 629
 630         /// Returns a forward const iterator addressing the first element in a set
 631         const_iterator begin() const
 632         {
 633             return const_iterator( *m_Head.head());
 634         }
 635         /// Returns a forward const iterator addressing the first element in a set
 636         const_iterator cbegin() const
 637         {
 638             return const_iterator( *m_Head.head());
 639         }
 640
 641         /// Returns a forward iterator that addresses the location succeeding the last element in a set.
 642         iterator end()
 643         {
 644             return iterator();
 645         }
 646
 647         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 648         const_iterator end() const
 649         {
 650             return const_iterator();
 651         }
 652         /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
 653         const_iterator cend() const
 654         {
 655             return const_iterator();
 656         }
 657     //@}
 658
 659     protected:
 660         //@cond
 661         iterator nonconst_end() const
 662         {
 663             return iterator();
 664         }
 665         //@endcond
 666
 667     public:
 668         /// Inserts new node
 669         /**
 670             The function inserts \p val in the set if it does not contain
 671             an item with key equal to \p val.
 672
 673             Returns \p true if \p val is placed into the set, \p false otherwise.
 674         */
 675         bool insert( value_type& val )
 676         {
 677             node_type * pNode = node_traits::to_node_ptr( val );
 678             scoped_node_ptr scp( pNode );
 679             unsigned int nHeight = pNode->height();
 680             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 681             bool bTowerMade = false;
 682
 683             position pos;
 684             while ( true )
 685             {
 686                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 687                 if ( bFound ) {
 688                     // scoped_node_ptr deletes the node tower if we create it
 689                     if ( !bTowerMade )
 690                         scp.release();
 691
 692                     m_Stat.onInsertFailed();
 693                     return false;
 694                 }
 695
 696                 if ( !bTowerOk ) {
 697                     build_node( pNode );
 698                     nHeight = pNode->height();
 699                     bTowerMade =
 700                         bTowerOk = true;
 701                 }
 702
 703                 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
 704                     m_Stat.onInsertRetry();
 705                     continue;
 706                 }
 707
 708                 increase_height( nHeight );
 709                 ++m_ItemCounter;
 710                 m_Stat.onAddNode( nHeight );
 711                 m_Stat.onInsertSuccess();
 712                 scp.release();
 713                 return true;
 714             }
 715         }
 716
 717         /// Updates the node
 718         /**
 719             The operation performs inserting or changing data with lock-free manner.
 720
 721             If the item \p val is not found in the set, then \p val is inserted into the set
 722             iff \p bInsert is \p true.
 723             Otherwise, the functor \p func is called with item found.
 724             The functor signature is:
 725             \code
 726                 void func( bool bNew, value_type& item, value_type& val );
 727             \endcode
 728             with arguments:
 729             - \p bNew - \p true if the item has been inserted, \p false otherwise
 730             - \p item - item of the set
 731             - \p val - argument \p val passed into the \p %update() function
 732             If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
 733             refer to the same thing.
 734
 735             The functor can change non-key fields of the \p item; however, \p func must guarantee
 736             that during changing no any other modifications could be made on this item by concurrent threads.
 737
 738             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
 739             \p second is \p true if new item has been added or \p false if the item with \p key
 740             already is in the set.
 741
 742             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
 743         */
 744         template <typename Func>
 745         std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
 746         {
 747             node_type * pNode = node_traits::to_node_ptr( val );
 748             scoped_node_ptr scp( pNode );
 749             unsigned int nHeight = pNode->height();
 750             bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
 751             bool bTowerMade = false;
 752
 753             position pos;
 754             while ( true )
 755             {
 756                 bool bFound = find_position( val, pos, key_comparator(), true, true );
 757                 if ( bFound ) {
 758                     // scoped_node_ptr deletes the node tower if we create it before
 759                     if ( !bTowerMade )
 760                         scp.release();
 761
 762                     func( false, *node_traits::to_value_ptr(pos.pCur), val );
 763                     m_Stat.onUpdateExist();
 764                     return std::make_pair( true, false );
 765                 }
 766
 767                 if ( !bInsert ) {
 768                     scp.release();
 769                     return std::make_pair( false, false );
 770                 }
 771
 772                 if ( !bTowerOk ) {
 773                     build_node( pNode );
 774                     nHeight = pNode->height();
 775                     bTowerMade =
 776                         bTowerOk = true;
 777                 }
 778
 779                 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
 780                     m_Stat.onInsertRetry();
 781                     continue;
 782                 }
 783
 784                 increase_height( nHeight );
 785                 ++m_ItemCounter;
 786                 scp.release();
 787                 m_Stat.onAddNode( nHeight );
 788                 m_Stat.onUpdateNew();
 789                 return std::make_pair( true, true );
 790             }
 791         }
 792         //@cond
 793         template <typename Func>
 794         CDS_DEPRECATED("ensure() is deprecated, use update()")
 795         std::pair<bool, bool> ensure( value_type& val, Func func )
 796         {
 797             return update( val, func, true );
 798         }
 799         //@endcond
 800
 801         /// Finds \p key
 802         /** \anchor cds_intrusive_SkipListSet_nogc_find_func
 803             The function searches the item with key equal to \p key and calls the functor \p f for item found.
 804             The interface of \p Func functor is:
 805             \code
 806             struct functor {
 807                 void operator()( value_type& item, Q& key );
 808             };
 809             \endcode
 810             where \p item is the item found, \p key is the <tt>find</tt> function argument.
 811
 812             The functor can change non-key fields of \p item. Note that the functor is only guarantee
 813             that \p item cannot be disposed during functor is executing.
 814             The functor does not serialize simultaneous access to the set \p item. If such access is
 815             possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
 816
 817             The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
 818             can modify both arguments.
 819
 820             Note the hash functor specified for class \p Traits template parameter
 821             should accept a parameter of type \p Q that can be not the same as \p value_type.
 822
 823             The function returns \p true if \p key is found, \p false otherwise.
 824         */
 825         template <typename Q, typename Func>
 826         bool find( Q& key, Func f ) const
 827         {
 828             return find_with_( key, key_comparator(), f ) != nullptr;
 829         }
 830         //@cond
 831         template <typename Q, typename Func>
 832         bool find( Q const& key, Func f ) const
 833         {
 834             return find_with_( key, key_comparator(), f ) != nullptr;
 835         }
 836         //@endcond
 837
 838         /// Finds the key \p key using \p pred predicate for comparing
 839         /**
 840             The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
 841             but \p pred predicate is used for key compare.
 842             \p Less has the interface like \p std::less.
 843             \p pred must imply the same element order as the comparator used for building the set.
 844         */
 845         template <typename Q, typename Less, typename Func>
 846         bool find_with( Q& key, Less pred, Func f ) const
 847         {
 848             CDS_UNUSED( pred );
 849             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 850         }
 851         //@cond
 852         template <typename Q, typename Less, typename Func>
 853         bool find_with( Q const& key, Less pred, Func f ) const
 854         {
 855             CDS_UNUSED( pred );
 856             return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
 857         }
 858         //@endcond
 859
 860         /// Checks whether the set contains \p key
 861         /**
 862             The function searches the item with key equal to \p key
 863             and returns pointer to item found or \p nullptr.
 864         */
 865         template <typename Q>
 866         value_type * contains( Q const& key ) const
 867         {
 868             node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
 869             if ( pNode )
 870                 return node_traits::to_value_ptr( pNode );
 871             return nullptr;
 872         }
 873         //@cond
 874         template <typename Q>
 875         CDS_DEPRECATED("deprecated, use contains()")
 876         value_type * find( Q const& key ) const
 877         {
 878             return contains( key );
 879         }
 880         //@endcond
 881
 882         /// Checks whether the set contains \p key using \p pred predicate for searching
 883         /**
 884             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 885             \p Less functor has the interface like \p std::less.
 886             \p Less must imply the same element order as the comparator used for building the set.
 887         */
 888         template <typename Q, typename Less>
 889         value_type * contains( Q const& key, Less pred ) const
 890         {
 891             CDS_UNUSED( pred );
 892             node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
 893             if ( pNode )
 894                 return node_traits::to_value_ptr( pNode );
 895             return nullptr;
 896         }
 897         //@cond
 898         template <typename Q, typename Less>
 899         CDS_DEPRECATED("deprecated, use contains()")
 900         value_type * find_with( Q const& key, Less pred ) const
 901         {
 902             return contains( key, pred );
 903         }
 904         //@endcond
 905
 906         /// Gets minimum key from the set
 907         /**
 908             If the set is empty the function returns \p nullptr
 909         */
 910         value_type * get_min() const
 911         {
 912             return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
 913         }
 914
 915         /// Gets maximum key from the set
 916         /**
 917             The function returns \p nullptr if the set is empty
 918         */
 919         value_type * get_max() const
 920         {
 921             node_type * pPred;
 922
 923             unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
 924             pPred = m_Head.head();
 925
 926             for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
 927                 while ( true ) {
 928                     node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
 929
 930                     if ( !pCur ) {
 931                         // end of the list at level nLevel - goto next level
 932                         break;
 933                     }
 934                     pPred = pCur;
 935                 }
 936             }
 937             return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
 938         }
 939
 940         /// Clears the set (non-atomic)
 941         /**
 942             The function is not atomic.
 943             Finding and/or inserting is prohibited while clearing.
 944             Otherwise an unpredictable result may be encountered.
 945             Thus, \p clear() may be used only for debugging purposes.
 946         */
 947         void clear()
 948         {
 949             node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
 950             m_Head.clear();
 951             m_ItemCounter.reset();
 952             m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
 953
 954             while ( pNode ) {
 955                 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
 956                 dispose_node( pNode );
 957                 pNode = pNext;
 958             }
 959         }
 960
 961         /// Returns item count in the set
 962         /**
 963             The value returned depends on item counter type provided by \p Traits template parameter.
 964             For \p atomicity::empty_item_counter the function always returns 0.
 965             The function is not suitable for checking the set emptiness, use \p empty().
 966         */
 967         size_t size() const
 968         {
 969             return m_ItemCounter;
 970         }
 971
 972         /// Checks if the set is empty
 973         bool empty() const
 974         {
 975             return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
 976         }
 977
 978         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 979         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 980         {
 981             return c_nMaxHeight;
 982         }
 983
 984         /// Returns const reference to internal statistics
 985         stat const& statistics() const
 986         {
 987             return m_Stat;
 988         }
 989     };
 990
 991 }} // namespace cds::intrusive
 992
 993
 994 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H