Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 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 |