Make the glyph array entries inline.

src/core/SkGlyphCache.cpp

 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkGlyphCache.h"
 #include "SkGlyphCache_Globals.h"
 #include "SkGraphics.h"
@@ skipping 49 matching lines @@
         : fScalerContext(ctx), fGlyphAlloc(kMinAllocAmount) {
     SkASSERT(typeface);
     SkASSERT(desc);
     SkASSERT(ctx);
 
     fPrev = fNext = NULL;
 
     fDesc = desc->copy();
     fScalerContext->getFontMetrics(&fFontMetrics);
 
     // init to 0 so that all of the pointers will be null

[reed1, 2015/01/30 13:57:38]

comment (0) disagrees with the code (0xFF)

I'm guessing 0xFFFF is your invalid glyph index?
Can we store a glyph at slot 0 that never matches (e.g. glyphindex == 0xFFFF) to
void the double check?

[herb_g, 2015/02/01 05:09:27]

Done.

-    memset(fGlyphHash, 0, sizeof(fGlyphHash));
-            
+    memset(fGlyphHash, 0xFF, sizeof(fGlyphHash));
+
     fMemoryUsed = sizeof(*this);
 
     fGlyphArray.setReserve(kMinGlyphCount);
 
     fAuxProcList = NULL;
 
 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
     fHashHitCount = fHashMissCount = 0;
 #endif
 }
@@ skipping 16 matching lines @@
             if (g.fImage) {
                 imageUsed += g.fHeight * g.rowBytes();
             }
         }
 
         SkDebugf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n",
                  ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(CharGlyphRec) * kHashCount, uniHashUsed);
 
     }
 #endif
-    SkGlyph**   gptr = fGlyphArray.begin();
-    SkGlyph**   stop = fGlyphArray.end();
+    SkGlyph*   gptr = fGlyphArray.begin();
+    SkGlyph*   stop = fGlyphArray.end();
     while (gptr < stop) {
-        SkPath* path = (*gptr)->fPath;
+        SkPath* path = gptr->fPath;
         if (path) {
             SkDELETE(path);
         }
         gptr += 1;
     }
     SkDescriptor::Free(fDesc);
     SkDELETE(fScalerContext);
     this->invokeAndRemoveAuxProcs();
 }
 
+
 SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
     if (NULL == fCharToGlyphHash.get()) {
         fCharToGlyphHash.reset(kHashCount);
         // init with 0xFF so that the charCode field will be -1, which is invalid
         memset(fCharToGlyphHash.get(), 0xFF,
                sizeof(CharGlyphRec) * kHashCount);
     }
     
     return &fCharToGlyphHash[ID2HashIndex(id)];
 }
 
+void SkGlyphCache::adjustCaches(int16_t insertion_index) {
+    for (int i = 0; i < kHashCount; ++i) {
+        // Beware: the following code uses the wrap around behavior of the
+        // unsigned unint16_t to change the kInvalidGlyph value to zero allowing
+        // a single comparison for if the index needs to be incremented.
+        // This trick is also used below.
+        if (fGlyphHash[i] + 1 >= insertion_index + 1) {
+            fGlyphHash[i] += 1;
+        }
+    }
+    if (fCharToGlyphHash.get() != NULL) {
+        for (int i = 0; i < kHashCount; ++i) {
+            // See the warning about about the following code.
+            if (fCharToGlyphHash[i].fGlyphIndex + 1 >= insertion_index + 1) {
+                fCharToGlyphHash[i].fGlyphIndex += 1;
+            }
+        }
+    }
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
 #define VALIDATE()  AutoValidate av(this)
 #else
 #define VALIDATE()
 #endif
 
 uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
     VALIDATE();
     uint32_t id = SkGlyph::MakeID(charCode);
     const CharGlyphRec& rec = *this->getCharGlyphRec(id);
 
     if (rec.fID == id) {
-        return rec.fGlyph->getGlyphID();
+        return fGlyphArray[rec.fGlyphIndex].getGlyphID();
     } else {
         return fScalerContext->charToGlyphID(charCode);
     }
 }
 
 SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
     return fScalerContext->glyphIDToChar(glyphID);
 }
 
 unsigned SkGlyphCache::getGlyphCount() {
     return fScalerContext->getGlyphCount();
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    CharGlyphRec* rec = this->getCharGlyphRec(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;
+    return *maintainCharCache(charCode, kJustAdvance_MetricsType);
 }
 
 const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
     VALIDATE();
     uint32_t id = SkGlyph::MakeID(glyphID);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
+    return *maintainGlyphCache(id, kJustAdvance_MetricsType);
 
-    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 = this->getCharGlyphRec(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;
+    return *maintainCharCache(charCode, kFull_MetricsType);
 }
 
 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
                                                SkFixed x, SkFixed y) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode, x, y);
-    CharGlyphRec* rec = this->getCharGlyphRec(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;
+    return *maintainCharCache(charCode, kFull_MetricsType, x, y);
 }
 
 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;
+    return *this->maintainGlyphCache(id, kFull_MetricsType);
 }
 
 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];
+    return *this->maintainGlyphCache(id, kFull_MetricsType);
+}
 
-    if (NULL == glyph || glyph->fID != id) {
-        RecordHashCollisionIf(glyph != NULL);
-        glyph = this->lookupMetrics(id, kFull_MetricsType);
-        fGlyphHash[index] = glyph;
+SkGlyph* SkGlyphCache::maintainCharCache(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
+    uint32_t id = SkGlyph::MakeID(charCode, x, y);
+    CharGlyphRec* rec = this->getCharGlyphRec(id);
+    SkGlyph* glyph;
+    if (rec->fID != id) {
+        RecordHashCollisionIf(rec->fGlyph != kInvalidGlyph);
+        // 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->fGlyphIndex = this->lookupMetrics(id, kFull_MetricsType);
+        glyph = &fGlyphArray[rec->fGlyphIndex];
     } else {
         RecordHashSuccess();
-        if (glyph->isJustAdvance()) {
+        glyph = &fGlyphArray[rec->fGlyphIndex];
+        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
             fScalerContext->getMetrics(glyph);
         }
     }
     SkASSERT(glyph->isFullMetrics());
-    return *glyph;
+    return glyph;
 }
 
-SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
+SkGlyph* SkGlyphCache::maintainGlyphCache(uint32_t id, MetricsType type) {
+    uint32_t hash_index = ID2HashIndex(id);
+    uint16_t glyph_index = fGlyphHash[hash_index];
     SkGlyph* glyph;
+    
+    if (kInvalidGlyph == glyph_index
+        || (glyph = &fGlyphArray[glyph_index])->fID != id) {
+        RecordHashCollisionIf(glyph != NULL);
+        glyph_index = this->lookupMetrics(id, type);
+        fGlyphHash[hash_index] = glyph_index;
+        glyph = &fGlyphArray[glyph_index];
+    } else {
+        RecordHashSuccess();
+        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
+           fScalerContext->getMetrics(glyph);
+        }
+        SkASSERT(glyph->isFullMetrics());
+    }
+    return glyph;
+}
 
-    int     hi = 0;
-    int     count = fGlyphArray.count();
-
-    if (count) {
-        SkGlyph**   gptr = fGlyphArray.begin();
-        int     lo = 0;
-
+uint16_t SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
+    uint16_t glyph_index = 0;
+    int      count = fGlyphArray.count();
+    int      hi = 0;
+  
+    if (count > 0) {
+        SkGlyph* gptr = fGlyphArray.begin();
+        int lo = 0;
+    
         hi = count - 1;
         while (lo < hi) {
             int mid = (hi + lo) >> 1;
-            if (gptr[mid]->fID < id) {
+            if (gptr[mid].fID < id) {
                 lo = mid + 1;
             } else {
                 hi = mid;
             }
         }
-        glyph = gptr[hi];
+        glyph_index = hi;
+        SkGlyph* glyph = &gptr[hi];
         if (glyph->fID == id) {
             if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
                 fScalerContext->getMetrics(glyph);
             }
-            return glyph;
+            return glyph_index;
         }
-
+    
         // check if we need to bump hi before falling though to the allocator
         if (glyph->fID < id) {
-            hi += 1;
+            glyph_index += 1;
         }
     }
-
+  
     // not found, but hi tells us where to inser the new glyph
     fMemoryUsed += sizeof(SkGlyph);
+  
+    this->adjustCaches(glyph_index);
 
-    glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
-                                        SkChunkAlloc::kThrow_AllocFailType);
+    SkGlyph* glyph = fGlyphArray.insert(glyph_index);
     glyph->init(id);
-    *fGlyphArray.insert(hi) = glyph;
 
     if (kJustAdvance_MetricsType == mtype) {
         fScalerContext->getAdvance(glyph);
     } else {
         SkASSERT(kFull_MetricsType == mtype);
         fScalerContext->getMetrics(glyph);
     }
 
-    return glyph;
+    return glyph_index;
 }
 
 const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
     if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
         if (NULL == glyph.fImage) {
             size_t  size = glyph.computeImageSize();
             const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size,
                                         SkChunkAlloc::kReturnNil_AllocFailType);
             // check that alloc() actually succeeded
             if (glyph.fImage) {
@@ skipping 408 matching lines @@
     return tls ? tls->getCacheSizeLimit() : 0;
 }
 
 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) {
     if (0 == bytes) {
         SkGlyphCache_Globals::DeleteTLS();
     } else {
         SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes);
     }
 }