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