From ceeac641b346ed462b802e2fee9091a6c0eb0dbb Mon Sep 17 00:00:00 2001 From: graehl 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 // std::max - where to get this? #include #include #include - +#include //sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1 -template + +template class SmallVector { - typedef unsigned short uint16_t; +// typedef unsigned short uint16_t; public: typedef SmallVector 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(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 SV_MAX); if (min_size < capacity_) return; uint16_t new_cap = std::max(static_cast(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;ioperator[](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 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 #include "fdict.h" +#include "small_vector.h" template inline T & extend_vector(std::vector &v,int i) { @@ -310,10 +311,20 @@ private: // doesn't support fast indexing directly template class SparseVectorList { - typedef std::vector ListType; - typedef typename ListType::value_type pair_type; - typedef typename ListType::const_iterator const_iterator; + typedef typename std::pair Pair; + typedef SmallVector List; + typedef typename List::const_iterator const_iterator; SparseVectorList() { } + template + SparseVectorList(I i,I const& end) { + const T z=T(0); + int c=0; + for (;i const& v) { const T z=T(0); for (unsigned i=0;i