1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkBitmapHeap.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,307 @@
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 +#ifndef SkBitmapHeap_DEFINED
1.12 +#define SkBitmapHeap_DEFINED
1.13 +
1.14 +#include "SkBitmap.h"
1.15 +#include "SkFlattenable.h"
1.16 +#include "SkRefCnt.h"
1.17 +#include "SkTDArray.h"
1.18 +#include "SkThread.h"
1.19 +#include "SkTRefArray.h"
1.20 +
1.21 +/**
1.22 + * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...
1.23 + * (1) get access a bitmap in the heap
1.24 + * (2) indicate they are done with bitmap by releasing their reference (if they were an owner).
1.25 + */
1.26 +class SkBitmapHeapEntry : SkNoncopyable {
1.27 +public:
1.28 + ~SkBitmapHeapEntry();
1.29 +
1.30 + int32_t getSlot() { return fSlot; }
1.31 +
1.32 + SkBitmap* getBitmap() { return &fBitmap; }
1.33 +
1.34 + void releaseRef() {
1.35 + sk_atomic_dec(&fRefCount);
1.36 + }
1.37 +
1.38 +private:
1.39 + SkBitmapHeapEntry();
1.40 +
1.41 + void addReferences(int count);
1.42 +
1.43 + int32_t fSlot;
1.44 + int32_t fRefCount;
1.45 +
1.46 + SkBitmap fBitmap;
1.47 + // Keep track of the bytes allocated for this bitmap. When replacing the
1.48 + // bitmap or removing this HeapEntry we know how much memory has been
1.49 + // reclaimed.
1.50 + size_t fBytesAllocated;
1.51 +
1.52 + friend class SkBitmapHeap;
1.53 + friend class SkBitmapHeapTester;
1.54 +};
1.55 +
1.56 +
1.57 +class SkBitmapHeapReader : public SkRefCnt {
1.58 +public:
1.59 + SK_DECLARE_INST_COUNT(SkBitmapHeapReader)
1.60 +
1.61 + SkBitmapHeapReader() : INHERITED() {}
1.62 + virtual SkBitmap* getBitmap(int32_t slot) const = 0;
1.63 + virtual void releaseRef(int32_t slot) = 0;
1.64 +private:
1.65 + typedef SkRefCnt INHERITED;
1.66 +};
1.67 +
1.68 +
1.69 +/**
1.70 + * TODO: stores immutable bitmaps into a heap
1.71 + */
1.72 +class SkBitmapHeap : public SkBitmapHeapReader {
1.73 +public:
1.74 + class ExternalStorage : public SkRefCnt {
1.75 + public:
1.76 + SK_DECLARE_INST_COUNT(ExternalStorage)
1.77 +
1.78 + virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;
1.79 +
1.80 + private:
1.81 + typedef SkRefCnt INHERITED;
1.82 + };
1.83 +
1.84 + static const int32_t UNLIMITED_SIZE = -1;
1.85 + static const int32_t IGNORE_OWNERS = -1;
1.86 + static const int32_t INVALID_SLOT = -1;
1.87 +
1.88 + /**
1.89 + * Constructs a heap that is responsible for allocating and managing its own storage. In the
1.90 + * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we
1.91 + * guarantee that once allocated in the heap a bitmap's index in the heap is immutable.
1.92 + * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.
1.93 + *
1.94 + * @param preferredSize Specifies the preferred maximum number of bitmaps to store. This is
1.95 + * not a hard limit as it can grow larger if the number of bitmaps in the heap with active
1.96 + * owners exceeds this limit.
1.97 + * @param ownerCount The number of owners to assign to each inserted bitmap. NOTE: while a
1.98 + * bitmap in the heap has a least one owner it can't be removed.
1.99 + */
1.100 + SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);
1.101 +
1.102 + /**
1.103 + * Constructs a heap that defers the responsibility of storing the bitmaps to an external
1.104 + * function. This is especially useful if the bitmaps will be used in a separate process as the
1.105 + * external storage can ensure the data is properly shuttled to the appropriate processes.
1.106 + *
1.107 + * Our LRU implementation assumes that inserts into the external storage are consumed in the
1.108 + * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the
1.109 + * external storage to see if a slot in the heap is eligible to be overwritten.
1.110 + *
1.111 + * @param externalStorage The class responsible for storing the bitmaps inserted into the heap
1.112 + * @param heapSize The maximum size of the heap. Because of the sequential limitation imposed
1.113 + * by our LRU implementation we can guarantee that the heap will never grow beyond this size.
1.114 + */
1.115 + SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);
1.116 +
1.117 + virtual ~SkBitmapHeap();
1.118 +
1.119 + /**
1.120 + * Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The
1.121 + * array indices match their position in the heap.
1.122 + *
1.123 + * @return a ptr to an array of bitmaps or NULL if external storage is being used.
1.124 + */
1.125 + SkTRefArray<SkBitmap>* extractBitmaps() const;
1.126 +
1.127 + /**
1.128 + * Retrieves the bitmap from the specified slot in the heap
1.129 + *
1.130 + * @return The bitmap located at that slot or NULL if external storage is being used.
1.131 + */
1.132 + virtual SkBitmap* getBitmap(int32_t slot) const SK_OVERRIDE {
1.133 + SkASSERT(fExternalStorage == NULL);
1.134 + SkBitmapHeapEntry* entry = getEntry(slot);
1.135 + if (entry) {
1.136 + return &entry->fBitmap;
1.137 + }
1.138 + return NULL;
1.139 + }
1.140 +
1.141 + /**
1.142 + * Retrieves the bitmap from the specified slot in the heap
1.143 + *
1.144 + * @return The bitmap located at that slot or NULL if external storage is being used.
1.145 + */
1.146 + virtual void releaseRef(int32_t slot) SK_OVERRIDE {
1.147 + SkASSERT(fExternalStorage == NULL);
1.148 + if (fOwnerCount != IGNORE_OWNERS) {
1.149 + SkBitmapHeapEntry* entry = getEntry(slot);
1.150 + if (entry) {
1.151 + entry->releaseRef();
1.152 + }
1.153 + }
1.154 + }
1.155 +
1.156 + /**
1.157 + * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable
1.158 + * and is not dependent on the lifecycle of the provided bitmap.
1.159 + *
1.160 + * @param bitmap the bitmap to be inserted into the heap
1.161 + * @return the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could
1.162 + * not be added to the heap. If it was added the slot will remain valid...
1.163 + * (1) indefinitely if no owner count has been specified.
1.164 + * (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*
1.165 + */
1.166 + int32_t insert(const SkBitmap& bitmap);
1.167 +
1.168 + /**
1.169 + * Retrieves an entry from the heap at a given slot.
1.170 + *
1.171 + * @param slot the slot in the heap where a bitmap was stored.
1.172 + * @return a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.
1.173 + */
1.174 + SkBitmapHeapEntry* getEntry(int32_t slot) const {
1.175 + SkASSERT(slot <= fStorage.count());
1.176 + if (fExternalStorage != NULL) {
1.177 + return NULL;
1.178 + }
1.179 + return fStorage[slot];
1.180 + }
1.181 +
1.182 + /**
1.183 + * Returns a count of the number of items currently in the heap
1.184 + */
1.185 + int count() const {
1.186 + SkASSERT(fExternalStorage != NULL ||
1.187 + fStorage.count() - fUnusedSlots.count() == fLookupTable.count());
1.188 + return fLookupTable.count();
1.189 + }
1.190 +
1.191 + /**
1.192 + * Returns the total number of bytes allocated by the bitmaps in the heap
1.193 + */
1.194 + size_t bytesAllocated() const {
1.195 + return fBytesAllocated;
1.196 + }
1.197 +
1.198 + /**
1.199 + * Attempt to reduce the storage allocated.
1.200 + * @param bytesToFree minimum number of bytes that should be attempted to
1.201 + * be freed.
1.202 + * @return number of bytes actually freed.
1.203 + */
1.204 + size_t freeMemoryIfPossible(size_t bytesToFree);
1.205 +
1.206 + /**
1.207 + * Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an
1.208 + * existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will
1.209 + * not have addReferences called on it, and the client does not need to make a corresponding
1.210 + * call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not
1.211 + * equal to IGNORE_OWNERS.
1.212 + */
1.213 + void deferAddingOwners();
1.214 +
1.215 + /**
1.216 + * Resume adding references when duplicate SkBitmaps are inserted.
1.217 + * @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted
1.218 + * while deferring.
1.219 + */
1.220 + void endAddingOwnersDeferral(bool add);
1.221 +
1.222 +private:
1.223 + struct LookupEntry {
1.224 + LookupEntry(const SkBitmap& bm)
1.225 + : fGenerationId(bm.getGenerationID())
1.226 + , fPixelOrigin(bm.pixelRefOrigin())
1.227 + , fWidth(bm.width())
1.228 + , fHeight(bm.height())
1.229 + , fMoreRecentlyUsed(NULL)
1.230 + , fLessRecentlyUsed(NULL){}
1.231 +
1.232 + const uint32_t fGenerationId; // SkPixelRef GenerationID.
1.233 + const SkIPoint fPixelOrigin;
1.234 + const uint32_t fWidth;
1.235 + const uint32_t fHeight;
1.236 +
1.237 + // TODO: Generalize the LRU caching mechanism
1.238 + LookupEntry* fMoreRecentlyUsed;
1.239 + LookupEntry* fLessRecentlyUsed;
1.240 +
1.241 + uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
1.242 +
1.243 + /**
1.244 + * Compare two LookupEntry pointers for sorting and searching.
1.245 + */
1.246 + static bool Less(const LookupEntry& a, const LookupEntry& b);
1.247 + };
1.248 +
1.249 + /**
1.250 + * Remove the entry from the lookup table. Also deletes the entry pointed
1.251 + * to by the table. Therefore, if a pointer to that one was passed in, the
1.252 + * pointer should no longer be used, since the object to which it points has
1.253 + * been deleted.
1.254 + * @return The index in the lookup table of the entry before removal.
1.255 + */
1.256 + int removeEntryFromLookupTable(LookupEntry*);
1.257 +
1.258 + /**
1.259 + * Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
1.260 + * If the bitmap was not already in the table it is added.
1.261 + *
1.262 + * @param key The key to search the lookup table, created from a bitmap.
1.263 + * @param entry A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
1.264 + * in the lookup table is populated with the entry from the heap storage.
1.265 + */
1.266 + int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry);
1.267 +
1.268 + LookupEntry* findEntryToReplace(const SkBitmap& replacement);
1.269 + bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
1.270 +
1.271 + /**
1.272 + * Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most
1.273 + * recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed
1.274 + * (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves
1.275 + * its fLessRecentlyUsed unmodified.
1.276 + */
1.277 + void removeFromLRU(LookupEntry* entry);
1.278 +
1.279 + /**
1.280 + * Append a LookupEntry to the end of the LRU cache, marking it as the most
1.281 + * recently used. Assumes that the LookupEntry is already in fLookupTable,
1.282 + * but is not in the LRU cache. If it is in the cache, removeFromLRU should
1.283 + * be called first.
1.284 + */
1.285 + void appendToLRU(LookupEntry*);
1.286 +
1.287 + // searchable index that maps to entries in the heap
1.288 + SkTDArray<LookupEntry*> fLookupTable;
1.289 +
1.290 + // heap storage
1.291 + SkTDArray<SkBitmapHeapEntry*> fStorage;
1.292 + // Used to mark slots in fStorage as deleted without actually deleting
1.293 + // the slot so as not to mess up the numbering.
1.294 + SkTDArray<int> fUnusedSlots;
1.295 + ExternalStorage* fExternalStorage;
1.296 +
1.297 + LookupEntry* fMostRecentlyUsed;
1.298 + LookupEntry* fLeastRecentlyUsed;
1.299 +
1.300 + const int32_t fPreferredCount;
1.301 + const int32_t fOwnerCount;
1.302 + size_t fBytesAllocated;
1.303 +
1.304 + bool fDeferAddingOwners;
1.305 + SkTDArray<int> fDeferredEntries;
1.306 +
1.307 + typedef SkBitmapHeapReader INHERITED;
1.308 +};
1.309 +
1.310 +#endif // SkBitmapHeap_DEFINED
