cds/intrusive/details/skip_list_base.h

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