1
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
9#include "SkBitmapHeap.h"
10
11#include "SkBitmap.h"
12#include "SkReadBuffer.h"
13#include "SkWriteBuffer.h"
14#include "SkTSearch.h"
15
16SkBitmapHeapEntry::SkBitmapHeapEntry()
17    : fSlot(-1)
18    , fRefCount(0)
19    , fBytesAllocated(0) {
20}
21
22SkBitmapHeapEntry::~SkBitmapHeapEntry() {
23    SkASSERT(0 == fRefCount);
24}
25
26void 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}
36
37///////////////////////////////////////////////////////////////////////////////
38
39static bool operator<(const SkIPoint& a, const SkIPoint& b) {
40    return *(const int64_t*)&a < *(const int64_t*)&b;
41}
42
43static bool operator>(const SkIPoint& a, const SkIPoint& b) {
44    return *(const int64_t*)&a > *(const int64_t*)&b;
45}
46
47bool 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}
66
67///////////////////////////////////////////////////////////////////////////////
68
69SkBitmapHeap::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}
79
80SkBitmapHeap::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}
91
92SkBitmapHeap::~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}
113
114SkTRefArray<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}
126
127void 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;
146
147        if (entry->fLessRecentlyUsed != NULL) {
148            SkASSERT(fLeastRecentlyUsed != entry);
149            entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
150        }
151    }
152    entry->fMoreRecentlyUsed = NULL;
153}
154
155void 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}
166
167// iterate through our LRU cache and try to find an entry to evict
168SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
169    SkASSERT(fPreferredCount != UNLIMITED_SIZE);
170    SkASSERT(fStorage.count() >= fPreferredCount);
171
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}
192
193size_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    }
218
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    }
233
234    return origBytesAllocated - fBytesAllocated;
235}
236
237int 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*));
242
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    }
251
252    return index;
253}
254
255bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
256    SkASSERT(!fExternalStorage);
257
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}
274
275int 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}
287
288int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
289    SkBitmapHeapEntry* entry = NULL;
290    int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
291
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    }
310
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);
321
322            // update the current search index now that we have removed one
323            if (index < searchIndex) {
324                searchIndex--;
325            }
326        }
327    }
328
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    }
342
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    }
350
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    }
367
368    // update the index with the appropriate slot in the heap
369    fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
370
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();
376
377    // add the bytes from this entry to the total count
378    fBytesAllocated += entry->fBytesAllocated;
379
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}
392
393void SkBitmapHeap::deferAddingOwners() {
394    fDeferAddingOwners = true;
395}
396
397void 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}
409