Line data Source code
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:
31 1268108 : static T getValue(const BitVectorTy &Bits, unsigned Idx) {
32 : T val = T();
33 3844676 : for (unsigned i = 0; i != BitNum; ++i)
34 3893277 : val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
35 1268108 : return val;
36 : }
37 :
38 1882157 : static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
39 : assert((val >> BitNum) == 0 && "value is too big");
40 5677409 : for (unsigned i = 0; i != BitNum; ++i)
41 3795252 : Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
42 1882157 : }
43 2 : };
44 :
45 8 : template <typename T, unsigned BitNum, typename BitVectorTy>
46 6 : class PackedVectorBase<T, BitNum, BitVectorTy, true> {
47 2 : protected:
48 14 : static T getValue(const BitVectorTy &Bits, unsigned Idx) {
49 : T val = T();
50 42 : for (unsigned i = 0; i != BitNum-1; ++i)
51 28 : val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
52 14 : 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 10 :
68 10 : /// Store a vector of values using a specific number of bits for each
69 5 : /// value. Both signed and unsigned types can be used, e.g
70 5 : /// @code
71 : /// PackedVector<signed, 2> vec;
72 : /// @endcode
73 22 : /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
74 12 : /// an assertion.
75 10 : template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
76 20631973 : class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
77 2 : std::numeric_limits<T>::is_signed> {
78 1 : BitVectorTy Bits;
79 1 : using base = PackedVectorBase<T, BitNum, BitVectorTy,
80 : std::numeric_limits<T>::is_signed>;
81 :
82 6 : public:
83 4 : class reference {
84 2 : PackedVector &Vec;
85 8 : const unsigned Idx;
86 8 :
87 4 : public:
88 4 : reference() = delete;
89 : reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {}
90 :
91 16 : reference &operator=(T val) {
92 1882149 : Vec.setValue(Vec.Bits, Idx, val);
93 8 : return *this;
94 : }
95 :
96 0 : operator T() const {
97 1258135 : return Vec.getValue(Vec.Bits, Idx);
98 : }
99 : };
100 :
101 : PackedVector() = default;
102 133 : explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
103 :
104 1 : bool empty() const { return Bits.empty(); }
105 :
106 24 : unsigned size() const { return Bits.size() >> (BitNum - 1); }
107 :
108 : void clear() { Bits.clear(); }
109 :
110 16976024 : 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 1871967 : Bits.reset();
116 : return *this;
117 : }
118 :
119 : void push_back(T val) {
120 13 : resize(size()+1);
121 : (*this)[size()-1] = val;
122 : }
123 :
124 0 : reference operator[](unsigned Idx) {
125 0 : return reference(*this, Idx);
126 : }
127 :
128 : T operator[](unsigned Idx) const {
129 : return base::getValue(Bits, Idx);
130 5 : }
131 :
132 5 : bool operator==(const PackedVector &RHS) const {
133 : return Bits == RHS.Bits;
134 3 : }
135 :
136 : bool operator!=(const PackedVector &RHS) const {
137 1871967 : return Bits != RHS.Bits;
138 2 : }
139 :
140 : PackedVector &operator|=(const PackedVector &RHS) {
141 547888 : Bits |= RHS.Bits;
142 : return *this;
143 : }
144 : };
145 :
146 : // Leave BitNum=0 undefined.
147 4 : template <typename T> class PackedVector<T, 0>;
148 4 :
149 4 : } // end namespace llvm
150 4 :
151 : #endif // LLVM_ADT_PACKEDVECTOR_H
|