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