src/jitcs_int_adt_bitmap.h

   1 //===-- src/jitcs_int_adt_bitmap.h ------------------------------*- C++ -*-===//
   2 // BitSlice class.
   3 //
   4 // Copyright (C) 2013-2014 Dirk Steinke.
   5 // See copyright and license notice in COPYRIGHT or include/jitcs.h
   6 //
   7 // A BitSlice is a view to an array of words, and allows checking and setting
   8 // single bits. A BitSlice does NOT own the data it points to.
   9 // A DynBitSlice provides the data array for the BitSlice. It will use a
  10 // fixed size array, or allocate the space from the heap.
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef _JITCS_INT_ADT_BITMAP_H_
  14 #define _JITCS_INT_ADT_BITMAP_H_
  15
  16 #include "jitcs_base.h"
  17 #include "jitcs_adt_ref.h"
  18 #include "jitcs_int_bitfuncs.h"
  19 #include "jitcs_int_power2funcs.h"
  20
  21 #include <stdio.h>
  22
  23 namespace jitcs {
  24 class IDumper;
  25 void DumpBitmap(IDumper& o, const size_t*, size_t);
  26
  27 template <unsigned FLAGS>
  28 struct _Bits {
  29   typedef const size_t CType;
  30   typedef size_t NCType;
  31   static const bool IsConstRef = (FLAGS & REF_Const) != 0;
  32   typedef typename std::conditional<IsConstRef, CType, NCType>::type WordType;
  33   typedef WordType* PtrType;
  34   typedef WordType& RefType;
  35
  36   typedef WordType* iterator;
  37   typedef WordType const* const_iterator;
  38
  39   static_assert(sizeof(WordType) == 4 || sizeof(WordType) == 8, "surprising size_t size");
  40   enum {
  41     E_BitsPerWord = sizeof(WordType) * 8, // 32 or 64
  42     E_Log2OfBitsPerWord = Log2CT<E_BitsPerWord>::Val, // 5 or 6
  43     E_MaskOfBitsPerWord = (1 << E_Log2OfBitsPerWord) - 1, // 0x1f or 0x3f
  44   };
  45
  46   struct BitEnumerator {
  47     size_t const *ptr;
  48     size_t nbits;
  49     size_t curpos0, curbit;
  50
  51     BitEnumerator(const WordType* p, size_t n)
  52       : ptr(p)
  53       , curpos0(0)
  54       , curbit(0)
  55       , nbits(n) {
  56       if (!isEmpty()) {
  57         _advance();
  58       }
  59     }
  60     BitEnumerator(const BitEnumerator&) = default;
  61     BitEnumerator& operator =(const BitEnumerator&) = default;
  62
  63     bool isEmpty() const { return curpos0 >= nbits; }
  64     size_t pos() const { return curpos0 + curbit; }
  65     void next() { ++curbit; _advance(); }
  66
  67     bool operator !() const { return isEmpty(); }
  68     size_t operator *() const { assert(!isEmpty()); return pos(); }
  69     void operator ++() { assert(!isEmpty()); next(); }
  70
  71   private:
  72     void _advance() {
  73       _JITCS_DBG_CHECK_(!isEmpty());
  74       while (curbit >= E_BitsPerWord || (*ptr >> curbit) == 0) {
  75         curpos0 += E_BitsPerWord;
  76         if (isEmpty()) return;
  77         ++ptr;
  78         curbit = 0;
  79       }
  80       curbit = t0cntnz(*ptr, curbit);
  81     }
  82   };
  83
  84
  85   _Bits() : _ptr(nullptr), _nbits(0) {}
  86   _Bits(const _Bits&) = default;
  87   _Bits& operator = (const _Bits&) = default;
  88
  89   template <unsigned FLAGS2>
  90   _Bits(_Bits<FLAGS2> o) {
  91     static_assert((~FLAGS & FLAGS2) == 0, "incompatible _Bits flags");
  92     //static_assert(std::is_base_of<T, T2>::value, "incompatible _Bits types");
  93     _ptr = o._ptr;
  94     _nbits = o._nbits;
  95   }
  96   _Bits(PtrType o, size_t n) {
  97     _ptr = o;
  98     _nbits = n;
  99   }
 100
 101   template <unsigned FLAGS2>
 102   _Bits& operator =(_Bits<FLAGS2> o) {
 103     static_assert((~FLAGS & FLAGS2) == 0, "incompatible _Bits flags");
 104     _ptr = o._ptr;
 105     _nbits = o._nbits;
 106   }
 107
 108   PtrType ptr() const { return _ptr; }
 109   size_t bitSize() const { return _nbits; }
 110   size_t wordSize() const { return DivRoundedUpByPowerOf2<E_BitsPerWord>(_nbits); }
 111
 112   bool isEmpty() const { return _nbits == 0; }
 113   bool empty() const { return isEmpty(); }
 114
 115   bool isValidIndex(size_t r) const { return r >= 0 && r < bitSize(); }
 116
 117   iterator wordBegin() { return ptr(); }
 118   iterator wordEnd() { return ptr() + wordSize(); }
 119   const_iterator wordBegin() const { return wordCBegin(); }
 120   const_iterator wordEnd() const { return wordCEnd(); }
 121   const_iterator wordCBegin() const { return ptr(); }
 122   const_iterator wordCEnd() const { return ptr() + wordSize(); }
 123
 124   BitEnumerator enumBits() const { return BitEnumerator(_ptr, _nbits); }
 125
 126   size_t getWordNoForIndex(size_t r) const { return r >> E_Log2OfBitsPerWord; }
 127   size_t getBitNoForIndex(size_t r) const { return r & E_MaskOfBitsPerWord; }
 128   RefType getWordForIndex(size_t r) const { return _ptr[getWordNoForIndex(r)]; }
 129   size_t getBitMaskForIndex(size_t r) const { return 1 << getBitNoForIndex(r); }
 130   size_t getLastWordBitNo() const { return bitSize() & E_MaskOfBitsPerWord; }
 131   size_t getLastWordShift() const { return E_BitsPerWord - getLastWordBitNo(); }
 132   bool hasIncompleteLastWord() const { return getLastWordBitNo() != 0; }
 133
 134   bool test(size_t r) const {
 135     _checkIndex(r);
 136     return (getWordForIndex(r) & getBitMaskForIndex(r)) != 0;
 137   }
 138   bool operator [](size_t i) const { return test(i); }
 139
 140   size_t countSetBits() const {
 141     size_t n = wordSize();
 142     size_t sum = 0;
 143     if (hasIncompleteLastWord()) {
 144       sum += popcnt(_ptr[n - 1] << getLastWordShift());
 145       --n;
 146     }
 147     for (size_t i = 0; i < n; ++i) {
 148       sum += popcnt(_ptr[i]);
 149     }
 150     return sum;
 151   }
 152   bool isAllZeroes() const {
 153     size_t n = wordSize();
 154     if (hasIncompleteLastWord()) {
 155       if ((_ptr[n - 1] << getLastWordShift()) != 0) return false;
 156     }
 157     for (size_t i = 0; i < n; ++i) {
 158       if (_ptr[i] != 0) return false;
 159     }
 160     return true;
 161   }
 162   bool isAllOnes() const {
 163     size_t n = wordSize();
 164     if (hasIncompleteLastWord()) {
 165       if (((~_ptr[n - 1]) << getLastWordShift()) != 0) return false;
 166     }
 167     for (size_t i = 0; i < n; ++i) {
 168       if ((~_ptr[i]) != 0) return false;
 169     }
 170     return true;
 171   }
 172   template <unsigned FLAGS2>
 173   bool isSubsetOf(const _Bits<FLAGS2>& p) const {
 174     _checkNotLongerThan(p);
 175     size_t n = wordSize();
 176     if (hasIncompleteLastWord()) {
 177       if ((_ptr[n - 1] & ~p._ptr[n - 1]) << getLastWordShift()) return false;
 178       --n;
 179     }
 180     for (size_t i = 0; i < n; ++i) {
 181       if (_ptr[i] & ~p._ptr[i]) return false;
 182     }
 183     return true;
 184   }
 185   template <unsigned FLAGS2>
 186   bool equals(const _Bits<FLAGS2>& p) const {
 187     _checkNotLongerThan(p);
 188     //if (bitSize() != p.bitSize()) return false;
 189     size_t n = wordSize();
 190     if (hasIncompleteLastWord()) {
 191       if ((_ptr[n - 1] ^ p._ptr[n - 1]) << getLastWordShift()) return false;
 192       --n;
 193     }
 194     for (size_t i = 0; i < n; ++i) {
 195       if (_ptr[i] != p._ptr[i]) return false;
 196     }
 197     return true;
 198   }
 199
 200   void mark(size_t r) {
 201     guarantee<(FLAGS & REF_Const) == 0>
 202       ("mutation disabled for immutable bitmap views");
 203     _checkIndex(r);
 204     RefType rw = getWordForIndex(r);
 205     rw |= getBitMaskForIndex(r);
 206   }
 207   void clear(size_t r) {
 208     guarantee<(FLAGS & REF_Const) == 0>
 209       ("mutation disabled for immutable bitmap views");
 210     _checkIndex(r);
 211     RefType rw = getWordForIndex(r);
 212     rw &= ~getBitMaskForIndex(r);
 213   }
 214   bool testAndMark(size_t r)  {
 215     guarantee<(FLAGS & REF_Const) == 0>
 216       ("mutation disabled for immutable bitmap views");
 217     _checkIndex(r);
 218     RefType rw = getWordForIndex(r);
 219     WordType m = getBitMaskForIndex(r);
 220     bool res = (rw & m) != 0;
 221     rw |= m;
 222     return res;
 223   }
 224   bool testAndClear(size_t r)  {
 225     guarantee<(FLAGS & REF_Const) == 0>
 226       ("mutation disabled for immutable bitmap views");
 227     _checkIndex(r);
 228     RefType rw = getWordForIndex(r);
 229     WordType m = getBitMaskForIndex(r);
 230     bool res = (rw & m) != 0;
 231     rw &= ~m;
 232     return res;
 233   }
 234   bool testAndComplement(size_t r)  {
 235     guarantee<(FLAGS & REF_Const) == 0>
 236       ("mutation disabled for immutable bitmap views");
 237     _checkIndex(r);
 238     RefType rw = getWordForIndex(r);
 239     WordType m = getBitMaskForIndex(r);
 240     bool res = (rw & m) != 0;
 241     rw ^= m;
 242     return res;
 243   }
 244
 245   void clearAll() {
 246     guarantee<(FLAGS & REF_Const) == 0>
 247       ("mutation disabled for immutable bitmap views");
 248     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 249       _ptr[i] = 0;
 250     }
 251   }
 252   void setAll() {
 253     guarantee<(FLAGS & REF_Const) == 0>
 254       ("mutation disabled for immutable bitmap views");
 255     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 256       _ptr[i] = ~0;
 257     }
 258   }
 259   template <unsigned FLAGS2>
 260   void copyFrom(const _Bits<FLAGS2>& p) {
 261     _checkNotLongerThan(p);
 262     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 263       _ptr[i] = p._ptr[i];
 264     }
 265   }
 266   template <unsigned FLAGS2>
 267   void intersectWith(const _Bits<FLAGS2>& p) {
 268     _checkNotLongerThan(p);
 269     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 270       _ptr[i] &= p._ptr[i];
 271     }
 272   }
 273   template <unsigned FLAGS2>
 274   void uniteWith(const _Bits<FLAGS2>& p) {
 275     _checkNotLongerThan(p);
 276     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 277       _ptr[i] |= p._ptr[i];
 278     }
 279   }
 280   template <unsigned FLAGS2>
 281   void setFrom(const _Bits<FLAGS2>& p) {
 282     return uniteWith(p);
 283   }
 284   template <unsigned FLAGS2>
 285   void clearFrom(const _Bits<FLAGS2>& p) {
 286     _checkNotLongerThan(p);
 287     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 288       _ptr[i] &= ~p._ptr[i];
 289     }
 290   }
 291
 292   void dump(IDumper& o) const { DumpBitmap(o, _ptr, _nbits); }
 293
 294 private:
 295   void _checkIndex(size_t r) const { _JITCS_DBG_CHECK_(isValidIndex(r)); }
 296   template <unsigned FLAGS2>
 297   void _checkNotLongerThan(const _Bits<FLAGS2>& bmp) const {
 298     _JITCS_DBG_CHECK_(bitSize() <= bmp.bitSize());
 299   }
 300
 301 public:
 302   WordType *_ptr;
 303   size_t _nbits;
 304 };
 305
 306 typedef _Bits<REF_Any> BitSlice;
 307 typedef _Bits<REF_Const> ConstBitSlice;
 308
 309 template <size_t N>
 310 struct DynBitSlice : BitSlice {
 311   size_t _short_data[RoundUpToPowerOf2CT<N, E_BitsPerWord>::Val];
 312
 313   DynBitSlice(size_t nbits, bool clear) {
 314     size_t n = DivRoundedUpByPowerOf2< E_BitsPerWord>(nbits);
 315     _ptr = n <= RoundUpToPowerOf2CT<N,  E_BitsPerWord>::Val ? _short_data : new size_t[n];
 316     _nbits = nbits;
 317     if (clear) clearAll();
 318   }
 319   ~DynBitSlice() {
 320     if (isUsingHeap()) delete[] _ptr;
 321   }
 322   bool isUsingHeap() const { return _ptr != _short_data; }
 323 };
 324
 325
 326 } // end of jitcs namespace
 327
 328 #endif
 329 // _JITCS_INT_ADT_BITMAP_H_