1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/Hash_test.cpp Sun Sep 20 15:14:12 2009 -0700
1.3 @@ -0,0 +1,193 @@
1.4 +/*
1.5 + * Hash_test.cpp
1.6 + * Ottoman
1.7 + *
1.8 + * Created by Jens Alfke on 9/2/09.
1.9 + * Copyright 2009 Jens Alfke. All rights reserved.
1.10 + * BSD-Licensed: See the file "LICENSE.txt" for details.
1.11 + */
1.12 +
1.13 +#include <gtest/gtest.h>
1.14 +#include "TestUtils.h"
1.15 +#include "File.h"
1.16 +#include "Hash.h"
1.17 +#include <stdio.h>
1.18 +
1.19 +using namespace Mooseyard;
1.20 +
1.21 +
1.22 +static bool verbose = false;
1.23 +static int num = 100;
1.24 +
1.25 +
1.26 +#pragma mark -
1.27 +#pragma mark UTILITIES:
1.28 +
1.29 +
1.30 +char* mkKey (int i) {
1.31 + static char* sKeys[100];
1.32 + if (i>=0 && i<100 && sKeys[i] != NULL)
1.33 + return sKeys[i];
1.34 + char str[10];
1.35 + sprintf(str, "%i",i);
1.36 + char *key = strdup(str);
1.37 + if (i>=0 && i<100)
1.38 + sKeys[i] = key;
1.39 + return key;
1.40 +}
1.41 +
1.42 +static char* Insert(Hash &hash, const char* key) {
1.43 + char string[100];
1.44 + sprintf(string, "value for %s", key);
1.45 + if (verbose)
1.46 + fprintf(stderr, "\nInserting %s -> '%s'\n", key,string);
1.47 + int count = hash.count();
1.48 + char *leaf = strdup(string);
1.49 +
1.50 + hash.put(key,leaf);
1.51 +
1.52 + if (verbose)
1.53 + hash.dump();
1.54 + EXPECT_EQ( count+1, hash.count() );
1.55 + EXPECT_EQ( leaf, hash.get(key) );
1.56 + return leaf;
1.57 +}
1.58 +
1.59 +static char* Insert(Hash &hash, int i) {
1.60 + return Insert(hash, mkKey(i));
1.61 +}
1.62 +
1.63 +static void Remove(Hash &hash, int i) {
1.64 + char* key = mkKey(i);
1.65 + char string[100];
1.66 + sprintf(string, "value for %s", key);
1.67 + if (verbose)
1.68 + fprintf(stderr, "\nRemoving %s\n", key);
1.69 + int count = hash.count();
1.70 + char *value = (char*) hash.get(key);
1.71 + EXPECT_TRUE(value!=NULL);
1.72 + EXPECT_EQ(0, strcmp(value,string));
1.73 +
1.74 + EXPECT_TRUE(hash.remove(key));
1.75 +
1.76 + if (verbose)
1.77 + hash.dump();
1.78 + EXPECT_EQ( count-1, hash.count() );
1.79 + EXPECT_EQ( NULL, hash.get(key) );
1.80 +}
1.81 +
1.82 +
1.83 +
1.84 +#pragma mark -
1.85 +#pragma mark TESTS:
1.86 +
1.87 +
1.88 +TEST(Hash,Simple) {
1.89 + Hash hash;
1.90 + hash.dump();
1.91 + EXPECT_EQ(0, hash.count());
1.92 +
1.93 + char *seventeen = Insert(hash, "seventeen");
1.94 +
1.95 + EXPECT_EQ(NULL, hash.get("zero"));
1.96 + EXPECT_EQ(NULL, hash.get("eighteen"));
1.97 +
1.98 + char *four = Insert(hash, "four");
1.99 + EXPECT_EQ(seventeen, hash.get("seventeen"));
1.100 +
1.101 + char *zero = Insert(hash, "zero");
1.102 + char *hundred = Insert(hash, "one hundred");
1.103 + char *eight = Insert(hash, "eight");
1.104 + char *twenty = Insert(hash, "twenty");
1.105 +
1.106 + EXPECT_EQ(zero, hash.get("zero"));
1.107 + EXPECT_EQ(four, hash.get("four"));
1.108 + EXPECT_EQ(eight, hash.get("eight"));
1.109 + EXPECT_EQ(seventeen, hash.get("seventeen"));
1.110 + EXPECT_EQ(twenty, hash.get("twenty"));
1.111 + EXPECT_EQ(hundred, hash.get("one hundred"));
1.112 +
1.113 + int i=0;
1.114 + for (Hash::Iterator iter(&hash); iter; ++iter, ++i) {
1.115 + Blob key = iter.key();
1.116 + if (verbose)
1.117 + fprintf(stderr, " %*s -> %s\n",
1.118 + (int)key.length,(const char*)key.bytes,
1.119 + ((char*)iter.value()));
1.120 + }
1.121 + EXPECT_EQ(6, i);
1.122 +}
1.123 +
1.124 +TEST(Hash,InsertLotsAtRandom) {
1.125 + int map[num];
1.126 + for (int i=0; i<num; i++)
1.127 + map[i] = i;
1.128 + shuffle(map,num);
1.129 + if (verbose) {
1.130 + for (int i=0; i<num; i++)
1.131 + fprintf(stderr, "%3d ",map[i]);
1.132 + fprintf(stderr, "\n");
1.133 + }
1.134 +
1.135 + Hash hash(8);
1.136 + char* expected[num];
1.137 + memset(&expected,0,sizeof(expected));
1.138 + for (int i=0; i<num; i++) {
1.139 + expected[map[i]] = Insert(hash, map[i]);
1.140 + for (int j=0; j<num; j++)
1.141 + EXPECT_EQ(expected[map[j]], hash.get(mkKey(map[j])));
1.142 + }
1.143 +}
1.144 +
1.145 +TEST(Hash,DeleteAtRandom) {
1.146 + Hash hash;
1.147 + for (int i=0; i<num; i++)
1.148 + Insert(hash,i);
1.149 +
1.150 + int map[num];
1.151 + for (int i=0; i<num; i++)
1.152 + map[i] = i;
1.153 + shuffle(map,num);
1.154 + if (verbose) {
1.155 + for (int i=0; i<num; i++)
1.156 + fprintf(stderr, "%3d ",map[i]);
1.157 + fprintf(stderr, "\n");
1.158 + }
1.159 +
1.160 + for (int i=0; i<num; i++)
1.161 + Remove(hash,map[i]);
1.162 +}
1.163 +
1.164 +TEST(Hash,Words) {
1.165 + const int kIterations = 3;
1.166 + readWords();
1.167 + double totalAdd = 0.0, totalGet = 0.0, totalRemove = 0.0;
1.168 + for (int iter=0; iter<kIterations; iter++) {
1.169 + printf("Adding words to Hash...\n");
1.170 + Hash hash;
1.171 + {
1.172 + Timer t("adding");
1.173 + for( int i=0; i<sNWords; i++)
1.174 + hash.put(sWords[i], sWords[i]);
1.175 + EXPECT_EQ(sNWords, hash.count());
1.176 + totalAdd += t.elapsed();
1.177 + }
1.178 + {
1.179 + Timer t("getting");
1.180 + for( int i=0; i<sNWords; i++)
1.181 + EXPECT_EQ( sWords[i] , hash.get(sWords[i]) );
1.182 + totalGet += t.elapsed();
1.183 + }
1.184 + {
1.185 + Timer t("removing");
1.186 + for( int i=0; i<sNWords; i++)
1.187 + EXPECT_TRUE( hash.remove(sWords[i]) );
1.188 + totalRemove += t.elapsed();
1.189 + }
1.190 + }
1.191 + printf("Average put = %.0lfns\n", totalAdd/kIterations/sNWords*1e9);
1.192 + printf("Average get = %.0lfns\n", totalGet/kIterations/sNWords*1e9);
1.193 + printf("Average remove= %.0lfns\n", totalRemove/kIterations/sNWords*1e9);
1.194 +}
1.195 +
1.196 +