1 #include "SkTextureCache.h"
2
3 //#define TRACE_HASH_HITS
4 //#define TRACE_TEXTURE_CACHE_PURGE
5
Entry(const SkBitmap & bitmap)6 SkTextureCache::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
~Entry()13 SkTextureCache::Entry::~Entry() {
14 if (fName != 0) {
15 glDeleteTextures(1, &fName);
16 }
17 }
18
19 ///////////////////////////////////////////////////////////////////////////////
20
SkTextureCache(size_t countMax,size_t sizeMax)21 SkTextureCache::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
~SkTextureCache()30 SkTextureCache::~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
deleteAllCaches(bool texturesAreValid)41 void 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
findInSorted(const Key & key) const67 int 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
99 static int gHashHits;
100 static int gSortedHits;
101 #endif
102
find(const Key & key,int * insert) const103 SkTextureCache::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
lock(const SkBitmap & bitmap)135 SkTextureCache::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
unlock(Entry * entry)200 void 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
purgeIfNecessary(size_t extraSize)213 void 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
setMaxCount(size_t count)278 void SkTextureCache::setMaxCount(size_t count) {
279 if (fTexCountMax != count) {
280 fTexCountMax = count;
281 this->purgeIfNecessary(0);
282 }
283 }
284
setMaxSize(size_t size)285 void 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
validate() const295 void 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