1 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements the PackedVector class.
11 //===----------------------------------------------------------------------===//
13 #ifndef LLVM_ADT_PACKEDVECTOR_H
14 #define LLVM_ADT_PACKEDVECTOR_H
16 #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 /// 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 using base
= PackedVectorBase
<T
, BitNum
, BitVectorTy
,
79 std::numeric_limits
<T
>::is_signed
>;
88 reference(PackedVector
&vec
, unsigned idx
) : Vec(vec
), Idx(idx
) {}
90 reference
&operator=(T val
) {
91 Vec
.setValue(Vec
.Bits
, Idx
, val
);
96 return Vec
.getValue(Vec
.Bits
, Idx
);
100 PackedVector() = default;
101 explicit PackedVector(unsigned size
) : Bits(size
<< (BitNum
-1)) {}
103 bool empty() const { return Bits
.empty(); }
105 unsigned size() const { return Bits
.size() >> (BitNum
- 1); }
107 void clear() { Bits
.clear(); }
109 void resize(unsigned N
) { Bits
.resize(N
<< (BitNum
- 1)); }
111 void reserve(unsigned N
) { Bits
.reserve(N
<< (BitNum
-1)); }
113 PackedVector
&reset() {
118 void push_back(T val
) {
120 (*this)[size()-1] = val
;
123 reference
operator[](unsigned Idx
) {
124 return reference(*this, Idx
);
127 T
operator[](unsigned Idx
) const {
128 return base::getValue(Bits
, Idx
);
131 bool operator==(const PackedVector
&RHS
) const {
132 return Bits
== RHS
.Bits
;
135 bool operator!=(const PackedVector
&RHS
) const {
136 return Bits
!= RHS
.Bits
;
139 PackedVector
&operator|=(const PackedVector
&RHS
) {
145 // Leave BitNum=0 undefined.
146 template <typename T
> class PackedVector
<T
, 0>;
148 } // end namespace llvm
150 #endif // LLVM_ADT_PACKEDVECTOR_H