llvm/ADT/PackedVector.h

0001 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file implements the PackedVector class.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_PACKEDVECTOR_H
0015 #define LLVM_ADT_PACKEDVECTOR_H
0016
0017 #include "llvm/ADT/BitVector.h"
0018 #include <cassert>
0019 #include <limits>
0020
0021 namespace llvm {
0022
0023 template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
0024 class PackedVectorBase;
0025
0026 // This won't be necessary if we can specialize members without specializing
0027 // the parent template.
0028 template <typename T, unsigned BitNum, typename BitVectorTy>
0029 class PackedVectorBase<T, BitNum, BitVectorTy, false> {
0030 protected:
0031   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
0032     T val = T();
0033     for (unsigned i = 0; i != BitNum; ++i)
0034       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
0035     return val;
0036   }
0037
0038   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
0039     assert((val >> BitNum) == 0 && "value is too big");
0040     for (unsigned i = 0; i != BitNum; ++i)
0041       Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
0042   }
0043 };
0044
0045 template <typename T, unsigned BitNum, typename BitVectorTy>
0046 class PackedVectorBase<T, BitNum, BitVectorTy, true> {
0047 protected:
0048   static T getValue(const BitVectorTy &Bits, unsigned Idx) {
0049     T val = T();
0050     for (unsigned i = 0; i != BitNum-1; ++i)
0051       val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
0052     if (Bits[(Idx << (BitNum-1)) + BitNum-1])
0053       val = ~val;
0054     return val;
0055   }
0056
0057   static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
0058     if (val < 0) {
0059       val = ~val;
0060       Bits.set((Idx << (BitNum-1)) + BitNum-1);
0061     }
0062     assert((val >> (BitNum-1)) == 0 && "value is too big");
0063     for (unsigned i = 0; i != BitNum-1; ++i)
0064       Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
0065   }
0066 };
0067
0068 /// Store a vector of values using a specific number of bits for each
0069 /// value. Both signed and unsigned types can be used, e.g
0070 /// @code
0071 ///   PackedVector<signed, 2> vec;
0072 /// @endcode
0073 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
0074 /// an assertion.
0075 template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
0076 class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
0077                                             std::numeric_limits<T>::is_signed> {
0078   BitVectorTy Bits;
0079   using base = PackedVectorBase<T, BitNum, BitVectorTy,
0080                                 std::numeric_limits<T>::is_signed>;
0081
0082 public:
0083   class reference {
0084     PackedVector &Vec;
0085     const unsigned Idx;
0086
0087   public:
0088     reference() = delete;
0089     reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {}
0090
0091     reference &operator=(T val) {
0092       Vec.setValue(Vec.Bits, Idx, val);
0093       return *this;
0094     }
0095
0096     operator T() const {
0097       return Vec.getValue(Vec.Bits, Idx);
0098     }
0099   };
0100
0101   PackedVector() = default;
0102   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
0103
0104   bool empty() const { return Bits.empty(); }
0105
0106   unsigned size() const { return Bits.size() >> (BitNum - 1); }
0107
0108   void clear() { Bits.clear(); }
0109
0110   void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
0111
0112   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
0113
0114   PackedVector &reset() {
0115     Bits.reset();
0116     return *this;
0117   }
0118
0119   void push_back(T val) {
0120     resize(size()+1);
0121     (*this)[size()-1] = val;
0122   }
0123
0124   reference operator[](unsigned Idx) {
0125     return reference(*this, Idx);
0126   }
0127
0128   T operator[](unsigned Idx) const {
0129     return base::getValue(Bits, Idx);
0130   }
0131
0132   bool operator==(const PackedVector &RHS) const {
0133     return Bits == RHS.Bits;
0134   }
0135
0136   bool operator!=(const PackedVector &RHS) const {
0137     return Bits != RHS.Bits;
0138   }
0139
0140   PackedVector &operator|=(const PackedVector &RHS) {
0141     Bits |= RHS.Bits;
0142     return *this;
0143   }
0144
0145   const BitVectorTy &raw_bits() const { return Bits; }
0146   BitVectorTy &raw_bits() { return Bits; }
0147 };
0148
0149 // Leave BitNum=0 undefined.
0150 template <typename T> class PackedVector<T, 0>;
0151
0152 } // end namespace llvm
0153
0154 #endif // LLVM_ADT_PACKEDVECTOR_H