SkGlyphCache.cpp revision 4d494f031cd52c79fec69adeaab2c02134b7959b 
1
2/*
3 * Copyright 2006 The Android Open Source Project
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
10#include "SkGlyphCache.h"
11#include "SkGraphics.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//#define USE_CACHE_HASH
20//#define RECORD_HASH_EFFICIENCY
21
22bool gSkSuppressFontCachePurgeSpew;
23
24///////////////////////////////////////////////////////////////////////////////
25
26#ifdef RECORD_HASH_EFFICIENCY
27    static uint32_t gHashSuccess;
28    static uint32_t gHashCollision;
29
30    static void RecordHashSuccess() {
31        gHashSuccess += 1;
32    }
33
34    static void RecordHashCollisionIf(bool pred) {
35        if (pred) {
36            gHashCollision += 1;
37
38            uint32_t total = gHashSuccess + gHashCollision;
39            SkDebugf("Font Cache Hash success rate: %d%%\n",
40                     100 * gHashSuccess / total);
41        }
42    }
43#else
44    #define RecordHashSuccess() (void)0
45    #define RecordHashCollisionIf(pred) (void)0
46#endif
47#define RecordHashCollision() RecordHashCollisionIf(true)
48
49///////////////////////////////////////////////////////////////////////////////
50
51// so we don't grow our arrays a lot
52#define kMinGlyphCount      16
53#define kMinGlyphImageSize  (16*2)
54#define kMinAllocAmount     ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount)
55
56SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc)
57        : fGlyphAlloc(kMinAllocAmount) {
58    SkASSERT(typeface);
59
60    fPrev = fNext = NULL;
61
62    fDesc = desc->copy();
63    fScalerContext = typeface->createScalerContext(desc);
64    fScalerContext->getFontMetrics(&fFontMetrics);
65
66    // init to 0 so that all of the pointers will be null
67    memset(fGlyphHash, 0, sizeof(fGlyphHash));
68    // init with 0xFF so that the charCode field will be -1, which is invalid
69    memset(fCharToGlyphHash, 0xFF, sizeof(fCharToGlyphHash));
70
71    fMemoryUsed = sizeof(*this);
72
73    fGlyphArray.setReserve(kMinGlyphCount);
74
75    fMetricsCount = 0;
76    fAdvanceCount = 0;
77    fAuxProcList = NULL;
78}
79
80SkGlyphCache::~SkGlyphCache() {
81#if 0
82    {
83        size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*);
84        size_t glyphAlloc = fGlyphAlloc.totalCapacity();
85        size_t glyphHashUsed = 0;
86        size_t uniHashUsed = 0;
87        for (int i = 0; i < kHashCount; ++i) {
88            glyphHashUsed += fGlyphHash[i] ? sizeof(fGlyphHash[0]) : 0;
89            uniHashUsed += fCharToGlyphHash[i].fID != 0xFFFFFFFF ? sizeof(fCharToGlyphHash[0]) : 0;
90        }
91        size_t glyphUsed = fGlyphArray.count() * sizeof(SkGlyph);
92        size_t imageUsed = 0;
93        for (int i = 0; i < fGlyphArray.count(); ++i) {
94            const SkGlyph& g = *fGlyphArray[i];
95            if (g.fImage) {
96                imageUsed += g.fHeight * g.rowBytes();
97            }
98        }
99
100        printf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n",
101                 ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(fCharToGlyphHash), uniHashUsed);
102
103    }
104#endif
105    SkGlyph**   gptr = fGlyphArray.begin();
106    SkGlyph**   stop = fGlyphArray.end();
107    while (gptr < stop) {
108        SkPath* path = (*gptr)->fPath;
109        if (path) {
110            SkDELETE(path);
111        }
112        gptr += 1;
113    }
114    SkDescriptor::Free(fDesc);
115    SkDELETE(fScalerContext);
116    this->invokeAndRemoveAuxProcs();
117}
118
119///////////////////////////////////////////////////////////////////////////////
120
121#ifdef SK_DEBUG
122#define VALIDATE()  AutoValidate av(this)
123#else
124#define VALIDATE()
125#endif
126
127uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
128    VALIDATE();
129    uint32_t id = SkGlyph::MakeID(charCode);
130    const CharGlyphRec& rec = fCharToGlyphHash[ID2HashIndex(id)];
131
132    if (rec.fID == id) {
133        return rec.fGlyph->getGlyphID();
134    } else {
135        return fScalerContext->charToGlyphID(charCode);
136    }
137}
138
139SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
140    return fScalerContext->glyphIDToChar(glyphID);
141}
142
143unsigned SkGlyphCache::getGlyphCount() {
144    return fScalerContext->getGlyphCount();
145}
146
147///////////////////////////////////////////////////////////////////////////////
148
149const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
150    VALIDATE();
151    uint32_t id = SkGlyph::MakeID(charCode);
152    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
153
154    if (rec->fID != id) {
155        // this ID is based on the UniChar
156        rec->fID = id;
157        // this ID is based on the glyph index
158        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
159        rec->fGlyph = this->lookupMetrics(id, kJustAdvance_MetricsType);
160    }
161    return *rec->fGlyph;
162}
163
164const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
165    VALIDATE();
166    uint32_t id = SkGlyph::MakeID(glyphID);
167    unsigned index = ID2HashIndex(id);
168    SkGlyph* glyph = fGlyphHash[index];
169
170    if (NULL == glyph || glyph->fID != id) {
171        glyph = this->lookupMetrics(glyphID, kJustAdvance_MetricsType);
172        fGlyphHash[index] = glyph;
173    }
174    return *glyph;
175}
176
177///////////////////////////////////////////////////////////////////////////////
178
179const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
180    VALIDATE();
181    uint32_t id = SkGlyph::MakeID(charCode);
182    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
183
184    if (rec->fID != id) {
185        RecordHashCollisionIf(rec->fGlyph != NULL);
186        // this ID is based on the UniChar
187        rec->fID = id;
188        // this ID is based on the glyph index
189        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
190        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
191    } else {
192        RecordHashSuccess();
193        if (rec->fGlyph->isJustAdvance()) {
194            fScalerContext->getMetrics(rec->fGlyph);
195        }
196    }
197    SkASSERT(rec->fGlyph->isFullMetrics());
198    return *rec->fGlyph;
199}
200
201const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
202                                               SkFixed x, SkFixed y) {
203    VALIDATE();
204    uint32_t id = SkGlyph::MakeID(charCode, x, y);
205    CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
206
207    if (rec->fID != id) {
208        RecordHashCollisionIf(rec->fGlyph != NULL);
209        // this ID is based on the UniChar
210        rec->fID = id;
211        // this ID is based on the glyph index
212        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
213        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
214    } else {
215        RecordHashSuccess();
216        if (rec->fGlyph->isJustAdvance()) {
217            fScalerContext->getMetrics(rec->fGlyph);
218        }
219    }
220    SkASSERT(rec->fGlyph->isFullMetrics());
221    return *rec->fGlyph;
222}
223
224const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
225    VALIDATE();
226    uint32_t id = SkGlyph::MakeID(glyphID);
227    unsigned index = ID2HashIndex(id);
228    SkGlyph* glyph = fGlyphHash[index];
229
230    if (NULL == glyph || glyph->fID != id) {
231        RecordHashCollisionIf(glyph != NULL);
232        glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
233        fGlyphHash[index] = glyph;
234    } else {
235        RecordHashSuccess();
236        if (glyph->isJustAdvance()) {
237            fScalerContext->getMetrics(glyph);
238        }
239    }
240    SkASSERT(glyph->isFullMetrics());
241    return *glyph;
242}
243
244const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID,
245                                               SkFixed x, SkFixed y) {
246    VALIDATE();
247    uint32_t id = SkGlyph::MakeID(glyphID, x, y);
248    unsigned index = ID2HashIndex(id);
249    SkGlyph* glyph = fGlyphHash[index];
250
251    if (NULL == glyph || glyph->fID != id) {
252        RecordHashCollisionIf(glyph != NULL);
253        glyph = this->lookupMetrics(id, kFull_MetricsType);
254        fGlyphHash[index] = glyph;
255    } else {
256        RecordHashSuccess();
257        if (glyph->isJustAdvance()) {
258            fScalerContext->getMetrics(glyph);
259        }
260    }
261    SkASSERT(glyph->isFullMetrics());
262    return *glyph;
263}
264
265SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
266    SkGlyph* glyph;
267
268    int     hi = 0;
269    int     count = fGlyphArray.count();
270
271    if (count) {
272        SkGlyph**   gptr = fGlyphArray.begin();
273        int     lo = 0;
274
275        hi = count - 1;
276        while (lo < hi) {
277            int mid = (hi + lo) >> 1;
278            if (gptr[mid]->fID < id) {
279                lo = mid + 1;
280            } else {
281                hi = mid;
282            }
283        }
284        glyph = gptr[hi];
285        if (glyph->fID == id) {
286            if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
287                fScalerContext->getMetrics(glyph);
288            }
289            return glyph;
290        }
291
292        // check if we need to bump hi before falling though to the allocator
293        if (glyph->fID < id) {
294            hi += 1;
295        }
296    }
297
298    // not found, but hi tells us where to inser the new glyph
299    fMemoryUsed += sizeof(SkGlyph);
300
301    glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
302                                        SkChunkAlloc::kThrow_AllocFailType);
303    glyph->init(id);
304    *fGlyphArray.insert(hi) = glyph;
305
306    if (kJustAdvance_MetricsType == mtype) {
307        fScalerContext->getAdvance(glyph);
308        fAdvanceCount += 1;
309    } else {
310        SkASSERT(kFull_MetricsType == mtype);
311        fScalerContext->getMetrics(glyph);
312        fMetricsCount += 1;
313    }
314
315    return glyph;
316}
317
318const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
319    if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
320        if (glyph.fImage == NULL) {
321            size_t  size = glyph.computeImageSize();
322            const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size,
323                                        SkChunkAlloc::kReturnNil_AllocFailType);
324            // check that alloc() actually succeeded
325            if (glyph.fImage) {
326                fScalerContext->getImage(glyph);
327                // TODO: the scaler may have changed the maskformat during
328                // getImage (e.g. from AA or LCD to BW) which means we may have
329                // overallocated the buffer. Check if the new computedImageSize
330                // is smaller, and if so, strink the alloc size in fImageAlloc.
331                fMemoryUsed += size;
332            }
333        }
334    }
335    return glyph.fImage;
336}
337
338const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
339    if (glyph.fWidth) {
340        if (glyph.fPath == NULL) {
341            const_cast<SkGlyph&>(glyph).fPath = SkNEW(SkPath);
342            fScalerContext->getPath(glyph, glyph.fPath);
343            fMemoryUsed += sizeof(SkPath) +
344                    glyph.fPath->countPoints() * sizeof(SkPoint);
345        }
346    }
347    return glyph.fPath;
348}
349
350///////////////////////////////////////////////////////////////////////////////
351
352bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
353    const AuxProcRec* rec = fAuxProcList;
354    while (rec) {
355        if (rec->fProc == proc) {
356            if (dataPtr) {
357                *dataPtr = rec->fData;
358            }
359            return true;
360        }
361        rec = rec->fNext;
362    }
363    return false;
364}
365
366void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) {
367    if (proc == NULL) {
368        return;
369    }
370
371    AuxProcRec* rec = fAuxProcList;
372    while (rec) {
373        if (rec->fProc == proc) {
374            rec->fData = data;
375            return;
376        }
377        rec = rec->fNext;
378    }
379    // not found, create a new rec
380    rec = SkNEW(AuxProcRec);
381    rec->fProc = proc;
382    rec->fData = data;
383    rec->fNext = fAuxProcList;
384    fAuxProcList = rec;
385}
386
387void SkGlyphCache::invokeAndRemoveAuxProcs() {
388    AuxProcRec* rec = fAuxProcList;
389    while (rec) {
390        rec->fProc(rec->fData);
391        AuxProcRec* next = rec->fNext;
392        SkDELETE(rec);
393        rec = next;
394    }
395}
396
397///////////////////////////////////////////////////////////////////////////////
398///////////////////////////////////////////////////////////////////////////////
399
400#ifndef SK_DEFAULT_FONT_CACHE_LIMIT
401    #define SK_DEFAULT_FONT_CACHE_LIMIT     (2 * 1024 * 1024)
402#endif
403
404#ifdef USE_CACHE_HASH
405    #define HASH_BITCOUNT   6
406    #define HASH_COUNT      (1 << HASH_BITCOUNT)
407    #define HASH_MASK       (HASH_COUNT - 1)
408
409    static unsigned desc_to_hashindex(const SkDescriptor* desc)
410    {
411        SkASSERT(HASH_MASK < 256);  // since our munging reduces to 8 bits
412
413        uint32_t n = *(const uint32_t*)desc;    //desc->getChecksum();
414        SkASSERT(n == desc->getChecksum());
415
416        // don't trust that the low bits of checksum vary enough, so...
417        n ^= (n >> 24) ^ (n >> 16) ^ (n >> 8) ^ (n >> 30);
418
419        return n & HASH_MASK;
420    }
421#endif
422
423#include "SkThread.h"
424
425class SkGlyphCache_Globals {
426public:
427    enum UseMutex {
428        kNo_UseMutex,  // thread-local cache
429        kYes_UseMutex  // shared cache
430    };
431
432    SkGlyphCache_Globals(UseMutex um) {
433        fHead = NULL;
434        fTotalMemoryUsed = 0;
435        fFontCacheLimit = SK_DEFAULT_FONT_CACHE_LIMIT;
436        fMutex = (kYes_UseMutex == um) ? SkNEW(SkMutex) : NULL;
437
438#ifdef USE_CACHE_HASH
439        sk_bzero(fHash, sizeof(fHash));
440#endif
441    }
442
443    ~SkGlyphCache_Globals() {
444        SkGlyphCache* cache = fHead;
445        while (cache) {
446            SkGlyphCache* next = cache->fNext;
447            SkDELETE(cache);
448            cache = next;
449        }
450
451        SkDELETE(fMutex);
452    }
453
454    SkMutex*        fMutex;
455    SkGlyphCache*   fHead;
456    size_t          fTotalMemoryUsed;
457#ifdef USE_CACHE_HASH
458    SkGlyphCache*   fHash[HASH_COUNT];
459#endif
460
461#ifdef SK_DEBUG
462    void validate() const;
463#else
464    void validate() const {}
465#endif
466
467    size_t  getFontCacheLimit() const { return fFontCacheLimit; }
468    size_t  setFontCacheLimit(size_t limit);
469    void    purgeAll(); // does not change budget
470
471    // can return NULL
472    static SkGlyphCache_Globals* FindTLS() {
473        return (SkGlyphCache_Globals*)SkTLS::Find(CreateTLS);
474    }
475
476    static SkGlyphCache_Globals& GetTLS() {
477        return *(SkGlyphCache_Globals*)SkTLS::Get(CreateTLS, DeleteTLS);
478    }
479
480    static void DeleteTLS() { SkTLS::Delete(CreateTLS); }
481
482private:
483    size_t  fFontCacheLimit;
484
485    static void* CreateTLS() {
486        return SkNEW_ARGS(SkGlyphCache_Globals, (kNo_UseMutex));
487    }
488
489    static void DeleteTLS(void* ptr) {
490        SkDELETE((SkGlyphCache_Globals*)ptr);
491    }
492};
493
494size_t SkGlyphCache_Globals::setFontCacheLimit(size_t newLimit) {
495    static const size_t minLimit = 256 * 1024;
496    if (newLimit < minLimit) {
497        newLimit = minLimit;
498    }
499
500    size_t prevLimit = fFontCacheLimit;
501    fFontCacheLimit = newLimit;
502
503    size_t currUsed = fTotalMemoryUsed;
504    if (currUsed > newLimit) {
505        SkAutoMutexAcquire    ac(fMutex);
506        SkGlyphCache::InternalFreeCache(this, currUsed - newLimit);
507    }
508    return prevLimit;
509}
510
511void SkGlyphCache_Globals::purgeAll() {
512    SkAutoMutexAcquire    ac(fMutex);
513    SkGlyphCache::InternalFreeCache(this, fTotalMemoryUsed);
514}
515
516// Returns the shared globals
517static SkGlyphCache_Globals& getSharedGlobals() {
518    // we leak this, so we don't incur any shutdown cost of the destructor
519    static SkGlyphCache_Globals* gGlobals = SkNEW_ARGS(SkGlyphCache_Globals,
520                                       (SkGlyphCache_Globals::kYes_UseMutex));
521    return *gGlobals;
522}
523
524// Returns the TLS globals (if set), or the shared globals
525static SkGlyphCache_Globals& getGlobals() {
526    SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
527    return tls ? *tls : getSharedGlobals();
528}
529
530void SkGlyphCache::VisitAllCaches(bool (*proc)(SkGlyphCache*, void*),
531                                  void* context) {
532    SkGlyphCache_Globals& globals = getGlobals();
533    SkAutoMutexAcquire    ac(globals.fMutex);
534    SkGlyphCache*         cache;
535
536    globals.validate();
537
538    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
539        if (proc(cache, context)) {
540            break;
541        }
542    }
543
544    globals.validate();
545}
546
547/*  This guy calls the visitor from within the mutext lock, so the visitor
548    cannot:
549    - take too much time
550    - try to acquire the mutext again
551    - call a fontscaler (which might call into the cache)
552*/
553SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
554                              const SkDescriptor* desc,
555                              bool (*proc)(const SkGlyphCache*, void*),
556                              void* context) {
557    if (!typeface) {
558        typeface = SkTypeface::GetDefaultTypeface();
559    }
560    SkASSERT(desc);
561
562    SkGlyphCache_Globals& globals = getGlobals();
563    SkAutoMutexAcquire    ac(globals.fMutex);
564    SkGlyphCache*         cache;
565    bool                  insideMutex = true;
566
567    globals.validate();
568
569#ifdef USE_CACHE_HASH
570    SkGlyphCache** hash = globals.fHash;
571    unsigned index = desc_to_hashindex(desc);
572    cache = hash[index];
573    if (cache && *cache->fDesc == *desc) {
574        cache->detach(&globals.fHead);
575        goto FOUND_IT;
576    }
577#endif
578
579    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
580        if (cache->fDesc->equals(*desc)) {
581            cache->detach(&globals.fHead);
582            goto FOUND_IT;
583        }
584    }
585
586    /* Release the mutex now, before we create a new entry (which might have
587        side-effects like trying to access the cache/mutex (yikes!)
588    */
589    ac.release();           // release the mutex now
590    insideMutex = false;    // can't use globals anymore
591
592    cache = SkNEW_ARGS(SkGlyphCache, (typeface, desc));
593
594FOUND_IT:
595
596    AutoValidate av(cache);
597
598    if (proc(cache, context)) {   // stay detached
599        if (insideMutex) {
600            SkASSERT(globals.fTotalMemoryUsed >= cache->fMemoryUsed);
601            globals.fTotalMemoryUsed -= cache->fMemoryUsed;
602#ifdef USE_CACHE_HASH
603            hash[index] = NULL;
604#endif
605        }
606    } else {                        // reattach
607        if (insideMutex) {
608            cache->attachToHead(&globals.fHead);
609#ifdef USE_CACHE_HASH
610            hash[index] = cache;
611#endif
612        } else {
613            AttachCache(cache);
614        }
615        cache = NULL;
616    }
617    return cache;
618}
619
620void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
621    SkASSERT(cache);
622    SkASSERT(cache->fNext == NULL);
623
624    SkGlyphCache_Globals& globals = getGlobals();
625    SkAutoMutexAcquire    ac(globals.fMutex);
626
627    globals.validate();
628    cache->validate();
629
630    // if we have a fixed budget for our cache, do a purge here
631    {
632        size_t allocated = globals.fTotalMemoryUsed + cache->fMemoryUsed;
633        size_t budgeted = globals.getFontCacheLimit();
634        if (allocated > budgeted) {
635            (void)InternalFreeCache(&globals, allocated - budgeted);
636        }
637    }
638
639    cache->attachToHead(&globals.fHead);
640    globals.fTotalMemoryUsed += cache->fMemoryUsed;
641
642#ifdef USE_CACHE_HASH
643    unsigned index = desc_to_hashindex(cache->fDesc);
644    SkASSERT(globals.fHash[index] != cache);
645    globals.fHash[index] = cache;
646#endif
647
648    globals.validate();
649}
650
651///////////////////////////////////////////////////////////////////////////////
652
653SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
654    if (cache) {
655        while (cache->fNext) {
656            cache = cache->fNext;
657        }
658    }
659    return cache;
660}
661
662#ifdef SK_DEBUG
663void SkGlyphCache_Globals::validate() const {
664    size_t computed = 0;
665
666    const SkGlyphCache* head = fHead;
667    while (head != NULL) {
668        computed += head->fMemoryUsed;
669        head = head->fNext;
670    }
671
672    if (fTotalMemoryUsed != computed) {
673        printf("total %d, computed %d\n", (int)fTotalMemoryUsed, (int)computed);
674    }
675    SkASSERT(fTotalMemoryUsed == computed);
676}
677#endif
678
679size_t SkGlyphCache::InternalFreeCache(SkGlyphCache_Globals* globals,
680                                       size_t bytesNeeded) {
681    globals->validate();
682
683    size_t  bytesFreed = 0;
684    int     count = 0;
685
686    // don't do any "small" purges
687    size_t minToPurge = globals->fTotalMemoryUsed >> 2;
688    if (bytesNeeded < minToPurge)
689        bytesNeeded = minToPurge;
690
691    SkGlyphCache* cache = FindTail(globals->fHead);
692    while (cache != NULL && bytesFreed < bytesNeeded) {
693        SkGlyphCache* prev = cache->fPrev;
694        bytesFreed += cache->fMemoryUsed;
695
696#ifdef USE_CACHE_HASH
697        unsigned index = desc_to_hashindex(cache->fDesc);
698        if (cache == globals->fHash[index]) {
699            globals->fHash[index] = NULL;
700        }
701#endif
702
703        cache->detach(&globals->fHead);
704        SkDELETE(cache);
705        cache = prev;
706        count += 1;
707    }
708
709    SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
710    globals->fTotalMemoryUsed -= bytesFreed;
711    globals->validate();
712
713#ifdef SPEW_PURGE_STATUS
714    if (count && !gSkSuppressFontCachePurgeSpew) {
715        SkDebugf("purging %dK from font cache [%d entries]\n",
716                 (int)(bytesFreed >> 10), count);
717    }
718#endif
719
720    return bytesFreed;
721}
722
723///////////////////////////////////////////////////////////////////////////////
724
725#ifdef SK_DEBUG
726void SkGlyphCache::validate() const {
727#ifdef SK_DEBUG_GLYPH_CACHE
728    int count = fGlyphArray.count();
729    for (int i = 0; i < count; i++) {
730        const SkGlyph* glyph = fGlyphArray[i];
731        SkASSERT(glyph);
732        SkASSERT(fGlyphAlloc.contains(glyph));
733        if (glyph->fImage) {
734            SkASSERT(fGlyphAlloc.contains(glyph->fImage));
735        }
736    }
737#endif
738}
739#endif
740
741///////////////////////////////////////////////////////////////////////////////
742///////////////////////////////////////////////////////////////////////////////
743
744#include "SkTypefaceCache.h"
745
746size_t SkGraphics::GetFontCacheLimit() {
747    return getSharedGlobals().getFontCacheLimit();
748}
749
750size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
751    return getSharedGlobals().setFontCacheLimit(bytes);
752}
753
754size_t SkGraphics::GetFontCacheUsed() {
755    return getSharedGlobals().fTotalMemoryUsed;
756}
757
758void SkGraphics::PurgeFontCache() {
759    getSharedGlobals().purgeAll();
760    SkTypefaceCache::PurgeAll();
761}
762
763size_t SkGraphics::GetTLSFontCacheLimit() {
764    const SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
765    return tls ? tls->getFontCacheLimit() : 0;
766}
767
768void SkGraphics::SetTLSFontCacheLimit(size_t bytes) {
769    if (0 == bytes) {
770        SkGlyphCache_Globals::DeleteTLS();
771    } else {
772        SkGlyphCache_Globals::GetTLS().setFontCacheLimit(bytes);
773    }
774}
775