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