cds/intrusive/details/skip_list_base.h

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