[Assorted-commits] SF.net SVN: assorted:[1268] cpp-commons/trunk/src

[<yan...@us...>]

Revision: 1268
          http://assorted.svn.sourceforge.net/assorted/?rev=1268&view=rev
Author:   yangzhang
Date:     2009-03-07 21:30:30 +0000 (Sat, 07 Mar 2009)

Log Message:
-----------
- added some load tests for fast_map
- fixed an index-out-of-bounds bug, using incorrect index into old table when growing

Modified Paths:
--------------
    cpp-commons/trunk/src/commons/fast_map.h
    cpp-commons/trunk/src/test/fast_map.cc

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:18:08 UTC (rev 1267)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-07 21:30:30 UTC (rev 1268)
@@ -169,7 +169,7 @@
                  pos = (pos + ++probe) & mask) {
               assert(probe < newtab.size());
             }
-            newtab[pos] = table[pos];
+            newtab[pos] = table[i];
           }
         }
         swap(newtab, table);

Modified: cpp-commons/trunk/src/test/fast_map.cc
===================================================================
--- cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:18:08 UTC (rev 1267)
+++ cpp-commons/trunk/src/test/fast_map.cc	2009-03-07 21:30:30 UTC (rev 1268)
@@ -1,8 +1,13 @@
 #include <commons/fast_map.h>
+#include <commons/rand.h>
 #include <boost/foreach.hpp>
+#include <map>
 #include "test.h"
+using namespace std;
 
 static const char *unset_key_string = "Assertion `has_empty_key && has_deleted_key' failed.";
+typedef fast_map<int, int> map_t;
+typedef pair<int, int> pii;
 
 template<typename T>
 void const_uninit_tests(T &fm) {
@@ -36,7 +41,6 @@
   EXPECT_TRUE(fm.begin() == fm.find(0));
   EXPECT_TRUE(fm.end() == fm.find(1));
 
-  typedef pair<int, int> pii;
   size_t counter = 0;
   vector<int> xs(20);
   for (typeof(fm.begin()) it = fm.begin();
@@ -53,7 +57,6 @@
 }
 
 TEST(fast_map, basics) {
-  typedef fast_map<int, int> map_t;
   map_t fm;
 
   // Uninitialized tests.
@@ -81,3 +84,31 @@
     EXPECT_EQ(4*i, fm[2*i]);
   }
 }
+
+TEST(fast_map, randload) {
+  map_t fm;
+  map<int, int> m;
+  fm.set_empty_key(-1);
+  fm.set_deleted_key(-2);
+  for (int i = 0; i < 1<<22; ++i) {
+    int k = randint();
+    if (fm.find(k) == fm.end()) {
+      int v = randint();
+      fm[k] = v;
+      m[k] = v;
+    }
+  }
+  foreach (const pii &p, m) {
+    EXPECT_EQ(p.second, fm[p.first]);
+  }
+}
+
+TEST(fast_map, load) {
+  map_t m;
+  m.set_empty_key(-1);
+  m.set_deleted_key(-2);
+  for (int i = 0; i < 1<<22; ++i)
+    m[i] = i<<1;
+  for (int i = 0; i < 1<<22; ++i)
+    EXPECT_EQ(i<<1, m[i]);
+}


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.