test/unit/test_hashtable.cpp

   1 #include <climits>
   2
   3 #include "../../src/hashtable.h"
   4 #include "gtest/gtest.h"
   5
   6 typedef uint64_t Value;
   7
   8 class HashTableTest : public testing::Test
   9 {
  10     protected:
  11         static const int HT_SIZE = 1024;
  12         HashTable<Value> ht;
  13
  14         HashTableTest() : ht(HT_SIZE) {}
  15
  16         Hash hash_from_index(int i) const {
  17             return static_cast<Hash>(i & (ht.size() - 1));
  18         }
  19 };
  20
  21 TEST_F(HashTableTest, Size)
  22 {
  23     HashTable<Value> ht2(HT_SIZE);
  24     EXPECT_EQ(sizeof(ht2), sizeof(ht));
  25
  26     int entry_size = sizeof(Hash) + sizeof(Value);
  27     EXPECT_EQ(16, entry_size);
  28
  29     int size = HT_SIZE / entry_size;
  30
  31     // 'size' must be a power of two for HashTable<T>::lookup()
  32     EXPECT_EQ(0, size & (size - 1));
  33
  34     EXPECT_EQ(size, ht.size());
  35 }
  36
  37 TEST_F(HashTableTest, Constructor)
  38 {
  39     ht.clear();
  40     const int n = ht.size();
  41     for (int i = 0; i < n; ++i) {
  42         EXPECT_EQ(0, ht.hash_at(i));
  43         EXPECT_EQ(0, ht.value_at(i));
  44     }
  45 }
  46
  47 TEST_F(HashTableTest, ConstructorWithoutClear)
  48 {
  49     const int n = ht.size();
  50     for (int i = 0; i < n; ++i) {
  51         EXPECT_EQ(0, ht.hash_at(i));
  52         EXPECT_EQ(0, ht.value_at(i));
  53     }
  54 }
  55
  56 TEST_F(HashTableTest, Clear)
  57 {
  58     const int n = ht.size();
  59     for (int i = 0; i < n; ++i) {
  60         Hash h = hash_from_index(i);
  61         ht.save(h, i);
  62
  63         EXPECT_EQ(h, ht.hash_at(i));
  64         EXPECT_EQ(i, ht.value_at(i));
  65     }
  66     ht.clear();
  67     for (int i = 0; i < n; ++i) {
  68         EXPECT_EQ(0, ht.hash_at(i));
  69         EXPECT_EQ(0, ht.value_at(i));
  70     }
  71 }
  72
  73 TEST_F(HashTableTest, Lookup)
  74 {
  75     const int n = ht.size();
  76     for (int i = 0; i < n; ++i) {
  77         Hash h = hash_from_index(i);
  78         bool is_empty;
  79         Value v = ht.lookup(h, &is_empty);
  80         EXPECT_EQ(0, v);
  81         if (i == 0) {
  82             // FIXME
  83             EXPECT_FALSE(is_empty);
  84         } else {
  85             EXPECT_TRUE(is_empty);
  86         }
  87     }
  88     for (int i = -1; i < n; ++i) {
  89         for (int s = SHRT_MIN; s <= SHRT_MAX; s += 1000) {
  90             if (++i >= n) break;
  91
  92             Value v = static_cast<Value>(s + i);
  93             Hash h = hash_from_index(i);
  94             ht.save(h, v);
  95
  96             // Check save
  97             EXPECT_EQ(h, ht.hash_at(i));
  98             EXPECT_EQ(v, ht.value_at(i));
  99             EXPECT_NE(0, ht.value_at(i));
 100         }
 101     }
 102     for (int i = -1; i < n; ++i) {
 103         for (int s = SHRT_MIN; s <= SHRT_MAX; s += 1000) {
 104             if (++i >= n) break;
 105
 106             Value v = static_cast<Value>(s + i);
 107             Hash h = hash_from_index(i);
 108             ht.save(h, v);
 109
 110             // Test lookup
 111             bool is_empty;
 112             Value v2 = ht.lookup(h, &is_empty);
 113             EXPECT_FALSE(is_empty);
 114             EXPECT_EQ(v, v2);
 115         }
 116     }
 117 }
 118
 119 TEST(MaterialTableTest, Size)
 120 {
 121     HashTable<Material> ht(MT_SIZE);
 122
 123     int entry_size = sizeof(Hash) + sizeof(Material);
 124     EXPECT_EQ(16, entry_size);
 125
 126     int size = MT_SIZE / entry_size;
 127
 128     // 'size' must be a power of two for HashTable<Material>::lookup()
 129     EXPECT_EQ(0, size & (size - 1));
 130
 131     EXPECT_EQ(size, ht.size());
 132 }