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             //@endcond
  67
  68         protected:
  69             //@cond
  70             atomic_marked_ptr           m_pNext;     ///< Next item in bottom-list (list at level 0)
  71             unsigned int                m_nHeight;   ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
  72             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
  73             atomics::atomic<unsigned int> m_nUnlink; ///< How many levels has been unlinked
  74             //@endcond
  75
  76         public:
  77             node()
  78                 : m_pNext( nullptr )
  79                 , m_nHeight( 1 )
  80                 , m_arrNext( nullptr )
  81                 , m_nUnlink( 0 )
  82             {}
  83
  84
  85             /// Constructs a node's tower of height \p nHeight
  86             void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
  87             {
  88                 assert( nHeight > 0 );
  89                 assert( (nHeight == 1 && nextTower == nullptr)      // bottom-list node
  90                         || (nHeight > 1 && nextTower != nullptr)    // node at level of more than 0
  91                 );
  92
  93                 m_arrNext = nextTower;
  94                 m_nHeight = nHeight;
  95                 atomics::atomic_thread_fence( atomics::memory_order_release );
  96             }
  97
  98             //@cond
  99             atomic_marked_ptr * release_tower()
 100             {
 101                 atomic_marked_ptr * pTower = m_arrNext;
 102                 m_arrNext = nullptr;
 103                 m_nHeight = 1;
 104                 return pTower;
 105             }
 106
 107             atomic_marked_ptr * get_tower() const
 108             {
 109                 return m_arrNext;
 110             }
 111
 112             bool has_tower() const
 113             {
 114                 return m_nHeight > 1;
 115             }
 116             //@endcond
 117
 118             /// Access to element of next pointer array
 119             atomic_marked_ptr& next( unsigned int nLevel )
 120             {
 121                 assert( nLevel < height());
 122                 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr));
 123
 124                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 125             }
 126
 127             /// Access to element of next pointer array (const version)
 128             atomic_marked_ptr const& next( unsigned int nLevel ) const
 129             {
 130                 assert( nLevel < height());
 131                 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
 132
 133                 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
 134             }
 135
 136             /// Access to element of next pointer array (synonym for \p next() function)
 137             atomic_marked_ptr& operator[]( unsigned int nLevel )
 138             {
 139                 return next( nLevel );
 140             }
 141
 142             /// Access to element of next pointer array (synonym for \p next() function)
 143             atomic_marked_ptr const& operator[]( unsigned int nLevel ) const
 144             {
 145                 return next( nLevel );
 146             }
 147
 148             /// Height of the node
 149             unsigned int height() const
 150             {
 151                 return m_nHeight;
 152             }
 153
 154             /// Clears internal links
 155             void clear()
 156             {
 157                 assert( m_arrNext == nullptr );
 158                 m_pNext.store( marked_ptr(), atomics::memory_order_release );
 159             }
 160
 161             //@cond
 162             bool is_cleared() const
 163             {
 164                 return m_pNext == atomic_marked_ptr()
 165                     && m_arrNext == nullptr
 166                     && m_nHeight <= 1;
 167             }
 168
 169             bool level_unlinked( unsigned nCount = 1 )
 170             {
 171                 return m_nUnlink.fetch_add( nCount, std::memory_order_relaxed ) + 1 == height();
 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_nEraseWhileInsert     ; ///< Count of events "The node has been disposed while inserting"
 407             event_counter   m_nNotFoundWhileInsert  ; ///< Count of events "Inserting node is not found"
 408             event_counter   m_nFastErase            ; ///< Fast erase event counter
 409             event_counter   m_nFastEraseHelped      ; ///< Fast erase with helping of other thread
 410             event_counter   m_nFastExtract          ; ///< Fast extract event counter
 411             event_counter   m_nFastExtractHelped    ; ///< Fast extract with helping of other thread
 412             event_counter   m_nSlowErase            ; ///< Slow erase event counter
 413             event_counter   m_nSlowExtract          ; ///< Slow extract event counter
 414             event_counter   m_nExtractSuccess       ; ///< Count of successful call of \p extract
 415             event_counter   m_nExtractFailed        ; ///< Count of failed call of \p extract
 416             event_counter   m_nExtractRetries       ; ///< Count of retries of \p extract call
 417             event_counter   m_nExtractMinSuccess    ; ///< Count of successful call of \p extract_min
 418             event_counter   m_nExtractMinFailed     ; ///< Count of failed call of \p extract_min
 419             event_counter   m_nExtractMinRetries    ; ///< Count of retries of \p extract_min call
 420             event_counter   m_nExtractMaxSuccess    ; ///< Count of successful call of \p extract_max
 421             event_counter   m_nExtractMaxFailed     ; ///< Count of failed call of \p extract_max
 422             event_counter   m_nExtractMaxRetries    ; ///< Count of retries of \p extract_max call
 423             event_counter   m_nEraseWhileFind       ; ///< Count of erased item while searching
 424             event_counter   m_nExtractWhileFind     ; ///< Count of extracted item while searching (RCU only)
 425             event_counter   m_nMarkFailed           ; ///< Count of failed node marking (logical deletion mark)
 426             event_counter   m_nEraseContention      ; ///< Count of key erasing contention encountered
 427
 428             //@cond
 429             void onAddNode( unsigned int nHeight )
 430             {
 431                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
 432                 ++m_nNodeHeightAdd[nHeight - 1];
 433             }
 434             void onRemoveNode( unsigned int nHeight )
 435             {
 436                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
 437                 ++m_nNodeHeightDel[nHeight - 1];
 438             }
 439
 440             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 441             void onInsertFailed()           { ++m_nInsertFailed     ; }
 442             void onInsertRetry()            { ++m_nInsertRetries    ; }
 443             void onUpdateExist()            { ++m_nUpdateExist      ; }
 444             void onUpdateNew()              { ++m_nUpdateNew        ; }
 445             void onUnlinkSuccess()          { ++m_nUnlinkSuccess    ; }
 446             void onUnlinkFailed()           { ++m_nUnlinkFailed     ; }
 447             void onEraseSuccess()           { ++m_nEraseSuccess     ; }
 448             void onEraseFailed()            { ++m_nEraseFailed      ; }
 449             void onEraseRetry()             { ++m_nEraseRetry; }
 450             void onFindFastSuccess()        { ++m_nFindFastSuccess  ; }
 451             void onFindFastFailed()         { ++m_nFindFastFailed   ; }
 452             void onFindSlowSuccess()        { ++m_nFindSlowSuccess  ; }
 453             void onFindSlowFailed()         { ++m_nFindSlowFailed   ; }
 454             void onEraseWhileFind()         { ++m_nEraseWhileFind   ; }
 455             void onExtractWhileFind()       { ++m_nExtractWhileFind ; }
 456             void onRenewInsertPosition()    { ++m_nRenewInsertPosition; }
 457             void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
 458             void onEraseWhileInsert()       { ++m_nEraseWhileInsert;  }
 459             void onNotFoundWhileInsert()    { ++m_nNotFoundWhileInsert; }
 460             void onFastErase()              { ++m_nFastErase;         }
 461             void onFastEraseHelped()        { ++m_nFastEraseHelped;   }
 462             void onFastExtract()            { ++m_nFastExtract;       }
 463             void onFastExtractHelped()      { ++m_nFastExtractHelped; }
 464             void onSlowErase()              { ++m_nSlowErase;         }
 465             void onSlowExtract()            { ++m_nSlowExtract;       }
 466             void onExtractSuccess()         { ++m_nExtractSuccess;    }
 467             void onExtractFailed()          { ++m_nExtractFailed;     }
 468             void onExtractRetry()           { ++m_nExtractRetries;    }
 469             void onExtractMinSuccess()      { ++m_nExtractMinSuccess; }
 470             void onExtractMinFailed()       { ++m_nExtractMinFailed;  }
 471             void onExtractMinRetry()        { ++m_nExtractMinRetries; }
 472             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
 473             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
 474             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
 475             void onMarkFailed()             { ++m_nMarkFailed;        }
 476             void onEraseContention()        { ++m_nEraseContention;   }
 477             //@endcond
 478         };
 479
 480         /// \p SkipListSet empty internal statistics
 481         struct empty_stat {
 482             //@cond
 483             void onAddNode( unsigned int /*nHeight*/ ) const {}
 484             void onRemoveNode( unsigned int /*nHeight*/ ) const {}
 485             void onInsertSuccess()          const {}
 486             void onInsertFailed()           const {}
 487             void onInsertRetry()            const {}
 488             void onUpdateExist()            const {}
 489             void onUpdateNew()              const {}
 490             void onUnlinkSuccess()          const {}
 491             void onUnlinkFailed()           const {}
 492             void onEraseSuccess()           const {}
 493             void onEraseFailed()            const {}
 494             void onEraseRetry()             const {}
 495             void onFindFastSuccess()        const {}
 496             void onFindFastFailed()         const {}
 497             void onFindSlowSuccess()        const {}
 498             void onFindSlowFailed()         const {}
 499             void onEraseWhileFind()         const {}
 500             void onExtractWhileFind()       const {}
 501             void onRenewInsertPosition()    const {}
 502             void onLogicDeleteWhileInsert() const {}
 503             void onEraseWhileInsert()       const {}
 504             void onNotFoundWhileInsert()    const {}
 505             void onFastErase()              const {}
 506             void onFastEraseHelped()        const {}
 507             void onFastExtract()            const {}
 508             void onFastExtractHelped()      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 onMarkFailed()             const {}
 521             void onEraseContention()        const {}
 522             //@endcond
 523         };
 524
 525         //@cond
 526         // For internal use only!!!
 527         template <typename Type>
 528         struct internal_node_builder {
 529             template <typename Base>
 530             struct pack: public Base
 531             {
 532                 typedef Type internal_node_builder;
 533             };
 534         };
 535         //@endcond
 536
 537         /// \p SkipListSet traits
 538         struct traits
 539         {
 540             /// Hook used
 541             /**
 542                 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
 543             */
 544             typedef base_hook<>       hook;
 545
 546             /// Key comparison functor
 547             /**
 548                 No default functor is provided. If the option is not specified, the \p less is used.
 549             */
 550             typedef opt::none                       compare;
 551
 552             /// specifies binary predicate used for key compare.
 553             /**
 554                 Default is \p std::less<T>.
 555             */
 556             typedef opt::none                       less;
 557
 558             /// Disposer
 559             /**
 560                 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
 561             */
 562             typedef opt::v::empty_disposer          disposer;
 563
 564             /// Item counter
 565             /**
 566                 The type for item counting feature.
 567                 By default, item counting is disabled (\p atomicity::empty_item_counter),
 568                 \p atomicity::item_counter enables it.
 569             */
 570             typedef atomicity::empty_item_counter     item_counter;
 571
 572             /// C++ memory ordering model
 573             /**
 574                 List of available memory ordering see \p opt::memory_model
 575             */
 576             typedef opt::v::relaxed_ordering        memory_model;
 577
 578             /// Random level generator
 579             /**
 580                 The random level generator is an important part of skip-list algorithm.
 581                 The node height in the skip-list have a probabilistic distribution
 582                 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
 583                 (i = 0..30). So, the height of a node is in range [0..31].
 584
 585                 See \p skip_list::random_level_generator option setter.
 586             */
 587             typedef turbo_pascal                    random_level_generator;
 588
 589             /// Allocator
 590             /**
 591                 Although the skip-list is an intrusive container,
 592                 an allocator should be provided to maintain variable randomly-calculated height of the node
 593                 since the node can contain up to 32 next pointers.
 594                 The allocator specified is used to allocate an array of next pointers
 595                 for nodes which height is more than 1.
 596             */
 597             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 598
 599             /// back-off strategy
 600             /**
 601                 If the option is not specified, the \p cds::backoff::Default is used.
 602             */
 603             typedef cds::backoff::Default           back_off;
 604
 605             /// Internal statistics
 606             /**
 607                 By default, internal statistics is disabled (\p skip_list::empty_stat).
 608                 Use \p skip_list::stat to enable it.
 609             */
 610             typedef empty_stat                      stat;
 611
 612             /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
 613             /**
 614                 List of available options see \p opt::rcu_check_deadlock
 615             */
 616             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 617
 618             //@cond
 619             // For internal use only!!!
 620             typedef opt::none                       internal_node_builder;
 621             //@endcond
 622         };
 623
 624         /// Metafunction converting option list to \p SkipListSet traits
 625         /**
 626             \p Options are:
 627             - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
 628                 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
 629             - \p opt::compare - key comparison functor. No default functor is provided.
 630                 If the option is not specified, the \p opt::less is used.
 631             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 632             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 633                 of GC schema the disposer may be called asynchronously.
 634             - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
 635                 To enable it use \p atomicity::item_counter
 636             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 637                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 638             - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xorshift,
 639                 \p skip_list::turbo_pascal (the default) or
 640                 user-provided one. See \p skip_list::random_level_generator option description for explanation.
 641             - \p opt::allocator - although the skip-list is an intrusive container,
 642                 an allocator should be provided to maintain variable randomly-calculated height of the node
 643                 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
 644                 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
 645             - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
 646             - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
 647                 To enable it use \p skip_list::stat
 648         */
 649         template <typename... Options>
 650         struct make_traits {
 651 #   ifdef CDS_DOXYGEN_INVOKED
 652             typedef implementation_defined type ;   ///< Metafunction result
 653 #   else
 654             typedef typename cds::opt::make_options<
 655                 typename cds::opt::find_type_traits< traits, Options... >::type
 656                 ,Options...
 657             >::type   type;
 658 #   endif
 659         };
 660
 661         //@cond
 662         namespace details {
 663             template <typename Node>
 664             class head_node: public Node
 665             {
 666                 typedef Node node_type;
 667                 typename node_type::atomic_marked_ptr   m_Tower[skip_list::c_nHeightLimit];
 668
 669             public:
 670                 head_node( unsigned int nHeight )
 671                 {
 672                     for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 673                         m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
 674
 675                     node_type::make_tower( nHeight, m_Tower );
 676                 }
 677
 678                 node_type * head() const
 679                 {
 680                     return const_cast<node_type *>( static_cast<node_type const *>(this));
 681                 }
 682             };
 683
 684             template <typename NodeType, typename AtomicNodePtr, typename Alloc>
 685             struct intrusive_node_builder
 686             {
 687                 typedef NodeType        node_type;
 688                 typedef AtomicNodePtr   atomic_node_ptr;
 689                 typedef Alloc           allocator_type;
 690
 691                 typedef cds::details::Allocator< atomic_node_ptr, allocator_type >  tower_allocator;
 692
 693                 template <typename RandomGen>
 694                 static node_type * make_tower( node_type * pNode, RandomGen& gen )
 695                 {
 696                     return make_tower( pNode, gen() + 1 );
 697                 }
 698
 699                 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
 700                 {
 701                     if ( nHeight > 1 )
 702                         pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
 703                     return pNode;
 704                 }
 705
 706                 static void dispose_tower( node_type * pNode )
 707                 {
 708                     unsigned int nHeight = pNode->height();
 709                     if ( nHeight > 1 )
 710                         tower_allocator().Delete( pNode->release_tower(), nHeight );
 711                 }
 712
 713                 struct node_disposer {
 714                     void operator()( node_type * pNode )
 715                     {
 716                         dispose_tower( pNode );
 717                     }
 718                 };
 719             };
 720
 721             // Forward declaration
 722             template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
 723             class iterator;
 724
 725         } // namespace details
 726         //@endcond
 727
 728     }   // namespace skip_list
 729
 730     // Forward declaration
 731     template <class GC, typename T, typename Traits = skip_list::traits >
 732     class SkipListSet;
 733
 734 }}   // namespace cds::intrusive
 735
 736 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H