include/jitcs_adt_bitstore.h

   1 //===-- jitcs_adt_bitstore.h - bit vector type ------------------*- C++ -*-===//
   2 //
   3 // A BitStore contains a fixed number of bits, and uses either an array
   4 // of bytes or a single integer variable for storage.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #ifndef _JITCS_ADT_BITSTORE_H_
   9 #define _JITCS_ADT_BITSTORE_H_
  10
  11 #include "jitcs_base.h"
  12
  13 namespace jitcs {
  14 // structure to contain a small, fixed amount of bits
  15 // will either use a single integer value or an array of bytes
  16 template <unsigned N, bool SMALL> struct _BitStore {
  17   static_assert(N > 0, "BitStore doesn't allow zero bits");
  18   u8 data[(N + 7) >> 3];
  19
  20   void setBit(u32 f, bool val) {
  21     u32 ix = f >> 3;
  22     u8 msk = 1 << (f & 7);
  23     data[ix] = val ? (data[ix] | msk) : (data[ix] & ~msk);
  24   }
  25   bool testBit(u32 f) const {
  26     u32 ix = f >> 3;
  27     u8 msk = 1 << (f & 7);
  28     return (data[ix] & msk) != 0;
  29   }
  30   void clear() {
  31     memset(&data, 0, sizeof(data));
  32   }
  33 };
  34 template <unsigned N> struct _BitStore<N, true> {
  35   static_assert(N > 0 && N <= 64,
  36                 "_BitStore<N,true> doesn't support more than 64 bits");
  37   enum {
  38     N1 = N - 1,
  39     N2 = N1 | (N1 >> 1),
  40     N3 = N2 | (N2 >> 2),
  41     N4 = N3 | (N3 >> 4),
  42     N5 = N4 <= 7 ? 7 : N4,
  43   };
  44   typedef typename UInt<N5 + 1>::Type DataType;
  45   DataType data;
  46
  47   void setBit(u32 f, bool val) {
  48     DataType msk = DataType(1) << f;
  49     data = val ? (data | msk) : (data & ~msk);
  50   }
  51   bool testBit(u32 f) const {
  52     DataType msk = DataType(1) << f;
  53     return (data & msk) != 0;
  54   }
  55   void clear() {
  56     data = 0;
  57   }
  58 };
  59 template <unsigned N> struct BitStore : _BitStore<N, (sizeof(unsigned) <= sizeof(iptr))> {};
  60 } // end of namespace jitcs
  61
  62 #endif
  63 // _JITCS_ADT_BITSTORE_H_