1#include "SkTextureCache.h"
2
3//#define TRACE_HASH_HITS
4//#define TRACE_TEXTURE_CACHE_PURGE
5
6SkTextureCache::Entry::Entry(const SkBitmap& bitmap)
7        : fName(0), fKey(bitmap), fPrev(NULL), fNext(NULL) {
8
9    fMemSize = SkGL::ComputeTextureMemorySize(bitmap);
10    fLockCount = 0;
11}
12
13SkTextureCache::Entry::~Entry() {
14    if (fName != 0) {
15        glDeleteTextures(1, &fName);
16    }
17}
18
19///////////////////////////////////////////////////////////////////////////////
20
21SkTextureCache::SkTextureCache(size_t countMax, size_t sizeMax)
22        : fHead(NULL), fTail(NULL),
23          fTexCountMax(countMax), fTexSizeMax(sizeMax),
24          fTexCount(0), fTexSize(0) {
25
26    sk_bzero(fHash, sizeof(fHash));
27    this->validate();
28}
29
30SkTextureCache::~SkTextureCache() {
31#ifdef SK_DEBUG
32    Entry* entry = fHead;
33    while (entry) {
34        SkASSERT(entry->lockCount() == 0);
35        entry = entry->fNext;
36    }
37#endif
38    this->validate();
39}
40
41void SkTextureCache::deleteAllCaches(bool texturesAreValid) {
42    this->validate();
43
44    Entry* entry = fHead;
45    while (entry) {
46        Entry* next = entry->fNext;
47        if (!texturesAreValid) {
48            entry->abandonTexture();
49        }
50        SkDELETE(entry);
51        entry = next;
52    }
53
54    fSorted.reset();
55    sk_bzero(fHash, sizeof(fHash));
56
57    fTexCount = 0;
58    fTexSize = 0;
59
60    fTail = fHead = NULL;
61
62    this->validate();
63}
64
65///////////////////////////////////////////////////////////////////////////////
66
67int SkTextureCache::findInSorted(const Key& key) const {
68    int count = fSorted.count();
69    if (count == 0) {
70        return ~0;
71    }
72
73    Entry** sorted = fSorted.begin();
74    int lo = 0;
75    int hi = count - 1;
76    while (lo < hi) {
77        int mid = (hi + lo) >> 1;
78        if (sorted[mid]->getKey() < key) {
79            lo = mid + 1;
80        } else {
81            hi = mid;
82        }
83    }
84
85    // hi is now our best guess
86    const Entry* entry = sorted[hi];
87    if (entry->getKey() == key) {
88        return hi;
89    }
90
91    // return where to insert it
92    if (entry->getKey() < key) {
93        hi += 1;
94    }
95    return ~hi; // we twiddle to indicate not-found
96}
97
98#ifdef TRACE_HASH_HITS
99static int gHashHits;
100static int gSortedHits;
101#endif
102
103SkTextureCache::Entry* SkTextureCache::find(const Key& key, int* insert) const {
104    int count = fSorted.count();
105    if (count == 0) {
106        *insert = 0;
107        return NULL;
108    }
109
110    // check the hash first
111    int hashIndex = key.getHashIndex();
112    Entry* entry = fHash[hashIndex];
113    if (NULL != entry && entry->getKey() == key) {
114#ifdef TRACE_HASH_HITS
115        gHashHits += 1;
116#endif
117        return entry;
118    }
119
120    int index = this->findInSorted(key);
121    if (index >= 0) {
122#ifdef TRACE_HASH_HITS
123        gSortedHits += 1;
124#endif
125        entry = fSorted[index];
126        fHash[hashIndex] = entry;
127        return entry;
128    }
129
130    // ~index is where to insert the entry
131    *insert = ~index;
132    return NULL;
133}
134
135SkTextureCache::Entry* SkTextureCache::lock(const SkBitmap& bitmap) {
136    this->validate();
137
138    // call this before we call find(), so we don't reorder after find() and
139    // invalidate our index
140    this->purgeIfNecessary(SkGL::ComputeTextureMemorySize(bitmap));
141
142    Key key(bitmap);
143    int index;
144    Entry* entry = this->find(key, &index);
145
146    if (NULL == entry) {
147        entry = SkNEW_ARGS(Entry, (bitmap));
148
149        entry->fName = SkGL::BindNewTexture(bitmap, &entry->fTexSize);
150        if (0 == entry->fName) {
151            SkDELETE(entry);
152            return NULL;
153        }
154        fHash[key.getHashIndex()] = entry;
155        *fSorted.insert(index) = entry;
156
157        fTexCount += 1;
158        fTexSize += entry->memSize();
159    } else {
160        // detach from our llist
161        Entry* prev = entry->fPrev;
162        Entry* next = entry->fNext;
163        if (prev) {
164            prev->fNext = next;
165        } else {
166            SkASSERT(fHead == entry);
167            fHead = next;
168        }
169        if (next) {
170            next->fPrev = prev;
171        } else {
172            SkASSERT(fTail == entry);
173            fTail = prev;
174        }
175        // now bind the texture
176        glBindTexture(GL_TEXTURE_2D, entry->fName);
177    }
178
179    // add to head of llist for LRU
180    entry->fPrev = NULL;
181    entry->fNext = fHead;
182    if (NULL != fHead) {
183        SkASSERT(NULL == fHead->fPrev);
184        fHead->fPrev = entry;
185    }
186    fHead = entry;
187    if (NULL == fTail) {
188        fTail = entry;
189    }
190
191    this->validate();
192    entry->lock();
193
194#ifdef TRACE_HASH_HITS
195    SkDebugf("---- texture cache hash=%d sorted=%d\n", gHashHits, gSortedHits);
196#endif
197    return entry;
198}
199
200void SkTextureCache::unlock(Entry* entry) {
201    this->validate();
202
203#ifdef SK_DEBUG
204    SkASSERT(entry);
205    int index = this->findInSorted(entry->getKey());
206    SkASSERT(fSorted[index] == entry);
207#endif
208
209    SkASSERT(entry->fLockCount > 0);
210    entry->unlock();
211}
212
213void SkTextureCache::purgeIfNecessary(size_t extraSize) {
214    this->validate();
215
216    size_t countMax = fTexCountMax;
217    size_t sizeMax = fTexSizeMax;
218
219    // take extraSize into account, but watch for underflow of size_t
220    if (extraSize > sizeMax) {
221        sizeMax = 0;
222    } else {
223        sizeMax -= extraSize;
224    }
225
226    Entry* entry = fTail;
227    while (entry) {
228        if (fTexCount <= countMax && fTexSize <= sizeMax) {
229            break;
230        }
231
232        Entry* prev = entry->fPrev;
233        // don't purge an entry that is locked
234        if (entry->isLocked()) {
235            entry = prev;
236            continue;
237        }
238
239        fTexCount -= 1;
240        fTexSize -= entry->memSize();
241
242        // remove from our sorted and hash arrays
243        int index = this->findInSorted(entry->getKey());
244        SkASSERT(index >= 0);
245        fSorted.remove(index);
246        index = entry->getKey().getHashIndex();
247        if (entry == fHash[index]) {
248            fHash[index] = NULL;
249        }
250
251        // now detach it from our llist
252        Entry* next = entry->fNext;
253        if (prev) {
254            prev->fNext = next;
255        } else {
256            fHead = next;
257        }
258        if (next) {
259            next->fPrev = prev;
260        } else {
261            fTail = prev;
262        }
263
264        // now delete it
265#ifdef TRACE_TEXTURE_CACHE_PURGE
266        SkDebugf("---- purge texture cache %d size=%d\n",
267                 entry->name(), entry->memSize());
268#endif
269        SkDELETE(entry);
270
271        // keep going
272        entry = prev;
273    }
274
275    this->validate();
276}
277
278void SkTextureCache::setMaxCount(size_t count) {
279    if (fTexCountMax != count) {
280        fTexCountMax = count;
281        this->purgeIfNecessary(0);
282    }
283}
284
285void SkTextureCache::setMaxSize(size_t size) {
286    if (fTexSizeMax != size) {
287        fTexSizeMax = size;
288        this->purgeIfNecessary(0);
289    }
290}
291
292///////////////////////////////////////////////////////////////////////////////
293
294#ifdef SK_DEBUG
295void SkTextureCache::validate() const {
296    if (0 == fTexCount) {
297        SkASSERT(0 == fTexSize);
298        SkASSERT(NULL == fHead);
299        SkASSERT(NULL == fTail);
300        return;
301    }
302
303    SkASSERT(fTexSize); // do we allow a zero-sized texture?
304    SkASSERT(fHead);
305    SkASSERT(fTail);
306
307    SkASSERT(NULL == fHead->fPrev);
308    SkASSERT(NULL == fTail->fNext);
309    if (1 == fTexCount) {
310        SkASSERT(fHead == fTail);
311    }
312
313    const Entry* entry = fHead;
314    size_t count = 0;
315    size_t size = 0;
316    size_t i;
317
318    while (entry != NULL) {
319        SkASSERT(count < fTexCount);
320        SkASSERT(size < fTexSize);
321        size += entry->memSize();
322        count += 1;
323        if (NULL == entry->fNext) {
324            SkASSERT(fTail == entry);
325        }
326        entry = entry->fNext;
327    }
328    SkASSERT(count == fTexCount);
329    SkASSERT(size == fTexSize);
330
331    count = 0;
332    size = 0;
333    entry = fTail;
334    while (entry != NULL) {
335        SkASSERT(count < fTexCount);
336        SkASSERT(size < fTexSize);
337        size += entry->memSize();
338        count += 1;
339        if (NULL == entry->fPrev) {
340            SkASSERT(fHead == entry);
341        }
342        entry = entry->fPrev;
343    }
344    SkASSERT(count == fTexCount);
345    SkASSERT(size == fTexSize);
346
347    SkASSERT(count == (size_t)fSorted.count());
348    for (i = 1; i < count; i++) {
349        SkASSERT(fSorted[i-1]->getKey() < fSorted[i]->getKey());
350    }
351
352    for (i = 0; i < kHashCount; i++) {
353        if (fHash[i]) {
354            size_t index = fHash[i]->getKey().getHashIndex();
355            SkASSERT(index == i);
356            index = fSorted.find(fHash[i]);
357            SkASSERT((size_t)index < count);
358        }
359    }
360}
361#endif
362
363
364