bit-vector.cpp

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