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>
12 namespace cds { namespace intrusive {
14 /// MichaelHashSet related definitions
15 /** @ingroup cds_intrusive_helper
17 namespace michael_set {
19 /// MichaelHashSet traits
23 Hash function converts the key fields of struct \p T stored in the hash-set
24 into value of type \p size_t called hash value that is an index of hash table.
26 This is mandatory type and has no predefined one.
28 typedef opt::none hash;
32 The item counting is an important part of \p MichaelHashSet algorithm:
33 the \p empty() member function depends on correct item counting.
34 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
36 Default is \p atomicity::item_counter.
38 typedef cds::atomicity::item_counter item_counter;
40 /// Bucket table allocator
42 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
43 The allocator uses only in constructor for allocating bucket table
44 and in destructor for destroying bucket table
46 typedef CDS_DEFAULT_ALLOCATOR allocator;
49 /// Metafunction converting option list to traits struct
52 - \p opt::hash - mandatory option, specifies hash functor.
53 - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
55 - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
57 template <typename... Options>
59 typedef typename cds::opt::make_options< traits, Options...>::type type; ///< Metafunction result
64 static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
66 if ( nLoadFactor == 0 )
68 if ( nMaxItemCount == 0 )
70 const size_t nBucketCount = (size_t)( nMaxItemCount / nLoadFactor );
71 const size_t nLog2 = cds::bitop::MSB( nBucketCount );
73 return (( size_t( 1 << nLog2 ) < nBucketCount ? size_t( 1 << (nLog2 + 1) ) : size_t( 1 << nLog2 ))) - 1;
76 template <typename OrderedList, bool IsConst>
77 struct list_iterator_selector;
79 template <typename OrderedList>
80 struct list_iterator_selector< OrderedList, false>
82 typedef OrderedList * bucket_ptr;
83 typedef typename OrderedList::iterator type;
86 template <typename OrderedList>
87 struct list_iterator_selector< OrderedList, true>
89 typedef OrderedList const * bucket_ptr;
90 typedef typename OrderedList::const_iterator type;
93 template <typename OrderedList, bool IsConst>
96 friend class iterator < OrderedList, !IsConst > ;
98 typedef OrderedList bucket_type;
99 typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
100 typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
102 bucket_ptr m_pCurBucket;
103 list_iterator m_itList;
104 bucket_ptr m_pEndBucket;
106 friend class iterator < bucket_type, !IsConst > ;
110 if ( m_pCurBucket < m_pEndBucket ) {
111 if ( ++m_itList != m_pCurBucket->end() )
113 while ( ++m_pCurBucket < m_pEndBucket ) {
114 m_itList = m_pCurBucket->begin();
115 if ( m_itList != m_pCurBucket->end() )
119 m_pCurBucket = m_pEndBucket - 1;
120 m_itList = m_pCurBucket->end();
124 typedef typename list_iterator::value_ptr value_ptr;
125 typedef typename list_iterator::value_ref value_ref;
129 : m_pCurBucket( nullptr )
131 , m_pEndBucket( nullptr )
134 iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
135 : m_pCurBucket( pFirst )
137 , m_pEndBucket( pLast )
139 if ( it == pFirst->end() )
143 iterator( iterator const& src )
144 : m_pCurBucket( src.m_pCurBucket )
145 , m_itList( src.m_itList )
146 , m_pEndBucket( src.m_pEndBucket )
149 value_ptr operator ->() const
151 assert( m_pCurBucket != nullptr );
152 return m_itList.operator ->();
155 value_ref operator *() const
157 assert( m_pCurBucket != nullptr );
158 return m_itList.operator *();
162 iterator& operator ++()
168 iterator& operator = (const iterator& src)
170 m_pCurBucket = src.m_pCurBucket;
171 m_pEndBucket = src.m_pEndBucket;
172 m_itList = src.m_itList;
176 bucket_ptr bucket() const
178 return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
182 bool operator ==(iterator<bucket_type, C> const& i) const
184 return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
187 bool operator !=(iterator<OrderedList, C> const& i ) const
189 return !( *this == i );
198 // Forward declarations
199 template <class GC, class OrderedList, class Traits = michael_set::traits>
200 class MichaelHashSet;
203 }} // namespace cds::intrusive
205 #endif // #ifndef __CDS_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H