cds/intrusive/michael_set_base.h

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