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