src/core/SkScaledImageCache.cpp - skia - Git at Google

 /*
  * 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 "SkMipMap.h"
 #include "SkPixelRef.h"
 #include "SkRect.h"

 // This can be defined by the caller's build system
 //#define SK_USE_DISCARDABLE_SCALEDIMAGECACHE

 #ifndef SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT
 #   define SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT   1024
 #endif

 #ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
     #define SK_DEFAULT_IMAGE_CACHE_LIMIT     (2 * 1024 * 1024)
 #endif

 static inline SkScaledImageCache::ID* rec_to_id(SkScaledImageCache::Rec* rec) {
     return reinterpret_cast<SkScaledImageCache::ID*>(rec);
 }

 static inline SkScaledImageCache::Rec* id_to_rec(SkScaledImageCache::ID* id) {
     return reinterpret_cast<SkScaledImageCache::Rec*>(id);
 }

  // 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;
 }

 struct SkScaledImageCache::Key {
     Key(uint32_t genID,
         SkScalar scaleX,
         SkScalar scaleY,
         SkIRect  bounds)
         : fGenID(genID)
         , fScaleX(scaleX)
         , fScaleY(scaleY)
         , fBounds(bounds) {
         fHash = compute_hash(&fGenID, 7);
     }

     bool operator<(const Key& other) const {
         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 {
         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;
         fMip = NULL;
     }

     Rec(const Key& key, const SkMipMap* mip) : fKey(key) {
         fLockCount = 1;
         fMip = mip;
         mip->ref();
     }

     ~Rec() {
         SkSafeUnref(fMip);
     }

     static const Key& GetKey(const Rec& rec) { return rec.fKey; }
     static uint32_t Hash(const Key& key) { return key.fHash; }

     size_t bytesUsed() const {
         return fMip ? fMip->getSize() : fBitmap.getSize();
     }

     Rec*    fNext;
     Rec*    fPrev;

     // this guy wants to be 64bit aligned
     Key     fKey;

     int32_t fLockCount;

     // we use either fBitmap or fMip, but not both
     SkBitmap fBitmap;
     const SkMipMap* fMip;
 };

 #include "SkTDynamicHash.h"

 class SkScaledImageCache::Hash :
     public SkTDynamicHash<SkScaledImageCache::Rec, SkScaledImageCache::Key> {};


 ///////////////////////////////////////////////////////////////////////////////

 // experimental hash to speed things up
 #define USE_HASH

 #if !defined(USE_HASH)
 static inline SkScaledImageCache::Rec* find_rec_in_list(
         SkScaledImageCache::Rec* head, const Key & key) {
     SkScaledImageCache::Rec* rec = head;
     while ((rec != NULL) && (rec->fKey != key)) {
         rec = rec->fNext;
     }
     return rec;
 }
 #endif

 void SkScaledImageCache::init() {
     fHead = NULL;
     fTail = NULL;
 #ifdef USE_HASH
     fHash = new Hash;
 #else
     fHash = NULL;
 #endif
     fBytesUsed = 0;
     fCount = 0;
     fAllocator = NULL;

     // One of these should be explicit set by the caller after we return.
     fByteLimit = 0;
     fDiscardableFactory = NULL;
 }

 #include "SkDiscardableMemory.h"

 class SkOneShotDiscardablePixelRef : public SkPixelRef {
 public:
     SK_DECLARE_INST_COUNT(SkOneShotDiscardablePixelRef)
     // Ownership of the discardablememory is transfered to the pixelref
     SkOneShotDiscardablePixelRef(const SkImageInfo&, SkDiscardableMemory*, size_t rowBytes);
     ~SkOneShotDiscardablePixelRef();

 #ifdef SK_SUPPORT_LEGACY_PIXELREF_UNFLATTENABLE
     SK_DECLARE_UNFLATTENABLE_OBJECT()
 #endif

 protected:
     virtual bool onNewLockPixels(LockRec*) SK_OVERRIDE;
     virtual void onUnlockPixels() SK_OVERRIDE;
     virtual size_t getAllocatedSizeInBytes() const SK_OVERRIDE;

 private:
     SkDiscardableMemory* fDM;
     size_t               fRB;
     bool                 fFirstTime;

     typedef SkPixelRef INHERITED;
 };

 SkOneShotDiscardablePixelRef::SkOneShotDiscardablePixelRef(const SkImageInfo& info,
                                              SkDiscardableMemory* dm,
                                              size_t rowBytes)
     : INHERITED(info)
     , fDM(dm)
     , fRB(rowBytes)
 {
     SkASSERT(dm->data());
     fFirstTime = true;
 }

 SkOneShotDiscardablePixelRef::~SkOneShotDiscardablePixelRef() {
     SkDELETE(fDM);
 }

 bool SkOneShotDiscardablePixelRef::onNewLockPixels(LockRec* rec) {
     if (fFirstTime) {
         // we're already locked
         SkASSERT(fDM->data());
         fFirstTime = false;
         goto SUCCESS;
     }

     // A previous call to onUnlock may have deleted our DM, so check for that
     if (NULL == fDM) {
         return false;
     }

     if (!fDM->lock()) {
         // since it failed, we delete it now, to free-up the resource
         delete fDM;
         fDM = NULL;
         return false;
     }

 SUCCESS:
     rec->fPixels = fDM->data();
     rec->fColorTable = NULL;
     rec->fRowBytes = fRB;
     return true;
 }

 void SkOneShotDiscardablePixelRef::onUnlockPixels() {
     SkASSERT(!fFirstTime);
     fDM->unlock();
 }

 size_t SkOneShotDiscardablePixelRef::getAllocatedSizeInBytes() const {
     return this->info().getSafeSize(fRB);
 }

 class SkScaledImageCacheDiscardableAllocator : public SkBitmap::Allocator {
 public:
     SkScaledImageCacheDiscardableAllocator(
                             SkScaledImageCache::DiscardableFactory factory) {
         SkASSERT(factory);
         fFactory = factory;
     }

     virtual bool allocPixelRef(SkBitmap*, SkColorTable*) SK_OVERRIDE;

 private:
     SkScaledImageCache::DiscardableFactory fFactory;
 };

 bool SkScaledImageCacheDiscardableAllocator::allocPixelRef(SkBitmap* bitmap,
                                                        SkColorTable* ctable) {
     size_t size = bitmap->getSize();
     uint64_t size64 = bitmap->computeSize64();
     if (0 == size || size64 > (uint64_t)size) {
         return false;
     }

     SkDiscardableMemory* dm = fFactory(size);
     if (NULL == dm) {
         return false;
     }

     // can we relax this?
     if (kN32_SkColorType != bitmap->colorType()) {
         return false;
     }

     SkImageInfo info = bitmap->info();
     bitmap->setPixelRef(SkNEW_ARGS(SkOneShotDiscardablePixelRef,
                                    (info, dm, bitmap->rowBytes())))->unref();
     bitmap->lockPixels();
     return bitmap->readyToDraw();
 }

 SkScaledImageCache::SkScaledImageCache(DiscardableFactory factory) {
     this->init();
     fDiscardableFactory = factory;

     fAllocator = SkNEW_ARGS(SkScaledImageCacheDiscardableAllocator, (factory));
 }

 SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
     this->init();
     fByteLimit = byteLimit;
 }

 SkScaledImageCache::~SkScaledImageCache() {
     SkSafeUnref(fAllocator);

     Rec* rec = fHead;
     while (rec) {
         Rec* next = rec->fNext;
         SkDELETE(rec);
         rec = next;
     }
     delete fHash;
 }

 ////////////////////////////////////////////////////////////////////////////////


 SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(uint32_t genID,
                                                         SkScalar scaleX,
                                                         SkScalar scaleY,
                                                         const SkIRect& bounds) {
     const Key key(genID, scaleX, scaleY, bounds);
     return this->findAndLock(key);
 }

 /**
    This private method is the fully general record finder. All other
    record finders should call this function or the one above. */
 SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkScaledImageCache::Key& key) {
     if (key.fBounds.isEmpty()) {
         return NULL;
     }
 #ifdef USE_HASH
     Rec* rec = fHash->find(key);
 #else
     Rec* rec = find_rec_in_list(fHead, key);
 #endif
     if (rec) {
         this->moveToHead(rec);  // for our LRU
         rec->fLockCount += 1;
     }
     return rec;
 }

 /**
    This function finds the bounds of the bitmap *within its pixelRef*.
    If the bitmap lacks a pixelRef, it will return an empty rect, since
    that doesn't make sense.  This may be a useful enough function that
    it should be somewhere else (in SkBitmap?). */
 static SkIRect get_bounds_from_bitmap(const SkBitmap& bm) {
     if (!(bm.pixelRef())) {
         return SkIRect::MakeEmpty();
     }
     SkIPoint origin = bm.pixelRefOrigin();
     return SkIRect::MakeXYWH(origin.fX, origin.fY, bm.width(), bm.height());
 }


 SkScaledImageCache::ID* SkScaledImageCache::findAndLock(uint32_t genID,
                                                         int32_t width,
                                                         int32_t height,
                                                         SkBitmap* bitmap) {
     Rec* rec = this->findAndLock(genID, SK_Scalar1, SK_Scalar1,
                                  SkIRect::MakeWH(width, height));
     if (rec) {
         SkASSERT(NULL == rec->fMip);
         SkASSERT(rec->fBitmap.pixelRef());
         *bitmap = rec->fBitmap;
     }
     return rec_to_id(rec);
 }

 SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
                                                         SkScalar scaleX,
                                                         SkScalar scaleY,
                                                         SkBitmap* scaled) {
     if (0 == scaleX || 0 == scaleY) {
         // degenerate, and the key we use for mipmaps
         return NULL;
     }
     Rec* rec = this->findAndLock(orig.getGenerationID(), scaleX,
                                  scaleY, get_bounds_from_bitmap(orig));
     if (rec) {
         SkASSERT(NULL == rec->fMip);
         SkASSERT(rec->fBitmap.pixelRef());
         *scaled = rec->fBitmap;
     }
     return rec_to_id(rec);
 }

 SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig,
                                                            SkMipMap const ** mip) {
     Rec* rec = this->findAndLock(orig.getGenerationID(), 0, 0,
                                  get_bounds_from_bitmap(orig));
     if (rec) {
         SkASSERT(rec->fMip);
         SkASSERT(NULL == rec->fBitmap.pixelRef());
         *mip = rec->fMip;
     }
     return rec_to_id(rec);
 }


 ////////////////////////////////////////////////////////////////////////////////
 /**
    This private method is the fully general record adder. All other
    record adders should call this funtion. */
 SkScaledImageCache::ID* SkScaledImageCache::addAndLock(SkScaledImageCache::Rec* rec) {
     SkASSERT(rec);
     // See if we already have this key (racy inserts, etc.)
     Rec* existing = this->findAndLock(rec->fKey);
     if (NULL != existing) {
         // Since we already have a matching entry, just delete the new one and return.
         // Call sites cannot assume the passed in object will live past this call.
         existing->fBitmap = rec->fBitmap;
         SkDELETE(rec);
         return rec_to_id(existing);
     }

     this->addToHead(rec);
     SkASSERT(1 == rec->fLockCount);
 #ifdef USE_HASH
     SkASSERT(fHash);
     fHash->add(rec);
 #endif
     // We may (now) be overbudget, so see if we need to purge something.
     this->purgeAsNeeded();
     return rec_to_id(rec);
 }

 SkScaledImageCache::ID* SkScaledImageCache::addAndLock(uint32_t genID,
                                                        int32_t width,
                                                        int32_t height,
                                                        const SkBitmap& bitmap) {
     Key key(genID, SK_Scalar1, SK_Scalar1, SkIRect::MakeWH(width, height));
     Rec* rec = SkNEW_ARGS(Rec, (key, bitmap));
     return this->addAndLock(rec);
 }

 SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig,
                                                        SkScalar scaleX,
                                                        SkScalar scaleY,
                                                        const SkBitmap& scaled) {
     if (0 == scaleX || 0 == scaleY) {
         // degenerate, and the key we use for mipmaps
         return NULL;
     }
     SkIRect bounds = get_bounds_from_bitmap(orig);
     if (bounds.isEmpty()) {
         return NULL;
     }
     Key key(orig.getGenerationID(), scaleX, scaleY, bounds);
     Rec* rec = SkNEW_ARGS(Rec, (key, scaled));
     return this->addAndLock(rec);
 }

 SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig,
                                                           const SkMipMap* mip) {
     SkIRect bounds = get_bounds_from_bitmap(orig);
     if (bounds.isEmpty()) {
         return NULL;
     }
     Key key(orig.getGenerationID(), 0, 0, bounds);
     Rec* rec = SkNEW_ARGS(Rec, (key, mip));
     return this->addAndLock(rec);
 }

 void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
     SkASSERT(id);

 #ifdef SK_DEBUG
     {
         bool found = false;
         Rec* rec = fHead;
         while (rec != NULL) {
             if (rec == id_to_rec(id)) {
                 found = true;
                 break;
             }
             rec = rec->fNext;
         }
         SkASSERT(found);
     }
 #endif
     Rec* rec = id_to_rec(id);
     SkASSERT(rec->fLockCount > 0);
     rec->fLockCount -= 1;

     // 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;
     int    countLimit;

     if (fDiscardableFactory) {
         countLimit = SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT;
         byteLimit = SK_MaxU32;  // no limit based on bytes
     } else {
         countLimit = SK_MaxS32; // no limit based on count
         byteLimit = fByteLimit;
     }

     size_t bytesUsed = fBytesUsed;
     int    countUsed = fCount;

     Rec* rec = fTail;
     while (rec) {
         if (bytesUsed < byteLimit && countUsed < countLimit) {
             break;
         }

         Rec* prev = rec->fPrev;
         if (0 == rec->fLockCount) {
             size_t used = rec->bytesUsed();
             SkASSERT(used <= bytesUsed);
             this->detach(rec);
 #ifdef USE_HASH
             fHash->remove(rec->fKey);
 #endif

             SkDELETE(rec);

             bytesUsed -= used;
             countUsed -= 1;
         }
         rec = prev;
     }

     fBytesUsed = bytesUsed;
     fCount = countUsed;
 }

 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

 void SkScaledImageCache::dump() const {
     this->validate();

     const Rec* rec = fHead;
     int locked = 0;
     while (rec) {
         locked += rec->fLockCount > 0;
         rec = rec->fNext;
     }

     SkDebugf("SkScaledImageCache: count=%d bytes=%d locked=%d %s\n",
              fCount, fBytesUsed, locked,
              fDiscardableFactory ? "discardable" : "malloc");
 }

 ///////////////////////////////////////////////////////////////////////////////

 #include "SkThread.h"

 SK_DECLARE_STATIC_MUTEX(gMutex);
 static SkScaledImageCache* gScaledImageCache = NULL;
 static void cleanup_gScaledImageCache() {
     // We'll clean this up in our own tests, but disable for clients.
     // Chrome seems to have funky multi-process things going on in unit tests that
     // makes this unsafe to delete when the main process atexit()s.
     // SkLazyPtr does the same sort of thing.
 #if SK_DEVELOPER
     SkDELETE(gScaledImageCache);
 #endif
 }

 /** Must hold gMutex when calling. */
 static SkScaledImageCache* get_cache() {
     // gMutex is always held when this is called, so we don't need to be fancy in here.
     gMutex.assertHeld();
     if (NULL == gScaledImageCache) {
 #ifdef SK_USE_DISCARDABLE_SCALEDIMAGECACHE
         gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SkDiscardableMemory::Create));
 #else
         gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT));
 #endif
         atexit(cleanup_gScaledImageCache);
     }
     return gScaledImageCache;
 }


 SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(
                                 uint32_t pixelGenerationID,
                                 int32_t width,
                                 int32_t height,
                                 SkBitmap* scaled) {
     SkAutoMutexAcquire am(gMutex);
     return get_cache()->findAndLock(pixelGenerationID, width, height, scaled);
 }

 SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(
                                uint32_t pixelGenerationID,
                                int32_t width,
                                int32_t height,
                                const SkBitmap& scaled) {
     SkAutoMutexAcquire am(gMutex);
     return get_cache()->addAndLock(pixelGenerationID, width, height, scaled);
 }


 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::FindAndLockMip(const SkBitmap& orig,
                                                        SkMipMap const ** mip) {
     SkAutoMutexAcquire am(gMutex);
     return get_cache()->findAndLockMip(orig, mip);
 }

 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);
 }

 SkScaledImageCache::ID* SkScaledImageCache::AddAndLockMip(const SkBitmap& orig,
                                                           const SkMipMap* mip) {
     SkAutoMutexAcquire am(gMutex);
     return get_cache()->addAndLockMip(orig, mip);
 }

 void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) {
     SkAutoMutexAcquire am(gMutex);
     get_cache()->unlock(id);

 //    get_cache()->dump();
 }

 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);
 }

 SkBitmap::Allocator* SkScaledImageCache::GetAllocator() {
     SkAutoMutexAcquire am(gMutex);
     return get_cache()->allocator();
 }

 void SkScaledImageCache::Dump() {
     SkAutoMutexAcquire am(gMutex);
     get_cache()->dump();
 }

 ///////////////////////////////////////////////////////////////////////////////

 #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);
 }
	/*
	* 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 "SkMipMap.h"
	#include "SkPixelRef.h"
	#include "SkRect.h"

	// This can be defined by the caller's build system
	//#define SK_USE_DISCARDABLE_SCALEDIMAGECACHE

	#ifndef SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT
	# define SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT 1024
	#endif

	#ifndef SK_DEFAULT_IMAGE_CACHE_LIMIT
	#define SK_DEFAULT_IMAGE_CACHE_LIMIT (2 * 1024 * 1024)
	#endif

	static inline SkScaledImageCache::ID* rec_to_id(SkScaledImageCache::Rec* rec) {
	return reinterpret_cast<SkScaledImageCache::ID*>(rec);
	}

	static inline SkScaledImageCache::Rec* id_to_rec(SkScaledImageCache::ID* id) {
	return reinterpret_cast<SkScaledImageCache::Rec*>(id);
	}

	// 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;
	}

	struct SkScaledImageCache::Key {
	Key(uint32_t genID,
	SkScalar scaleX,
	SkScalar scaleY,
	SkIRect bounds)
	: fGenID(genID)
	, fScaleX(scaleX)
	, fScaleY(scaleY)
	, fBounds(bounds) {
	fHash = compute_hash(&fGenID, 7);
	}

	bool operator<(const Key& other) const {
	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 {
	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;
	fMip = NULL;
	}

	Rec(const Key& key, const SkMipMap* mip) : fKey(key) {
	fLockCount = 1;
	fMip = mip;
	mip->ref();
	}

	~Rec() {
	SkSafeUnref(fMip);
	}

	static const Key& GetKey(const Rec& rec) { return rec.fKey; }
	static uint32_t Hash(const Key& key) { return key.fHash; }

	size_t bytesUsed() const {
	return fMip ? fMip->getSize() : fBitmap.getSize();
	}

	Rec* fNext;
	Rec* fPrev;

	// this guy wants to be 64bit aligned
	Key fKey;

	int32_t fLockCount;

	// we use either fBitmap or fMip, but not both
	SkBitmap fBitmap;
	const SkMipMap* fMip;
	};

	#include "SkTDynamicHash.h"

	class SkScaledImageCache::Hash :
	public SkTDynamicHash<SkScaledImageCache::Rec, SkScaledImageCache::Key> {};


	///////////////////////////////////////////////////////////////////////////////

	// experimental hash to speed things up
	#define USE_HASH

	#if !defined(USE_HASH)
	static inline SkScaledImageCache::Rec* find_rec_in_list(
	SkScaledImageCache::Rec* head, const Key & key) {
	SkScaledImageCache::Rec* rec = head;
	while ((rec != NULL) && (rec->fKey != key)) {
	rec = rec->fNext;
	}
	return rec;
	}
	#endif

	void SkScaledImageCache::init() {
	fHead = NULL;
	fTail = NULL;
	#ifdef USE_HASH
	fHash = new Hash;
	#else
	fHash = NULL;
	#endif
	fBytesUsed = 0;
	fCount = 0;
	fAllocator = NULL;

	// One of these should be explicit set by the caller after we return.
	fByteLimit = 0;
	fDiscardableFactory = NULL;
	}

	#include "SkDiscardableMemory.h"

	class SkOneShotDiscardablePixelRef : public SkPixelRef {
	public:
	SK_DECLARE_INST_COUNT(SkOneShotDiscardablePixelRef)
	// Ownership of the discardablememory is transfered to the pixelref
	SkOneShotDiscardablePixelRef(const SkImageInfo&, SkDiscardableMemory*, size_t rowBytes);
	~SkOneShotDiscardablePixelRef();

	#ifdef SK_SUPPORT_LEGACY_PIXELREF_UNFLATTENABLE
	SK_DECLARE_UNFLATTENABLE_OBJECT()
	#endif

	protected:
	virtual bool onNewLockPixels(LockRec*) SK_OVERRIDE;
	virtual void onUnlockPixels() SK_OVERRIDE;
	virtual size_t getAllocatedSizeInBytes() const SK_OVERRIDE;

	private:
	SkDiscardableMemory* fDM;
	size_t fRB;
	bool fFirstTime;

	typedef SkPixelRef INHERITED;
	};

	SkOneShotDiscardablePixelRef::SkOneShotDiscardablePixelRef(const SkImageInfo& info,
	SkDiscardableMemory* dm,
	size_t rowBytes)
	: INHERITED(info)
	, fDM(dm)
	, fRB(rowBytes)
	{
	SkASSERT(dm->data());
	fFirstTime = true;
	}

	SkOneShotDiscardablePixelRef::~SkOneShotDiscardablePixelRef() {
	SkDELETE(fDM);
	}

	bool SkOneShotDiscardablePixelRef::onNewLockPixels(LockRec* rec) {
	if (fFirstTime) {
	// we're already locked
	SkASSERT(fDM->data());
	fFirstTime = false;
	goto SUCCESS;
	}

	// A previous call to onUnlock may have deleted our DM, so check for that
	if (NULL == fDM) {
	return false;
	}

	if (!fDM->lock()) {
	// since it failed, we delete it now, to free-up the resource
	delete fDM;
	fDM = NULL;
	return false;
	}

	SUCCESS:
	rec->fPixels = fDM->data();
	rec->fColorTable = NULL;
	rec->fRowBytes = fRB;
	return true;
	}

	void SkOneShotDiscardablePixelRef::onUnlockPixels() {
	SkASSERT(!fFirstTime);
	fDM->unlock();
	}

	size_t SkOneShotDiscardablePixelRef::getAllocatedSizeInBytes() const {
	return this->info().getSafeSize(fRB);
	}

	class SkScaledImageCacheDiscardableAllocator : public SkBitmap::Allocator {
	public:
	SkScaledImageCacheDiscardableAllocator(
	SkScaledImageCache::DiscardableFactory factory) {
	SkASSERT(factory);
	fFactory = factory;
	}

	virtual bool allocPixelRef(SkBitmap, SkColorTable) SK_OVERRIDE;

	private:
	SkScaledImageCache::DiscardableFactory fFactory;
	};

	bool SkScaledImageCacheDiscardableAllocator::allocPixelRef(SkBitmap* bitmap,
	SkColorTable* ctable) {
	size_t size = bitmap->getSize();
	uint64_t size64 = bitmap->computeSize64();
	if (0 == size \|\| size64 > (uint64_t)size) {
	return false;
	}

	SkDiscardableMemory* dm = fFactory(size);
	if (NULL == dm) {
	return false;
	}

	// can we relax this?
	if (kN32_SkColorType != bitmap->colorType()) {
	return false;
	}

	SkImageInfo info = bitmap->info();
	bitmap->setPixelRef(SkNEW_ARGS(SkOneShotDiscardablePixelRef,
	(info, dm, bitmap->rowBytes())))->unref();
	bitmap->lockPixels();
	return bitmap->readyToDraw();
	}

	SkScaledImageCache::SkScaledImageCache(DiscardableFactory factory) {
	this->init();
	fDiscardableFactory = factory;

	fAllocator = SkNEW_ARGS(SkScaledImageCacheDiscardableAllocator, (factory));
	}

	SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
	this->init();
	fByteLimit = byteLimit;
	}

	SkScaledImageCache::~SkScaledImageCache() {
	SkSafeUnref(fAllocator);

	Rec* rec = fHead;
	while (rec) {
	Rec* next = rec->fNext;
	SkDELETE(rec);
	rec = next;
	}
	delete fHash;
	}

	////////////////////////////////////////////////////////////////////////////////


	SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(uint32_t genID,
	SkScalar scaleX,
	SkScalar scaleY,
	const SkIRect& bounds) {
	const Key key(genID, scaleX, scaleY, bounds);
	return this->findAndLock(key);
	}

	/**
	This private method is the fully general record finder. All other
	record finders should call this function or the one above. */
	SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkScaledImageCache::Key& key) {
	if (key.fBounds.isEmpty()) {
	return NULL;
	}
	#ifdef USE_HASH
	Rec* rec = fHash->find(key);
	#else
	Rec* rec = find_rec_in_list(fHead, key);
	#endif
	if (rec) {
	this->moveToHead(rec); // for our LRU
	rec->fLockCount += 1;
	}
	return rec;
	}

	/**
	This function finds the bounds of the bitmap within its pixelRef.
	If the bitmap lacks a pixelRef, it will return an empty rect, since
	that doesn't make sense. This may be a useful enough function that
	it should be somewhere else (in SkBitmap?). */
	static SkIRect get_bounds_from_bitmap(const SkBitmap& bm) {
	if (!(bm.pixelRef())) {
	return SkIRect::MakeEmpty();
	}
	SkIPoint origin = bm.pixelRefOrigin();
	return SkIRect::MakeXYWH(origin.fX, origin.fY, bm.width(), bm.height());
	}


	SkScaledImageCache::ID* SkScaledImageCache::findAndLock(uint32_t genID,
	int32_t width,
	int32_t height,
	SkBitmap* bitmap) {
	Rec* rec = this->findAndLock(genID, SK_Scalar1, SK_Scalar1,
	SkIRect::MakeWH(width, height));
	if (rec) {
	SkASSERT(NULL == rec->fMip);
	SkASSERT(rec->fBitmap.pixelRef());
	*bitmap = rec->fBitmap;
	}
	return rec_to_id(rec);
	}

	SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
	SkScalar scaleX,
	SkScalar scaleY,
	SkBitmap* scaled) {
	if (0 == scaleX \|\| 0 == scaleY) {
	// degenerate, and the key we use for mipmaps
	return NULL;
	}
	Rec* rec = this->findAndLock(orig.getGenerationID(), scaleX,
	scaleY, get_bounds_from_bitmap(orig));
	if (rec) {
	SkASSERT(NULL == rec->fMip);
	SkASSERT(rec->fBitmap.pixelRef());
	*scaled = rec->fBitmap;
	}
	return rec_to_id(rec);
	}

	SkScaledImageCache::ID* SkScaledImageCache::findAndLockMip(const SkBitmap& orig,
	SkMipMap const ** mip) {
	Rec* rec = this->findAndLock(orig.getGenerationID(), 0, 0,
	get_bounds_from_bitmap(orig));
	if (rec) {
	SkASSERT(rec->fMip);
	SkASSERT(NULL == rec->fBitmap.pixelRef());
	*mip = rec->fMip;
	}
	return rec_to_id(rec);
	}


	////////////////////////////////////////////////////////////////////////////////
	/**
	This private method is the fully general record adder. All other
	record adders should call this funtion. */
	SkScaledImageCache::ID* SkScaledImageCache::addAndLock(SkScaledImageCache::Rec* rec) {
	SkASSERT(rec);
	// See if we already have this key (racy inserts, etc.)
	Rec* existing = this->findAndLock(rec->fKey);
	if (NULL != existing) {
	// Since we already have a matching entry, just delete the new one and return.
	// Call sites cannot assume the passed in object will live past this call.
	existing->fBitmap = rec->fBitmap;
	SkDELETE(rec);
	return rec_to_id(existing);
	}

	this->addToHead(rec);
	SkASSERT(1 == rec->fLockCount);
	#ifdef USE_HASH
	SkASSERT(fHash);
	fHash->add(rec);
	#endif
	// We may (now) be overbudget, so see if we need to purge something.
	this->purgeAsNeeded();
	return rec_to_id(rec);
	}

	SkScaledImageCache::ID* SkScaledImageCache::addAndLock(uint32_t genID,
	int32_t width,
	int32_t height,
	const SkBitmap& bitmap) {
	Key key(genID, SK_Scalar1, SK_Scalar1, SkIRect::MakeWH(width, height));
	Rec* rec = SkNEW_ARGS(Rec, (key, bitmap));
	return this->addAndLock(rec);
	}

	SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig,
	SkScalar scaleX,
	SkScalar scaleY,
	const SkBitmap& scaled) {
	if (0 == scaleX \|\| 0 == scaleY) {
	// degenerate, and the key we use for mipmaps
	return NULL;
	}
	SkIRect bounds = get_bounds_from_bitmap(orig);
	if (bounds.isEmpty()) {
	return NULL;
	}
	Key key(orig.getGenerationID(), scaleX, scaleY, bounds);
	Rec* rec = SkNEW_ARGS(Rec, (key, scaled));
	return this->addAndLock(rec);
	}

	SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig,
	const SkMipMap* mip) {
	SkIRect bounds = get_bounds_from_bitmap(orig);
	if (bounds.isEmpty()) {
	return NULL;
	}
	Key key(orig.getGenerationID(), 0, 0, bounds);
	Rec* rec = SkNEW_ARGS(Rec, (key, mip));
	return this->addAndLock(rec);
	}

	void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
	SkASSERT(id);

	#ifdef SK_DEBUG
	{
	bool found = false;
	Rec* rec = fHead;
	while (rec != NULL) {
	if (rec == id_to_rec(id)) {
	found = true;
	break;
	}
	rec = rec->fNext;
	}
	SkASSERT(found);
	}
	#endif
	Rec* rec = id_to_rec(id);
	SkASSERT(rec->fLockCount > 0);
	rec->fLockCount -= 1;

	// 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;
	int countLimit;

	if (fDiscardableFactory) {
	countLimit = SK_DISCARDABLEMEMORY_SCALEDIMAGECACHE_COUNT_LIMIT;
	byteLimit = SK_MaxU32; // no limit based on bytes
	} else {
	countLimit = SK_MaxS32; // no limit based on count
	byteLimit = fByteLimit;
	}

	size_t bytesUsed = fBytesUsed;
	int countUsed = fCount;

	Rec* rec = fTail;
	while (rec) {
	if (bytesUsed < byteLimit && countUsed < countLimit) {
	break;
	}

	Rec* prev = rec->fPrev;
	if (0 == rec->fLockCount) {
	size_t used = rec->bytesUsed();
	SkASSERT(used <= bytesUsed);
	this->detach(rec);
	#ifdef USE_HASH
	fHash->remove(rec->fKey);
	#endif

	SkDELETE(rec);

	bytesUsed -= used;
	countUsed -= 1;
	}
	rec = prev;
	}

	fBytesUsed = bytesUsed;
	fCount = countUsed;
	}

	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

	void SkScaledImageCache::dump() const {
	this->validate();

	const Rec* rec = fHead;
	int locked = 0;
	while (rec) {
	locked += rec->fLockCount > 0;
	rec = rec->fNext;
	}

	SkDebugf("SkScaledImageCache: count=%d bytes=%d locked=%d %s\n",
	fCount, fBytesUsed, locked,
	fDiscardableFactory ? "discardable" : "malloc");
	}

	///////////////////////////////////////////////////////////////////////////////

	#include "SkThread.h"

	SK_DECLARE_STATIC_MUTEX(gMutex);
	static SkScaledImageCache* gScaledImageCache = NULL;
	static void cleanup_gScaledImageCache() {
	// We'll clean this up in our own tests, but disable for clients.
	// Chrome seems to have funky multi-process things going on in unit tests that
	// makes this unsafe to delete when the main process atexit()s.
	// SkLazyPtr does the same sort of thing.
	#if SK_DEVELOPER
	SkDELETE(gScaledImageCache);
	#endif
	}

	/** Must hold gMutex when calling. */
	static SkScaledImageCache* get_cache() {
	// gMutex is always held when this is called, so we don't need to be fancy in here.
	gMutex.assertHeld();
	if (NULL == gScaledImageCache) {
	#ifdef SK_USE_DISCARDABLE_SCALEDIMAGECACHE
	gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SkDiscardableMemory::Create));
	#else
	gScaledImageCache = SkNEW_ARGS(SkScaledImageCache, (SK_DEFAULT_IMAGE_CACHE_LIMIT));
	#endif
	atexit(cleanup_gScaledImageCache);
	}
	return gScaledImageCache;
	}


	SkScaledImageCache::ID* SkScaledImageCache::FindAndLock(
	uint32_t pixelGenerationID,
	int32_t width,
	int32_t height,
	SkBitmap* scaled) {
	SkAutoMutexAcquire am(gMutex);
	return get_cache()->findAndLock(pixelGenerationID, width, height, scaled);
	}

	SkScaledImageCache::ID* SkScaledImageCache::AddAndLock(
	uint32_t pixelGenerationID,
	int32_t width,
	int32_t height,
	const SkBitmap& scaled) {
	SkAutoMutexAcquire am(gMutex);
	return get_cache()->addAndLock(pixelGenerationID, width, height, scaled);
	}


	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::FindAndLockMip(const SkBitmap& orig,
	SkMipMap const ** mip) {
	SkAutoMutexAcquire am(gMutex);
	return get_cache()->findAndLockMip(orig, mip);
	}

	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);
	}

	SkScaledImageCache::ID* SkScaledImageCache::AddAndLockMip(const SkBitmap& orig,
	const SkMipMap* mip) {
	SkAutoMutexAcquire am(gMutex);
	return get_cache()->addAndLockMip(orig, mip);
	}

	void SkScaledImageCache::Unlock(SkScaledImageCache::ID* id) {
	SkAutoMutexAcquire am(gMutex);
	get_cache()->unlock(id);

	// get_cache()->dump();
	}

	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);
	}

	SkBitmap::Allocator* SkScaledImageCache::GetAllocator() {
	SkAutoMutexAcquire am(gMutex);
	return get_cache()->allocator();
	}

	void SkScaledImageCache::Dump() {
	SkAutoMutexAcquire am(gMutex);
	get_cache()->dump();
	}

	///////////////////////////////////////////////////////////////////////////////

	#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);
	}