grab from latest android
git-svn-id: http://skia.googlecode.com/svn/trunk@27 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
new file mode 100644
index 0000000..6b214df
--- /dev/null
+++ b/src/core/SkGlyphCache.cpp
@@ -0,0 +1,662 @@
+/* libs/graphics/sgl/SkGlyphCache.cpp
+**
+** Copyright 2006, The Android Open Source Project
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+** http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include "SkGlyphCache.h"
+#include "SkFontHost.h"
+#include "SkPaint.h"
+#include "SkTemplates.h"
+
+#define SPEW_PURGE_STATUS
+//#define USE_CACHE_HASH
+//#define RECORD_HASH_EFFICIENCY
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef RECORD_HASH_EFFICIENCY
+ static uint32_t gHashSuccess;
+ static uint32_t gHashCollision;
+
+ static void RecordHashSuccess() {
+ gHashSuccess += 1;
+ }
+
+ static void RecordHashCollisionIf(bool pred) {
+ if (pred) {
+ gHashCollision += 1;
+
+ uint32_t total = gHashSuccess + gHashCollision;
+ SkDebugf("Font Cache Hash success rate: %d%%\n",
+ 100 * gHashSuccess / total);
+ }
+ }
+#else
+ #define RecordHashSuccess() (void)0
+ #define RecordHashCollisionIf(pred) (void)0
+#endif
+#define RecordHashCollision() RecordHashCollisionIf(true)
+
+///////////////////////////////////////////////////////////////////////////////
+
+#define kMinGlphAlloc (sizeof(SkGlyph) * 64)
+#define kMinImageAlloc (24 * 64) // should be pointsize-dependent
+
+#define METRICS_RESERVE_COUNT 128 // so we don't grow this array a lot
+
+SkGlyphCache::SkGlyphCache(const SkDescriptor* desc)
+ : fGlyphAlloc(kMinGlphAlloc), fImageAlloc(kMinImageAlloc) {
+ fPrev = fNext = NULL;
+
+ fDesc = desc->copy();
+ fScalerContext = SkScalerContext::Create(desc);
+ fScalerContext->getFontMetrics(NULL, &fFontMetricsY);
+
+ // init to 0 so that all of the pointers will be null
+ memset(fGlyphHash, 0, sizeof(fGlyphHash));
+ // init with 0xFF so that the charCode field will be -1, which is invalid
+ memset(fCharToGlyphHash, 0xFF, sizeof(fCharToGlyphHash));
+
+ fMemoryUsed = sizeof(*this) + kMinGlphAlloc + kMinImageAlloc;
+
+ fGlyphArray.setReserve(METRICS_RESERVE_COUNT);
+
+ fMetricsCount = 0;
+ fAdvanceCount = 0;
+ fAuxProcList = NULL;
+}
+
+SkGlyphCache::~SkGlyphCache() {
+ SkGlyph** gptr = fGlyphArray.begin();
+ SkGlyph** stop = fGlyphArray.end();
+ while (gptr < stop) {
+ SkPath* path = (*gptr)->fPath;
+ if (path) {
+ SkDELETE(path);
+ }
+ gptr += 1;
+ }
+ SkDescriptor::Free(fDesc);
+ SkDELETE(fScalerContext);
+ this->invokeAndRemoveAuxProcs();
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifdef SK_DEBUG
+class AutoCheckForNull {
+public:
+ AutoCheckForNull(const SkTDArray<SkGlyph*>& array) : fArray(array) {
+ for (int i = 0; i < array.count(); i++)
+ SkASSERT(array[i]);
+ }
+ ~AutoCheckForNull() {
+ const SkTDArray<SkGlyph*>& array = fArray;
+ for (int i = 0; i < array.count(); i++) {
+ SkASSERT(array[i]);
+ }
+ }
+private:
+ const SkTDArray<SkGlyph*>& fArray;
+};
+#define VALIDATE() AutoCheckForNull acfn(fGlyphArray)
+#else
+#define VALIDATE()
+#endif
+
+uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(charCode);
+ const CharGlyphRec& rec = fCharToGlyphHash[ID2HashIndex(id)];
+
+ if (rec.fID == id) {
+ return rec.fGlyph->getGlyphID();
+ } else {
+ return fScalerContext->charToGlyphID(charCode);
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(charCode);
+ CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
+
+ if (rec->fID != id) {
+ // this ID is based on the UniChar
+ rec->fID = id;
+ // this ID is based on the glyph index
+ id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
+ rec->fGlyph = this->lookupMetrics(id, kJustAdvance_MetricsType);
+ }
+ return *rec->fGlyph;
+}
+
+const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(glyphID);
+ unsigned index = ID2HashIndex(id);
+ SkGlyph* glyph = fGlyphHash[index];
+
+ if (NULL == glyph || glyph->fID != id) {
+ glyph = this->lookupMetrics(glyphID, kJustAdvance_MetricsType);
+ fGlyphHash[index] = glyph;
+ }
+ return *glyph;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(charCode);
+ CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
+
+ if (rec->fID != id) {
+ RecordHashCollisionIf(rec->fGlyph != NULL);
+ // this ID is based on the UniChar
+ rec->fID = id;
+ // this ID is based on the glyph index
+ id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
+ rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
+ } else {
+ RecordHashSuccess();
+ if (rec->fGlyph->isJustAdvance()) {
+ fScalerContext->getMetrics(rec->fGlyph);
+ }
+ }
+ SkASSERT(rec->fGlyph->isFullMetrics());
+ return *rec->fGlyph;
+}
+
+const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
+ SkFixed x, SkFixed y) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(charCode, x, y);
+ CharGlyphRec* rec = &fCharToGlyphHash[ID2HashIndex(id)];
+
+ if (rec->fID != id) {
+ RecordHashCollisionIf(rec->fGlyph != NULL);
+ // this ID is based on the UniChar
+ rec->fID = id;
+ // this ID is based on the glyph index
+ id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
+ rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
+ } else {
+ RecordHashSuccess();
+ if (rec->fGlyph->isJustAdvance()) {
+ fScalerContext->getMetrics(rec->fGlyph);
+ }
+ }
+ SkASSERT(rec->fGlyph->isFullMetrics());
+ return *rec->fGlyph;
+}
+
+const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(glyphID);
+ unsigned index = ID2HashIndex(id);
+ SkGlyph* glyph = fGlyphHash[index];
+
+ if (NULL == glyph || glyph->fID != id) {
+ RecordHashCollisionIf(glyph != NULL);
+ glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
+ fGlyphHash[index] = glyph;
+ } else {
+ RecordHashSuccess();
+ if (glyph->isJustAdvance()) {
+ fScalerContext->getMetrics(glyph);
+ }
+ }
+ SkASSERT(glyph->isFullMetrics());
+ return *glyph;
+}
+
+const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID,
+ SkFixed x, SkFixed y) {
+ VALIDATE();
+ uint32_t id = SkGlyph::MakeID(glyphID, x, y);
+ unsigned index = ID2HashIndex(id);
+ SkGlyph* glyph = fGlyphHash[index];
+
+ if (NULL == glyph || glyph->fID != id) {
+ RecordHashCollisionIf(glyph != NULL);
+ glyph = this->lookupMetrics(id, kFull_MetricsType);
+ fGlyphHash[index] = glyph;
+ } else {
+ RecordHashSuccess();
+ if (glyph->isJustAdvance()) {
+ fScalerContext->getMetrics(glyph);
+ }
+ }
+ SkASSERT(glyph->isFullMetrics());
+ return *glyph;
+}
+
+SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
+ SkGlyph* glyph;
+
+ int hi = 0;
+ int count = fGlyphArray.count();
+
+ if (count) {
+ SkGlyph** gptr = fGlyphArray.begin();
+ int lo = 0;
+
+ hi = count - 1;
+ while (lo < hi) {
+ int mid = (hi + lo) >> 1;
+ if (gptr[mid]->fID < id) {
+ lo = mid + 1;
+ } else {
+ hi = mid;
+ }
+ }
+ glyph = gptr[hi];
+ if (glyph->fID == id) {
+ if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
+ fScalerContext->getMetrics(glyph);
+ }
+ return glyph;
+ }
+
+ // check if we need to bump hi before falling though to the allocator
+ if (glyph->fID < id) {
+ hi += 1;
+ }
+ }
+
+ // not found, but hi tells us where to inser the new glyph
+ fMemoryUsed += sizeof(SkGlyph);
+
+ glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
+ SkChunkAlloc::kThrow_AllocFailType);
+ glyph->fID = id;
+ glyph->fImage = NULL;
+ glyph->fPath = NULL;
+ *fGlyphArray.insert(hi) = glyph;
+
+ if (kJustAdvance_MetricsType == mtype) {
+ fScalerContext->getAdvance(glyph);
+ fAdvanceCount += 1;
+ } else {
+ SkASSERT(kFull_MetricsType == mtype);
+ fScalerContext->getMetrics(glyph);
+ fMetricsCount += 1;
+ }
+
+ return glyph;
+}
+
+const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
+ if (glyph.fWidth) {
+ if (glyph.fImage == NULL) {
+ size_t size = glyph.computeImageSize();
+ const_cast<SkGlyph&>(glyph).fImage = fImageAlloc.alloc(size,
+ SkChunkAlloc::kReturnNil_AllocFailType);
+ fScalerContext->getImage(glyph);
+ fMemoryUsed += size;
+ }
+ }
+ return glyph.fImage;
+}
+
+const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
+ if (glyph.fWidth) {
+ if (glyph.fPath == NULL) {
+ const_cast<SkGlyph&>(glyph).fPath = SkNEW(SkPath);
+ fScalerContext->getPath(glyph, glyph.fPath);
+ fMemoryUsed += sizeof(SkPath) +
+ glyph.fPath->getPoints(NULL, 0x7FFFFFFF) * sizeof(SkPoint);
+ }
+ }
+ return glyph.fPath;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
+ const AuxProcRec* rec = fAuxProcList;
+ while (rec) {
+ if (rec->fProc == proc) {
+ if (dataPtr) {
+ *dataPtr = rec->fData;
+ }
+ return true;
+ }
+ rec = rec->fNext;
+ }
+ return false;
+}
+
+void SkGlyphCache::setAuxProc(void (*proc)(void*), void* data) {
+ if (proc == NULL) {
+ return;
+ }
+
+ AuxProcRec* rec = fAuxProcList;
+ while (rec) {
+ if (rec->fProc == proc) {
+ rec->fData = data;
+ return;
+ }
+ rec = rec->fNext;
+ }
+ // not found, create a new rec
+ rec = SkNEW(AuxProcRec);
+ rec->fProc = proc;
+ rec->fData = data;
+ rec->fNext = fAuxProcList;
+ fAuxProcList = rec;
+}
+
+void SkGlyphCache::removeAuxProc(void (*proc)(void*)) {
+ AuxProcRec* rec = fAuxProcList;
+ AuxProcRec* prev = NULL;
+ while (rec) {
+ AuxProcRec* next = rec->fNext;
+ if (rec->fProc == proc) {
+ if (prev) {
+ prev->fNext = next;
+ } else {
+ fAuxProcList = next;
+ }
+ SkDELETE(rec);
+ return;
+ }
+ prev = rec;
+ rec = next;
+ }
+}
+
+void SkGlyphCache::invokeAndRemoveAuxProcs() {
+ AuxProcRec* rec = fAuxProcList;
+ while (rec) {
+ rec->fProc(rec->fData);
+ AuxProcRec* next = rec->fNext;
+ SkDELETE(rec);
+ rec = next;
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+#include "SkGlobals.h"
+#include "SkThread.h"
+
+#define SkGlyphCache_GlobalsTag SkSetFourByteTag('g', 'l', 'f', 'c')
+
+#ifdef USE_CACHE_HASH
+ #define HASH_BITCOUNT 6
+ #define HASH_COUNT (1 << HASH_BITCOUNT)
+ #define HASH_MASK (HASH_COUNT - 1)
+
+ static unsigned desc_to_hashindex(const SkDescriptor* desc)
+ {
+ SkASSERT(HASH_MASK < 256); // since our munging reduces to 8 bits
+
+ uint32_t n = *(const uint32_t*)desc; //desc->getChecksum();
+ SkASSERT(n == desc->getChecksum());
+
+ // don't trust that the low bits of checksum vary enough, so...
+ n ^= (n >> 24) ^ (n >> 16) ^ (n >> 8) ^ (n >> 30);
+
+ return n & HASH_MASK;
+ }
+#endif
+
+class SkGlyphCache_Globals : public SkGlobals::Rec {
+public:
+ SkMutex fMutex;
+ SkGlyphCache* fHead;
+ size_t fTotalMemoryUsed;
+#ifdef USE_CACHE_HASH
+ SkGlyphCache* fHash[HASH_COUNT];
+#endif
+
+#ifdef SK_DEBUG
+ void validate() const;
+#else
+ void validate() const {}
+#endif
+};
+
+#ifdef SK_USE_RUNTIME_GLOBALS
+ static SkGlobals::Rec* create_globals() {
+ SkGlyphCache_Globals* rec = SkNEW(SkGlyphCache_Globals);
+ rec->fHead = NULL;
+ rec->fTotalMemoryUsed = 0;
+#ifdef USE_CACHE_HASH
+ memset(rec->fHash, 0, sizeof(rec->fHash));
+#endif
+ return rec;
+ }
+
+ #define FIND_GC_GLOBALS() *(SkGlyphCache_Globals*)SkGlobals::Find(SkGlyphCache_GlobalsTag, create_globals)
+ #define GET_GC_GLOBALS() *(SkGlyphCache_Globals*)SkGlobals::Get(SkGlyphCache_GlobalsTag)
+#else
+ static SkGlyphCache_Globals gGCGlobals;
+ #define FIND_GC_GLOBALS() gGCGlobals
+ #define GET_GC_GLOBALS() gGCGlobals
+#endif
+
+void SkGlyphCache::VisitAllCaches(bool (*proc)(SkGlyphCache*, void*),
+ void* context) {
+ SkGlyphCache_Globals& globals = FIND_GC_GLOBALS();
+ SkAutoMutexAcquire ac(globals.fMutex);
+ SkGlyphCache* cache;
+
+ globals.validate();
+
+ for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+ if (proc(cache, context)) {
+ break;
+ }
+ }
+
+ globals.validate();
+}
+
+/* This guy calls the visitor from within the mutext lock, so the visitor
+ cannot:
+ - take too much time
+ - try to acquire the mutext again
+ - call a fontscaler (which might call into the cache)
+*/
+SkGlyphCache* SkGlyphCache::VisitCache(const SkDescriptor* desc,
+ bool (*proc)(const SkGlyphCache*, void*),
+ void* context) {
+ SkASSERT(desc);
+
+ SkGlyphCache_Globals& globals = FIND_GC_GLOBALS();
+ SkAutoMutexAcquire ac(globals.fMutex);
+ SkGlyphCache* cache;
+ bool insideMutex = true;
+
+ globals.validate();
+
+#ifdef USE_CACHE_HASH
+ SkGlyphCache** hash = globals.fHash;
+ unsigned index = desc_to_hashindex(desc);
+ cache = hash[index];
+ if (cache && *cache->fDesc == *desc) {
+ cache->detach(&globals.fHead);
+ goto FOUND_IT;
+ }
+#endif
+
+ for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+ if (cache->fDesc->equals(*desc)) {
+ cache->detach(&globals.fHead);
+ goto FOUND_IT;
+ }
+ }
+
+ /* Release the mutex now, before we create a new entry (which might have
+ side-effects like trying to access the cache/mutex (yikes!)
+ */
+ ac.release(); // release the mutex now
+ insideMutex = false; // can't use globals anymore
+
+ cache = SkNEW_ARGS(SkGlyphCache, (desc));
+
+FOUND_IT:
+ if (proc(cache, context)) { // stay detached
+ if (insideMutex) {
+ SkASSERT(globals.fTotalMemoryUsed >= cache->fMemoryUsed);
+ globals.fTotalMemoryUsed -= cache->fMemoryUsed;
+#ifdef USE_CACHE_HASH
+ hash[index] = NULL;
+#endif
+ }
+ } else { // reattach
+ if (insideMutex) {
+ cache->attachToHead(&globals.fHead);
+#ifdef USE_CACHE_HASH
+ hash[index] = cache;
+#endif
+ } else {
+ AttachCache(cache);
+ }
+ cache = NULL;
+ }
+ return cache;
+}
+
+void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
+ SkASSERT(cache);
+ SkASSERT(cache->fNext == NULL);
+
+ SkGlyphCache_Globals& globals = GET_GC_GLOBALS();
+ SkAutoMutexAcquire ac(globals.fMutex);
+
+ globals.validate();
+
+ // if we have a fixed budget for our cache, do a purge here
+ {
+ size_t allocated = globals.fTotalMemoryUsed + cache->fMemoryUsed;
+ size_t amountToFree = SkFontHost::ShouldPurgeFontCache(allocated);
+ if (amountToFree)
+ (void)InternalFreeCache(&globals, amountToFree);
+ }
+
+ cache->attachToHead(&globals.fHead);
+ globals.fTotalMemoryUsed += cache->fMemoryUsed;
+
+#ifdef USE_CACHE_HASH
+ unsigned index = desc_to_hashindex(cache->fDesc);
+ SkASSERT(globals.fHash[index] != cache);
+ globals.fHash[index] = cache;
+#endif
+
+ globals.validate();
+}
+
+size_t SkGlyphCache::GetCacheUsed() {
+ SkGlyphCache_Globals& globals = FIND_GC_GLOBALS();
+ SkAutoMutexAcquire ac(globals.fMutex);
+
+ return SkGlyphCache::ComputeMemoryUsed(globals.fHead);
+}
+
+bool SkGlyphCache::SetCacheUsed(size_t bytesUsed) {
+ size_t curr = SkGlyphCache::GetCacheUsed();
+
+ if (curr > bytesUsed) {
+ SkGlyphCache_Globals& globals = FIND_GC_GLOBALS();
+ SkAutoMutexAcquire ac(globals.fMutex);
+
+ return InternalFreeCache(&globals, curr - bytesUsed) > 0;
+ }
+ return false;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
+ if (cache) {
+ while (cache->fNext) {
+ cache = cache->fNext;
+ }
+ }
+ return cache;
+}
+
+size_t SkGlyphCache::ComputeMemoryUsed(const SkGlyphCache* head) {
+ size_t size = 0;
+
+ while (head != NULL) {
+ size += head->fMemoryUsed;
+ head = head->fNext;
+ }
+ return size;
+}
+
+#ifdef SK_DEBUG
+void SkGlyphCache_Globals::validate() const {
+ size_t computed = SkGlyphCache::ComputeMemoryUsed(fHead);
+ if (fTotalMemoryUsed != computed) {
+ printf("total %d, computed %d\n", (int)fTotalMemoryUsed, (int)computed);
+ }
+ SkASSERT(fTotalMemoryUsed == computed);
+}
+#endif
+
+size_t SkGlyphCache::InternalFreeCache(SkGlyphCache_Globals* globals,
+ size_t bytesNeeded) {
+ globals->validate();
+
+ size_t bytesFreed = 0;
+ int count = 0;
+
+ // don't do any "small" purges
+ size_t minToPurge = globals->fTotalMemoryUsed >> 2;
+ if (bytesNeeded < minToPurge)
+ bytesNeeded = minToPurge;
+
+ SkGlyphCache* cache = FindTail(globals->fHead);
+ while (cache != NULL && bytesFreed < bytesNeeded) {
+ SkGlyphCache* prev = cache->fPrev;
+ bytesFreed += cache->fMemoryUsed;
+
+#ifdef USE_CACHE_HASH
+ unsigned index = desc_to_hashindex(cache->fDesc);
+ if (cache == globals->fHash[index]) {
+ globals->fHash[index] = NULL;
+ }
+#endif
+
+ cache->detach(&globals->fHead);
+ SkDELETE(cache);
+ cache = prev;
+ count += 1;
+ }
+
+ SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
+ globals->fTotalMemoryUsed -= bytesFreed;
+ globals->validate();
+
+#ifdef SPEW_PURGE_STATUS
+ if (count) {
+ SkDebugf("purging %dK from font cache [%d entries]\n",
+ (int)(bytesFreed >> 10), count);
+ }
+#endif
+
+ return bytesFreed;
+}
+