Home | History | Annotate | Line # | Download | only in ADT 
      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:
     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 
     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:
     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 
     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;
     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 
     95     operator T() const {
     96       return Vec.getValue(Vec.Bits, Idx);
     97     }
     98   };
     99 
    100   PackedVector() = default;
    101   explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
    102 
    103   bool empty() const { return Bits.empty(); }
    104 
    105   unsigned size() const { return Bits.size() >> (BitNum - 1); }
    106 
    107   void clear() { Bits.clear(); }
    108 
    109   void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
    110 
    111   void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
    112 
    113   PackedVector &reset() {
    114     Bits.reset();
    115     return *this;
    116   }
    117 
    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