From 74ee8ace0c6fd6715d16fd4f1a0e36a8a158868e Mon Sep 17 00:00:00 2001
From: Argyrios Kyrtzidis <akyrtzi@gmail.com>
Date: Tue, 31 May 2011 03:53:41 +0000
Subject: [PATCH] Introduce PackedVector, useful for storing a vector of values
 using a specific number of bits for each value. Both signed and unsigned
 types can be used, e.g

   PackedVector<signed, 2> vec;

will create a vector accepting values -2, -1, 0, 1. Any other value will hit an assertion.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132325 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/ADT/PackedVector.h | 158 ++++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
 create mode 100644 include/llvm/ADT/PackedVector.h

diff --git a/include/llvm/ADT/PackedVector.h b/include/llvm/ADT/PackedVector.h
new file mode 100644
index 00000000000..272322a2f4b
--- /dev/null
+++ b/include/llvm/ADT/PackedVector.h
@@ -0,0 +1,158 @@
+//===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the PackedVector class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_PACKEDVECTOR_H
+#define LLVM_ADT_PACKEDVECTOR_H
+
+#include "llvm/ADT/BitVector.h"
+#include <limits>
+
+namespace llvm {
+
+template <typename T, unsigned BitNum, bool isSigned>
+class PackedVectorBase;
+
+// This won't be necessary if we can specialize members without specializing
+// the parent template.
+template <typename T, unsigned BitNum>
+class PackedVectorBase<T, BitNum, false> {
+protected:
+  static T getValue(const llvm::BitVector &Bits, unsigned Idx) {
+    T val = T();
+    for (unsigned i = 0; i != BitNum; ++i)
+      val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
+    return val;
+  }
+
+  static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) {
+    assert((val >> BitNum) == 0 && "value is too big");
+    for (unsigned i = 0; i != BitNum; ++i)
+      Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
+  }
+};
+
+template <typename T, unsigned BitNum>
+class PackedVectorBase<T, BitNum, true> {
+protected:
+  static T getValue(const llvm::BitVector &Bits, unsigned Idx) {
+    T val = T();
+    for (unsigned i = 0; i != BitNum-1; ++i)
+      val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
+    if (Bits[(Idx << (BitNum-1)) + BitNum-1])
+      val = ~val;
+    return val;
+  }
+
+  static void setValue(llvm::BitVector &Bits, unsigned Idx, T val) {
+    if (val < 0) {
+      val = ~val;
+      Bits.set((Idx << (BitNum-1)) + BitNum-1);
+    }
+    assert((val >> (BitNum-1)) == 0 && "value is too big");
+    for (unsigned i = 0; i != BitNum-1; ++i)
+      Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
+  }
+};
+
+/// \brief Store a vector of values using a specific number of bits for each
+/// value. Both signed and unsigned types can be used, e.g
+/// @code
+///   PackedVector<signed, 2> vec;
+/// @endcode
+/// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
+/// an assertion.
+template <typename T, unsigned BitNum>
+class PackedVector : public PackedVectorBase<T, BitNum,
+                                            std::numeric_limits<T>::is_signed> {
+  llvm::BitVector Bits;
+  typedef PackedVectorBase<T, BitNum, std::numeric_limits<T>::is_signed> base;
+
+public:
+  class reference {
+    PackedVector &Vec;
+    const unsigned Idx;
+
+    reference();  // Undefined    
+  public:
+    reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) { }    
+
+    reference &operator=(T val) {
+      Vec.setValue(Vec.Bits, Idx, val);
+      return *this;
+    }
+    operator T() {
+      return Vec.getValue(Vec.Bits, Idx);
+    }
+  };
+
+  PackedVector() { }
+  explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) { }
+
+  bool empty() const { return Bits.empty(); }
+
+  unsigned size() const { return Bits.size() >> (BitNum-1); }
+  
+  void clear() { Bits.clear(); }
+  
+  void resize(unsigned N) { Bits.resize(N << (BitNum-1)); }
+
+  void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
+
+  PackedVector &reset() {
+    Bits.reset();
+    return *this;
+  }
+
+  void push_back(T val) {
+    resize(size()+1);
+    (*this)[size()-1] = val;
+  }
+
+  reference operator[](unsigned Idx) {
+    return reference(*this, Idx);
+  }
+
+  T operator[](unsigned Idx) const {
+    return base::getValue(Bits, Idx);
+  }
+
+  bool operator==(const PackedVector &RHS) const {
+    return Bits == RHS.Bits;
+  }
+
+  bool operator!=(const PackedVector &RHS) const {
+    return Bits != RHS.Bits;
+  }
+
+  const PackedVector &operator=(const PackedVector &RHS) {
+    Bits = RHS.Bits;
+    return *this;
+  }
+
+  PackedVector &operator|=(const PackedVector &RHS) {
+    Bits |= RHS.Bits;
+    return *this;
+  }
+
+  void swap(PackedVector &RHS) {
+    Bits.swap(RHS.Bits);
+  }
+};
+
+// Leave BitNum=0 undefined. 
+template <typename T>
+class PackedVector<T, 0>;
+
+} // end llvm namespace
+
+#endif
-- 
2.34.1