Huge refactoring to remove diego' C/C++ chimera code.

[SXSI/XMLTree.git] / bit-vector.cpp

diff --git a/bit-vector.cpp b/bit-vector.cpp
new file mode 100644 (file)
index 0000000..d69c177
--- /dev/null
+++ b/bit-vector.cpp
@@ -0,0 +1,223 @@
+#include <stdexcept>
+#include "bit-vector.hpp"
+
+static inline uint8_t pow2_mult8(uint8_t x){
+  return (~((x & (x-1))==0) + 1) & (x >> 3);
+
+}
+
+static inline size_t uint32bits(size_t bits){
+  return ((bits-1) / W) + 1;
+}
+
+
+
+void array_copy(const uint32_t * src, uint32_t * dst, size_t len)
+{
+  while (len--) *dst++ = *src++;
+}
+
+size_t bit_vector::allocforsize(size_t bits)
+{
+  size_t i = _alloc;
+  while (uint32bits(bits) >= i)
+    i = 2*i+1;
+  return i;
+}
+
+void bit_vector::grow(size_t alloc)
+{
+  if (alloc <= _alloc)
+    return;
+
+  uint32_t* vector = new uint32_t[ alloc ];
+
+  array_copy(_vector,vector,_alloc);
+
+  if (!_leaked) delete [] _vector;
+  _vector = vector;
+  _alloc = alloc;
+  _leaked = false;
+  return;
+}
+
+
+bit_vector::bit_vector (size_t len, size_t blen, uint32_t init)
+{
+  _size = len*blen;
+  _leaked = false;
+  if (_size == 0) {
+    _alloc = 0;
+    _vector = 0;
+    return;
+  };
+  _alloc = uint32bits(_size);
+  _vector = new uint32_t[_alloc];
+
+  for(size_t i = 0; i < len; ++i) set_field(i,blen, init);
+  return;
+}
+
+bit_vector::bit_vector(int fd)
+{
+  ssize_t toread = sizeof(size_t);
+  auto msg = std::runtime_error("I/O error in bit_vector::read");
+  _leaked = false;
+  if (toread != read(fd, &_size,  toread))
+    throw msg;
+
+  _alloc = uint32bits(_size);
+  _vector = new uint32_t[_alloc];
+
+  toread = sizeof(uint32_t);
+  for(size_t i = 0; i < _alloc; ++i)
+    if (toread != read(fd, &_vector[i], toread)){
+      delete [] _vector;
+      _vector = 0;
+      throw msg;
+    };
+  return;
+
+}
+
+bit_vector::bit_vector (const bit_vector& src)
+{
+  _leaked = false;
+  _size = src._size;
+  _vector = new uint32_t[ _alloc = src._alloc ];
+  array_copy(src._vector,_vector,_alloc);
+}
+
+bit_vector & bit_vector::operator=(const bit_vector& src)
+{
+  if (this != &src) {
+    _size = src._size;
+    delete [] _vector;
+    _vector = new uint32_t[ _alloc = src._alloc ];
+    array_copy(src._vector,_vector,_alloc);
+    _leaked = false;
+  };
+  return *this;
+}
+
+bit_vector::~bit_vector()
+{
+  if (!_leaked) delete [] _vector;
+  _size = 0;
+  _vector = 0;
+  _alloc = 0;
+}
+
+
+
+void bit_vector::save(int fd) const
+{
+
+  ssize_t towrite = sizeof(size_t);
+  std::string msg = "I/O error in bit_vector::write";
+
+  if (towrite != write(fd,&_size,towrite))
+    throw msg;
+
+  towrite = sizeof(uint32_t);
+
+  for (size_t i = 0; i < _alloc; ++i)
+    if (towrite != write(fd, &_vector[i], towrite))
+      throw msg;
+
+  return;
+
+}
+
+
+void bit_vector::pack()
+{
+
+  size_t nalloc = uint32bits(_size);
+  uint32_t * nvector = new uint32_t[nalloc];
+  array_copy(_vector,nvector,nalloc);
+  if (!_leaked) delete [] _vector;
+  _alloc = nalloc;
+  _vector = nvector;
+  _leaked = false;
+
+}
+
+//sets the idxth bit to b
+void bit_vector::set(size_t idx, bool b)
+{
+    size_t i = idx / sizeof(uint32_t);
+    size_t j = idx % sizeof(uint32_t);
+    grow(allocforsize(idx+1));
+    if (idx >= _size)
+      _size = idx+1;
+    uint32_t mask = 1 << j;
+    if (b)
+      _vector[i] |=  mask;
+    else
+      _vector[i] &= ~mask;
+}
+
+void bit_vector::push_back(bool b)
+{
+  set(_size, b);
+}
+
+bool bit_vector::pop_back()
+{
+  _size--;
+  return unsafe_get(_size);
+}
+
+bool bit_vector::flip(size_t idx)
+{
+  bool b = get(idx);
+  set(idx, !b);
+  return b;
+}
+
+void bit_vector::set_field(size_t index, size_t len, uint32_t v)
+{
+  size_t i=index*len/W, j=index*len-i*W;
+
+  grow(allocforsize((index+2)*len));
+  if (j+len > W){
+    if ((index+1)*len >= _size)
+      _size = (index+2)*len;
+  } else if (index*len >= _size)
+      _size = (index+1)*len;
+
+  uint32_t mask = ((j+len) < W ? ~0U << (j+len) : 0)
+          | ((W-j) < W ? ~0U >> (W-j) : 0);
+  _vector[i] = (_vector[i] & mask) | v << j;
+
+  if (j+len>W) {
+    mask = ((~0U) << (len+j-W));
+    _vector[i+1] = (_vector[i+1] & mask)| v >> (W-j);
+  }
+}
+
+bool bit_vector::get(size_t index) const
+{
+  if (index >= _size)
+    throw (std::out_of_range("bit_vector::get"));
+
+  return unsafe_get(index);
+}
+
+uint32_t bit_vector::get_field(size_t index, size_t len) const
+{
+  if ((index+1)*len > _size)
+    throw (std::out_of_range("bit_vector::get_field: index out of bound"));
+  if (len > W)
+    throw (std::invalid_argument("bit_vector::get_field: len > 32" ));
+
+  return unsafe_get_field(index, len);
+}
+
+uint32_t * bit_vector::get_vector() const
+{
+  uint32_t * vector = new uint32_t[_alloc];
+  array_copy(_vector,vector,_alloc);
+  return vector;
+}