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
 150     size_t i = idx / W;
 151     size_t j = idx % W;
 152     grow(allocforsize(idx+1));
 153     if (idx >= _size)
 154       _size = idx+1;
 155     uint32_t mask = 1 << (W - 1 - j);
 156     if (b)
 157       _vector[i] |=  mask;
 158     else
 159       _vector[i] &= ~mask;
 160 }
 161
 162 void bit_vector::push_back(bool b)
 163 {
 164   set(_size, b);
 165 }
 166
 167 bool bit_vector::pop_back()
 168 {
 169   _size--;
 170   return unsafe_get(_size);
 171 }
 172
 173 bool bit_vector::flip(size_t idx)
 174 {
 175   bool b = get(idx);
 176   set(idx, !b);
 177   return b;
 178 }
 179
 180 void bit_vector::set_field(size_t index, size_t len, uint32_t v)
 181 {
 182   size_t i=index*len/W, j=index*len-i*W;
 183
 184   grow(allocforsize((index+2)*len));
 185   if (j+len > W){
 186     if ((index+1)*len >= _size)
 187       _size = (index+2)*len;
 188   } else if (index*len >= _size)
 189       _size = (index+1)*len;
 190
 191   uint32_t mask = ((j+len) < W ? ~0U << (j+len) : 0)
 192           | ((W-j) < W ? ~0U >> (W-j) : 0);
 193   _vector[i] = (_vector[i] & mask) | v << j;
 194
 195   if (j+len>W) {
 196     mask = ((~0U) << (len+j-W));
 197     _vector[i+1] = (_vector[i+1] & mask)| v >> (W-j);
 198   }
 199 }
 200
 201 bool bit_vector::get(size_t index) const
 202 {
 203   if (index >= _size)
 204     throw (std::out_of_range("bit_vector::get"));
 205
 206   return unsafe_get(index);
 207 }
 208
 209 uint32_t bit_vector::get_field(size_t index, size_t len) const
 210 {
 211   if ((index+1)*len > _size)
 212     throw (std::out_of_range("bit_vector::get_field: index out of bound"));
 213   if (len > W)
 214     throw (std::invalid_argument("bit_vector::get_field: len > 32" ));
 215
 216   return unsafe_get_field(index, len);
 217 }
 218
 219 uint32_t * bit_vector::get_vector() const
 220 {
 221   uint32_t * vector = new uint32_t[_alloc];
 222   array_copy(_vector,vector,_alloc);
 223   return vector;
 224 }