cds/intrusive/details/split_list_base.h

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