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 // This file implements the PackedVector class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ADT_PACKEDVECTOR_H 14 #define LLVM_ADT_PACKEDVECTOR_H 15 16 #include "llvm/ADT/BitVector.h" 17 #include <cassert> 18 #include <limits> 19 20 namespace llvm { 21 22 template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned> 23 class PackedVectorBase; 24 25 // This won't be necessary if we can specialize members without specializing 26 // the parent template. 27 template <typename T, unsigned BitNum, typename BitVectorTy> 28 class PackedVectorBase<T, BitNum, BitVectorTy, false> { 29 protected: getValue(const BitVectorTy & Bits,unsigned Idx)30 static T getValue(const BitVectorTy &Bits, unsigned Idx) { 31 T val = T(); 32 for (unsigned i = 0; i != BitNum; ++i) 33 val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); 34 return val; 35 } 36 setValue(BitVectorTy & Bits,unsigned Idx,T val)37 static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { 38 assert((val >> BitNum) == 0 && "value is too big"); 39 for (unsigned i = 0; i != BitNum; ++i) 40 Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); 41 } 42 }; 43 44 template <typename T, unsigned BitNum, typename BitVectorTy> 45 class PackedVectorBase<T, BitNum, BitVectorTy, true> { 46 protected: getValue(const BitVectorTy & Bits,unsigned Idx)47 static T getValue(const BitVectorTy &Bits, unsigned Idx) { 48 T val = T(); 49 for (unsigned i = 0; i != BitNum-1; ++i) 50 val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); 51 if (Bits[(Idx << (BitNum-1)) + BitNum-1]) 52 val = ~val; 53 return val; 54 } 55 setValue(BitVectorTy & Bits,unsigned Idx,T val)56 static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { 57 if (val < 0) { 58 val = ~val; 59 Bits.set((Idx << (BitNum-1)) + BitNum-1); 60 } 61 assert((val >> (BitNum-1)) == 0 && "value is too big"); 62 for (unsigned i = 0; i != BitNum-1; ++i) 63 Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); 64 } 65 }; 66 67 /// Store a vector of values using a specific number of bits for each 68 /// value. Both signed and unsigned types can be used, e.g 69 /// @code 70 /// PackedVector<signed, 2> vec; 71 /// @endcode 72 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit 73 /// an assertion. 74 template <typename T, unsigned BitNum, typename BitVectorTy = BitVector> 75 class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy, 76 std::numeric_limits<T>::is_signed> { 77 BitVectorTy Bits; 78 using base = PackedVectorBase<T, BitNum, BitVectorTy, 79 std::numeric_limits<T>::is_signed>; 80 81 public: 82 class reference { 83 PackedVector &Vec; 84 const unsigned Idx; 85 86 public: 87 reference() = delete; reference(PackedVector & vec,unsigned idx)88 reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {} 89 90 reference &operator=(T val) { 91 Vec.setValue(Vec.Bits, Idx, val); 92 return *this; 93 } 94 T()95 operator T() const { 96 return Vec.getValue(Vec.Bits, Idx); 97 } 98 }; 99 100 PackedVector() = default; PackedVector(unsigned size)101 explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {} 102 empty()103 bool empty() const { return Bits.empty(); } 104 size()105 unsigned size() const { return Bits.size() >> (BitNum - 1); } 106 clear()107 void clear() { Bits.clear(); } 108 resize(unsigned N)109 void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); } 110 reserve(unsigned N)111 void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); } 112 reset()113 PackedVector &reset() { 114 Bits.reset(); 115 return *this; 116 } 117 push_back(T val)118 void push_back(T val) { 119 resize(size()+1); 120 (*this)[size()-1] = val; 121 } 122 123 reference operator[](unsigned Idx) { 124 return reference(*this, Idx); 125 } 126 127 T operator[](unsigned Idx) const { 128 return base::getValue(Bits, Idx); 129 } 130 131 bool operator==(const PackedVector &RHS) const { 132 return Bits == RHS.Bits; 133 } 134 135 bool operator!=(const PackedVector &RHS) const { 136 return Bits != RHS.Bits; 137 } 138 139 PackedVector &operator|=(const PackedVector &RHS) { 140 Bits |= RHS.Bits; 141 return *this; 142 } 143 }; 144 145 // Leave BitNum=0 undefined. 146 template <typename T> class PackedVector<T, 0>; 147 148 } // end namespace llvm 149 150 #endif // LLVM_ADT_PACKEDVECTOR_H 151