The Tor Browser: comparison gfx/skia/trunk/src/core/SkBitmapHeap.cpp

--1:000000000000
+:aec31c864eda
+/*
+* Copyright 2012 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#include "SkBitmapHeap.h"
+#include "SkBitmap.h"
+#include "SkReadBuffer.h"
+#include "SkWriteBuffer.h"
+#include "SkTSearch.h"
+SkBitmapHeapEntry::SkBitmapHeapEntry()
+: fSlot(-1)
+, fRefCount(0)
+, fBytesAllocated(0) {
+}
+SkBitmapHeapEntry::~SkBitmapHeapEntry() {
+SkASSERT(0 == fRefCount);
+}
+void SkBitmapHeapEntry::addReferences(int count) {
+if (0 == fRefCount) {
+// If there are no current owners then the heap manager
+// will be the only one able to modify it, so it does not
+// need to be an atomic operation.
+fRefCount = count;
+} else {
+sk_atomic_add(&fRefCount, count);
+}
+}
+///////////////////////////////////////////////////////////////////////////////
+static bool operator<(const SkIPoint& a, const SkIPoint& b) {
+return *(const int64_t*)&a < *(const int64_t*)&b;
+}
+static bool operator>(const SkIPoint& a, const SkIPoint& b) {
+return *(const int64_t*)&a > *(const int64_t*)&b;
+}
+bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
+const SkBitmapHeap::LookupEntry& b) {
+if (a.fGenerationId < b.fGenerationId) {
+return true;
+} else if (a.fGenerationId > b.fGenerationId) {
+return false;
+} else if (a.fPixelOrigin < b.fPixelOrigin) {
+return true;
+} else if (a.fPixelOrigin > b.fPixelOrigin) {
+return false;
+} else if (a.fWidth < b.fWidth) {
+return true;
+} else if (a.fWidth > b.fWidth) {
+return false;
+} else if (a.fHeight < b.fHeight) {
+return true;
+}
+return false;
+}
+///////////////////////////////////////////////////////////////////////////////
+SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount)
+: INHERITED()
+, fExternalStorage(NULL)
+, fMostRecentlyUsed(NULL)
+, fLeastRecentlyUsed(NULL)
+, fPreferredCount(preferredSize)
+, fOwnerCount(ownerCount)
+, fBytesAllocated(0)
+, fDeferAddingOwners(false) {
+}
+SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
+: INHERITED()
+, fExternalStorage(storage)
+, fMostRecentlyUsed(NULL)
+, fLeastRecentlyUsed(NULL)
+, fPreferredCount(preferredSize)
+, fOwnerCount(IGNORE_OWNERS)
+, fBytesAllocated(0)
+, fDeferAddingOwners(false) {
+SkSafeRef(storage);
+}
+SkBitmapHeap::~SkBitmapHeap() {
+SkDEBUGCODE(
+for (int i = 0; i < fStorage.count(); i++) {
+bool unused = false;
+for (int j = 0; j < fUnusedSlots.count(); j++) {
+if (fUnusedSlots[j] == fStorage[i]->fSlot) {
+unused = true;
+break;
+}
+}
+if (!unused) {
+fBytesAllocated -= fStorage[i]->fBytesAllocated;
+}
+}
+fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
+)
+SkASSERT(0 == fBytesAllocated);
+fStorage.deleteAll();
+SkSafeUnref(fExternalStorage);
+fLookupTable.deleteAll();
+}
+SkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const {
+const int size = fStorage.count();
+SkTRefArray<SkBitmap>* array = NULL;
+if (size > 0) {
+array = SkTRefArray<SkBitmap>::Create(size);
+for (int i = 0; i < size; i++) {
+// make a shallow copy of the bitmap
+array->writableAt(i) = fStorage[i]->fBitmap;
+}
+}
+return array;
+}
+void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) {
+if (fMostRecentlyUsed == entry) {
+fMostRecentlyUsed = entry->fLessRecentlyUsed;
+if (NULL == fMostRecentlyUsed) {
+SkASSERT(fLeastRecentlyUsed == entry);
+fLeastRecentlyUsed = NULL;
+} else {
+fMostRecentlyUsed->fMoreRecentlyUsed = NULL;
+}
+} else {
+// Remove entry from its prior place, and make sure to cover the hole.
+if (fLeastRecentlyUsed == entry) {
+SkASSERT(entry->fMoreRecentlyUsed != NULL);
+fLeastRecentlyUsed = entry->fMoreRecentlyUsed;
+}
+// Since we have already considered the case where entry is the most recently used, it must
+// have a more recently used at this point.
+SkASSERT(entry->fMoreRecentlyUsed != NULL);
+entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed;
+if (entry->fLessRecentlyUsed != NULL) {
+SkASSERT(fLeastRecentlyUsed != entry);
+entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
+}
+}
+entry->fMoreRecentlyUsed = NULL;
+}
+void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) {
+if (fMostRecentlyUsed != NULL) {
+SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed);
+fMostRecentlyUsed->fMoreRecentlyUsed = entry;
+entry->fLessRecentlyUsed = fMostRecentlyUsed;
+}
+fMostRecentlyUsed = entry;
+if (NULL == fLeastRecentlyUsed) {
+fLeastRecentlyUsed = entry;
+}
+}
+// iterate through our LRU cache and try to find an entry to evict
+SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
+SkASSERT(fPreferredCount != UNLIMITED_SIZE);
+SkASSERT(fStorage.count() >= fPreferredCount);
+SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed;
+while (iter != NULL) {
+SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
+if (heapEntry->fRefCount > 0) {
+// If the least recently used bitmap has not been unreferenced
+// by its owner, then according to our LRU specifications a more
+// recently used one can not have used all its references yet either.
+return NULL;
+}
+if (replacement.getGenerationID() == iter->fGenerationId) {
+// Do not replace a bitmap with a new one using the same
+// pixel ref. Instead look for a different one that will
+// potentially free up more space.
+iter = iter->fMoreRecentlyUsed;
+} else {
+return iter;
+}
+}
+return NULL;
+}
+size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
+if (UNLIMITED_SIZE == fPreferredCount) {
+return 0;
+}
+LookupEntry* iter = fLeastRecentlyUsed;
+size_t origBytesAllocated = fBytesAllocated;
+// Purge starting from LRU until a non-evictable bitmap is found or until
+// everything is evicted.
+while (iter != NULL) {
+SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
+if (heapEntry->fRefCount > 0) {
+break;
+}
+LookupEntry* next = iter->fMoreRecentlyUsed;
+this->removeEntryFromLookupTable(iter);
+// Free the pixel memory. removeEntryFromLookupTable already reduced
+// fBytesAllocated properly.
+heapEntry->fBitmap.reset();
+// Add to list of unused slots which can be reused in the future.
+fUnusedSlots.push(heapEntry->fSlot);
+iter = next;
+if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
+break;
+}
+}
+if (fLeastRecentlyUsed != iter) {
+// There was at least one eviction.
+fLeastRecentlyUsed = iter;
+if (NULL == fLeastRecentlyUsed) {
+// Everything was evicted
+fMostRecentlyUsed = NULL;
+fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
+fStorage.deleteAll();
+fUnusedSlots.reset();
+SkASSERT(0 == fBytesAllocated);
+} else {
+fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
+}
+}
+return origBytesAllocated - fBytesAllocated;
+}
+int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
+int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
+(const LookupEntry**)fLookupTable.begin(),
+fLookupTable.count(),
+&indexEntry, sizeof(void*));
+if (index < 0) {
+// insert ourselves into the bitmapIndex
+index = ~index;
+*fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry));
+} else if (entry != NULL) {
+// populate the entry if needed
+*entry = fStorage[fLookupTable[index]->fStorageSlot];
+}
+return index;
+}
+bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
+SkASSERT(!fExternalStorage);
+// If the bitmap is mutable, we need to do a deep copy, since the
+// caller may modify it afterwards.
+if (originalBitmap.isImmutable()) {
+copiedBitmap = originalBitmap;
+// TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy
+//    else if (sharedPixelRef != NULL) {
+//        copiedBitmap = orig;
+//        copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset());
+} else if (originalBitmap.empty()) {
+copiedBitmap.reset();
+} else if (!originalBitmap.deepCopyTo(&copiedBitmap)) {
+return false;
+}
+copiedBitmap.setImmutable();
+return true;
+}
+int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) {
+// remove the bitmap index for the deleted entry
+SkDEBUGCODE(int count = fLookupTable.count();)
+int index = this->findInLookupTable(*entry, NULL);
+// Verify that findInLookupTable found an existing entry rather than adding
+// a new entry to the lookup table.
+SkASSERT(count == fLookupTable.count());
+fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated;
+SkDELETE(fLookupTable[index]);
+fLookupTable.remove(index);
+return index;
+}
+int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
+SkBitmapHeapEntry* entry = NULL;
+int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
+if (entry) {
+// Already had a copy of the bitmap in the heap.
+if (fOwnerCount != IGNORE_OWNERS) {
+if (fDeferAddingOwners) {
+*fDeferredEntries.append() = entry->fSlot;
+} else {
+entry->addReferences(fOwnerCount);
+}
+}
+if (fPreferredCount != UNLIMITED_SIZE) {
+LookupEntry* lookupEntry = fLookupTable[searchIndex];
+if (lookupEntry != fMostRecentlyUsed) {
+this->removeFromLRU(lookupEntry);
+this->appendToLRU(lookupEntry);
+}
+}
+return entry->fSlot;
+}
+// decide if we need to evict an existing heap entry or create a new one
+if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) {
+// iterate through our LRU cache and try to find an entry to evict
+LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap);
+if (lookupEntry != NULL) {
+// we found an entry to evict
+entry = fStorage[lookupEntry->fStorageSlot];
+// Remove it from the LRU. The new entry will be added to the LRU later.
+this->removeFromLRU(lookupEntry);
+int index = this->removeEntryFromLookupTable(lookupEntry);
+// update the current search index now that we have removed one
+if (index < searchIndex) {
+searchIndex--;
+}
+}
+}
+// if we didn't have an entry yet we need to create one
+if (!entry) {
+if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
+int slot;
+fUnusedSlots.pop(&slot);
+entry = fStorage[slot];
+} else {
+entry = SkNEW(SkBitmapHeapEntry);
+fStorage.append(1, &entry);
+entry->fSlot = fStorage.count() - 1;
+fBytesAllocated += sizeof(SkBitmapHeapEntry);
+}
+}
+// create a copy of the bitmap
+bool copySucceeded;
+if (fExternalStorage) {
+copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot);
+} else {
+copySucceeded = copyBitmap(originalBitmap, entry->fBitmap);
+}
+// if the copy failed then we must abort
+if (!copySucceeded) {
+// delete the index
+SkDELETE(fLookupTable[searchIndex]);
+fLookupTable.remove(searchIndex);
+// If entry is the last slot in storage, it is safe to delete it.
+if (fStorage.count() - 1 == entry->fSlot) {
+// free the slot
+fStorage.remove(entry->fSlot);
+fBytesAllocated -= sizeof(SkBitmapHeapEntry);
+SkDELETE(entry);
+} else {
+fUnusedSlots.push(entry->fSlot);
+}
+return INVALID_SLOT;
+}
+// update the index with the appropriate slot in the heap
+fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
+// compute the space taken by this entry
+// TODO if there is a shared pixel ref don't count it
+// If the SkBitmap does not share an SkPixelRef with an SkBitmap already
+// in the SharedHeap, also include the size of its pixels.
+entry->fBytesAllocated = originalBitmap.getSize();
+// add the bytes from this entry to the total count
+fBytesAllocated += entry->fBytesAllocated;
+if (fOwnerCount != IGNORE_OWNERS) {
+if (fDeferAddingOwners) {
+*fDeferredEntries.append() = entry->fSlot;
+} else {
+entry->addReferences(fOwnerCount);
+}
+}
+if (fPreferredCount != UNLIMITED_SIZE) {
+this->appendToLRU(fLookupTable[searchIndex]);
+}
+return entry->fSlot;
+}
+void SkBitmapHeap::deferAddingOwners() {
+fDeferAddingOwners = true;
+}
+void SkBitmapHeap::endAddingOwnersDeferral(bool add) {
+if (add) {
+for (int i = 0; i < fDeferredEntries.count(); i++) {
+SkASSERT(fOwnerCount != IGNORE_OWNERS);
+SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]);
+SkASSERT(heapEntry != NULL);
+heapEntry->addReferences(fOwnerCount);
+}
+}
+fDeferAddingOwners = false;
+fDeferredEntries.reset();
+}

The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkBitmapHeap.cpp

gfx/skia/trunk/src/core/SkBitmapHeap.cpp