cds/intrusive/details/split_list_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H
   4 #define CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H
   5
   6 #include <cds/intrusive/details/base.h>
   7 #include <cds/algo/atomic.h>
   8 #include <cds/details/allocator.h>
   9 #include <cds/algo/int_algo.h>
  10 #include <cds/algo/bitop.h>
  11 #include <cds/opt/hash.h>
  12
  13 namespace cds { namespace intrusive {
  14
  15     /// Split-ordered list related definitions
  16     /** @ingroup cds_intrusive_helper
  17     */
  18     namespace split_list {
  19         //@cond
  20         struct implementation_tag;
  21         //@endcond
  22
  23         /// Split-ordered list node
  24         /**
  25             Template parameter:
  26             - OrderedListNode - node type for underlying ordered list
  27         */
  28         template <typename OrderedListNode>
  29         struct node: public OrderedListNode
  30         {
  31             //@cond
  32             typedef OrderedListNode base_class;
  33             //@endcond
  34
  35             size_t  m_nHash ;   ///< Hash value for node
  36
  37             /// Default constructor
  38             node()
  39                 : m_nHash(0)
  40             {
  41                 assert( is_dummy() );
  42             }
  43
  44             /// Initializes dummy node with \p nHash value
  45             node( size_t nHash )
  46                 : m_nHash( nHash )
  47             {
  48                 assert( is_dummy() );
  49             }
  50
  51             /// Checks if the node is dummy node
  52             bool is_dummy() const
  53             {
  54                 return (m_nHash & 1) == 0;
  55             }
  56         };
  57
  58         /// SplitListSet internal statistics. May be used for debugging or profiling
  59         /**
  60             Template argument \p Counter defines type of counter.
  61             Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
  62             strict event counting.
  63             You may use stronger type of counter like as \p cds::atomicity::item_counter,
  64             or even integral type, for example, \p int.
  65         */
  66         template <typename Counter = cds::atomicity::event_counter >
  67         struct stat
  68         {
  69             typedef Counter     counter_type;   ///< Counter type
  70
  71             counter_type    m_nInsertSuccess;        ///< Count of success inserting
  72             counter_type    m_nInsertFailed;         ///< Count of failed inserting
  73             counter_type    m_nEnsureNew;            ///< Count of new item created by \p ensure() member function
  74             counter_type    m_nEnsureExist;          ///< Count of \p ensure() call for existing item
  75             counter_type    m_nEraseSuccess;         ///< Count of success erasing of items
  76             counter_type    m_nEraseFailed;          ///< Count of attempts to erase unknown item
  77             counter_type    m_nExtractSuccess;       ///< Count of success extracting of items
  78             counter_type    m_nExtractFailed;        ///< Count of attempts to extract unknown item
  79             counter_type    m_nFindSuccess;          ///< Count of success finding
  80             counter_type    m_nFindFailed;           ///< Count of failed finding
  81             counter_type    m_nHeadNodeAllocated;    ///< Count of allocated head node
  82             counter_type    m_nHeadNodeFreed;        ///< Count of freed head node
  83             counter_type    m_nBucketCount;          ///< Current bucket count
  84             counter_type    m_nInitBucketRecursive;  ///< Count of recursive bucket initialization
  85             counter_type    m_nInitBucketContention; ///< Count of bucket init contention encountered
  86             counter_type    m_nBusyWaitBucketInit;   ///< Count of busy wait cycle while a bucket is initialized
  87
  88             //@cond
  89             void onInsertSuccess()       { ++m_nInsertSuccess; }
  90             void onInsertFailed()        { ++m_nInsertFailed; }
  91             void onEnsureNew()           { ++m_nEnsureNew; }
  92             void onEnsureExist()         { ++m_nEnsureExist; }
  93             void onEraseSuccess()        { ++m_nEraseSuccess; }
  94             void onEraseFailed()         { ++m_nEraseFailed; }
  95             void onExtractSuccess()      { ++m_nExtractSuccess; }
  96             void onExtractFailed()       { ++m_nExtractFailed; }
  97             void onFindSuccess()         { ++m_nFindSuccess; }
  98             void onFindFailed()          { ++m_nFindFailed; }
  99             bool onFind(bool bSuccess)
 100             {
 101                 if ( bSuccess )
 102                     onFindSuccess();
 103                 else
 104                     onFindFailed();
 105                 return bSuccess;
 106             }
 107             void onHeadNodeAllocated()   { ++m_nHeadNodeAllocated; }
 108             void onHeadNodeFreed()       { ++m_nHeadNodeFreed; }
 109             void onNewBucket()           { ++m_nBucketCount; }
 110             void onRecursiveInitBucket() { ++m_nInitBucketRecursive; }
 111             void onBucketInitContenton() { ++m_nInitBucketContention; }
 112             void onBusyWaitBucketInit()  { ++m_nBusyWaitBucketInit; }
 113             //@endcond
 114         };
 115
 116         /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p split_list::stat
 117         struct empty_stat {
 118             //@cond
 119             void onInsertSuccess()       const {}
 120             void onInsertFailed()        const {}
 121             void onEnsureNew()           const {}
 122             void onEnsureExist()         const {}
 123             void onEraseSuccess()        const {}
 124             void onEraseFailed()         const {}
 125             void onExtractSuccess()      const {}
 126             void onExtractFailed()       const {}
 127             void onFindSuccess()         const {}
 128             void onFindFailed()          const {}
 129             bool onFind( bool bSuccess ) const { return bSuccess; }
 130             void onHeadNodeAllocated()   const {}
 131             void onHeadNodeFreed()       const {}
 132             void onNewBucket()           const {}
 133             void onRecursiveInitBucket() const {}
 134             void onBucketInitContenton() const {}
 135             void onBusyWaitBucketInit()  const {}
 136             //@endcond
 137         };
 138
 139         /// SplitListSet traits
 140         struct traits
 141         {
 142             /// Hash function
 143             /**
 144                 Hash function converts the key fields of struct \p T stored in the split list
 145                 into hash value of type \p size_t that is an index in hash table.
 146
 147                 Hash typedef is mandatory and has no predefined one.
 148             */
 149             typedef opt::none       hash;
 150
 151             /// Item counter
 152             /**
 153                 The item counting is an important part of \p SplitListSet algorithm:
 154                 the <tt>empty()</tt> member function depends on correct item counting.
 155                 Therefore, \p cds::atomicity::empty_item_counter is not allowed as a type of the option.
 156
 157                 Default is \p cds::atomicity::item_counter.
 158             */
 159             typedef cds::atomicity::item_counter item_counter;
 160
 161             /// Bucket table allocator
 162             /**
 163                 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 164             */
 165             typedef CDS_DEFAULT_ALLOCATOR   allocator;
 166
 167             /// Internal statistics (by default, disabled)
 168             /**
 169                 Possible statistics types are: \p split_list::stat (enable internal statistics),
 170                 \p split_list::empty_stat (the default, internal statistics disabled),
 171                 user-provided class that supports \p %split_list::stat interface.
 172             */
 173             typedef split_list::empty_stat  stat;
 174
 175
 176             /// C++ memory ordering model
 177             /**
 178                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 179                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 180             */
 181             typedef opt::v::relaxed_ordering memory_model;
 182
 183             /// What type of bucket table is used
 184             /**
 185                 \p true - use \p split_list::expandable_bucket_table that can be expanded
 186                     if the load factor of the set is exhausted.
 187                 \p false - use \p split_list::static_bucket_table that cannot be expanded
 188                     and is allocated in \p SplitListSet constructor.
 189
 190                 Default is \p true.
 191             */
 192             static const bool dynamic_bucket_table = true;
 193
 194             /// Back-off strategy
 195             typedef cds::backoff::Default back_off;
 196         };
 197
 198         /// [value-option] Split-list dynamic bucket table option
 199         /**
 200             The option is used to select bucket table implementation.
 201             Possible values of \p Value are:
 202             - \p true - select \p expandable_bucket_table
 203             - \p false - select \p static_bucket_table
 204         */
 205         template <bool Value>
 206         struct dynamic_bucket_table
 207         {
 208             //@cond
 209             template <typename Base> struct pack: public Base
 210             {
 211                 enum { dynamic_bucket_table = Value };
 212             };
 213             //@endcond
 214         };
 215
 216         /// Metafunction converting option list to \p split_list::traits
 217         /**
 218             Available \p Options:
 219             - \p opt::hash - mandatory option, specifies hash functor.
 220             - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
 221                 for default type.
 222             - \p opt::memory_model - C++ memory model for atomic operations.
 223                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 224                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 225             - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
 226             - \p split_list::dynamic_bucket_table - use dynamic or static bucket table implementation.
 227                 Dynamic bucket table expands its size up to maximum bucket count when necessary
 228             - \p opt::back_off - back-off strategy used for spinning, defult is \p cds::backoff::Default.
 229             - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled).
 230                 To enable internal statistics use \p split_list::stat.
 231         */
 232         template <typename... Options>
 233         struct make_traits {
 234             typedef typename cds::opt::make_options< traits, Options...>::type type  ;   ///< Result of metafunction
 235         };
 236
 237         /// Static bucket table
 238         /**
 239             Non-resizeable bucket table for \p SplitListSet class.
 240             The capacity of table (max bucket count) is defined in the constructor call.
 241
 242             Template parameter:
 243             - \p GC - garbage collector
 244             - \p Node - node type, must be a type based on \p split_list::node
 245             - \p Options... - options
 246
 247             \p Options are:
 248             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 249             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 250         */
 251         template <typename GC, typename Node, typename... Options>
 252         class static_bucket_table
 253         {
 254             //@cond
 255             struct default_options
 256             {
 257                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 258                 typedef opt::v::relaxed_ordering    memory_model;
 259             };
 260             typedef typename opt::make_options< default_options, Options... >::type options;
 261             //@endcond
 262
 263         public:
 264             typedef GC      gc;         ///< Garbage collector
 265             typedef Node    node_type;  ///< Bucket node type
 266             typedef atomics::atomic<node_type *> table_entry;  ///< Table entry type
 267
 268             /// Bucket table allocator
 269             typedef cds::details::Allocator< table_entry, typename options::allocator >  bucket_table_allocator;
 270
 271             /// Memory model for atomic operations
 272             typedef typename options::memory_model  memory_model;
 273
 274         protected:
 275             const size_t   m_nLoadFactor; ///< load factor (average count of items per bucket)
 276             const size_t   m_nCapacity;   ///< Bucket table capacity
 277             table_entry *  m_Table;       ///< Bucket table
 278
 279         protected:
 280             //@cond
 281             void allocate_table()
 282             {
 283                 m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr );
 284             }
 285
 286             void destroy_table()
 287             {
 288                 bucket_table_allocator().Delete( m_Table, m_nCapacity );
 289             }
 290             //@endcond
 291
 292         public:
 293             /// Constructs bucket table for 512K buckets. Load factor is 1.
 294             static_bucket_table()
 295                 : m_nLoadFactor(1)
 296                 , m_nCapacity( 512 * 1024 )
 297             {
 298                 allocate_table();
 299             }
 300
 301             /// Creates the table with specified size rounded up to nearest power-of-two
 302             static_bucket_table(
 303                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 304                 size_t nLoadFactor        ///< Load factor
 305                 )
 306                 : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 ),
 307                 m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) )
 308             {
 309                 // m_nCapacity must be power of 2
 310                 assert( cds::beans::is_power2( m_nCapacity ) );
 311                 allocate_table();
 312             }
 313
 314             /// Destroys bucket table
 315             ~static_bucket_table()
 316             {
 317                 destroy_table();
 318             }
 319
 320             /// Returns head node of bucket \p nBucket
 321             node_type * bucket( size_t nBucket ) const
 322             {
 323                 assert( nBucket < capacity() );
 324                 return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
 325             }
 326
 327             /// Set \p pNode as a head of bucket \p nBucket
 328             void bucket( size_t nBucket, node_type * pNode )
 329             {
 330                 assert( nBucket < capacity() );
 331                 assert( bucket( nBucket ) == nullptr );
 332
 333                 m_Table[ nBucket ].store( pNode, memory_model::memory_order_release );
 334             }
 335
 336             /// Returns the capacity of the bucket table
 337             size_t capacity() const
 338             {
 339                 return m_nCapacity;
 340             }
 341
 342             /// Returns the load factor, i.e. average count of items per bucket
 343             size_t load_factor() const
 344             {
 345                 return m_nLoadFactor;
 346             }
 347         };
 348
 349         /// Expandable bucket table
 350         /**
 351             This bucket table can dynamically grow its capacity when necessary
 352             up to maximum bucket count.
 353
 354             Template parameter:
 355             - \p GC - garbage collector
 356             - \p Node - node type, must be derived from \p split_list::node
 357             - \p Options... - options
 358
 359             \p Options are:
 360             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 361             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 362         */
 363         template <typename GC, typename Node, typename... Options>
 364         class expandable_bucket_table
 365         {
 366             //@cond
 367             struct default_options
 368             {
 369                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 370                 typedef opt::v::relaxed_ordering    memory_model;
 371             };
 372             typedef typename opt::make_options< default_options, Options... >::type options;
 373             //@endcond
 374         public:
 375             typedef GC      gc;        ///< Garbage collector
 376             typedef Node    node_type; ///< Bucket node type
 377             typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
 378
 379             /// Memory model for atomic operations
 380             typedef typename options::memory_model memory_model;
 381
 382         protected:
 383             typedef atomics::atomic<table_entry *>   segment_type; ///< Bucket table segment type
 384
 385         public:
 386             /// Bucket table allocator
 387             typedef cds::details::Allocator< segment_type, typename options::allocator >  bucket_table_allocator;
 388
 389             /// Bucket table segment allocator
 390             typedef cds::details::Allocator< table_entry, typename options::allocator >  segment_allocator;
 391
 392         protected:
 393             /// Bucket table metrics
 394             struct metrics {
 395                 size_t    nSegmentCount;    ///< max count of segments in bucket table
 396                 size_t    nSegmentSize;     ///< the segment's capacity. The capacity must be power of two.
 397                 size_t    nSegmentSizeLog2; ///< <tt> log2( m_nSegmentSize )</tt>
 398                 size_t    nLoadFactor;      ///< load factor
 399                 size_t    nCapacity;        ///< max capacity of bucket table
 400
 401                 //@cond
 402                 metrics()
 403                     : nSegmentCount(1024)
 404                     , nSegmentSize(512)
 405                     , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ) )
 406                     , nLoadFactor(1)
 407                     , nCapacity( nSegmentCount * nSegmentSize )
 408                 {}
 409                 //@endcond
 410             };
 411             const metrics   m_metrics; ///< Dynamic bucket table metrics
 412
 413         protected:
 414             segment_type * m_Segments; ///< bucket table - array of segments
 415
 416         protected:
 417             //@cond
 418             metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
 419             {
 420                 metrics m;
 421
 422                 // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
 423                 m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
 424
 425                 size_t nBucketCount = (size_t)( ((float) nItemCount) / m.nLoadFactor );
 426                 if ( nBucketCount <= 2 ) {
 427                     m.nSegmentCount = 1;
 428                     m.nSegmentSize = 2;
 429                 }
 430                 else if ( nBucketCount <= 1024 ) {
 431                     m.nSegmentCount = 1;
 432                     m.nSegmentSize = ((size_t) 1) << beans::log2ceil( nBucketCount );
 433                 }
 434                 else {
 435                     nBucketCount = beans::log2ceil( nBucketCount );
 436                     m.nSegmentCount =
 437                         m.nSegmentSize = ((size_t) 1) << ( nBucketCount / 2 );
 438                     if ( nBucketCount & 1 )
 439                         m.nSegmentSize *= 2;
 440                     if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
 441                         m.nSegmentSize *= 2;
 442                 }
 443                 m.nCapacity = m.nSegmentCount * m.nSegmentSize;
 444                 m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
 445                 assert( m.nSegmentSizeLog2 != 0 )   ;   //
 446                 return m;
 447             }
 448
 449             segment_type * allocate_table()
 450             {
 451                 return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
 452             }
 453
 454             void destroy_table( segment_type * pTable )
 455             {
 456                 bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
 457             }
 458
 459             table_entry * allocate_segment()
 460             {
 461                 return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
 462             }
 463
 464             void destroy_segment( table_entry * pSegment )
 465             {
 466                 segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
 467             }
 468
 469             void init_segments()
 470             {
 471                 // m_nSegmentSize must be 2**N
 472                 assert( cds::beans::is_power2( m_metrics.nSegmentSize ));
 473                 assert( ( ((size_t) 1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
 474
 475                 // m_nSegmentCount must be 2**K
 476                 assert( cds::beans::is_power2( m_metrics.nSegmentCount ));
 477
 478                 m_Segments = allocate_table();
 479             }
 480
 481             //@endcond
 482
 483         public:
 484             /// Constructs bucket table for 512K buckets. Load factor is 1.
 485             expandable_bucket_table()
 486                 : m_metrics( calc_metrics( 512 * 1024, 1 ))
 487             {
 488                 init_segments();
 489             }
 490
 491             /// Creates the table with specified capacity rounded up to nearest power-of-two
 492             expandable_bucket_table(
 493                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 494                 size_t nLoadFactor        ///< Load factor
 495                 )
 496                 : m_metrics( calc_metrics( nItemCount, nLoadFactor ))
 497             {
 498                 init_segments();
 499             }
 500
 501             /// Destroys bucket table
 502             ~expandable_bucket_table()
 503             {
 504                 segment_type * pSegments = m_Segments;
 505                 for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) {
 506                     table_entry * pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
 507                     if ( pEntry != nullptr )
 508                         destroy_segment( pEntry );
 509                 }
 510                 destroy_table( pSegments );
 511             }
 512
 513             /// Returns head node of the bucket \p nBucket
 514             node_type * bucket( size_t nBucket ) const
 515             {
 516                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 517                 assert( nSegment < m_metrics.nSegmentCount );
 518
 519                 table_entry * pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
 520                 if ( pSegment == nullptr )
 521                     return nullptr;    // uninitialized bucket
 522                 return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire);
 523             }
 524
 525             /// Set \p pNode as a head of bucket \p nBucket
 526             void bucket( size_t nBucket, node_type * pNode )
 527             {
 528                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 529                 assert( nSegment < m_metrics.nSegmentCount );
 530
 531                 segment_type& segment = m_Segments[nSegment];
 532                 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
 533                     table_entry * pNewSegment = allocate_segment();
 534                     table_entry * pNull = nullptr;
 535                     if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 536                         destroy_segment( pNewSegment );
 537                     }
 538                 }
 539                 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
 540             }
 541
 542             /// Returns the capacity of the bucket table
 543             size_t capacity() const
 544             {
 545                 return m_metrics.nCapacity;
 546             }
 547
 548             /// Returns the load factor, i.e. average count of items per bucket
 549             size_t load_factor() const
 550             {
 551                 return m_metrics.nLoadFactor;
 552             }
 553         };
 554
 555         /// Split-list node traits
 556         /**
 557             This traits is intended for converting between underlying ordered list node type
 558             and split-list node type
 559
 560             Template parameter:
 561             - \p BaseNodeTraits - node traits of base ordered list type
 562         */
 563         template <class BaseNodeTraits>
 564         struct node_traits: private BaseNodeTraits
 565         {
 566             typedef BaseNodeTraits base_class;     ///< Base ordered list node type
 567             typedef typename base_class::value_type value_type;     ///< Value type
 568             typedef typename base_class::node_type  base_node_type; ///< Ordered list node type
 569             typedef node<base_node_type>            node_type;      ///< Spit-list node type
 570
 571             /// Convert value reference to node pointer
 572             static node_type * to_node_ptr( value_type& v )
 573             {
 574                 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
 575             }
 576
 577             /// Convert value pointer to node pointer
 578             static node_type * to_node_ptr( value_type * v )
 579             {
 580                 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
 581             }
 582
 583             /// Convert value reference to node pointer (const version)
 584             static node_type const * to_node_ptr( value_type const& v )
 585             {
 586                 return static_cast<node_type const*>( base_class::to_node_ptr( v ) );
 587             }
 588
 589             /// Convert value pointer to node pointer (const version)
 590             static node_type const * to_node_ptr( value_type const * v )
 591             {
 592                 return static_cast<node_type const *>( base_class::to_node_ptr( v ) );
 593             }
 594
 595             /// Convert node refernce to value pointer
 596             static value_type * to_value_ptr( node_type&  n )
 597             {
 598                 return base_class::to_value_ptr( static_cast<base_node_type &>( n ) );
 599             }
 600
 601             /// Convert node pointer to value pointer
 602             static value_type * to_value_ptr( node_type *  n )
 603             {
 604                 return base_class::to_value_ptr( static_cast<base_node_type *>( n ) );
 605             }
 606
 607             /// Convert node reference to value pointer (const version)
 608             static const value_type * to_value_ptr( node_type const & n )
 609             {
 610                 return base_class::to_value_ptr( static_cast<base_node_type const &>( n ) );
 611             }
 612
 613             /// Convert node pointer to value pointer (const version)
 614             static const value_type * to_value_ptr( node_type const * n )
 615             {
 616                 return base_class::to_value_ptr( static_cast<base_node_type const *>( n ) );
 617             }
 618         };
 619
 620         //@cond
 621         namespace details {
 622             template <bool Value, typename GC, typename Node, typename... Options>
 623             struct bucket_table_selector;
 624
 625             template <typename GC, typename Node, typename... Options>
 626             struct bucket_table_selector< true, GC, Node, Options...>
 627             {
 628                 typedef expandable_bucket_table<GC, Node, Options...>    type;
 629             };
 630
 631             template <typename GC, typename Node, typename... Options>
 632             struct bucket_table_selector< false, GC, Node, Options...>
 633             {
 634                 typedef static_bucket_table<GC, Node, Options...>    type;
 635             };
 636
 637             template <typename GC, class Alloc >
 638             struct dummy_node_disposer {
 639                 template <typename Node>
 640                 void operator()( Node * p )
 641                 {
 642                     typedef cds::details::Allocator< Node, Alloc >  node_deallocator;
 643                     node_deallocator().Delete( p );
 644                 }
 645             };
 646
 647             template <typename Q>
 648             struct search_value_type
 649             {
 650                 Q&      val;
 651                 size_t  nHash;
 652
 653                 search_value_type( Q& v, size_t h )
 654                     : val( v )
 655                     , nHash( h )
 656                 {}
 657             };
 658
 659             template <class OrderedList, class Traits>
 660             class rebind_list_traits
 661             {
 662                 typedef OrderedList native_ordered_list;
 663                 typedef Traits      traits;
 664
 665                 typedef typename native_ordered_list::gc                gc;
 666                 typedef typename native_ordered_list::key_comparator    native_key_comparator;
 667                 typedef typename native_ordered_list::node_type         node_type;
 668                 typedef typename native_ordered_list::value_type        value_type;
 669                 typedef typename native_ordered_list::node_traits       node_traits;
 670                 typedef typename native_ordered_list::disposer          native_disposer;
 671
 672                 typedef split_list::node<node_type>                     splitlist_node_type;
 673
 674                 struct key_compare {
 675                     int operator()( value_type const& v1, value_type const& v2 ) const
 676                     {
 677                         splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v1 ));
 678                         splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v2 ));
 679                         if ( n1->m_nHash != n2->m_nHash )
 680                             return n1->m_nHash < n2->m_nHash ? -1 : 1;
 681
 682                         if ( n1->is_dummy() ) {
 683                             assert( n2->is_dummy() );
 684                             return 0;
 685                         }
 686
 687                         assert( !n1->is_dummy() && !n2->is_dummy() );
 688
 689                         return native_key_comparator()( v1, v2 );
 690                     }
 691
 692                     template <typename Q>
 693                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
 694                     {
 695                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 696                         if ( n->m_nHash != q.nHash )
 697                             return n->m_nHash < q.nHash ? -1 : 1;
 698
 699                         assert( !n->is_dummy() );
 700                         return native_key_comparator()( v, q.val );
 701                     }
 702
 703                     template <typename Q>
 704                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
 705                     {
 706                         return -operator()( v, q );
 707                     }
 708                 };
 709
 710                 struct wrapped_disposer
 711                 {
 712                     void operator()( value_type * v )
 713                     {
 714                         splitlist_node_type * p = static_cast<splitlist_node_type *>( node_traits::to_node_ptr( v ));
 715                         if ( p->is_dummy() ) {
 716                             dummy_node_disposer<gc, typename traits::allocator>()( p );
 717                         }
 718                         else {
 719                             native_disposer()( v );
 720                         }
 721                     }
 722                 };
 723
 724             public:
 725                 template <typename Less>
 726                 struct make_compare_from_less: public cds::opt::details::make_comparator_from_less<Less>
 727                 {
 728                     typedef cds::opt::details::make_comparator_from_less<Less>  base_class;
 729
 730                     template <typename Q>
 731                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
 732                     {
 733                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 734                         if ( n->m_nHash != q.nHash )
 735                             return n->m_nHash < q.nHash ? -1 : 1;
 736
 737                         assert( !n->is_dummy() );
 738                         return base_class()( v, q.val );
 739                     }
 740
 741                     template <typename Q>
 742                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
 743                     {
 744                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 745                         if ( n->m_nHash != q.nHash )
 746                             return q.nHash < n->m_nHash ? -1 : 1;
 747
 748                         assert( !n->is_dummy() );
 749                         return base_class()( q.val, v );
 750                     }
 751
 752                     template <typename Q1, typename Q2>
 753                     int operator()( Q1 const& v1, Q2 const& v2 ) const
 754                     {
 755                         return base_class()( v1, v2 );
 756                     }
 757                 };
 758
 759                 typedef typename native_ordered_list::template rebind_traits<
 760                     opt::compare< key_compare >
 761                     ,opt::disposer< wrapped_disposer >
 762                     ,opt::boundary_node_type< splitlist_node_type >
 763                 >::type    result;
 764             };
 765
 766             template <typename OrderedList, bool IsConst>
 767             struct select_list_iterator;
 768
 769             template <typename OrderedList>
 770             struct select_list_iterator<OrderedList, false>
 771             {
 772                 typedef typename OrderedList::iterator  type;
 773             };
 774
 775             template <typename OrderedList>
 776             struct select_list_iterator<OrderedList, true>
 777             {
 778                 typedef typename OrderedList::const_iterator  type;
 779             };
 780
 781             template <typename NodeTraits, typename OrderedList, bool IsConst>
 782             class iterator_type
 783             {
 784                 typedef OrderedList     ordered_list_type;
 785                 friend class iterator_type <NodeTraits, OrderedList, !IsConst >;
 786
 787             protected:
 788                 typedef typename select_list_iterator<ordered_list_type, IsConst>::type    list_iterator;
 789                 typedef NodeTraits      node_traits;
 790
 791             private:
 792                 list_iterator   m_itCur;
 793                 list_iterator   m_itEnd;
 794
 795             public:
 796                 typedef typename list_iterator::value_ptr   value_ptr;
 797                 typedef typename list_iterator::value_ref   value_ref;
 798
 799             public:
 800                 iterator_type()
 801                 {}
 802
 803                 iterator_type( iterator_type const& src )
 804                     : m_itCur( src.m_itCur )
 805                     , m_itEnd( src.m_itEnd )
 806                 {}
 807
 808                 // This ctor should be protected...
 809                 iterator_type( list_iterator itCur, list_iterator itEnd )
 810                     : m_itCur( itCur )
 811                     , m_itEnd( itEnd )
 812                 {
 813                     // skip dummy nodes
 814                     while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() )
 815                         ++m_itCur;
 816                 }
 817
 818
 819                 value_ptr operator ->() const
 820                 {
 821                     return m_itCur.operator->();
 822                 }
 823
 824                 value_ref operator *() const
 825                 {
 826                     return m_itCur.operator*();
 827                 }
 828
 829                 /// Pre-increment
 830                 iterator_type& operator ++()
 831                 {
 832                     if ( m_itCur != m_itEnd ) {
 833                         do {
 834                             ++m_itCur;
 835                         } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() );
 836                     }
 837                     return *this;
 838                 }
 839
 840                 iterator_type& operator = (iterator_type const& src)
 841                 {
 842                     m_itCur = src.m_itCur;
 843                     m_itEnd = src.m_itEnd;
 844                     return *this;
 845                 }
 846
 847                 template <bool C>
 848                 bool operator ==(iterator_type<node_traits, ordered_list_type, C> const& i ) const
 849                 {
 850                     return m_itCur == i.m_itCur;
 851                 }
 852                 template <bool C>
 853                 bool operator !=(iterator_type<node_traits, ordered_list_type, C> const& i ) const
 854                 {
 855                     return m_itCur != i.m_itCur;
 856                 }
 857             };
 858         }   // namespace details
 859         //@endcond
 860
 861         //@cond
 862         // Helper functions
 863
 864         /// Reverses bit order in \p nHash
 865         static inline size_t reverse_bits( size_t nHash )
 866         {
 867             return bitop::RBO( nHash );
 868         }
 869
 870         static inline size_t regular_hash( size_t nHash )
 871         {
 872             return reverse_bits( nHash ) | size_t(1);
 873         }
 874
 875         static inline size_t dummy_hash( size_t nHash )
 876         {
 877             return reverse_bits( nHash ) & ~size_t(1);
 878         }
 879         //@endcond
 880
 881     } // namespace split_list
 882
 883     //@cond
 884     // Forward declaration
 885     template <class GC, class OrderedList, class Traits = split_list::traits>
 886     class SplitListSet;
 887     //@endcond
 888
 889 }}  // namespace cds::intrusive
 890
 891 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H