cds/intrusive/details/skip_list_base.h

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