SkGlyphCache.cpp revision 0449bcfb2fa1dd33cb3a4c0c8b17960d17edf01a 
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 "SkOncePtr.h"
12#include "SkPath.h"
13#include "SkTemplates.h"
14#include "SkTraceMemoryDump.h"
15#include "SkTypeface.h"
16
17#include <cctype>
18
19//#define SPEW_PURGE_STATUS
20
21namespace {
22const char gGlyphCacheDumpName[] = "skia/sk_glyph_cache";
23}  // namespace
24
25// Returns the shared globals
26SK_DECLARE_STATIC_ONCE_PTR(SkGlyphCache_Globals, globals);
27static SkGlyphCache_Globals& get_globals() {
28    return *globals.get([]{ return new SkGlyphCache_Globals; });
29}
30
31///////////////////////////////////////////////////////////////////////////////
32
33// so we don't grow our arrays a lot
34#define kMinGlyphCount      16
35#define kMinGlyphImageSize  (16*2)
36#define kMinAllocAmount     ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount)
37
38SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkScalerContext* ctx)
39    : fDesc(desc->copy())
40    , fScalerContext(ctx)
41    , fGlyphAlloc(kMinAllocAmount) {
42    SkASSERT(typeface);
43    SkASSERT(desc);
44    SkASSERT(ctx);
45
46    fPrev = fNext = nullptr;
47
48    fScalerContext->getFontMetrics(&fFontMetrics);
49
50    fMemoryUsed = sizeof(*this);
51
52    fAuxProcList = nullptr;
53}
54
55SkGlyphCache::~SkGlyphCache() {
56    fGlyphMap.foreach ([](SkGlyph* g) {
57        if (g->fPathData) {
58            delete g->fPathData->fPath;
59        } } );
60    SkDescriptor::Free(fDesc);
61    delete fScalerContext;
62    this->invokeAndRemoveAuxProcs();
63}
64
65SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(PackedUnicharID packedUnicharID) {
66    if (nullptr == fPackedUnicharIDToPackedGlyphID.get()) {
67        // Allocate the array.
68        fPackedUnicharIDToPackedGlyphID.reset(kHashCount);
69        // Initialize array to map character and position with the impossible glyph ID. This
70        // represents no mapping.
71        for (int i = 0; i <kHashCount; ++i) {
72            fPackedUnicharIDToPackedGlyphID[i].fPackedUnicharID = SkGlyph::kImpossibleID;
73            fPackedUnicharIDToPackedGlyphID[i].fPackedGlyphID = 0;
74        }
75    }
76
77    return &fPackedUnicharIDToPackedGlyphID[SkChecksum::CheapMix(packedUnicharID) & kHashMask];
78}
79
80///////////////////////////////////////////////////////////////////////////////
81
82#ifdef SK_DEBUG
83#define VALIDATE()  AutoValidate av(this)
84#else
85#define VALIDATE()
86#endif
87
88uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
89    VALIDATE();
90    PackedUnicharID packedUnicharID = SkGlyph::MakeID(charCode);
91    const CharGlyphRec& rec = *this->getCharGlyphRec(packedUnicharID);
92
93    if (rec.fPackedUnicharID == packedUnicharID) {
94        return SkGlyph::ID2Code(rec.fPackedGlyphID);
95    } else {
96        return fScalerContext->charToGlyphID(charCode);
97    }
98}
99
100SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
101    return fScalerContext->glyphIDToChar(glyphID);
102}
103
104unsigned SkGlyphCache::getGlyphCount() const {
105    return fScalerContext->getGlyphCount();
106}
107
108int SkGlyphCache::countCachedGlyphs() const {
109    return fGlyphMap.count();
110}
111
112///////////////////////////////////////////////////////////////////////////////
113
114const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
115    VALIDATE();
116    return *this->lookupByChar(charCode, kJustAdvance_MetricsType);
117}
118
119const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
120    VALIDATE();
121    PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID);
122    return *this->lookupByPackedGlyphID(packedGlyphID, kJustAdvance_MetricsType);
123}
124
125///////////////////////////////////////////////////////////////////////////////
126
127const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
128    VALIDATE();
129    return *this->lookupByChar(charCode, kFull_MetricsType);
130}
131
132const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) {
133    VALIDATE();
134    return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
135}
136
137const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
138    VALIDATE();
139    PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID);
140    return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
141}
142
143const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
144    VALIDATE();
145    PackedGlyphID packedGlyphID = SkGlyph::MakeID(glyphID, x, y);
146    return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
147}
148
149SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
150    PackedUnicharID id = SkGlyph::MakeID(charCode, x, y);
151    CharGlyphRec* rec = this->getCharGlyphRec(id);
152    if (rec->fPackedUnicharID != id) {
153        // this ID is based on the UniChar
154        rec->fPackedUnicharID = id;
155        // this ID is based on the glyph index
156        PackedGlyphID combinedID = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
157        rec->fPackedGlyphID = combinedID;
158        return this->lookupByPackedGlyphID(combinedID, type);
159    } else {
160        return this->lookupByPackedGlyphID(rec->fPackedGlyphID, type);
161    }
162}
163
164SkGlyph* SkGlyphCache::lookupByPackedGlyphID(PackedGlyphID packedGlyphID, MetricsType type) {
165    SkGlyph* glyph = fGlyphMap.find(packedGlyphID);
166
167    if (nullptr == glyph) {
168        glyph = this->allocateNewGlyph(packedGlyphID, type);
169    } else {
170        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
171           fScalerContext->getMetrics(glyph);
172        }
173    }
174    return glyph;
175}
176
177SkGlyph* SkGlyphCache::allocateNewGlyph(PackedGlyphID packedGlyphID, MetricsType mtype) {
178    fMemoryUsed += sizeof(SkGlyph);
179
180    SkGlyph* glyphPtr;
181    {
182        SkGlyph glyph;
183        glyph.initGlyphFromCombinedID(packedGlyphID);
184        glyphPtr = fGlyphMap.set(glyph);
185    }
186
187    if (kJustAdvance_MetricsType == mtype) {
188        fScalerContext->getAdvance(glyphPtr);
189    } else {
190        SkASSERT(kFull_MetricsType == mtype);
191        fScalerContext->getMetrics(glyphPtr);
192    }
193
194    SkASSERT(glyphPtr->fID != SkGlyph::kImpossibleID);
195    return glyphPtr;
196}
197
198const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
199    if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
200        if (nullptr == glyph.fImage) {
201            size_t  size = glyph.computeImageSize();
202            const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size,
203                                        SkChunkAlloc::kReturnNil_AllocFailType);
204            // check that alloc() actually succeeded
205            if (glyph.fImage) {
206                fScalerContext->getImage(glyph);
207                // TODO: the scaler may have changed the maskformat during
208                // getImage (e.g. from AA or LCD to BW) which means we may have
209                // overallocated the buffer. Check if the new computedImageSize
210                // is smaller, and if so, strink the alloc size in fImageAlloc.
211                fMemoryUsed += size;
212            }
213        }
214    }
215    return glyph.fImage;
216}
217
218const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
219    if (glyph.fWidth) {
220        if (glyph.fPathData == nullptr) {
221            SkGlyph::PathData* pathData =
222                    (SkGlyph::PathData* ) fGlyphAlloc.allocThrow(sizeof(SkGlyph::PathData));
223            const_cast<SkGlyph&>(glyph).fPathData = pathData;
224            pathData->fIntercept = nullptr;
225            SkPath* path = pathData->fPath = new SkPath;
226            fScalerContext->getPath(glyph, path);
227            fMemoryUsed += sizeof(SkPath) + path->countPoints() * sizeof(SkPoint);
228        }
229    }
230    return glyph.fPathData ? glyph.fPathData->fPath : nullptr;
231}
232
233#include "../pathops/SkPathOpsCubic.h"
234#include "../pathops/SkPathOpsQuad.h"
235
236static bool quad_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
237    SkScalar min = SkTMin(SkTMin(pts[0], pts[2]), pts[4]);
238    if (bounds[1] < min) {
239        return false;
240    }
241    SkScalar max = SkTMax(SkTMax(pts[0], pts[2]), pts[4]);
242    return bounds[0] < max;
243}
244
245static bool cubic_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
246    SkScalar min = SkTMin(SkTMin(SkTMin(pts[0], pts[2]), pts[4]), pts[6]);
247    if (bounds[1] < min) {
248        return false;
249    }
250    SkScalar max = SkTMax(SkTMax(SkTMax(pts[0], pts[2]), pts[4]), pts[6]);
251    return bounds[0] < max;
252}
253
254void SkGlyphCache::OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale,
255                                 SkScalar xPos, SkScalar* array, int* count) {
256    if (array) {
257        array += *count;
258        for (int index = 0; index < 2; index++) {
259            *array++ = intercept->fInterval[index] * scale + xPos;
260        }
261    }
262    *count += 2;
263}
264
265void SkGlyphCache::AddInterval(SkScalar val, SkGlyph::Intercept* intercept) {
266    intercept->fInterval[0] = SkTMin(intercept->fInterval[0], val);
267    intercept->fInterval[1] = SkTMax(intercept->fInterval[1], val);
268}
269
270void SkGlyphCache::AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2],
271        bool yAxis, SkGlyph::Intercept* intercept) {
272    for (int i = 0; i < ptCount; ++i) {
273        SkScalar val = *(&pts[i].fY - yAxis);
274        if (bounds[0] < val && val < bounds[1]) {
275            AddInterval(*(&pts[i].fX + yAxis), intercept);
276        }
277    }
278}
279
280void SkGlyphCache::AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis,
281                     SkGlyph::Intercept* intercept) {
282    SkScalar t = yAxis ? (axis - pts[0].fX) / (pts[1].fX - pts[0].fX)
283            : (axis - pts[0].fY) / (pts[1].fY - pts[0].fY);
284    if (0 <= t && t < 1) {   // this handles divide by zero above
285        AddInterval(yAxis ? pts[0].fY + t * (pts[1].fY - pts[0].fY)
286            : pts[0].fX + t * (pts[1].fX - pts[0].fX), intercept);
287    }
288}
289
290void SkGlyphCache::AddQuad(const SkPoint pts[2], SkScalar axis, bool yAxis,
291                     SkGlyph::Intercept* intercept) {
292    SkDQuad quad;
293    quad.set(pts);
294    double roots[2];
295    int count = yAxis ? quad.verticalIntersect(axis, roots)
296            : quad.horizontalIntersect(axis, roots);
297    while (--count >= 0) {
298        SkPoint pt = quad.ptAtT(roots[count]).asSkPoint();
299        AddInterval(*(&pt.fX + yAxis), intercept);
300    }
301}
302
303void SkGlyphCache::AddCubic(const SkPoint pts[3], SkScalar axis, bool yAxis,
304                      SkGlyph::Intercept* intercept) {
305    SkDCubic cubic;
306    cubic.set(pts);
307    double roots[3];
308    int count = yAxis ? cubic.verticalIntersect(axis, roots)
309            : cubic.horizontalIntersect(axis, roots);
310    while (--count >= 0) {
311        SkPoint pt = cubic.ptAtT(roots[count]).asSkPoint();
312        AddInterval(*(&pt.fX + yAxis), intercept);
313    }
314}
315
316const SkGlyph::Intercept* SkGlyphCache::MatchBounds(const SkGlyph* glyph,
317                                                    const SkScalar bounds[2]) {
318    if (!glyph->fPathData) {
319        return nullptr;
320    }
321    const SkGlyph::Intercept* intercept = glyph->fPathData->fIntercept;
322    while (intercept) {
323        if (bounds[0] == intercept->fBounds[0] && bounds[1] == intercept->fBounds[1]) {
324            return intercept;
325        }
326        intercept = intercept->fNext;
327    }
328    return nullptr;
329}
330
331void SkGlyphCache::findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
332        bool yAxis, SkGlyph* glyph, SkScalar* array, int* count) {
333    const SkGlyph::Intercept* match = MatchBounds(glyph, bounds);
334
335    if (match) {
336        if (match->fInterval[0] < match->fInterval[1]) {
337            OffsetResults(match, scale, xPos, array, count);
338        }
339        return;
340    }
341
342    SkGlyph::Intercept* intercept =
343            (SkGlyph::Intercept* ) fGlyphAlloc.allocThrow(sizeof(SkGlyph::Intercept));
344    intercept->fNext = glyph->fPathData->fIntercept;
345    intercept->fBounds[0] = bounds[0];
346    intercept->fBounds[1] = bounds[1];
347    intercept->fInterval[0] = SK_ScalarMax;
348    intercept->fInterval[1] = SK_ScalarMin;
349    glyph->fPathData->fIntercept = intercept;
350    const SkPath* path = glyph->fPathData->fPath;
351    const SkRect& pathBounds = path->getBounds();
352    if (*(&pathBounds.fBottom - yAxis) < bounds[0] || bounds[1] < *(&pathBounds.fTop - yAxis)) {
353        return;
354    }
355    SkPath::Iter iter(*path, false);
356    SkPoint pts[4];
357    SkPath::Verb verb;
358    while (SkPath::kDone_Verb != (verb = iter.next(pts))) {
359        switch (verb) {
360            case SkPath::kMove_Verb:
361                break;
362            case SkPath::kLine_Verb:
363                AddLine(pts, bounds[0], yAxis, intercept);
364                AddLine(pts, bounds[1], yAxis, intercept);
365                AddPoints(pts, 2, bounds, yAxis, intercept);
366                break;
367            case SkPath::kQuad_Verb:
368                if (!quad_in_bounds(&pts[0].fY - yAxis, bounds)) {
369                    break;
370                }
371                AddQuad(pts, bounds[0], yAxis, intercept);
372                AddQuad(pts, bounds[1], yAxis, intercept);
373                AddPoints(pts, 3, bounds, yAxis, intercept);
374                break;
375            case SkPath::kConic_Verb:
376                SkASSERT(0);  // no support for text composed of conics
377                break;
378            case SkPath::kCubic_Verb:
379                if (!cubic_in_bounds(&pts[0].fY - yAxis, bounds)) {
380                    break;
381                }
382                AddCubic(pts, bounds[0], yAxis, intercept);
383                AddCubic(pts, bounds[1], yAxis, intercept);
384                AddPoints(pts, 4, bounds, yAxis, intercept);
385                break;
386            case SkPath::kClose_Verb:
387                break;
388            default:
389                SkASSERT(0);
390                break;
391        }
392    }
393    if (intercept->fInterval[0] >= intercept->fInterval[1]) {
394        intercept->fInterval[0] = SK_ScalarMax;
395        intercept->fInterval[1] = SK_ScalarMin;
396        return;
397    }
398    OffsetResults(intercept, scale, xPos, array, count);
399}
400
401void SkGlyphCache::dump() const {
402    const SkTypeface* face = fScalerContext->getTypeface();
403    const SkScalerContextRec& rec = fScalerContext->getRec();
404    SkMatrix matrix;
405    rec.getSingleMatrix(&matrix);
406    matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize));
407    SkString name;
408    face->getFamilyName(&name);
409
410    SkString msg;
411    msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d",
412               face->uniqueID(), name.c_str(), face->style(), rec.fTextSize,
413               matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
414               matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
415               rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
416               fGlyphMap.count());
417    SkDebugf("%s\n", msg.c_str());
418}
419
420///////////////////////////////////////////////////////////////////////////////
421
422bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
423    const AuxProcRec* rec = fAuxProcList;
424    while (rec) {
425        if (rec->fProc == proc) {
426            if (dataPtr) {
427                *dataPtr = rec->fData;
428            }
429            return true;
430        }
431        rec = rec->fNext;
432    }
433    return false;
434}
435
436void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) {
437    if (proc == nullptr) {
438        return;
439    }
440
441    AuxProcRec* rec = fAuxProcList;
442    while (rec) {
443        if (rec->fProc == proc) {
444            rec->fData = data;
445            return;
446        }
447        rec = rec->fNext;
448    }
449    // not found, create a new rec
450    rec = new AuxProcRec;
451    rec->fProc = proc;
452    rec->fData = data;
453    rec->fNext = fAuxProcList;
454    fAuxProcList = rec;
455}
456
457void SkGlyphCache::invokeAndRemoveAuxProcs() {
458    AuxProcRec* rec = fAuxProcList;
459    while (rec) {
460        rec->fProc(rec->fData);
461        AuxProcRec* next = rec->fNext;
462        delete rec;
463        rec = next;
464    }
465}
466
467///////////////////////////////////////////////////////////////////////////////
468///////////////////////////////////////////////////////////////////////////////
469
470typedef SkAutoTExclusive<SkSpinlock> Exclusive;
471
472size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
473    static const size_t minLimit = 256 * 1024;
474    if (newLimit < minLimit) {
475        newLimit = minLimit;
476    }
477
478    Exclusive ac(fLock);
479
480    size_t prevLimit = fCacheSizeLimit;
481    fCacheSizeLimit = newLimit;
482    this->internalPurge();
483    return prevLimit;
484}
485
486int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
487    if (newCount < 0) {
488        newCount = 0;
489    }
490
491    Exclusive ac(fLock);
492
493    int prevCount = fCacheCountLimit;
494    fCacheCountLimit = newCount;
495    this->internalPurge();
496    return prevCount;
497}
498
499void SkGlyphCache_Globals::purgeAll() {
500    Exclusive ac(fLock);
501    this->internalPurge(fTotalMemoryUsed);
502}
503
504/*  This guy calls the visitor from within the mutext lock, so the visitor
505    cannot:
506    - take too much time
507    - try to acquire the mutext again
508    - call a fontscaler (which might call into the cache)
509*/
510SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
511                              const SkDescriptor* desc,
512                              bool (*proc)(const SkGlyphCache*, void*),
513                              void* context) {
514    if (!typeface) {
515        typeface = SkTypeface::GetDefaultTypeface();
516    }
517    SkASSERT(desc);
518
519    SkGlyphCache_Globals& globals = get_globals();
520    SkGlyphCache*         cache;
521
522    {
523        Exclusive ac(globals.fLock);
524
525        globals.validate();
526
527        for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
528            if (cache->fDesc->equals(*desc)) {
529                globals.internalDetachCache(cache);
530                if (!proc(cache, context)) {
531                    globals.internalAttachCacheToHead(cache);
532                    cache = nullptr;
533                }
534                return cache;
535            }
536        }
537    }
538
539    // Check if we can create a scaler-context before creating the glyphcache.
540    // If not, we may have exhausted OS/font resources, so try purging the
541    // cache once and try again.
542    {
543        // pass true the first time, to notice if the scalercontext failed,
544        // so we can try the purge.
545        SkScalerContext* ctx = typeface->createScalerContext(desc, true);
546        if (!ctx) {
547            get_globals().purgeAll();
548            ctx = typeface->createScalerContext(desc, false);
549            SkASSERT(ctx);
550        }
551        cache = new SkGlyphCache(typeface, desc, ctx);
552    }
553
554    AutoValidate av(cache);
555
556    if (!proc(cache, context)) {   // need to reattach
557        globals.attachCacheToHead(cache);
558        cache = nullptr;
559    }
560    return cache;
561}
562
563void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
564    SkASSERT(cache);
565    SkASSERT(cache->fNext == nullptr);
566
567    get_globals().attachCacheToHead(cache);
568}
569
570static void dump_visitor(const SkGlyphCache& cache, void* context) {
571    int* counter = (int*)context;
572    int index = *counter;
573    *counter += 1;
574
575    const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
576
577    SkDebugf("[%3d] ID %3d, glyphs %3d, size %g, scale %g, skew %g, [%g %g %g %g]\n",
578             index, rec.fFontID, cache.countCachedGlyphs(),
579             rec.fTextSize, rec.fPreScaleX, rec.fPreSkewX,
580             rec.fPost2x2[0][0], rec.fPost2x2[0][1], rec.fPost2x2[1][0], rec.fPost2x2[1][1]);
581}
582
583void SkGlyphCache::Dump() {
584    SkDebugf("GlyphCache [     used    budget ]\n");
585    SkDebugf("    bytes  [ %8zu  %8zu ]\n",
586             SkGraphics::GetFontCacheUsed(), SkGraphics::GetFontCacheLimit());
587    SkDebugf("    count  [ %8zu  %8zu ]\n",
588             SkGraphics::GetFontCacheCountUsed(), SkGraphics::GetFontCacheCountLimit());
589
590    int counter = 0;
591    SkGlyphCache::VisitAll(dump_visitor, &counter);
592}
593
594static void sk_trace_dump_visitor(const SkGlyphCache& cache, void* context) {
595    SkTraceMemoryDump* dump = static_cast<SkTraceMemoryDump*>(context);
596
597    const SkTypeface* face = cache.getScalerContext()->getTypeface();
598    const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
599
600    SkString fontName;
601    face->getFamilyName(&fontName);
602    // Replace all special characters with '_'.
603    for (size_t index = 0; index < fontName.size(); ++index) {
604        if (!std::isalnum(fontName[index])) {
605            fontName[index] = '_';
606        }
607    }
608
609    SkString dumpName = SkStringPrintf("%s/%s_%d/%p",
610                                       gGlyphCacheDumpName, fontName.c_str(), rec.fFontID, &cache);
611
612    dump->dumpNumericValue(dumpName.c_str(), "size", "bytes", cache.getMemoryUsed());
613    dump->dumpNumericValue(dumpName.c_str(), "glyph_count", "objects", cache.countCachedGlyphs());
614    dump->setMemoryBacking(dumpName.c_str(), "malloc", nullptr);
615}
616
617void SkGlyphCache::DumpMemoryStatistics(SkTraceMemoryDump* dump) {
618    dump->dumpNumericValue(gGlyphCacheDumpName, "size", "bytes", SkGraphics::GetFontCacheUsed());
619    dump->dumpNumericValue(gGlyphCacheDumpName, "budget_size", "bytes",
620                           SkGraphics::GetFontCacheLimit());
621    dump->dumpNumericValue(gGlyphCacheDumpName, "glyph_count", "objects",
622                           SkGraphics::GetFontCacheCountUsed());
623    dump->dumpNumericValue(gGlyphCacheDumpName, "budget_glyph_count", "objects",
624                           SkGraphics::GetFontCacheCountLimit());
625
626    if (dump->getRequestedDetails() == SkTraceMemoryDump::kLight_LevelOfDetail) {
627        dump->setMemoryBacking(gGlyphCacheDumpName, "malloc", nullptr);
628        return;
629    }
630
631    SkGlyphCache::VisitAll(sk_trace_dump_visitor, dump);
632}
633
634void SkGlyphCache::VisitAll(Visitor visitor, void* context) {
635    SkGlyphCache_Globals& globals = get_globals();
636    Exclusive ac(globals.fLock);
637    SkGlyphCache*         cache;
638
639    globals.validate();
640
641    for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
642        visitor(*cache, context);
643    }
644}
645
646///////////////////////////////////////////////////////////////////////////////
647
648void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
649    Exclusive ac(fLock);
650
651    this->validate();
652    cache->validate();
653
654    this->internalAttachCacheToHead(cache);
655    this->internalPurge();
656}
657
658SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
659    SkGlyphCache* cache = fHead;
660    if (cache) {
661        while (cache->fNext) {
662            cache = cache->fNext;
663        }
664    }
665    return cache;
666}
667
668size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
669    this->validate();
670
671    size_t bytesNeeded = 0;
672    if (fTotalMemoryUsed > fCacheSizeLimit) {
673        bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
674    }
675    bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded);
676    if (bytesNeeded) {
677        // no small purges!
678        bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2);
679    }
680
681    int countNeeded = 0;
682    if (fCacheCount > fCacheCountLimit) {
683        countNeeded = fCacheCount - fCacheCountLimit;
684        // no small purges!
685        countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
686    }
687
688    // early exit
689    if (!countNeeded && !bytesNeeded) {
690        return 0;
691    }
692
693    size_t  bytesFreed = 0;
694    int     countFreed = 0;
695
696    // we start at the tail and proceed backwards, as the linklist is in LRU
697    // order, with unimportant entries at the tail.
698    SkGlyphCache* cache = this->internalGetTail();
699    while (cache != nullptr &&
700           (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
701        SkGlyphCache* prev = cache->fPrev;
702        bytesFreed += cache->fMemoryUsed;
703        countFreed += 1;
704
705        this->internalDetachCache(cache);
706        delete cache;
707        cache = prev;
708    }
709
710    this->validate();
711
712#ifdef SPEW_PURGE_STATUS
713    if (countFreed) {
714        SkDebugf("purging %dK from font cache [%d entries]\n",
715                 (int)(bytesFreed >> 10), countFreed);
716    }
717#endif
718
719    return bytesFreed;
720}
721
722void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
723    SkASSERT(nullptr == cache->fPrev && nullptr == cache->fNext);
724    if (fHead) {
725        fHead->fPrev = cache;
726        cache->fNext = fHead;
727    }
728    fHead = cache;
729
730    fCacheCount += 1;
731    fTotalMemoryUsed += cache->fMemoryUsed;
732}
733
734void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
735    SkASSERT(fCacheCount > 0);
736    fCacheCount -= 1;
737    fTotalMemoryUsed -= cache->fMemoryUsed;
738
739    if (cache->fPrev) {
740        cache->fPrev->fNext = cache->fNext;
741    } else {
742        fHead = cache->fNext;
743    }
744    if (cache->fNext) {
745        cache->fNext->fPrev = cache->fPrev;
746    }
747    cache->fPrev = cache->fNext = nullptr;
748}
749
750///////////////////////////////////////////////////////////////////////////////
751
752#ifdef SK_DEBUG
753
754void SkGlyphCache::validate() const {
755#ifdef SK_DEBUG_GLYPH_CACHE
756    int count = fGlyphArray.count();
757    for (int i = 0; i < count; i++) {
758        const SkGlyph* glyph = &fGlyphArray[i];
759        SkASSERT(glyph);
760        if (glyph->fImage) {
761            SkASSERT(fGlyphAlloc.contains(glyph->fImage));
762        }
763    }
764#endif
765}
766
767void SkGlyphCache_Globals::validate() const {
768    size_t computedBytes = 0;
769    int computedCount = 0;
770
771    const SkGlyphCache* head = fHead;
772    while (head != nullptr) {
773        computedBytes += head->fMemoryUsed;
774        computedCount += 1;
775        head = head->fNext;
776    }
777
778    SkASSERTF(fCacheCount == computedCount, "fCacheCount: %d, computedCount: %d", fCacheCount,
779              computedCount);
780    SkASSERTF(fTotalMemoryUsed == computedBytes, "fTotalMemoryUsed: %d, computedBytes: %d",
781              fTotalMemoryUsed, computedBytes);
782}
783
784#endif
785
786///////////////////////////////////////////////////////////////////////////////
787///////////////////////////////////////////////////////////////////////////////
788
789#include "SkTypefaceCache.h"
790
791size_t SkGraphics::GetFontCacheLimit() {
792    return get_globals().getCacheSizeLimit();
793}
794
795size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
796    return get_globals().setCacheSizeLimit(bytes);
797}
798
799size_t SkGraphics::GetFontCacheUsed() {
800    return get_globals().getTotalMemoryUsed();
801}
802
803int SkGraphics::GetFontCacheCountLimit() {
804    return get_globals().getCacheCountLimit();
805}
806
807int SkGraphics::SetFontCacheCountLimit(int count) {
808    return get_globals().setCacheCountLimit(count);
809}
810
811int SkGraphics::GetFontCacheCountUsed() {
812    return get_globals().getCacheCountUsed();
813}
814
815void SkGraphics::PurgeFontCache() {
816    get_globals().purgeAll();
817    SkTypefaceCache::PurgeAll();
818}
819
820// TODO(herb): clean up TLS apis.
821size_t SkGraphics::GetTLSFontCacheLimit() { return 0; }
822void SkGraphics::SetTLSFontCacheLimit(size_t bytes) { }
823