1//===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the PackedVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_PACKEDVECTOR_H
14#define LLVM_ADT_PACKEDVECTOR_H
15
16#include "llvm/ADT/BitVector.h"
17#include <cassert>
18#include <limits>
19
20namespace llvm {
21
22template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
23class PackedVectorBase;
24
25// This won't be necessary if we can specialize members without specializing
26// the parent template.
27template <typename T, unsigned BitNum, typename BitVectorTy>
28class PackedVectorBase<T, BitNum, BitVectorTy, false> {
29protected:
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
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
44template <typename T, unsigned BitNum, typename BitVectorTy>
45class PackedVectorBase<T, BitNum, BitVectorTy, true> {
46protected:
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
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/// 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.
74template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
75class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
76 std::numeric_limits<T>::is_signed> {
77 BitVectorTy Bits;
78 using base = PackedVectorBase<T, BitNum, BitVectorTy,
79 std::numeric_limits<T>::is_signed>;
80
81public:
82 class reference {
83 PackedVector &Vec;
84 const unsigned Idx;
85
86 public:
87 reference() = delete;
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 }
94
95 operator T() const {
96 return Vec.getValue(Vec.Bits, Idx);
97 }
98 };
99
100 PackedVector() = default;
101 explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
102
103 bool empty() const { return Bits.empty(); }
104
105 unsigned size() const { return Bits.size() >> (BitNum - 1); }
106
107 void clear() { Bits.clear(); }
108
109 void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
110
111 void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
112
113 PackedVector &reset() {
114 Bits.reset();
115 return *this;
116 }
117
118 void push_back(T val) {
119 resize(size()+1);
120 (*this)[size()-1] = val;
121 }
122
123 reference operator[](unsigned Idx) {
124 return reference(*this, Idx);
125 }
126
127 T operator[](unsigned Idx) const {
128 return base::getValue(Bits, Idx);
129 }
130
131 bool operator==(const PackedVector &RHS) const {
132 return Bits == RHS.Bits;
133 }
134
135 bool operator!=(const PackedVector &RHS) const {
136 return Bits != RHS.Bits;
137 }
138
139 PackedVector &operator|=(const PackedVector &RHS) {
140 Bits |= RHS.Bits;
141 return *this;
142 }
143};
144
145// Leave BitNum=0 undefined.
146template <typename T> class PackedVector<T, 0>;
147
148} // end namespace llvm
149
150#endif // LLVM_ADT_PACKEDVECTOR_H
151