cds/intrusive/details/skip_list_base.h

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