experimental dynamic-hash (disabled)
git-svn-id: http://skia.googlecode.com/svn/trunk@10353 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkScaledImageCache.cpp b/src/core/SkScaledImageCache.cpp
index b8590f5..147697a 100644
--- a/src/core/SkScaledImageCache.cpp
+++ b/src/core/SkScaledImageCache.cpp
@@ -14,7 +14,7 @@
#define SK_DEFAULT_IMAGE_CACHE_LIMIT (2 * 1024 * 1024)
#endif
-#if 1
+
// Implemented from en.wikipedia.org/wiki/MurmurHash.
static uint32_t compute_hash(const uint32_t data[], int count) {
uint32_t hash = 0;
@@ -40,20 +40,6 @@
return hash;
}
-#else
-static uint32_t mix(uint32_t a, uint32_t b) {
- return ((a >> 1) | (a << 31)) ^ b;
-}
-
-static uint32_t compute_hash(const uint32_t data[], int count) {
- uint32_t hash = 0;
-
- for (int i = 0; i < count; ++i) {
- hash = mix(hash, data[i]);
- }
- return hash;
-}
-#endif
struct Key {
bool init(const SkBitmap& bm, SkScalar scaleX, SkScalar scaleY) {
@@ -76,7 +62,7 @@
return true;
}
- bool operator<(const Key& other) {
+ bool operator<(const Key& other) const {
const uint32_t* a = &fGenID;
const uint32_t* b = &other.fGenID;
for (int i = 0; i < 7; ++i) {
@@ -90,7 +76,7 @@
return false;
}
- bool operator==(const Key& other) {
+ bool operator==(const Key& other) const {
const uint32_t* a = &fHash;
const uint32_t* b = &other.fHash;
for (int i = 0; i < 8; ++i) {
@@ -141,9 +127,36 @@
const SkMipMap* fMip;
};
+#include "SkTDynamicHash.h"
+
+static const Key& key_from_rec(const SkScaledImageCache::Rec& rec) {
+ return rec.fKey;
+}
+
+static uint32_t hash_from_key(const Key& key) {
+ return key.fHash;
+}
+
+static bool eq_rec_key(const SkScaledImageCache::Rec& rec, const Key& key) {
+ return rec.fKey == key;
+}
+
+class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec,
+ Key, key_from_rec, hash_from_key,
+ eq_rec_key> {};
+
+///////////////////////////////////////////////////////////////////////////////
+
+//#define USE_HASH
+
SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
fHead = NULL;
fTail = NULL;
+#ifdef USE_HASH
+ fHash = new Hash;
+#else
+ fHash = NULL;
+#endif
fBytesUsed = 0;
fByteLimit = byteLimit;
fCount = 0;
@@ -156,6 +169,7 @@
SkDELETE(rec);
rec = next;
}
+ delete fHash;
}
SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig,
@@ -166,16 +180,23 @@
return NULL;
}
+#ifdef USE_HASH
+ Rec* rec = fHash->find(key);
+#else
Rec* rec = fHead;
while (rec != NULL) {
if (rec->fKey == key) {
- this->moveToHead(rec); // for our LRU
- rec->fLockCount += 1;
- return rec;
+ break;
}
rec = rec->fNext;
}
- return NULL;
+#endif
+
+ if (rec) {
+ this->moveToHead(rec); // for our LRU
+ rec->fLockCount += 1;
+ }
+ return rec;
}
SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
@@ -225,6 +246,10 @@
this->addToHead(rec);
SkASSERT(1 == rec->fLockCount);
+#ifdef USE_HASH
+ fHash->add(key, rec);
+#endif
+
// We may (now) be overbudget, so see if we need to purge something.
this->purgeAsNeeded();
return (ID*)rec;
@@ -241,6 +266,10 @@
this->addToHead(rec);
SkASSERT(1 == rec->fLockCount);
+#ifdef USE_HASH
+ fHash->add(key, rec);
+#endif
+
// We may (now) be overbudget, so see if we need to purge something.
this->purgeAsNeeded();
return (ID*)rec;
@@ -292,6 +321,10 @@
SkASSERT(used <= bytesUsed);
bytesUsed -= used;
this->detach(rec);
+#ifdef USE_HASH
+ fHash->remove(rec->fKey);
+#endif
+
SkDELETE(rec);
fCount -= 1;
}
diff --git a/src/core/SkScaledImageCache.h b/src/core/SkScaledImageCache.h
index 6ec6275..32474b7 100644
--- a/src/core/SkScaledImageCache.h
+++ b/src/core/SkScaledImageCache.h
@@ -88,11 +88,15 @@
*/
size_t setByteLimit(size_t newLimit);
-private:
+public:
struct Rec;
+private:
Rec* fHead;
Rec* fTail;
+ class Hash;
+ Hash* fHash;
+
size_t fBytesUsed;
size_t fByteLimit;
int fCount;
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
new file mode 100644
index 0000000..665028a
--- /dev/null
+++ b/src/core/SkTDynamicHash.h
@@ -0,0 +1,146 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTDynamicHash_DEFINED
+#define SkTDynamicHash_DEFINED
+
+#include "SkTypes.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&)>
+class SkTDynamicHash {
+private:
+ T* fStorage[1];
+ T** fArray;
+ int fCapacity;
+ int fCountUsed;
+ int fCountDeleted;
+
+ unsigned hashMask() const { return fCapacity - 1; }
+ const T* deletedValue() const { return reinterpret_cast<const T*>(-1); }
+
+public:
+ SkTDynamicHash() {
+ fArray = fStorage;
+ fCapacity = 1;
+ fCountUsed = fCountDeleted = 0;
+ }
+ ~SkTDynamicHash() {
+ if (fArray != fStorage) {
+ sk_free(fArray);
+ }
+ }
+
+ T* find(const KEY& key) {
+ const T* const deleted = this->deletedValue();
+ const unsigned mask = this->hashMask();
+ int index = HASH_FROM_KEY(key) & mask;
+ const int origIndex = index;
+ int delta = 1;
+
+ do {
+ T* candidate = fArray[index];
+ if (NULL == candidate) {
+ return NULL;
+ }
+ if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+ return candidate;
+ }
+ index = (index + delta) & mask;
+ delta <<= 1;
+ } while (index != origIndex);
+ 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 = HASH_FROM_KEY(key) & mask;
+ const int origIndex = index;
+ int delta = 1;
+
+ 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 (index != origIndex);
+ if (autoGrow) {
+ this->grow();
+ } else {
+ return false;
+ }
+ }
+ SkASSERT(!"never get here");
+ return false;
+ }
+
+ void remove(const KEY& key) {
+ const T* const deleted = this->deletedValue();
+ const unsigned mask = this->hashMask();
+ const uint32_t hash = HASH_FROM_KEY(key);
+ int index = hash & mask;
+ SkDEBUGCODE(const int origIndex = index;)
+ int delta = 1;
+
+ for (;;) {
+ const T* candidate = fArray[index];
+ SkASSERT(candidate);
+ if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+ fArray[index] = const_cast<T*>(deleted);
+ fCountDeleted += 1;
+ break;
+ }
+ index = (index + delta) & mask;
+ delta <<= 1;
+ SkASSERT(index != origIndex);
+ }
+ this->checkStrink();
+ }
+
+private:
+ void grow() {
+ const T* const deleted = this->deletedValue();
+
+ 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);
+
+ 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;
+ }
+ SkDEBUGCODE(bool success =) this->add(KEY_FROM_T(*elem), elem, false);
+ SkASSERT(success);
+ }
+ SkASSERT(oldCountUsed == fCountUsed);
+ sk_free(oldArray);
+ }
+
+ void checkStrink() {}
+};
+
+#endif