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 #include <cds/intrusive/free_list_selector.h>
  41
  42 namespace cds { namespace intrusive {
  43
  44     /// Split-ordered list related definitions
  45     /** @ingroup cds_intrusive_helper
  46     */
  47     namespace split_list {
  48         /// Split-ordered list node
  49         /**
  50             Template parameter:
  51             - \p OrderedListNode - node type for underlying ordered list
  52         */
  53         template <typename OrderedListNode>
  54         struct node: public OrderedListNode
  55         {
  56             //@cond
  57             typedef OrderedListNode base_class;
  58             //@endcond
  59
  60             size_t  m_nHash ;   ///< Hash value for node
  61
  62             /// Default constructor
  63             node()
  64                 : m_nHash(0)
  65             {
  66                 assert( is_dummy() );
  67             }
  68
  69             /// Initializes dummy node with \p nHash value
  70             node( size_t nHash )
  71                 : m_nHash( nHash )
  72             {
  73                 assert( is_dummy() );
  74             }
  75
  76             /// Checks if the node is dummy node
  77             bool is_dummy() const
  78             {
  79                 return (m_nHash & 1) == 0;
  80             }
  81         };
  82
  83         /// \p SplitListSet internal statistics. May be used for debugging or profiling
  84         /**
  85             Template argument \p Counter defines type of counter, default is \p cds::atomicity::event_counter.
  86         */
  87         template <typename Counter = cds::atomicity::event_counter >
  88         struct stat
  89         {
  90             typedef Counter     counter_type;   ///< Counter type
  91
  92             counter_type    m_nInsertSuccess;        ///< Count of success inserting
  93             counter_type    m_nInsertFailed;         ///< Count of failed inserting
  94             counter_type    m_nUpdateNew;            ///< Count of new item created by \p ensure() member function
  95             counter_type    m_nUpdateExist;          ///< Count of \p ensure() call for existing item
  96             counter_type    m_nEraseSuccess;         ///< Count of success erasing of items
  97             counter_type    m_nEraseFailed;          ///< Count of attempts to erase unknown item
  98             counter_type    m_nExtractSuccess;       ///< Count of success extracting of items
  99             counter_type    m_nExtractFailed;        ///< Count of attempts to extract unknown item
 100             counter_type    m_nFindSuccess;          ///< Count of success finding
 101             counter_type    m_nFindFailed;           ///< Count of failed finding
 102             counter_type    m_nHeadNodeAllocated;    ///< Count of allocated head node
 103             counter_type    m_nHeadNodeFreed;        ///< Count of freed head node
 104             counter_type    m_nBucketCount;          ///< Current bucket count
 105             counter_type    m_nInitBucketRecursive;  ///< Count of recursive bucket initialization
 106             counter_type    m_nInitBucketContention; ///< Count of bucket init contention encountered
 107             counter_type    m_nBusyWaitBucketInit;   ///< Count of busy wait cycle while a bucket is initialized
 108             counter_type    m_nBucketsExhausted;     ///< Count of failed bucket allocation
 109
 110             //@cond
 111             void onInsertSuccess()       { ++m_nInsertSuccess; }
 112             void onInsertFailed()        { ++m_nInsertFailed; }
 113             void onUpdateNew()           { ++m_nUpdateNew; }
 114             void onUpdateExist()         { ++m_nUpdateExist; }
 115             void onEraseSuccess()        { ++m_nEraseSuccess; }
 116             void onEraseFailed()         { ++m_nEraseFailed; }
 117             void onExtractSuccess()      { ++m_nExtractSuccess; }
 118             void onExtractFailed()       { ++m_nExtractFailed; }
 119             void onFindSuccess()         { ++m_nFindSuccess; }
 120             void onFindFailed()          { ++m_nFindFailed; }
 121             bool onFind(bool bSuccess)
 122             {
 123                 if ( bSuccess )
 124                     onFindSuccess();
 125                 else
 126                     onFindFailed();
 127                 return bSuccess;
 128             }
 129             void onHeadNodeAllocated()   { ++m_nHeadNodeAllocated; }
 130             void onHeadNodeFreed()       { ++m_nHeadNodeFreed; }
 131             void onNewBucket()           { ++m_nBucketCount; }
 132             void onRecursiveInitBucket() { ++m_nInitBucketRecursive; }
 133             void onBucketInitContenton() { ++m_nInitBucketContention; }
 134             void onBusyWaitBucketInit()  { ++m_nBusyWaitBucketInit; }
 135             void onBucketsExhausted()    { ++m_nBucketsExhausted; }
 136             //@endcond
 137         };
 138
 139         /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p split_list::stat
 140         struct empty_stat {
 141             //@cond
 142             void onInsertSuccess()       const {}
 143             void onInsertFailed()        const {}
 144             void onUpdateNew()           const {}
 145             void onUpdateExist()         const {}
 146             void onEraseSuccess()        const {}
 147             void onEraseFailed()         const {}
 148             void onExtractSuccess()      const {}
 149             void onExtractFailed()       const {}
 150             void onFindSuccess()         const {}
 151             void onFindFailed()          const {}
 152             bool onFind( bool bSuccess ) const { return bSuccess; }
 153             void onHeadNodeAllocated()   const {}
 154             void onHeadNodeFreed()       const {}
 155             void onNewBucket()           const {}
 156             void onRecursiveInitBucket() const {}
 157             void onBucketInitContenton() const {}
 158             void onBusyWaitBucketInit()  const {}
 159             void onBucketsExhausted()    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             /// Padding; default is cache-line padding
 221             enum {
 222                 padding = cds::opt::cache_line_padding
 223             };
 224
 225             /// Free-list of auxiliary nodes
 226             /**
 227                 The split-list contains auxiliary nodes marked the start of buckets.
 228                 To increase performance, there is a pool of preallocated aux nodes. The part of the pool is a free-list
 229                 of aux nodes.
 230
 231                 Default is:
 232                 - \p cds::intrusive::FreeList - if architecture and/or compiler does not support double-width CAS primitive
 233                 - \p cds::intrusive::TaggedFreeList - if architecture and/or compiler supports double-width CAS primitive
 234             */
 235             typedef FreeListImpl free_list;
 236         };
 237
 238         /// [value-option] Split-list dynamic bucket table option
 239         /**
 240             The option is used to select bucket table implementation.
 241             Possible values of \p Value are:
 242             - \p true - select \p expandable_bucket_table
 243             - \p false - select \p static_bucket_table
 244         */
 245         template <bool Value>
 246         struct dynamic_bucket_table
 247         {
 248             //@cond
 249             template <typename Base> struct pack: public Base
 250             {
 251                 enum { dynamic_bucket_table = Value };
 252             };
 253             //@endcond
 254         };
 255
 256         /// Metafunction converting option list to \p split_list::traits
 257         /**
 258             Available \p Options:
 259             - \p opt::hash - mandatory option, specifies hash functor.
 260             - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
 261                 for default type.
 262             - \p opt::memory_model - C++ memory model for atomic operations.
 263                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 264                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 265             - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
 266             - \p split_list::dynamic_bucket_table - use dynamic or static bucket table implementation.
 267                 Dynamic bucket table expands its size up to maximum bucket count when necessary
 268             - \p opt::back_off - back-off strategy used for spinning, default is \p cds::backoff::Default.
 269             - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled).
 270                 To enable internal statistics use \p split_list::stat.
 271             - \p opt::padding - a padding to solve false-sharing issues; default is cache-line padding
 272             - \p opt::free_list - a free-list implementation, see \p traits::free_list
 273         */
 274         template <typename... Options>
 275         struct make_traits {
 276             typedef typename cds::opt::make_options< traits, Options...>::type type  ;   ///< Result of metafunction
 277         };
 278
 279         /// Static bucket table
 280         /**
 281             Non-resizeable bucket table for \p SplitListSet class.
 282             The capacity of table (max bucket count) is defined in the constructor call.
 283
 284             Template parameter:
 285             - \p GC - garbage collector
 286             - \p Node - node type, must be a type based on \p split_list::node
 287             - \p Options... - options
 288
 289             \p Options are:
 290             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 291             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 292             - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
 293                  otherwise \p FreeList.
 294         */
 295         template <typename GC, typename Node, typename... Options>
 296         class static_bucket_table
 297         {
 298             //@cond
 299             struct default_options
 300             {
 301                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 302                 typedef opt::v::relaxed_ordering    memory_model;
 303                 typedef FreeListImpl                free_list;
 304             };
 305             typedef typename opt::make_options< default_options, Options... >::type options;
 306             //@endcond
 307
 308         public:
 309             typedef GC       gc;         ///< Garbage collector
 310             typedef Node     node_type;  ///< Bucket node type
 311             typedef typename options::allocator allocator; ///< allocator
 312             typedef typename options::memory_model  memory_model; ///< Memory model for atomic operations
 313             typedef typename options::free_list free_list; ///< Free-list
 314
 315             /// Auxiliary node type
 316             struct aux_node_type: public node_type, public free_list::node
 317             {};
 318
 319             typedef atomics::atomic<aux_node_type *> table_entry;  ///< Table entry type
 320             typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator; ///< Bucket table allocator
 321
 322         protected:
 323             //@cond
 324             const size_t   m_nLoadFactor; ///< load factor (average count of items per bucket)
 325             const size_t   m_nCapacity;   ///< Bucket table capacity
 326             table_entry *  m_Table;       ///< Bucket table
 327
 328             typedef typename allocator::template rebind< aux_node_type >::other aux_node_allocator;
 329
 330             aux_node_type*          m_auxNode;           ///< Array of pre-allocated auxiliary nodes
 331             atomics::atomic<size_t> m_nAuxNodeAllocated; ///< how many auxiliary node allocated
 332             free_list               m_freeList;          ///< Free list
 333             //@endcond
 334
 335         protected:
 336             //@cond
 337             void allocate_table()
 338             {
 339                 m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr );
 340                 m_auxNode = aux_node_allocator().allocate( m_nCapacity );
 341             }
 342
 343             void destroy_table()
 344             {
 345                 m_freeList.clear( []( typename free_list::node* ) {} );
 346                 aux_node_allocator().deallocate( m_auxNode, m_nCapacity );
 347                 bucket_table_allocator().Delete( m_Table, m_nCapacity );
 348             }
 349             //@endcond
 350
 351         public:
 352             /// Constructs bucket table for 512K buckets. Load factor is 1.
 353             static_bucket_table()
 354                 : m_nLoadFactor(1)
 355                 , m_nCapacity( 512 * 1024 )
 356                 , m_nAuxNodeAllocated( 0 )
 357             {
 358                 allocate_table();
 359             }
 360
 361             /// Creates the table with specified size rounded up to nearest power-of-two
 362             static_bucket_table(
 363                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 364                 size_t nLoadFactor        ///< Load factor
 365                 )
 366                 : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 )
 367                 , m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) )
 368                 , m_nAuxNodeAllocated( 0 )
 369             {
 370                 // m_nCapacity must be power of 2
 371                 assert( cds::beans::is_power2( m_nCapacity ) );
 372                 allocate_table();
 373             }
 374
 375             /// Destroys bucket table
 376             ~static_bucket_table()
 377             {
 378                 destroy_table();
 379             }
 380
 381             /// Returns head node of bucket \p nBucket
 382             aux_node_type * bucket( size_t nBucket ) const
 383             {
 384                 assert( nBucket < capacity() );
 385                 return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
 386             }
 387
 388             /// Set \p pNode as a head of bucket \p nBucket
 389             void bucket( size_t nBucket, aux_node_type * pNode )
 390             {
 391                 assert( nBucket < capacity() );
 392                 assert( bucket( nBucket ) == nullptr );
 393
 394                 m_Table[ nBucket ].store( pNode, memory_model::memory_order_release );
 395             }
 396
 397             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
 398             aux_node_type* alloc_aux_node()
 399             {
 400                 if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity() ) {
 401                     // alloc next free node from m_auxNode
 402                     size_t const idx = m_nAuxNodeAllocated.fetch_add( 1, memory_model::memory_order_relaxed );
 403                     if ( idx < capacity() )
 404                         return new( &m_auxNode[idx] ) aux_node_type();
 405                 }
 406
 407                 // get from free-list
 408                 auto pFree = m_freeList.get();
 409                 if ( pFree )
 410                     return static_cast<aux_node_type*>( pFree );
 411
 412                 // table exhausted
 413                 return nullptr;
 414             }
 415
 416             /// Places node type to free-list
 417             void free_aux_node( aux_node_type* p )
 418             {
 419                 m_freeList.put( static_cast<aux_node_type*>( p ));
 420             }
 421
 422             /// Returns the capacity of the bucket table
 423             size_t capacity() const
 424             {
 425                 return m_nCapacity;
 426             }
 427
 428             /// Returns the load factor, i.e. average count of items per bucket
 429             size_t load_factor() const
 430             {
 431                 return m_nLoadFactor;
 432             }
 433         };
 434
 435         /// Expandable bucket table
 436         /**
 437             This bucket table can dynamically grow its capacity when necessary
 438             up to maximum bucket count.
 439
 440             Template parameter:
 441             - \p GC - garbage collector
 442             - \p Node - node type, must be derived from \p split_list::node
 443             - \p Options... - options
 444
 445             \p Options are:
 446             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 447             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 448             - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
 449                 otherwise \p FreeList.
 450             */
 451         template <typename GC, typename Node, typename... Options>
 452         class expandable_bucket_table
 453         {
 454             //@cond
 455             struct default_options
 456             {
 457                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 458                 typedef opt::v::relaxed_ordering    memory_model;
 459                 typedef FreeListImpl                free_list;
 460             };
 461             typedef typename opt::make_options< default_options, Options... >::type options;
 462             //@endcond
 463
 464         public:
 465             typedef GC       gc;                            ///< Garbage collector
 466             typedef Node     node_type;                     ///< Bucket node type
 467             typedef typename options::allocator allocator;  ///< allocator
 468
 469             /// Memory model for atomic operations
 470             typedef typename options::memory_model memory_model;
 471
 472             /// Free-list
 473             typedef typename options::free_list free_list;
 474
 475             /// Auxiliary node type
 476             class aux_node_type: public node_type, public free_list::node
 477             {};
 478
 479         protected:
 480             //@cond
 481             typedef atomics::atomic<aux_node_type *> table_entry;    ///< Table entry type
 482             typedef atomics::atomic<table_entry *>   segment_type;   ///< Bucket table segment type
 483
 484             struct aux_node_segment {
 485                 atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment
 486                 aux_node_segment*         next_segment;
 487                 // aux_node_type     nodes[];
 488
 489                 aux_node_segment()
 490                     : aux_node_count(0)
 491                     , next_segment( nullptr )
 492                 {}
 493
 494                 aux_node_type* segment()
 495                 {
 496                     return reinterpret_cast<aux_node_type*>( this + 1 );
 497                 }
 498             };
 499
 500             /// Bucket table metrics
 501             struct metrics {
 502                 size_t    nSegmentCount;    ///< max count of segments in bucket table
 503                 size_t    nSegmentSize;     ///< the segment's capacity. The capacity must be power of two.
 504                 size_t    nSegmentSizeLog2; ///< <tt> log2( m_nSegmentSize )</tt>
 505                 size_t    nLoadFactor;      ///< load factor
 506                 size_t    nCapacity;        ///< max capacity of bucket table
 507
 508                 metrics()
 509                     : nSegmentCount( 1024 )
 510                     , nSegmentSize( 512 )
 511                     , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ) )
 512                     , nLoadFactor( 1 )
 513                     , nCapacity( nSegmentCount * nSegmentSize )
 514                 {}
 515             };
 516
 517             /// Bucket table allocator
 518             typedef cds::details::Allocator< segment_type, allocator > bucket_table_allocator;
 519
 520             /// Bucket table segment allocator
 521             typedef cds::details::Allocator< table_entry, allocator > segment_allocator;
 522
 523             // Aux node segment allocator
 524             typedef typename allocator::template rebind<char>::other raw_allocator;
 525
 526             //@endcond
 527
 528         public:
 529             /// Constructs bucket table for 512K buckets. Load factor is 1.
 530             expandable_bucket_table()
 531                 : m_metrics( calc_metrics( 512 * 1024, 1 ))
 532             {
 533                 init();
 534             }
 535
 536             /// Creates the table with specified capacity rounded up to nearest power-of-two
 537             expandable_bucket_table(
 538                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 539                 size_t nLoadFactor        ///< Load factor
 540                 )
 541                 : m_metrics( calc_metrics( nItemCount, nLoadFactor ))
 542             {
 543                 init();
 544             }
 545
 546             /// Destroys bucket table
 547             ~expandable_bucket_table()
 548             {
 549                 m_freeList.clear( []( typename free_list::node* ) {} );
 550
 551                 for ( auto aux_segment  = m_auxNodeList.load( atomics::memory_order_relaxed ); aux_segment; ) {
 552                     auto next_segment = aux_segment->next_segment;
 553                     free_aux_segment( aux_segment );
 554                     aux_segment = next_segment;
 555                 }
 556
 557                 segment_type * pSegments = m_Segments;
 558                 for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) {
 559                     table_entry* pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
 560                     if ( pEntry != nullptr )
 561                         destroy_segment( pEntry );
 562                 }
 563
 564                 destroy_table( pSegments );
 565             }
 566
 567             /// Returns head node of the bucket \p nBucket
 568             aux_node_type * bucket( size_t nBucket ) const
 569             {
 570                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 571                 assert( nSegment < m_metrics.nSegmentCount );
 572
 573                 table_entry* pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
 574                 if ( pSegment == nullptr )
 575                     return nullptr;    // uninitialized bucket
 576                 return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire);
 577             }
 578
 579             /// Set \p pNode as a head of bucket \p nBucket
 580             void bucket( size_t nBucket, aux_node_type * pNode )
 581             {
 582                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 583                 assert( nSegment < m_metrics.nSegmentCount );
 584
 585                 segment_type& segment = m_Segments[nSegment];
 586                 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
 587                     table_entry* pNewSegment = allocate_segment();
 588                     table_entry * pNull = nullptr;
 589                     if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
 590                         destroy_segment( pNewSegment );
 591                     }
 592                 }
 593                 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
 594             }
 595
 596             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
 597             aux_node_type* alloc_aux_node()
 598             {
 599                 for ( ;; ) {
 600                     aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_relaxed );
 601                     assert( aux_segment != nullptr );
 602
 603                     // try to allocate from current aux segment
 604                     if ( aux_segment->aux_node_count.load( memory_model::memory_order_relaxed ) < m_metrics.nSegmentSize ) {
 605                         size_t idx = aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
 606                         if ( idx < m_metrics.nSegmentSize )
 607                             return new( aux_segment->segment() + idx ) aux_node_type();
 608                     }
 609
 610                     // try allocate from free-list
 611                     auto pFree = m_freeList.get();
 612                     if ( pFree )
 613                         return static_cast<aux_node_type*>( pFree );
 614
 615                     // free-list is empty, current segment is full
 616                     // try to allocate new aux segment
 617                     // We can allocate more aux segments than we need but it is not a problem in this context
 618                     aux_node_segment* new_aux_segment = allocate_aux_segment();
 619                     new_aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
 620                     if ( m_auxNodeList.compare_exchange_strong( aux_segment, new_aux_segment, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ))
 621                         return new( new_aux_segment->segment() ) aux_node_type();
 622
 623                     free_aux_segment( new_aux_segment );
 624                 }
 625             }
 626
 627             /// Places auxiliary node type to free-list
 628             void free_aux_node( aux_node_type* p )
 629             {
 630                 m_freeList.put( static_cast<aux_node_type*>( p ));
 631             }
 632
 633             /// Returns the capacity of the bucket table
 634             size_t capacity() const
 635             {
 636                 return m_metrics.nCapacity;
 637             }
 638
 639             /// Returns the load factor, i.e. average count of items per bucket
 640             size_t load_factor() const
 641             {
 642                 return m_metrics.nLoadFactor;
 643             }
 644
 645         protected:
 646             //@cond
 647             metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
 648             {
 649                 metrics m;
 650
 651                 // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
 652                 m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
 653
 654                 size_t nBucketCount = (size_t)(((float)nItemCount) / m.nLoadFactor);
 655                 if ( nBucketCount <= 2 ) {
 656                     m.nSegmentCount = 1;
 657                     m.nSegmentSize = 2;
 658                 }
 659                 else if ( nBucketCount <= 1024 ) {
 660                     m.nSegmentCount = 1;
 661                     m.nSegmentSize = ((size_t)1) << beans::log2ceil( nBucketCount );
 662                 }
 663                 else {
 664                     nBucketCount = beans::log2ceil( nBucketCount );
 665                     m.nSegmentCount =
 666                         m.nSegmentSize = ((size_t)1) << (nBucketCount / 2);
 667                     if ( nBucketCount & 1 )
 668                         m.nSegmentSize *= 2;
 669                     if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
 670                         m.nSegmentSize *= 2;
 671                 }
 672                 m.nCapacity = m.nSegmentCount * m.nSegmentSize;
 673                 m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
 674                 assert( m.nSegmentSizeLog2 != 0 );   //
 675                 return m;
 676             }
 677
 678             segment_type * allocate_table()
 679             {
 680                 return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
 681             }
 682
 683             void destroy_table( segment_type * pTable )
 684             {
 685                 bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
 686             }
 687
 688             table_entry* allocate_segment()
 689             {
 690                 return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
 691             }
 692
 693             void destroy_segment( table_entry* pSegment )
 694             {
 695                 segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
 696             }
 697
 698             aux_node_segment* allocate_aux_segment()
 699             {
 700                 char* p = raw_allocator().allocate( sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize );
 701                 return new(p) aux_node_segment();
 702             }
 703
 704             void free_aux_segment( aux_node_segment* p )
 705             {
 706                 raw_allocator().deallocate( reinterpret_cast<char*>( p ), sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize );
 707             }
 708
 709             void init()
 710             {
 711                 // m_nSegmentSize must be 2**N
 712                 assert( cds::beans::is_power2( m_metrics.nSegmentSize ) );
 713                 assert( (((size_t)1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
 714
 715                 // m_nSegmentCount must be 2**K
 716                 assert( cds::beans::is_power2( m_metrics.nSegmentCount ) );
 717
 718                 m_Segments = allocate_table();
 719                 m_auxNodeList = allocate_aux_segment();
 720             }
 721             //@endcond
 722
 723         protected:
 724             //@cond
 725             metrics const       m_metrics;  ///< Dynamic bucket table metrics
 726             segment_type*       m_Segments; ///< bucket table - array of segments
 727             atomics::atomic<aux_node_segment*> m_auxNodeList;  ///< segment list of aux nodes
 728             free_list           m_freeList; ///< List of free aux nodes
 729             //@endcond
 730         };
 731
 732         /// Split-list node traits
 733         /**
 734             This traits is intended for converting between underlying ordered list node type
 735             and split-list node type
 736
 737             Template parameter:
 738             - \p BaseNodeTraits - node traits of base ordered list type
 739         */
 740         template <class BaseNodeTraits>
 741         struct node_traits: private BaseNodeTraits
 742         {
 743             typedef BaseNodeTraits base_class;     ///< Base ordered list node type
 744             typedef typename base_class::value_type value_type;     ///< Value type
 745             typedef typename base_class::node_type  base_node_type; ///< Ordered list node type
 746             typedef node<base_node_type>            node_type;      ///< Spit-list node type
 747
 748             /// Convert value reference to node pointer
 749             static node_type * to_node_ptr( value_type& v )
 750             {
 751                 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
 752             }
 753
 754             /// Convert value pointer to node pointer
 755             static node_type * to_node_ptr( value_type * v )
 756             {
 757                 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
 758             }
 759
 760             /// Convert value reference to node pointer (const version)
 761             static node_type const * to_node_ptr( value_type const& v )
 762             {
 763                 return static_cast<node_type const*>( base_class::to_node_ptr( v ) );
 764             }
 765
 766             /// Convert value pointer to node pointer (const version)
 767             static node_type const * to_node_ptr( value_type const * v )
 768             {
 769                 return static_cast<node_type const *>( base_class::to_node_ptr( v ) );
 770             }
 771
 772             /// Convert node reference to value pointer
 773             static value_type * to_value_ptr( node_type&  n )
 774             {
 775                 return base_class::to_value_ptr( static_cast<base_node_type &>( n ) );
 776             }
 777
 778             /// Convert node pointer to value pointer
 779             static value_type * to_value_ptr( node_type *  n )
 780             {
 781                 return base_class::to_value_ptr( static_cast<base_node_type *>( n ) );
 782             }
 783
 784             /// Convert node reference to value pointer (const version)
 785             static const value_type * to_value_ptr( node_type const & n )
 786             {
 787                 return base_class::to_value_ptr( static_cast<base_node_type const &>( n ) );
 788             }
 789
 790             /// Convert node pointer to value pointer (const version)
 791             static const value_type * to_value_ptr( node_type const * n )
 792             {
 793                 return base_class::to_value_ptr( static_cast<base_node_type const *>( n ) );
 794             }
 795         };
 796
 797         //@cond
 798         namespace details {
 799             template <bool Value, typename GC, typename Node, typename... Options>
 800             struct bucket_table_selector;
 801
 802             template <typename GC, typename Node, typename... Options>
 803             struct bucket_table_selector< true, GC, Node, Options...>
 804             {
 805                 typedef expandable_bucket_table<GC, Node, Options...>    type;
 806             };
 807
 808             template <typename GC, typename Node, typename... Options>
 809             struct bucket_table_selector< false, GC, Node, Options...>
 810             {
 811                 typedef static_bucket_table<GC, Node, Options...>    type;
 812             };
 813
 814             template <typename Q>
 815             struct search_value_type
 816             {
 817                 Q&      val;
 818                 size_t  nHash;
 819
 820                 search_value_type( Q& v, size_t h )
 821                     : val( v )
 822                     , nHash( h )
 823                 {}
 824             };
 825
 826             template <class OrderedList, class Traits>
 827             class rebind_list_traits
 828             {
 829                 typedef OrderedList native_ordered_list;
 830                 typedef Traits      traits;
 831
 832                 typedef typename native_ordered_list::gc                gc;
 833                 typedef typename native_ordered_list::key_comparator    native_key_comparator;
 834                 typedef typename native_ordered_list::node_type         node_type;
 835                 typedef typename native_ordered_list::value_type        value_type;
 836                 typedef typename native_ordered_list::node_traits       node_traits;
 837                 typedef typename native_ordered_list::disposer          native_disposer;
 838
 839                 typedef split_list::node<node_type>                     splitlist_node_type;
 840
 841                 struct key_compare {
 842                     int operator()( value_type const& v1, value_type const& v2 ) const
 843                     {
 844                         splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v1 ));
 845                         splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v2 ));
 846                         if ( n1->m_nHash != n2->m_nHash )
 847                             return n1->m_nHash < n2->m_nHash ? -1 : 1;
 848
 849                         if ( n1->is_dummy() ) {
 850                             assert( n2->is_dummy() );
 851                             return 0;
 852                         }
 853
 854                         assert( !n1->is_dummy() && !n2->is_dummy() );
 855
 856                         return native_key_comparator()( v1, v2 );
 857                     }
 858
 859                     template <typename Q>
 860                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
 861                     {
 862                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 863                         if ( n->m_nHash != q.nHash )
 864                             return n->m_nHash < q.nHash ? -1 : 1;
 865
 866                         assert( !n->is_dummy() );
 867                         return native_key_comparator()( v, q.val );
 868                     }
 869
 870                     template <typename Q>
 871                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
 872                     {
 873                         return -operator()( v, q );
 874                     }
 875                 };
 876
 877                 struct wrapped_disposer
 878                 {
 879                     void operator()( value_type * v )
 880                     {
 881                         splitlist_node_type * p = static_cast<splitlist_node_type *>( node_traits::to_node_ptr( v ));
 882                         if ( !p->is_dummy() )
 883                             native_disposer()( v );
 884                     }
 885                 };
 886
 887             public:
 888                 template <typename Less>
 889                 struct make_compare_from_less: public cds::opt::details::make_comparator_from_less<Less>
 890                 {
 891                     typedef cds::opt::details::make_comparator_from_less<Less>  base_class;
 892
 893                     template <typename Q>
 894                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
 895                     {
 896                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 897                         if ( n->m_nHash != q.nHash )
 898                             return n->m_nHash < q.nHash ? -1 : 1;
 899
 900                         assert( !n->is_dummy() );
 901                         return base_class()( v, q.val );
 902                     }
 903
 904                     template <typename Q>
 905                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
 906                     {
 907                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
 908                         if ( n->m_nHash != q.nHash )
 909                             return q.nHash < n->m_nHash ? -1 : 1;
 910
 911                         assert( !n->is_dummy() );
 912                         return base_class()( q.val, v );
 913                     }
 914
 915                     template <typename Q1, typename Q2>
 916                     int operator()( Q1 const& v1, Q2 const& v2 ) const
 917                     {
 918                         return base_class()( v1, v2 );
 919                     }
 920                 };
 921
 922                 typedef typename native_ordered_list::template rebind_traits<
 923                     opt::compare< key_compare >
 924                     ,opt::disposer< wrapped_disposer >
 925                     ,opt::boundary_node_type< splitlist_node_type >
 926                 >::type result;
 927             };
 928
 929             template <typename OrderedList, bool IsConst>
 930             struct select_list_iterator;
 931
 932             template <typename OrderedList>
 933             struct select_list_iterator<OrderedList, false>
 934             {
 935                 typedef typename OrderedList::iterator  type;
 936             };
 937
 938             template <typename OrderedList>
 939             struct select_list_iterator<OrderedList, true>
 940             {
 941                 typedef typename OrderedList::const_iterator  type;
 942             };
 943
 944             template <typename NodeTraits, typename OrderedList, bool IsConst>
 945             class iterator_type
 946             {
 947                 typedef OrderedList     ordered_list_type;
 948                 friend class iterator_type <NodeTraits, OrderedList, !IsConst >;
 949
 950             protected:
 951                 typedef typename select_list_iterator<ordered_list_type, IsConst>::type    list_iterator;
 952                 typedef NodeTraits      node_traits;
 953
 954             private:
 955                 list_iterator   m_itCur;
 956                 list_iterator   m_itEnd;
 957
 958             public:
 959                 typedef typename list_iterator::value_ptr   value_ptr;
 960                 typedef typename list_iterator::value_ref   value_ref;
 961
 962             public:
 963                 iterator_type()
 964                 {}
 965
 966                 iterator_type( iterator_type const& src )
 967                     : m_itCur( src.m_itCur )
 968                     , m_itEnd( src.m_itEnd )
 969                 {}
 970
 971                 // This ctor should be protected...
 972                 iterator_type( list_iterator itCur, list_iterator itEnd )
 973                     : m_itCur( itCur )
 974                     , m_itEnd( itEnd )
 975                 {
 976                     // skip dummy nodes
 977                     while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() )
 978                         ++m_itCur;
 979                 }
 980
 981                 value_ptr operator ->() const
 982                 {
 983                     return m_itCur.operator->();
 984                 }
 985
 986                 value_ref operator *() const
 987                 {
 988                     return m_itCur.operator*();
 989                 }
 990
 991                 /// Pre-increment
 992                 iterator_type& operator ++()
 993                 {
 994                     if ( m_itCur != m_itEnd ) {
 995                         do {
 996                             ++m_itCur;
 997                         } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() );
 998                     }
 999                     return *this;
1000                 }
1001
1002                 iterator_type& operator = (iterator_type const& src)
1003                 {
1004                     m_itCur = src.m_itCur;
1005                     m_itEnd = src.m_itEnd;
1006                     return *this;
1007                 }
1008
1009                 template <bool C>
1010                 bool operator ==(iterator_type<node_traits, ordered_list_type, C> const& i ) const
1011                 {
1012                     return m_itCur == i.m_itCur;
1013                 }
1014                 template <bool C>
1015                 bool operator !=(iterator_type<node_traits, ordered_list_type, C> const& i ) const
1016                 {
1017                     return m_itCur != i.m_itCur;
1018                 }
1019             };
1020         }   // namespace details
1021         //@endcond
1022
1023         //@cond
1024         // Helper functions
1025
1026         /// Reverses bit order in \p nHash
1027         static inline size_t reverse_bits( size_t nHash )
1028         {
1029             return bitop::RBO( nHash );
1030         }
1031
1032         static inline size_t regular_hash( size_t nHash )
1033         {
1034             return reverse_bits( nHash ) | size_t(1);
1035         }
1036
1037         static inline size_t dummy_hash( size_t nHash )
1038         {
1039             return reverse_bits( nHash ) & ~size_t(1);
1040         }
1041         //@endcond
1042
1043     } // namespace split_list
1044
1045     //@cond
1046     // Forward declaration
1047     template <class GC, class OrderedList, class Traits = split_list::traits>
1048     class SplitListSet;
1049     //@endcond
1050
1051 }}  // namespace cds::intrusive
1052
1053 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H