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:
getValue(const BitVectorTy & Bits,unsigned Idx)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 
setValue(BitVectorTy & Bits,unsigned Idx,T val)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:
getValue(const BitVectorTy & Bits,unsigned Idx)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 
setValue(BitVectorTy & Bits,unsigned Idx,T val)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:
reference(PackedVector & vec,unsigned idx)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     }
T()94     operator T() const {
95       return Vec.getValue(Vec.Bits, Idx);
96     }
97   };
98 
99   PackedVector() = default;
PackedVector(unsigned size)100   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
101 
empty()102   bool empty() const { return Bits.empty(); }
103 
size()104   unsigned size() const { return Bits.size() >> (BitNum - 1); }
105 
clear()106   void clear() { Bits.clear(); }
107 
resize(unsigned N)108   void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
109 
reserve(unsigned N)110   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
111 
reset()112   PackedVector &reset() {
113     Bits.reset();
114     return *this;
115   }
116 
push_back(T val)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   PackedVector &operator|=(const PackedVector &RHS) {
139     Bits |= RHS.Bits;
140     return *this;
141   }
142 };
143 
144 // Leave BitNum=0 undefined.
145 template <typename T> class PackedVector<T, 0>;
146 
147 } // end llvm namespace
148 
149 #endif
150