1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkBitmapHeap.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,408 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2012 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#include "SkBitmapHeap.h"
1.13 +
1.14 +#include "SkBitmap.h"
1.15 +#include "SkReadBuffer.h"
1.16 +#include "SkWriteBuffer.h"
1.17 +#include "SkTSearch.h"
1.18 +
1.19 +SkBitmapHeapEntry::SkBitmapHeapEntry()
1.20 + : fSlot(-1)
1.21 + , fRefCount(0)
1.22 + , fBytesAllocated(0) {
1.23 +}
1.24 +
1.25 +SkBitmapHeapEntry::~SkBitmapHeapEntry() {
1.26 + SkASSERT(0 == fRefCount);
1.27 +}
1.28 +
1.29 +void SkBitmapHeapEntry::addReferences(int count) {
1.30 + if (0 == fRefCount) {
1.31 + // If there are no current owners then the heap manager
1.32 + // will be the only one able to modify it, so it does not
1.33 + // need to be an atomic operation.
1.34 + fRefCount = count;
1.35 + } else {
1.36 + sk_atomic_add(&fRefCount, count);
1.37 + }
1.38 +}
1.39 +
1.40 +///////////////////////////////////////////////////////////////////////////////
1.41 +
1.42 +static bool operator<(const SkIPoint& a, const SkIPoint& b) {
1.43 + return *(const int64_t*)&a < *(const int64_t*)&b;
1.44 +}
1.45 +
1.46 +static bool operator>(const SkIPoint& a, const SkIPoint& b) {
1.47 + return *(const int64_t*)&a > *(const int64_t*)&b;
1.48 +}
1.49 +
1.50 +bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
1.51 + const SkBitmapHeap::LookupEntry& b) {
1.52 + if (a.fGenerationId < b.fGenerationId) {
1.53 + return true;
1.54 + } else if (a.fGenerationId > b.fGenerationId) {
1.55 + return false;
1.56 + } else if (a.fPixelOrigin < b.fPixelOrigin) {
1.57 + return true;
1.58 + } else if (a.fPixelOrigin > b.fPixelOrigin) {
1.59 + return false;
1.60 + } else if (a.fWidth < b.fWidth) {
1.61 + return true;
1.62 + } else if (a.fWidth > b.fWidth) {
1.63 + return false;
1.64 + } else if (a.fHeight < b.fHeight) {
1.65 + return true;
1.66 + }
1.67 + return false;
1.68 +}
1.69 +
1.70 +///////////////////////////////////////////////////////////////////////////////
1.71 +
1.72 +SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount)
1.73 + : INHERITED()
1.74 + , fExternalStorage(NULL)
1.75 + , fMostRecentlyUsed(NULL)
1.76 + , fLeastRecentlyUsed(NULL)
1.77 + , fPreferredCount(preferredSize)
1.78 + , fOwnerCount(ownerCount)
1.79 + , fBytesAllocated(0)
1.80 + , fDeferAddingOwners(false) {
1.81 +}
1.82 +
1.83 +SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
1.84 + : INHERITED()
1.85 + , fExternalStorage(storage)
1.86 + , fMostRecentlyUsed(NULL)
1.87 + , fLeastRecentlyUsed(NULL)
1.88 + , fPreferredCount(preferredSize)
1.89 + , fOwnerCount(IGNORE_OWNERS)
1.90 + , fBytesAllocated(0)
1.91 + , fDeferAddingOwners(false) {
1.92 + SkSafeRef(storage);
1.93 +}
1.94 +
1.95 +SkBitmapHeap::~SkBitmapHeap() {
1.96 + SkDEBUGCODE(
1.97 + for (int i = 0; i < fStorage.count(); i++) {
1.98 + bool unused = false;
1.99 + for (int j = 0; j < fUnusedSlots.count(); j++) {
1.100 + if (fUnusedSlots[j] == fStorage[i]->fSlot) {
1.101 + unused = true;
1.102 + break;
1.103 + }
1.104 + }
1.105 + if (!unused) {
1.106 + fBytesAllocated -= fStorage[i]->fBytesAllocated;
1.107 + }
1.108 + }
1.109 + fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
1.110 + )
1.111 + SkASSERT(0 == fBytesAllocated);
1.112 + fStorage.deleteAll();
1.113 + SkSafeUnref(fExternalStorage);
1.114 + fLookupTable.deleteAll();
1.115 +}
1.116 +
1.117 +SkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const {
1.118 + const int size = fStorage.count();
1.119 + SkTRefArray<SkBitmap>* array = NULL;
1.120 + if (size > 0) {
1.121 + array = SkTRefArray<SkBitmap>::Create(size);
1.122 + for (int i = 0; i < size; i++) {
1.123 + // make a shallow copy of the bitmap
1.124 + array->writableAt(i) = fStorage[i]->fBitmap;
1.125 + }
1.126 + }
1.127 + return array;
1.128 +}
1.129 +
1.130 +void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) {
1.131 + if (fMostRecentlyUsed == entry) {
1.132 + fMostRecentlyUsed = entry->fLessRecentlyUsed;
1.133 + if (NULL == fMostRecentlyUsed) {
1.134 + SkASSERT(fLeastRecentlyUsed == entry);
1.135 + fLeastRecentlyUsed = NULL;
1.136 + } else {
1.137 + fMostRecentlyUsed->fMoreRecentlyUsed = NULL;
1.138 + }
1.139 + } else {
1.140 + // Remove entry from its prior place, and make sure to cover the hole.
1.141 + if (fLeastRecentlyUsed == entry) {
1.142 + SkASSERT(entry->fMoreRecentlyUsed != NULL);
1.143 + fLeastRecentlyUsed = entry->fMoreRecentlyUsed;
1.144 + }
1.145 + // Since we have already considered the case where entry is the most recently used, it must
1.146 + // have a more recently used at this point.
1.147 + SkASSERT(entry->fMoreRecentlyUsed != NULL);
1.148 + entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed;
1.149 +
1.150 + if (entry->fLessRecentlyUsed != NULL) {
1.151 + SkASSERT(fLeastRecentlyUsed != entry);
1.152 + entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
1.153 + }
1.154 + }
1.155 + entry->fMoreRecentlyUsed = NULL;
1.156 +}
1.157 +
1.158 +void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) {
1.159 + if (fMostRecentlyUsed != NULL) {
1.160 + SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed);
1.161 + fMostRecentlyUsed->fMoreRecentlyUsed = entry;
1.162 + entry->fLessRecentlyUsed = fMostRecentlyUsed;
1.163 + }
1.164 + fMostRecentlyUsed = entry;
1.165 + if (NULL == fLeastRecentlyUsed) {
1.166 + fLeastRecentlyUsed = entry;
1.167 + }
1.168 +}
1.169 +
1.170 +// iterate through our LRU cache and try to find an entry to evict
1.171 +SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
1.172 + SkASSERT(fPreferredCount != UNLIMITED_SIZE);
1.173 + SkASSERT(fStorage.count() >= fPreferredCount);
1.174 +
1.175 + SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed;
1.176 + while (iter != NULL) {
1.177 + SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
1.178 + if (heapEntry->fRefCount > 0) {
1.179 + // If the least recently used bitmap has not been unreferenced
1.180 + // by its owner, then according to our LRU specifications a more
1.181 + // recently used one can not have used all its references yet either.
1.182 + return NULL;
1.183 + }
1.184 + if (replacement.getGenerationID() == iter->fGenerationId) {
1.185 + // Do not replace a bitmap with a new one using the same
1.186 + // pixel ref. Instead look for a different one that will
1.187 + // potentially free up more space.
1.188 + iter = iter->fMoreRecentlyUsed;
1.189 + } else {
1.190 + return iter;
1.191 + }
1.192 + }
1.193 + return NULL;
1.194 +}
1.195 +
1.196 +size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
1.197 + if (UNLIMITED_SIZE == fPreferredCount) {
1.198 + return 0;
1.199 + }
1.200 + LookupEntry* iter = fLeastRecentlyUsed;
1.201 + size_t origBytesAllocated = fBytesAllocated;
1.202 + // Purge starting from LRU until a non-evictable bitmap is found or until
1.203 + // everything is evicted.
1.204 + while (iter != NULL) {
1.205 + SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
1.206 + if (heapEntry->fRefCount > 0) {
1.207 + break;
1.208 + }
1.209 + LookupEntry* next = iter->fMoreRecentlyUsed;
1.210 + this->removeEntryFromLookupTable(iter);
1.211 + // Free the pixel memory. removeEntryFromLookupTable already reduced
1.212 + // fBytesAllocated properly.
1.213 + heapEntry->fBitmap.reset();
1.214 + // Add to list of unused slots which can be reused in the future.
1.215 + fUnusedSlots.push(heapEntry->fSlot);
1.216 + iter = next;
1.217 + if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
1.218 + break;
1.219 + }
1.220 + }
1.221 +
1.222 + if (fLeastRecentlyUsed != iter) {
1.223 + // There was at least one eviction.
1.224 + fLeastRecentlyUsed = iter;
1.225 + if (NULL == fLeastRecentlyUsed) {
1.226 + // Everything was evicted
1.227 + fMostRecentlyUsed = NULL;
1.228 + fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
1.229 + fStorage.deleteAll();
1.230 + fUnusedSlots.reset();
1.231 + SkASSERT(0 == fBytesAllocated);
1.232 + } else {
1.233 + fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
1.234 + }
1.235 + }
1.236 +
1.237 + return origBytesAllocated - fBytesAllocated;
1.238 +}
1.239 +
1.240 +int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
1.241 + int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
1.242 + (const LookupEntry**)fLookupTable.begin(),
1.243 + fLookupTable.count(),
1.244 + &indexEntry, sizeof(void*));
1.245 +
1.246 + if (index < 0) {
1.247 + // insert ourselves into the bitmapIndex
1.248 + index = ~index;
1.249 + *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry));
1.250 + } else if (entry != NULL) {
1.251 + // populate the entry if needed
1.252 + *entry = fStorage[fLookupTable[index]->fStorageSlot];
1.253 + }
1.254 +
1.255 + return index;
1.256 +}
1.257 +
1.258 +bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
1.259 + SkASSERT(!fExternalStorage);
1.260 +
1.261 + // If the bitmap is mutable, we need to do a deep copy, since the
1.262 + // caller may modify it afterwards.
1.263 + if (originalBitmap.isImmutable()) {
1.264 + copiedBitmap = originalBitmap;
1.265 +// TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy
1.266 +// else if (sharedPixelRef != NULL) {
1.267 +// copiedBitmap = orig;
1.268 +// copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset());
1.269 + } else if (originalBitmap.empty()) {
1.270 + copiedBitmap.reset();
1.271 + } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) {
1.272 + return false;
1.273 + }
1.274 + copiedBitmap.setImmutable();
1.275 + return true;
1.276 +}
1.277 +
1.278 +int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) {
1.279 + // remove the bitmap index for the deleted entry
1.280 + SkDEBUGCODE(int count = fLookupTable.count();)
1.281 + int index = this->findInLookupTable(*entry, NULL);
1.282 + // Verify that findInLookupTable found an existing entry rather than adding
1.283 + // a new entry to the lookup table.
1.284 + SkASSERT(count == fLookupTable.count());
1.285 + fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated;
1.286 + SkDELETE(fLookupTable[index]);
1.287 + fLookupTable.remove(index);
1.288 + return index;
1.289 +}
1.290 +
1.291 +int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
1.292 + SkBitmapHeapEntry* entry = NULL;
1.293 + int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
1.294 +
1.295 + if (entry) {
1.296 + // Already had a copy of the bitmap in the heap.
1.297 + if (fOwnerCount != IGNORE_OWNERS) {
1.298 + if (fDeferAddingOwners) {
1.299 + *fDeferredEntries.append() = entry->fSlot;
1.300 + } else {
1.301 + entry->addReferences(fOwnerCount);
1.302 + }
1.303 + }
1.304 + if (fPreferredCount != UNLIMITED_SIZE) {
1.305 + LookupEntry* lookupEntry = fLookupTable[searchIndex];
1.306 + if (lookupEntry != fMostRecentlyUsed) {
1.307 + this->removeFromLRU(lookupEntry);
1.308 + this->appendToLRU(lookupEntry);
1.309 + }
1.310 + }
1.311 + return entry->fSlot;
1.312 + }
1.313 +
1.314 + // decide if we need to evict an existing heap entry or create a new one
1.315 + if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) {
1.316 + // iterate through our LRU cache and try to find an entry to evict
1.317 + LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap);
1.318 + if (lookupEntry != NULL) {
1.319 + // we found an entry to evict
1.320 + entry = fStorage[lookupEntry->fStorageSlot];
1.321 + // Remove it from the LRU. The new entry will be added to the LRU later.
1.322 + this->removeFromLRU(lookupEntry);
1.323 + int index = this->removeEntryFromLookupTable(lookupEntry);
1.324 +
1.325 + // update the current search index now that we have removed one
1.326 + if (index < searchIndex) {
1.327 + searchIndex--;
1.328 + }
1.329 + }
1.330 + }
1.331 +
1.332 + // if we didn't have an entry yet we need to create one
1.333 + if (!entry) {
1.334 + if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
1.335 + int slot;
1.336 + fUnusedSlots.pop(&slot);
1.337 + entry = fStorage[slot];
1.338 + } else {
1.339 + entry = SkNEW(SkBitmapHeapEntry);
1.340 + fStorage.append(1, &entry);
1.341 + entry->fSlot = fStorage.count() - 1;
1.342 + fBytesAllocated += sizeof(SkBitmapHeapEntry);
1.343 + }
1.344 + }
1.345 +
1.346 + // create a copy of the bitmap
1.347 + bool copySucceeded;
1.348 + if (fExternalStorage) {
1.349 + copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot);
1.350 + } else {
1.351 + copySucceeded = copyBitmap(originalBitmap, entry->fBitmap);
1.352 + }
1.353 +
1.354 + // if the copy failed then we must abort
1.355 + if (!copySucceeded) {
1.356 + // delete the index
1.357 + SkDELETE(fLookupTable[searchIndex]);
1.358 + fLookupTable.remove(searchIndex);
1.359 + // If entry is the last slot in storage, it is safe to delete it.
1.360 + if (fStorage.count() - 1 == entry->fSlot) {
1.361 + // free the slot
1.362 + fStorage.remove(entry->fSlot);
1.363 + fBytesAllocated -= sizeof(SkBitmapHeapEntry);
1.364 + SkDELETE(entry);
1.365 + } else {
1.366 + fUnusedSlots.push(entry->fSlot);
1.367 + }
1.368 + return INVALID_SLOT;
1.369 + }
1.370 +
1.371 + // update the index with the appropriate slot in the heap
1.372 + fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
1.373 +
1.374 + // compute the space taken by this entry
1.375 + // TODO if there is a shared pixel ref don't count it
1.376 + // If the SkBitmap does not share an SkPixelRef with an SkBitmap already
1.377 + // in the SharedHeap, also include the size of its pixels.
1.378 + entry->fBytesAllocated = originalBitmap.getSize();
1.379 +
1.380 + // add the bytes from this entry to the total count
1.381 + fBytesAllocated += entry->fBytesAllocated;
1.382 +
1.383 + if (fOwnerCount != IGNORE_OWNERS) {
1.384 + if (fDeferAddingOwners) {
1.385 + *fDeferredEntries.append() = entry->fSlot;
1.386 + } else {
1.387 + entry->addReferences(fOwnerCount);
1.388 + }
1.389 + }
1.390 + if (fPreferredCount != UNLIMITED_SIZE) {
1.391 + this->appendToLRU(fLookupTable[searchIndex]);
1.392 + }
1.393 + return entry->fSlot;
1.394 +}
1.395 +
1.396 +void SkBitmapHeap::deferAddingOwners() {
1.397 + fDeferAddingOwners = true;
1.398 +}
1.399 +
1.400 +void SkBitmapHeap::endAddingOwnersDeferral(bool add) {
1.401 + if (add) {
1.402 + for (int i = 0; i < fDeferredEntries.count(); i++) {
1.403 + SkASSERT(fOwnerCount != IGNORE_OWNERS);
1.404 + SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]);
1.405 + SkASSERT(heapEntry != NULL);
1.406 + heapEntry->addReferences(fOwnerCount);
1.407 + }
1.408 + }
1.409 + fDeferAddingOwners = false;
1.410 + fDeferredEntries.reset();
1.411 +}
