diff options
author | mtklein@google.com <mtklein@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-08-12 14:51:25 +0000 |
---|---|---|
committer | mtklein@google.com <mtklein@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-08-12 14:51:25 +0000 |
commit | c9ab2b7dd8411f8a78654b237c69a5886567dfec (patch) | |
tree | 3260584eecd429828cf923cec2e9393f0c9b7857 | |
parent | fb4a68de439b59fd71cea47ca1fd4e9f58844d2a (diff) |
SkTDynamicHash
- add validate()
- make add() and remove() strict
- fill in maybeShrink()
- make grow and shrink thresholds configurable.
- fix issue where we were getting filled with deleted items - we need to count them as occupied when determining if we should grow
BUG=
R=reed@google.com
Review URL: https://codereview.chromium.org/22571010
git-svn-id: http://skia.googlecode.com/svn/trunk@10677 2bbb7eff-a529-9590-31e7-b0007b416f81
-rw-r--r-- | src/core/SkTDynamicHash.h | 159 | ||||
-rw-r--r-- | tests/DynamicHashTest.cpp | 18 | ||||
-rw-r--r-- | tests/ImageCacheTest.cpp | 4 |
3 files changed, 122 insertions, 59 deletions
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h index 21aca07b90..a40870193e 100644 --- a/src/core/SkTDynamicHash.h +++ b/src/core/SkTDynamicHash.h @@ -15,13 +15,16 @@ template <typename T, typename Key, const Key& (GetKey)(const T&), uint32_t (Hash)(const Key&), - bool (Equal)(const T&, const Key&)> + bool (Equal)(const T&, const Key&), + int kGrowPercent = 75, // Larger -> more memory efficient, but slower. + int kShrinkPercent = 25> class SkTDynamicHash { + static const int kMinCapacity = 4; // Smallest capacity we allow. public: - SkTDynamicHash(int initialCapacity=64/sizeof(T*)) - : fCount(0) - , fCapacity(SkNextPow2(initialCapacity > 0 ? initialCapacity : 1)) - , fArray(AllocArray(fCapacity)) {} + SkTDynamicHash(int initialCapacity=64/sizeof(T*)) { + this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity)); + SkASSERT(this->validate()); + } ~SkTDynamicHash() { sk_free(fArray); @@ -34,10 +37,10 @@ public: int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { T* candidate = fArray[index]; - if (candidate == Empty()) { + if (Empty() == candidate) { return NULL; } - if (candidate != Deleted() && Equal(*candidate, key)) { + if (Deleted() != candidate && Equal(*candidate, key)) { return candidate; } index = this->nextIndex(index, round); @@ -46,32 +49,22 @@ public: return NULL; } - // Add an entry with this key. + // Add an entry with this key. We require that no entry with newEntry's key is already present. void add(T* newEntry) { + SkASSERT(NULL == this->find(GetKey(*newEntry))); this->maybeGrow(); - - 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(!"add: should be unreachable"); + SkASSERT(this->validate()); + this->innerAdd(newEntry); + SkASSERT(this->validate()); } - // Remove entry with this key, if we have it. + // Remove the entry with this key. We reqire that an entry with this key is present. void remove(const Key& key) { + SkASSERT(NULL != this->find(key)); this->innerRemove(key); + SkASSERT(this->validate()); this->maybeShrink(); + SkASSERT(this->validate()); } protected: @@ -84,7 +77,7 @@ protected: int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { const T* candidate = fArray[index]; - if (candidate == Empty() || candidate == Deleted() || Equal(*candidate, key)) { + if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) { return round; } index = this->nextIndex(index, round); @@ -95,8 +88,8 @@ protected: private: // 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. + static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL + static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer. static T** AllocArray(int capacity) { T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity); @@ -104,16 +97,91 @@ private: return array; } - void innerRemove(const Key& key) { + void reset(int capacity) { + fCount = 0; + fDeleted = 0; + fCapacity = capacity; + fArray = AllocArray(fCapacity); + } + + bool validate() const { + #define CHECK(x) SkASSERT((x)); if (!(x)) return false + + // Is capacity sane? + CHECK(SkIsPow2(fCapacity)); + CHECK(fCapacity >= kMinCapacity); + + // Is fCount correct? + int count = 0; + for (int i = 0; i < fCapacity; i++) { + if (Empty() != fArray[i] && Deleted() != fArray[i]) { + count++; + } + } + CHECK(count == fCount); + + // Is fDeleted correct? + int deleted = 0; + for (int i = 0; i < fCapacity; i++) { + if (Deleted() == fArray[i]) { + deleted++; + } + } + CHECK(deleted == fDeleted); + + // Are all entries findable? + for (int i = 0; i < fCapacity; i++) { + if (Empty() == fArray[i] || Deleted() == fArray[i]) { + continue; + } + CHECK(NULL != this->find(GetKey(*fArray[i]))); + } + + // Are all entries unique? + for (int i = 0; i < fCapacity; i++) { + if (Empty() == fArray[i] || Deleted() == fArray[i]) { + continue; + } + for (int j = i+1; j < fCapacity; j++) { + if (Empty() == fArray[j] || Deleted() == fArray[j]) { + continue; + } + CHECK(fArray[i] != fArray[j]); + CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); + CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); + } + } + #undef CHECK + return true; + } + + void innerAdd(T* newEntry) { + const Key& key = GetKey(*newEntry); int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { const T* candidate = fArray[index]; - if (candidate == Empty()) { + if (Empty() == candidate || Deleted() == candidate) { + if (Deleted() == candidate) { + fDeleted--; + } + fCount++; + fArray[index] = newEntry; return; } - if (candidate != Deleted() && Equal(*candidate, key)) { - fArray[index] = const_cast<T*>(Deleted()); + index = this->nextIndex(index, round); + } + SkASSERT(!"add: should be unreachable"); + } + + void innerRemove(const Key& key) { + const int firstIndex = this->firstIndex(key); + int index = firstIndex; + for (int round = 0; round < fCapacity; round++) { + const T* candidate = fArray[index]; + if (Deleted() != candidate && Equal(*candidate, key)) { + fDeleted++; fCount--; + fArray[index] = Deleted(); return; } index = this->nextIndex(index, round); @@ -122,21 +190,27 @@ private: } void maybeGrow() { - if (fCount < fCapacity / 2) { - return; + if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) { + resize(fCapacity * 2); + } + } + + void maybeShrink() { + if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) { + resize(fCapacity / 2); } + } + void resize(int newCapacity) { SkDEBUGCODE(int oldCount = fCount;) int oldCapacity = fCapacity; T** oldArray = fArray; - fCount = 0; - fCapacity *= 2; - fArray = AllocArray(fCapacity); + reset(newCapacity); for (int i = 0; i < oldCapacity; i++) { T* entry = oldArray[i]; - if (entry != Empty() && entry != Deleted()) { + if (Empty() != entry && Deleted() != entry) { this->add(entry); } } @@ -145,10 +219,6 @@ private: sk_free(oldArray); } - 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; } @@ -162,7 +232,8 @@ private: return (index + round + 1) & this->hashMask(); } - int fCount; // Number of non-empty, non-deleted entries in fArray. + int fCount; // Number of non Empty(), non Deleted() entries in fArray. + int fDeleted; // Number of Deleted() entries in fArray. int fCapacity; // Number of entries in fArray. Always a power of 2. T** fArray; }; diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp index 4a8c3a01a2..2425ea24ca 100644 --- a/tests/DynamicHashTest.cpp +++ b/tests/DynamicHashTest.cpp @@ -36,23 +36,23 @@ static void test_growth(skiatest::Reporter* reporter) { Entry d = { 4, 5.0 }; Entry e = { 5, 6.0 }; - Hash hash(0); - ASSERT(hash.capacity() == 1); + Hash hash(4); + ASSERT(hash.capacity() == 4); hash.add(&a); - ASSERT(hash.capacity() == 2); + ASSERT(hash.capacity() == 4); hash.add(&b); ASSERT(hash.capacity() == 4); hash.add(&c); - ASSERT(hash.capacity() == 8); + ASSERT(hash.capacity() == 4); hash.add(&d); ASSERT(hash.capacity() == 8); hash.add(&e); - ASSERT(hash.capacity() == 16); + ASSERT(hash.capacity() == 8); ASSERT(hash.count() == 5); } @@ -61,20 +61,12 @@ 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) { diff --git a/tests/ImageCacheTest.cpp b/tests/ImageCacheTest.cpp index 947ece1e21..877591acc7 100644 --- a/tests/ImageCacheTest.cpp +++ b/tests/ImageCacheTest.cpp @@ -48,14 +48,14 @@ static void TestImageCache(skiatest::Reporter* reporter) { // stress test, should trigger purges for (size_t i = 0; i < COUNT * 100; ++i) { + scale += 1; + SkBitmap tmp; make_bm(&tmp, DIM, DIM); id = cache.addAndLock(bm[0], scale, scale, tmp); REPORTER_ASSERT(reporter, NULL != id); cache.unlock(id); - - scale += 1; } cache.setByteLimit(0); |