cds/intrusive/details/michael_set_base.h

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