diff -r 000000000000 -r 31a43d94cc26 test/Hash_test.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/Hash_test.cpp	Sun Sep 20 15:14:12 2009 -0700
@@ -0,0 +1,193 @@
+/*
+ *  Hash_test.cpp
+ *  Ottoman
+ *
+ *  Created by Jens Alfke on 9/2/09.
+ *  Copyright 2009 Jens Alfke. All rights reserved.
+ *  BSD-Licensed: See the file "LICENSE.txt" for details.
+ */
+
+#include <gtest/gtest.h>
+#include "TestUtils.h"
+#include "File.h"
+#include "Hash.h"
+#include <stdio.h>
+
+using namespace Mooseyard;
+
+
+static bool verbose = false;
+static int num = 100;
+
+
+#pragma mark -
+#pragma mark UTILITIES:
+
+
+char* mkKey (int i) {
+    static char* sKeys[100];
+    if (i>=0 && i<100 && sKeys[i] != NULL)
+        return sKeys[i];
+    char str[10];
+    sprintf(str, "%i",i);
+    char *key = strdup(str);
+    if (i>=0 && i<100)
+        sKeys[i] = key;
+    return key;
+}
+
+static char* Insert(Hash &hash, const char* key) {
+    char string[100];
+    sprintf(string, "value for %s", key);
+    if (verbose)
+        fprintf(stderr, "\nInserting %s -> '%s'\n", key,string);
+    int count = hash.count();
+    char *leaf = strdup(string);
+    
+    hash.put(key,leaf);
+    
+    if (verbose)
+        hash.dump();
+    EXPECT_EQ( count+1, hash.count() );
+    EXPECT_EQ( leaf, hash.get(key) );
+    return leaf;
+}
+
+static char* Insert(Hash &hash, int i) {
+    return Insert(hash, mkKey(i));
+}
+
+static void Remove(Hash &hash, int i) {
+    char* key = mkKey(i);
+    char string[100];
+    sprintf(string, "value for %s", key);
+    if (verbose)
+        fprintf(stderr, "\nRemoving %s\n", key);
+    int count = hash.count();
+    char *value = (char*) hash.get(key);
+    EXPECT_TRUE(value!=NULL);
+    EXPECT_EQ(0, strcmp(value,string));
+
+    EXPECT_TRUE(hash.remove(key));
+    
+    if (verbose)
+        hash.dump();
+    EXPECT_EQ( count-1, hash.count() );
+    EXPECT_EQ( NULL, hash.get(key) );
+}
+
+
+
+#pragma mark -
+#pragma mark TESTS:
+
+
+TEST(Hash,Simple) {
+    Hash hash;
+    hash.dump();
+    EXPECT_EQ(0, hash.count());
+    
+    char *seventeen = Insert(hash, "seventeen");
+    
+    EXPECT_EQ(NULL, hash.get("zero"));
+    EXPECT_EQ(NULL, hash.get("eighteen"));
+    
+    char *four = Insert(hash, "four");
+    EXPECT_EQ(seventeen, hash.get("seventeen"));
+    
+    char *zero = Insert(hash, "zero");
+    char *hundred = Insert(hash, "one hundred");
+    char *eight = Insert(hash, "eight");
+    char *twenty = Insert(hash, "twenty");
+    
+    EXPECT_EQ(zero, hash.get("zero"));
+    EXPECT_EQ(four, hash.get("four"));
+    EXPECT_EQ(eight, hash.get("eight"));
+    EXPECT_EQ(seventeen, hash.get("seventeen"));
+    EXPECT_EQ(twenty, hash.get("twenty"));
+    EXPECT_EQ(hundred, hash.get("one hundred"));
+    
+    int i=0;
+    for (Hash::Iterator iter(&hash); iter; ++iter, ++i) {
+        Blob key = iter.key();
+        if (verbose)
+            fprintf(stderr, "   %*s -> %s\n", 
+                    (int)key.length,(const char*)key.bytes,
+                    ((char*)iter.value()));
+    }
+    EXPECT_EQ(6, i);
+}
+
+TEST(Hash,InsertLotsAtRandom) {
+    int map[num];
+    for (int i=0; i<num; i++)
+        map[i] = i;
+    shuffle(map,num);
+    if (verbose) {
+        for (int i=0; i<num; i++)
+            fprintf(stderr, "%3d ",map[i]);
+        fprintf(stderr, "\n");
+    }
+    
+    Hash hash(8);
+    char* expected[num];
+    memset(&expected,0,sizeof(expected));
+    for (int i=0; i<num; i++) {
+        expected[map[i]] = Insert(hash, map[i]);
+        for (int j=0; j<num; j++)
+            EXPECT_EQ(expected[map[j]], hash.get(mkKey(map[j])));
+    }
+}
+
+TEST(Hash,DeleteAtRandom) {
+    Hash hash;
+    for (int i=0; i<num; i++)
+        Insert(hash,i);
+
+    int map[num];
+    for (int i=0; i<num; i++)
+        map[i] = i;
+    shuffle(map,num);
+    if (verbose) {
+        for (int i=0; i<num; i++)
+            fprintf(stderr, "%3d ",map[i]);
+        fprintf(stderr, "\n");
+    }
+    
+    for (int i=0; i<num; i++)
+        Remove(hash,map[i]);
+}
+
+TEST(Hash,Words) {
+    const int kIterations = 3;
+    readWords();
+    double totalAdd = 0.0, totalGet = 0.0, totalRemove = 0.0;
+    for (int iter=0; iter<kIterations; iter++) {
+        printf("Adding words to Hash...\n");
+        Hash hash;
+        {
+            Timer t("adding");
+            for( int i=0; i<sNWords; i++)
+                hash.put(sWords[i], sWords[i]);
+            EXPECT_EQ(sNWords, hash.count());
+            totalAdd += t.elapsed();
+        }        
+        {
+            Timer t("getting");
+            for( int i=0; i<sNWords; i++)
+                EXPECT_EQ( sWords[i] ,  hash.get(sWords[i]) );
+            totalGet += t.elapsed();
+        }        
+        {
+            Timer t("removing");
+            for( int i=0; i<sNWords; i++)
+                EXPECT_TRUE( hash.remove(sWords[i]) );
+            totalRemove += t.elapsed();
+        }        
+    }
+    printf("Average put   = %.0lfns\n", totalAdd/kIterations/sNWords*1e9);
+    printf("Average get   = %.0lfns\n", totalGet/kIterations/sNWords*1e9);
+    printf("Average remove= %.0lfns\n", totalRemove/kIterations/sNWords*1e9);
+}
+
+