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 <tt>[0 .. c_nUpperBound - 1]</tt>
 279
 280
 281             Stateful generators are supported.
 282
 283             Available \p Type implementations:
 284             - \p skip_list::xor_shift
 285             - \p skip_list::turbo
 286         */
 287         template <typename Type>
 288         struct random_level_generator {
 289             //@cond
 290             template <typename Base>
 291             struct pack: public Base
 292             {
 293                 typedef Type random_level_generator;
 294             };
 295             //@endcond
 296         };
 297
 298         /// Xor-shift random level generator
 299         /**
 300             The simplest of the generators described in George Marsaglia's "Xorshift RNGs" paper.
 301             This is not a high-quality generator but is acceptable for skip-list.
 302
 303             The random generator should return numbers from range [0 .. MaxHeight - 1].
 304
 305             From Doug Lea's ConcurrentSkipListMap.java.
 306         */
 307         template <unsigned MaxHeight>
 308         class xor_shift {
 309             //@cond
 310             atomics::atomic<unsigned int>    m_nSeed;
 311
 312             static_assert( MaxHeight > 1, "MaxHeight" );
 313             static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
 314             static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
 315             //@endcond
 316
 317         public:
 318             /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
 319             static unsigned int const c_nUpperBound = MaxHeight;
 320
 321             /// Initializes the generator instance
 322             xor_shift()
 323             {
 324                 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
 325             }
 326
 327             /// Main generator function
 328             unsigned int operator()()
 329             {
 330                 /* ConcurrentSkipListMap.java
 331                 private int randomLevel() {
 332                     int x = randomSeed;
 333                     x ^= x << 13;
 334                     x ^= x >>> 17;
 335                     randomSeed = x ^= x << 5;
 336                     if ((x & 0x80000001) != 0) // test highest and lowest bits
 337                         return 0;
 338                     int level = 1;
 339                     while (((x >>>= 1) & 1) != 0) ++level;
 340                     return level;
 341                 }
 342                 */
 343                 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed );
 344                 x ^= x << 13;
 345                 x ^= x >> 17;
 346                 x ^= x << 5;
 347                 m_nSeed.store( x, atomics::memory_order_relaxed );
 348                 unsigned int nLevel = ((x & 0x00000001) != 0) ? 0 : cds::bitop::LSB( (~(x >> 1)) & c_nBitMask );
 349
 350                 assert( nLevel < c_nUpperBound );
 351                 return nLevel;
 352             }
 353         };
 354
 355         /// Xor-shift random level generator, max height 32
 356         typedef xor_shift<c_nHeightLimit> xorshift32;
 357
 358         //@cond
 359         // For backward compatibility
 360         typedef xorshift32 xorshift;
 361         //@endcond
 362
 363         /// \ref xor_shift generator, max height 24
 364         typedef xor_shift< 24 > xorshift24;
 365
 366         /// \ref xor_shift generator, max height = 16
 367         typedef xor_shift< 16 > xorshift16;
 368
 369         /// Turbo-pascal random level generator
 370         /**
 371             This uses a cheap pseudo-random function that was used in Turbo Pascal.
 372
 373             The random generator should return numbers from range [0..31].
 374
 375             From Doug Lea's ConcurrentSkipListMap.java.
 376         */
 377         template <unsigned MaxHeight>
 378         class turbo
 379         {
 380             //@cond
 381             atomics::atomic<unsigned int>    m_nSeed;
 382
 383             static_assert( MaxHeight > 1, "MaxHeight" );
 384             static_assert( MaxHeight <= c_nHeightLimit, "MaxHeight is too large" );
 385             static unsigned int const c_nBitMask = (1u << ( MaxHeight - 1 )) - 1;
 386             //@endcond
 387         public:
 388             /// The upper bound of generator's return value. The generator produces random number in range <tt>[0..c_nUpperBound)</tt>
 389             static unsigned int const c_nUpperBound = MaxHeight;
 390
 391             /// Initializes the generator instance
 392             turbo()
 393             {
 394                 m_nSeed.store( (unsigned int) cds::OS::Timer::random_seed(), atomics::memory_order_relaxed );
 395             }
 396
 397             /// Main generator function
 398             unsigned int operator()()
 399             {
 400                 /*
 401                 private int randomLevel() {
 402                     int level = 0;
 403                     int r = randomSeed;
 404                     randomSeed = r * 134775813 + 1;
 405                     if (r < 0) {
 406                         while ((r <<= 1) > 0)
 407                             ++level;
 408                     }
 409                 return level;
 410                 }
 411                 */
 412                 /*
 413                     The low bits are apparently not very random (the original used only
 414                     upper 16 bits) so we traverse from highest bit down (i.e., test
 415                     sign), thus hardly ever use lower bits.
 416                 */
 417                 unsigned int x = m_nSeed.load( atomics::memory_order_relaxed ) * 134775813 + 1;
 418                 m_nSeed.store( x, atomics::memory_order_relaxed );
 419                 unsigned int nLevel = ( x & 0x80000000 ) ? ( c_nUpperBound - 1 - cds::bitop::MSBnz( (x & c_nBitMask ) | 1 )) : 0;
 420
 421                 assert( nLevel < c_nUpperBound );
 422                 return nLevel;
 423             }
 424         };
 425
 426         /// Turbo-Pascal random level generator, max height 32
 427         typedef turbo<c_nHeightLimit> turbo32;
 428
 429         //@cond
 430         // For backward compatibility
 431         typedef turbo32 turbo_pascal;
 432         //@endcond
 433
 434         /// Turbo-Pascal generator, max height 24
 435         typedef turbo< 24 > turbo24;
 436
 437         /// Turbo-Pascal generator, max height 16
 438         typedef turbo< 16 > turbo16;
 439
 440         /// \p SkipListSet internal statistics
 441         template <typename EventCounter = cds::atomicity::event_counter>
 442         struct stat {
 443             typedef EventCounter event_counter ; ///< Event counter type
 444
 445             event_counter   m_nNodeHeightAdd[c_nHeightLimit] ; ///< Count of added node of each height
 446             event_counter   m_nNodeHeightDel[c_nHeightLimit] ; ///< Count of deleted node of each height
 447             event_counter   m_nInsertSuccess        ; ///< Count of success insertion
 448             event_counter   m_nInsertFailed         ; ///< Count of failed insertion
 449             event_counter   m_nInsertRetries        ; ///< Count of unsuccessful retries of insertion
 450             event_counter   m_nUpdateExist          ; ///< Count of \p update() call for existed node
 451             event_counter   m_nUpdateNew            ; ///< Count of \p update() call for new node
 452             event_counter   m_nUnlinkSuccess        ; ///< Count of successful call of \p unlink
 453             event_counter   m_nUnlinkFailed         ; ///< Count of failed call of \p unlink
 454             event_counter   m_nEraseSuccess         ; ///< Count of successful call of \p erase
 455             event_counter   m_nEraseFailed          ; ///< Count of failed call of \p erase
 456             event_counter   m_nEraseRetry           ; ///< Count of retries while erasing node
 457             event_counter   m_nFindFastSuccess      ; ///< Count of successful call of \p find and all derivatives (via fast-path)
 458             event_counter   m_nFindFastFailed       ; ///< Count of failed call of \p find and all derivatives (via fast-path)
 459             event_counter   m_nFindSlowSuccess      ; ///< Count of successful call of \p find and all derivatives (via slow-path)
 460             event_counter   m_nFindSlowFailed       ; ///< Count of failed call of \p find and all derivatives (via slow-path)
 461             event_counter   m_nRenewInsertPosition  ; ///< Count of renewing position events while inserting
 462             event_counter   m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting"
 463             event_counter   m_nRemoveWhileInsert    ; ///< Count of evnts "The node is removing while inserting"
 464             event_counter   m_nFastErase            ; ///< Fast erase event counter
 465             event_counter   m_nFastExtract          ; ///< Fast extract event counter
 466             event_counter   m_nSlowErase            ; ///< Slow erase event counter
 467             event_counter   m_nSlowExtract          ; ///< Slow extract event counter
 468             event_counter   m_nExtractSuccess       ; ///< Count of successful call of \p extract
 469             event_counter   m_nExtractFailed        ; ///< Count of failed call of \p extract
 470             event_counter   m_nExtractRetries       ; ///< Count of retries of \p extract call
 471             event_counter   m_nExtractMinSuccess    ; ///< Count of successful call of \p extract_min
 472             event_counter   m_nExtractMinFailed     ; ///< Count of failed call of \p extract_min
 473             event_counter   m_nExtractMinRetries    ; ///< Count of retries of \p extract_min call
 474             event_counter   m_nExtractMaxSuccess    ; ///< Count of successful call of \p extract_max
 475             event_counter   m_nExtractMaxFailed     ; ///< Count of failed call of \p extract_max
 476             event_counter   m_nExtractMaxRetries    ; ///< Count of retries of \p extract_max call
 477             event_counter   m_nEraseWhileFind       ; ///< Count of erased item while searching
 478             event_counter   m_nExtractWhileFind     ; ///< Count of extracted item while searching (RCU only)
 479             event_counter   m_nMarkFailed           ; ///< Count of failed node marking (logical deletion mark)
 480             event_counter   m_nEraseContention      ; ///< Count of key erasing contention encountered
 481
 482             //@cond
 483             void onAddNode( unsigned int nHeight )
 484             {
 485                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightAdd) / sizeof(m_nNodeHeightAdd[0]));
 486                 ++m_nNodeHeightAdd[nHeight - 1];
 487             }
 488             void onRemoveNode( unsigned int nHeight )
 489             {
 490                 assert( nHeight > 0 && nHeight <= sizeof(m_nNodeHeightDel) / sizeof(m_nNodeHeightDel[0]));
 491                 ++m_nNodeHeightDel[nHeight - 1];
 492             }
 493
 494             void onInsertSuccess()          { ++m_nInsertSuccess    ; }
 495             void onInsertFailed()           { ++m_nInsertFailed     ; }
 496             void onInsertRetry()            { ++m_nInsertRetries    ; }
 497             void onUpdateExist()            { ++m_nUpdateExist      ; }
 498             void onUpdateNew()              { ++m_nUpdateNew        ; }
 499             void onUnlinkSuccess()          { ++m_nUnlinkSuccess    ; }
 500             void onUnlinkFailed()           { ++m_nUnlinkFailed     ; }
 501             void onEraseSuccess()           { ++m_nEraseSuccess     ; }
 502             void onEraseFailed()            { ++m_nEraseFailed      ; }
 503             void onEraseRetry()             { ++m_nEraseRetry; }
 504             void onFindFastSuccess()        { ++m_nFindFastSuccess  ; }
 505             void onFindFastFailed()         { ++m_nFindFastFailed   ; }
 506             void onFindSlowSuccess()        { ++m_nFindSlowSuccess  ; }
 507             void onFindSlowFailed()         { ++m_nFindSlowFailed   ; }
 508             void onEraseWhileFind()         { ++m_nEraseWhileFind   ; }
 509             void onExtractWhileFind()       { ++m_nExtractWhileFind ; }
 510             void onRenewInsertPosition()    { ++m_nRenewInsertPosition; }
 511             void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; }
 512             void onRemoveWhileInsert()      { ++m_nRemoveWhileInsert; }
 513             void onFastErase()              { ++m_nFastErase;         }
 514             void onFastExtract()            { ++m_nFastExtract;       }
 515             void onSlowErase()              { ++m_nSlowErase;         }
 516             void onSlowExtract()            { ++m_nSlowExtract;       }
 517             void onExtractSuccess()         { ++m_nExtractSuccess;    }
 518             void onExtractFailed()          { ++m_nExtractFailed;     }
 519             void onExtractRetry()           { ++m_nExtractRetries;    }
 520             void onExtractMinSuccess()      { ++m_nExtractMinSuccess; }
 521             void onExtractMinFailed()       { ++m_nExtractMinFailed;  }
 522             void onExtractMinRetry()        { ++m_nExtractMinRetries; }
 523             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
 524             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
 525             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
 526             void onMarkFailed()             { ++m_nMarkFailed;        }
 527             void onEraseContention()        { ++m_nEraseContention;   }
 528             //@endcond
 529         };
 530
 531         /// \p SkipListSet empty internal statistics
 532         struct empty_stat {
 533             //@cond
 534             void onAddNode( unsigned int /*nHeight*/ ) const {}
 535             void onRemoveNode( unsigned int /*nHeight*/ ) const {}
 536             void onInsertSuccess()          const {}
 537             void onInsertFailed()           const {}
 538             void onInsertRetry()            const {}
 539             void onUpdateExist()            const {}
 540             void onUpdateNew()              const {}
 541             void onUnlinkSuccess()          const {}
 542             void onUnlinkFailed()           const {}
 543             void onEraseSuccess()           const {}
 544             void onEraseFailed()            const {}
 545             void onEraseRetry()             const {}
 546             void onFindFastSuccess()        const {}
 547             void onFindFastFailed()         const {}
 548             void onFindSlowSuccess()        const {}
 549             void onFindSlowFailed()         const {}
 550             void onEraseWhileFind()         const {}
 551             void onExtractWhileFind()       const {}
 552             void onRenewInsertPosition()    const {}
 553             void onLogicDeleteWhileInsert() const {}
 554             void onRemoveWhileInsert()      const {}
 555             void onFastErase()              const {}
 556             void onFastExtract()            const {}
 557             void onSlowErase()              const {}
 558             void onSlowExtract()            const {}
 559             void onExtractSuccess()         const {}
 560             void onExtractFailed()          const {}
 561             void onExtractRetry()           const {}
 562             void onExtractMinSuccess()      const {}
 563             void onExtractMinFailed()       const {}
 564             void onExtractMinRetry()        const {}
 565             void onExtractMaxSuccess()      const {}
 566             void onExtractMaxFailed()       const {}
 567             void onExtractMaxRetry()        const {}
 568             void onMarkFailed()             const {}
 569             void onEraseContention()        const {}
 570             //@endcond
 571         };
 572
 573         //@cond
 574         // For internal use only!!!
 575         template <typename Type>
 576         struct internal_node_builder {
 577             template <typename Base>
 578             struct pack: public Base
 579             {
 580                 typedef Type internal_node_builder;
 581             };
 582         };
 583         //@endcond
 584
 585         /// \p SkipListSet traits
 586         struct traits
 587         {
 588             /// Hook used
 589             /**
 590                 Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
 591             */
 592             typedef base_hook<>       hook;
 593
 594             /// Key comparison functor
 595             /**
 596                 No default functor is provided. If the option is not specified, the \p less is used.
 597             */
 598             typedef opt::none                       compare;
 599
 600             /// specifies binary predicate used for key compare.
 601             /**
 602                 Default is \p std::less<T>.
 603             */
 604             typedef opt::none                       less;
 605
 606             /// Disposer
 607             /**
 608                 The functor used for dispose removed items. Default is \p opt::v::empty_disposer.
 609             */
 610             typedef opt::v::empty_disposer          disposer;
 611
 612             /// Item counter
 613             /**
 614                 The type for item counting feature.
 615                 By default, item counting is disabled (\p atomicity::empty_item_counter),
 616                 \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter enables it.
 617             */
 618             typedef atomicity::empty_item_counter     item_counter;
 619
 620             /// C++ memory ordering model
 621             /**
 622                 List of available memory ordering see \p opt::memory_model
 623             */
 624             typedef opt::v::relaxed_ordering        memory_model;
 625
 626             /// Random level generator
 627             /**
 628                 The random level generator is an important part of skip-list algorithm.
 629                 The node height in the skip-list have a probabilistic distribution
 630                 where half of the nodes that have level \p i pointers also have level <tt>i+1</tt> pointers
 631                 (i = 0..30). So, the height of a node is in range [0..31].
 632
 633                 See \p skip_list::random_level_generator option setter.
 634             */
 635             typedef turbo32 random_level_generator;
 636
 637             /// Allocator
 638             /**
 639                 Although the skip-list is an intrusive container,
 640                 an allocator should be provided to maintain variable randomly-calculated height of the node
 641                 since the node can contain up to 32 next pointers.
 642                 The allocator specified is used to allocate an array of next pointers
 643                 for nodes which height is more than 1.
 644             */
 645             typedef CDS_DEFAULT_ALLOCATOR           allocator;
 646
 647             /// back-off strategy
 648             /**
 649                 If the option is not specified, the \p cds::backoff::Default is used.
 650             */
 651             typedef cds::backoff::Default           back_off;
 652
 653             /// Internal statistics
 654             /**
 655                 By default, internal statistics is disabled (\p skip_list::empty_stat).
 656                 Use \p skip_list::stat to enable it.
 657             */
 658             typedef empty_stat                      stat;
 659
 660             /// RCU deadlock checking policy (only for \ref cds_intrusive_SkipListSet_rcu "RCU-based SkipListSet")
 661             /**
 662                 List of available options see \p opt::rcu_check_deadlock
 663             */
 664             typedef opt::v::rcu_throw_deadlock      rcu_check_deadlock;
 665
 666             //@cond
 667             // For internal use only!!!
 668             typedef opt::none                       internal_node_builder;
 669             //@endcond
 670         };
 671
 672         /// Metafunction converting option list to \p SkipListSet traits
 673         /**
 674             \p Options are:
 675             - \p opt::hook - hook used. Possible values are: \p skip_list::base_hook, \p skip_list::member_hook, \p skip_list::traits_hook.
 676                 If the option is not specified, <tt>skip_list::base_hook<></tt> and \p gc::HP is used.
 677             - \p opt::compare - key comparison functor. No default functor is provided.
 678                 If the option is not specified, the \p opt::less is used.
 679             - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
 680             - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. Due the nature
 681                 of GC schema the disposer may be called asynchronously.
 682             - \p opt::item_counter - the type of item counting feature. Default is disabled, i.e. \p atomicity::empty_item_counter.
 683                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
 684             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 685                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 686             - \p skip_list::random_level_generator - random level generator. Can be \p skip_list::xor_shift,
 687                 \p skip_list::turbo32 (the default) or user-provided one.
 688                 See \p skip_list::random_level_generator option description for explanation.
 689             - \p opt::allocator - although the skip-list is an intrusive container,
 690                 an allocator should be provided to maintain variable randomly-calculated height of the node
 691                 since the node can contain up to 32 next pointers. The allocator option is used to allocate an array of next pointers
 692                 for nodes which height is more than 1. Default is \ref CDS_DEFAULT_ALLOCATOR.
 693             - \p opt::back_off - back-off strategy, default is \p cds::backoff::Default.
 694             - \p opt::stat - internal statistics. By default, it is disabled (\p skip_list::empty_stat).
 695                 To enable it use \p skip_list::stat
 696         */
 697         template <typename... Options>
 698         struct make_traits {
 699 #   ifdef CDS_DOXYGEN_INVOKED
 700             typedef implementation_defined type ;   ///< Metafunction result
 701 #   else
 702             typedef typename cds::opt::make_options<
 703                 typename cds::opt::find_type_traits< traits, Options... >::type
 704                 ,Options...
 705             >::type   type;
 706 #   endif
 707         };
 708
 709         //@cond
 710         namespace details {
 711             template <typename Node>
 712             class head_node: public Node
 713             {
 714                 typedef Node node_type;
 715                 typename node_type::atomic_marked_ptr   m_Tower[skip_list::c_nHeightLimit];
 716
 717             public:
 718                 head_node( unsigned int nHeight )
 719                 {
 720                     for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
 721                         m_Tower[i].store( typename node_type::marked_ptr(), atomics::memory_order_relaxed );
 722
 723                     node_type::make_tower( nHeight, m_Tower );
 724                 }
 725
 726                 node_type * head() const
 727                 {
 728                     return const_cast<node_type *>( static_cast<node_type const *>(this));
 729                 }
 730             };
 731
 732             template <typename NodeType, typename AtomicNodePtr, typename Alloc>
 733             struct intrusive_node_builder
 734             {
 735                 typedef NodeType        node_type;
 736                 typedef AtomicNodePtr   atomic_node_ptr;
 737                 typedef Alloc           allocator_type;
 738
 739                 typedef cds::details::Allocator< atomic_node_ptr, allocator_type >  tower_allocator;
 740
 741                 template <typename RandomGen>
 742                 static node_type * make_tower( node_type * pNode, RandomGen& gen )
 743                 {
 744                     return make_tower( pNode, gen() + 1 );
 745                 }
 746
 747                 static node_type * make_tower( node_type * pNode, unsigned int nHeight )
 748                 {
 749                     if ( nHeight > 1 )
 750                         pNode->make_tower( nHeight, tower_allocator().NewArray( nHeight - 1, nullptr ));
 751                     return pNode;
 752                 }
 753
 754                 static void dispose_tower( node_type * pNode )
 755                 {
 756                     unsigned int nHeight = pNode->height();
 757                     if ( nHeight > 1 )
 758                         tower_allocator().Delete( pNode->release_tower(), nHeight );
 759                 }
 760
 761                 struct node_disposer {
 762                     void operator()( node_type * pNode )
 763                     {
 764                         dispose_tower( pNode );
 765                     }
 766                 };
 767             };
 768
 769             // Forward declaration
 770             template <class GC, typename NodeTraits, typename BackOff, bool IsConst>
 771             class iterator;
 772
 773         } // namespace details
 774         //@endcond
 775
 776     }   // namespace skip_list
 777
 778     // Forward declaration
 779     template <class GC, typename T, typename Traits = skip_list::traits >
 780     class SkipListSet;
 781
 782 }}   // namespace cds::intrusive
 783
 784 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SKIP_LIST_BASE_H