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
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index 21aca07..a408701 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -15,13 +15,16 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
}
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 @@
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 @@
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 4a8c3a0..2425ea2 100644
--- a/tests/DynamicHashTest.cpp
+++ b/tests/DynamicHashTest.cpp
@@ -36,23 +36,23 @@
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 @@
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 947ece1..877591a 100644
--- a/tests/ImageCacheTest.cpp
+++ b/tests/ImageCacheTest.cpp
@@ -48,14 +48,14 @@
// 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);