cds/intrusive/details/michael_set_base.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
   4 #define CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
   5
   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/algo/atomic.h>
  11
  12 namespace cds { namespace intrusive {
  13
  14     /// MichaelHashSet related definitions
  15     /** @ingroup cds_intrusive_helper
  16     */
  17     namespace michael_set {
  18         /// MichaelHashSet traits
  19         struct traits {
  20             /// Hash function
  21             /**
  22                 Hash function converts the key fields of struct \p T stored in the hash-set
  23                 into value of type \p size_t called hash value that is an index of hash table.
  24
  25                 This is mandatory type and has no predefined one.
  26             */
  27             typedef opt::none hash;
  28
  29             /// Item counter
  30             /**
  31                 The item counting is an important part of \p MichaelHashSet algorithm:
  32                 the \p empty() member function depends on correct item counting.
  33                 Therefore, \p atomicity::empty_item_counter is not allowed as a type of the option.
  34
  35                 Default is \p atomicity::item_counter.
  36             */
  37             typedef cds::atomicity::item_counter item_counter;
  38
  39             /// Bucket table allocator
  40             /**
  41                 Allocator for bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR
  42                 The allocator uses only in constructor for allocating bucket table
  43                 and in destructor for destroying bucket table
  44             */
  45             typedef CDS_DEFAULT_ALLOCATOR   allocator;
  46         };
  47
  48         /// Metafunction converting option list to traits struct
  49         /**
  50             Available \p Options:
  51             - \p opt::hash - mandatory option, specifies hash functor.
  52             - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter
  53                 for default type.
  54             - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR.
  55         */
  56         template <typename... Options>
  57         struct make_traits {
  58             typedef typename cds::opt::make_options< traits, Options...>::type type;   ///< Metafunction result
  59         };
  60
  61         //@cond
  62         namespace details {
  63             static inline size_t init_hash_bitmask( size_t nMaxItemCount, size_t nLoadFactor )
  64             {
  65                 if ( nLoadFactor == 0 )
  66                     nLoadFactor = 1;
  67                 if ( nMaxItemCount == 0 )
  68                     nMaxItemCount = 4;
  69                 const size_t nBucketCount = (size_t)( nMaxItemCount / nLoadFactor );
  70                 const size_t nLog2 = cds::bitop::MSB( nBucketCount );
  71
  72                 return (( size_t( 1 << nLog2 ) < nBucketCount ? size_t( 1 << (nLog2 + 1) ) : size_t( 1 << nLog2 ))) - 1;
  73             }
  74
  75             template <typename OrderedList, bool IsConst>
  76             struct list_iterator_selector;
  77
  78             template <typename OrderedList>
  79             struct list_iterator_selector< OrderedList, false>
  80             {
  81                 typedef OrderedList * bucket_ptr;
  82                 typedef typename OrderedList::iterator  type;
  83             };
  84
  85             template <typename OrderedList>
  86             struct list_iterator_selector< OrderedList, true>
  87             {
  88                 typedef OrderedList const * bucket_ptr;
  89                 typedef typename OrderedList::const_iterator  type;
  90             };
  91
  92             template <typename OrderedList, bool IsConst>
  93             class iterator
  94             {
  95                 friend class iterator < OrderedList, !IsConst >;
  96             protected:
  97                 typedef OrderedList bucket_type;
  98                 typedef typename list_iterator_selector< bucket_type, IsConst>::bucket_ptr bucket_ptr;
  99                 typedef typename list_iterator_selector< bucket_type, IsConst>::type list_iterator;
 100
 101                 bucket_ptr      m_pCurBucket;
 102                 list_iterator   m_itList;
 103                 bucket_ptr      m_pEndBucket;
 104
 105                 void next()
 106                 {
 107                     if ( m_pCurBucket < m_pEndBucket ) {
 108                         if ( ++m_itList != m_pCurBucket->end() )
 109                             return;
 110                         while ( ++m_pCurBucket < m_pEndBucket ) {
 111                             m_itList = m_pCurBucket->begin();
 112                             if ( m_itList != m_pCurBucket->end() )
 113                                 return;
 114                         }
 115                     }
 116                     m_pCurBucket = m_pEndBucket - 1;
 117                     m_itList = m_pCurBucket->end();
 118                 }
 119
 120             public:
 121                 typedef typename list_iterator::value_ptr   value_ptr;
 122                 typedef typename list_iterator::value_ref   value_ref;
 123
 124             public:
 125                 iterator()
 126                     : m_pCurBucket( nullptr )
 127                     , m_itList()
 128                     , m_pEndBucket( nullptr )
 129                 {}
 130
 131                 iterator( list_iterator const& it, bucket_ptr pFirst, bucket_ptr pLast )
 132                     : m_pCurBucket( pFirst )
 133                     , m_itList( it )
 134                     , m_pEndBucket( pLast )
 135                 {
 136                     if ( it == pFirst->end() )
 137                         next();
 138                 }
 139
 140                 iterator( iterator const& src )
 141                     : m_pCurBucket( src.m_pCurBucket )
 142                     , m_itList( src.m_itList )
 143                     , m_pEndBucket( src.m_pEndBucket )
 144                 {}
 145
 146                 value_ptr operator ->() const
 147                 {
 148                     assert( m_pCurBucket != nullptr );
 149                     return m_itList.operator ->();
 150                 }
 151
 152                 value_ref operator *() const
 153                 {
 154                     assert( m_pCurBucket != nullptr );
 155                     return m_itList.operator *();
 156                 }
 157
 158                 /// Pre-increment
 159                 iterator& operator ++()
 160                 {
 161                     next();
 162                     return *this;
 163                 }
 164
 165                 iterator& operator = (const iterator& src)
 166                 {
 167                     m_pCurBucket = src.m_pCurBucket;
 168                     m_pEndBucket = src.m_pEndBucket;
 169                     m_itList = src.m_itList;
 170                     return *this;
 171                 }
 172
 173                 bucket_ptr bucket() const
 174                 {
 175                     return m_pCurBucket != m_pEndBucket ? m_pCurBucket : nullptr;
 176                 }
 177
 178                 template <bool C>
 179                 bool operator ==(iterator<bucket_type, C> const& i) const
 180                 {
 181                     return m_pCurBucket == i.m_pCurBucket && m_itList == i.m_itList;
 182                 }
 183                 template <bool C>
 184                 bool operator !=(iterator<OrderedList, C> const& i ) const
 185                 {
 186                     return !( *this == i );
 187                 }
 188
 189             };
 190         }
 191         //@endcond
 192     } // namespace michael_set
 193
 194     //@cond
 195     // Forward declarations
 196     template <class GC, class OrderedList, class Traits = michael_set::traits>
 197     class MichaelHashSet;
 198     //@endcond
 199
 200 }} // namespace cds::intrusive
 201
 202 #endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H