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:
getValue(const BitVectorTy & Bits,unsigned Idx)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 
setValue(BitVectorTy & Bits,unsigned Idx,T val)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:
getValue(const BitVectorTy & Bits,unsigned Idx)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 
setValue(BitVectorTy & Bits,unsigned Idx,T val)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 /// 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;
reference(PackedVector & vec,unsigned idx)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 
T()96     operator T() const {
97       return Vec.getValue(Vec.Bits, Idx);
98     }
99   };
100 
101   PackedVector() = default;
PackedVector(unsigned size)102   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
103 
empty()104   bool empty() const { return Bits.empty(); }
105 
size()106   unsigned size() const { return Bits.size() >> (BitNum - 1); }
107 
clear()108   void clear() { Bits.clear(); }
109 
resize(unsigned N)110   void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
111 
reserve(unsigned N)112   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
113 
reset()114   PackedVector &reset() {
115     Bits.reset();
116     return *this;
117   }
118 
push_back(T val)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
152