hphp/util/bitset-array.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 #pragma once
  18
  19 #include <hphp/util/assertions.h>
  20
  21 namespace HPHP {
  22
  23 struct BitsetArray;
  24 struct BitsetWrapper;
  25
  26 struct BitsetRef {
  27   friend struct BitsetArray;
  28   friend struct BitsetWrapper;
  29
  30   const BitsetRef& operator=(const BitsetRef&) = delete;
  31
  32   size_t size() const { return (e - s) * bits_per_word; }
  33
  34   friend bool operator==(const BitsetRef& o1, const BitsetRef& o2) {
  35     auto p1 = o1.s;
  36     auto p2 = o2.s;
  37     while (p1 != o1.e) {
  38       if (*p1 != *p2) return false;
  39       ++p1;
  40       ++p2;
  41     }
  42     assert(p2 == o2.e);
  43     return true;
  44   }
  45
  46   friend bool operator!=(const BitsetRef& o1, const BitsetRef& o2) {
  47     return !(o1 == o2);
  48   }
  49
  50   friend BitsetWrapper operator|(const BitsetRef& o1, const BitsetRef& o2);
  51   friend BitsetWrapper operator&(const BitsetRef& o1, const BitsetRef& o2);
  52   friend BitsetWrapper operator-(const BitsetRef& o1, const BitsetRef& o2);
  53
  54   BitsetRef& operator|=(const BitsetRef& o) {
  55     perform(o,
  56             [](uint64_t* dst, const uint64_t *src) {
  57               *dst |= *src;
  58             });
  59     return *this;
  60   }
  61   BitsetRef& operator&=(const BitsetRef& o) {
  62     perform(o,
  63             [](uint64_t* dst, const uint64_t *src) {
  64               *dst &= *src;
  65             });
  66     return *this;
  67   }
  68   BitsetRef& operator-=(const BitsetRef& o) {
  69     perform(o,
  70             [](uint64_t* dst, const uint64_t *src) {
  71               *dst &= ~*src;
  72             });
  73     return *this;
  74   }
  75
  76   void assign(const BitsetRef& o) {
  77     perform(o,
  78             [](uint64_t* dst, const uint64_t *src) {
  79               *dst = *src;
  80             });
  81   }
  82
  83   void assign_add(const BitsetRef& o1, const BitsetRef& o2) {
  84     perform(o1, o2,
  85             [](uint64_t* dst, const uint64_t *src1, const uint64_t *src2) {
  86               *dst = *src1 | *src2;
  87             });
  88   }
  89
  90   void assign_sub(const BitsetRef& o1, const BitsetRef& o2) {
  91     perform(o1, o2,
  92             [](uint64_t* dst, const uint64_t *src1, const uint64_t *src2) {
  93               *dst = *src1 & ~*src2;
  94             });
  95   }
  96
  97   void assign_and(const BitsetRef& o1, const BitsetRef& o2) {
  98     perform(o1, o2,
  99             [](uint64_t* dst, const uint64_t *src1, const uint64_t *src2) {
 100               *dst = *src1 & *src2;
 101             });
 102   }
 103
 104   BitsetRef next(int n = 1) const {
 105     return BitsetRef { s + (e - s) * n, e + (e - s) * n };
 106   }
 107
 108   BitsetRef prev(int n = 1) const {
 109     return BitsetRef { s - (e - s) * n, e - (e - s) * n };
 110   }
 111
 112   bool operator[](size_t bit) const { return test(bit); }
 113   bool test(size_t bit) const {
 114     auto idx = bit / bits_per_word;
 115     auto pos = bit - (idx * bits_per_word);
 116
 117     assert(idx < (e - s));
 118     return (s[idx] >> pos) & 1;
 119   }
 120
 121   void reset(size_t bit) {
 122     auto idx = bit / bits_per_word;
 123     auto pos = bit - (idx * bits_per_word);
 124
 125     assert(idx < (e - s));
 126     s[idx] &= ~(ElemType{1} << pos);
 127   }
 128
 129   void reset() {
 130     for (auto p = s; p != e; ++p) *p = 0;
 131   }
 132
 133   void set(size_t bit) {
 134     auto idx = bit / bits_per_word;
 135     auto pos = bit - (idx * bits_per_word);
 136
 137     assert(idx < (e - s));
 138     s[idx] |= ElemType{1} << pos;
 139   }
 140
 141   void set() {
 142     for (auto p = s; p != e; ++p) *p = ~ElemType{};
 143   }
 144
 145   bool any() const {
 146     for (auto p = s; p != e; ++p) if (*p) return true;
 147     return false;
 148   }
 149
 150   bool none() const { return !any(); }
 151 private:
 152   using ElemType = uint64_t;
 153   static constexpr auto bits_per_word = std::numeric_limits<ElemType>::digits;
 154
 155   BitsetRef(ElemType* s, ElemType* e) : s{s}, e{e} {}
 156   size_t words() const { return e - s; }
 157
 158   template <typename F>
 159   void perform(const BitsetRef& o, F&& f) {
 160     auto dst = s;
 161     auto src = o.s;
 162     while (dst != e) {
 163       f(dst, src);
 164       ++dst;
 165       ++src;
 166     }
 167     assert(src == o.e);
 168   }
 169
 170   template <typename F>
 171   void perform(const BitsetRef& o1, const BitsetRef& o2, F&& f) {
 172     auto dst = s;
 173     auto src1 = o1.s;
 174     auto src2 = o2.s;
 175     while (dst != e) {
 176       f(dst, src1, src2);
 177       ++dst;
 178       ++src1;
 179       ++src2;
 180     }
 181     assert(src1 == o1.e);
 182     assert(src2 == o2.e);
 183   }
 184
 185   ElemType *s;
 186   ElemType *e;
 187 };
 188
 189 struct BitsetWrapper : BitsetRef {
 190   BitsetWrapper(BitsetWrapper&& o) : BitsetRef{o.s, o.e} {
 191     o.s = o.e = nullptr;
 192   }
 193   ~BitsetWrapper() { delete [] s; }
 194
 195   friend BitsetWrapper operator|(const BitsetRef& o1, const BitsetRef& o2) {
 196     BitsetWrapper r{o1.words()};
 197     r.assign_add(o1, o2);
 198     return r;
 199   }
 200
 201   friend BitsetWrapper operator&(const BitsetRef& o1, const BitsetRef& o2) {
 202     BitsetWrapper r{o1.words()};
 203     r.assign_and(o1, o2);
 204     return r;
 205   }
 206
 207   friend BitsetWrapper operator-(const BitsetRef& o1, const BitsetRef& o2) {
 208     BitsetWrapper r{o1.words()};
 209     r.assign_sub(o1, o2);
 210     return r;
 211   }
 212
 213
 214 private:
 215   BitsetWrapper(size_t words) : BitsetRef{nullptr, nullptr} {
 216     s = new uint64_t[words];
 217     e = s + words;
 218   }
 219 };
 220
 221 struct BitsetArray {
 222   BitsetArray(size_t rows, size_t bits) : m_rows{rows}, m_rowData{nullptr} {
 223     m_rowElems =
 224       (bits + BitsetRef::bits_per_word - 1) / BitsetRef::bits_per_word;
 225     auto const words = m_rowElems * rows;
 226     m_rowData = new uint64_t[words];
 227     memset(m_rowData, 0, words * sizeof(*m_rowData));
 228   }
 229
 230   BitsetRef row(size_t r) {
 231     assert(r < m_rows);
 232     auto const s = m_rowData + r * m_rowElems;
 233     return BitsetRef { s, s + m_rowElems };
 234   }
 235
 236   const BitsetRef row(size_t r) const {
 237     assert(r < m_rows);
 238     auto const s = m_rowData + r * m_rowElems;
 239     return BitsetRef { s, s + m_rowElems };
 240   }
 241
 242   ~BitsetArray() { delete [] m_rowData; }
 243 private:
 244   size_t m_rows;
 245   size_t m_rowElems;
 246   BitsetRef::ElemType* m_rowData;
 247 };
 248
 249 }