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
  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
  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   return (_vector[idx / W] >> (idx % W)) & true;
 121 };
 122
 123 /** Unsafe version of get_field. Does not perform bound checking.
 124     Assumes 1<= len <= sizeof(uint32_t).
 125 */
 126 inline uint32_t bit_vector::unsafe_get_field(size_t idx, size_t len) const
 127 {
 128   switch (len){
 129   case 8:
 130     return ((uint8_t*)_vector)[idx];
 131   case 16:
 132     return ((uint16_t*)_vector)[idx];
 133   case 32:
 134     return _vector[idx];
 135   case 1:
 136     return unsafe_get(idx);
 137   default:
 138    size_t idxlen = idx*len;
 139    size_t j = idxlen % W;
 140    size_t i = idxlen / W;
 141    size_t offset = W - len;
 142    return (offset >= j)
 143      ? (_vector[i] << (offset-j)) >> offset
 144      : (_vector[i] >> j) | (_vector [i+1] << (W+offset-j)) >> offset;
 145   };
 146 };
 147
 148 #endif