gfx/skia/trunk/src/core/SkBitmapHeap.cpp@129ffea94266
gfx/skia/trunk/src/core/SkBitmapHeap.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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 */
9 #include "SkBitmapHeap.h"
11 #include "SkBitmap.h"
12 #include "SkReadBuffer.h"
13 #include "SkWriteBuffer.h"
14 #include "SkTSearch.h"
16 SkBitmapHeapEntry::SkBitmapHeapEntry()
17 : fSlot(-1)
18 , fRefCount(0)
19 , fBytesAllocated(0) {
20 }
22 SkBitmapHeapEntry::~SkBitmapHeapEntry() {
23 SkASSERT(0 == fRefCount);
24 }
26 void SkBitmapHeapEntry::addReferences(int count) {
27 if (0 == fRefCount) {
28 // If there are no current owners then the heap manager
29 // will be the only one able to modify it, so it does not
30 // need to be an atomic operation.
31 fRefCount = count;
32 } else {
33 sk_atomic_add(&fRefCount, count);
34 }
35 }
37 ///////////////////////////////////////////////////////////////////////////////
39 static bool operator<(const SkIPoint& a, const SkIPoint& b) {
40 return *(const int64_t*)&a < *(const int64_t*)&b;
41 }
43 static bool operator>(const SkIPoint& a, const SkIPoint& b) {
44 return *(const int64_t*)&a > *(const int64_t*)&b;
45 }
47 bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
48 const SkBitmapHeap::LookupEntry& b) {
49 if (a.fGenerationId < b.fGenerationId) {
50 return true;
51 } else if (a.fGenerationId > b.fGenerationId) {
52 return false;
53 } else if (a.fPixelOrigin < b.fPixelOrigin) {
54 return true;
55 } else if (a.fPixelOrigin > b.fPixelOrigin) {
56 return false;
57 } else if (a.fWidth < b.fWidth) {
58 return true;
59 } else if (a.fWidth > b.fWidth) {
60 return false;
61 } else if (a.fHeight < b.fHeight) {
62 return true;
63 }
64 return false;
65 }
67 ///////////////////////////////////////////////////////////////////////////////
69 SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount)
70 : INHERITED()
71 , fExternalStorage(NULL)
72 , fMostRecentlyUsed(NULL)
73 , fLeastRecentlyUsed(NULL)
74 , fPreferredCount(preferredSize)
75 , fOwnerCount(ownerCount)
76 , fBytesAllocated(0)
77 , fDeferAddingOwners(false) {
78 }
80 SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
81 : INHERITED()
82 , fExternalStorage(storage)
83 , fMostRecentlyUsed(NULL)
84 , fLeastRecentlyUsed(NULL)
85 , fPreferredCount(preferredSize)
86 , fOwnerCount(IGNORE_OWNERS)
87 , fBytesAllocated(0)
88 , fDeferAddingOwners(false) {
89 SkSafeRef(storage);
90 }
92 SkBitmapHeap::~SkBitmapHeap() {
93 SkDEBUGCODE(
94 for (int i = 0; i < fStorage.count(); i++) {
95 bool unused = false;
96 for (int j = 0; j < fUnusedSlots.count(); j++) {
97 if (fUnusedSlots[j] == fStorage[i]->fSlot) {
98 unused = true;
99 break;
100 }
101 }
102 if (!unused) {
103 fBytesAllocated -= fStorage[i]->fBytesAllocated;
104 }
105 }
106 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
107 )
108 SkASSERT(0 == fBytesAllocated);
109 fStorage.deleteAll();
110 SkSafeUnref(fExternalStorage);
111 fLookupTable.deleteAll();
112 }
114 SkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const {
115 const int size = fStorage.count();
116 SkTRefArray<SkBitmap>* array = NULL;
117 if (size > 0) {
118 array = SkTRefArray<SkBitmap>::Create(size);
119 for (int i = 0; i < size; i++) {
120 // make a shallow copy of the bitmap
121 array->writableAt(i) = fStorage[i]->fBitmap;
122 }
123 }
124 return array;
125 }
127 void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) {
128 if (fMostRecentlyUsed == entry) {
129 fMostRecentlyUsed = entry->fLessRecentlyUsed;
130 if (NULL == fMostRecentlyUsed) {
131 SkASSERT(fLeastRecentlyUsed == entry);
132 fLeastRecentlyUsed = NULL;
133 } else {
134 fMostRecentlyUsed->fMoreRecentlyUsed = NULL;
135 }
136 } else {
137 // Remove entry from its prior place, and make sure to cover the hole.
138 if (fLeastRecentlyUsed == entry) {
139 SkASSERT(entry->fMoreRecentlyUsed != NULL);
140 fLeastRecentlyUsed = entry->fMoreRecentlyUsed;
141 }
142 // Since we have already considered the case where entry is the most recently used, it must
143 // have a more recently used at this point.
144 SkASSERT(entry->fMoreRecentlyUsed != NULL);
145 entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed;
147 if (entry->fLessRecentlyUsed != NULL) {
148 SkASSERT(fLeastRecentlyUsed != entry);
149 entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
150 }
151 }
152 entry->fMoreRecentlyUsed = NULL;
153 }
155 void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) {
156 if (fMostRecentlyUsed != NULL) {
157 SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed);
158 fMostRecentlyUsed->fMoreRecentlyUsed = entry;
159 entry->fLessRecentlyUsed = fMostRecentlyUsed;
160 }
161 fMostRecentlyUsed = entry;
162 if (NULL == fLeastRecentlyUsed) {
163 fLeastRecentlyUsed = entry;
164 }
165 }
167 // iterate through our LRU cache and try to find an entry to evict
168 SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
169 SkASSERT(fPreferredCount != UNLIMITED_SIZE);
170 SkASSERT(fStorage.count() >= fPreferredCount);
172 SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed;
173 while (iter != NULL) {
174 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
175 if (heapEntry->fRefCount > 0) {
176 // If the least recently used bitmap has not been unreferenced
177 // by its owner, then according to our LRU specifications a more
178 // recently used one can not have used all its references yet either.
179 return NULL;
180 }
181 if (replacement.getGenerationID() == iter->fGenerationId) {
182 // Do not replace a bitmap with a new one using the same
183 // pixel ref. Instead look for a different one that will
184 // potentially free up more space.
185 iter = iter->fMoreRecentlyUsed;
186 } else {
187 return iter;
188 }
189 }
190 return NULL;
191 }
193 size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
194 if (UNLIMITED_SIZE == fPreferredCount) {
195 return 0;
196 }
197 LookupEntry* iter = fLeastRecentlyUsed;
198 size_t origBytesAllocated = fBytesAllocated;
199 // Purge starting from LRU until a non-evictable bitmap is found or until
200 // everything is evicted.
201 while (iter != NULL) {
202 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
203 if (heapEntry->fRefCount > 0) {
204 break;
205 }
206 LookupEntry* next = iter->fMoreRecentlyUsed;
207 this->removeEntryFromLookupTable(iter);
208 // Free the pixel memory. removeEntryFromLookupTable already reduced
209 // fBytesAllocated properly.
210 heapEntry->fBitmap.reset();
211 // Add to list of unused slots which can be reused in the future.
212 fUnusedSlots.push(heapEntry->fSlot);
213 iter = next;
214 if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
215 break;
216 }
217 }
219 if (fLeastRecentlyUsed != iter) {
220 // There was at least one eviction.
221 fLeastRecentlyUsed = iter;
222 if (NULL == fLeastRecentlyUsed) {
223 // Everything was evicted
224 fMostRecentlyUsed = NULL;
225 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
226 fStorage.deleteAll();
227 fUnusedSlots.reset();
228 SkASSERT(0 == fBytesAllocated);
229 } else {
230 fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
231 }
232 }
234 return origBytesAllocated - fBytesAllocated;
235 }
237 int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
238 int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
239 (const LookupEntry**)fLookupTable.begin(),
240 fLookupTable.count(),
241 &indexEntry, sizeof(void*));
243 if (index < 0) {
244 // insert ourselves into the bitmapIndex
245 index = ~index;
246 *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry));
247 } else if (entry != NULL) {
248 // populate the entry if needed
249 *entry = fStorage[fLookupTable[index]->fStorageSlot];
250 }
252 return index;
253 }
255 bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
256 SkASSERT(!fExternalStorage);
258 // If the bitmap is mutable, we need to do a deep copy, since the
259 // caller may modify it afterwards.
260 if (originalBitmap.isImmutable()) {
261 copiedBitmap = originalBitmap;
262 // TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy
263 // else if (sharedPixelRef != NULL) {
264 // copiedBitmap = orig;
265 // copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset());
266 } else if (originalBitmap.empty()) {
267 copiedBitmap.reset();
268 } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) {
269 return false;
270 }
271 copiedBitmap.setImmutable();
272 return true;
273 }
275 int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) {
276 // remove the bitmap index for the deleted entry
277 SkDEBUGCODE(int count = fLookupTable.count();)
278 int index = this->findInLookupTable(*entry, NULL);
279 // Verify that findInLookupTable found an existing entry rather than adding
280 // a new entry to the lookup table.
281 SkASSERT(count == fLookupTable.count());
282 fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated;
283 SkDELETE(fLookupTable[index]);
284 fLookupTable.remove(index);
285 return index;
286 }
288 int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
289 SkBitmapHeapEntry* entry = NULL;
290 int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
292 if (entry) {
293 // Already had a copy of the bitmap in the heap.
294 if (fOwnerCount != IGNORE_OWNERS) {
295 if (fDeferAddingOwners) {
296 *fDeferredEntries.append() = entry->fSlot;
297 } else {
298 entry->addReferences(fOwnerCount);
299 }
300 }
301 if (fPreferredCount != UNLIMITED_SIZE) {
302 LookupEntry* lookupEntry = fLookupTable[searchIndex];
303 if (lookupEntry != fMostRecentlyUsed) {
304 this->removeFromLRU(lookupEntry);
305 this->appendToLRU(lookupEntry);
306 }
307 }
308 return entry->fSlot;
309 }
311 // decide if we need to evict an existing heap entry or create a new one
312 if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) {
313 // iterate through our LRU cache and try to find an entry to evict
314 LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap);
315 if (lookupEntry != NULL) {
316 // we found an entry to evict
317 entry = fStorage[lookupEntry->fStorageSlot];
318 // Remove it from the LRU. The new entry will be added to the LRU later.
319 this->removeFromLRU(lookupEntry);
320 int index = this->removeEntryFromLookupTable(lookupEntry);
322 // update the current search index now that we have removed one
323 if (index < searchIndex) {
324 searchIndex--;
325 }
326 }
327 }
329 // if we didn't have an entry yet we need to create one
330 if (!entry) {
331 if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
332 int slot;
333 fUnusedSlots.pop(&slot);
334 entry = fStorage[slot];
335 } else {
336 entry = SkNEW(SkBitmapHeapEntry);
337 fStorage.append(1, &entry);
338 entry->fSlot = fStorage.count() - 1;
339 fBytesAllocated += sizeof(SkBitmapHeapEntry);
340 }
341 }
343 // create a copy of the bitmap
344 bool copySucceeded;
345 if (fExternalStorage) {
346 copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot);
347 } else {
348 copySucceeded = copyBitmap(originalBitmap, entry->fBitmap);
349 }
351 // if the copy failed then we must abort
352 if (!copySucceeded) {
353 // delete the index
354 SkDELETE(fLookupTable[searchIndex]);
355 fLookupTable.remove(searchIndex);
356 // If entry is the last slot in storage, it is safe to delete it.
357 if (fStorage.count() - 1 == entry->fSlot) {
358 // free the slot
359 fStorage.remove(entry->fSlot);
360 fBytesAllocated -= sizeof(SkBitmapHeapEntry);
361 SkDELETE(entry);
362 } else {
363 fUnusedSlots.push(entry->fSlot);
364 }
365 return INVALID_SLOT;
366 }
368 // update the index with the appropriate slot in the heap
369 fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
371 // compute the space taken by this entry
372 // TODO if there is a shared pixel ref don't count it
373 // If the SkBitmap does not share an SkPixelRef with an SkBitmap already
374 // in the SharedHeap, also include the size of its pixels.
375 entry->fBytesAllocated = originalBitmap.getSize();
377 // add the bytes from this entry to the total count
378 fBytesAllocated += entry->fBytesAllocated;
380 if (fOwnerCount != IGNORE_OWNERS) {
381 if (fDeferAddingOwners) {
382 *fDeferredEntries.append() = entry->fSlot;
383 } else {
384 entry->addReferences(fOwnerCount);
385 }
386 }
387 if (fPreferredCount != UNLIMITED_SIZE) {
388 this->appendToLRU(fLookupTable[searchIndex]);
389 }
390 return entry->fSlot;
391 }
393 void SkBitmapHeap::deferAddingOwners() {
394 fDeferAddingOwners = true;
395 }
397 void SkBitmapHeap::endAddingOwnersDeferral(bool add) {
398 if (add) {
399 for (int i = 0; i < fDeferredEntries.count(); i++) {
400 SkASSERT(fOwnerCount != IGNORE_OWNERS);
401 SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]);
402 SkASSERT(heapEntry != NULL);
403 heapEntry->addReferences(fOwnerCount);
404 }
405 }
406 fDeferAddingOwners = false;
407 fDeferredEntries.reset();
408 }
