Add skia to the repository.

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@16 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 598 insertions, 0 deletions

diff --git a/skia/sgl/SkGlyphCache.cpp b/skia/sgl/SkGlyphCache.cpp
new file mode 100644
index 0000000..f67223d
--- /dev/null
+++ b/skia/sgl/SkGlyphCache.cpp
@@ -0,0 +1,598 @@
+/* libs/graphics/sgl/SkGlyphCache.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** 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_HASHxxxxx
+
+///////////////////////////////////////////////////////////////////////////////
+
+#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
+
+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) {
+        // 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 {
+        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) {
+        // 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 {
+        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) {
+        glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
+        fGlyphHash[index] = glyph;
+    } else {
+        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) {
+        glyph = this->lookupMetrics(id, kFull_MetricsType);
+        fGlyphHash[index] = glyph;
+    } else {
+        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
+
+/*  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
+
+    cache = globals.fHead;
+    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;
+}
+