From ceeac641b346ed462b802e2fee9091a6c0eb0dbb Mon Sep 17 00:00:00 2001
From: graehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>
Date: Fri, 16 Jul 2010 22:48:09 +0000
Subject: small/sparse vector fixes
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@304 ec762483-ff6d-05da-a07a-a48fb63a330f
---
decoder/small_vector.h | 124 +++++++++++++++++++++++++++++++++++++-----------
decoder/sparse_vector.h | 21 ++++++--
2 files changed, 111 insertions(+), 34 deletions(-)
diff --git a/decoder/small_vector.h b/decoder/small_vector.h
index e5c314de..ed3e1096 100644
--- a/decoder/small_vector.h
+++ b/decoder/small_vector.h
@@ -1,26 +1,55 @@
#ifndef _SMALL_VECTOR_H_
+#define _SMALL_VECTOR_H_
+
+/* REQUIRES that T is POD (can be memcpy). won't work (yet) due to union with SMALL_VECTOR_POD==0 - may be possible to handle movable types that have ctor/dtor, by using explicit allocation, ctor/dtor calls. but for now JUST USE THIS FOR no-meaningful ctor/dtor POD types.
+
+ stores small element (<=SV_MAX items) vectors inline. recommend SV_MAX=sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1. may not work if SV_MAX==0.
+ */
+
+#define SMALL_VECTOR_POD 1
#include <streambuf> // std::max - where to get this?
#include <cstring>
#include <cassert>
#include <limits.h>
-
+#include <new>
//sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1
-template <class T,int SV_MAX=2 >
+
+template <class T,int SV_MAX=2>
class SmallVector {
- typedef unsigned short uint16_t;
+// typedef unsigned short uint16_t;
public:
typedef SmallVector<T,SV_MAX> Self;
SmallVector() : size_(0) {}
- explicit SmallVector(size_t s, int v = 0) : size_(s) {
- assert(s < 0x80);
+ typedef T const* const_iterator;
+ typedef T* iterator;
+ T *begin() { return size_>SV_MAX?data_.ptr:data_.vals; }
+ T const* begin() const { return const_cast<Self*>(this)->begin(); }
+ T *end() { return begin()+size_; }
+ T const* end() const { return begin()+size_; }
+
+
+ explicit SmallVector(size_t s) : size_(s) {
+ assert(s < 0xA000);
+ if (s <= SV_MAX) {
+ for (int i = 0; i < s; ++i) new(&data_.vals[i]) T();
+ } else {
+ capacity_ = s;
+ size_ = s;
+ data_.ptr = new T[s]; // TODO: replace this with allocator or ::operator new(sizeof(T)*s) everywhere
+ for (int i = 0; i < size_; ++i) new(&data_.ptr[i]) T();
+ }
+ }
+
+ SmallVector(size_t s, T const& v) : size_(s) {
+ assert(s < 0xA000);
if (s <= SV_MAX) {
for (int i = 0; i < s; ++i) data_.vals[i] = v;
} else {
capacity_ = s;
size_ = s;
- data_.ptr = new int[s];
+ data_.ptr = new T[s];
for (int i = 0; i < size_; ++i) data_.ptr[i] = v;
}
}
@@ -30,8 +59,8 @@ class SmallVector {
for (int i = 0; i < SV_MAX; ++i) data_.vals[i] = o.data_.vals[i];
} else {
capacity_ = size_ = o.size_;
- data_.ptr = new int[capacity_];
- std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(int));
+ data_.ptr = new T[capacity_];
+ std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T));
}
}
@@ -42,8 +71,8 @@ class SmallVector {
for (int i = 0; i < SV_MAX; ++i) data_.vals[i] = o.data_.vals[i];
} else {
capacity_ = size_ = o.size_;
- data_.ptr = new int[capacity_];
- std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(int));
+ data_.ptr = new T[capacity_];
+ std::memcpy(data_.ptr, o.data_.ptr, size_ * sizeof(T));
}
} else {
if (o.size_ <= SV_MAX) {
@@ -54,7 +83,7 @@ class SmallVector {
if (capacity_ < o.size_) {
delete[] data_.ptr;
capacity_ = o.size_;
- data_.ptr = new int[capacity_];
+ data_.ptr = new T[capacity_];
}
size_ = o.size_;
for (int i = 0; i < size_; ++i)
@@ -65,8 +94,13 @@ class SmallVector {
}
~SmallVector() {
- if (size_ <= SV_MAX) return;
- delete[] data_.ptr;
+ if (size_ <= SV_MAX) {
+ // skip if pod? yes, we required pod anyway. no need to destruct
+#if !SMALL_VECTOR_POD
+ for (int i=0;i<size_;++i) data_.vals[i].~T();
+#endif
+ } else
+ delete[] data_.ptr;
}
void clear() {
@@ -83,21 +117,31 @@ class SmallVector {
assert(min_size > SV_MAX);
if (min_size < capacity_) return;
uint16_t new_cap = std::max(static_cast<uint16_t>(capacity_ << 1), min_size);
- int* tmp = new int[new_cap];
- std::memcpy(tmp, data_.ptr, capacity_ * sizeof(int));
+ T* tmp = new T[new_cap];
+ std::memcpy(tmp, data_.ptr, capacity_ * sizeof(T));
delete[] data_.ptr;
data_.ptr = tmp;
capacity_ = new_cap;
}
+private:
inline void copy_vals_to_ptr() {
capacity_ = SV_MAX * 2;
- int* tmp = new int[capacity_];
+ T* tmp = new T[capacity_];
for (int i = 0; i < SV_MAX; ++i) tmp[i] = data_.vals[i];
data_.ptr = tmp;
}
+ inline void ptr_to_small() {
+ assert(size_<=SV_MAX);
+ int *tmp=data_.ptr;
+ for (int i=0;i<size_;++i)
+ data_.vals[i]=tmp[i];
+ delete[] tmp;
+ }
+
+public:
- inline void push_back(int v) {
+ inline void push_back(T const& v) {
if (size_ < SV_MAX) {
data_.vals[size_] = v;
++size_;
@@ -111,18 +155,40 @@ class SmallVector {
++size_;
}
- int& back() { return this->operator[](size_ - 1); }
- const int& back() const { return this->operator[](size_ - 1); }
- int& front() { return this->operator[](0); }
- const int& front() const { return this->operator[](0); }
+ T& back() { return this->operator[](size_ - 1); }
+ const T& back() const { return this->operator[](size_ - 1); }
+ T& front() { return this->operator[](0); }
+ const T& front() const { return this->operator[](0); }
+
+ void pop_back() {
+ assert(size_>0);
+ --size_;
+ if (size_==SV_MAX)
+ ptr_to_small();
+ }
+
+
+ void compact() {
+ compact(size_);
+ }
+
+ // size must be <= size_ - TODO: test
+ void compact(uint16_t size) {
+ assert(size<=size_);
+ if (size_>SV_MAX) {
+ size_=size;
+ if (size<=SV_MAX)
+ ptr_to_small();
+ } else
+ size_=size;
+ }
void resize(size_t s, int v = 0) {
if (s <= SV_MAX) {
if (size_ > SV_MAX) {
- int tmp[SV_MAX];
- for (int i = 0; i < s; ++i) tmp[i] = data_.ptr[i];
- delete[] data_.ptr;
+ T *tmp=data_.ptr;
for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i];
+ delete[] tmp;
size_ = s;
return;
}
@@ -148,12 +214,12 @@ class SmallVector {
}
}
- int& operator[](size_t i) {
+ T& operator[](size_t i) {
if (size_ <= SV_MAX) return data_.vals[i];
return data_.ptr[i];
}
- const int& operator[](size_t i) const {
+ const T& operator[](size_t i) const {
if (size_ <= SV_MAX) return data_.vals[i];
return data_.ptr[i];
}
@@ -177,12 +243,12 @@ class SmallVector {
private:
union StorageType {
- int vals[SV_MAX];
- int* ptr;
+ T vals[SV_MAX];
+ T* ptr;
};
StorageType data_;
uint16_t size_;
- uint16_t capacity_; // only defined when size_ >= __SV_MAX_STATIC
+ uint16_t capacity_; // only defined when size_ > __SV_MAX_STATIC
};
typedef SmallVector<int,2> SmallVectorInt;
diff --git a/decoder/sparse_vector.h b/decoder/sparse_vector.h
index 43880014..f41bedf5 100644
--- a/decoder/sparse_vector.h
+++ b/decoder/sparse_vector.h
@@ -11,6 +11,7 @@
#include <valarray>
#include "fdict.h"
+#include "small_vector.h"
template <class T>
inline T & extend_vector(std::vector<T> &v,int i) {
@@ -310,10 +311,20 @@ private:
// doesn't support fast indexing directly
template <class T>
class SparseVectorList {
- typedef std::vector<const int,T> ListType;
- typedef typename ListType::value_type pair_type;
- typedef typename ListType::const_iterator const_iterator;
+ typedef typename std::pair<int,T> Pair;
+ typedef SmallVector<Pair,1> List;
+ typedef typename List::const_iterator const_iterator;
SparseVectorList() { }
+ template <class I>
+ SparseVectorList(I i,I const& end) {
+ const T z=T(0);
+ int c=0;
+ for (;i<end;++i,++c) {
+ if (*i!=z)
+ p.push_back(pair_type(c,*i));
+ }
+ p.compact();
+ }
explicit SparseVectorList(std::vector<T> const& v) {
const T z=T(0);
for (unsigned i=0;i<v.size();++i) {
@@ -321,10 +332,10 @@ class SparseVectorList {
if (t!=z)
p.push_back(pair_type(i,t));
}
- p.resize(p.size());
+ p.compact();
}
private:
- ListType p;
+ List p;
};
--
cgit v1.2.3