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