tests/DynamicHashTest.cpp

#include "Test.h"
#include "SkTDynamicHash.h"

namespace {

struct Entry {
    int key;
    float value;

    static const int& Key(const Entry& entry) { return entry.key; }
    static uint32_t Hash(const int& key) { return key; }
    static bool Equal(const Entry& entry, const int& key) { return entry.key == key; }
};

class Hash : public SkTDynamicHash<Entry, int, Entry::Key, Entry::Hash, Entry::Equal> {
public:
    Hash() : INHERITED() {}
    Hash(int capacity) : INHERITED(capacity) {}

    // Promote protected methods to public for this test.
    int capacity() const { return this->INHERITED::capacity(); }
    int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }

private:
    typedef SkTDynamicHash<Entry, int, Entry::Key, Entry::Hash, Entry::Equal> INHERITED;
};

}  // namespace

#define ASSERT(x) REPORTER_ASSERT(reporter, x)

static void test_growth(skiatest::Reporter* reporter) {
    Entry a = { 1, 2.0 };
    Entry b = { 2, 3.0 };
    Entry c = { 3, 4.0 };
    Entry d = { 4, 5.0 };
    Entry e = { 5, 6.0 };

    Hash hash(0);
    ASSERT(hash.capacity() == 1);

    hash.add(&a);
    ASSERT(hash.capacity() == 2);

    hash.add(&b);
    ASSERT(hash.capacity() == 4);

    hash.add(&c);
    ASSERT(hash.capacity() == 8);

    hash.add(&d);
    ASSERT(hash.capacity() == 8);

    hash.add(&e);
    ASSERT(hash.capacity() == 16);

    ASSERT(hash.count() == 5);
}

static void test_add(skiatest::Reporter* reporter) {
    Hash hash;
    Entry a = { 1, 2.0 };
    Entry b = { 2, 3.0 };
    Entry c = { 1, 1.0 };

    ASSERT(hash.count() == 0);
    hash.add(&a);
    ASSERT(hash.count() == 1);
    hash.add(&b);
    ASSERT(hash.count() == 2);
    hash.add(&c);  // Overwrites a.
    ASSERT(hash.count() == 2);

    // Make sure the hash didn't modify the entries we inserted when overwriting.
    ASSERT(a.value == 2.0);
    ASSERT(b.value == 3.0);
    ASSERT(c.value == 1.0);
}

static void test_lookup(skiatest::Reporter* reporter) {
    Hash hash(4);
    ASSERT(hash.capacity() == 4);

    // These collide.
    Entry a = { 1, 2.0 };
    Entry b = { 5, 3.0 };

    // Before we insert anything, nothing can collide.
    ASSERT(hash.countCollisions(1) == 0);
    ASSERT(hash.countCollisions(5) == 0);
    ASSERT(hash.countCollisions(9) == 0);

    // First is easy.
    hash.add(&a);
    ASSERT(hash.countCollisions(1) == 0);
    ASSERT(hash.countCollisions(5) == 1);
    ASSERT(hash.countCollisions(9) == 1);

    // Second is one step away.
    hash.add(&b);
    ASSERT(hash.countCollisions(1) == 0);
    ASSERT(hash.countCollisions(5) == 1);
    ASSERT(hash.countCollisions(9) == 2);

    // We can find our data right?
    ASSERT(hash.find(1) != NULL);
    ASSERT(hash.find(1)->value == 2.0);
    ASSERT(hash.find(5) != NULL);
    ASSERT(hash.find(5)->value == 3.0);

    // These aren't in the hash.
    ASSERT(hash.find(2) == NULL);
    ASSERT(hash.find(9) == NULL);
}

static void test_remove(skiatest::Reporter* reporter) {
    Hash hash(4);
    ASSERT(hash.capacity() == 4);

    // These collide.
    Entry a = { 1, 2.0 };
    Entry b = { 5, 3.0 };
    Entry c = { 9, 4.0 };

    hash.add(&a);
    hash.add(&b);
    hash.remove(1);
    // a should be marked deleted, and b should still be findable.

    ASSERT(hash.find(1) == NULL);
    ASSERT(hash.find(5) != NULL);
    ASSERT(hash.find(5)->value == 3.0);

    // This will go in the same slot as 'a' did before.
    ASSERT(hash.countCollisions(9) == 0);
    hash.add(&c);
    ASSERT(hash.find(9) != NULL);
    ASSERT(hash.find(9)->value == 4.0);
    ASSERT(hash.find(5) != NULL);
    ASSERT(hash.find(5)->value == 3.0);
}

static void test_dynamic_hash(skiatest::Reporter* reporter) {
    test_growth(reporter);
    test_add(reporter);
    test_lookup(reporter);
    test_remove(reporter);
}

#include "TestClassDef.h"
DEFINE_TESTCLASS("DynamicHash", DynamicHashTestClass, test_dynamic_hash);