revise SkTDynamicHash and add unit tests
BUG=
R=reed@google.com
Author: mtklein@google.com
Review URL: https://chromiumcodereview.appspot.com/22292004
git-svn-id: http://skia.googlecode.com/svn/trunk@10552 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gyp/tests.gyp b/gyp/tests.gyp
index b151031..0bb3550 100644
--- a/gyp/tests.gyp
+++ b/gyp/tests.gyp
@@ -48,6 +48,7 @@
'../tests/DrawBitmapRectTest.cpp',
'../tests/DrawPathTest.cpp',
'../tests/DrawTextTest.cpp',
+ '../tests/DynamicHashTest.cpp',
'../tests/EmptyPathTest.cpp',
'../tests/ErrorTest.cpp',
'../tests/FillPathTest.cpp',
diff --git a/src/core/SkScaledImageCache.cpp b/src/core/SkScaledImageCache.cpp
index 45c7344..75dac78 100644
--- a/src/core/SkScaledImageCache.cpp
+++ b/src/core/SkScaledImageCache.cpp
@@ -250,7 +250,7 @@
SkASSERT(1 == rec->fLockCount);
#ifdef USE_HASH
- fHash->add(key, rec);
+ fHash->add(rec);
#endif
// We may (now) be overbudget, so see if we need to purge something.
@@ -270,7 +270,7 @@
SkASSERT(1 == rec->fLockCount);
#ifdef USE_HASH
- fHash->add(key, rec);
+ fHash->add(rec);
#endif
// We may (now) be overbudget, so see if we need to purge something.
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index b3d4b26..21aca07 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -9,185 +9,162 @@
#define SkTDynamicHash_DEFINED
#include "SkTypes.h"
+#include "SkMath.h"
template <typename T,
- typename KEY,
- const KEY& (KEY_FROM_T)(const T&),
- uint32_t (HASH_FROM_KEY)(const KEY&),
- bool (EQ_T_KEY)(const T&, const KEY&)>
+ typename Key,
+ const Key& (GetKey)(const T&),
+ uint32_t (Hash)(const Key&),
+ bool (Equal)(const T&, const Key&)>
class SkTDynamicHash {
-private:
- T* fStorage[4]; // cheap storage for small arrays
- T** fArray;
- int fCapacity; // number of slots in fArray. Must be pow2
- int fCountUsed; // number of valid entries in fArray
- int fCountDeleted; // number of deletedValue() entries in fArray
-
- // Need an illegal ptr value different from NULL (which we use to
- // signal empty/unused.
- const T* deletedValue() const { return reinterpret_cast<const T*>(-1); }
-
- // fCapacity is a pow2, so that minus one is a clean mask to grab
- // the low bits of hash to use as an index.
- uint32_t hashMask() const { return fCapacity - 1; }
-
- int hashToIndex(uint32_t hash) const {
- // this 16bit fold may be overkill, if we trust that hash is good
- return ((hash >> 16) ^ hash) & this->hashMask();
- }
-
public:
- SkTDynamicHash() {
- sk_bzero(fStorage, sizeof(fStorage));
- fArray = fStorage;
- fCapacity = SK_ARRAY_COUNT(fStorage);
- fCountUsed = fCountDeleted = 0;
- }
+ SkTDynamicHash(int initialCapacity=64/sizeof(T*))
+ : fCount(0)
+ , fCapacity(SkNextPow2(initialCapacity > 0 ? initialCapacity : 1))
+ , fArray(AllocArray(fCapacity)) {}
+
~SkTDynamicHash() {
- if (fArray != fStorage) {
- sk_free(fArray);
- }
+ sk_free(fArray);
}
- T* find(const KEY& key) {
- const T* const deleted = this->deletedValue();
- const unsigned mask = this->hashMask();
- int index = this->hashToIndex(HASH_FROM_KEY(key));
- int delta = 1;
+ int count() const { return fCount; }
- do {
+ // Return the entry with this key if we have it, otherwise NULL.
+ T* find(const Key& key) const {
+ int index = this->firstIndex(key);
+ for (int round = 0; round < fCapacity; round++) {
T* candidate = fArray[index];
- if (NULL == candidate) {
+ if (candidate == Empty()) {
return NULL;
}
- if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+ if (candidate != Deleted() && Equal(*candidate, key)) {
return candidate;
}
- index = (index + delta) & mask;
- delta <<= 1;
- } while (delta <= fCapacity);
+ index = this->nextIndex(index, round);
+ }
+ SkASSERT(!"find: should be unreachable");
return NULL;
}
- bool add(const KEY& key, T* newElement, bool autoGrow = true) {
- const T* const deleted = this->deletedValue();
- for (;;) {
- const unsigned mask = this->hashMask();
- int index = this->hashToIndex(HASH_FROM_KEY(key));
- int delta = 1;
+ // Add an entry with this key.
+ void add(T* newEntry) {
+ this->maybeGrow();
- do {
- const T* candidate = fArray[index];
- if (NULL == candidate || deleted == candidate) {
- fArray[index] = newElement;
- fCountUsed += 1;
- if (deleted == candidate) {
- SkASSERT(fCountDeleted > 0);
- fCountDeleted -= 1;
- }
- return true;
- }
- index = (index + delta) & mask;
- delta <<= 1;
- } while (delta <= fCapacity);
- if (autoGrow) {
- this->grow();
- } else {
- return false;
+ const Key& key = GetKey(*newEntry);
+ int index = this->firstIndex(key);
+ for (int round = 0; round < fCapacity; round++) {
+ T* candidate = fArray[index];
+ if (candidate == Empty() || candidate == Deleted()) {
+ fArray[index] = newEntry;
+ fCount++;
+ return;
}
+ if (Equal(*candidate, key)) {
+ fArray[index] = newEntry;
+ return;
+ }
+ index = this->nextIndex(index, round);
}
- SkASSERT(!"never get here");
- return false;
+ SkASSERT(!"add: should be unreachable");
}
- void remove(const KEY& key) {
- const T* const deleted = this->deletedValue();
- const unsigned mask = this->hashMask();
- int index = this->hashToIndex(HASH_FROM_KEY(key));
- int delta = 1;
+ // Remove entry with this key, if we have it.
+ void remove(const Key& key) {
+ this->innerRemove(key);
+ this->maybeShrink();
+ }
- for (;;) {
+protected:
+ // These methods are used by tests only.
+
+ int capacity() const { return fCapacity; }
+
+ // How many collisions do we go through before finding where this entry should be inserted?
+ int countCollisions(const Key& key) const {
+ int index = this->firstIndex(key);
+ for (int round = 0; round < fCapacity; round++) {
const T* candidate = fArray[index];
- SkASSERT(candidate);
- if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
- fArray[index] = const_cast<T*>(deleted);
- fCountUsed -= 1;
- fCountDeleted += 1;
- break;
+ if (candidate == Empty() || candidate == Deleted() || Equal(*candidate, key)) {
+ return round;
}
- index = (index + delta) & mask;
- delta <<= 1;
- SkASSERT(delta <= fCapacity);
+ index = this->nextIndex(index, round);
}
- this->checkStrink();
+ SkASSERT(!"countCollisions: should be unreachable");
+ return -1;
}
private:
- int countCollisions(const KEY& key) const {
- const T* const deleted = this->deletedValue();
- const unsigned mask = this->hashMask();
- int index = this->hashToIndex(HASH_FROM_KEY(key));
- int delta = 1;
- int collisionCount = 0;
+ // We have two special values to indicate an empty or deleted entry.
+ static const T* Empty() { return reinterpret_cast<const T*>(0); } // i.e. NULL
+ static const T* Deleted() { return reinterpret_cast<const T*>(1); } // Also an invalid pointer.
- for (;;) {
- const T* candidate = fArray[index];
- SkASSERT(candidate);
- if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
- break;
- }
- index = (index + delta) & mask;
- delta <<= 1;
- collisionCount += 1;
- SkASSERT(delta <= fCapacity);
- }
- return collisionCount;
+ static T** AllocArray(int capacity) {
+ T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity);
+ sk_bzero(array, sizeof(T*) * capacity); // All cells == Empty().
+ return array;
}
- void grow() {
- const T* const deleted = this->deletedValue();
-#if 0
- SkDebugf("growing from %d: used=%d\n", fCapacity, fCountUsed);
- for (int i = 0; i < fCapacity; ++i) {
- T* elem = fArray[i];
- if (NULL == elem || deleted == elem) {
- continue;
+ void innerRemove(const Key& key) {
+ int index = this->firstIndex(key);
+ for (int round = 0; round < fCapacity; round++) {
+ const T* candidate = fArray[index];
+ if (candidate == Empty()) {
+ return;
}
- SkDebugf(" entry[%d] had %d collisions\n", i, countCollisions(KEY_FROM_T(*elem)));
+ if (candidate != Deleted() && Equal(*candidate, key)) {
+ fArray[index] = const_cast<T*>(Deleted());
+ fCount--;
+ return;
+ }
+ index = this->nextIndex(index, round);
}
-#endif
+ SkASSERT(!"innerRemove: should be unreachable");
+ }
+
+ void maybeGrow() {
+ if (fCount < fCapacity / 2) {
+ return;
+ }
+
+ SkDEBUGCODE(int oldCount = fCount;)
int oldCapacity = fCapacity;
T** oldArray = fArray;
- int newCapacity = oldCapacity << 1;
- T** newArray = (T**)sk_malloc_throw(sizeof(T*) * newCapacity);
- sk_bzero(newArray, sizeof(T*) * newCapacity);
+ fCount = 0;
+ fCapacity *= 2;
+ fArray = AllocArray(fCapacity);
- SkDEBUGCODE(int oldCountUsed = fCountUsed;)
- fArray = newArray;
- fCapacity = newCapacity;
- fCountUsed = 0;
- fCountDeleted = 0;
-
- for (int i = 0; i < oldCapacity; ++i) {
- T* elem = oldArray[i];
- if (NULL == elem || deleted == elem) {
- continue;
+ for (int i = 0; i < oldCapacity; i++) {
+ T* entry = oldArray[i];
+ if (entry != Empty() && entry != Deleted()) {
+ this->add(entry);
}
- SkDEBUGCODE(bool success =) this->add(KEY_FROM_T(*elem), elem, false);
- SkASSERT(success);
}
- SkASSERT(oldCountUsed == fCountUsed);
+ SkASSERT(oldCount == fCount);
- if (oldArray != fStorage) {
- sk_free(oldArray);
- }
+ sk_free(oldArray);
}
- void checkStrink() {
- // todo: based on density and deadspace (fCountDeleted), consider
- // shrinking fArray and repopulating it.
+ void maybeShrink() {
+ // TODO
}
+
+ // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
+ uint32_t hashMask() const { return fCapacity - 1; }
+
+ int firstIndex(const Key& key) const {
+ return Hash(key) & this->hashMask();
+ }
+
+ // Given index at round N, what is the index to check at N+1? round should start at 0.
+ int nextIndex(int index, int round) const {
+ // This will search a power-of-two array fully without repeating an index.
+ return (index + round + 1) & this->hashMask();
+ }
+
+ int fCount; // Number of non-empty, non-deleted entries in fArray.
+ int fCapacity; // Number of entries in fArray. Always a power of 2.
+ T** fArray;
};
#endif
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
new file mode 100644
index 0000000..e15aad5
--- /dev/null
+++ b/tests/DynamicHashTest.cpp
@@ -0,0 +1,151 @@
+#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);