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-2017
   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/algo/bit_reversal.h>
  37 #include <cds/details/allocator.h>
  38 #include <cds/algo/int_algo.h>
  39 #include <cds/algo/bitop.h>
  40 #include <cds/opt/hash.h>
  41 #include <cds/intrusive/free_list_selector.h>
  42 #include <cds/details/size_t_cast.h>
  43
  44 namespace cds { namespace intrusive {
  45
  46     /// Split-ordered list related definitions
  47     /** @ingroup cds_intrusive_helper
  48     */
  49     namespace split_list {
  50         //@cond
  51         struct hash_node
  52         {
  53             size_t  m_nHash;   ///< Hash value for node
  54
  55             /// Default constructor
  56             hash_node()
  57                 : m_nHash( 0 )
  58             {
  59                 assert( is_dummy());
  60             }
  61
  62             /// Initializes dummy node with \p nHash value
  63             explicit hash_node( size_t nHash )
  64                 : m_nHash( nHash )
  65             {
  66                 assert( is_dummy());
  67             }
  68
  69             /// Checks if the node is dummy node
  70             bool is_dummy() const
  71             {
  72                 return (m_nHash & 1) == 0;
  73             }
  74         };
  75         //@endcond
  76
  77         /// Split-ordered list node
  78         /**
  79             Template parameter:
  80             - \p OrderedListNode - node type for underlying ordered list
  81         */
  82         template <typename OrderedListNode>
  83         struct node: public OrderedListNode, public hash_node
  84         {
  85             //@cond
  86             typedef OrderedListNode base_class;
  87             //@endcond
  88
  89             /// Default constructor
  90             node()
  91                 : hash_node(0)
  92             {
  93                 assert( is_dummy());
  94             }
  95
  96             /// Initializes dummy node with \p nHash value
  97             explicit node( size_t nHash )
  98                 : hash_node( nHash )
  99             {
 100                 assert( is_dummy());
 101             }
 102
 103             /// Checks if the node is dummy node
 104             bool is_dummy() const
 105             {
 106                 return hash_node::is_dummy();
 107             }
 108         };
 109
 110         //@cond
 111         // for IterableList
 112         template <>
 113         struct node<void>: public hash_node
 114         {
 115             // Default ctor
 116             node()
 117                 : hash_node( 0 )
 118             {
 119                 assert( is_dummy());
 120             }
 121
 122             /// Initializes dummy node with \p nHash value
 123             explicit node( size_t nHash )
 124                 : hash_node( nHash )
 125             {
 126                 assert( is_dummy());
 127             }
 128
 129             /// Checks if the node is dummy node
 130             bool is_dummy() const
 131             {
 132                 return hash_node::is_dummy();
 133             }
 134         };
 135         //@endcond
 136
 137         /// \p SplitListSet internal statistics. May be used for debugging or profiling
 138         /**
 139             Template argument \p Counter defines type of counter, default is \p cds::atomicity::event_counter.
 140         */
 141         template <typename Counter = cds::atomicity::event_counter >
 142         struct stat
 143         {
 144             typedef Counter     counter_type;   ///< Counter type
 145
 146             counter_type    m_nInsertSuccess;        ///< Count of success inserting
 147             counter_type    m_nInsertFailed;         ///< Count of failed inserting
 148             counter_type    m_nUpdateNew;            ///< Count of new item created by \p ensure() member function
 149             counter_type    m_nUpdateExist;          ///< Count of \p ensure() call for existing item
 150             counter_type    m_nEraseSuccess;         ///< Count of success erasing of items
 151             counter_type    m_nEraseFailed;          ///< Count of attempts to erase unknown item
 152             counter_type    m_nExtractSuccess;       ///< Count of success extracting of items
 153             counter_type    m_nExtractFailed;        ///< Count of attempts to extract unknown item
 154             counter_type    m_nFindSuccess;          ///< Count of success finding
 155             counter_type    m_nFindFailed;           ///< Count of failed finding
 156             counter_type    m_nHeadNodeAllocated;    ///< Count of allocated head node
 157             counter_type    m_nHeadNodeFreed;        ///< Count of freed head node
 158             counter_type    m_nBucketCount;          ///< Current bucket count
 159             counter_type    m_nInitBucketRecursive;  ///< Count of recursive bucket initialization
 160             counter_type    m_nInitBucketContention; ///< Count of bucket init contention encountered
 161             counter_type    m_nBusyWaitBucketInit;   ///< Count of busy wait cycle while a bucket is initialized
 162             counter_type    m_nBucketsExhausted;     ///< Count of failed bucket allocation
 163
 164             //@cond
 165             void onInsertSuccess()       { ++m_nInsertSuccess; }
 166             void onInsertFailed()        { ++m_nInsertFailed; }
 167             void onUpdateNew()           { ++m_nUpdateNew; }
 168             void onUpdateExist()         { ++m_nUpdateExist; }
 169             void onEraseSuccess()        { ++m_nEraseSuccess; }
 170             void onEraseFailed()         { ++m_nEraseFailed; }
 171             void onExtractSuccess()      { ++m_nExtractSuccess; }
 172             void onExtractFailed()       { ++m_nExtractFailed; }
 173             void onFindSuccess()         { ++m_nFindSuccess; }
 174             void onFindFailed()          { ++m_nFindFailed; }
 175             bool onFind(bool bSuccess)
 176             {
 177                 if ( bSuccess )
 178                     onFindSuccess();
 179                 else
 180                     onFindFailed();
 181                 return bSuccess;
 182             }
 183             void onHeadNodeAllocated()   { ++m_nHeadNodeAllocated; }
 184             void onHeadNodeFreed()       { ++m_nHeadNodeFreed; }
 185             void onNewBucket()           { ++m_nBucketCount; }
 186             void onRecursiveInitBucket() { ++m_nInitBucketRecursive; }
 187             void onBucketInitContenton() { ++m_nInitBucketContention; }
 188             void onBusyWaitBucketInit()  { ++m_nBusyWaitBucketInit; }
 189             void onBucketsExhausted()    { ++m_nBucketsExhausted; }
 190             //@endcond
 191         };
 192
 193         /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p split_list::stat
 194         struct empty_stat {
 195             //@cond
 196             void onInsertSuccess()       const {}
 197             void onInsertFailed()        const {}
 198             void onUpdateNew()           const {}
 199             void onUpdateExist()         const {}
 200             void onEraseSuccess()        const {}
 201             void onEraseFailed()         const {}
 202             void onExtractSuccess()      const {}
 203             void onExtractFailed()       const {}
 204             void onFindSuccess()         const {}
 205             void onFindFailed()          const {}
 206             bool onFind( bool bSuccess ) const { return bSuccess; }
 207             void onHeadNodeAllocated()   const {}
 208             void onHeadNodeFreed()       const {}
 209             void onNewBucket()           const {}
 210             void onRecursiveInitBucket() const {}
 211             void onBucketInitContenton() const {}
 212             void onBusyWaitBucketInit()  const {}
 213             void onBucketsExhausted()    const {}
 214             //@endcond
 215         };
 216
 217         /// Option to control bit reversal algorithm
 218         /**
 219             Bit reversal is a significant part of split-list.
 220             \p Type can be one of predefined algorithm in \p cds::algo::bit_reversal namespace.
 221         */
 222         template <typename Type>
 223         struct bit_reversal {
 224             //@cond
 225             template <typename Base>
 226             struct pack: public Base
 227             {
 228                 typedef Type bit_reversal;
 229             };
 230             //@endcond
 231         };
 232
 233         /// SplitListSet traits
 234         struct traits
 235         {
 236             /// Hash function
 237             /**
 238                 Hash function converts the key fields of struct \p T stored in the split list
 239                 into hash value of type \p size_t that is an index in hash table.
 240                 By default, \p std::hash is used.
 241             */
 242             typedef opt::none       hash;
 243
 244             /// Bit reversal algorithm
 245             /**
 246                 Bit reversal is a significant part of split-list.
 247                 There are several predefined algorithm in \p cds::algo::bit_reversal namespace,
 248                 \p cds::algo::bit_reversal::lookup is the best general purpose one.
 249
 250                 There are more efficient bit reversal algoritm for particular processor architecture,
 251                 for example, based on x86 SIMD/AVX instruction set, see <a href="http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c">here</a>
 252             */
 253             typedef cds::algo::bit_reversal::lookup bit_reversal;
 254
 255             /// Item counter
 256             /**
 257                 The item counting is an important part of \p SplitListSet algorithm:
 258                 the <tt>empty()</tt> member function depends on correct item counting.
 259                 Therefore, \p cds::atomicity::empty_item_counter is not allowed as a type of the option.
 260
 261                 Default is \p cds::atomicity::item_counter; to avoid false sharing you may use \p atomicity::cache_friendly_item_counter
 262             */
 263             typedef cds::atomicity::item_counter item_counter;
 264
 265             /// Bucket table allocator
 266             /**
 267                 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 268             */
 269             typedef CDS_DEFAULT_ALLOCATOR   allocator;
 270
 271             /// Internal statistics (by default, disabled)
 272             /**
 273                 Possible statistics types are: \p split_list::stat (enable internal statistics),
 274                 \p split_list::empty_stat (the default, internal statistics disabled),
 275                 user-provided class that supports \p %split_list::stat interface.
 276             */
 277             typedef split_list::empty_stat  stat;
 278
 279
 280             /// C++ memory ordering model
 281             /**
 282                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 283                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
 284             */
 285             typedef opt::v::relaxed_ordering memory_model;
 286
 287             /// What type of bucket table is used
 288             /**
 289                 \p true - use \p split_list::expandable_bucket_table that can be expanded
 290                     if the load factor of the set is exhausted.
 291                 \p false - use \p split_list::static_bucket_table that cannot be expanded
 292                     and is allocated in \p SplitListSet constructor.
 293
 294                 Default is \p true.
 295             */
 296             static const bool dynamic_bucket_table = true;
 297
 298             /// Back-off strategy
 299             typedef cds::backoff::Default back_off;
 300
 301             /// Padding; default is cache-line padding
 302             enum {
 303                 padding = cds::opt::cache_line_padding
 304             };
 305
 306             /// Free-list of auxiliary nodes
 307             /**
 308                 The split-list contains auxiliary nodes marked the start of buckets.
 309                 To increase performance, there is a pool of preallocated aux nodes. The part of the pool is a free-list
 310                 of aux nodes.
 311
 312                 Default is:
 313                 - \p cds::intrusive::FreeList - if architecture and/or compiler does not support double-width CAS primitive
 314                 - \p cds::intrusive::TaggedFreeList - if architecture and/or compiler supports double-width CAS primitive
 315             */
 316             typedef FreeListImpl free_list;
 317         };
 318
 319         /// [value-option] Split-list dynamic bucket table option
 320         /**
 321             The option is used to select bucket table implementation.
 322             Possible values of \p Value are:
 323             - \p true - select \p expandable_bucket_table
 324             - \p false - select \p static_bucket_table
 325         */
 326         template <bool Value>
 327         struct dynamic_bucket_table
 328         {
 329             //@cond
 330             template <typename Base> struct pack: public Base
 331             {
 332                 enum { dynamic_bucket_table = Value };
 333             };
 334             //@endcond
 335         };
 336
 337         /// Metafunction converting option list to \p split_list::traits
 338         /**
 339             Available \p Options:
 340             - \p opt::hash - mandatory option, specifies hash functor.
 341             - \p split_list::bit_reversal - bit reversal algorithm, see \p traits::bit_reversal for explanation
 342                 default is \p cds::algo::bit_reversal::lookup
 343             - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
 344                 for default type.
 345             - \p opt::memory_model - C++ memory model for atomic operations.
 346                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
 347                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
 348             - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
 349             - \p split_list::dynamic_bucket_table - use dynamic or static bucket table implementation.
 350                 Dynamic bucket table expands its size up to maximum bucket count when necessary
 351             - \p opt::back_off - back-off strategy used for spinning, default is \p cds::backoff::Default.
 352             - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled).
 353                 To enable internal statistics use \p split_list::stat.
 354             - \p opt::padding - a padding to solve false-sharing issues; default is cache-line padding
 355             - \p opt::free_list - a free-list implementation, see \p traits::free_list
 356         */
 357         template <typename... Options>
 358         struct make_traits {
 359             typedef typename cds::opt::make_options< traits, Options...>::type type  ;   ///< Result of metafunction
 360         };
 361
 362         /// Static bucket table
 363         /**
 364             Non-resizeable bucket table for \p SplitListSet class.
 365             The capacity of table (max bucket count) is defined in the constructor call.
 366
 367             Template parameter:
 368             - \p GC - garbage collector
 369             - \p Node - node type, must be a type based on \p split_list::node
 370             - \p Options... - options
 371
 372             \p Options are:
 373             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 374             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 375             - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
 376                  otherwise \p FreeList.
 377         */
 378         template <typename GC, typename Node, typename... Options>
 379         class static_bucket_table
 380         {
 381             //@cond
 382             struct default_options
 383             {
 384                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 385                 typedef opt::v::relaxed_ordering    memory_model;
 386                 typedef FreeListImpl                free_list;
 387             };
 388             typedef typename opt::make_options< default_options, Options... >::type options;
 389             //@endcond
 390
 391         public:
 392             typedef GC       gc;         ///< Garbage collector
 393             typedef Node     node_type;  ///< Bucket node type
 394             typedef typename options::allocator allocator; ///< allocator
 395             typedef typename options::memory_model  memory_model; ///< Memory model for atomic operations
 396             typedef typename options::free_list free_list; ///< Free-list
 397
 398             /// Auxiliary node type
 399             struct aux_node_type: public node_type, public free_list::node
 400             {
 401 #           ifdef CDS_DEBUG
 402                 atomics::atomic<bool> m_busy;
 403
 404                 aux_node_type()
 405                 {
 406                     m_busy.store( false, atomics::memory_order_release );
 407                 }
 408 #           endif
 409             };
 410
 411             typedef atomics::atomic<aux_node_type *> table_entry;  ///< Table entry type
 412             typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator; ///< Bucket table allocator
 413
 414         protected:
 415             //@cond
 416             const size_t   m_nLoadFactor; ///< load factor (average count of items per bucket)
 417             const size_t   m_nCapacity;   ///< Bucket table capacity
 418             table_entry *  m_Table;       ///< Bucket table
 419
 420             typedef typename allocator::template rebind< aux_node_type >::other aux_node_allocator;
 421
 422             aux_node_type*          m_auxNode;           ///< Array of pre-allocated auxiliary nodes
 423             atomics::atomic<size_t> m_nAuxNodeAllocated; ///< how many auxiliary node allocated
 424             free_list               m_freeList;          ///< Free list
 425             //@endcond
 426
 427         protected:
 428             //@cond
 429             void allocate_table()
 430             {
 431                 m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr );
 432                 m_auxNode = aux_node_allocator().allocate( m_nCapacity );
 433             }
 434
 435             void destroy_table()
 436             {
 437                 m_freeList.clear( []( typename free_list::node* ) {} );
 438                 aux_node_allocator().deallocate( m_auxNode, m_nCapacity );
 439                 bucket_table_allocator().Delete( m_Table, m_nCapacity );
 440             }
 441             //@endcond
 442
 443         public:
 444             /// Constructs bucket table for 512K buckets. Load factor is 1.
 445             static_bucket_table()
 446                 : m_nLoadFactor(1)
 447                 , m_nCapacity( 512 * 1024 )
 448                 , m_nAuxNodeAllocated( 0 )
 449             {
 450                 allocate_table();
 451             }
 452
 453             /// Creates the table with specified size rounded up to nearest power-of-two
 454             static_bucket_table(
 455                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 456                 size_t nLoadFactor        ///< Load factor
 457                 )
 458                 : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 )
 459                 , m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ))
 460                 , m_nAuxNodeAllocated( 0 )
 461             {
 462                 // m_nCapacity must be power of 2
 463                 assert( cds::beans::is_power2( m_nCapacity ));
 464                 allocate_table();
 465             }
 466
 467             /// Destroys bucket table
 468             ~static_bucket_table()
 469             {
 470                 destroy_table();
 471             }
 472
 473             /// Returns head node of bucket \p nBucket
 474             aux_node_type * bucket( size_t nBucket ) const
 475             {
 476                 assert( nBucket < capacity());
 477                 return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
 478             }
 479
 480             /// Set \p pNode as a head of bucket \p nBucket
 481             void bucket( size_t nBucket, aux_node_type * pNode )
 482             {
 483                 assert( nBucket < capacity());
 484                 assert( bucket( nBucket ) == nullptr );
 485
 486                 m_Table[ nBucket ].store( pNode, memory_model::memory_order_release );
 487             }
 488
 489             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
 490             aux_node_type* alloc_aux_node()
 491             {
 492                 if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity()) {
 493                     // alloc next free node from m_auxNode
 494                     size_t const idx = m_nAuxNodeAllocated.fetch_add( 1, memory_model::memory_order_relaxed );
 495                     if ( idx < capacity()) {
 496                         CDS_TSAN_ANNOTATE_NEW_MEMORY( &m_auxNode[idx], sizeof( aux_node_type ));
 497                         return new( &m_auxNode[idx] ) aux_node_type();
 498                     }
 499                 }
 500
 501                 // get from free-list
 502                 auto pFree = m_freeList.get();
 503                 if ( pFree )
 504                     return static_cast<aux_node_type*>( pFree );
 505
 506                 // table exhausted
 507                 return nullptr;
 508             }
 509
 510             /// Places node type to free-list
 511             void free_aux_node( aux_node_type* p )
 512             {
 513                 m_freeList.put( static_cast<aux_node_type*>( p ));
 514             }
 515
 516             /// Returns the capacity of the bucket table
 517             size_t capacity() const
 518             {
 519                 return m_nCapacity;
 520             }
 521
 522             /// Returns the load factor, i.e. average count of items per bucket
 523             size_t load_factor() const
 524             {
 525                 return m_nLoadFactor;
 526             }
 527         };
 528
 529         /// Expandable bucket table
 530         /**
 531             This bucket table can dynamically grow its capacity when necessary
 532             up to maximum bucket count.
 533
 534             Template parameter:
 535             - \p GC - garbage collector
 536             - \p Node - node type, must be derived from \p split_list::node
 537             - \p Options... - options
 538
 539             \p Options are:
 540             - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
 541             - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
 542             - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS
 543                 otherwise \p FreeList.
 544             */
 545         template <typename GC, typename Node, typename... Options>
 546         class expandable_bucket_table
 547         {
 548             //@cond
 549             struct default_options
 550             {
 551                 typedef CDS_DEFAULT_ALLOCATOR       allocator;
 552                 typedef opt::v::relaxed_ordering    memory_model;
 553                 typedef FreeListImpl                free_list;
 554             };
 555             typedef typename opt::make_options< default_options, Options... >::type options;
 556             //@endcond
 557
 558         public:
 559             typedef GC       gc;                            ///< Garbage collector
 560             typedef Node     node_type;                     ///< Bucket node type
 561             typedef typename options::allocator allocator;  ///< allocator
 562
 563             /// Memory model for atomic operations
 564             typedef typename options::memory_model memory_model;
 565
 566             /// Free-list
 567             typedef typename options::free_list free_list;
 568
 569             /// Auxiliary node type
 570             struct aux_node_type: public node_type, public free_list::node
 571             {
 572 #           ifdef CDS_DEBUG
 573                 atomics::atomic<bool> m_busy;
 574
 575                 aux_node_type()
 576                 {
 577                     m_busy.store( false, atomics::memory_order_release );
 578                 }
 579 #           endif
 580             };
 581
 582         protected:
 583             //@cond
 584             typedef atomics::atomic<aux_node_type *> table_entry;    ///< Table entry type
 585             typedef atomics::atomic<table_entry *>   segment_type;   ///< Bucket table segment type
 586
 587             struct aux_node_segment {
 588                 atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment
 589                 aux_node_segment*         next_segment;
 590                 // aux_node_type     nodes[];
 591
 592                 aux_node_segment()
 593                     : next_segment( nullptr )
 594                 {
 595                     aux_node_count.store( 0, atomics::memory_order_release );
 596                 }
 597
 598                 aux_node_type* segment()
 599                 {
 600                     return reinterpret_cast<aux_node_type*>( this + 1 );
 601                 }
 602             };
 603
 604             /// Bucket table metrics
 605             struct metrics {
 606                 size_t    nSegmentCount;    ///< max count of segments in bucket table
 607                 size_t    nSegmentSize;     ///< the segment's capacity. The capacity must be power of two.
 608                 size_t    nSegmentSizeLog2; ///< <tt> log2( m_nSegmentSize )</tt>
 609                 size_t    nLoadFactor;      ///< load factor
 610                 size_t    nCapacity;        ///< max capacity of bucket table
 611
 612                 metrics()
 613                     : nSegmentCount( 1024 )
 614                     , nSegmentSize( 512 )
 615                     , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ))
 616                     , nLoadFactor( 1 )
 617                     , nCapacity( nSegmentCount * nSegmentSize )
 618                 {}
 619             };
 620
 621             /// Bucket table allocator
 622             typedef cds::details::Allocator< segment_type, allocator > bucket_table_allocator;
 623
 624             /// Bucket table segment allocator
 625             typedef cds::details::Allocator< table_entry, allocator > segment_allocator;
 626
 627             // Aux node segment allocator
 628             typedef typename allocator::template rebind<char>::other raw_allocator;
 629
 630             //@endcond
 631
 632         public:
 633             /// Constructs bucket table for 512K buckets. Load factor is 1.
 634             expandable_bucket_table()
 635                 : m_metrics( calc_metrics( 512 * 1024, 1 ))
 636             {
 637                 init();
 638             }
 639
 640             /// Creates the table with specified capacity rounded up to nearest power-of-two
 641             expandable_bucket_table(
 642                 size_t nItemCount,        ///< Max expected item count in split-ordered list
 643                 size_t nLoadFactor        ///< Load factor
 644                 )
 645                 : m_metrics( calc_metrics( nItemCount, nLoadFactor ))
 646             {
 647                 init();
 648             }
 649
 650             /// Destroys bucket table
 651             ~expandable_bucket_table()
 652             {
 653                 m_freeList.clear( []( typename free_list::node* ) {} );
 654
 655                 for ( auto aux_segment  = m_auxNodeList.load( atomics::memory_order_relaxed ); aux_segment; ) {
 656                     auto next_segment = aux_segment->next_segment;
 657                     free_aux_segment( aux_segment );
 658                     aux_segment = next_segment;
 659                 }
 660
 661                 segment_type * pSegments = m_Segments;
 662                 for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) {
 663                     table_entry* pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
 664                     if ( pEntry != nullptr )
 665                         destroy_segment( pEntry );
 666                 }
 667
 668                 destroy_table( pSegments );
 669             }
 670
 671             /// Returns head node of the bucket \p nBucket
 672             aux_node_type * bucket( size_t nBucket ) const
 673             {
 674                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 675                 assert( nSegment < m_metrics.nSegmentCount );
 676
 677                 table_entry* pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
 678                 if ( pSegment == nullptr )
 679                     return nullptr;    // uninitialized bucket
 680                 return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire);
 681             }
 682
 683             /// Set \p pNode as a head of bucket \p nBucket
 684             void bucket( size_t nBucket, aux_node_type * pNode )
 685             {
 686                 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
 687                 assert( nSegment < m_metrics.nSegmentCount );
 688
 689                 segment_type& segment = m_Segments[nSegment];
 690                 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
 691                     table_entry* pNewSegment = allocate_segment();
 692                     table_entry * pNull = nullptr;
 693                     if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed ))
 694                         destroy_segment( pNewSegment );
 695                 }
 696
 697                 assert( segment.load( atomics::memory_order_relaxed )[nBucket & (m_metrics.nSegmentSize - 1)].load( atomics::memory_order_relaxed ) == nullptr );
 698                 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
 699             }
 700
 701             /// Allocates auxiliary node; can return \p nullptr if the table exhausted
 702             aux_node_type* alloc_aux_node()
 703             {
 704                 aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_acquire );
 705
 706                 for ( ;; ) {
 707                     assert( aux_segment != nullptr );
 708
 709                     // try to allocate from current aux segment
 710                     if ( aux_segment->aux_node_count.load( memory_model::memory_order_acquire ) < m_metrics.nSegmentSize ) {
 711                         size_t idx = aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
 712                         if ( idx < m_metrics.nSegmentSize ) {
 713                             CDS_TSAN_ANNOTATE_NEW_MEMORY( aux_segment->segment() + idx, sizeof( aux_node_type ));
 714                             return new( aux_segment->segment() + idx ) aux_node_type();
 715                         }
 716                     }
 717
 718                     // try allocate from free-list
 719                     auto pFree = m_freeList.get();
 720                     if ( pFree )
 721                         return static_cast<aux_node_type*>( pFree );
 722
 723                     // free-list is empty, current segment is full
 724                     // try to allocate new aux segment
 725                     // We can allocate more aux segments than we need but it is not a problem in this context
 726                     aux_node_segment* new_aux_segment = allocate_aux_segment();
 727                     new_aux_segment->next_segment = aux_segment;
 728                     new_aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed );
 729
 730                     if ( m_auxNodeList.compare_exchange_strong( aux_segment, new_aux_segment, memory_model::memory_order_release, atomics::memory_order_acquire )) {
 731                         CDS_TSAN_ANNOTATE_NEW_MEMORY( new_aux_segment->segment(), sizeof( aux_node_type ));
 732                         return new( new_aux_segment->segment()) aux_node_type();
 733                     }
 734
 735                     free_aux_segment( new_aux_segment );
 736                 }
 737             }
 738
 739             /// Places auxiliary node type to free-list
 740             void free_aux_node( aux_node_type* p )
 741             {
 742                 m_freeList.put( static_cast<aux_node_type*>( p ));
 743             }
 744
 745             /// Returns the capacity of the bucket table
 746             size_t capacity() const
 747             {
 748                 return m_metrics.nCapacity;
 749             }
 750
 751             /// Returns the load factor, i.e. average count of items per bucket
 752             size_t load_factor() const
 753             {
 754                 return m_metrics.nLoadFactor;
 755             }
 756
 757         protected:
 758             //@cond
 759             metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
 760             {
 761                 metrics m;
 762
 763                 // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
 764                 m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
 765
 766                 size_t nBucketCount = ( nItemCount + m.nLoadFactor - 1 ) / m.nLoadFactor;
 767                 if ( nBucketCount <= 2 ) {
 768                     m.nSegmentCount = 1;
 769                     m.nSegmentSize = 2;
 770                 }
 771                 else if ( nBucketCount <= 1024 ) {
 772                     m.nSegmentCount = 1;
 773                     m.nSegmentSize = ((size_t)1) << beans::log2ceil( nBucketCount );
 774                 }
 775                 else {
 776                     nBucketCount = beans::log2ceil( nBucketCount );
 777                     m.nSegmentCount =
 778                         m.nSegmentSize = ((size_t)1) << (nBucketCount / 2);
 779                     if ( nBucketCount & 1 )
 780                         m.nSegmentSize *= 2;
 781                     if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
 782                         m.nSegmentSize *= 2;
 783                 }
 784                 m.nCapacity = m.nSegmentCount * m.nSegmentSize;
 785                 m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
 786                 assert( m.nSegmentSizeLog2 != 0 );   //
 787                 return m;
 788             }
 789
 790             segment_type * allocate_table()
 791             {
 792                 return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
 793             }
 794
 795             void destroy_table( segment_type * pTable )
 796             {
 797                 bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
 798             }
 799
 800             table_entry* allocate_segment()
 801             {
 802                 return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
 803             }
 804
 805             void destroy_segment( table_entry* pSegment )
 806             {
 807                 segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
 808             }
 809
 810             aux_node_segment* allocate_aux_segment()
 811             {
 812                 char* p = raw_allocator().allocate( sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize );
 813                 CDS_TSAN_ANNOTATE_NEW_MEMORY( p, sizeof( aux_node_segment ));
 814                 return new(p) aux_node_segment();
 815             }
 816
 817             void free_aux_segment( aux_node_segment* p )
 818             {
 819                 raw_allocator().deallocate( reinterpret_cast<char*>( p ), sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize );
 820             }
 821
 822             void init()
 823             {
 824                 // m_nSegmentSize must be 2**N
 825                 assert( cds::beans::is_power2( m_metrics.nSegmentSize ));
 826                 assert( (((size_t)1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
 827
 828                 // m_nSegmentCount must be 2**K
 829                 assert( cds::beans::is_power2( m_metrics.nSegmentCount ));
 830
 831                 m_Segments = allocate_table();
 832                 m_auxNodeList = allocate_aux_segment();
 833             }
 834             //@endcond
 835
 836         protected:
 837             //@cond
 838             metrics const       m_metrics;  ///< Dynamic bucket table metrics
 839             segment_type*       m_Segments; ///< bucket table - array of segments
 840             atomics::atomic<aux_node_segment*> m_auxNodeList;  ///< segment list of aux nodes
 841             free_list           m_freeList; ///< List of free aux nodes
 842             //@endcond
 843         };
 844
 845
 846         //@cond
 847         namespace details {
 848             template <bool Value, typename GC, typename Node, typename... Options>
 849             struct bucket_table_selector;
 850
 851             template <typename GC, typename Node, typename... Options>
 852             struct bucket_table_selector< true, GC, Node, Options...>
 853             {
 854                 typedef expandable_bucket_table<GC, Node, Options...>    type;
 855             };
 856
 857             template <typename GC, typename Node, typename... Options>
 858             struct bucket_table_selector< false, GC, Node, Options...>
 859             {
 860                 typedef static_bucket_table<GC, Node, Options...>    type;
 861             };
 862
 863             template <typename Q>
 864             struct search_value_type
 865             {
 866                 Q&      val;
 867                 size_t  nHash;
 868
 869                 search_value_type( Q& v, size_t h )
 870                     : val( v )
 871                     , nHash( h )
 872                 {}
 873             };
 874
 875             template <class OrderedList, class Traits, bool Iterable >
 876             class ordered_list_adapter;
 877
 878             template <class OrderedList, class Traits>
 879             class ordered_list_adapter< OrderedList, Traits, false >
 880             {
 881                 typedef OrderedList native_ordered_list;
 882                 typedef Traits      traits;
 883
 884                 typedef typename native_ordered_list::gc                gc;
 885                 typedef typename native_ordered_list::key_comparator    native_key_comparator;
 886                 typedef typename native_ordered_list::node_type         node_type;
 887                 typedef typename native_ordered_list::value_type        value_type;
 888                 typedef typename native_ordered_list::node_traits       native_node_traits;
 889                 typedef typename native_ordered_list::disposer          native_disposer;
 890
 891                 typedef split_list::node<node_type>                     splitlist_node_type;
 892
 893                 struct key_compare {
 894                     int operator()( value_type const& v1, value_type const& v2 ) const
 895                     {
 896                         splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( v1 ));
 897                         splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( v2 ));
 898                         if ( n1->m_nHash != n2->m_nHash )
 899                             return n1->m_nHash < n2->m_nHash ? -1 : 1;
 900
 901                         if ( n1->is_dummy()) {
 902                             assert( n2->is_dummy());
 903                             return 0;
 904                         }
 905
 906                         assert( !n1->is_dummy() && !n2->is_dummy());
 907
 908                         return native_key_comparator()(v1, v2);
 909                     }
 910
 911                     template <typename Q>
 912                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
 913                     {
 914                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( v ));
 915                         if ( n->m_nHash != q.nHash )
 916                             return n->m_nHash < q.nHash ? -1 : 1;
 917
 918                         assert( !n->is_dummy());
 919                         return native_key_comparator()(v, q.val);
 920                     }
 921
 922                     template <typename Q>
 923                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
 924                     {
 925                         return -operator()( v, q );
 926                     }
 927                 };
 928
 929                 struct wrapped_disposer
 930                 {
 931                     void operator()( value_type * v )
 932                     {
 933                         splitlist_node_type * p = static_cast<splitlist_node_type *>(native_node_traits::to_node_ptr( v ));
 934                         if ( !p->is_dummy())
 935                             native_disposer()(v);
 936                     }
 937                 };
 938
 939             public:
 940                 typedef node_type ordered_list_node_type;
 941                 typedef splitlist_node_type aux_node;
 942
 943                 struct node_traits: private native_node_traits
 944                 {
 945                     typedef native_node_traits              base_class;     ///< Base ordered list node type
 946                     typedef typename base_class::value_type value_type;     ///< Value type
 947                     typedef typename base_class::node_type  base_node_type; ///< Ordered list node type
 948                     typedef node<base_node_type>            node_type;      ///< Split-list node type
 949
 950                     /// Convert value reference to node pointer
 951                     static node_type * to_node_ptr( value_type& v )
 952                     {
 953                         return static_cast<node_type *>(base_class::to_node_ptr( v ));
 954                     }
 955
 956                     /// Convert value pointer to node pointer
 957                     static node_type * to_node_ptr( value_type * v )
 958                     {
 959                         return static_cast<node_type *>(base_class::to_node_ptr( v ));
 960                     }
 961
 962                     /// Convert value reference to node pointer (const version)
 963                     static node_type const * to_node_ptr( value_type const& v )
 964                     {
 965                         return static_cast<node_type const*>(base_class::to_node_ptr( v ));
 966                     }
 967
 968                     /// Convert value pointer to node pointer (const version)
 969                     static node_type const * to_node_ptr( value_type const * v )
 970                     {
 971                         return static_cast<node_type const *>(base_class::to_node_ptr( v ));
 972                     }
 973
 974                     /// Convert node reference to value pointer
 975                     static value_type * to_value_ptr( node_type&  n )
 976                     {
 977                         return base_class::to_value_ptr( static_cast<base_node_type &>(n));
 978                     }
 979
 980                     /// Convert node pointer to value pointer
 981                     static value_type * to_value_ptr( node_type *  n )
 982                     {
 983                         return base_class::to_value_ptr( static_cast<base_node_type *>(n));
 984                     }
 985
 986                     /// Convert node reference to value pointer (const version)
 987                     static const value_type * to_value_ptr( node_type const & n )
 988                     {
 989                         return base_class::to_value_ptr( static_cast<base_node_type const &>(n));
 990                     }
 991
 992                     /// Convert node pointer to value pointer (const version)
 993                     static const value_type * to_value_ptr( node_type const * n )
 994                     {
 995                         return base_class::to_value_ptr( static_cast<base_node_type const *>(n));
 996                     }
 997                 };
 998
 999                 template <typename Less>
1000                 struct make_compare_from_less: public cds::opt::details::make_comparator_from_less<Less>
1001                 {
1002                     typedef cds::opt::details::make_comparator_from_less<Less>  base_class;
1003
1004                     template <typename Q>
1005                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
1006                     {
1007                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( v ));
1008                         if ( n->m_nHash != q.nHash )
1009                             return n->m_nHash < q.nHash ? -1 : 1;
1010
1011                         assert( !n->is_dummy());
1012                         return base_class()(v, q.val);
1013                     }
1014
1015                     template <typename Q>
1016                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
1017                     {
1018                         splitlist_node_type const * n = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( v ));
1019                         if ( n->m_nHash != q.nHash )
1020                             return q.nHash < n->m_nHash ? -1 : 1;
1021
1022                         assert( !n->is_dummy());
1023                         return base_class()(q.val, v);
1024                     }
1025
1026                     int operator()( value_type const& lhs, value_type const& rhs ) const
1027                     {
1028                         splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( lhs ));
1029                         splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( rhs ));
1030                         if ( n1->m_nHash != n2->m_nHash )
1031                             return n1->m_nHash < n2->m_nHash ? -1 : 1;
1032
1033                         if ( n1->is_dummy()) {
1034                             assert( n2->is_dummy());
1035                             return 0;
1036                         }
1037
1038                         assert( !n1->is_dummy() && !n2->is_dummy());
1039
1040                         return native_key_comparator()( lhs, rhs );
1041                     }
1042                 };
1043
1044                 typedef typename native_ordered_list::template rebind_traits<
1045                     opt::compare< key_compare >
1046                     , opt::disposer< wrapped_disposer >
1047                     , opt::boundary_node_type< splitlist_node_type >
1048                 >::type result;
1049             };
1050
1051             template <class OrderedList, class Traits>
1052             class ordered_list_adapter< OrderedList, Traits, true >
1053             {
1054                 typedef OrderedList native_ordered_list;
1055                 typedef Traits      traits;
1056
1057                 typedef typename native_ordered_list::gc                gc;
1058                 typedef typename native_ordered_list::key_comparator    native_key_comparator;
1059                 typedef typename native_ordered_list::value_type        value_type;
1060                 typedef typename native_ordered_list::disposer          native_disposer;
1061
1062                 struct key_compare {
1063                     int operator()( value_type const& v1, value_type const& v2 ) const
1064                     {
1065                         hash_node const& n1 = static_cast<hash_node const&>( v1 );
1066                         hash_node const& n2 = static_cast<hash_node const&>( v2 );
1067                         if ( n1.m_nHash != n2.m_nHash )
1068                             return n1.m_nHash < n2.m_nHash ? -1 : 1;
1069
1070                         if ( n1.is_dummy()) {
1071                             assert( n2.is_dummy());
1072                             return 0;
1073                         }
1074
1075                         assert( !n1.is_dummy() && !n2.is_dummy());
1076
1077                         return native_key_comparator()(v1, v2);
1078                     }
1079
1080                     template <typename Q>
1081                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
1082                     {
1083                         hash_node const& n = static_cast<hash_node const&>( v );
1084                         if ( n.m_nHash != q.nHash )
1085                             return n.m_nHash < q.nHash ? -1 : 1;
1086
1087                         assert( !n.is_dummy());
1088                         return native_key_comparator()(v, q.val);
1089                     }
1090
1091                     template <typename Q>
1092                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
1093                     {
1094                         return -operator()( v, q );
1095                     }
1096                 };
1097
1098                 struct wrapped_disposer
1099                 {
1100                     void operator()( value_type * v )
1101                     {
1102                         if ( !static_cast<hash_node*>( v )->is_dummy())
1103                             native_disposer()( v );
1104                     }
1105                 };
1106
1107             public:
1108                 typedef void ordered_list_node_type;
1109
1110                 struct aux_node: public native_ordered_list::node_type, public hash_node
1111                 {
1112                     aux_node()
1113                     {
1114                         typedef typename native_ordered_list::node_type list_node_type;
1115
1116                         list_node_type::data.store( typename list_node_type::marked_data_ptr(
1117                             static_cast<value_type*>( static_cast<hash_node *>( this ))),
1118                             atomics::memory_order_release
1119                         );
1120                     }
1121                 };
1122
1123                 struct node_traits
1124                 {
1125                     static hash_node * to_node_ptr( value_type& v )
1126                     {
1127                         return static_cast<hash_node *>( &v );
1128                     }
1129
1130                     static hash_node * to_node_ptr( value_type * v )
1131                     {
1132                         return static_cast<hash_node *>( v );
1133                     }
1134
1135                     static hash_node const * to_node_ptr( value_type const& v )
1136                     {
1137                         return static_cast<hash_node const*>( &v );
1138                     }
1139
1140                     static hash_node const * to_node_ptr( value_type const * v )
1141                     {
1142                         return static_cast<hash_node const *>( v );
1143                     }
1144                 };
1145
1146                 template <typename Less>
1147                 struct make_compare_from_less: public cds::opt::details::make_comparator_from_less<Less>
1148                 {
1149                     typedef cds::opt::details::make_comparator_from_less<Less>  base_class;
1150
1151                     template <typename Q>
1152                     int operator()( value_type const& v, search_value_type<Q> const& q ) const
1153                     {
1154                         hash_node const& n = static_cast<hash_node const&>( v );
1155                         if ( n.m_nHash != q.nHash )
1156                             return n.m_nHash < q.nHash ? -1 : 1;
1157
1158                         assert( !n.is_dummy());
1159                         return base_class()(v, q.val);
1160                     }
1161
1162                     template <typename Q>
1163                     int operator()( search_value_type<Q> const& q, value_type const& v ) const
1164                     {
1165                         hash_node const& n = static_cast<hash_node const&>( v );
1166                         if ( n.m_nHash != q.nHash )
1167                             return q.nHash < n.m_nHash ? -1 : 1;
1168
1169                         assert( !n.is_dummy());
1170                         return base_class()(q.val, v);
1171                     }
1172
1173                     int operator()( value_type const& lhs, value_type const& rhs ) const
1174                     {
1175                         hash_node const& n1 = static_cast<hash_node const&>( lhs );
1176                         hash_node const& n2 = static_cast<hash_node const&>( rhs );
1177                         if ( n1.m_nHash != n2.m_nHash )
1178                             return n1.m_nHash < n2.m_nHash ? -1 : 1;
1179
1180                         if ( n1.is_dummy()) {
1181                             assert( n2.is_dummy());
1182                             return 0;
1183                         }
1184
1185                         assert( !n1.is_dummy() && !n2.is_dummy());
1186
1187                         return base_class()( lhs, rhs );
1188                     }
1189                 };
1190
1191                 typedef typename native_ordered_list::template rebind_traits<
1192                     opt::compare< key_compare >
1193                     , opt::disposer< wrapped_disposer >
1194                     , opt::boundary_node_type< aux_node >
1195                 >::type result;
1196             };
1197
1198             template <class OrderedList, class Traits>
1199             using rebind_list_traits = ordered_list_adapter< OrderedList, Traits, is_iterable_list<OrderedList>::value >;
1200
1201             template <typename OrderedList, bool IsConst>
1202             struct select_list_iterator;
1203
1204             template <typename OrderedList>
1205             struct select_list_iterator<OrderedList, false>
1206             {
1207                 typedef typename OrderedList::iterator  type;
1208             };
1209
1210             template <typename OrderedList>
1211             struct select_list_iterator<OrderedList, true>
1212             {
1213                 typedef typename OrderedList::const_iterator  type;
1214             };
1215
1216             template <typename NodeTraits, typename OrderedList, bool IsConst>
1217             class iterator_type
1218             {
1219                 typedef OrderedList     ordered_list_type;
1220                 friend class iterator_type <NodeTraits, OrderedList, !IsConst >;
1221
1222             protected:
1223                 typedef typename select_list_iterator<ordered_list_type, IsConst>::type    list_iterator;
1224                 typedef NodeTraits      node_traits;
1225
1226             private:
1227                 list_iterator   m_itCur;
1228                 list_iterator   m_itEnd;
1229
1230             public:
1231                 typedef typename list_iterator::value_ptr   value_ptr;
1232                 typedef typename list_iterator::value_ref   value_ref;
1233
1234             public:
1235                 iterator_type()
1236                 {}
1237
1238                 iterator_type( iterator_type const& src )
1239                     : m_itCur( src.m_itCur )
1240                     , m_itEnd( src.m_itEnd )
1241                 {}
1242
1243                 // This ctor should be protected...
1244                 iterator_type( list_iterator itCur, list_iterator itEnd )
1245                     : m_itCur( itCur )
1246                     , m_itEnd( itEnd )
1247                 {
1248                     // skip dummy nodes
1249                     while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy())
1250                         ++m_itCur;
1251                 }
1252
1253                 value_ptr operator ->() const
1254                 {
1255                     return m_itCur.operator->();
1256                 }
1257
1258                 value_ref operator *() const
1259                 {
1260                     return m_itCur.operator*();
1261                 }
1262
1263                 /// Pre-increment
1264                 iterator_type& operator ++()
1265                 {
1266                     if ( m_itCur != m_itEnd ) {
1267                         do {
1268                             ++m_itCur;
1269                         } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy());
1270                     }
1271                     return *this;
1272                 }
1273
1274                 iterator_type& operator = (iterator_type const& src)
1275                 {
1276                     m_itCur = src.m_itCur;
1277                     m_itEnd = src.m_itEnd;
1278                     return *this;
1279                 }
1280
1281                 template <bool C>
1282                 bool operator ==(iterator_type<node_traits, ordered_list_type, C> const& i ) const
1283                 {
1284                     return m_itCur == i.m_itCur;
1285                 }
1286                 template <bool C>
1287                 bool operator !=(iterator_type<node_traits, ordered_list_type, C> const& i ) const
1288                 {
1289                     return m_itCur != i.m_itCur;
1290                 }
1291
1292             protected:
1293                 list_iterator const& underlying_iterator() const
1294                 {
1295                     return m_itCur;
1296                 }
1297             };
1298         }   // namespace details
1299         //@endcond
1300
1301         //@cond
1302         // Helper functions
1303         template <typename BitReversalAlgo>
1304         static inline size_t regular_hash( size_t nHash )
1305         {
1306             return static_cast<size_t>( BitReversalAlgo()( cds::details::size_t_cast( nHash ))) | size_t(1);
1307         }
1308
1309         template <typename BitReversalAlgo>
1310         static inline size_t dummy_hash( size_t nHash )
1311         {
1312             return static_cast<size_t>( BitReversalAlgo()( cds::details::size_t_cast( nHash ))) & ~size_t(1);
1313         }
1314         //@endcond
1315
1316     } // namespace split_list
1317
1318     //@cond
1319     // Forward declaration
1320     template <class GC, class OrderedList, class Traits = split_list::traits>
1321     class SplitListSet;
1322     //@endcond
1323
1324 }}  // namespace cds::intrusive
1325
1326 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H