cds/intrusive/details/skip_list_base.h

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