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