121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com/* 321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com * Copyright 2012 Google Inc. 421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com * 521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com * Use of this source code is governed by a BSD-style license that can be 621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com * found in the LICENSE file. 721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com */ 821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com#include "SkBitmapHeap.h" 1021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 1121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com#include "SkBitmap.h" 128b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org#include "SkReadBuffer.h" 138b0e8ac5f582de80356019406e2975079bf0829dcommit-bot@chromium.org#include "SkWriteBuffer.h" 1421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com#include "SkTSearch.h" 1521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 1621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkBitmapHeapEntry::SkBitmapHeapEntry() 1721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com : fSlot(-1) 1821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fRefCount(0) 193e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com , fBytesAllocated(0) { 2021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 2121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 2221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkBitmapHeapEntry::~SkBitmapHeapEntry() { 2321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(0 == fRefCount); 2421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 2521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 2621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comvoid SkBitmapHeapEntry::addReferences(int count) { 2721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (0 == fRefCount) { 2821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // If there are no current owners then the heap manager 2921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // will be the only one able to modify it, so it does not 3021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // need to be an atomic operation. 3121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fRefCount = count; 3221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } else { 3321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com sk_atomic_add(&fRefCount, count); 3421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 3521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 3621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 3721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com/////////////////////////////////////////////////////////////////////////////// 3821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 39672588b684d484dce6ae251e9e163e4a46924322reed@google.comstatic bool operator<(const SkIPoint& a, const SkIPoint& b) { 40672588b684d484dce6ae251e9e163e4a46924322reed@google.com return *(const int64_t*)&a < *(const int64_t*)&b; 41672588b684d484dce6ae251e9e163e4a46924322reed@google.com} 42672588b684d484dce6ae251e9e163e4a46924322reed@google.com 43672588b684d484dce6ae251e9e163e4a46924322reed@google.comstatic bool operator>(const SkIPoint& a, const SkIPoint& b) { 44672588b684d484dce6ae251e9e163e4a46924322reed@google.com return *(const int64_t*)&a > *(const int64_t*)&b; 45672588b684d484dce6ae251e9e163e4a46924322reed@google.com} 46672588b684d484dce6ae251e9e163e4a46924322reed@google.com 4720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.combool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a, 4820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com const SkBitmapHeap::LookupEntry& b) { 4920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com if (a.fGenerationId < b.fGenerationId) { 5020f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return true; 5120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com } else if (a.fGenerationId > b.fGenerationId) { 5220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return false; 53672588b684d484dce6ae251e9e163e4a46924322reed@google.com } else if (a.fPixelOrigin < b.fPixelOrigin) { 5420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return true; 55672588b684d484dce6ae251e9e163e4a46924322reed@google.com } else if (a.fPixelOrigin > b.fPixelOrigin) { 5620f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return false; 5720f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com } else if (a.fWidth < b.fWidth) { 5820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return true; 5920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com } else if (a.fWidth > b.fWidth) { 6020f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return false; 6120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com } else if (a.fHeight < b.fHeight) { 6220f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return true; 633e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 6420f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com return false; 653e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com} 663e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com 673e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com/////////////////////////////////////////////////////////////////////////////// 683e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com 6921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount) 7021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com : INHERITED() 7121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fExternalStorage(NULL) 7221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fMostRecentlyUsed(NULL) 7321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fLeastRecentlyUsed(NULL) 7421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fPreferredCount(preferredSize) 7521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fOwnerCount(ownerCount) 767ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com , fBytesAllocated(0) 777ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com , fDeferAddingOwners(false) { 7821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 7921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 8021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize) 8121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com : INHERITED() 8221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fExternalStorage(storage) 8321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fMostRecentlyUsed(NULL) 8421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fLeastRecentlyUsed(NULL) 8521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fPreferredCount(preferredSize) 8621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com , fOwnerCount(IGNORE_OWNERS) 877ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com , fBytesAllocated(0) 887ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com , fDeferAddingOwners(false) { 8910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkSafeRef(storage); 9021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 9121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 9221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkBitmapHeap::~SkBitmapHeap() { 9310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkDEBUGCODE( 9410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com for (int i = 0; i < fStorage.count(); i++) { 9510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com bool unused = false; 9610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com for (int j = 0; j < fUnusedSlots.count(); j++) { 9710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (fUnusedSlots[j] == fStorage[i]->fSlot) { 9810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com unused = true; 9910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com break; 10010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 10110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 10210dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (!unused) { 10310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fBytesAllocated -= fStorage[i]->fBytesAllocated; 10410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 10510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 10610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); 10710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com ) 10810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkASSERT(0 == fBytesAllocated); 10921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fStorage.deleteAll(); 11021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkSafeUnref(fExternalStorage); 111c51db02181982fbcb8888e2a89132363a7d9371cscroggo fLookupTable.deleteAll(); 11221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 11321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 11421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comSkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const { 11521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com const int size = fStorage.count(); 11621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkTRefArray<SkBitmap>* array = NULL; 11721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (size > 0) { 11821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com array = SkTRefArray<SkBitmap>::Create(size); 11921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com for (int i = 0; i < size; i++) { 12021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // make a shallow copy of the bitmap 12121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com array->writableAt(i) = fStorage[i]->fBitmap; 12221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 12321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 12421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return array; 12521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 12621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 1273e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.comvoid SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) { 1283e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (fMostRecentlyUsed == entry) { 1293e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fMostRecentlyUsed = entry->fLessRecentlyUsed; 1303e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (NULL == fMostRecentlyUsed) { 1313e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkASSERT(fLeastRecentlyUsed == entry); 1323e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fLeastRecentlyUsed = NULL; 1333e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } else { 1343e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fMostRecentlyUsed->fMoreRecentlyUsed = NULL; 1353e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 1363e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } else { 1373e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // Remove entry from its prior place, and make sure to cover the hole. 1383e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (fLeastRecentlyUsed == entry) { 1393e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkASSERT(entry->fMoreRecentlyUsed != NULL); 1403e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fLeastRecentlyUsed = entry->fMoreRecentlyUsed; 1413e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 1423e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // Since we have already considered the case where entry is the most recently used, it must 1433e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // have a more recently used at this point. 14421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(entry->fMoreRecentlyUsed != NULL); 14521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed; 1463e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com 1473e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (entry->fLessRecentlyUsed != NULL) { 1483e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkASSERT(fLeastRecentlyUsed != entry); 1493e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed; 1503e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 15121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 15221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com entry->fMoreRecentlyUsed = NULL; 1533e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com} 1543e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com 1553e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.comvoid SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) { 15621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fMostRecentlyUsed != NULL) { 15721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed); 15821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fMostRecentlyUsed->fMoreRecentlyUsed = entry; 15921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com entry->fLessRecentlyUsed = fMostRecentlyUsed; 16021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 16121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fMostRecentlyUsed = entry; 16221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (NULL == fLeastRecentlyUsed) { 16321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fLeastRecentlyUsed = entry; 16421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 16521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 16621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 16721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com// iterate through our LRU cache and try to find an entry to evict 1683e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.comSkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) { 16921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(fPreferredCount != UNLIMITED_SIZE); 17021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(fStorage.count() >= fPreferredCount); 17121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 1723e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed; 17321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com while (iter != NULL) { 1743e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; 1753e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (heapEntry->fRefCount > 0) { 17621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // If the least recently used bitmap has not been unreferenced 17721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // by its owner, then according to our LRU specifications a more 1787ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com // recently used one can not have used all its references yet either. 17921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return NULL; 18021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 1813e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (replacement.getGenerationID() == iter->fGenerationId) { 18221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // Do not replace a bitmap with a new one using the same 18321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // pixel ref. Instead look for a different one that will 18421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // potentially free up more space. 18521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com iter = iter->fMoreRecentlyUsed; 18621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } else { 18721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return iter; 18821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 18921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 19021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return NULL; 19121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 19221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 19310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.comsize_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) { 19410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (UNLIMITED_SIZE == fPreferredCount) { 19510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com return 0; 19610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 1973e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com LookupEntry* iter = fLeastRecentlyUsed; 19810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com size_t origBytesAllocated = fBytesAllocated; 19910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // Purge starting from LRU until a non-evictable bitmap is found or until 20010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // everything is evicted. 2013e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com while (iter != NULL) { 2023e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; 2033e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (heapEntry->fRefCount > 0) { 2043e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com break; 2053e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 2063e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com LookupEntry* next = iter->fMoreRecentlyUsed; 2073e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com this->removeEntryFromLookupTable(iter); 20810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // Free the pixel memory. removeEntryFromLookupTable already reduced 20910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // fBytesAllocated properly. 2103e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com heapEntry->fBitmap.reset(); 21110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // Add to list of unused slots which can be reused in the future. 2123e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fUnusedSlots.push(heapEntry->fSlot); 21310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com iter = next; 21410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (origBytesAllocated - fBytesAllocated >= bytesToFree) { 21510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com break; 21610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 21710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 21810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com 21910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (fLeastRecentlyUsed != iter) { 22010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // There was at least one eviction. 22110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fLeastRecentlyUsed = iter; 22210dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (NULL == fLeastRecentlyUsed) { 22310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // Everything was evicted 22410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fMostRecentlyUsed = NULL; 22510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); 22610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fStorage.deleteAll(); 22710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fUnusedSlots.reset(); 22810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkASSERT(0 == fBytesAllocated); 22910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } else { 23010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fLeastRecentlyUsed->fLessRecentlyUsed = NULL; 23110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 23210dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 233fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 23410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com return origBytesAllocated - fBytesAllocated; 23510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com} 23610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com 23710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.comint SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) { 23820f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com int index = SkTSearch<const LookupEntry, LookupEntry::Less>( 23920f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com (const LookupEntry**)fLookupTable.begin(), 24010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fLookupTable.count(), 24120f7f173e05b60f541910d0c1da9850ac73e2958bsalomon@google.com &indexEntry, sizeof(void*)); 24221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 24321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (index < 0) { 24421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // insert ourselves into the bitmapIndex 24521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com index = ~index; 2463e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry)); 24721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } else if (entry != NULL) { 24821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // populate the entry if needed 2493e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com *entry = fStorage[fLookupTable[index]->fStorageSlot]; 25021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 25121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 25221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return index; 25321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 25421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 25521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.combool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) { 25621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkASSERT(!fExternalStorage); 25721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 25821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // If the bitmap is mutable, we need to do a deep copy, since the 25921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // caller may modify it afterwards. 26021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (originalBitmap.isImmutable()) { 26121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com copiedBitmap = originalBitmap; 26221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com// TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy 26321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com// else if (sharedPixelRef != NULL) { 26421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com// copiedBitmap = orig; 26521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com// copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset()); 26621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } else if (originalBitmap.empty()) { 26721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com copiedBitmap.reset(); 2686285f4f7662853336b788d6ee3e177c396f7fb01commit-bot@chromium.org } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) { 26921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return false; 27021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 27121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com copiedBitmap.setImmutable(); 27221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return true; 27321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 27421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 2753e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.comint SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) { 27610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // remove the bitmap index for the deleted entry 27710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkDEBUGCODE(int count = fLookupTable.count();) 2783e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com int index = this->findInLookupTable(*entry, NULL); 27910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // Verify that findInLookupTable found an existing entry rather than adding 28010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // a new entry to the lookup table. 28110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkASSERT(count == fLookupTable.count()); 2823e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated; 2833e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkDELETE(fLookupTable[index]); 28410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fLookupTable.remove(index); 28510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com return index; 28610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com} 28710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com 28821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.comint32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) { 28921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com SkBitmapHeapEntry* entry = NULL; 29010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry); 29121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 29221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (entry) { 2933e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // Already had a copy of the bitmap in the heap. 29421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fOwnerCount != IGNORE_OWNERS) { 2957ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com if (fDeferAddingOwners) { 2967ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com *fDeferredEntries.append() = entry->fSlot; 2977ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com } else { 2987ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com entry->addReferences(fOwnerCount); 2997ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com } 30021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 30121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fPreferredCount != UNLIMITED_SIZE) { 3023e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com LookupEntry* lookupEntry = fLookupTable[searchIndex]; 3033e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (lookupEntry != fMostRecentlyUsed) { 3043e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com this->removeFromLRU(lookupEntry); 3053e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com this->appendToLRU(lookupEntry); 3063e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } 30721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 30821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return entry->fSlot; 30921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 31021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 31121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // decide if we need to evict an existing heap entry or create a new one 31221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) { 31321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // iterate through our LRU cache and try to find an entry to evict 3143e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap); 3153e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com if (lookupEntry != NULL) { 3163e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // we found an entry to evict 3173e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com entry = fStorage[lookupEntry->fStorageSlot]; 3183e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // Remove it from the LRU. The new entry will be added to the LRU later. 3193e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com this->removeFromLRU(lookupEntry); 3203e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com int index = this->removeEntryFromLookupTable(lookupEntry); 32121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 32221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // update the current search index now that we have removed one 32321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (index < searchIndex) { 32421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com searchIndex--; 32521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 32621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 32721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 32821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 32921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // if we didn't have an entry yet we need to create one 33021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (!entry) { 33110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) { 33210dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com int slot; 33310dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fUnusedSlots.pop(&slot); 33410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com entry = fStorage[slot]; 33510dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } else { 33610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com entry = SkNEW(SkBitmapHeapEntry); 33710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fStorage.append(1, &entry); 33810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com entry->fSlot = fStorage.count() - 1; 33910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fBytesAllocated += sizeof(SkBitmapHeapEntry); 34010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 34121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 34221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 34321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // create a copy of the bitmap 34421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com bool copySucceeded; 34521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fExternalStorage) { 34621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot); 34721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } else { 34821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com copySucceeded = copyBitmap(originalBitmap, entry->fBitmap); 34921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 35021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 35121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // if the copy failed then we must abort 35221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (!copySucceeded) { 35321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // delete the index 3543e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com SkDELETE(fLookupTable[searchIndex]); 35521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fLookupTable.remove(searchIndex); 35610dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // If entry is the last slot in storage, it is safe to delete it. 35710dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com if (fStorage.count() - 1 == entry->fSlot) { 35810dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com // free the slot 35910dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fStorage.remove(entry->fSlot); 36010dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com fBytesAllocated -= sizeof(SkBitmapHeapEntry); 36110dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com SkDELETE(entry); 3623e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com } else { 3633e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fUnusedSlots.push(entry->fSlot); 36410dccde54a769b8d472bccf8c1993034b93ef58dscroggo@google.com } 36521830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return INVALID_SLOT; 36621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 36721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 36821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // update the index with the appropriate slot in the heap 3693e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com fLookupTable[searchIndex]->fStorageSlot = entry->fSlot; 37021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 3713e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com // compute the space taken by this entry 37221830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // TODO if there is a shared pixel ref don't count it 37321830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // If the SkBitmap does not share an SkPixelRef with an SkBitmap already 37421830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // in the SharedHeap, also include the size of its pixels. 375ce65f385a0d31a93a31ffd57478de4b8c4e833b3junov@chromium.org entry->fBytesAllocated = originalBitmap.getSize(); 37621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 37721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com // add the bytes from this entry to the total count 37821830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com fBytesAllocated += entry->fBytesAllocated; 37921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com 38021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fOwnerCount != IGNORE_OWNERS) { 381013c5d9107a4abd50e879ca66cf60b0c3a8256d4scroggo@google.com if (fDeferAddingOwners) { 382013c5d9107a4abd50e879ca66cf60b0c3a8256d4scroggo@google.com *fDeferredEntries.append() = entry->fSlot; 383013c5d9107a4abd50e879ca66cf60b0c3a8256d4scroggo@google.com } else { 384013c5d9107a4abd50e879ca66cf60b0c3a8256d4scroggo@google.com entry->addReferences(fOwnerCount); 385013c5d9107a4abd50e879ca66cf60b0c3a8256d4scroggo@google.com } 38621830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 38721830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com if (fPreferredCount != UNLIMITED_SIZE) { 3883e26bd0c357d849ff40b092decd7a5c46ec2ada4scroggo@google.com this->appendToLRU(fLookupTable[searchIndex]); 38921830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com } 39021830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com return entry->fSlot; 39121830d90096d2dccc4168d99a427e78035ce942adjsollen@google.com} 3927ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com 3937ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.comvoid SkBitmapHeap::deferAddingOwners() { 3947ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com fDeferAddingOwners = true; 3957ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com} 3967ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com 3977ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.comvoid SkBitmapHeap::endAddingOwnersDeferral(bool add) { 3987ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com if (add) { 3997ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com for (int i = 0; i < fDeferredEntries.count(); i++) { 4007ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com SkASSERT(fOwnerCount != IGNORE_OWNERS); 4017ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]); 4027ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com SkASSERT(heapEntry != NULL); 4037ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com heapEntry->addReferences(fOwnerCount); 4047ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com } 4057ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com } 4067ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com fDeferAddingOwners = false; 4077ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com fDeferredEntries.reset(); 4087ca24437c71af06fc06ab5f6f261b185882fa440scroggo@google.com} 409