include/llvm/ADT/PackedVector.h

   1 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the PackedVector class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_PACKEDVECTOR_H
  15 #define LLVM_ADT_PACKEDVECTOR_H
  16
  17 #include "llvm/ADT/BitVector.h"
  18 #include <limits>
  19
  20 namespace llvm {
  21
  22 template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
  23 class PackedVectorBase;
  24
  25 // This won't be necessary if we can specialize members without specializing
  26 // the parent template.
  27 template <typename T, unsigned BitNum, typename BitVectorTy>
  28 class PackedVectorBase<T, BitNum, BitVectorTy, false> {
  29 protected:
  30   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
  31     T val = T();
  32     for (unsigned i = 0; i != BitNum; ++i)
  33       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
  34     return val;
  35   }
  36
  37   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
  38     assert((val >> BitNum) == 0 && "value is too big");
  39     for (unsigned i = 0; i != BitNum; ++i)
  40       Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
  41   }
  42 };
  43
  44 template <typename T, unsigned BitNum, typename BitVectorTy>
  45 class PackedVectorBase<T, BitNum, BitVectorTy, true> {
  46 protected:
  47   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
  48     T val = T();
  49     for (unsigned i = 0; i != BitNum-1; ++i)
  50       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
  51     if (Bits[(Idx << (BitNum-1)) + BitNum-1])
  52       val = ~val;
  53     return val;
  54   }
  55
  56   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
  57     if (val < 0) {
  58       val = ~val;
  59       Bits.set((Idx << (BitNum-1)) + BitNum-1);
  60     }
  61     assert((val >> (BitNum-1)) == 0 && "value is too big");
  62     for (unsigned i = 0; i != BitNum-1; ++i)
  63       Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
  64   }
  65 };
  66
  67 /// \brief Store a vector of values using a specific number of bits for each
  68 /// value. Both signed and unsigned types can be used, e.g
  69 /// @code
  70 ///   PackedVector<signed, 2> vec;
  71 /// @endcode
  72 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
  73 /// an assertion.
  74 template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
  75 class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
  76                                             std::numeric_limits<T>::is_signed> {
  77   BitVectorTy Bits;
  78   typedef PackedVectorBase<T, BitNum, BitVectorTy,
  79                            std::numeric_limits<T>::is_signed> base;
  80
  81 public:
  82   class reference {
  83     PackedVector &Vec;
  84     const unsigned Idx;
  85
  86     reference();  // Undefined
  87   public:
  88     reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { }
  89
  90     reference &operator=(T val) {
  91       Vec.setValue(Vec.Bits, Idx, val);
  92       return *this;
  93     }
  94     operator T() const {
  95       return Vec.getValue(Vec.Bits, Idx);
  96     }
  97   };
  98
  99   PackedVector() { }
 100   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
 101
 102   bool empty() const { return Bits.empty(); }
 103
 104   unsigned size() const { return Bits.size() >> (BitNum-1); }
 105
 106   void clear() { Bits.clear(); }
 107
 108   void resize(unsigned N) { Bits.resize(N << (BitNum-1)); }
 109
 110   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
 111
 112   PackedVector &reset() {
 113     Bits.reset();
 114     return *this;
 115   }
 116
 117   void push_back(T val) {
 118     resize(size()+1);
 119     (*this)[size()-1] = val;
 120   }
 121
 122   reference operator[](unsigned Idx) {
 123     return reference(*this, Idx);
 124   }
 125
 126   T operator[](unsigned Idx) const {
 127     return base::getValue(Bits, Idx);
 128   }
 129
 130   bool operator==(const PackedVector &RHS) const {
 131     return Bits == RHS.Bits;
 132   }
 133
 134   bool operator!=(const PackedVector &RHS) const {
 135     return Bits != RHS.Bits;
 136   }
 137
 138   const PackedVector &operator=(const PackedVector &RHS) {
 139     Bits = RHS.Bits;
 140     return *this;
 141   }
 142
 143   PackedVector &operator|=(const PackedVector &RHS) {
 144     Bits |= RHS.Bits;
 145     return *this;
 146   }
 147
 148   void swap(PackedVector &RHS) {
 149     Bits.swap(RHS.Bits);
 150   }
 151 };
 152
 153 // Leave BitNum=0 undefined.
 154 template <typename T>
 155 class PackedVector<T, 0>;
 156
 157 } // end llvm namespace
 158
 159 #endif