1223013Sdim//===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===// 2223013Sdim// 3223013Sdim// The LLVM Compiler Infrastructure 4223013Sdim// 5223013Sdim// This file is distributed under the University of Illinois Open Source 6223013Sdim// License. See LICENSE.TXT for details. 7223013Sdim// 8223013Sdim//===----------------------------------------------------------------------===// 9223013Sdim// 10223013Sdim// This file implements the PackedVector class. 11223013Sdim// 12223013Sdim//===----------------------------------------------------------------------===// 13223013Sdim 14223013Sdim#ifndef LLVM_ADT_PACKEDVECTOR_H 15223013Sdim#define LLVM_ADT_PACKEDVECTOR_H 16223013Sdim 17223013Sdim#include "llvm/ADT/BitVector.h" 18223013Sdim#include <limits> 19223013Sdim 20223013Sdimnamespace llvm { 21223013Sdim 22243830Sdimtemplate <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned> 23223013Sdimclass PackedVectorBase; 24223013Sdim 25223013Sdim// This won't be necessary if we can specialize members without specializing 26223013Sdim// the parent template. 27243830Sdimtemplate <typename T, unsigned BitNum, typename BitVectorTy> 28243830Sdimclass PackedVectorBase<T, BitNum, BitVectorTy, false> { 29223013Sdimprotected: 30243830Sdim static T getValue(const BitVectorTy &Bits, unsigned Idx) { 31223013Sdim T val = T(); 32223013Sdim for (unsigned i = 0; i != BitNum; ++i) 33223013Sdim val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); 34223013Sdim return val; 35223013Sdim } 36223013Sdim 37243830Sdim static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { 38223013Sdim assert((val >> BitNum) == 0 && "value is too big"); 39223013Sdim for (unsigned i = 0; i != BitNum; ++i) 40223013Sdim Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); 41223013Sdim } 42223013Sdim}; 43223013Sdim 44243830Sdimtemplate <typename T, unsigned BitNum, typename BitVectorTy> 45243830Sdimclass PackedVectorBase<T, BitNum, BitVectorTy, true> { 46223013Sdimprotected: 47243830Sdim static T getValue(const BitVectorTy &Bits, unsigned Idx) { 48223013Sdim T val = T(); 49223013Sdim for (unsigned i = 0; i != BitNum-1; ++i) 50223013Sdim val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i)); 51223013Sdim if (Bits[(Idx << (BitNum-1)) + BitNum-1]) 52223013Sdim val = ~val; 53223013Sdim return val; 54223013Sdim } 55223013Sdim 56243830Sdim static void setValue(BitVectorTy &Bits, unsigned Idx, T val) { 57223013Sdim if (val < 0) { 58223013Sdim val = ~val; 59223013Sdim Bits.set((Idx << (BitNum-1)) + BitNum-1); 60223013Sdim } 61223013Sdim assert((val >> (BitNum-1)) == 0 && "value is too big"); 62223013Sdim for (unsigned i = 0; i != BitNum-1; ++i) 63223013Sdim Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i); 64223013Sdim } 65223013Sdim}; 66223013Sdim 67223013Sdim/// \brief Store a vector of values using a specific number of bits for each 68223013Sdim/// value. Both signed and unsigned types can be used, e.g 69223013Sdim/// @code 70223013Sdim/// PackedVector<signed, 2> vec; 71223013Sdim/// @endcode 72223013Sdim/// will create a vector accepting values -2, -1, 0, 1. Any other value will hit 73223013Sdim/// an assertion. 74243830Sdimtemplate <typename T, unsigned BitNum, typename BitVectorTy = BitVector> 75243830Sdimclass PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy, 76223013Sdim std::numeric_limits<T>::is_signed> { 77243830Sdim BitVectorTy Bits; 78243830Sdim typedef PackedVectorBase<T, BitNum, BitVectorTy, 79243830Sdim std::numeric_limits<T>::is_signed> base; 80223013Sdim 81223013Sdimpublic: 82223013Sdim class reference { 83223013Sdim PackedVector &Vec; 84223013Sdim const unsigned Idx; 85223013Sdim 86223013Sdim reference(); // Undefined 87223013Sdim public: 88223013Sdim reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { } 89223013Sdim 90223013Sdim reference &operator=(T val) { 91223013Sdim Vec.setValue(Vec.Bits, Idx, val); 92223013Sdim return *this; 93223013Sdim } 94224145Sdim operator T() const { 95223013Sdim return Vec.getValue(Vec.Bits, Idx); 96223013Sdim } 97223013Sdim }; 98223013Sdim 99223013Sdim PackedVector() { } 100223013Sdim explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { } 101223013Sdim 102223013Sdim bool empty() const { return Bits.empty(); } 103223013Sdim 104223013Sdim unsigned size() const { return Bits.size() >> (BitNum-1); } 105223013Sdim 106223013Sdim void clear() { Bits.clear(); } 107223013Sdim 108223013Sdim void resize(unsigned N) { Bits.resize(N << (BitNum-1)); } 109223013Sdim 110223013Sdim void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); } 111223013Sdim 112223013Sdim PackedVector &reset() { 113223013Sdim Bits.reset(); 114223013Sdim return *this; 115223013Sdim } 116223013Sdim 117223013Sdim void push_back(T val) { 118223013Sdim resize(size()+1); 119223013Sdim (*this)[size()-1] = val; 120223013Sdim } 121223013Sdim 122223013Sdim reference operator[](unsigned Idx) { 123223013Sdim return reference(*this, Idx); 124223013Sdim } 125223013Sdim 126223013Sdim T operator[](unsigned Idx) const { 127223013Sdim return base::getValue(Bits, Idx); 128223013Sdim } 129223013Sdim 130223013Sdim bool operator==(const PackedVector &RHS) const { 131223013Sdim return Bits == RHS.Bits; 132223013Sdim } 133223013Sdim 134223013Sdim bool operator!=(const PackedVector &RHS) const { 135223013Sdim return Bits != RHS.Bits; 136223013Sdim } 137223013Sdim 138223013Sdim const PackedVector &operator=(const PackedVector &RHS) { 139223013Sdim Bits = RHS.Bits; 140223013Sdim return *this; 141223013Sdim } 142223013Sdim 143223013Sdim PackedVector &operator|=(const PackedVector &RHS) { 144223013Sdim Bits |= RHS.Bits; 145223013Sdim return *this; 146223013Sdim } 147223013Sdim 148223013Sdim void swap(PackedVector &RHS) { 149223013Sdim Bits.swap(RHS.Bits); 150223013Sdim } 151223013Sdim}; 152223013Sdim 153223013Sdim// Leave BitNum=0 undefined. 154223013Sdimtemplate <typename T> 155223013Sdimclass PackedVector<T, 0>; 156223013Sdim 157223013Sdim} // end llvm namespace 158223013Sdim 159223013Sdim#endif 160