1 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the PackedVector class.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ADT_PACKEDVECTOR_H
15 #define LLVM_ADT_PACKEDVECTOR_H
17 #include "llvm/ADT/BitVector.h"
22 template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
23 class PackedVectorBase;
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> {
30 static T getValue(const BitVectorTy &Bits, unsigned Idx) {
32 for (unsigned i = 0; i != BitNum; ++i)
33 val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
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);
44 template <typename T, unsigned BitNum, typename BitVectorTy>
45 class PackedVectorBase<T, BitNum, BitVectorTy, true> {
47 static T getValue(const BitVectorTy &Bits, unsigned Idx) {
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])
56 static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
59 Bits.set((Idx << (BitNum-1)) + BitNum-1);
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);
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
70 /// PackedVector<signed, 2> vec;
72 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
74 template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
75 class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
76 std::numeric_limits<T>::is_signed> {
78 typedef PackedVectorBase<T, BitNum, BitVectorTy,
79 std::numeric_limits<T>::is_signed> base;
86 reference(); // Undefined
88 reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { }
90 reference &operator=(T val) {
91 Vec.setValue(Vec.Bits, Idx, val);
95 return Vec.getValue(Vec.Bits, Idx);
100 explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
102 bool empty() const { return Bits.empty(); }
104 unsigned size() const { return Bits.size() >> (BitNum-1); }
106 void clear() { Bits.clear(); }
108 void resize(unsigned N) { Bits.resize(N << (BitNum-1)); }
110 void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
112 PackedVector &reset() {
117 void push_back(T val) {
119 (*this)[size()-1] = val;
122 reference operator[](unsigned Idx) {
123 return reference(*this, Idx);
126 T operator[](unsigned Idx) const {
127 return base::getValue(Bits, Idx);
130 bool operator==(const PackedVector &RHS) const {
131 return Bits == RHS.Bits;
134 bool operator!=(const PackedVector &RHS) const {
135 return Bits != RHS.Bits;
138 const PackedVector &operator=(const PackedVector &RHS) {
143 PackedVector &operator|=(const PackedVector &RHS) {
148 void swap(PackedVector &RHS) {
153 // Leave BitNum=0 undefined.
154 template <typename T>
155 class PackedVector<T, 0>;
157 } // end llvm namespace