bit-vector.hpp

   1 #ifndef __BIT_VECTOR_HPP__
   2 #define __BIT_VECTOR_HPP__
   3
   4 #include <cstdint>
   5 #include <cstddef>
   6 #include <climits>
   7
   8
   9 #ifndef W
  10 #define W   (sizeof(uint32_t)*CHAR_BIT)
  11 #define WW  (W*2)
  12 #endif
  13
  14
  15 /** Simple class implementing a vector of bits as an uint32_t array.
  16  */
  17
  18 class bit_vector {
  19
  20  public:
  21   /** Builds a bit vector capable of holding len elements of blen bits each,
  22       initializes the vector with the copies len times the blen lowermost bits
  23       of init.
  24       Throws an exception if blen == 0 or blen > 32.
  25   */
  26   bit_vector (size_t len=0, size_t blen=1, uint32_t init=0);
  27
  28   /** Load the bit_vector from a file descriptor */
  29   bit_vector (int fd);
  30
  31   /** copy constructor */
  32   bit_vector (const bit_vector& src);
  33
  34   bit_vector & operator=(const bit_vector& src);
  35
  36   /** Destructor
  37    */
  38   ~bit_vector ();
  39
  40   /** Writes the content of the the bit_vector to the file descriptor fd, in
  41       binary format.
  42   */
  43   void save(int fd) const;
  44
  45   /** Returns the size of the bit_vector in bits */
  46   size_t size() const { return _size; };
  47
  48   /** Returns the maximum number of bits that can be added without
  49       reallocation
  50   */
  51   size_t max_size() const { return _alloc*W; };
  52
  53   /** Resizes the vector so that it can store size() bits and such that at most
  54    sizeof(uint32_t) - 1 bits are wasted.*/
  55   void pack();
  56
  57   /** Sets the idxth bit to b. The bit_vector is resized if necessary */
  58   void set(size_t idx, bool b);
  59   void set_le(size_t idx, bool b);
  60   /** Adds bit b at the end of the bit_vector. The bit_vector is resized if
  61       necessary */
  62   void push_back(bool b);
  63
  64   /** Returns the last bit of the bit vector, which is removed */
  65   bool pop_back();
  66
  67   /** Sets bits [idx*len - (idx+1)*len] of the bit vector to the len
  68       lowermost bits of v.
  69       Throws an exception if len == 0 or len > W
  70       The bit_vector is resized if necessary.
  71    */
  72   void set_field(size_t idx, size_t len, uint32_t v);
  73
  74   /** Flips the idxth bit of the bit_vector. Returns the value of the bit
  75       before flipping */
  76   bool flip(size_t idx);
  77
  78   /** Returns the idxth bit. Performs bound checking */
  79   bool get(size_t idx) const;
  80
  81   /** Returns the bits idx*len to (idx+1)*len, packed into an uint32_t.
  82       Throws an exception if len == 0 or len > sizeof(uint32_t).
  83       Performs bound checking.
  84   */
  85   uint32_t get_field(size_t idx, size_t len) const;
  86
  87   /** returns a copy of the internal vector
  88    */
  89   uint32_t* get_vector() const;
  90   /** returns a pointer to the internal vector
  91    */
  92   uint32_t* get_vector_ptr() { _leaked = true; return _vector; }
  93
  94   /** Efficient unsafe get/get_field */
  95   bool unsafe_get(size_t idx) const;
  96   uint32_t unsafe_get_field(size_t idx, size_t len) const;
  97   void debug(void) const;
  98
  99 private:
 100   // true if get_vector_ptr() was called
 101   bool _leaked;
 102   // Size in bits
 103   size_t _size;
 104   // Allocated space in sizeof(uint32_t)
 105   size_t _alloc;
 106   uint32_t * _vector;
 107   /** Increase the size of _vector
 108    */
 109
 110   size_t allocforsize(size_t bits);
 111   void grow(size_t alloc);
 112
 113
 114 };
 115
 116 /** Unsafe version of get. Does not perform bound checking
 117  */
 118 inline bool bit_vector::unsafe_get(size_t idx) const
 119 {
 120   size_t i = idx / W;
 121   size_t j = idx % W;
 122   return (_vector[i] >> (W - 1 - j)) & true;
 123 };
 124
 125 /** Unsafe version of get_field. Does not perform bound checking.
 126     Assumes 1<= len <= sizeof(uint32_t).
 127 */
 128 inline uint32_t bit_vector::unsafe_get_field(size_t idx, size_t len) const
 129 {
 130   //TODO FIX TO REFLECT BIG ENDIAN ORDER.
 131   switch (len){
 132   case 8:
 133     return ((uint8_t*)_vector)[idx];
 134   case 16:
 135     return ((uint16_t*)_vector)[idx];
 136   case 32:
 137     return _vector[idx];
 138   case 1:
 139     return unsafe_get(idx);
 140   default:
 141    size_t idxlen = idx*len;
 142    size_t j = idxlen % W;
 143    size_t i = idxlen / W;
 144    size_t offset = W - len;
 145    return (offset >= j)
 146      ? (_vector[i] << (offset-j)) >> offset
 147      : (_vector[i] >> j) | (_vector [i+1] << (W+offset-j)) >> offset;
 148   };
 149 };
 150
 151 #endif