cds/intrusive/details/split_list_base.h

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