3 #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
4 #define __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
6 #include <cds/intrusive/details/base.h>
7 #include <cds/opt/compare.h>
8 #include <cds/opt/hash.h>
9 #include <cds/algo/bitop.h>
10 #include <cds/cxx11_atomic.h>
13 namespace cds { namespace intrusive {
15 /// MichaelHashSet related definitions
16 /** @ingroup cds_intrusive_helper
18 namespace michael_set {
20 /// Type traits for MichaelHashSet class
24 Hash function converts the key fields of struct \p T stored in the hash-set
25 into value of type \p size_t called hash value that is an index of hash table.
27 This is mandatory type and has no predefined one.
29 typedef opt::none hash;
33 The item counting is an important part of MichaelHashSet algorithm:
34 the <tt>empty()</tt> member function depends on correct item counting.
35 Therefore, atomicity::empty_item_counter is not allowed as a type of the option.
37 Default is atomicity::item_counter.
39 typedef atomicity::item_counter item_counter;
41 /// Bucket table allocator
43 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
44 The allocator uses only in ctor (for allocating bucket table)
45 and in dtor (for destroying bucket table)
47 typedef CDS_DEFAULT_ALLOCATOR allocator;
50 /// Metafunction converting option list to traits struct
52 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
55 - opt::hash - mandatory option, specifies hash functor.
56 - opt::item_counter - optional, specifies item counting policy. See type_traits::item_counter
58 - opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
60 See \ref MichaelHashSet, \ref type_traits.
62 template <typename... Options>
64 typedef typename cds::opt::make_options< type_traits, Options...>::type type ; ///< Result of metafunction
69 static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
71 if ( nLoadFactor == 0 )
73 if ( nMaxItemCount == 0 )
75 const size_t nBucketCount = (size_t)( nMaxItemCount / nLoadFactor );
76 const size_t nLog2 = cds::bitop::MSB( nBucketCount );
78 return (( size_t( 1 << nLog2 ) < nBucketCount ? size_t( 1 << (nLog2 + 1) ) : size_t( 1 << nLog2 ))) - 1;
81 template <typename OrderedList, bool IsConst>
82 struct list_iterator_selector;
84 template <typename OrderedList>
85 struct list_iterator_selector< OrderedList, false>
87 typedef OrderedList * bucket_ptr;
88 typedef typename OrderedList::iterator type;
91 template <typename OrderedList>
92 struct list_iterator_selector< OrderedList, true>
94 typedef OrderedList const * bucket_ptr;
95 typedef typename OrderedList::const_iterator type;
98 template <typename OrderedList, bool IsConst>
102 typedef OrderedList bucket_type;
103 typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
104 typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
106 bucket_ptr m_pCurBucket;
107 list_iterator m_itList;
108 bucket_ptr m_pEndBucket;
112 if ( m_pCurBucket < m_pEndBucket ) {
113 if ( ++m_itList != m_pCurBucket->end() )
115 while ( ++m_pCurBucket < m_pEndBucket ) {
116 m_itList = m_pCurBucket->begin();
117 if ( m_itList != m_pCurBucket->end() )
121 m_pCurBucket = m_pEndBucket - 1;
122 m_itList = m_pCurBucket->end();
126 typedef typename list_iterator::value_ptr value_ptr;
127 typedef typename list_iterator::value_ref value_ref;
131 : m_pCurBucket( nullptr )
133 , m_pEndBucket( nullptr )
136 iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
137 : m_pCurBucket( pFirst )
139 , m_pEndBucket( pLast )
141 if ( it == pFirst->end() )
145 iterator( iterator const& src )
146 : m_pCurBucket( src.m_pCurBucket )
147 , m_itList( src.m_itList )
148 , m_pEndBucket( src.m_pEndBucket )
151 value_ptr operator ->() const
153 assert( m_pCurBucket != nullptr );
154 return m_itList.operator ->();
157 value_ref operator *() const
159 assert( m_pCurBucket != nullptr );
160 return m_itList.operator *();
164 iterator& operator ++()
170 iterator& operator = (const iterator& src)
172 m_pCurBucket = src.m_pCurBucket;
173 m_pEndBucket = src.m_pEndBucket;
174 m_itList = src.m_itList;
178 bucket_ptr bucket() const
180 return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
184 bool operator ==(iterator<OrderedList, C> const& i ) const
186 return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
189 bool operator !=(iterator<OrderedList, C> const& i ) const
191 return !( *this == i );
200 // Forward declarations
201 template <class GC, class OrderedList, class Traits = michael_set::type_traits>
202 class MichaelHashSet;
205 }} // namespace cds::intrusive
207 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H