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