Home | History | Annotate | Download | only in ADT 
      1 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     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 /// \brief 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
    152