1 /*
2  * Copyright 2006 The Android Open Source Project
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 
8 #include "SkGlyphCache.h"
9 #include "SkGlyphCache_Globals.h"
10 #include "SkGraphics.h"
11 #include "SkLazyPtr.h"
12 #include "SkPaint.h"
13 #include "SkPath.h"
14 #include "SkTemplates.h"
15 #include "SkTLS.h"
16 #include "SkTypeface.h"
17 
18 //#define SPEW_PURGE_STATUS
19 
20 namespace {
21 
create_globals()22 SkGlyphCache_Globals* create_globals() {
23     return SkNEW_ARGS(SkGlyphCache_Globals, (SkGlyphCache_Globals::kYes_UseMutex));
24 }
25 
26 }  // namespace
27 
28 SK_DECLARE_STATIC_LAZY_PTR(SkGlyphCache_Globals, globals, create_globals);
29 
30 // Returns the shared globals
getSharedGlobals()31 static SkGlyphCache_Globals& getSharedGlobals() {
32     return *globals.get();
33 }
34 
35 // Returns the TLS globals (if set), or the shared globals
getGlobals()36 static SkGlyphCache_Globals& getGlobals() {
37     SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
38     return tls ? *tls : getSharedGlobals();
39 }
40 
41 ///////////////////////////////////////////////////////////////////////////////
42 
43 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
44     #define RecordHashSuccess()             fHashHitCount += 1
45     #define RecordHashCollisionIf(pred)     do { if (pred) fHashMissCount += 1; } while (0)
46 #else
47     #define RecordHashSuccess()             (void)0
48     #define RecordHashCollisionIf(pred)     (void)0
49 #endif
50 #define RecordHashCollision() RecordHashCollisionIf(true)
51 
52 ///////////////////////////////////////////////////////////////////////////////
53 
54 // so we don't grow our arrays a lot
55 #define kMinGlyphCount      16
56 #define kMinGlyphImageSize  (16*2)
57 #define kMinAllocAmount     ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount)
58 
SkGlyphCache(SkTypeface * typeface,const SkDescriptor * desc,SkScalerContext * ctx)59 SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkScalerContext* ctx)
60         : fScalerContext(ctx), fGlyphAlloc(kMinAllocAmount) {
61     SkASSERT(typeface);
62     SkASSERT(desc);
63     SkASSERT(ctx);
64 
65     fPrev = fNext = NULL;
66 
67     fDesc = desc->copy();
68     fScalerContext->getFontMetrics(&fFontMetrics);
69 
70     // Create the sentinel SkGlyph.
71     SkGlyph* sentinel = fGlyphArray.insert(0);
72     sentinel->initGlyphFromCombinedID(SkGlyph::kImpossibleID);
73 
74     // Initialize all index to zero which points to the sentinel SkGlyph.
75     memset(fGlyphHash, 0x00, sizeof(fGlyphHash));
76 
77     fMemoryUsed = sizeof(*this);
78 
79     fGlyphArray.setReserve(kMinGlyphCount);
80 
81     fAuxProcList = NULL;
82 
83 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
84     fHashHitCount = fHashMissCount = 0;
85 #endif
86 }
87 
~SkGlyphCache()88 SkGlyphCache::~SkGlyphCache() {
89 #if 0
90     {
91         size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*);
92         size_t glyphAlloc = fGlyphAlloc.totalCapacity();
93         size_t glyphHashUsed = 0;
94         size_t uniHashUsed = 0;
95         for (int i = 0; i < kHashCount; ++i) {
96             glyphHashUsed += fGlyphHash[i] ? sizeof(fGlyphHash[0]) : 0;
97             uniHashUsed += fCharToGlyphHash[i].fID != 0xFFFFFFFF ? sizeof(fCharToGlyphHash[0]) : 0;
98         }
99         size_t glyphUsed = fGlyphArray.count() * sizeof(SkGlyph);
100         size_t imageUsed = 0;
101         for (int i = 0; i < fGlyphArray.count(); ++i) {
102             const SkGlyph& g = *fGlyphArray[i];
103             if (g.fImage) {
104                 imageUsed += g.fHeight * g.rowBytes();
105             }
106         }
107 
108         SkDebugf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n",
109                  ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(CharGlyphRec) * kHashCount, uniHashUsed);
110 
111     }
112 #endif
113     SkGlyph*   gptr = fGlyphArray.begin();
114     SkGlyph*   stop = fGlyphArray.end();
115     while (gptr < stop) {
116         SkPath* path = gptr->fPath;
117         if (path) {
118             SkDELETE(path);
119         }
120         gptr += 1;
121     }
122     SkDescriptor::Free(fDesc);
123     SkDELETE(fScalerContext);
124     this->invokeAndRemoveAuxProcs();
125 }
126 
getCharGlyphRec(uint32_t id)127 SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
128     if (NULL == fCharToGlyphHash.get()) {
129         // Allocate the array.
130         fCharToGlyphHash.reset(kHashCount);
131         // Initialize entries of fCharToGlyphHash to index the sentinel glyph and
132         // an fID value that will not match any id.
133         for (int i = 0; i <kHashCount; ++i) {
134             fCharToGlyphHash[i].fID = SkGlyph::kImpossibleID;
135             fCharToGlyphHash[i].fGlyphIndex = 0;
136         }
137     }
138 
139     return &fCharToGlyphHash[ID2HashIndex(id)];
140 }
141 
adjustCaches(int insertion_index)142 void SkGlyphCache::adjustCaches(int insertion_index) {
143     for (int i = 0; i < kHashCount; ++i) {
144         if (fGlyphHash[i] >= SkToU16(insertion_index)) {
145             fGlyphHash[i] += 1;
146         }
147     }
148     if (fCharToGlyphHash.get() != NULL) {
149         for (int i = 0; i < kHashCount; ++i) {
150             if (fCharToGlyphHash[i].fGlyphIndex >= SkToU16(insertion_index)) {
151                 fCharToGlyphHash[i].fGlyphIndex += 1;
152             }
153         }
154     }
155 }
156 
157 ///////////////////////////////////////////////////////////////////////////////
158 
159 #ifdef SK_DEBUG
160 #define VALIDATE()  AutoValidate av(this)
161 #else
162 #define VALIDATE()
163 #endif
164 
unicharToGlyph(SkUnichar charCode)165 uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
166     VALIDATE();
167     uint32_t id = SkGlyph::MakeID(charCode);
168     const CharGlyphRec& rec = *this->getCharGlyphRec(id);
169 
170     if (rec.fID == id) {
171         return fGlyphArray[rec.fGlyphIndex].getGlyphID();
172     } else {
173         return fScalerContext->charToGlyphID(charCode);
174     }
175 }
176 
glyphToUnichar(uint16_t glyphID)177 SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
178     return fScalerContext->glyphIDToChar(glyphID);
179 }
180 
getGlyphCount()181 unsigned SkGlyphCache::getGlyphCount() {
182     return fScalerContext->getGlyphCount();
183 }
184 
185 ///////////////////////////////////////////////////////////////////////////////
186 
getUnicharAdvance(SkUnichar charCode)187 const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
188     VALIDATE();
189     return *this->lookupByChar(charCode, kJustAdvance_MetricsType);
190 }
191 
getGlyphIDAdvance(uint16_t glyphID)192 const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
193     VALIDATE();
194     uint32_t id = SkGlyph::MakeID(glyphID);
195     return *this->lookupByCombinedID(id, kJustAdvance_MetricsType);
196 }
197 
198 ///////////////////////////////////////////////////////////////////////////////
199 
getUnicharMetrics(SkUnichar charCode)200 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
201     VALIDATE();
202     return *this->lookupByChar(charCode, kFull_MetricsType);
203 }
204 
getUnicharMetrics(SkUnichar charCode,SkFixed x,SkFixed y)205 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
206                                                SkFixed x, SkFixed y) {
207     VALIDATE();
208     return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
209 }
210 
getGlyphIDMetrics(uint16_t glyphID)211 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
212     VALIDATE();
213     uint32_t id = SkGlyph::MakeID(glyphID);
214     return *this->lookupByCombinedID(id, kFull_MetricsType);
215 }
216 
getGlyphIDMetrics(uint16_t glyphID,SkFixed x,SkFixed y)217 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
218     VALIDATE();
219     uint32_t id = SkGlyph::MakeID(glyphID, x, y);
220     return *this->lookupByCombinedID(id, kFull_MetricsType);
221 }
222 
lookupByChar(SkUnichar charCode,MetricsType type,SkFixed x,SkFixed y)223 SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
224     uint32_t id = SkGlyph::MakeID(charCode, x, y);
225     CharGlyphRec* rec = this->getCharGlyphRec(id);
226     SkGlyph* glyph;
227     if (rec->fID != id) {
228         RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID);
229         // this ID is based on the UniChar
230         rec->fID = id;
231         // this ID is based on the glyph index
232         id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
233         rec->fGlyphIndex = this->lookupMetrics(id, type);
234         glyph = &fGlyphArray[rec->fGlyphIndex];
235     } else {
236         RecordHashSuccess();
237         glyph = &fGlyphArray[rec->fGlyphIndex];
238         if (type == kFull_MetricsType && glyph->isJustAdvance()) {
239             fScalerContext->getMetrics(glyph);
240         }
241     }
242     return glyph;
243 }
244 
lookupByCombinedID(uint32_t id,MetricsType type)245 SkGlyph* SkGlyphCache::lookupByCombinedID(uint32_t id, MetricsType type) {
246     uint32_t hash_index = ID2HashIndex(id);
247     uint16_t glyph_index = fGlyphHash[hash_index];
248     SkGlyph* glyph = &fGlyphArray[glyph_index];
249 
250     if (glyph->fID != id) {
251         RecordHashCollisionIf(glyph_index != SkGlyph::kImpossibleID);
252         glyph_index = this->lookupMetrics(id, type);
253         fGlyphHash[hash_index] = glyph_index;
254         glyph = &fGlyphArray[glyph_index];
255     } else {
256         RecordHashSuccess();
257         if (type == kFull_MetricsType && glyph->isJustAdvance()) {
258            fScalerContext->getMetrics(glyph);
259         }
260     }
261     return glyph;
262 }
263 
lookupMetrics(uint32_t id,MetricsType mtype)264 uint16_t SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
265     SkASSERT(id != SkGlyph::kImpossibleID);
266     // Count is always greater than 0 because of the sentinel.
267     // The fGlyphArray cache is in descending order, so that the sentinel with a value of ~0 is
268     // always at index 0.
269     SkGlyph* gptr = fGlyphArray.begin();
270     int lo = 0;
271     int hi = fGlyphArray.count() - 1;
272     while (lo < hi) {
273         int mid = (hi + lo) >> 1;
274         if (gptr[mid].fID > id) {
275             lo = mid + 1;
276         } else {
277             hi = mid;
278         }
279     }
280 
281     uint16_t glyph_index = hi;
282     SkGlyph* glyph = &gptr[glyph_index];
283     if (glyph->fID == id) {
284         if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
285             fScalerContext->getMetrics(glyph);
286         }
287         SkASSERT(glyph->fID != SkGlyph::kImpossibleID);
288         return glyph_index;
289     }
290 
291     // check if we need to bump hi before falling though to the allocator
292     if (glyph->fID > id) {
293         glyph_index += 1;
294     }
295 
296     // Not found, but hi contains the index of the insertion point of the new glyph.
297     fMemoryUsed += sizeof(SkGlyph);
298 
299     this->adjustCaches(glyph_index);
300 
301     glyph = fGlyphArray.insert(glyph_index);
302     glyph->initGlyphFromCombinedID(id);
303 
304     if (kJustAdvance_MetricsType == mtype) {
305         fScalerContext->getAdvance(glyph);
306     } else {
307         SkASSERT(kFull_MetricsType == mtype);
308         fScalerContext->getMetrics(glyph);
309     }
310 
311     SkASSERT(glyph->fID != SkGlyph::kImpossibleID);
312     return glyph_index;
313 }
314 
findImage(const SkGlyph & glyph)315 const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
316     if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
317         if (NULL == glyph.fImage) {
318             size_t  size = glyph.computeImageSize();
319             const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size,
320                                         SkChunkAlloc::kReturnNil_AllocFailType);
321             // check that alloc() actually succeeded
322             if (glyph.fImage) {
323                 fScalerContext->getImage(glyph);
324                 // TODO: the scaler may have changed the maskformat during
325                 // getImage (e.g. from AA or LCD to BW) which means we may have
326                 // overallocated the buffer. Check if the new computedImageSize
327                 // is smaller, and if so, strink the alloc size in fImageAlloc.
328                 fMemoryUsed += size;
329             }
330         }
331     }
332     return glyph.fImage;
333 }
334 
findPath(const SkGlyph & glyph)335 const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
336     if (glyph.fWidth) {
337         if (glyph.fPath == NULL) {
338             const_cast<SkGlyph&>(glyph).fPath = SkNEW(SkPath);
339             fScalerContext->getPath(glyph, glyph.fPath);
340             fMemoryUsed += sizeof(SkPath) +
341                     glyph.fPath->countPoints() * sizeof(SkPoint);
342         }
343     }
344     return glyph.fPath;
345 }
346 
dump() const347 void SkGlyphCache::dump() const {
348     const SkTypeface* face = fScalerContext->getTypeface();
349     const SkScalerContextRec& rec = fScalerContext->getRec();
350     SkMatrix matrix;
351     rec.getSingleMatrix(&matrix);
352     matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize));
353     SkString name;
354     face->getFamilyName(&name);
355 
356     SkString msg;
357     msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d",
358                face->uniqueID(), name.c_str(), face->style(), rec.fTextSize,
359                matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
360                matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
361                rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
362                fGlyphArray.count());
363 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
364     const int sum = SkTMax(fHashHitCount + fHashMissCount, 1);   // avoid divide-by-zero
365     msg.appendf(" hash:%2d\n", 100 * fHashHitCount / sum);
366 #endif
367     SkDebugf("%s\n", msg.c_str());
368 }
369 
370 ///////////////////////////////////////////////////////////////////////////////
371 
getAuxProcData(void (* proc)(void *),void ** dataPtr) const372 bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
373     const AuxProcRec* rec = fAuxProcList;
374     while (rec) {
375         if (rec->fProc == proc) {
376             if (dataPtr) {
377                 *dataPtr = rec->fData;
378             }
379             return true;
380         }
381         rec = rec->fNext;
382     }
383     return false;
384 }
385 
setAuxProc(void (* proc)(void *),void * data)386 void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) {
387     if (proc == NULL) {
388         return;
389     }
390 
391     AuxProcRec* rec = fAuxProcList;
392     while (rec) {
393         if (rec->fProc == proc) {
394             rec->fData = data;
395             return;
396         }
397         rec = rec->fNext;
398     }
399     // not found, create a new rec
400     rec = SkNEW(AuxProcRec);
401     rec->fProc = proc;
402     rec->fData = data;
403     rec->fNext = fAuxProcList;
404     fAuxProcList = rec;
405 }
406 
invokeAndRemoveAuxProcs()407 void SkGlyphCache::invokeAndRemoveAuxProcs() {
408     AuxProcRec* rec = fAuxProcList;
409     while (rec) {
410         rec->fProc(rec->fData);
411         AuxProcRec* next = rec->fNext;
412         SkDELETE(rec);
413         rec = next;
414     }
415 }
416 
417 ///////////////////////////////////////////////////////////////////////////////
418 ///////////////////////////////////////////////////////////////////////////////
419 
420 #include "SkThread.h"
421 
setCacheSizeLimit(size_t newLimit)422 size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
423     static const size_t minLimit = 256 * 1024;
424     if (newLimit < minLimit) {
425         newLimit = minLimit;
426     }
427 
428     SkAutoMutexAcquire    ac(fMutex);
429 
430     size_t prevLimit = fCacheSizeLimit;
431     fCacheSizeLimit = newLimit;
432     this->internalPurge();
433     return prevLimit;
434 }
435 
setCacheCountLimit(int newCount)436 int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
437     if (newCount < 0) {
438         newCount = 0;
439     }
440 
441     SkAutoMutexAcquire    ac(fMutex);
442 
443     int prevCount = fCacheCountLimit;
444     fCacheCountLimit = newCount;
445     this->internalPurge();
446     return prevCount;
447 }
448 
purgeAll()449 void SkGlyphCache_Globals::purgeAll() {
450     SkAutoMutexAcquire    ac(fMutex);
451     this->internalPurge(fTotalMemoryUsed);
452 }
453 
454 /*  This guy calls the visitor from within the mutext lock, so the visitor
455     cannot:
456     - take too much time
457     - try to acquire the mutext again
458     - call a fontscaler (which might call into the cache)
459 */
VisitCache(SkTypeface * typeface,const SkDescriptor * desc,bool (* proc)(const SkGlyphCache *,void *),void * context)460 SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
461                               const SkDescriptor* desc,
462                               bool (*proc)(const SkGlyphCache*, void*),
463                               void* context) {
464     if (!typeface) {
465         typeface = SkTypeface::GetDefaultTypeface();
466     }
467     SkASSERT(desc);
468 
469     SkGlyphCache_Globals& globals = getGlobals();
470     SkAutoMutexAcquire    ac(globals.fMutex);
471     SkGlyphCache*         cache;
472     bool                  insideMutex = true;
473 
474     globals.validate();
475 
476     for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
477         if (cache->fDesc->equals(*desc)) {
478             globals.internalDetachCache(cache);
479             goto FOUND_IT;
480         }
481     }
482 
483     /* Release the mutex now, before we create a new entry (which might have
484         side-effects like trying to access the cache/mutex (yikes!)
485     */
486     ac.release();           // release the mutex now
487     insideMutex = false;    // can't use globals anymore
488 
489     // Check if we can create a scaler-context before creating the glyphcache.
490     // If not, we may have exhausted OS/font resources, so try purging the
491     // cache once and try again.
492     {
493         // pass true the first time, to notice if the scalercontext failed,
494         // so we can try the purge.
495         SkScalerContext* ctx = typeface->createScalerContext(desc, true);
496         if (!ctx) {
497             getSharedGlobals().purgeAll();
498             ctx = typeface->createScalerContext(desc, false);
499             SkASSERT(ctx);
500         }
501         cache = SkNEW_ARGS(SkGlyphCache, (typeface, desc, ctx));
502     }
503 
504 FOUND_IT:
505 
506     AutoValidate av(cache);
507 
508     if (!proc(cache, context)) {   // need to reattach
509         if (insideMutex) {
510             globals.internalAttachCacheToHead(cache);
511         } else {
512             globals.attachCacheToHead(cache);
513         }
514         cache = NULL;
515     }
516     return cache;
517 }
518 
AttachCache(SkGlyphCache * cache)519 void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
520     SkASSERT(cache);
521     SkASSERT(cache->fNext == NULL);
522 
523     getGlobals().attachCacheToHead(cache);
524 }
525 
Dump()526 void SkGlyphCache::Dump() {
527     SkGlyphCache_Globals& globals = getGlobals();
528     SkAutoMutexAcquire    ac(globals.fMutex);
529     SkGlyphCache*         cache;
530 
531     globals.validate();
532 
533     SkDebugf("SkGlyphCache strikes:%d memory:%d\n",
534              globals.getCacheCountUsed(), (int)globals.getTotalMemoryUsed());
535 
536 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
537     int hitCount = 0;
538     int missCount = 0;
539 #endif
540 
541     for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
542 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
543         hitCount += cache->fHashHitCount;
544         missCount += cache->fHashMissCount;
545 #endif
546         cache->dump();
547     }
548 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
549     SkDebugf("Hash hit percent:%2d\n", 100 * hitCount / (hitCount + missCount));
550 #endif
551 }
552 
553 ///////////////////////////////////////////////////////////////////////////////
554 
attachCacheToHead(SkGlyphCache * cache)555 void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
556     SkAutoMutexAcquire    ac(fMutex);
557 
558     this->validate();
559     cache->validate();
560 
561     this->internalAttachCacheToHead(cache);
562     this->internalPurge();
563 }
564 
internalGetTail() const565 SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
566     SkGlyphCache* cache = fHead;
567     if (cache) {
568         while (cache->fNext) {
569             cache = cache->fNext;
570         }
571     }
572     return cache;
573 }
574 
internalPurge(size_t minBytesNeeded)575 size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
576     this->validate();
577 
578     size_t bytesNeeded = 0;
579     if (fTotalMemoryUsed > fCacheSizeLimit) {
580         bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
581     }
582     bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded);
583     if (bytesNeeded) {
584         // no small purges!
585         bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2);
586     }
587 
588     int countNeeded = 0;
589     if (fCacheCount > fCacheCountLimit) {
590         countNeeded = fCacheCount - fCacheCountLimit;
591         // no small purges!
592         countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
593     }
594 
595     // early exit
596     if (!countNeeded && !bytesNeeded) {
597         return 0;
598     }
599 
600     size_t  bytesFreed = 0;
601     int     countFreed = 0;
602 
603     // we start at the tail and proceed backwards, as the linklist is in LRU
604     // order, with unimportant entries at the tail.
605     SkGlyphCache* cache = this->internalGetTail();
606     while (cache != NULL &&
607            (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
608         SkGlyphCache* prev = cache->fPrev;
609         bytesFreed += cache->fMemoryUsed;
610         countFreed += 1;
611 
612         this->internalDetachCache(cache);
613         SkDELETE(cache);
614         cache = prev;
615     }
616 
617     this->validate();
618 
619 #ifdef SPEW_PURGE_STATUS
620     if (countFreed) {
621         SkDebugf("purging %dK from font cache [%d entries]\n",
622                  (int)(bytesFreed >> 10), countFreed);
623     }
624 #endif
625 
626     return bytesFreed;
627 }
628 
internalAttachCacheToHead(SkGlyphCache * cache)629 void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
630     SkASSERT(NULL == cache->fPrev && NULL == cache->fNext);
631     if (fHead) {
632         fHead->fPrev = cache;
633         cache->fNext = fHead;
634     }
635     fHead = cache;
636 
637     fCacheCount += 1;
638     fTotalMemoryUsed += cache->fMemoryUsed;
639 }
640 
internalDetachCache(SkGlyphCache * cache)641 void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
642     SkASSERT(fCacheCount > 0);
643     fCacheCount -= 1;
644     fTotalMemoryUsed -= cache->fMemoryUsed;
645 
646     if (cache->fPrev) {
647         cache->fPrev->fNext = cache->fNext;
648     } else {
649         fHead = cache->fNext;
650     }
651     if (cache->fNext) {
652         cache->fNext->fPrev = cache->fPrev;
653     }
654     cache->fPrev = cache->fNext = NULL;
655 }
656 
657 ///////////////////////////////////////////////////////////////////////////////
658 
659 #ifdef SK_DEBUG
660 
validate() const661 void SkGlyphCache::validate() const {
662 #ifdef SK_DEBUG_GLYPH_CACHE
663     int count = fGlyphArray.count();
664     for (int i = 0; i < count; i++) {
665         const SkGlyph* glyph = &fGlyphArray[i];
666         SkASSERT(glyph);
667         if (glyph->fImage) {
668             SkASSERT(fGlyphAlloc.contains(glyph->fImage));
669         }
670     }
671 #endif
672 }
673 
validate() const674 void SkGlyphCache_Globals::validate() const {
675     size_t computedBytes = 0;
676     int computedCount = 0;
677 
678     const SkGlyphCache* head = fHead;
679     while (head != NULL) {
680         computedBytes += head->fMemoryUsed;
681         computedCount += 1;
682         head = head->fNext;
683     }
684 
685     SkASSERT(fTotalMemoryUsed == computedBytes);
686     SkASSERT(fCacheCount == computedCount);
687 }
688 
689 #endif
690 
691 ///////////////////////////////////////////////////////////////////////////////
692 ///////////////////////////////////////////////////////////////////////////////
693 
694 #include "SkTypefaceCache.h"
695 
GetFontCacheLimit()696 size_t SkGraphics::GetFontCacheLimit() {
697     return getSharedGlobals().getCacheSizeLimit();
698 }
699 
SetFontCacheLimit(size_t bytes)700 size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
701     return getSharedGlobals().setCacheSizeLimit(bytes);
702 }
703 
GetFontCacheUsed()704 size_t SkGraphics::GetFontCacheUsed() {
705     return getSharedGlobals().getTotalMemoryUsed();
706 }
707 
GetFontCacheCountLimit()708 int SkGraphics::GetFontCacheCountLimit() {
709     return getSharedGlobals().getCacheCountLimit();
710 }
711 
SetFontCacheCountLimit(int count)712 int SkGraphics::SetFontCacheCountLimit(int count) {
713     return getSharedGlobals().setCacheCountLimit(count);
714 }
715 
GetFontCacheCountUsed()716 int SkGraphics::GetFontCacheCountUsed() {
717     return getSharedGlobals().getCacheCountUsed();
718 }
719 
PurgeFontCache()720 void SkGraphics::PurgeFontCache() {
721     getSharedGlobals().purgeAll();
722     SkTypefaceCache::PurgeAll();
723 }
724 
GetTLSFontCacheLimit()725 size_t SkGraphics::GetTLSFontCacheLimit() {
726     const SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
727     return tls ? tls->getCacheSizeLimit() : 0;
728 }
729 
SetTLSFontCacheLimit(size_t bytes)730 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) {
731     if (0 == bytes) {
732         SkGlyphCache_Globals::DeleteTLS();
733     } else {
734         SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes);
735     }
736 }
737