add scaledimagecache
BUG=
Review URL: https://codereview.chromium.org/20005003
git-svn-id: http://skia.googlecode.com/svn/trunk@10286 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkScaledImageCache.cpp b/src/core/SkScaledImageCache.cpp
new file mode 100644
index 0000000..993b81b
--- /dev/null
+++ b/src/core/SkScaledImageCache.cpp
@@ -0,0 +1,421 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkScaledImageCache.h"
+#include "SkPixelRef.h"
+#include "SkRect.h"
+
+#ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
+ #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;
+
+ for (int i = 0; i < count; ++i) {
+ uint32_t k = data[i];
+ k *= 0xcc9e2d51;
+ k = (k << 15) | (k >> 17);
+ k *= 0x1b873593;
+
+ hash ^= k;
+ hash = (hash << 13) | (hash >> 19);
+ hash *= 5;
+ hash += 0xe6546b64;
+ }
+
+ // hash ^= size;
+ hash ^= hash >> 16;
+ hash *= 0x85ebca6b;
+ hash ^= hash >> 13;
+ hash *= 0xc2b2ae35;
+ hash ^= hash >> 16;
+
+ 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) {
+ SkPixelRef* pr = bm.pixelRef();
+ if (!pr) {
+ return false;
+ }
+
+ size_t offset = bm.pixelRefOffset();
+ size_t rowBytes = bm.rowBytes();
+ int x = (offset % rowBytes) >> 2;
+ int y = offset / rowBytes;
+
+ fGenID = pr->getGenerationID();
+ fBounds.set(x, y, x + bm.width(), y + bm.height());
+ fScaleX = scaleX;
+ fScaleY = scaleY;
+
+ fHash = compute_hash(&fGenID, 7);
+ return true;
+ }
+
+ bool operator<(const Key& other) {
+ const uint32_t* a = &fGenID;
+ const uint32_t* b = &other.fGenID;
+ for (int i = 0; i < 7; ++i) {
+ if (a[i] < b[i]) {
+ return true;
+ }
+ if (a[i] > b[i]) {
+ return false;
+ }
+ }
+ return false;
+ }
+
+ bool operator==(const Key& other) {
+ const uint32_t* a = &fHash;
+ const uint32_t* b = &other.fHash;
+ for (int i = 0; i < 8; ++i) {
+ if (a[i] != b[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ uint32_t fHash;
+ uint32_t fGenID;
+ float fScaleX;
+ float fScaleY;
+ SkIRect fBounds;
+};
+
+struct SkScaledImageCache::Rec {
+ Rec(const Key& key, const SkBitmap& bm) : fKey(key), fBitmap(bm) {
+ fLockCount = 1;
+ }
+
+ size_t bytesUsed() const {
+ return fBitmap.getSize();
+ }
+
+ Rec* fNext;
+ Rec* fPrev;
+
+ // this guy wants to be 64bit aligned
+ Key fKey;
+
+ int32_t fLockCount;
+ SkBitmap fBitmap;
+};
+
+SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
+ fHead = NULL;
+ fTail = NULL;
+ fBytesUsed = 0;
+ fByteLimit = byteLimit;
+ fCount = 0;
+}
+
+SkScaledImageCache::~SkScaledImageCache() {
+ Rec* rec = fHead;
+ while (rec) {
+ Rec* next = rec->fNext;
+ SkDELETE(rec);
+ rec = next;
+ }
+}
+
+SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
+ SkScalar scaleX,
+ SkScalar scaleY,
+ SkBitmap* scaled) {
+ Key key;
+ if (!key.init(orig, scaleX, scaleY)) {
+ return NULL;
+ }
+
+ Rec* rec = fHead;
+ while (rec != NULL) {
+ if (rec->fKey == key) {
+ this->moveToHead(rec); // for our LRU
+ rec->fLockCount += 1;
+ *scaled = rec->fBitmap;
+// SkDebugf("Found: [%d %d] %d\n", rec->fBitmap.width(), rec->fBitmap.height(), rec->fLockCount);
+ return (ID*)rec;
+ }
+ rec = rec->fNext;
+ }
+ return NULL;
+}
+
+SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig,
+ SkScalar scaleX,
+ SkScalar scaleY,
+ const SkBitmap& scaled) {
+ Key key;
+ if (!key.init(orig, scaleX, scaleY)) {
+ return NULL;
+ }
+
+ Rec* rec = SkNEW_ARGS(Rec, (key, scaled));
+ this->addToHead(rec);
+ SkASSERT(1 == rec->fLockCount);
+
+// SkDebugf("Added: [%d %d]\n", rec->fBitmap.width(), rec->fBitmap.height());
+
+ // We may (now) be overbudget, so see if we need to purge something.
+ this->purgeAsNeeded();
+ return (ID*)rec;
+}
+
+void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
+ SkASSERT(id);
+
+#ifdef SK_DEBUG
+ {
+ bool found = false;
+ Rec* rec = fHead;
+ while (rec != NULL) {
+ if ((ID*)rec == id) {
+ found = true;
+ break;
+ }
+ rec = rec->fNext;
+ }
+ SkASSERT(found);
+ }
+#endif
+ Rec* rec = (Rec*)id;
+ SkASSERT(rec->fLockCount > 0);
+ rec->fLockCount -= 1;
+
+// SkDebugf("Unlock: [%d %d] %d\n", rec->fBitmap.width(), rec->fBitmap.height(), rec->fLockCount);
+
+ // we may have been over-budget, but now have released something, so check
+ // if we should purge.
+ if (0 == rec->fLockCount) {
+ this->purgeAsNeeded();
+ }
+}
+
+void SkScaledImageCache::purgeAsNeeded() {
+ size_t byteLimit = fByteLimit;
+ size_t bytesUsed = fBytesUsed;
+
+ Rec* rec = fTail;
+ while (rec) {
+ if (bytesUsed < byteLimit) {
+ break;
+ }
+ Rec* prev = rec->fPrev;
+ if (0 == rec->fLockCount) {
+// SkDebugf("Purge: [%d %d] %d\n", rec->fBitmap.width(), rec->fBitmap.height(), fCount);
+ size_t used = rec->bytesUsed();
+ SkASSERT(used <= bytesUsed);
+ bytesUsed -= used;
+ this->detach(rec);
+ SkDELETE(rec);
+ fCount -= 1;
+ }
+ rec = prev;
+ }
+ fBytesUsed = bytesUsed;
+}
+
+size_t SkScaledImageCache::setByteLimit(size_t newLimit) {
+ size_t prevLimit = fByteLimit;
+ fByteLimit = newLimit;
+ if (newLimit < prevLimit) {
+ this->purgeAsNeeded();
+ }
+ return prevLimit;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkScaledImageCache::detach(Rec* rec) {
+ Rec* prev = rec->fPrev;
+ Rec* next = rec->fNext;
+
+ if (!prev) {
+ SkASSERT(fHead == rec);
+ fHead = next;
+ } else {
+ prev->fNext = next;
+ }
+
+ if (!next) {
+ fTail = prev;
+ } else {
+ next->fPrev = prev;
+ }
+
+ rec->fNext = rec->fPrev = NULL;
+}
+
+void SkScaledImageCache::moveToHead(Rec* rec) {
+ if (fHead == rec) {
+ return;
+ }
+
+ SkASSERT(fHead);
+ SkASSERT(fTail);
+
+ this->validate();
+
+ this->detach(rec);
+
+ fHead->fPrev = rec;
+ rec->fNext = fHead;
+ fHead = rec;
+
+ this->validate();
+}
+
+void SkScaledImageCache::addToHead(Rec* rec) {
+ this->validate();
+
+ rec->fPrev = NULL;
+ rec->fNext = fHead;
+ if (fHead) {
+ fHead->fPrev = rec;
+ }
+ fHead = rec;
+ if (!fTail) {
+ fTail = rec;
+ }
+ fBytesUsed += rec->bytesUsed();
+ fCount += 1;
+
+ this->validate();
+}
+
+#ifdef SK_DEBUG
+void SkScaledImageCache::validate() const {
+ if (NULL == fHead) {
+ SkASSERT(NULL == fTail);
+ SkASSERT(0 == fBytesUsed);
+ return;
+ }
+
+ if (fHead == fTail) {
+ SkASSERT(NULL == fHead->fPrev);
+ SkASSERT(NULL == fHead->fNext);
+ SkASSERT(fHead->bytesUsed() == fBytesUsed);
+ return;
+ }
+
+ SkASSERT(NULL == fHead->fPrev);
+ SkASSERT(NULL != fHead->fNext);
+ SkASSERT(NULL == fTail->fNext);
+ SkASSERT(NULL != fTail->fPrev);
+
+ size_t used = 0;
+ int count = 0;
+ const Rec* rec = fHead;
+ while (rec) {
+ count += 1;
+ used += rec->bytesUsed();
+ SkASSERT(used <= fBytesUsed);
+ rec = rec->fNext;
+ }
+ SkASSERT(fCount == count);
+
+ rec = fTail;
+ while (rec) {
+ SkASSERT(count > 0);
+ count -= 1;
+ SkASSERT(used >= rec->bytesUsed());
+ used -= rec->bytesUsed();
+ rec = rec->fPrev;
+ }
+
+ SkASSERT(0 == count);
+ SkASSERT(0 == used);
+}
+#endif
+
+///////////////////////////////////////////////////////////////////////////////
+
+#include "SkThread.h"
+
+static SkMutex gMutex;
+
+static SkScaledImageCache* get_cache() {
+ static SkScaledImageCache* gCache;
+ if (!gCache) {
+ gCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT));
+ }
+ return gCache;
+}
+
+SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(const SkBitmap& orig,
+ SkScalar scaleX,
+ SkScalar scaleY,
+ SkBitmap* scaled) {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->findAndLock(orig, scaleX, scaleY, scaled);
+}
+
+SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(const SkBitmap& orig,
+ SkScalar scaleX,
+ SkScalar scaleY,
+ const SkBitmap& scaled) {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->addAndLock(orig, scaleX, scaleY, scaled);
+}
+
+void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->unlock(id);
+}
+
+size_t SkScaledImageCache::GetBytesUsed() {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->getBytesUsed();
+}
+
+size_t SkScaledImageCache::GetByteLimit() {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->getByteLimit();
+}
+
+size_t SkScaledImageCache::SetByteLimit(size_t newLimit) {
+ SkAutoMutexAcquire am(gMutex);
+ return get_cache()->setByteLimit(newLimit);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#include "SkGraphics.h"
+
+size_t SkGraphics::GetImageCacheBytesUsed() {
+ return SkScaledImageCache::GetBytesUsed();
+}
+
+size_t SkGraphics::GetImageCacheByteLimit() {
+ return SkScaledImageCache::GetByteLimit();
+}
+
+size_t SkGraphics::SetImageCacheByteLimit(size_t newLimit) {
+ return SkScaledImageCache::SetByteLimit(newLimit);
+}
+