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, 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> 28 class PackedVectorBase<T, BitNum, false> { 29 protected: 30 static T getValue(const llvm::BitVector &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(llvm::BitVector &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> 45 class PackedVectorBase<T, BitNum, true> { 46 protected: 47 static T getValue(const llvm::BitVector &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(llvm::BitVector &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> 75 class PackedVector : public PackedVectorBase<T, BitNum, 76 std::numeric_limits<T>::is_signed> { 77 llvm::BitVector Bits; 78 typedef PackedVectorBase<T, BitNum, std::numeric_limits<T>::is_signed> base; 79 80 public: 81 class reference { 82 PackedVector &Vec; 83 const unsigned Idx; 84 85 reference(); // Undefined 86 public: 87 reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { } 88 89 reference &operator=(T val) { 90 Vec.setValue(Vec.Bits, Idx, val); 91 return *this; 92 } 93 operator T() const { 94 return Vec.getValue(Vec.Bits, Idx); 95 } 96 }; 97 98 PackedVector() { } 99 explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { } 100 101 bool empty() const { return Bits.empty(); } 102 103 unsigned size() const { return Bits.size() >> (BitNum-1); } 104 105 void clear() { Bits.clear(); } 106 107 void resize(unsigned N) { Bits.resize(N << (BitNum-1)); } 108 109 void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); } 110 111 PackedVector &reset() { 112 Bits.reset(); 113 return *this; 114 } 115 116 void push_back(T val) { 117 resize(size()+1); 118 (*this)[size()-1] = val; 119 } 120 121 reference operator[](unsigned Idx) { 122 return reference(*this, Idx); 123 } 124 125 T operator[](unsigned Idx) const { 126 return base::getValue(Bits, Idx); 127 } 128 129 bool operator==(const PackedVector &RHS) const { 130 return Bits == RHS.Bits; 131 } 132 133 bool operator!=(const PackedVector &RHS) const { 134 return Bits != RHS.Bits; 135 } 136 137 const PackedVector &operator=(const PackedVector &RHS) { 138 Bits = RHS.Bits; 139 return *this; 140 } 141 142 PackedVector &operator|=(const PackedVector &RHS) { 143 Bits |= RHS.Bits; 144 return *this; 145 } 146 147 void swap(PackedVector &RHS) { 148 Bits.swap(RHS.Bits); 149 } 150 }; 151 152 // Leave BitNum=0 undefined. 153 template <typename T> 154 class PackedVector<T, 0>; 155 156 } // end llvm namespace 157 158 #endif 159
