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