summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorgraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-07-16 22:08:37 +0000
committergraehl <graehl@ec762483-ff6d-05da-a07a-a48fb63a330f>2010-07-16 22:08:37 +0000
commitd484433d9ad566076b7d078c77443ce7841f4f3e (patch)
tree6d6eb905ed25589821b7bec12a38b1fb211c37b1
parent0a11da06831d5a062b6703f1aa1431cc33689e23 (diff)
smallvector template
git-svn-id: https://ws10smt.googlecode.com/svn/trunk@302 ec762483-ff6d-05da-a07a-a48fb63a330f
-rw-r--r--decoder/apply_models.cc2
-rw-r--r--decoder/hg.h2
-rw-r--r--decoder/hg_io.cc8
-rw-r--r--decoder/kbest.h12
-rw-r--r--decoder/maxtrans_blunsom.cc4
-rw-r--r--decoder/small_vector.h65
-rw-r--r--decoder/small_vector_test.cc28
7 files changed, 62 insertions, 59 deletions
diff --git a/decoder/apply_models.cc b/decoder/apply_models.cc
index 240bd12b..ba573984 100644
--- a/decoder/apply_models.cc
+++ b/decoder/apply_models.cc
@@ -18,7 +18,7 @@ using namespace std;
using namespace std::tr1;
struct Candidate;
-typedef SmallVector JVector;
+typedef SmallVectorInt JVector;
typedef vector<Candidate*> CandidateHeap;
typedef vector<Candidate*> CandidateList;
diff --git a/decoder/hg.h b/decoder/hg.h
index a21a7acf..53b5a53d 100644
--- a/decoder/hg.h
+++ b/decoder/hg.h
@@ -22,7 +22,7 @@ class Hypergraph {
Hypergraph() : is_linear_chain_(false) {}
// SmallVector is a fast, small vector<int> implementation for sizes <= 2
- typedef SmallVector TailNodeVector;
+ typedef SmallVectorInt TailNodeVector;
// TODO get rid of cat_?
// TODO keep cat_ and add span and/or state? :)
diff --git a/decoder/hg_io.cc b/decoder/hg_io.cc
index 6a5561e6..d6e73b8a 100644
--- a/decoder/hg_io.cc
+++ b/decoder/hg_io.cc
@@ -27,7 +27,7 @@ struct HGReader : public JSONParser {
hg.ConnectEdgeToHeadNode(&hg.edges_[in_edges[i]], node);
}
}
- void CreateEdge(const TRulePtr& rule, SparseVector<double>* feats, const SmallVector& tail) {
+ void CreateEdge(const TRulePtr& rule, FeatureVector* feats, const SmallVectorInt& tail) {
Hypergraph::Edge* edge = hg.AddEdge(rule, tail);
feats->swap(edge->feature_values_);
edge->i_ = spans[0];
@@ -228,7 +228,7 @@ struct HGReader : public JSONParser {
}
string rp;
string cat;
- SmallVector tail;
+ SmallVectorInt tail;
vector<int> in_edges;
TRulePtr cur_rule;
map<int, TRulePtr> rules;
@@ -524,7 +524,7 @@ void ReadPLFNode(const std::string& in, int &c, int cur_node, int line, Hypergra
}
}
-} // namespace PLF
+} // namespace PLF
void HypergraphIO::ReadFromPLF(const std::string& in, Hypergraph* hg, int line) {
hg->clear();
@@ -644,7 +644,7 @@ void b64encode(const char* data, const size_t size, ostream* out) {
}
}
-static void decodeblock(const unsigned char* in, unsigned char* out) {
+static void decodeblock(const unsigned char* in, unsigned char* out) {
out[0] = (unsigned char ) (in[0] << 2 | in[1] >> 4);
out[1] = (unsigned char ) (in[1] << 4 | in[2] >> 2);
out[2] = (unsigned char ) (((in[2] << 6) & 0xc0) | in[3]);
diff --git a/decoder/kbest.h b/decoder/kbest.h
index fcd40fcd..35e79bcc 100644
--- a/decoder/kbest.h
+++ b/decoder/kbest.h
@@ -49,7 +49,7 @@ namespace KBest {
struct Derivation {
Derivation(const Hypergraph::Edge& e,
- const SmallVector& jv,
+ const SmallVectorInt& jv,
const WeightType& w,
const SparseVector<double>& f) :
edge(&e),
@@ -59,11 +59,11 @@ namespace KBest {
// dummy constructor, just for query
Derivation(const Hypergraph::Edge& e,
- const SmallVector& jv) : edge(&e), j(jv) {}
+ const SmallVectorInt& jv) : edge(&e), j(jv) {}
T yield;
const Hypergraph::Edge* const edge;
- const SmallVector j;
+ const SmallVectorInt j;
const WeightType score;
const SparseVector<double> feature_values;
};
@@ -141,7 +141,7 @@ namespace KBest {
// the yield is computed in LazyKthBest before the derivation is added to D
// returns NULL if j refers to derivation numbers larger than the
// antecedent structure define
- Derivation* CreateDerivation(const Hypergraph::Edge& e, const SmallVector& j) {
+ Derivation* CreateDerivation(const Hypergraph::Edge& e, const SmallVectorInt& j) {
WeightType score = w(e);
SparseVector<double> feats = e.feature_values_;
for (int i = 0; i < e.Arity(); ++i) {
@@ -161,7 +161,7 @@ namespace KBest {
const Hypergraph::Node& node = g.nodes_[v];
for (int i = 0; i < node.in_edges_.size(); ++i) {
const Hypergraph::Edge& edge = g.edges_[node.in_edges_[i]];
- SmallVector jv(edge.Arity(), 0);
+ SmallVectorInt jv(edge.Arity(), 0);
Derivation* d = CreateDerivation(edge, jv);
assert(d);
s.cand.push_back(d);
@@ -178,7 +178,7 @@ namespace KBest {
void LazyNext(const Derivation* d, CandidateHeap* cand, UniqueDerivationSet* ds) {
for (int i = 0; i < d->j.size(); ++i) {
- SmallVector j = d->j;
+ SmallVectorInt j = d->j;
++j[i];
const Derivation* ant = LazyKthBest(d->edge->tail_nodes_[i], j[i]);
if (ant) {
diff --git a/decoder/maxtrans_blunsom.cc b/decoder/maxtrans_blunsom.cc
index 34e175db..6efab454 100644
--- a/decoder/maxtrans_blunsom.cc
+++ b/decoder/maxtrans_blunsom.cc
@@ -19,7 +19,7 @@ using namespace std::tr1;
namespace Hack {
struct Candidate;
-typedef SmallVector JVector;
+typedef SmallVectorInt JVector;
typedef vector<Candidate*> CandidateHeap;
typedef vector<Candidate*> CandidateList;
@@ -188,7 +188,7 @@ public:
new_edge->edge_prob_ = item->out_edge_.edge_prob_;
Candidate*& o_item = (*s2n)[item->state_];
if (!o_item) o_item = item;
-
+
int& node_id = o_item->node_index_;
if (node_id < 0) {
Hypergraph::Node* new_node = out.AddNode(in.nodes_[item->in_edge_->head_node_].cat_);
diff --git a/decoder/small_vector.h b/decoder/small_vector.h
index 2c61ab3a..e5c314de 100644
--- a/decoder/small_vector.h
+++ b/decoder/small_vector.h
@@ -5,16 +5,17 @@
#include <cassert>
#include <limits.h>
-#define __SV_MAX_STATIC 2
-
+//sizeof(T)/sizeof(T*)>1?sizeof(T)/sizeof(T*):1
+template <class T,int SV_MAX=2 >
class SmallVector {
-
+ 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);
- if (s <= __SV_MAX_STATIC) {
+ if (s <= SV_MAX) {
for (int i = 0; i < s; ++i) data_.vals[i] = v;
} else {
capacity_ = s;
@@ -24,9 +25,9 @@ class SmallVector {
}
}
- SmallVector(const SmallVector& o) : size_(o.size_) {
- if (size_ <= __SV_MAX_STATIC) {
- for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i];
+ SmallVector(const Self& o) : size_(o.size_) {
+ if (size_ <= SV_MAX) {
+ 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_];
@@ -34,18 +35,18 @@ class SmallVector {
}
}
- const SmallVector& operator=(const SmallVector& o) {
- if (size_ <= __SV_MAX_STATIC) {
- if (o.size_ <= __SV_MAX_STATIC) {
+ const Self& operator=(const Self& o) {
+ if (size_ <= SV_MAX) {
+ if (o.size_ <= SV_MAX) {
size_ = o.size_;
- for (int i = 0; i < __SV_MAX_STATIC; ++i) data_.vals[i] = o.data_.vals[i];
+ 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));
}
} else {
- if (o.size_ <= __SV_MAX_STATIC) {
+ if (o.size_ <= SV_MAX) {
delete[] data_.ptr;
size_ = o.size_;
for (int i = 0; i < size_; ++i) data_.vals[i] = o.data_.vals[i];
@@ -64,12 +65,12 @@ class SmallVector {
}
~SmallVector() {
- if (size_ <= __SV_MAX_STATIC) return;
+ if (size_ <= SV_MAX) return;
delete[] data_.ptr;
}
void clear() {
- if (size_ > __SV_MAX_STATIC) {
+ if (size_ > SV_MAX) {
delete[] data_.ptr;
}
size_ = 0;
@@ -79,7 +80,7 @@ class SmallVector {
size_t size() const { return size_; }
inline void ensure_capacity(uint16_t min_size) {
- assert(min_size > __SV_MAX_STATIC);
+ 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];
@@ -90,18 +91,18 @@ class SmallVector {
}
inline void copy_vals_to_ptr() {
- capacity_ = __SV_MAX_STATIC * 2;
+ capacity_ = SV_MAX * 2;
int* tmp = new int[capacity_];
- for (int i = 0; i < __SV_MAX_STATIC; ++i) tmp[i] = data_.vals[i];
+ for (int i = 0; i < SV_MAX; ++i) tmp[i] = data_.vals[i];
data_.ptr = tmp;
}
inline void push_back(int v) {
- if (size_ < __SV_MAX_STATIC) {
+ if (size_ < SV_MAX) {
data_.vals[size_] = v;
++size_;
return;
- } else if (size_ == __SV_MAX_STATIC) {
+ } else if (size_ == SV_MAX) {
copy_vals_to_ptr();
} else if (size_ == capacity_) {
ensure_capacity(size_ + 1);
@@ -116,9 +117,9 @@ class SmallVector {
const int& front() const { return this->operator[](0); }
void resize(size_t s, int v = 0) {
- if (s <= __SV_MAX_STATIC) {
- if (size_ > __SV_MAX_STATIC) {
- int tmp[__SV_MAX_STATIC];
+ 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;
for (int i = 0; i < s; ++i) data_.vals[i] = tmp[i];
@@ -135,7 +136,7 @@ class SmallVector {
return;
}
} else {
- if (size_ <= __SV_MAX_STATIC)
+ if (size_ <= SV_MAX)
copy_vals_to_ptr();
if (s > capacity_)
ensure_capacity(s);
@@ -148,18 +149,18 @@ class SmallVector {
}
int& operator[](size_t i) {
- if (size_ <= __SV_MAX_STATIC) return data_.vals[i];
+ if (size_ <= SV_MAX) return data_.vals[i];
return data_.ptr[i];
}
const int& operator[](size_t i) const {
- if (size_ <= __SV_MAX_STATIC) return data_.vals[i];
+ if (size_ <= SV_MAX) return data_.vals[i];
return data_.ptr[i];
}
- bool operator==(const SmallVector& o) const {
+ bool operator==(const Self& o) const {
if (size_ != o.size_) return false;
- if (size_ <= __SV_MAX_STATIC) {
+ if (size_ <= SV_MAX) {
for (size_t i = 0; i < size_; ++i)
if (data_.vals[i] != o.data_.vals[i]) return false;
return true;
@@ -170,9 +171,13 @@ class SmallVector {
}
}
+ friend bool operator!=(const Self& a, const Self& b) {
+ return !(a==b);
+ }
+
private:
union StorageType {
- int vals[__SV_MAX_STATIC];
+ int vals[SV_MAX];
int* ptr;
};
StorageType data_;
@@ -180,8 +185,6 @@ class SmallVector {
uint16_t capacity_; // only defined when size_ >= __SV_MAX_STATIC
};
-inline bool operator!=(const SmallVector& a, const SmallVector& b) {
- return !(a==b);
-}
+typedef SmallVector<int,2> SmallVectorInt;
#endif
diff --git a/decoder/small_vector_test.cc b/decoder/small_vector_test.cc
index 84237791..d1d8dcab 100644
--- a/decoder/small_vector_test.cc
+++ b/decoder/small_vector_test.cc
@@ -12,10 +12,10 @@ class SVTest : public testing::Test {
virtual void SetUp() { }
virtual void TearDown() { }
};
-
+
TEST_F(SVTest, LargerThan2) {
- SmallVector v;
- SmallVector v2;
+ SmallVectorInt v;
+ SmallVectorInt v2;
v.push_back(0);
v.push_back(1);
v.push_back(2);
@@ -24,7 +24,7 @@ TEST_F(SVTest, LargerThan2) {
assert(v[1] == 1);
assert(v[0] == 0);
v2 = v;
- SmallVector copy(v);
+ SmallVectorInt copy(v);
assert(copy.size() == 3);
assert(copy[0] == 0);
assert(copy[1] == 1);
@@ -42,12 +42,12 @@ TEST_F(SVTest, LargerThan2) {
assert(v2[2] == 0);
assert(v2[1] == -1);
assert(v2[0] == -2);
- SmallVector v3(1,1);
+ SmallVectorInt v3(1,1);
assert(v3[0] == 1);
v2 = v3;
assert(v2.size() == 1);
assert(v2[0] == 1);
- SmallVector v4(10, 1);
+ SmallVectorInt v4(10, 1);
assert(v4.size() == 10);
assert(v4[5] == 1);
assert(v4[9] == 1);
@@ -56,7 +56,7 @@ TEST_F(SVTest, LargerThan2) {
assert(v4[2] == 2);
assert(v4[1] == 1);
assert(v4[0] == 0);
- SmallVector v5(10, 2);
+ SmallVectorInt v5(10, 2);
assert(v5.size() == 10);
assert(v5[7] == 2);
assert(v5[0] == 2);
@@ -65,7 +65,7 @@ TEST_F(SVTest, LargerThan2) {
assert(v.size() == 10);
assert(v[2] == 2);
assert(v[9] == 2);
- SmallVector cc;
+ SmallVectorInt cc;
for (int i = 0; i < 33; ++i)
cc.push_back(i);
for (int i = 0; i < 33; ++i)
@@ -88,10 +88,10 @@ TEST_F(SVTest, LargerThan2) {
}
TEST_F(SVTest, Small) {
- SmallVector v;
- SmallVector v1(1,0);
- SmallVector v2(2,10);
- SmallVector v1a(2,0);
+ SmallVectorInt v;
+ SmallVectorInt v1(1,0);
+ SmallVectorInt v2(2,10);
+ SmallVectorInt v1a(2,0);
EXPECT_TRUE(v1 != v1a);
EXPECT_TRUE(v1 == v1);
EXPECT_EQ(v1[0], 0);
@@ -101,7 +101,7 @@ TEST_F(SVTest, Small) {
--v2[0];
EXPECT_EQ(v2[0], 9);
EXPECT_EQ(v2[1], 11);
- SmallVector v3(v2);
+ SmallVectorInt v3(v2);
assert(v3[0] == 9);
assert(v3[1] == 11);
assert(!v3.empty());
@@ -118,7 +118,7 @@ TEST_F(SVTest, Small) {
assert(v3[1] == 11);
assert(!v3.empty());
assert(v3.size() == 2);
- cerr << sizeof(SmallVector) << endl;
+ cerr << sizeof(SmallVectorInt) << endl;
cerr << sizeof(vector<int>) << endl;
}