hphp/util/multibitset-inl.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #include "hphp/util/assertions.h"
  18 #include "hphp/util/bitops.h"
  19
  20 #include <algorithm>
  21 #include <cstdlib>
  22
  23 namespace HPHP {
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26
  27 template<size_t N>
  28 multibitset<N>::multibitset() {}
  29
  30 template<size_t N>
  31 multibitset<N>::multibitset(size_t nelms) {
  32   resize(nelms);
  33   reset();
  34 }
  35
  36 template<size_t N>
  37 multibitset<N>::~multibitset() {
  38   free(m_bits);
  39 }
  40
  41 template<size_t N>
  42 void multibitset<N>::resize(size_t nelms) {
  43   auto const prev_nwords = m_nwords;
  44   auto const prev_size = m_size;
  45
  46   auto const nbits = N * nelms;
  47   auto const whole_words = nbits / 64;
  48   m_nwords = whole_words + (whole_words * 64 != nbits);
  49   m_size = nelms;
  50   m_bits = reinterpret_cast<uint64_t*>(
  51     realloc(m_bits, m_nwords * sizeof(*m_bits))
  52   );
  53
  54   if (prev_nwords < m_nwords) {
  55     memset(m_bits + prev_nwords, 0,
  56            (m_nwords - prev_nwords) * sizeof(*m_bits));
  57   } else if (m_size < prev_size) {
  58     // f{f,l}s() rely on the out-of-range bits being zeroed.
  59     if (whole_words != m_nwords) {
  60       auto const tail_nbits = N * m_size - whole_words * 64;
  61       auto const tail_mask = (1ull << tail_nbits) - 1;
  62       m_bits[m_nwords - 1] &= tail_mask;
  63     }
  64   }
  65 }
  66
  67 template<size_t N>
  68 void multibitset<N>::reset() {
  69   memset(m_bits, 0, m_nwords * sizeof(*m_bits));
  70 }
  71
  72 template<size_t N>
  73 multibitset<N>::reference::reference(multibitset<N>& mbs, size_t pos)
  74   : m_mbs(mbs)
  75   , m_word(N * pos / 64)
  76   , m_bit(N * pos - m_word * 64)
  77 {}
  78
  79 template<size_t N>
  80 multibitset<N>::reference::operator uint64_t() const {
  81   constexpr auto mask = (1ull << N) - 1;
  82
  83   if (m_bit + N <= 64) {
  84     return (m_mbs.m_bits[m_word] >> m_bit) & mask;
  85   }
  86
  87   auto const head_nbits = 64 - m_bit;
  88   auto const head_mask = (1ull << head_nbits) - 1;
  89
  90   auto const head = (m_mbs.m_bits[m_word] >> m_bit) & head_mask;
  91   auto const tail = m_mbs.m_bits[m_word + 1] << head_nbits;
  92
  93   return (head | tail) & mask;
  94 }
  95
  96 template<size_t N>
  97 typename multibitset<N>::reference&
  98 multibitset<N>::reference::operator=(uint64_t val) {
  99   constexpr auto mask = (1ull << N) - 1;
 100   assertx((val & mask) == val);
 101
 102   {
 103     auto& word = m_mbs.m_bits[m_word];
 104     word = (word & ~(mask << m_bit)) | ((val & mask) << m_bit);
 105   }
 106
 107   if (m_bit + N > 64) {
 108     auto const head_nbits = 64 - m_bit;
 109
 110     auto& word = m_mbs.m_bits[m_word + 1];
 111     word = (word & ~(mask >> head_nbits)) | ((val & mask) >> head_nbits);
 112   }
 113   return *this;
 114 }
 115
 116 template<size_t N>
 117 uint64_t multibitset<N>::operator[](size_t pos) const {
 118   assertx(pos < m_size);
 119   return reference(*const_cast<multibitset<N>*>(this), pos);
 120 }
 121
 122 template<size_t N>
 123 typename multibitset<N>::reference multibitset<N>::operator[](size_t pos) {
 124   assertx(pos < m_size);
 125   return reference(*this, pos);
 126 }
 127
 128 template<size_t N>
 129 size_t multibitset<N>::size() const { return m_size; }
 130
 131 template<size_t N>
 132 size_t multibitset<N>::ffs(size_t pos) const {
 133   assertx(pos < m_size);
 134
 135   size_t b;
 136   auto const ref = reference(*const_cast<multibitset<N>*>(this), pos);
 137
 138   auto const mask = ~((1ull << ref.m_bit) - 1);
 139   auto const word = m_bits[ref.m_word] & mask;
 140   if (ffs64(word, b)) return (ref.m_word * 64 + b) / N;
 141
 142   for (auto d = ref.m_word + 1; d < m_nwords; ++d) {
 143     if (ffs64(m_bits[d], b)) return (d * 64 + b) / N;
 144   }
 145   return npos;
 146 }
 147
 148 template<size_t N>
 149 size_t multibitset<N>::fls(size_t pos) const {
 150   if (pos == npos) pos = m_size - 1;
 151   assertx(pos < m_size);
 152
 153   size_t b;
 154   // We use a reference to the next position to take care of the case where the
 155   // N-bit at `pos' straddles a word boundary.
 156   auto const ref = reference(*const_cast<multibitset<N>*>(this), pos + 1);
 157
 158   auto const mask = (1ull << ref.m_bit) - 1;
 159   auto const word = m_bits[ref.m_word] & mask;
 160   if (fls64(word, b)) return (ref.m_word * 64 + b) / N;
 161
 162   for (auto d = ref.m_word; d-- > 0; ) {
 163     if (fls64(m_bits[d], b)) return (d * 64 + b) / N;
 164   }
 165   return npos;
 166 }
 167
 168 ///////////////////////////////////////////////////////////////////////////////
 169
 170 template<size_t N>
 171 chunked_multibitset<N>::chunked_multibitset(size_t chunk_sz)
 172   : m_chunk_sz{chunk_sz}
 173 {
 174   always_assert(m_chunk_sz > 0);
 175 }
 176
 177 template<size_t N>
 178 chunked_multibitset<N>::reference::reference(chunked_multibitset<N>& cmbs,
 179                                              size_t pos)
 180   : m_cmbs(cmbs)
 181   , m_pos(pos)
 182 {}
 183
 184 template<size_t N>
 185 void chunked_multibitset<N>::reset() {
 186   m_chunks.clear();
 187   m_highwater = 0;
 188   m_lowwater = npos;
 189 }
 190
 191 template<size_t N>
 192 multibitset<N>& chunked_multibitset<N>::chunk_for(size_t pos) {
 193   auto const c = pos / m_chunk_sz;
 194   if (m_chunks[c].size() == 0) {
 195     m_chunks[c].resize(m_chunk_sz);
 196     m_highwater = std::max(c, m_highwater);
 197     m_lowwater = std::min(c, m_lowwater);
 198   }
 199   return m_chunks[c];
 200 }
 201
 202 template<size_t N>
 203 chunked_multibitset<N>::reference::operator uint64_t() const {
 204   auto const it = m_cmbs.m_chunks.find(m_pos / m_cmbs.m_chunk_sz);
 205   return it != m_cmbs.m_chunks.end()
 206     ? it->second[m_pos % m_cmbs.m_chunk_sz]
 207     : 0;
 208 }
 209
 210 template<size_t N>
 211 typename chunked_multibitset<N>::reference&
 212 chunked_multibitset<N>::reference::operator=(uint64_t val) {
 213   m_cmbs.chunk_for(m_pos)[m_pos % m_cmbs.m_chunk_sz] = val;
 214   return *this;
 215 }
 216
 217 template<size_t N>
 218 uint64_t chunked_multibitset<N>::operator[](size_t pos) const {
 219   return reference(*const_cast<chunked_multibitset<N>*>(this), pos);
 220 }
 221
 222 template<size_t N>
 223 typename chunked_multibitset<N>::reference
 224 chunked_multibitset<N>::operator[](size_t pos) {
 225   return reference(*this, pos);
 226 }
 227
 228 template<size_t N>
 229 size_t chunked_multibitset<N>::ffs(size_t pos) const {
 230   {
 231     auto const c = std::max(pos / m_chunk_sz, m_lowwater);
 232     auto const it = m_chunks.find(c);
 233     if (it != m_chunks.end()) {
 234       auto const res = it->second.ffs(pos % m_chunk_sz);
 235       if (res != npos) return c * m_chunk_sz + res;
 236     }
 237   }
 238
 239   for (auto c = pos / m_chunk_sz + 1; c <= m_highwater; ++c) {
 240     auto const it = m_chunks.find(c);
 241     if (it != m_chunks.end()) {
 242       auto const res = it->second.ffs();
 243       if (res != npos) return c * m_chunk_sz + res;
 244     }
 245   }
 246   return npos;
 247 }
 248
 249 template<size_t N>
 250 size_t chunked_multibitset<N>::fls(size_t pos) const {
 251   {
 252     auto const c = std::min(pos / m_chunk_sz, m_highwater);
 253     auto const it = m_chunks.find(c);
 254     if (it != m_chunks.end()) {
 255       auto const res = it->second.fls(pos != npos ? pos % m_chunk_sz : npos);
 256       if (res != npos) return c * m_chunk_sz + res;
 257     }
 258   }
 259
 260   for (auto c = pos / m_chunk_sz; c-- > m_lowwater; ) {
 261     auto const it = m_chunks.find(c);
 262     if (it != m_chunks.end()) {
 263       auto const res = it->second.fls();
 264       if (res != npos) return c * m_chunk_sz + res;
 265     }
 266   }
 267   return npos;
 268 }
 269
 270 ///////////////////////////////////////////////////////////////////////////////
 271
 272 }