reed | fb8c1fc | 2015-08-04 18:44:56 -0700 | [diff] [blame] | 1 | |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 2 | /* |
| 3 | * Copyright 2012 Google Inc. |
| 4 | * |
| 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
| 7 | */ |
| 8 | #ifndef SkBitmapHeap_DEFINED |
| 9 | #define SkBitmapHeap_DEFINED |
| 10 | |
| 11 | #include "SkBitmap.h" |
reed | fb8c1fc | 2015-08-04 18:44:56 -0700 | [diff] [blame] | 12 | #include "SkFlattenable.h" |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 13 | #include "SkRefCnt.h" |
| 14 | #include "SkTDArray.h" |
reed | fb8c1fc | 2015-08-04 18:44:56 -0700 | [diff] [blame] | 15 | #include "SkAtomics.h" |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 16 | |
| 17 | /** |
| 18 | * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to... |
| 19 | * (1) get access a bitmap in the heap |
| 20 | * (2) indicate they are done with bitmap by releasing their reference (if they were an owner). |
| 21 | */ |
| 22 | class SkBitmapHeapEntry : SkNoncopyable { |
| 23 | public: |
| 24 | ~SkBitmapHeapEntry(); |
| 25 | |
| 26 | int32_t getSlot() { return fSlot; } |
| 27 | |
| 28 | SkBitmap* getBitmap() { return &fBitmap; } |
| 29 | |
| 30 | void releaseRef() { |
| 31 | sk_atomic_dec(&fRefCount); |
| 32 | } |
| 33 | |
| 34 | private: |
| 35 | SkBitmapHeapEntry(); |
| 36 | |
| 37 | void addReferences(int count); |
| 38 | |
| 39 | int32_t fSlot; |
| 40 | int32_t fRefCount; |
| 41 | |
| 42 | SkBitmap fBitmap; |
| 43 | // Keep track of the bytes allocated for this bitmap. When replacing the |
| 44 | // bitmap or removing this HeapEntry we know how much memory has been |
| 45 | // reclaimed. |
| 46 | size_t fBytesAllocated; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 47 | |
| 48 | friend class SkBitmapHeap; |
scroggo@google.com | 013c5d9 | 2012-11-16 20:34:37 +0000 | [diff] [blame] | 49 | friend class SkBitmapHeapTester; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 50 | }; |
| 51 | |
| 52 | |
| 53 | class SkBitmapHeapReader : public SkRefCnt { |
| 54 | public: |
mtklein | 1b24933 | 2015-07-07 12:21:21 -0700 | [diff] [blame] | 55 | |
robertphillips@google.com | a22e211 | 2012-08-16 14:58:06 +0000 | [diff] [blame] | 56 | |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 57 | SkBitmapHeapReader() : INHERITED() {} |
| 58 | virtual SkBitmap* getBitmap(int32_t slot) const = 0; |
| 59 | virtual void releaseRef(int32_t slot) = 0; |
| 60 | private: |
| 61 | typedef SkRefCnt INHERITED; |
| 62 | }; |
| 63 | |
| 64 | |
| 65 | /** |
| 66 | * TODO: stores immutable bitmaps into a heap |
| 67 | */ |
| 68 | class SkBitmapHeap : public SkBitmapHeapReader { |
| 69 | public: |
| 70 | class ExternalStorage : public SkRefCnt { |
| 71 | public: |
mtklein | 1b24933 | 2015-07-07 12:21:21 -0700 | [diff] [blame] | 72 | |
robertphillips@google.com | a22e211 | 2012-08-16 14:58:06 +0000 | [diff] [blame] | 73 | |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 74 | virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0; |
robertphillips@google.com | a22e211 | 2012-08-16 14:58:06 +0000 | [diff] [blame] | 75 | |
| 76 | private: |
| 77 | typedef SkRefCnt INHERITED; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 78 | }; |
| 79 | |
| 80 | static const int32_t UNLIMITED_SIZE = -1; |
| 81 | static const int32_t IGNORE_OWNERS = -1; |
| 82 | static const int32_t INVALID_SLOT = -1; |
| 83 | |
| 84 | /** |
| 85 | * Constructs a heap that is responsible for allocating and managing its own storage. In the |
| 86 | * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we |
| 87 | * guarantee that once allocated in the heap a bitmap's index in the heap is immutable. |
| 88 | * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero. |
| 89 | * |
| 90 | * @param preferredSize Specifies the preferred maximum number of bitmaps to store. This is |
| 91 | * not a hard limit as it can grow larger if the number of bitmaps in the heap with active |
| 92 | * owners exceeds this limit. |
| 93 | * @param ownerCount The number of owners to assign to each inserted bitmap. NOTE: while a |
| 94 | * bitmap in the heap has a least one owner it can't be removed. |
| 95 | */ |
| 96 | SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS); |
| 97 | |
| 98 | /** |
| 99 | * Constructs a heap that defers the responsibility of storing the bitmaps to an external |
| 100 | * function. This is especially useful if the bitmaps will be used in a separate process as the |
| 101 | * external storage can ensure the data is properly shuttled to the appropriate processes. |
| 102 | * |
| 103 | * Our LRU implementation assumes that inserts into the external storage are consumed in the |
| 104 | * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the |
| 105 | * external storage to see if a slot in the heap is eligible to be overwritten. |
| 106 | * |
| 107 | * @param externalStorage The class responsible for storing the bitmaps inserted into the heap |
| 108 | * @param heapSize The maximum size of the heap. Because of the sequential limitation imposed |
| 109 | * by our LRU implementation we can guarantee that the heap will never grow beyond this size. |
| 110 | */ |
| 111 | SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE); |
| 112 | |
commit-bot@chromium.org | d7e0fbe | 2014-03-10 16:41:00 +0000 | [diff] [blame] | 113 | virtual ~SkBitmapHeap(); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 114 | |
| 115 | /** |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 116 | * Retrieves the bitmap from the specified slot in the heap |
| 117 | * |
| 118 | * @return The bitmap located at that slot or NULL if external storage is being used. |
| 119 | */ |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 120 | SkBitmap* getBitmap(int32_t slot) const override { |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 121 | SkASSERT(fExternalStorage == NULL); |
| 122 | SkBitmapHeapEntry* entry = getEntry(slot); |
| 123 | if (entry) { |
| 124 | return &entry->fBitmap; |
| 125 | } |
| 126 | return NULL; |
| 127 | } |
| 128 | |
| 129 | /** |
| 130 | * Retrieves the bitmap from the specified slot in the heap |
| 131 | * |
| 132 | * @return The bitmap located at that slot or NULL if external storage is being used. |
| 133 | */ |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame] | 134 | void releaseRef(int32_t slot) override { |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 135 | SkASSERT(fExternalStorage == NULL); |
| 136 | if (fOwnerCount != IGNORE_OWNERS) { |
| 137 | SkBitmapHeapEntry* entry = getEntry(slot); |
| 138 | if (entry) { |
| 139 | entry->releaseRef(); |
| 140 | } |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | /** |
| 145 | * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable |
| 146 | * and is not dependent on the lifecycle of the provided bitmap. |
| 147 | * |
| 148 | * @param bitmap the bitmap to be inserted into the heap |
| 149 | * @return the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could |
| 150 | * not be added to the heap. If it was added the slot will remain valid... |
| 151 | * (1) indefinitely if no owner count has been specified. |
| 152 | * (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry* |
| 153 | */ |
| 154 | int32_t insert(const SkBitmap& bitmap); |
| 155 | |
| 156 | /** |
| 157 | * Retrieves an entry from the heap at a given slot. |
| 158 | * |
| 159 | * @param slot the slot in the heap where a bitmap was stored. |
| 160 | * @return a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used. |
| 161 | */ |
| 162 | SkBitmapHeapEntry* getEntry(int32_t slot) const { |
| 163 | SkASSERT(slot <= fStorage.count()); |
| 164 | if (fExternalStorage != NULL) { |
| 165 | return NULL; |
| 166 | } |
| 167 | return fStorage[slot]; |
| 168 | } |
| 169 | |
| 170 | /** |
| 171 | * Returns a count of the number of items currently in the heap |
| 172 | */ |
| 173 | int count() const { |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 174 | SkASSERT(fExternalStorage != NULL || |
| 175 | fStorage.count() - fUnusedSlots.count() == fLookupTable.count()); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 176 | return fLookupTable.count(); |
| 177 | } |
| 178 | |
| 179 | /** |
| 180 | * Returns the total number of bytes allocated by the bitmaps in the heap |
| 181 | */ |
| 182 | size_t bytesAllocated() const { |
| 183 | return fBytesAllocated; |
| 184 | } |
| 185 | |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 186 | /** |
| 187 | * Attempt to reduce the storage allocated. |
| 188 | * @param bytesToFree minimum number of bytes that should be attempted to |
| 189 | * be freed. |
| 190 | * @return number of bytes actually freed. |
| 191 | */ |
| 192 | size_t freeMemoryIfPossible(size_t bytesToFree); |
| 193 | |
scroggo@google.com | 7ca2443 | 2012-08-14 15:48:43 +0000 | [diff] [blame] | 194 | /** |
| 195 | * Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an |
| 196 | * existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will |
| 197 | * not have addReferences called on it, and the client does not need to make a corresponding |
| 198 | * call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not |
| 199 | * equal to IGNORE_OWNERS. |
| 200 | */ |
| 201 | void deferAddingOwners(); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 202 | |
scroggo@google.com | 7ca2443 | 2012-08-14 15:48:43 +0000 | [diff] [blame] | 203 | /** |
| 204 | * Resume adding references when duplicate SkBitmaps are inserted. |
| 205 | * @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted |
| 206 | * while deferring. |
| 207 | */ |
| 208 | void endAddingOwnersDeferral(bool add); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 209 | |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 210 | private: |
| 211 | struct LookupEntry { |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 212 | LookupEntry(const SkBitmap& bm) |
| 213 | : fGenerationId(bm.getGenerationID()) |
reed@google.com | 672588b | 2014-01-08 15:42:01 +0000 | [diff] [blame] | 214 | , fPixelOrigin(bm.pixelRefOrigin()) |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 215 | , fWidth(bm.width()) |
| 216 | , fHeight(bm.height()) |
| 217 | , fMoreRecentlyUsed(NULL) |
| 218 | , fLessRecentlyUsed(NULL){} |
| 219 | |
| 220 | const uint32_t fGenerationId; // SkPixelRef GenerationID. |
reed@google.com | 672588b | 2014-01-08 15:42:01 +0000 | [diff] [blame] | 221 | const SkIPoint fPixelOrigin; |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 222 | const uint32_t fWidth; |
| 223 | const uint32_t fHeight; |
| 224 | |
| 225 | // TODO: Generalize the LRU caching mechanism |
| 226 | LookupEntry* fMoreRecentlyUsed; |
| 227 | LookupEntry* fLessRecentlyUsed; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 228 | |
| 229 | uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage. |
| 230 | |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 231 | /** |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 232 | * Compare two LookupEntry pointers for sorting and searching. |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 233 | */ |
bsalomon@google.com | 20f7f17 | 2013-05-17 19:05:03 +0000 | [diff] [blame] | 234 | static bool Less(const LookupEntry& a, const LookupEntry& b); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 235 | }; |
| 236 | |
| 237 | /** |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 238 | * Remove the entry from the lookup table. Also deletes the entry pointed |
| 239 | * to by the table. Therefore, if a pointer to that one was passed in, the |
| 240 | * pointer should no longer be used, since the object to which it points has |
| 241 | * been deleted. |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 242 | * @return The index in the lookup table of the entry before removal. |
| 243 | */ |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 244 | int removeEntryFromLookupTable(LookupEntry*); |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 245 | |
| 246 | /** |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 247 | * Searches for the bitmap in the lookup table and returns the bitmaps index within the table. |
| 248 | * If the bitmap was not already in the table it is added. |
| 249 | * |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 250 | * @param key The key to search the lookup table, created from a bitmap. |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 251 | * @param entry A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found |
| 252 | * in the lookup table is populated with the entry from the heap storage. |
| 253 | */ |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 254 | int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 255 | |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 256 | LookupEntry* findEntryToReplace(const SkBitmap& replacement); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 257 | bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap); |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 258 | |
| 259 | /** |
| 260 | * Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most |
| 261 | * recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed |
| 262 | * (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves |
| 263 | * its fLessRecentlyUsed unmodified. |
| 264 | */ |
| 265 | void removeFromLRU(LookupEntry* entry); |
| 266 | |
| 267 | /** |
| 268 | * Append a LookupEntry to the end of the LRU cache, marking it as the most |
| 269 | * recently used. Assumes that the LookupEntry is already in fLookupTable, |
| 270 | * but is not in the LRU cache. If it is in the cache, removeFromLRU should |
| 271 | * be called first. |
| 272 | */ |
| 273 | void appendToLRU(LookupEntry*); |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 274 | |
| 275 | // searchable index that maps to entries in the heap |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 276 | SkTDArray<LookupEntry*> fLookupTable; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 277 | |
| 278 | // heap storage |
| 279 | SkTDArray<SkBitmapHeapEntry*> fStorage; |
scroggo@google.com | 10dccde | 2012-08-08 20:43:22 +0000 | [diff] [blame] | 280 | // Used to mark slots in fStorage as deleted without actually deleting |
| 281 | // the slot so as not to mess up the numbering. |
| 282 | SkTDArray<int> fUnusedSlots; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 283 | ExternalStorage* fExternalStorage; |
| 284 | |
scroggo@google.com | 3e26bd0 | 2012-08-14 15:20:01 +0000 | [diff] [blame] | 285 | LookupEntry* fMostRecentlyUsed; |
| 286 | LookupEntry* fLeastRecentlyUsed; |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 287 | |
| 288 | const int32_t fPreferredCount; |
| 289 | const int32_t fOwnerCount; |
| 290 | size_t fBytesAllocated; |
| 291 | |
scroggo@google.com | 7ca2443 | 2012-08-14 15:48:43 +0000 | [diff] [blame] | 292 | bool fDeferAddingOwners; |
| 293 | SkTDArray<int> fDeferredEntries; |
| 294 | |
djsollen@google.com | 21830d9 | 2012-08-07 19:49:41 +0000 | [diff] [blame] | 295 | typedef SkBitmapHeapReader INHERITED; |
| 296 | }; |
| 297 | |
| 298 | #endif // SkBitmapHeap_DEFINED |