Yi Kong | e5b9f24 | 2023-04-26 13:35:57 +0900 | [diff] [blame^] | 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(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 |