cds/intrusive/split_list_base.h

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