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