bit-vector.cpp

   1 #include <stdexcept>
   2 #include "bit-vector.hpp"
   3 #include <cstdio>
   4
   5 static inline uint8_t pow2_mult8(uint8_t x){
   6   return (~((x & (x-1))==0) + 1) & (x >> 3);
   7
   8 }
   9
  10 static inline size_t uint32bits(size_t bits){
  11   return ((bits-1) / W) + 1;
  12 }
  13
  14
  15 static void array_copy(const uint32_t * src, uint32_t * dst, size_t len)
  16 {
  17   for(size_t i = 0; i < len; i++) dst[i] = src[i];
  18 }
  19
  20 size_t bit_vector::allocforsize(size_t bits)
  21 {
  22   size_t i = _alloc;
  23   while (uint32bits(bits) >= i)
  24     i = 2*i+1;
  25   return i;
  26 }
  27
  28 void bit_vector::grow(size_t alloc)
  29 {
  30   if (alloc <= _alloc)
  31     return;
  32
  33   uint32_t* vector = new uint32_t[ alloc ];
  34
  35   array_copy(_vector,vector,_alloc);
  36
  37   if (!_leaked) delete [] _vector;
  38   _vector = vector;
  39   _alloc = alloc;
  40   _leaked = false;
  41   return;
  42 }
  43
  44
  45 bit_vector::bit_vector (size_t len, size_t blen, uint32_t init)
  46 {
  47   _size = len*blen;
  48   _leaked = false;
  49   if (_size == 0) {
  50     _alloc = 0;
  51     _vector = 0;
  52     return;
  53   };
  54   _alloc = uint32bits(_size);
  55   _vector = new uint32_t[_alloc];
  56
  57   for(size_t i = 0; i < len; ++i) set_field(i,blen, init);
  58   return;
  59 }
  60
  61 bit_vector::bit_vector(int fd)
  62 {
  63   ssize_t toread = sizeof(size_t);
  64   auto msg = std::runtime_error("I/O error in bit_vector::read");
  65   _leaked = false;
  66   if (toread != read(fd, &_size,  toread))
  67     throw msg;
  68
  69   _alloc = uint32bits(_size);
  70   _vector = new uint32_t[_alloc];
  71
  72   toread = sizeof(uint32_t);
  73   for(size_t i = 0; i < _alloc; ++i)
  74     if (toread != read(fd, &_vector[i], toread)){
  75       delete [] _vector;
  76       _vector = 0;
  77       throw msg;
  78     };
  79   return;
  80
  81 }
  82
  83 bit_vector::bit_vector (const bit_vector& src)
  84 {
  85   _leaked = false;
  86   _size = src._size;
  87   _vector = new uint32_t[ _alloc = src._alloc ];
  88   array_copy(src._vector,_vector,_alloc);
  89 }
  90
  91 bit_vector & bit_vector::operator=(const bit_vector& src)
  92 {
  93   if (this != &src) {
  94     _size = src._size;
  95     delete [] _vector;
  96     _vector = new uint32_t[ _alloc = src._alloc ];
  97     array_copy(src._vector,_vector,_alloc);
  98     _leaked = false;
  99   };
 100   return *this;
 101 }
 102
 103 bit_vector::~bit_vector()
 104 {
 105   if (!_leaked) delete [] _vector;
 106   _size = 0;
 107   _vector = 0;
 108   _alloc = 0;
 109 }
 110
 111
 112
 113 void bit_vector::save(int fd) const
 114 {
 115
 116   ssize_t towrite = sizeof(size_t);
 117   std::string msg = "I/O error in bit_vector::write";
 118
 119   if (towrite != write(fd,&_size,towrite))
 120     throw msg;
 121
 122   towrite = sizeof(uint32_t);
 123
 124   for (size_t i = 0; i < _alloc; ++i)
 125     if (towrite != write(fd, &_vector[i], towrite))
 126       throw msg;
 127
 128   return;
 129
 130 }
 131
 132
 133 void bit_vector::pack()
 134 {
 135
 136   size_t nalloc = uint32bits(_size);
 137   uint32_t * nvector = new uint32_t[nalloc];
 138   array_copy(_vector, nvector, nalloc);
 139   if (!_leaked && _vector) delete [] _vector;
 140   _alloc = nalloc;
 141   this->_vector = nvector;
 142   this->_leaked = false;
 143
 144 }
 145
 146 //sets the idxth bit to b
 147 void bit_vector::set(size_t idx, bool b)
 148 {
 149   size_t i = idx / W;
 150   size_t j = idx % W;
 151   grow(allocforsize(idx+1));
 152   if (idx >= _size)
 153     _size = idx+1;
 154   uint32_t mask = 1 << (W - 1 - j);
 155   if (b)
 156     _vector[i] |=  mask;
 157   else
 158     _vector[i] &= ~mask;
 159 }
 160 void bit_vector::set_le(size_t idx, bool b)
 161 {
 162   size_t i = idx / W;
 163   size_t j = idx % W;
 164   grow(allocforsize(idx+1));
 165   if (idx >= _size)
 166     _size = idx+1;
 167   uint32_t mask = 1 << j;
 168   if (b)
 169     _vector[i] |=  mask;
 170   else
 171     _vector[i] &= ~mask;
 172 }
 173
 174 void bit_vector::push_back(bool b)
 175 {
 176   set(_size, b);
 177 }
 178
 179 bool bit_vector::pop_back()
 180 {
 181   _size--;
 182   return unsafe_get(_size);
 183 }
 184
 185 bool bit_vector::flip(size_t idx)
 186 {
 187   bool b = get(idx);
 188   set(idx, !b);
 189   return b;
 190 }
 191
 192 void bit_vector::set_field(size_t index, size_t len, uint32_t v)
 193 {
 194   size_t i=index*len/W, j=index*len-i*W;
 195
 196   grow(allocforsize((index+2)*len));
 197   if (j+len > W){
 198     if ((index+1)*len >= _size)
 199       _size = (index+2)*len;
 200   } else if (index*len >= _size)
 201       _size = (index+1)*len;
 202
 203   uint32_t mask = ((j+len) < W ? ~0U << (j+len) : 0)
 204           | ((W-j) < W ? ~0U >> (W-j) : 0);
 205   _vector[i] = (_vector[i] & mask) | v << j;
 206
 207   if (j+len>W) {
 208     mask = ((~0U) << (len+j-W));
 209     _vector[i+1] = (_vector[i+1] & mask)| v >> (W-j);
 210   }
 211 }
 212
 213 bool bit_vector::get(size_t index) const
 214 {
 215   if (index >= _size)
 216     throw (std::out_of_range("bit_vector::get"));
 217
 218   return unsafe_get(index);
 219 }
 220
 221 uint32_t bit_vector::get_field(size_t index, size_t len) const
 222 {
 223   if ((index+1)*len > _size)
 224     throw (std::out_of_range("bit_vector::get_field: index out of bound"));
 225   if (len > W)
 226     throw (std::invalid_argument("bit_vector::get_field: len > 32" ));
 227
 228   return unsafe_get_field(index, len);
 229 }
 230
 231 uint32_t * bit_vector::get_vector() const
 232 {
 233   uint32_t * vector = new uint32_t[_alloc];
 234   array_copy(_vector,vector,_alloc);
 235   return vector;
 236 }
 237
 238 void bit_vector::debug(void) const
 239 {
 240   for(size_t i = 0; i < _size; i++)
 241     fprintf(stderr, "%i ", get(i));
 242   fprintf(stderr, "\n");
 243
 244
 245 }