2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H
32 #define CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H
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>
41 namespace cds { namespace intrusive {
43 /// Split-ordered list related definitions
44 /** @ingroup cds_intrusive_helper
46 namespace split_list {
47 /// Split-ordered list node
50 - OrderedListNode - node type for underlying ordered list
52 template <typename OrderedListNode>
53 struct node: public OrderedListNode
56 typedef OrderedListNode base_class;
59 size_t m_nHash ; ///< Hash value for node
61 /// Default constructor
68 /// Initializes dummy node with \p nHash value
75 /// Checks if the node is dummy node
78 return (m_nHash & 1) == 0;
82 /// SplitListSet internal statistics. May be used for debugging or profiling
84 Template argument \p Counter defines type of counter.
85 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
86 strict event counting.
87 You may use stronger type of counter like as \p cds::atomicity::item_counter,
88 or even integral type, for example, \p int.
90 template <typename Counter = cds::atomicity::event_counter >
93 typedef Counter counter_type; ///< Counter type
95 counter_type m_nInsertSuccess; ///< Count of success inserting
96 counter_type m_nInsertFailed; ///< Count of failed inserting
97 counter_type m_nEnsureNew; ///< Count of new item created by \p ensure() member function
98 counter_type m_nEnsureExist; ///< Count of \p ensure() call for existing item
99 counter_type m_nEraseSuccess; ///< Count of success erasing of items
100 counter_type m_nEraseFailed; ///< Count of attempts to erase unknown item
101 counter_type m_nExtractSuccess; ///< Count of success extracting of items
102 counter_type m_nExtractFailed; ///< Count of attempts to extract unknown item
103 counter_type m_nFindSuccess; ///< Count of success finding
104 counter_type m_nFindFailed; ///< Count of failed finding
105 counter_type m_nHeadNodeAllocated; ///< Count of allocated head node
106 counter_type m_nHeadNodeFreed; ///< Count of freed head node
107 counter_type m_nBucketCount; ///< Current bucket count
108 counter_type m_nInitBucketRecursive; ///< Count of recursive bucket initialization
109 counter_type m_nInitBucketContention; ///< Count of bucket init contention encountered
110 counter_type m_nBusyWaitBucketInit; ///< Count of busy wait cycle while a bucket is initialized
113 void onInsertSuccess() { ++m_nInsertSuccess; }
114 void onInsertFailed() { ++m_nInsertFailed; }
115 void onEnsureNew() { ++m_nEnsureNew; }
116 void onEnsureExist() { ++m_nEnsureExist; }
117 void onEraseSuccess() { ++m_nEraseSuccess; }
118 void onEraseFailed() { ++m_nEraseFailed; }
119 void onExtractSuccess() { ++m_nExtractSuccess; }
120 void onExtractFailed() { ++m_nExtractFailed; }
121 void onFindSuccess() { ++m_nFindSuccess; }
122 void onFindFailed() { ++m_nFindFailed; }
123 bool onFind(bool bSuccess)
131 void onHeadNodeAllocated() { ++m_nHeadNodeAllocated; }
132 void onHeadNodeFreed() { ++m_nHeadNodeFreed; }
133 void onNewBucket() { ++m_nBucketCount; }
134 void onRecursiveInitBucket() { ++m_nInitBucketRecursive; }
135 void onBucketInitContenton() { ++m_nInitBucketContention; }
136 void onBusyWaitBucketInit() { ++m_nBusyWaitBucketInit; }
140 /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p split_list::stat
143 void onInsertSuccess() const {}
144 void onInsertFailed() const {}
145 void onEnsureNew() const {}
146 void onEnsureExist() const {}
147 void onEraseSuccess() const {}
148 void onEraseFailed() const {}
149 void onExtractSuccess() const {}
150 void onExtractFailed() const {}
151 void onFindSuccess() const {}
152 void onFindFailed() const {}
153 bool onFind( bool bSuccess ) const { return bSuccess; }
154 void onHeadNodeAllocated() const {}
155 void onHeadNodeFreed() const {}
156 void onNewBucket() const {}
157 void onRecursiveInitBucket() const {}
158 void onBucketInitContenton() const {}
159 void onBusyWaitBucketInit() const {}
163 /// SplitListSet traits
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.
172 typedef opt::none hash;
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.
180 Default is \p cds::atomicity::item_counter.
182 typedef cds::atomicity::item_counter item_counter;
184 /// Bucket table allocator
186 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
188 typedef CDS_DEFAULT_ALLOCATOR allocator;
190 /// Internal statistics (by default, disabled)
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.
196 typedef split_list::empty_stat stat;
199 /// C++ memory ordering model
201 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
202 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
204 typedef opt::v::relaxed_ordering memory_model;
206 /// What type of bucket table is used
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.
215 static const bool dynamic_bucket_table = true;
217 /// Back-off strategy
218 typedef cds::backoff::Default back_off;
221 /// [value-option] Split-list dynamic bucket table option
223 The option is used to select bucket table implementation.
224 Possible values of \p Value are:
225 - \p true - select \p expandable_bucket_table
226 - \p false - select \p static_bucket_table
228 template <bool Value>
229 struct dynamic_bucket_table
232 template <typename Base> struct pack: public Base
234 enum { dynamic_bucket_table = Value };
239 /// Metafunction converting option list to \p split_list::traits
241 Available \p Options:
242 - \p opt::hash - mandatory option, specifies hash functor.
243 - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
245 - \p opt::memory_model - C++ memory model for atomic operations.
246 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
247 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
248 - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
249 - \p split_list::dynamic_bucket_table - use dynamic or static bucket table implementation.
250 Dynamic bucket table expands its size up to maximum bucket count when necessary
251 - \p opt::back_off - back-off strategy used for spinning, defult is \p cds::backoff::Default.
252 - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled).
253 To enable internal statistics use \p split_list::stat.
255 template <typename... Options>
257 typedef typename cds::opt::make_options< traits, Options...>::type type ; ///< Result of metafunction
260 /// Static bucket table
262 Non-resizeable bucket table for \p SplitListSet class.
263 The capacity of table (max bucket count) is defined in the constructor call.
266 - \p GC - garbage collector
267 - \p Node - node type, must be a type based on \p split_list::node
268 - \p Options... - options
271 - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
272 - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
274 template <typename GC, typename Node, typename... Options>
275 class static_bucket_table
278 struct default_options
280 typedef CDS_DEFAULT_ALLOCATOR allocator;
281 typedef opt::v::relaxed_ordering memory_model;
283 typedef typename opt::make_options< default_options, Options... >::type options;
287 typedef GC gc; ///< Garbage collector
288 typedef Node node_type; ///< Bucket node type
289 typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
291 /// Bucket table allocator
292 typedef cds::details::Allocator< table_entry, typename options::allocator > bucket_table_allocator;
294 /// Memory model for atomic operations
295 typedef typename options::memory_model memory_model;
298 const size_t m_nLoadFactor; ///< load factor (average count of items per bucket)
299 const size_t m_nCapacity; ///< Bucket table capacity
300 table_entry * m_Table; ///< Bucket table
304 void allocate_table()
306 m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr );
311 bucket_table_allocator().Delete( m_Table, m_nCapacity );
316 /// Constructs bucket table for 512K buckets. Load factor is 1.
317 static_bucket_table()
319 , m_nCapacity( 512 * 1024 )
324 /// Creates the table with specified size rounded up to nearest power-of-two
326 size_t nItemCount, ///< Max expected item count in split-ordered list
327 size_t nLoadFactor ///< Load factor
329 : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 ),
330 m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) )
332 // m_nCapacity must be power of 2
333 assert( cds::beans::is_power2( m_nCapacity ) );
337 /// Destroys bucket table
338 ~static_bucket_table()
343 /// Returns head node of bucket \p nBucket
344 node_type * bucket( size_t nBucket ) const
346 assert( nBucket < capacity() );
347 return m_Table[ nBucket ].load(memory_model::memory_order_acquire);
350 /// Set \p pNode as a head of bucket \p nBucket
351 void bucket( size_t nBucket, node_type * pNode )
353 assert( nBucket < capacity() );
354 assert( bucket( nBucket ) == nullptr );
356 m_Table[ nBucket ].store( pNode, memory_model::memory_order_release );
359 /// Returns the capacity of the bucket table
360 size_t capacity() const
365 /// Returns the load factor, i.e. average count of items per bucket
366 size_t load_factor() const
368 return m_nLoadFactor;
372 /// Expandable bucket table
374 This bucket table can dynamically grow its capacity when necessary
375 up to maximum bucket count.
378 - \p GC - garbage collector
379 - \p Node - node type, must be derived from \p split_list::node
380 - \p Options... - options
383 - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
384 - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering
386 template <typename GC, typename Node, typename... Options>
387 class expandable_bucket_table
390 struct default_options
392 typedef CDS_DEFAULT_ALLOCATOR allocator;
393 typedef opt::v::relaxed_ordering memory_model;
395 typedef typename opt::make_options< default_options, Options... >::type options;
398 typedef GC gc; ///< Garbage collector
399 typedef Node node_type; ///< Bucket node type
400 typedef atomics::atomic<node_type *> table_entry; ///< Table entry type
402 /// Memory model for atomic operations
403 typedef typename options::memory_model memory_model;
406 typedef atomics::atomic<table_entry *> segment_type; ///< Bucket table segment type
409 /// Bucket table allocator
410 typedef cds::details::Allocator< segment_type, typename options::allocator > bucket_table_allocator;
412 /// Bucket table segment allocator
413 typedef cds::details::Allocator< table_entry, typename options::allocator > segment_allocator;
416 /// Bucket table metrics
418 size_t nSegmentCount; ///< max count of segments in bucket table
419 size_t nSegmentSize; ///< the segment's capacity. The capacity must be power of two.
420 size_t nSegmentSizeLog2; ///< <tt> log2( m_nSegmentSize )</tt>
421 size_t nLoadFactor; ///< load factor
422 size_t nCapacity; ///< max capacity of bucket table
426 : nSegmentCount(1024)
428 , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ) )
430 , nCapacity( nSegmentCount * nSegmentSize )
434 const metrics m_metrics; ///< Dynamic bucket table metrics
437 segment_type * m_Segments; ///< bucket table - array of segments
441 metrics calc_metrics( size_t nItemCount, size_t nLoadFactor )
445 // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount
446 m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1;
448 size_t nBucketCount = (size_t)( ((float) nItemCount) / m.nLoadFactor );
449 if ( nBucketCount <= 2 ) {
453 else if ( nBucketCount <= 1024 ) {
455 m.nSegmentSize = ((size_t) 1) << beans::log2ceil( nBucketCount );
458 nBucketCount = beans::log2ceil( nBucketCount );
460 m.nSegmentSize = ((size_t) 1) << ( nBucketCount / 2 );
461 if ( nBucketCount & 1 )
463 if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount )
466 m.nCapacity = m.nSegmentCount * m.nSegmentSize;
467 m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize );
468 assert( m.nSegmentSizeLog2 != 0 ) ; //
472 segment_type * allocate_table()
474 return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr );
477 void destroy_table( segment_type * pTable )
479 bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount );
482 table_entry * allocate_segment()
484 return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr );
487 void destroy_segment( table_entry * pSegment )
489 segment_allocator().Delete( pSegment, m_metrics.nSegmentSize );
494 // m_nSegmentSize must be 2**N
495 assert( cds::beans::is_power2( m_metrics.nSegmentSize ));
496 assert( ( ((size_t) 1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize );
498 // m_nSegmentCount must be 2**K
499 assert( cds::beans::is_power2( m_metrics.nSegmentCount ));
501 m_Segments = allocate_table();
507 /// Constructs bucket table for 512K buckets. Load factor is 1.
508 expandable_bucket_table()
509 : m_metrics( calc_metrics( 512 * 1024, 1 ))
514 /// Creates the table with specified capacity rounded up to nearest power-of-two
515 expandable_bucket_table(
516 size_t nItemCount, ///< Max expected item count in split-ordered list
517 size_t nLoadFactor ///< Load factor
519 : m_metrics( calc_metrics( nItemCount, nLoadFactor ))
524 /// Destroys bucket table
525 ~expandable_bucket_table()
527 segment_type * pSegments = m_Segments;
528 for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) {
529 table_entry * pEntry = pSegments[i].load(memory_model::memory_order_relaxed);
530 if ( pEntry != nullptr )
531 destroy_segment( pEntry );
533 destroy_table( pSegments );
536 /// Returns head node of the bucket \p nBucket
537 node_type * bucket( size_t nBucket ) const
539 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
540 assert( nSegment < m_metrics.nSegmentCount );
542 table_entry * pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire);
543 if ( pSegment == nullptr )
544 return nullptr; // uninitialized bucket
545 return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire);
548 /// Set \p pNode as a head of bucket \p nBucket
549 void bucket( size_t nBucket, node_type * pNode )
551 size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2;
552 assert( nSegment < m_metrics.nSegmentCount );
554 segment_type& segment = m_Segments[nSegment];
555 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
556 table_entry * pNewSegment = allocate_segment();
557 table_entry * pNull = nullptr;
558 if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
559 destroy_segment( pNewSegment );
562 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
565 /// Returns the capacity of the bucket table
566 size_t capacity() const
568 return m_metrics.nCapacity;
571 /// Returns the load factor, i.e. average count of items per bucket
572 size_t load_factor() const
574 return m_metrics.nLoadFactor;
578 /// Split-list node traits
580 This traits is intended for converting between underlying ordered list node type
581 and split-list node type
584 - \p BaseNodeTraits - node traits of base ordered list type
586 template <class BaseNodeTraits>
587 struct node_traits: private BaseNodeTraits
589 typedef BaseNodeTraits base_class; ///< Base ordered list node type
590 typedef typename base_class::value_type value_type; ///< Value type
591 typedef typename base_class::node_type base_node_type; ///< Ordered list node type
592 typedef node<base_node_type> node_type; ///< Spit-list node type
594 /// Convert value reference to node pointer
595 static node_type * to_node_ptr( value_type& v )
597 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
600 /// Convert value pointer to node pointer
601 static node_type * to_node_ptr( value_type * v )
603 return static_cast<node_type *>( base_class::to_node_ptr( v ) );
606 /// Convert value reference to node pointer (const version)
607 static node_type const * to_node_ptr( value_type const& v )
609 return static_cast<node_type const*>( base_class::to_node_ptr( v ) );
612 /// Convert value pointer to node pointer (const version)
613 static node_type const * to_node_ptr( value_type const * v )
615 return static_cast<node_type const *>( base_class::to_node_ptr( v ) );
618 /// Convert node refernce to value pointer
619 static value_type * to_value_ptr( node_type& n )
621 return base_class::to_value_ptr( static_cast<base_node_type &>( n ) );
624 /// Convert node pointer to value pointer
625 static value_type * to_value_ptr( node_type * n )
627 return base_class::to_value_ptr( static_cast<base_node_type *>( n ) );
630 /// Convert node reference to value pointer (const version)
631 static const value_type * to_value_ptr( node_type const & n )
633 return base_class::to_value_ptr( static_cast<base_node_type const &>( n ) );
636 /// Convert node pointer to value pointer (const version)
637 static const value_type * to_value_ptr( node_type const * n )
639 return base_class::to_value_ptr( static_cast<base_node_type const *>( n ) );
645 template <bool Value, typename GC, typename Node, typename... Options>
646 struct bucket_table_selector;
648 template <typename GC, typename Node, typename... Options>
649 struct bucket_table_selector< true, GC, Node, Options...>
651 typedef expandable_bucket_table<GC, Node, Options...> type;
654 template <typename GC, typename Node, typename... Options>
655 struct bucket_table_selector< false, GC, Node, Options...>
657 typedef static_bucket_table<GC, Node, Options...> type;
660 template <typename GC, class Alloc >
661 struct dummy_node_disposer {
662 template <typename Node>
663 void operator()( Node * p )
665 typedef cds::details::Allocator< Node, Alloc > node_deallocator;
666 node_deallocator().Delete( p );
670 template <typename Q>
671 struct search_value_type
676 search_value_type( Q& v, size_t h )
682 template <class OrderedList, class Traits>
683 class rebind_list_traits
685 typedef OrderedList native_ordered_list;
686 typedef Traits traits;
688 typedef typename native_ordered_list::gc gc;
689 typedef typename native_ordered_list::key_comparator native_key_comparator;
690 typedef typename native_ordered_list::node_type node_type;
691 typedef typename native_ordered_list::value_type value_type;
692 typedef typename native_ordered_list::node_traits node_traits;
693 typedef typename native_ordered_list::disposer native_disposer;
695 typedef split_list::node<node_type> splitlist_node_type;
698 int operator()( value_type const& v1, value_type const& v2 ) const
700 splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v1 ));
701 splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v2 ));
702 if ( n1->m_nHash != n2->m_nHash )
703 return n1->m_nHash < n2->m_nHash ? -1 : 1;
705 if ( n1->is_dummy() ) {
706 assert( n2->is_dummy() );
710 assert( !n1->is_dummy() && !n2->is_dummy() );
712 return native_key_comparator()( v1, v2 );
715 template <typename Q>
716 int operator()( value_type const& v, search_value_type<Q> const& q ) const
718 splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
719 if ( n->m_nHash != q.nHash )
720 return n->m_nHash < q.nHash ? -1 : 1;
722 assert( !n->is_dummy() );
723 return native_key_comparator()( v, q.val );
726 template <typename Q>
727 int operator()( search_value_type<Q> const& q, value_type const& v ) const
729 return -operator()( v, q );
733 struct wrapped_disposer
735 void operator()( value_type * v )
737 splitlist_node_type * p = static_cast<splitlist_node_type *>( node_traits::to_node_ptr( v ));
739 dummy_node_disposer<gc, typename traits::allocator>()( p );
741 native_disposer()( v );
746 template <typename Less>
747 struct make_compare_from_less: public cds::opt::details::make_comparator_from_less<Less>
749 typedef cds::opt::details::make_comparator_from_less<Less> base_class;
751 template <typename Q>
752 int operator()( value_type const& v, search_value_type<Q> const& q ) const
754 splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
755 if ( n->m_nHash != q.nHash )
756 return n->m_nHash < q.nHash ? -1 : 1;
758 assert( !n->is_dummy() );
759 return base_class()( v, q.val );
762 template <typename Q>
763 int operator()( search_value_type<Q> const& q, value_type const& v ) const
765 splitlist_node_type const * n = static_cast<splitlist_node_type const *>( node_traits::to_node_ptr( v ));
766 if ( n->m_nHash != q.nHash )
767 return q.nHash < n->m_nHash ? -1 : 1;
769 assert( !n->is_dummy() );
770 return base_class()( q.val, v );
773 template <typename Q1, typename Q2>
774 int operator()( Q1 const& v1, Q2 const& v2 ) const
776 return base_class()( v1, v2 );
780 typedef typename native_ordered_list::template rebind_traits<
781 opt::compare< key_compare >
782 ,opt::disposer< wrapped_disposer >
783 ,opt::boundary_node_type< splitlist_node_type >
787 template <typename OrderedList, bool IsConst>
788 struct select_list_iterator;
790 template <typename OrderedList>
791 struct select_list_iterator<OrderedList, false>
793 typedef typename OrderedList::iterator type;
796 template <typename OrderedList>
797 struct select_list_iterator<OrderedList, true>
799 typedef typename OrderedList::const_iterator type;
802 template <typename NodeTraits, typename OrderedList, bool IsConst>
805 typedef OrderedList ordered_list_type;
806 friend class iterator_type <NodeTraits, OrderedList, !IsConst >;
809 typedef typename select_list_iterator<ordered_list_type, IsConst>::type list_iterator;
810 typedef NodeTraits node_traits;
813 list_iterator m_itCur;
814 list_iterator m_itEnd;
817 typedef typename list_iterator::value_ptr value_ptr;
818 typedef typename list_iterator::value_ref value_ref;
824 iterator_type( iterator_type const& src )
825 : m_itCur( src.m_itCur )
826 , m_itEnd( src.m_itEnd )
829 // This ctor should be protected...
830 iterator_type( list_iterator itCur, list_iterator itEnd )
835 while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() )
839 value_ptr operator ->() const
841 return m_itCur.operator->();
844 value_ref operator *() const
846 return m_itCur.operator*();
850 iterator_type& operator ++()
852 if ( m_itCur != m_itEnd ) {
855 } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() );
860 iterator_type& operator = (iterator_type const& src)
862 m_itCur = src.m_itCur;
863 m_itEnd = src.m_itEnd;
868 bool operator ==(iterator_type<node_traits, ordered_list_type, C> const& i ) const
870 return m_itCur == i.m_itCur;
873 bool operator !=(iterator_type<node_traits, ordered_list_type, C> const& i ) const
875 return m_itCur != i.m_itCur;
878 } // namespace details
884 /// Reverses bit order in \p nHash
885 static inline size_t reverse_bits( size_t nHash )
887 return bitop::RBO( nHash );
890 static inline size_t regular_hash( size_t nHash )
892 return reverse_bits( nHash ) | size_t(1);
895 static inline size_t dummy_hash( size_t nHash )
897 return reverse_bits( nHash ) & ~size_t(1);
901 } // namespace split_list
904 // Forward declaration
905 template <class GC, class OrderedList, class Traits = split_list::traits>
909 }} // namespace cds::intrusive
911 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H