cds/intrusive/skip_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_INTRUSIVE_SKIP_LIST_BASE_H
   4 #define __CDS_INTRUSIVE_SKIP_LIST_BASE_H
   5
   6 #include <cds/intrusive/base.h>
   7 #include <cds/details/marked_ptr.h>
   8 #include <cds/bitop.h>
   9 #include <cds/os/timer.h>
  10 #include <cds/urcu/options.h>
  11
  12
  13 namespace cds { namespace intrusive {
  14     /// SkipListSet related definitions
  15     /** @ingroup cds_intrusive_helper
  16     */
  17     namespace skip_list {
  18
  19         /// The maximum possible height of any skip-list
  20         static unsigned int const c_nHeightLimit = 32;
  21
  22         /// Skip list node
  23         /**
  24             Template parameters:
  25             - GC - garbage collector
  26             - Tag - a tag used to distinguish between different implementation. An incomplete type may be used as a tag.
  27         */
  28         template <class GC, typename Tag = opt::none>
  29         class node {
  30         public:
  31             typedef GC      gc          ;   ///< Garbage collector
  32             typedef Tag     tag         ;   ///< tag
  33
  34             typedef cds::details::marked_ptr<node, 1>                       marked_ptr          ;   ///< marked pointer
  35             typedef typename gc::template atomic_marked_ptr< marked_ptr>    atomic_marked_ptr   ;   ///< atomic marked pointer specific for GC
  36             //@cond
  37             typedef atomic_marked_ptr tower_item_type;
  38             //@endcond
  39
  40         protected:
  41             atomic_marked_ptr       m_pNext     ;   ///< Next item in bottom-list (list at level 0)
  42             unsigned int            m_nHeight   ;   ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
  43             atomic_marked_ptr *     m_arrNext   ;   ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p NULL
  44
  45         public:
  46             /// Constructs a node of height 1 (a bottom-list node)
  47             node()
  48                 : m_pNext( nullptr )
  49                 , m_nHeight(1)
  50                 , m_arrNext( nullptr )
  51             {}
  52
  53             /// Constructs a node of height \p nHeight
  54             void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
  55             {
  56                 assert( nHeight > 0 );
  57                 assert( (nHeight == 1 && nextTower == nullptr)  // bottom-list node
  58                         || (nHeight > 1 && nextTower != nullptr)   // node at level of more than 0
  59                 );
  60
  61                 m_arrNext = nextTower;
  62                 m_nHeight = nHeight;
  63             }
  64
  65             //@cond
  66             atomic_marked_ptr * release_tower()
  67             {
  68                 atomic_marked_ptr * pTower = m_arrNext;
  69                 m_arrNext = nullptr;
  70                 m_nHeight = 1;
  71                 return pTower;
  72             }
  73
  74             atomic_marked_ptr * get_tower() const
  75             {
  76                 return m_arrNext;
  77             }
  78             //@endcond
  79
  80             /// Access to element of next pointer array
  81             atomic_marked_ptr& next( unsigned int nLevel )
  82             {
  83                 assert( nLevel < height() );
  84                 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
  85
  86                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  87             }
  88
  89             /// Access to element of next pointer array (const version)
  90             atomic_marked_ptr const& next( unsigned int nLevel ) const
  91             {
  92                 assert( nLevel < height() );
  93                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
  94
  95                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
  96             }
  97
  98             /// Access to element of next pointer array (same as \ref next function)
  99             atomic_marked_ptr& operator[]( unsigned int nLevel )
 100             {
 101                 return next( nLevel );
 102             }
 103
 104             /// Access to element of next pointer array (same as \ref next function)
 105             atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
 106             {
 107                 return next( nLevel );
 108             }
 109
 110             /// Height of the node
 111             unsigned int height() const
 112             {
 113                 return m_nHeight;
 114             }
 115
 116             /// Clears internal links
 117             void clear()
 118             {
 119                 assert( m_arrNext == nullptr );
 120                 m_pNext.store( marked_ptr(), CDS_ATOMIC::memory_order_release );
 121             }
 122
 123             //@cond
 124             bool is_cleared() const
 125             {
 126                 return m_pNext == atomic_marked_ptr()
 127                     && m_arrNext == nullptr
 128                     && m_nHeight <= 1
 129 ;
 130             }
 131             //@endcond
 132         };
 133
 134         //@cond
 135         struct undefined_gc;
 136         struct default_hook {
 137             typedef undefined_gc    gc;
 138             typedef opt::none       tag;
 139         };
 140         //@endcond
 141
 142         //@cond
 143         template < typename HookType, CDS_DECL_OPTIONS2>
 144         struct hook
 145         {
 146             typedef typename opt::make_options< default_hook, CDS_OPTIONS2>::type  options;
 147             typedef typename options::gc    gc;
 148             typedef typename options::tag   tag;
 149             typedef node<gc, tag>           node_type;
 150             typedef HookType                hook_type;
 151         };
 152         //@endcond
 153
 154         /// Base hook
 155         /**
 156             \p Options are:
 157             - opt::gc - garbage collector used.
 158             - opt::tag - a tag
 159         */
 160         template < CDS_DECL_OPTIONS2 >
 161         struct base_hook: public hook< opt::base_hook_tag, CDS_OPTIONS2 >
 162         {};
 163
 164         /// Member hook
 165         /**
 166             \p MemberOffset defines offset in bytes of \ref node member into your structure.
 167             Use \p offsetof macro to define \p MemberOffset
 168
 169             \p Options are:
 170             - opt::gc - garbage collector used.
 171             - opt::tag - a tag
 172         */
 173         template < size_t MemberOffset, CDS_DECL_OPTIONS2 >
 174         struct member_hook: public hook< opt::member_hook_tag, CDS_OPTIONS2 >
 175         {
 176             //@cond
 177             static const size_t c_nMemberOffset = MemberOffset;
 178             //@endcond
 179         };
 180
 181         /// Traits hook
 182         /**
 183             \p NodeTraits defines type traits for node.
 184             See \ref node_traits for \p NodeTraits interface description
 185
 186             \p Options are:
 187             - opt::gc - garbage collector used.
 188             - opt::tag - a tag
 189         */
 190         template <typename NodeTraits, CDS_DECL_OPTIONS2 >
 191         struct traits_hook: public hook< opt::traits_hook_tag, CDS_OPTIONS2 >
 192         {
 193             //@cond
 194             typedef NodeTraits node_traits;
 195             //@endcond
 196         };
 197
 198         /// Option specifying random level generator
 199         /**
 200             The random level generator is an important part of skip-list algorithm.
 201             The node height in the skip-list have a probabilistic distribution
 202             where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
 203             (i = 0..30).
 204             The random level generator should provide such distribution.
 205
 206             The \p Type functor interface is:
 207             \code
 208             struct random_generator {
 209                 static unsigned int const c_nUpperBound = 32;
 210                 random_generator();
 211                 unsigned int operator()();
 212             };
 213             \endcode
 214
 215             where
 216             - \p c_nUpperBound - constant that specifies the upper bound of random number generated.
 217                 The generator produces a number from range <tt>[0 .. c_nUpperBound)</tt> (upper bound excluded).
 218                 \p c_nUpperBound must be no more than 32.
 219             - <tt>random_generator()</tt> - the constructor of generator object initialises the generator instance (its internal state).
 220             - <tt>unsigned int operator()()</tt> - the main generating function. Returns random level from range 0..31.
 221
 222             Stateful generators are supported.
 223
 224             Available \p Type implementations:
 225             - \ref xorshift
 226             - \ref turbo_pascal
 227         */
 228         template <typename Type>
 229         struct random_level_generator {
 230             //@cond
 231             template <typename Base>
 232             struct pack: public Base
 233             {
 234                 typedef Type random_level_generator;
 235             };
 236             //@endcond
 237         };
 238
 239         /// Xor-shift random level generator
 240         /**
 241             The simplest of the generators described in George
 242             Marsaglia's "Xorshift RNGs" paper.  This is not a high-quality
 243             generator but is acceptable for skip-list.
 244
 245             The random generator should return numbers from range [0..31].
 246
 247             From Doug Lea's ConcurrentSkipListMap.java.
 248         */
 249         class xorshift {
 250             //@cond
 251             CDS_ATOMIC::atomic<unsigned int>    m_nSeed;
 252             //@endcond
 253         public:
 254             /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
 255             static unsigned int const c_nUpperBound = c_nHeightLimit;
 256
 257             /// Initializes the generator instance
 258             xorshift()
 259             {
 260                 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), CDS_ATOMIC::memory_order_relaxed );
 261             }
 262
 263             /// Main generator function
 264             unsigned int operator()()
 265             {
 266                 /* ConcurrentSkipListMap.java
 267                 private int randomLevel() {
 268                     int x = randomSeed;
 269                     x ^= x << 13;
 270                     x ^= x >>> 17;
 271                     randomSeed = x ^= x << 5;
 272                     if ((x & 0x80000001) != 0) // test highest and lowest bits
 273                         return 0;
 274                     int level = 1;
 275                     while (((x >>>= 1) & 1) != 0) ++level;
 276                     return level;
 277                 }
 278                 */
 279                 unsigned int x = m_nSeed.load( CDS_ATOMIC::memory_order_relaxed );
 280                 x ^= x << 13;
 281                 x ^= x >> 17;
 282                 x ^= x << 5;
 283                 m_nSeed.store( x, CDS_ATOMIC::memory_order_relaxed );
 284                 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & 0x7FFFFFFF );
 285                 assert( nLevel < c_nUpperBound );
 286                 return nLevel;
 287             }
 288         };
 289
 290         /// Turbo-pascal random level generator
 291         /**
 292             This uses a cheap pseudo-random function that was used in Turbo Pascal.
 293
 294             The random generator should return numbers from range [0..31].
 295
 296             From Doug Lea's ConcurrentSkipListMap.java.
 297         */
 298         class turbo_pascal
 299         {
 300             //@cond
 301             CDS_ATOMIC::atomic<unsigned int>    m_nSeed;
 302             //@endcond
 303         public:
 304             /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
 305             static unsigned int const c_nUpperBound = c_nHeightLimit;
 306
 307             /// Initializes the generator instance
 308             turbo_pascal()
 309             {
 310                 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), CDS_ATOMIC::memory_order_relaxed );
 311             }
 312
 313             /// Main generator function
 314             unsigned int operator()()
 315             {
 316                 /*
 317                 private int randomLevel() {
 318                     int level = 0;
 319                     int r = randomSeed;
 320                     randomSeed = r * 134775813 + 1;
 321                     if (r < 0) {
 322                         while ((r <<= 1) > 0)
 323                             ++level;
 324                     }
 325                 return level;
 326                 }
 327                 */
 328                 /*
 329                     The low bits are apparently not very random (the original used only
 330                     upper 16 bits) so we traverse from highest bit down (i.e., test
 331                     sign), thus hardly ever use lower bits.
 332                 */
 333                 unsigned int x = m_nSeed.load( CDS_ATOMIC::memory_order_relaxed ) * 134775813 + 1;
 334                 m_nSeed.store( x, CDS_ATOMIC::memory_order_relaxed );
 335                 unsigned int nLevel = ( x & 0x80000000 ) ? (31 - cds::bitop::MSBnz( (x & 0x7FFFFFFF) | 1 )) : 0;
 336                 assert( nLevel < c_nUpperBound );
 337                 return nLevel;
 338             }
 339         };
 340
 341         /// SkipListSet internal statistics
 342         template <typename EventCounter = cds::atomicity::event_counter>
 343         struct stat {
 344             typedef EventCounter event_counter ; ///< Event counter type
 345
 346             event_counter   m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
 347             event_counter   m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
 348             event_counter   m_nInsertSuccess        ; ///< Count of success insertion
 349             event_counter   m_nInsertFailed         ; ///< Count of failed insertion
 350             event_counter   m_nInsertRetries        ; ///< Count of unsuccessful retries of insertion
 351             event_counter   m_nEnsureExist          ; ///< Count of \p ensure call for existed node
 352             event_counter   m_nEnsureNew            ; ///< Count of \p ensure call for new node
 353             event_counter   m_nUnlinkSuccess        ; ///< Count of successful call of \p unlink
 354             event_counter   m_nUnlinkFailed         ; ///< Count of failed call of \p unlink
 355             event_counter   m_nEraseSuccess         ; ///< Count of successful call of \p erase
 356             event_counter   m_nEraseFailed          ; ///< Count of failed call of \p erase
 357             event_counter   m_nFindFastSuccess      ; ///< Count of successful call of \p find and all derivatives (via fast-path)
 358             event_counter   m_nFindFastFailed       ; ///< Count of failed call of \p find and all derivatives (via fast-path)
 359             event_counter   m_nFindSlowSuccess      ; ///< Count of successful call of \p find and all derivatives (via slow-path)
 360             event_counter   m_nFindSlowFailed       ; ///< Count of failed call of \p find and all derivatives (via slow-path)
 361             event_counter   m_nRenewInsertPosition  ; ///< Count of renewing position events while inserting
 362             event_counter   m_nLogicDeleteWhileInsert   ;   ///< Count of events "The node has been logically deleted while inserting"
 363             event_counter   m_nNotFoundWhileInsert  ; ///< Count of events "Inserting node is not found"
 364             event_counter   m_nFastErase            ; ///< Fast erase event counter
 365             event_counter   m_nFastExtract          ; ///< Fast extract event counter
 366             event_counter   m_nSlowErase            ; ///< Slow erase event counter
 367             event_counter   m_nSlowExtract          ; ///< Slow extract event counter
 368             event_counter   m_nExtractSuccess       ; ///< Count of successful call of \p extract
 369             event_counter   m_nExtractFailed        ; ///< Count of failed call of \p extract
 370             event_counter   m_nExtractRetries       ; ///< Count of retries of \p extract call
 371             event_counter   m_nExtractMinSuccess    ; ///< Count of successful call of \p extract_min
 372             event_counter   m_nExtractMinFailed     ; ///< Count of failed call of \p extract_min
 373             event_counter   m_nExtractMinRetries    ; ///< Count of retries of \p extract_min call
 374             event_counter   m_nExtractMaxSuccess    ; ///< Count of successful call of \p extract_max
 375             event_counter   m_nExtractMaxFailed     ; ///< Count of failed call of \p extract_max
 376             event_counter   m_nExtractMaxRetries    ; ///< Count of retries of \p extract_max call
 377             event_counter   m_nEraseWhileFind       ; ///< Count of erased item while searching
 378             event_counter   m_nExtractWhileFind     ; ///< Count of extracted item while searching (RCU only)
 379
 380             //@cond
 381             void onAddNode( unsigned int nHeight )
 382             {
 383                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
 384                 ++m_nNodeHeightAdd[nHeight - 1];
 385             }
 386             void onRemoveNode( unsigned int nHeight )
 387             {
 388                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
 389                 ++m_nNodeHeightDel[nHeight - 1];
 390             }
 391
 392             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 393             void onInsertFailed()           { ++m_nInsertFailed     ; }
 394             void onInsertRetry()            { ++m_nInsertRetries    ; }
 395             void onEnsureExist()            { ++m_nEnsureExist      ; }
 396             void onEnsureNew()              { ++m_nEnsureNew        ; }
 397             void onUnlinkSuccess()          { ++m_nUnlinkSuccess    ; }
 398             void onUnlinkFailed()           { ++m_nUnlinkFailed     ; }
 399             void onEraseSuccess()           { ++m_nEraseSuccess     ; }
 400             void onEraseFailed()            { ++m_nEraseFailed      ; }
 401             void onFindFastSuccess()        { ++m_nFindFastSuccess  ; }
 402             void onFindFastFailed()         { ++m_nFindFastFailed   ; }
 403             void onFindSlowSuccess()        { ++m_nFindSlowSuccess  ; }
 404             void onFindSlowFailed()         { ++m_nFindSlowFailed   ; }
 405             void onEraseWhileFind()         { ++m_nEraseWhileFind   ; }
 406             void onExtractWhileFind()       { ++m_nExtractWhileFind ; }
 407             void onRenewInsertPosition()    { ++m_nRenewInsertPosition; }
 408             void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
 409             void onNotFoundWhileInsert()    { ++m_nNotFoundWhileInsert; }
 410             void onFastErase()              { ++m_nFastErase;         }
 411             void onFastExtract()            { ++m_nFastExtract;       }
 412             void onSlowErase()              { ++m_nSlowErase;         }
 413             void onSlowExtract()            { ++m_nSlowExtract;       }
 414             void onExtractSuccess()         { ++m_nExtractSuccess;    }
 415             void onExtractFailed()          { ++m_nExtractFailed;     }
 416             void onExtractRetry()           { ++m_nExtractRetries;    }
 417             void onExtractMinSuccess()      { ++m_nExtractMinSuccess; }
 418             void onExtractMinFailed()       { ++m_nExtractMinFailed;  }
 419             void onExtractMinRetry()        { ++m_nExtractMinRetries; }
 420             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
 421             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
 422             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
 423
 424             //@endcond
 425         };
 426
 427         /// SkipListSet empty internal statistics
 428         struct empty_stat {
 429             //@cond
 430             void onAddNode( unsigned int nHeight ) const {}
 431             void onRemoveNode( unsigned int nHeight ) const {}
 432             void onInsertSuccess()          const {}
 433             void onInsertFailed()           const {}
 434             void onInsertRetry()            const {}
 435             void onEnsureExist()            const {}
 436             void onEnsureNew()              const {}
 437             void onUnlinkSuccess()          const {}
 438             void onUnlinkFailed()           const {}
 439             void onEraseSuccess()           const {}
 440             void onEraseFailed()            const {}
 441             void onFindFastSuccess()        const {}
 442             void onFindFastFailed()         const {}
 443             void onFindSlowSuccess()        const {}
 444             void onFindSlowFailed()         const {}
 445             void onEraseWhileFind()         const {}
 446             void onExtractWhileFind()       const {}
 447             void onRenewInsertPosition()    const {}
 448             void onLogicDeleteWhileInsert() const {}
 449             void onNotFoundWhileInsert()    const {}
 450             void onFastErase()              const {}
 451             void onFastExtract()            const {}
 452             void onSlowErase()              const {}
 453             void onSlowExtract()            const {}
 454             void onExtractSuccess()         const {}
 455             void onExtractFailed()          const {}
 456             void onExtractRetry()           const {}
 457             void onExtractMinSuccess()      const {}
 458             void onExtractMinFailed()       const {}
 459             void onExtractMinRetry()        const {}
 460             void onExtractMaxSuccess()      const {}
 461             void onExtractMaxFailed()       const {}
 462             void onExtractMaxRetry()        const {}
 463
 464             //@endcond
 465         };
 466
 467         //@cond
 468         // For internal use only!!!
 469         template <typename Type>
 470         struct internal_node_builder {
 471             template <typename Base>
 472             struct pack: public Base
 473             {
 474                 typedef Type internal_node_builder;
 475             };
 476         };
 477         //@endcond
 478
 479         /// Type traits for SkipListSet class
 480         struct type_traits
 481         {
 482             /// Hook used
 483             /**
 484                 Possible values are: skip_list::base_hook, skip_list::member_hook, skip_list::traits_hook.
 485             */
 486             typedef base_hook<>       hook;
 487
 488             /// Key comparison functor
 489             /**
 490                 No default functor is provided. If the option is not specified, the \p less is used.
 491             */
 492             typedef opt::none                       compare;
 493
 494             /// specifies binary predicate used for key compare.
 495             /**
 496                 Default is \p std::less<T>.
 497             */
 498             typedef opt::none                       less;
 499
 500             /// Disposer
 501             /**
 502                 The functor used for dispose removed items. Default is opt::v::empty_disposer.
 503             */
 504             typedef opt::v::empty_disposer          disposer;
 505
 506             /// Item counter
 507             /**
 508                 The type for item counting feature.
 509                 Default is no item counter (\ref atomicity::empty_item_counter)
 510             */
 511             typedef atomicity::empty_item_counter     item_counter;
 512
 513             /// C++ memory ordering model
 514             /**
 515                 List of available memory ordering see opt::memory_model
 516             */
 517             typedef opt::v::relaxed_ordering        memory_model;
 518
 519             /// Random level generator
 520             /**
 521                 The random level generator is an important part of skip-list algorithm.
 522                 The node height in the skip-list have a probabilistic distribution
 523                 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
 524                 (i = 0..30). So, the height of a node is in range [0..31].
 525
 526                 See skip_list::random_level_generator option setter.
 527             */
 528             typedef turbo_pascal                    random_level_generator;
 529
 530             /// Allocator
 531             /**
 532                 Although the skip-list is an intrusive container,
 533                 an allocator should be provided to maintain variable randomly-calculated height of the node
 534                 since the node can contain up to 32 next pointers.
 535                 The allocator specified is used to allocate an array of next pointers
 536                 for nodes which height is more than 1.
 537             */
 538             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 539
 540             /// back-off strategy used
 541             /**
 542                 If the option is not specified, the cds::backoff::Default is used.
 543             */
 544             typedef cds::backoff::Default           back_off;
 545
 546             /// Internal statistics
 547             typedef empty_stat                      stat;
 548
 549             /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
 550             /**
 551                 List of available options see opt::rcu_check_deadlock
 552             */
 553             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 554
 555             //@cond
 556             // For internal use only!!!
 557             typedef opt::none                       internal_node_builder;
 558             //@endcond
 559         };
 560
 561         /// Metafunction converting option list to SkipListSet traits
 562         /**
 563             This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
 564             \p Options list see \ref SkipListSet.
 565         */
 566         template <CDS_DECL_OPTIONS13>
 567         struct make_traits {
 568 #   ifdef CDS_DOXYGEN_INVOKED
 569             typedef implementation_defined type ;   ///< Metafunction result
 570 #   else
 571             typedef typename cds::opt::make_options<
 572                 typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS13 >::type
 573                 ,CDS_OPTIONS13
 574             >::type   type;
 575 #   endif
 576         };
 577
 578         //@cond
 579         namespace details {
 580             template <typename Node>
 581             class head_node: public Node
 582             {
 583                 typedef Node node_type;
 584
 585                 typename node_type::atomic_marked_ptr   m_Tower[skip_list::c_nHeightLimit];
 586
 587             public:
 588                 head_node( unsigned int nHeight )
 589                 {
 590                     for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 591                         m_Tower[i].store( typename node_type::marked_ptr(), CDS_ATOMIC::memory_order_relaxed );
 592
 593                     node_type::make_tower( nHeight, m_Tower );
 594                 }
 595
 596                 node_type * head() const
 597                 {
 598                     return const_cast<node_type *>( static_cast<node_type const *>(this));
 599                 }
 600             };
 601
 602             template <typename NodeType, typename AtomicNodePtr, typename Alloc>
 603             struct intrusive_node_builder
 604             {
 605                 typedef NodeType        node_type;
 606                 typedef AtomicNodePtr   atomic_node_ptr;
 607                 typedef Alloc           allocator_type;
 608
 609                 typedef cds::details::Allocator< atomic_node_ptr, allocator_type >  tower_allocator;
 610
 611                 template <typename RandomGen>
 612                 static node_type * make_tower( node_type * pNode, RandomGen& gen )
 613                 {
 614                     return make_tower( pNode, gen() + 1 );
 615                 }
 616
 617                 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
 618                 {
 619                     if ( nHeight > 1 )
 620                         pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ) );
 621                     return pNode;
 622                 }
 623
 624                 static void dispose_tower( node_type * pNode )
 625                 {
 626                     unsigned int nHeight = pNode->height();
 627                     if ( nHeight > 1 )
 628                         tower_allocator().Delete( pNode->release_tower(), nHeight );
 629                 }
 630
 631                 struct node_disposer {
 632                     void operator()( node_type * pNode )
 633                     {
 634                         dispose_tower( pNode );
 635                     }
 636                 };
 637             };
 638
 639             // Forward declaration
 640             template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
 641             class iterator;
 642
 643         } // namespace details
 644         //@endcond
 645
 646     }   // namespace skip_list
 647
 648     // Forward declaration
 649     template <class GC, typename T, typename Traits = skip_list::type_traits >
 650     class SkipListSet;
 651
 652 }}   // namespace cds::intrusive
 653
 654 #endif // #ifndef __CDS_INTRUSIVE_SKIP_LIST_BASE_H