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