src/third_party/skia/tests/DynamicHashTest.cpp

   1 /*
   2  * Copyright 2013 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include "SkTDynamicHash.h"
   9 #include "Test.h"
  10
  11 namespace {
  12
  13 struct Entry {
  14     int key;
  15     double value;
  16
  17     static const int& GetKey(const Entry& entry) { return entry.key; }
  18     static uint32_t Hash(const int& key) { return key; }
  19 };
  20
  21
  22 class Hash : public SkTDynamicHash<Entry, int> {
  23 public:
  24     Hash() : INHERITED() {}
  25
  26     // Promote protected methods to public for this test.
  27     int capacity() const { return this->INHERITED::capacity(); }
  28     int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
  29
  30 private:
  31     typedef SkTDynamicHash<Entry, int> INHERITED;
  32 };
  33
  34 }  // namespace
  35
  36 #define ASSERT(x) REPORTER_ASSERT(reporter, x)
  37
  38 DEF_TEST(DynamicHash_growth, reporter) {
  39     Entry a = { 1, 2.0 };
  40     Entry b = { 2, 3.0 };
  41     Entry c = { 3, 4.0 };
  42     Entry d = { 4, 5.0 };
  43     Entry e = { 5, 6.0 };
  44
  45     Hash hash;
  46     ASSERT(hash.capacity() == 0);
  47
  48     hash.add(&a);
  49     ASSERT(hash.capacity() == 4);
  50
  51     hash.add(&b);
  52     ASSERT(hash.capacity() == 4);
  53
  54     hash.add(&c);
  55     ASSERT(hash.capacity() == 4);
  56
  57     hash.add(&d);
  58     ASSERT(hash.capacity() == 8);
  59
  60     hash.add(&e);
  61     ASSERT(hash.capacity() == 8);
  62
  63     ASSERT(hash.count() == 5);
  64 }
  65
  66 DEF_TEST(DynamicHash_add, reporter) {
  67     Hash hash;
  68     Entry a = { 1, 2.0 };
  69     Entry b = { 2, 3.0 };
  70
  71     ASSERT(hash.count() == 0);
  72     hash.add(&a);
  73     ASSERT(hash.count() == 1);
  74     hash.add(&b);
  75     ASSERT(hash.count() == 2);
  76 }
  77
  78 DEF_TEST(DynamicHash_lookup, reporter) {
  79     Hash hash;
  80
  81     // These collide.
  82     Entry a = { 1, 2.0 };
  83     Entry b = { 5, 3.0 };
  84
  85     // Before we insert anything, nothing can collide.
  86     ASSERT(hash.countCollisions(1) == 0);
  87     ASSERT(hash.countCollisions(5) == 0);
  88     ASSERT(hash.countCollisions(9) == 0);
  89
  90     // First is easy.
  91     hash.add(&a);
  92     ASSERT(hash.countCollisions(1) == 0);
  93     ASSERT(hash.countCollisions(5) == 1);
  94     ASSERT(hash.countCollisions(9) == 1);
  95
  96     // Second is one step away.
  97     hash.add(&b);
  98     ASSERT(hash.countCollisions(1) == 0);
  99     ASSERT(hash.countCollisions(5) == 1);
 100     ASSERT(hash.countCollisions(9) == 2);
 101
 102     // We can find our data right?
 103     ASSERT(hash.find(1) != NULL);
 104     ASSERT(hash.find(1)->value == 2.0);
 105     ASSERT(hash.find(5) != NULL);
 106     ASSERT(hash.find(5)->value == 3.0);
 107
 108     // These aren't in the hash.
 109     ASSERT(hash.find(2) == NULL);
 110     ASSERT(hash.find(9) == NULL);
 111 }
 112
 113 DEF_TEST(DynamicHash_remove, reporter) {
 114     Hash hash;
 115
 116     // These collide.
 117     Entry a = { 1, 2.0 };
 118     Entry b = { 5, 3.0 };
 119     Entry c = { 9, 4.0 };
 120
 121     hash.add(&a);
 122     hash.add(&b);
 123     hash.remove(1);
 124     // a should be marked deleted, and b should still be findable.
 125
 126     ASSERT(hash.find(1) == NULL);
 127     ASSERT(hash.find(5) != NULL);
 128     ASSERT(hash.find(5)->value == 3.0);
 129
 130     // This will go in the same slot as 'a' did before.
 131     ASSERT(hash.countCollisions(9) == 0);
 132     hash.add(&c);
 133     ASSERT(hash.find(9) != NULL);
 134     ASSERT(hash.find(9)->value == 4.0);
 135     ASSERT(hash.find(5) != NULL);
 136     ASSERT(hash.find(5)->value == 3.0);
 137 }
 138
 139 template<typename T> static void TestIter(skiatest::Reporter* reporter) {
 140     Hash hash;
 141
 142     int count = 0;
 143     // this should fall out of loop immediately
 144     for (T iter(&hash); !iter.done(); ++iter) {
 145         ++count;
 146     }
 147     ASSERT(0 == count);
 148
 149     // These collide.
 150     Entry a = { 1, 2.0 };
 151     Entry b = { 5, 3.0 };
 152     Entry c = { 9, 4.0 };
 153
 154     hash.add(&a);
 155     hash.add(&b);
 156     hash.add(&c);
 157
 158     // should see all 3 unique keys when iterating over hash
 159     count = 0;
 160     int keys[3] = {0, 0, 0};
 161     for (T iter(&hash); !iter.done(); ++iter) {
 162         int key = (*iter).key;
 163         keys[count] = key;
 164         ASSERT(hash.find(key) != NULL);
 165         ++count;
 166     }
 167     ASSERT(3 == count);
 168     ASSERT(keys[0] != keys[1]);
 169     ASSERT(keys[0] != keys[2]);
 170     ASSERT(keys[1] != keys[2]);
 171
 172     // should see 2 unique keys when iterating over hash that aren't 1
 173     hash.remove(1);
 174     count = 0;
 175     memset(keys, 0, sizeof(keys));
 176     for (T iter(&hash); !iter.done(); ++iter) {
 177         int key = (*iter).key;
 178         keys[count] = key;
 179         ASSERT(key != 1);
 180         ASSERT(hash.find(key) != NULL);
 181         ++count;
 182     }
 183     ASSERT(2 == count);
 184     ASSERT(keys[0] != keys[1]);
 185 }
 186
 187 DEF_TEST(DynamicHash_iterator, reporter) {
 188     TestIter<Hash::Iter>(reporter);
 189     TestIter<Hash::ConstIter>(reporter);
 190 }
 191
 192 static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) {
 193     Hash hash;
 194     Entry a = { 1, 2.0 };
 195     Entry b = { 2, 3.0 };
 196
 197     ASSERT(hash.capacity() == 0);
 198     hash.add(&a);
 199     hash.add(&b);
 200     ASSERT(hash.count() == 2);
 201     ASSERT(hash.capacity() == 4);
 202
 203     if (testReset) {
 204         hash.reset();
 205         ASSERT(hash.capacity() == 0);
 206     } else {
 207         hash.rewind();
 208         ASSERT(hash.capacity() == 4);
 209     }
 210     ASSERT(hash.count() == 0);
 211
 212     // make sure things still work
 213     hash.add(&a);
 214     hash.add(&b);
 215     ASSERT(hash.count() == 2);
 216     ASSERT(hash.capacity() == 4);
 217
 218     ASSERT(hash.find(1) != NULL);
 219     ASSERT(hash.find(2) != NULL);
 220 }
 221
 222 DEF_TEST(DynamicHash_reset, reporter) {
 223     TestResetOrRewind(reporter, true);
 224 }
 225
 226 DEF_TEST(DynamicHash_rewind, reporter) {
 227     TestResetOrRewind(reporter, false);
 228 }