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