smallvector template

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@302 ec762483-ff6d-05da-a07a-a48fb63a330f

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;
 }