OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #include "SkBitmapHeap.h" | 9 #include "SkBitmapHeap.h" |
10 #include "SkBitmap.h" | 10 #include "SkBitmap.h" |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
58 } else if (a.fHeight < b.fHeight) { | 58 } else if (a.fHeight < b.fHeight) { |
59 return true; | 59 return true; |
60 } | 60 } |
61 return false; | 61 return false; |
62 } | 62 } |
63 | 63 |
64 /////////////////////////////////////////////////////////////////////////////// | 64 /////////////////////////////////////////////////////////////////////////////// |
65 | 65 |
66 SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount) | 66 SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount) |
67 : INHERITED() | 67 : INHERITED() |
68 , fExternalStorage(NULL) | 68 , fExternalStorage(nullptr) |
69 , fMostRecentlyUsed(NULL) | 69 , fMostRecentlyUsed(nullptr) |
70 , fLeastRecentlyUsed(NULL) | 70 , fLeastRecentlyUsed(nullptr) |
71 , fPreferredCount(preferredSize) | 71 , fPreferredCount(preferredSize) |
72 , fOwnerCount(ownerCount) | 72 , fOwnerCount(ownerCount) |
73 , fBytesAllocated(0) | 73 , fBytesAllocated(0) |
74 , fDeferAddingOwners(false) { | 74 , fDeferAddingOwners(false) { |
75 } | 75 } |
76 | 76 |
77 SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize) | 77 SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize) |
78 : INHERITED() | 78 : INHERITED() |
79 , fExternalStorage(storage) | 79 , fExternalStorage(storage) |
80 , fMostRecentlyUsed(NULL) | 80 , fMostRecentlyUsed(nullptr) |
81 , fLeastRecentlyUsed(NULL) | 81 , fLeastRecentlyUsed(nullptr) |
82 , fPreferredCount(preferredSize) | 82 , fPreferredCount(preferredSize) |
83 , fOwnerCount(IGNORE_OWNERS) | 83 , fOwnerCount(IGNORE_OWNERS) |
84 , fBytesAllocated(0) | 84 , fBytesAllocated(0) |
85 , fDeferAddingOwners(false) { | 85 , fDeferAddingOwners(false) { |
86 SkSafeRef(storage); | 86 SkSafeRef(storage); |
87 } | 87 } |
88 | 88 |
89 SkBitmapHeap::~SkBitmapHeap() { | 89 SkBitmapHeap::~SkBitmapHeap() { |
90 SkDEBUGCODE( | 90 SkDEBUGCODE( |
91 for (int i = 0; i < fStorage.count(); i++) { | 91 for (int i = 0; i < fStorage.count(); i++) { |
(...skipping 12 matching lines...) Expand all Loading... |
104 ) | 104 ) |
105 SkASSERT(0 == fBytesAllocated); | 105 SkASSERT(0 == fBytesAllocated); |
106 fStorage.deleteAll(); | 106 fStorage.deleteAll(); |
107 SkSafeUnref(fExternalStorage); | 107 SkSafeUnref(fExternalStorage); |
108 fLookupTable.deleteAll(); | 108 fLookupTable.deleteAll(); |
109 } | 109 } |
110 | 110 |
111 void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) { | 111 void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) { |
112 if (fMostRecentlyUsed == entry) { | 112 if (fMostRecentlyUsed == entry) { |
113 fMostRecentlyUsed = entry->fLessRecentlyUsed; | 113 fMostRecentlyUsed = entry->fLessRecentlyUsed; |
114 if (NULL == fMostRecentlyUsed) { | 114 if (nullptr == fMostRecentlyUsed) { |
115 SkASSERT(fLeastRecentlyUsed == entry); | 115 SkASSERT(fLeastRecentlyUsed == entry); |
116 fLeastRecentlyUsed = NULL; | 116 fLeastRecentlyUsed = nullptr; |
117 } else { | 117 } else { |
118 fMostRecentlyUsed->fMoreRecentlyUsed = NULL; | 118 fMostRecentlyUsed->fMoreRecentlyUsed = nullptr; |
119 } | 119 } |
120 } else { | 120 } else { |
121 // Remove entry from its prior place, and make sure to cover the hole. | 121 // Remove entry from its prior place, and make sure to cover the hole. |
122 if (fLeastRecentlyUsed == entry) { | 122 if (fLeastRecentlyUsed == entry) { |
123 SkASSERT(entry->fMoreRecentlyUsed != NULL); | 123 SkASSERT(entry->fMoreRecentlyUsed != nullptr); |
124 fLeastRecentlyUsed = entry->fMoreRecentlyUsed; | 124 fLeastRecentlyUsed = entry->fMoreRecentlyUsed; |
125 } | 125 } |
126 // Since we have already considered the case where entry is the most rec
ently used, it must | 126 // Since we have already considered the case where entry is the most rec
ently used, it must |
127 // have a more recently used at this point. | 127 // have a more recently used at this point. |
128 SkASSERT(entry->fMoreRecentlyUsed != NULL); | 128 SkASSERT(entry->fMoreRecentlyUsed != nullptr); |
129 entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed; | 129 entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed; |
130 | 130 |
131 if (entry->fLessRecentlyUsed != NULL) { | 131 if (entry->fLessRecentlyUsed != nullptr) { |
132 SkASSERT(fLeastRecentlyUsed != entry); | 132 SkASSERT(fLeastRecentlyUsed != entry); |
133 entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUs
ed; | 133 entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUs
ed; |
134 } | 134 } |
135 } | 135 } |
136 entry->fMoreRecentlyUsed = NULL; | 136 entry->fMoreRecentlyUsed = nullptr; |
137 } | 137 } |
138 | 138 |
139 void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) { | 139 void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) { |
140 if (fMostRecentlyUsed != NULL) { | 140 if (fMostRecentlyUsed != nullptr) { |
141 SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed); | 141 SkASSERT(nullptr == fMostRecentlyUsed->fMoreRecentlyUsed); |
142 fMostRecentlyUsed->fMoreRecentlyUsed = entry; | 142 fMostRecentlyUsed->fMoreRecentlyUsed = entry; |
143 entry->fLessRecentlyUsed = fMostRecentlyUsed; | 143 entry->fLessRecentlyUsed = fMostRecentlyUsed; |
144 } | 144 } |
145 fMostRecentlyUsed = entry; | 145 fMostRecentlyUsed = entry; |
146 if (NULL == fLeastRecentlyUsed) { | 146 if (nullptr == fLeastRecentlyUsed) { |
147 fLeastRecentlyUsed = entry; | 147 fLeastRecentlyUsed = entry; |
148 } | 148 } |
149 } | 149 } |
150 | 150 |
151 // iterate through our LRU cache and try to find an entry to evict | 151 // iterate through our LRU cache and try to find an entry to evict |
152 SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& repl
acement) { | 152 SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& repl
acement) { |
153 SkASSERT(fPreferredCount != UNLIMITED_SIZE); | 153 SkASSERT(fPreferredCount != UNLIMITED_SIZE); |
154 SkASSERT(fStorage.count() >= fPreferredCount); | 154 SkASSERT(fStorage.count() >= fPreferredCount); |
155 | 155 |
156 SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed; | 156 SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed; |
157 while (iter != NULL) { | 157 while (iter != nullptr) { |
158 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; | 158 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; |
159 if (heapEntry->fRefCount > 0) { | 159 if (heapEntry->fRefCount > 0) { |
160 // If the least recently used bitmap has not been unreferenced | 160 // If the least recently used bitmap has not been unreferenced |
161 // by its owner, then according to our LRU specifications a more | 161 // by its owner, then according to our LRU specifications a more |
162 // recently used one can not have used all its references yet either
. | 162 // recently used one can not have used all its references yet either
. |
163 return NULL; | 163 return nullptr; |
164 } | 164 } |
165 if (replacement.getGenerationID() == iter->fGenerationId) { | 165 if (replacement.getGenerationID() == iter->fGenerationId) { |
166 // Do not replace a bitmap with a new one using the same | 166 // Do not replace a bitmap with a new one using the same |
167 // pixel ref. Instead look for a different one that will | 167 // pixel ref. Instead look for a different one that will |
168 // potentially free up more space. | 168 // potentially free up more space. |
169 iter = iter->fMoreRecentlyUsed; | 169 iter = iter->fMoreRecentlyUsed; |
170 } else { | 170 } else { |
171 return iter; | 171 return iter; |
172 } | 172 } |
173 } | 173 } |
174 return NULL; | 174 return nullptr; |
175 } | 175 } |
176 | 176 |
177 size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) { | 177 size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) { |
178 if (UNLIMITED_SIZE == fPreferredCount) { | 178 if (UNLIMITED_SIZE == fPreferredCount) { |
179 return 0; | 179 return 0; |
180 } | 180 } |
181 LookupEntry* iter = fLeastRecentlyUsed; | 181 LookupEntry* iter = fLeastRecentlyUsed; |
182 size_t origBytesAllocated = fBytesAllocated; | 182 size_t origBytesAllocated = fBytesAllocated; |
183 // Purge starting from LRU until a non-evictable bitmap is found or until | 183 // Purge starting from LRU until a non-evictable bitmap is found or until |
184 // everything is evicted. | 184 // everything is evicted. |
185 while (iter != NULL) { | 185 while (iter != nullptr) { |
186 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; | 186 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; |
187 if (heapEntry->fRefCount > 0) { | 187 if (heapEntry->fRefCount > 0) { |
188 break; | 188 break; |
189 } | 189 } |
190 LookupEntry* next = iter->fMoreRecentlyUsed; | 190 LookupEntry* next = iter->fMoreRecentlyUsed; |
191 this->removeEntryFromLookupTable(iter); | 191 this->removeEntryFromLookupTable(iter); |
192 // Free the pixel memory. removeEntryFromLookupTable already reduced | 192 // Free the pixel memory. removeEntryFromLookupTable already reduced |
193 // fBytesAllocated properly. | 193 // fBytesAllocated properly. |
194 heapEntry->fBitmap.reset(); | 194 heapEntry->fBitmap.reset(); |
195 // Add to list of unused slots which can be reused in the future. | 195 // Add to list of unused slots which can be reused in the future. |
196 fUnusedSlots.push(heapEntry->fSlot); | 196 fUnusedSlots.push(heapEntry->fSlot); |
197 iter = next; | 197 iter = next; |
198 if (origBytesAllocated - fBytesAllocated >= bytesToFree) { | 198 if (origBytesAllocated - fBytesAllocated >= bytesToFree) { |
199 break; | 199 break; |
200 } | 200 } |
201 } | 201 } |
202 | 202 |
203 if (fLeastRecentlyUsed != iter) { | 203 if (fLeastRecentlyUsed != iter) { |
204 // There was at least one eviction. | 204 // There was at least one eviction. |
205 fLeastRecentlyUsed = iter; | 205 fLeastRecentlyUsed = iter; |
206 if (NULL == fLeastRecentlyUsed) { | 206 if (nullptr == fLeastRecentlyUsed) { |
207 // Everything was evicted | 207 // Everything was evicted |
208 fMostRecentlyUsed = NULL; | 208 fMostRecentlyUsed = nullptr; |
209 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); | 209 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); |
210 fStorage.deleteAll(); | 210 fStorage.deleteAll(); |
211 fUnusedSlots.reset(); | 211 fUnusedSlots.reset(); |
212 SkASSERT(0 == fBytesAllocated); | 212 SkASSERT(0 == fBytesAllocated); |
213 } else { | 213 } else { |
214 fLeastRecentlyUsed->fLessRecentlyUsed = NULL; | 214 fLeastRecentlyUsed->fLessRecentlyUsed = nullptr; |
215 } | 215 } |
216 } | 216 } |
217 | 217 |
218 return origBytesAllocated - fBytesAllocated; | 218 return origBytesAllocated - fBytesAllocated; |
219 } | 219 } |
220 | 220 |
221 int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapE
ntry** entry) { | 221 int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapE
ntry** entry) { |
222 int index = SkTSearch<const LookupEntry, LookupEntry::Less>( | 222 int index = SkTSearch<const LookupEntry, LookupEntry::Less>( |
223 (const LookupEntry**)fLookupTable.b
egin(), | 223 (const LookupEntry**)fLookupTable.b
egin(), |
224 fLookupTable.count(), | 224 fLookupTable.count(), |
225 &indexEntry, sizeof(void*)); | 225 &indexEntry, sizeof(void*)); |
226 | 226 |
227 if (index < 0) { | 227 if (index < 0) { |
228 // insert ourselves into the bitmapIndex | 228 // insert ourselves into the bitmapIndex |
229 index = ~index; | 229 index = ~index; |
230 *fLookupTable.insert(index) = new LookupEntry(indexEntry); | 230 *fLookupTable.insert(index) = new LookupEntry(indexEntry); |
231 } else if (entry != NULL) { | 231 } else if (entry != nullptr) { |
232 // populate the entry if needed | 232 // populate the entry if needed |
233 *entry = fStorage[fLookupTable[index]->fStorageSlot]; | 233 *entry = fStorage[fLookupTable[index]->fStorageSlot]; |
234 } | 234 } |
235 | 235 |
236 return index; | 236 return index; |
237 } | 237 } |
238 | 238 |
239 bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBi
tmap) { | 239 bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBi
tmap) { |
240 SkASSERT(!fExternalStorage); | 240 SkASSERT(!fExternalStorage); |
241 | 241 |
242 // If the bitmap is mutable, we need to do a deep copy, since the | 242 // If the bitmap is mutable, we need to do a deep copy, since the |
243 // caller may modify it afterwards. | 243 // caller may modify it afterwards. |
244 if (originalBitmap.isImmutable()) { | 244 if (originalBitmap.isImmutable()) { |
245 copiedBitmap = originalBitmap; | 245 copiedBitmap = originalBitmap; |
246 // TODO if we have the pixel ref in the heap we could pass it here to avoid a po
tential deep copy | 246 // TODO if we have the pixel ref in the heap we could pass it here to avoid a po
tential deep copy |
247 // else if (sharedPixelRef != NULL) { | 247 // else if (sharedPixelRef != nullptr) { |
248 // copiedBitmap = orig; | 248 // copiedBitmap = orig; |
249 // copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset
()); | 249 // copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset
()); |
250 } else if (originalBitmap.empty()) { | 250 } else if (originalBitmap.empty()) { |
251 copiedBitmap.reset(); | 251 copiedBitmap.reset(); |
252 } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) { | 252 } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) { |
253 return false; | 253 return false; |
254 } | 254 } |
255 copiedBitmap.setImmutable(); | 255 copiedBitmap.setImmutable(); |
256 return true; | 256 return true; |
257 } | 257 } |
258 | 258 |
259 int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) { | 259 int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) { |
260 // remove the bitmap index for the deleted entry | 260 // remove the bitmap index for the deleted entry |
261 SkDEBUGCODE(int count = fLookupTable.count();) | 261 SkDEBUGCODE(int count = fLookupTable.count();) |
262 int index = this->findInLookupTable(*entry, NULL); | 262 int index = this->findInLookupTable(*entry, nullptr); |
263 // Verify that findInLookupTable found an existing entry rather than adding | 263 // Verify that findInLookupTable found an existing entry rather than adding |
264 // a new entry to the lookup table. | 264 // a new entry to the lookup table. |
265 SkASSERT(count == fLookupTable.count()); | 265 SkASSERT(count == fLookupTable.count()); |
266 fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated; | 266 fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated; |
267 delete fLookupTable[index]; | 267 delete fLookupTable[index]; |
268 fLookupTable.remove(index); | 268 fLookupTable.remove(index); |
269 return index; | 269 return index; |
270 } | 270 } |
271 | 271 |
272 int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) { | 272 int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) { |
273 SkBitmapHeapEntry* entry = NULL; | 273 SkBitmapHeapEntry* entry = nullptr; |
274 int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entr
y); | 274 int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entr
y); |
275 | 275 |
276 if (entry) { | 276 if (entry) { |
277 // Already had a copy of the bitmap in the heap. | 277 // Already had a copy of the bitmap in the heap. |
278 if (fOwnerCount != IGNORE_OWNERS) { | 278 if (fOwnerCount != IGNORE_OWNERS) { |
279 if (fDeferAddingOwners) { | 279 if (fDeferAddingOwners) { |
280 *fDeferredEntries.append() = entry->fSlot; | 280 *fDeferredEntries.append() = entry->fSlot; |
281 } else { | 281 } else { |
282 entry->addReferences(fOwnerCount); | 282 entry->addReferences(fOwnerCount); |
283 } | 283 } |
284 } | 284 } |
285 if (fPreferredCount != UNLIMITED_SIZE) { | 285 if (fPreferredCount != UNLIMITED_SIZE) { |
286 LookupEntry* lookupEntry = fLookupTable[searchIndex]; | 286 LookupEntry* lookupEntry = fLookupTable[searchIndex]; |
287 if (lookupEntry != fMostRecentlyUsed) { | 287 if (lookupEntry != fMostRecentlyUsed) { |
288 this->removeFromLRU(lookupEntry); | 288 this->removeFromLRU(lookupEntry); |
289 this->appendToLRU(lookupEntry); | 289 this->appendToLRU(lookupEntry); |
290 } | 290 } |
291 } | 291 } |
292 return entry->fSlot; | 292 return entry->fSlot; |
293 } | 293 } |
294 | 294 |
295 // decide if we need to evict an existing heap entry or create a new one | 295 // decide if we need to evict an existing heap entry or create a new one |
296 if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount
) { | 296 if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount
) { |
297 // iterate through our LRU cache and try to find an entry to evict | 297 // iterate through our LRU cache and try to find an entry to evict |
298 LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap); | 298 LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap); |
299 if (lookupEntry != NULL) { | 299 if (lookupEntry != nullptr) { |
300 // we found an entry to evict | 300 // we found an entry to evict |
301 entry = fStorage[lookupEntry->fStorageSlot]; | 301 entry = fStorage[lookupEntry->fStorageSlot]; |
302 // Remove it from the LRU. The new entry will be added to the LRU la
ter. | 302 // Remove it from the LRU. The new entry will be added to the LRU la
ter. |
303 this->removeFromLRU(lookupEntry); | 303 this->removeFromLRU(lookupEntry); |
304 int index = this->removeEntryFromLookupTable(lookupEntry); | 304 int index = this->removeEntryFromLookupTable(lookupEntry); |
305 | 305 |
306 // update the current search index now that we have removed one | 306 // update the current search index now that we have removed one |
307 if (index < searchIndex) { | 307 if (index < searchIndex) { |
308 searchIndex--; | 308 searchIndex--; |
309 } | 309 } |
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
376 | 376 |
377 void SkBitmapHeap::deferAddingOwners() { | 377 void SkBitmapHeap::deferAddingOwners() { |
378 fDeferAddingOwners = true; | 378 fDeferAddingOwners = true; |
379 } | 379 } |
380 | 380 |
381 void SkBitmapHeap::endAddingOwnersDeferral(bool add) { | 381 void SkBitmapHeap::endAddingOwnersDeferral(bool add) { |
382 if (add) { | 382 if (add) { |
383 for (int i = 0; i < fDeferredEntries.count(); i++) { | 383 for (int i = 0; i < fDeferredEntries.count(); i++) { |
384 SkASSERT(fOwnerCount != IGNORE_OWNERS); | 384 SkASSERT(fOwnerCount != IGNORE_OWNERS); |
385 SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]); | 385 SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]); |
386 SkASSERT(heapEntry != NULL); | 386 SkASSERT(heapEntry != nullptr); |
387 heapEntry->addReferences(fOwnerCount); | 387 heapEntry->addReferences(fOwnerCount); |
388 } | 388 } |
389 } | 389 } |
390 fDeferAddingOwners = false; | 390 fDeferAddingOwners = false; |
391 fDeferredEntries.reset(); | 391 fDeferredEntries.reset(); |
392 } | 392 } |
OLD | NEW |