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/// \file
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
21namespace llvm {
22
23template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
24class PackedVectorBase;
25
26// This won't be necessary if we can specialize members without specializing
27// the parent template.
28template <typename T, unsigned BitNum, typename BitVectorTy>
29class PackedVectorBase<T, BitNum, BitVectorTy, false> {
30protected:
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
45template <typename T, unsigned BitNum, typename BitVectorTy>
46class PackedVectorBase<T, BitNum, BitVectorTy, true> {
47protected:
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/// 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.
75template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
76class 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
82public:
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.
147template <typename T> class PackedVector<T, 0>;
148
149} // end namespace llvm
150
151#endif // LLVM_ADT_PACKEDVECTOR_H
152