/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ADT/PackedVector.h
Line | Count | Source |
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 | 175k | static T getValue(const BitVectorTy &Bits, unsigned Idx) { |
32 | 175k | T val = T(); |
33 | 525k | for (unsigned i = 0; i != BitNum525k ; ++i350k ) |
34 | 350k | val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 350k 1UL176k : 0UL173k ) << i)); |
35 | 175k | return val; |
36 | 175k | } |
37 | | |
38 | 200k | static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { |
39 | 200k | assert((val >> BitNum) == 0 && "value is too big"); |
40 | 602k | for (unsigned i = 0; i != BitNum602k ; ++i401k ) |
41 | 401k | Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); |
42 | 200k | } |
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 | | /// \brief 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 | 376k | reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {} |
90 | | |
91 | 200k | reference &operator=(T val) { |
92 | 200k | Vec.setValue(Vec.Bits, Idx, val); |
93 | 200k | return *this; |
94 | 200k | } |
95 | | |
96 | 175k | operator T() const { |
97 | 175k | return Vec.getValue(Vec.Bits, Idx); |
98 | 175k | } |
99 | | }; |
100 | | |
101 | 678k | PackedVector() = default; |
102 | | explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {} |
103 | | |
104 | | 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 | 583k | void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); } |
111 | | |
112 | | void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); } |
113 | | |
114 | 233k | PackedVector &reset() { |
115 | 233k | Bits.reset(); |
116 | 233k | return *this; |
117 | 233k | } |
118 | | |
119 | | void push_back(T val) { |
120 | | resize(size()+1); |
121 | | (*this)[size()-1] = val; |
122 | | } |
123 | | |
124 | 376k | reference operator[](unsigned Idx) { |
125 | 376k | return reference(*this, Idx); |
126 | 376k | } |
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 | 233k | bool operator!=(const PackedVector &RHS) const { |
137 | 233k | return Bits != RHS.Bits; |
138 | 233k | } |
139 | | |
140 | 75.1k | PackedVector &operator|=(const PackedVector &RHS) { |
141 | 75.1k | Bits |= RHS.Bits; |
142 | 75.1k | return *this; |
143 | 75.1k | } |
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 |