cds/intrusive/details/skip_list_base.h

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