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     auto const tail_nbits = N * m_size - m_nwords * 64;
  60     auto const tail_mask = (1ull << tail_nbits) - 1;
  61     m_bits[m_nwords - 1] &= tail_mask;
  62   }
  63 }
  64
  65 template<size_t N>
  66 void multibitset<N>::reset() {
  67   memset(m_bits, 0, m_nwords * sizeof(*m_bits));
  68 }
  69
  70 template<size_t N>
  71 multibitset<N>::reference::reference(multibitset<N>& mbs, size_t pos)
  72   : m_mbs(mbs)
  73   , m_word(N * pos / 64)
  74   , m_bit(N * pos - m_word * 64)
  75 {}
  76
  77 template<size_t N>
  78 multibitset<N>::reference::operator uint64_t() const {
  79   constexpr auto mask = (1ull << N) - 1;
  80
  81   if (m_bit + N <= 64) {
  82     return (m_mbs.m_bits[m_word] >> m_bit) & mask;
  83   }
  84
  85   auto const head_nbits = 64 - m_bit;
  86   auto const head_mask = (1ull << head_nbits) - 1;
  87
  88   auto const head = (m_mbs.m_bits[m_word] >> m_bit) & head_mask;
  89   auto const tail = m_mbs.m_bits[m_word + 1] << head_nbits;
  90
  91   return (head | tail) & mask;
  92 }
  93
  94 template<size_t N>
  95 typename multibitset<N>::reference&
  96 multibitset<N>::reference::operator=(uint64_t val) {
  97   constexpr auto mask = (1ull << N) - 1;
  98   assertx((val & mask) == val);
  99
 100   {
 101     auto& word = m_mbs.m_bits[m_word];
 102     word = (word & ~(mask << m_bit)) | ((val & mask) << m_bit);
 103   }
 104
 105   if (m_bit + N > 64) {
 106     auto const head_nbits = 64 - m_bit;
 107
 108     auto& word = m_mbs.m_bits[m_word + 1];
 109     word = (word & ~(mask >> head_nbits)) | ((val & mask) >> head_nbits);
 110   }
 111   return *this;
 112 }
 113
 114 template<size_t N>
 115 uint64_t multibitset<N>::operator[](size_t pos) const {
 116   assertx(pos < m_size);
 117   return reference(*const_cast<multibitset<N>*>(this), pos);
 118 }
 119
 120 template<size_t N>
 121 typename multibitset<N>::reference multibitset<N>::operator[](size_t pos) {
 122   assertx(pos < m_size);
 123   return reference(*this, pos);
 124 }
 125
 126 template<size_t N>
 127 size_t multibitset<N>::size() const { return m_size; }
 128
 129 template<size_t N>
 130 size_t multibitset<N>::ffs(size_t pos) const {
 131   assertx(pos < m_size);
 132
 133   size_t b;
 134   auto const ref = reference(*const_cast<multibitset<N>*>(this), pos);
 135
 136   auto const mask = ~((1ull << ref.m_bit) - 1);
 137   auto const word = m_bits[ref.m_word] & mask;
 138   if (ffs64(word, b)) return (ref.m_word * 64 + b) / N;
 139
 140   for (auto d = ref.m_word + 1; d < m_nwords; ++d) {
 141     if (ffs64(m_bits[d], b)) return (d * 64 + b) / N;
 142   }
 143   return npos;
 144 }
 145
 146 template<size_t N>
 147 size_t multibitset<N>::fls(size_t pos) const {
 148   if (pos == npos) pos = m_size - 1;
 149   assertx(pos < m_size);
 150
 151   size_t b;
 152   // We use a reference to the next position to take care of the case where the
 153   // N-bit at `pos' straddles a word boundary.
 154   auto const ref = reference(*const_cast<multibitset<N>*>(this), pos + 1);
 155
 156   auto const mask = (1ull << ref.m_bit) - 1;
 157   auto const word = m_bits[ref.m_word] & mask;
 158   if (fls64(word, b)) return (ref.m_word * 64 + b) / N;
 159
 160   for (auto d = ref.m_word; d-- > 0; ) {
 161     if (fls64(m_bits[d], b)) return (d * 64 + b) / N;
 162   }
 163   return npos;
 164 }
 165
 166 ///////////////////////////////////////////////////////////////////////////////
 167
 168 template<size_t N>
 169 chunked_multibitset<N>::chunked_multibitset(size_t chunk_sz)
 170   : m_chunk_sz{chunk_sz}
 171 {
 172   always_assert(m_chunk_sz > 0);
 173 }
 174
 175 template<size_t N>
 176 chunked_multibitset<N>::reference::reference(chunked_multibitset<N>& cmbs,
 177                                              size_t pos)
 178   : m_cmbs(cmbs)
 179   , m_pos(pos)
 180 {}
 181
 182 template<size_t N>
 183 void chunked_multibitset<N>::reset() {
 184   m_chunks.clear();
 185   m_highwater = 0;
 186   m_lowwater = npos;
 187 }
 188
 189 template<size_t N>
 190 multibitset<N>& chunked_multibitset<N>::chunk_for(size_t pos) {
 191   auto const c = pos / m_chunk_sz;
 192   if (m_chunks[c].size() == 0) {
 193     m_chunks[c].resize(m_chunk_sz);
 194     m_highwater = std::max(c, m_highwater);
 195     m_lowwater = std::min(c, m_lowwater);
 196   }
 197   return m_chunks[c];
 198 }
 199
 200 template<size_t N>
 201 chunked_multibitset<N>::reference::operator uint64_t() const {
 202   auto const it = m_cmbs.m_chunks.find(m_pos / m_cmbs.m_chunk_sz);
 203   return it != m_cmbs.m_chunks.end()
 204     ? it->second[m_pos % m_cmbs.m_chunk_sz]
 205     : 0;
 206 }
 207
 208 template<size_t N>
 209 typename chunked_multibitset<N>::reference&
 210 chunked_multibitset<N>::reference::operator=(uint64_t val) {
 211   m_cmbs.chunk_for(m_pos)[m_pos % m_cmbs.m_chunk_sz] = val;
 212   return *this;
 213 }
 214
 215 template<size_t N>
 216 uint64_t chunked_multibitset<N>::operator[](size_t pos) const {
 217   return reference(*const_cast<chunked_multibitset<N>*>(this), pos);
 218 }
 219
 220 template<size_t N>
 221 typename chunked_multibitset<N>::reference
 222 chunked_multibitset<N>::operator[](size_t pos) {
 223   return reference(*this, pos);
 224 }
 225
 226 template<size_t N>
 227 size_t chunked_multibitset<N>::ffs(size_t pos) const {
 228   {
 229     auto const c = std::max(pos / m_chunk_sz, m_lowwater);
 230     auto const it = m_chunks.find(c);
 231     if (it != m_chunks.end()) {
 232       auto const res = it->second.ffs(pos % m_chunk_sz);
 233       if (res != npos) return c * m_chunk_sz + res;
 234     }
 235   }
 236
 237   for (auto c = pos / m_chunk_sz + 1; c <= m_highwater; ++c) {
 238     auto const it = m_chunks.find(c);
 239     if (it != m_chunks.end()) {
 240       auto const res = it->second.ffs();
 241       if (res != npos) return c * m_chunk_sz + res;
 242     }
 243   }
 244   return npos;
 245 }
 246
 247 template<size_t N>
 248 size_t chunked_multibitset<N>::fls(size_t pos) const {
 249   {
 250     auto const c = std::min(pos / m_chunk_sz, m_highwater);
 251     auto const it = m_chunks.find(c);
 252     if (it != m_chunks.end()) {
 253       auto const res = it->second.fls(pos != npos ? pos % m_chunk_sz : npos);
 254       if (res != npos) return c * m_chunk_sz + res;
 255     }
 256   }
 257
 258   for (auto c = pos / m_chunk_sz; c-- > m_lowwater; ) {
 259     auto const it = m_chunks.find(c);
 260     if (it != m_chunks.end()) {
 261       auto const res = it->second.fls();
 262       if (res != npos) return c * m_chunk_sz + res;
 263     }
 264   }
 265   return npos;
 266 }
 267
 268 ///////////////////////////////////////////////////////////////////////////////
 269
 270 }