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

--1:000000000000
+:0dce4544f92b
+/*
+* Copyright 2012 Google Inc.
+*
+* Use of this source code is governed by a BSD-style license that can be
+* found in the LICENSE file.
+*/
+#ifndef SkBitmapHeap_DEFINED
+#define SkBitmapHeap_DEFINED
+#include "SkBitmap.h"
+#include "SkFlattenable.h"
+#include "SkRefCnt.h"
+#include "SkTDArray.h"
+#include "SkThread.h"
+#include "SkTRefArray.h"
+/**
+* SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...
+*  (1) get access a bitmap in the heap
+*  (2) indicate they are done with bitmap by releasing their reference (if they were an owner).
+*/
+class SkBitmapHeapEntry : SkNoncopyable {
+public:
+~SkBitmapHeapEntry();
+int32_t getSlot() { return fSlot; }
+SkBitmap* getBitmap() { return &fBitmap; }
+void releaseRef() {
+sk_atomic_dec(&fRefCount);
+}
+private:
+SkBitmapHeapEntry();
+void addReferences(int count);
+int32_t fSlot;
+int32_t fRefCount;
+SkBitmap fBitmap;
+// Keep track of the bytes allocated for this bitmap. When replacing the
+// bitmap or removing this HeapEntry we know how much memory has been
+// reclaimed.
+size_t fBytesAllocated;
+friend class SkBitmapHeap;
+friend class SkBitmapHeapTester;
+};
+class SkBitmapHeapReader : public SkRefCnt {
+public:
+SK_DECLARE_INST_COUNT(SkBitmapHeapReader)
+SkBitmapHeapReader() : INHERITED() {}
+virtual SkBitmap* getBitmap(int32_t slot) const = 0;
+virtual void releaseRef(int32_t slot) = 0;
+private:
+typedef SkRefCnt INHERITED;
+};
+/**
+* TODO: stores immutable bitmaps into a heap
+*/
+class SkBitmapHeap : public SkBitmapHeapReader {
+public:
+class ExternalStorage : public SkRefCnt {
+public:
+SK_DECLARE_INST_COUNT(ExternalStorage)
+virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;
+private:
+typedef SkRefCnt INHERITED;
+};
+static const int32_t UNLIMITED_SIZE = -1;
+static const int32_t IGNORE_OWNERS  = -1;
+static const int32_t INVALID_SLOT   = -1;
+/**
+* Constructs a heap that is responsible for allocating and managing its own storage.  In the
+* case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we
+* guarantee that once allocated in the heap a bitmap's index in the heap is immutable.
+* Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.
+*
+* @param preferredSize  Specifies the preferred maximum number of bitmaps to store. This is
+*   not a hard limit as it can grow larger if the number of bitmaps in the heap with active
+*   owners exceeds this limit.
+* @param ownerCount  The number of owners to assign to each inserted bitmap. NOTE: while a
+*   bitmap in the heap has a least one owner it can't be removed.
+*/
+SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);
+/**
+* Constructs a heap that defers the responsibility of storing the bitmaps to an external
+* function. This is especially useful if the bitmaps will be used in a separate process as the
+* external storage can ensure the data is properly shuttled to the appropriate processes.
+*
+* Our LRU implementation assumes that inserts into the external storage are consumed in the
+* order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the
+* external storage to see if a slot in the heap is eligible to be overwritten.
+*
+* @param externalStorage  The class responsible for storing the bitmaps inserted into the heap
+* @param heapSize  The maximum size of the heap. Because of the sequential limitation imposed
+*   by our LRU implementation we can guarantee that the heap will never grow beyond this size.
+*/
+SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);
+virtual ~SkBitmapHeap();
+/**
+* Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The
+* array indices match their position in the heap.
+*
+* @return  a ptr to an array of bitmaps or NULL if external storage is being used.
+*/
+SkTRefArray<SkBitmap>* extractBitmaps() const;
+/**
+* Retrieves the bitmap from the specified slot in the heap
+*
+* @return  The bitmap located at that slot or NULL if external storage is being used.
+*/
+virtual SkBitmap* getBitmap(int32_t slot) const SK_OVERRIDE {
+SkASSERT(fExternalStorage == NULL);
+SkBitmapHeapEntry* entry = getEntry(slot);
+if (entry) {
+return &entry->fBitmap;
+}
+return NULL;
+}
+/**
+* Retrieves the bitmap from the specified slot in the heap
+*
+* @return  The bitmap located at that slot or NULL if external storage is being used.
+*/
+virtual void releaseRef(int32_t slot) SK_OVERRIDE {
+SkASSERT(fExternalStorage == NULL);
+if (fOwnerCount != IGNORE_OWNERS) {
+SkBitmapHeapEntry* entry = getEntry(slot);
+if (entry) {
+entry->releaseRef();
+}
+}
+}
+/**
+* Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable
+* and is not dependent on the lifecycle of the provided bitmap.
+*
+* @param bitmap  the bitmap to be inserted into the heap
+* @return  the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could
+*          not be added to the heap. If it was added the slot will remain valid...
+*            (1) indefinitely if no owner count has been specified.
+*            (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*
+*/
+int32_t insert(const SkBitmap& bitmap);
+/**
+* Retrieves an entry from the heap at a given slot.
+*
+* @param slot  the slot in the heap where a bitmap was stored.
+* @return  a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.
+*/
+SkBitmapHeapEntry* getEntry(int32_t slot) const {
+SkASSERT(slot <= fStorage.count());
+if (fExternalStorage != NULL) {
+return NULL;
+}
+return fStorage[slot];
+}
+/**
+* Returns a count of the number of items currently in the heap
+*/
+int count() const {
+SkASSERT(fExternalStorage != NULL ||
+fStorage.count() - fUnusedSlots.count() == fLookupTable.count());
+return fLookupTable.count();
+}
+/**
+* Returns the total number of bytes allocated by the bitmaps in the heap
+*/
+size_t bytesAllocated() const {
+return fBytesAllocated;
+}
+/**
+* Attempt to reduce the storage allocated.
+* @param bytesToFree minimum number of bytes that should be attempted to
+*   be freed.
+* @return number of bytes actually freed.
+*/
+size_t freeMemoryIfPossible(size_t bytesToFree);
+/**
+* Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an
+* existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will
+* not have addReferences called on it, and the client does not need to make a corresponding
+* call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not
+* equal to IGNORE_OWNERS.
+*/
+void deferAddingOwners();
+/**
+* Resume adding references when duplicate SkBitmaps are inserted.
+* @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted
+*            while deferring.
+*/
+void endAddingOwnersDeferral(bool add);
+private:
+struct LookupEntry {
+LookupEntry(const SkBitmap& bm)
+: fGenerationId(bm.getGenerationID())
+, fPixelOrigin(bm.pixelRefOrigin())
+, fWidth(bm.width())
+, fHeight(bm.height())
+, fMoreRecentlyUsed(NULL)
+, fLessRecentlyUsed(NULL){}
+const uint32_t fGenerationId; // SkPixelRef GenerationID.
+const SkIPoint fPixelOrigin;
+const uint32_t fWidth;
+const uint32_t fHeight;
+// TODO: Generalize the LRU caching mechanism
+LookupEntry* fMoreRecentlyUsed;
+LookupEntry* fLessRecentlyUsed;
+uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
+/**
+* Compare two LookupEntry pointers for sorting and searching.
+*/
+static bool Less(const LookupEntry& a, const LookupEntry& b);
+};
+/**
+* Remove the entry from the lookup table. Also deletes the entry pointed
+* to by the table. Therefore, if a pointer to that one was passed in, the
+* pointer should no longer be used, since the object to which it points has
+* been deleted.
+* @return The index in the lookup table of the entry before removal.
+*/
+int removeEntryFromLookupTable(LookupEntry*);
+/**
+* Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
+* If the bitmap was not already in the table it is added.
+*
+* @param key    The key to search the lookup table, created from a bitmap.
+* @param entry  A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
+*               in the lookup table is populated with the entry from the heap storage.
+*/
+int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry);
+LookupEntry* findEntryToReplace(const SkBitmap& replacement);
+bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
+/**
+* Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most
+* recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed
+* (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves
+* its fLessRecentlyUsed unmodified.
+*/
+void removeFromLRU(LookupEntry* entry);
+/**
+* Append a LookupEntry to the end of the LRU cache, marking it as the most
+* recently used. Assumes that the LookupEntry is already in fLookupTable,
+* but is not in the LRU cache. If it is in the cache, removeFromLRU should
+* be called first.
+*/
+void appendToLRU(LookupEntry*);
+// searchable index that maps to entries in the heap
+SkTDArray<LookupEntry*> fLookupTable;
+// heap storage
+SkTDArray<SkBitmapHeapEntry*> fStorage;
+// Used to mark slots in fStorage as deleted without actually deleting
+// the slot so as not to mess up the numbering.
+SkTDArray<int> fUnusedSlots;
+ExternalStorage* fExternalStorage;
+LookupEntry* fMostRecentlyUsed;
+LookupEntry* fLeastRecentlyUsed;
+const int32_t fPreferredCount;
+const int32_t fOwnerCount;
+size_t fBytesAllocated;
+bool fDeferAddingOwners;
+SkTDArray<int> fDeferredEntries;
+typedef SkBitmapHeapReader INHERITED;
+};
+#endif // SkBitmapHeap_DEFINED

The Tor Browser / file comparison

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

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