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

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

diff --git a/bit-vector.hpp b/bit-vector.hpp
new file mode 100644 (file)
index 0000000..cd6382e
--- /dev/null
+++ b/bit-vector.hpp
@@ -0,0 +1,148 @@
+#ifndef __BIT_VECTOR_HPP__
+#define __BIT_VECTOR_HPP__
+
+#include <cstdint>
+#include <cstddef>
+#include <climits>
+
+
+#ifndef W
+#define W   (sizeof(uint32_t)*CHAR_BIT)
+#define WW  (W*2)
+#endif
+
+
+/** Simple class implementing a vector of bits as an uint32_t array.
+ */
+
+class bit_vector {
+
+ public:
+  /** Builds a bit vector capable of holding len elements of blen bits each,
+      initializes the vector with the copies len times the blen lowermost bits
+      of init.
+      Throws an exception if blen == 0 or blen > 32.
+  */
+  bit_vector (size_t len=0, size_t blen=1, uint32_t init=0);
+
+  /** Load the bit_vector from a file descriptor */
+  bit_vector (int fd);
+
+  /** copy constructor */
+  bit_vector (const bit_vector& src);
+
+  bit_vector & operator=(const bit_vector& src);
+
+  /** Destructor
+   */
+  ~bit_vector ();
+
+  /** Writes the content of the the bit_vector to the file descriptor fd, in
+      binary format.
+  */
+  void save(int fd) const;
+
+  /** Returns the size of the bit_vector in bits */
+  size_t size() const { return _size; };
+
+  /** Returns the maximum number of bits that can be added without
+      reallocation
+  */
+  size_t max_size() const { return _alloc*W; };
+
+  /** Resizes the vector so that it can store size() bits and such that at most
+   sizeof(uint32_t) - 1 bits are wasted.*/
+  void pack();
+
+  /** Sets the idxth bit to b. The bit_vector is resized if necessary */
+  void set(size_t idx, bool b);
+
+  /** Adds bit b at the end of the bit_vector. The bit_vector is resized if
+      necessary */
+  void push_back(bool b);
+
+  /** Returns the last bit of the bit vector, which is removed */
+  bool pop_back();
+
+  /** Sets bits [idx*len - (idx+1)*len] of the bit vector to the len
+      lowermost bits of v.
+      Throws an exception if len == 0 or len > W
+      The bit_vector is resized if necessary.
+   */
+  void set_field(size_t idx, size_t len, uint32_t v);
+
+  /** Flips the idxth bit of the bit_vector. Returns the value of the bit
+      before flipping */
+  bool flip(size_t idx);
+
+  /** Returns the idxth bit. Performs bound checking */
+  bool get(size_t idx) const;
+
+  /** Returns the bits idx*len to (idx+1)*len, packed into an uint32_t.
+      Throws an exception if len == 0 or len > sizeof(uint32_t).
+      Performs bound checking.
+  */
+  uint32_t get_field(size_t idx, size_t len) const;
+
+  /** returns a copy of the internal vector
+   */
+  uint32_t* get_vector() const;
+  /** returns a pointer to the internal vector
+   */
+  uint32_t* get_vector_ptr() { _leaked = true; return _vector; }
+
+  /** Efficient unsafe get/get_field */
+  bool unsafe_get(size_t idx) const;
+  uint32_t unsafe_get_field(size_t idx, size_t len) const;
+
+
+private:
+  // true if get_vector_ptr() was called
+  bool _leaked;
+  // Size in bits
+  size_t _size;
+  // Allocated space in sizeof(uint32_t)
+  size_t _alloc;
+  uint32_t * _vector;
+  /** Increase the size of _vector
+   */
+
+  size_t allocforsize(size_t bits);
+  void grow(size_t alloc);
+
+
+};
+
+/** Unsafe version of get. Does not perform bound checking
+ */
+inline bool bit_vector::unsafe_get(size_t idx) const
+{
+  return (_vector[idx / W] >> (idx % W)) & true;
+};
+
+/** Unsafe version of get_field. Does not perform bound checking.
+    Assumes 1<= len <= sizeof(uint32_t).
+*/
+inline uint32_t bit_vector::unsafe_get_field(size_t idx, size_t len) const
+{
+  switch (len){
+  case 8:
+    return ((uint8_t*)_vector)[idx];
+  case 16:
+    return ((uint16_t*)_vector)[idx];
+  case 32:
+    return _vector[idx];
+  case 1:
+    return unsafe_get(idx);
+  default:
+   size_t idxlen = idx*len;
+   size_t j = idxlen % W;
+   size_t i = idxlen / W;
+   size_t offset = W - len;
+   return (offset >= j)
+     ? (_vector[i] << (offset-j)) >> offset
+     : (_vector[i] >> j) | (_vector [i+1] << (W+offset-j)) >> offset;
+  };
+};
+
+#endif