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 <limits>
19
20namespace llvm {
21
22template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
23class PackedVectorBase;
24
25// This won't be necessary if we can specialize members without specializing
26// the parent template.
27template <typename T, unsigned BitNum, typename BitVectorTy>
28class PackedVectorBase<T, BitNum, BitVectorTy, false> {
29protected:
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
44template <typename T, unsigned BitNum, typename BitVectorTy>
45class PackedVectorBase<T, BitNum, BitVectorTy, true> {
46protected:
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/// \brief 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.
74template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
75class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
76                                            std::numeric_limits<T>::is_signed> {
77  BitVectorTy Bits;
78  typedef PackedVectorBase<T, BitNum, BitVectorTy,
79                           std::numeric_limits<T>::is_signed> base;
80
81public:
82  class reference {
83    PackedVector &Vec;
84    const unsigned Idx;
85
86    reference(); // Undefined
87  public:
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    operator T() const {
95      return Vec.getValue(Vec.Bits, Idx);
96    }
97  };
98
99  PackedVector() = default;
100  explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
101
102  bool empty() const { return Bits.empty(); }
103
104  unsigned size() const { return Bits.size() >> (BitNum - 1); }
105
106  void clear() { Bits.clear(); }
107
108  void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
109
110  void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
111
112  PackedVector &reset() {
113    Bits.reset();
114    return *this;
115  }
116
117  void push_back(T val) {
118    resize(size()+1);
119    (*this)[size()-1] = val;
120  }
121
122  reference operator[](unsigned Idx) {
123    return reference(*this, Idx);
124  }
125
126  T operator[](unsigned Idx) const {
127    return base::getValue(Bits, Idx);
128  }
129
130  bool operator==(const PackedVector &RHS) const {
131    return Bits == RHS.Bits;
132  }
133
134  bool operator!=(const PackedVector &RHS) const {
135    return Bits != RHS.Bits;
136  }
137
138  PackedVector &operator|=(const PackedVector &RHS) {
139    Bits |= RHS.Bits;
140    return *this;
141  }
142};
143
144// Leave BitNum=0 undefined.
145template <typename T> class PackedVector<T, 0>;
146
147} // end llvm namespace
148
149#endif
150