add counting to Globals, and refactor some for clarity

BUG=

Review URL: https://codereview.chromium.org/24447003

git-svn-id: http://skia.googlecode.com/svn/trunk/src@11484 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/core/SkGlyphCache.cpp b/core/SkGlyphCache.cpp
index 538c968..9dd235c 100644
--- a/core/SkGlyphCache.cpp
+++ b/core/SkGlyphCache.cpp
@@ -8,6 +8,7 @@
 
 
 #include "SkGlyphCache.h"
+#include "SkGlyphCache_Globals.h"
 #include "SkGraphics.h"
 #include "SkPaint.h"
 #include "SkPath.h"
@@ -20,6 +21,20 @@
 
 bool gSkSuppressFontCachePurgeSpew;
 
+// Returns the shared globals
+static SkGlyphCache_Globals& getSharedGlobals() {
+    // we leak this, so we don't incur any shutdown cost of the destructor
+    static SkGlyphCache_Globals* gGlobals = SkNEW_ARGS(SkGlyphCache_Globals,
+                                                       (SkGlyphCache_Globals::kYes_UseMutex));
+    return *gGlobals;
+}
+
+// Returns the TLS globals (if set), or the shared globals
+static SkGlyphCache_Globals& getGlobals() {
+    SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
+    return tls ? *tls : getSharedGlobals();
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef RECORD_HASH_EFFICIENCY
@@ -397,108 +412,38 @@
 ///////////////////////////////////////////////////////////////////////////////
 ///////////////////////////////////////////////////////////////////////////////
 
-#ifndef SK_DEFAULT_FONT_CACHE_LIMIT
-    #define SK_DEFAULT_FONT_CACHE_LIMIT     (2 * 1024 * 1024)
-#endif
-
 #include "SkThread.h"
 
-class SkGlyphCache_Globals {
-public:
-    enum UseMutex {
-        kNo_UseMutex,  // thread-local cache
-        kYes_UseMutex  // shared cache
-    };
-
-    SkGlyphCache_Globals(UseMutex um) {
-        fHead = NULL;
-        fTotalMemoryUsed = 0;
-        fFontCacheLimit = SK_DEFAULT_FONT_CACHE_LIMIT;
-        fMutex = (kYes_UseMutex == um) ? SkNEW(SkMutex) : NULL;
-    }
-
-    ~SkGlyphCache_Globals() {
-        SkGlyphCache* cache = fHead;
-        while (cache) {
-            SkGlyphCache* next = cache->fNext;
-            SkDELETE(cache);
-            cache = next;
-        }
-
-        SkDELETE(fMutex);
-    }
-
-    SkMutex*        fMutex;
-    SkGlyphCache*   fHead;
-    size_t          fTotalMemoryUsed;
-
-#ifdef SK_DEBUG
-    void validate() const;
-#else
-    void validate() const {}
-#endif
-
-    size_t  getFontCacheLimit() const { return fFontCacheLimit; }
-    size_t  setFontCacheLimit(size_t limit);
-    void    purgeAll(); // does not change budget
-
-    // can return NULL
-    static SkGlyphCache_Globals* FindTLS() {
-        return (SkGlyphCache_Globals*)SkTLS::Find(CreateTLS);
-    }
-
-    static SkGlyphCache_Globals& GetTLS() {
-        return *(SkGlyphCache_Globals*)SkTLS::Get(CreateTLS, DeleteTLS);
-    }
-
-    static void DeleteTLS() { SkTLS::Delete(CreateTLS); }
-
-private:
-    size_t  fFontCacheLimit;
-
-    static void* CreateTLS() {
-        return SkNEW_ARGS(SkGlyphCache_Globals, (kNo_UseMutex));
-    }
-
-    static void DeleteTLS(void* ptr) {
-        SkDELETE((SkGlyphCache_Globals*)ptr);
-    }
-};
-
-size_t SkGlyphCache_Globals::setFontCacheLimit(size_t newLimit) {
+size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
     static const size_t minLimit = 256 * 1024;
     if (newLimit < minLimit) {
         newLimit = minLimit;
     }
-
-    size_t prevLimit = fFontCacheLimit;
-    fFontCacheLimit = newLimit;
-
-    size_t currUsed = fTotalMemoryUsed;
-    if (currUsed > newLimit) {
-        SkAutoMutexAcquire    ac(fMutex);
-        SkGlyphCache::InternalFreeCache(this, currUsed - newLimit);
-    }
+    
+    SkAutoMutexAcquire    ac(fMutex);
+    
+    size_t prevLimit = fCacheSizeLimit;
+    fCacheSizeLimit = newLimit;
+    this->internalPurge();
     return prevLimit;
 }
 
+int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
+    if (newCount < 0) {
+        newCount = 0;
+    }
+    
+    SkAutoMutexAcquire    ac(fMutex);
+    
+    int prevCount = fCacheCountLimit;
+    fCacheCountLimit = newCount;
+    this->internalPurge();
+    return prevCount;
+}
+
 void SkGlyphCache_Globals::purgeAll() {
     SkAutoMutexAcquire    ac(fMutex);
-    SkGlyphCache::InternalFreeCache(this, fTotalMemoryUsed);
-}
-
-// Returns the shared globals
-static SkGlyphCache_Globals& getSharedGlobals() {
-    // we leak this, so we don't incur any shutdown cost of the destructor
-    static SkGlyphCache_Globals* gGlobals = SkNEW_ARGS(SkGlyphCache_Globals,
-                                       (SkGlyphCache_Globals::kYes_UseMutex));
-    return *gGlobals;
-}
-
-// Returns the TLS globals (if set), or the shared globals
-static SkGlyphCache_Globals& getGlobals() {
-    SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
-    return tls ? *tls : getSharedGlobals();
+    this->internalPurge(fTotalMemoryUsed);
 }
 
 void SkGlyphCache::VisitAllCaches(bool (*proc)(SkGlyphCache*, void*),
@@ -509,7 +454,7 @@
 
     globals.validate();
 
-    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+    for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
         if (proc(cache, context)) {
             break;
         }
@@ -540,9 +485,9 @@
 
     globals.validate();
 
-    for (cache = globals.fHead; cache != NULL; cache = cache->fNext) {
+    for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
         if (cache->fDesc->equals(*desc)) {
-            cache->detach(&globals.fHead);
+            globals.internalDetachCache(cache);
             goto FOUND_IT;
         }
     }
@@ -572,16 +517,11 @@
 
     AutoValidate av(cache);
 
-    if (proc(cache, context)) {   // stay detached
+    if (!proc(cache, context)) {   // need to reattach
         if (insideMutex) {
-            SkASSERT(globals.fTotalMemoryUsed >= cache->fMemoryUsed);
-            globals.fTotalMemoryUsed -= cache->fMemoryUsed;
-        }
-    } else {                        // reattach
-        if (insideMutex) {
-            cache->attachToHead(&globals.fHead);
+            globals.internalAttachCacheToHead(cache);
         } else {
-            AttachCache(cache);
+            globals.attachCacheToHead(cache);
         }
         cache = NULL;
     }
@@ -592,30 +532,23 @@
     SkASSERT(cache);
     SkASSERT(cache->fNext == NULL);
 
-    SkGlyphCache_Globals& globals = getGlobals();
-    SkAutoMutexAcquire    ac(globals.fMutex);
-
-    globals.validate();
-    cache->validate();
-
-    // if we have a fixed budget for our cache, do a purge here
-    {
-        size_t allocated = globals.fTotalMemoryUsed + cache->fMemoryUsed;
-        size_t budgeted = globals.getFontCacheLimit();
-        if (allocated > budgeted) {
-            (void)InternalFreeCache(&globals, allocated - budgeted);
-        }
-    }
-
-    cache->attachToHead(&globals.fHead);
-    globals.fTotalMemoryUsed += cache->fMemoryUsed;
-
-    globals.validate();
+    getGlobals().attachCacheToHead(cache);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
-SkGlyphCache* SkGlyphCache::FindTail(SkGlyphCache* cache) {
+void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
+    SkAutoMutexAcquire    ac(fMutex);
+
+    this->validate();
+    cache->validate();
+
+    this->internalAttachCacheToHead(cache);
+    this->internalPurge();
+}
+
+SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
+    SkGlyphCache* cache = fHead;
     if (cache) {
         while (cache->fNext) {
             cache = cache->fNext;
@@ -624,63 +557,92 @@
     return cache;
 }
 
-#ifdef SK_DEBUG
-void SkGlyphCache_Globals::validate() const {
-    size_t computed = 0;
+size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
+    this->validate();
 
-    const SkGlyphCache* head = fHead;
-    while (head != NULL) {
-        computed += head->fMemoryUsed;
-        head = head->fNext;
+    size_t bytesNeeded = 0;
+    if (fTotalMemoryUsed > fCacheSizeLimit) {
+        bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
+    }
+    bytesNeeded = SkMax32(bytesNeeded, minBytesNeeded);
+    if (bytesNeeded) {
+        // no small purges!
+        bytesNeeded = SkMax32(bytesNeeded, fTotalMemoryUsed >> 2);
     }
 
-    if (fTotalMemoryUsed != computed) {
-        printf("total %d, computed %d\n", (int)fTotalMemoryUsed, (int)computed);
+    int countNeeded = 0;
+    if (fCacheCount > fCacheCountLimit) {
+        countNeeded = fCacheCount - fCacheCountLimit;
+        // no small purges!
+        countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
     }
-    SkASSERT(fTotalMemoryUsed == computed);
-}
-#endif
 
-size_t SkGlyphCache::InternalFreeCache(SkGlyphCache_Globals* globals,
-                                       size_t bytesNeeded) {
-    globals->validate();
+    // early exit
+    if (!countNeeded && !bytesNeeded) {
+        return 0;
+    }
 
     size_t  bytesFreed = 0;
-    int     count = 0;
+    int     countFreed = 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) {
+    // we start at the tail and proceed backwards, as the linklist is in LRU
+    // order, with unimportant entries at the tail.
+    SkGlyphCache* cache = this->internalGetTail();
+    while (cache != NULL &&
+           (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
         SkGlyphCache* prev = cache->fPrev;
         bytesFreed += cache->fMemoryUsed;
+        countFreed += 1;
 
-        cache->detach(&globals->fHead);
+        this->internalDetachCache(cache);
         SkDELETE(cache);
         cache = prev;
-        count += 1;
     }
 
-    SkASSERT(bytesFreed <= globals->fTotalMemoryUsed);
-    globals->fTotalMemoryUsed -= bytesFreed;
-    globals->validate();
+    this->validate();
 
 #ifdef SPEW_PURGE_STATUS
-    if (count && !gSkSuppressFontCachePurgeSpew) {
+    if (countFreed && !gSkSuppressFontCachePurgeSpew) {
         SkDebugf("purging %dK from font cache [%d entries]\n",
-                 (int)(bytesFreed >> 10), count);
+                 (int)(bytesFreed >> 10), countFreed);
     }
 #endif
 
     return bytesFreed;
 }
 
+void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
+    SkASSERT(NULL == cache->fPrev && NULL == cache->fNext);
+    if (fHead) {
+        fHead->fPrev = cache;
+        cache->fNext = fHead;
+    }
+    fHead = cache;
+    
+    fCacheCount += 1;
+    fTotalMemoryUsed += cache->fMemoryUsed;
+}
+
+void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
+    SkASSERT(fCacheCount > 0);
+    fCacheCount -= 1;
+    fTotalMemoryUsed -= cache->fMemoryUsed;
+
+    if (cache->fPrev) {
+        cache->fPrev->fNext = cache->fNext;
+    } else {
+        fHead = cache->fNext;
+    }
+    if (cache->fNext) {
+        cache->fNext->fPrev = cache->fPrev;
+    }
+    cache->fPrev = cache->fNext = NULL;
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
+
 void SkGlyphCache::validate() const {
 #ifdef SK_DEBUG_GLYPH_CACHE
     int count = fGlyphArray.count();
@@ -694,6 +656,22 @@
     }
 #endif
 }
+
+void SkGlyphCache_Globals::validate() const {
+    size_t computedBytes = 0;
+    int computedCount = 0;
+    
+    const SkGlyphCache* head = fHead;
+    while (head != NULL) {
+        computedBytes += head->fMemoryUsed;
+        computedCount += 1;
+        head = head->fNext;
+    }
+    
+    SkASSERT(fTotalMemoryUsed == computedBytes);
+    SkASSERT(fCacheCount == computedCount);
+}
+
 #endif
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -702,15 +680,27 @@
 #include "SkTypefaceCache.h"
 
 size_t SkGraphics::GetFontCacheLimit() {
-    return getSharedGlobals().getFontCacheLimit();
+    return getSharedGlobals().getCacheSizeLimit();
 }
 
 size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
-    return getSharedGlobals().setFontCacheLimit(bytes);
+    return getSharedGlobals().setCacheSizeLimit(bytes);
 }
 
 size_t SkGraphics::GetFontCacheUsed() {
-    return getSharedGlobals().fTotalMemoryUsed;
+    return getSharedGlobals().getTotalMemoryUsed();
+}
+
+int SkGraphics::GetFontCacheCountLimit() {
+    return getSharedGlobals().getCacheCountLimit();
+}
+
+int SkGraphics::SetFontCacheCountLimit(int count) {
+    return getSharedGlobals().setCacheCountLimit(count);
+}
+
+int SkGraphics::GetFontCacheCountUsed() {
+    return getSharedGlobals().getCacheCountUsed();
 }
 
 void SkGraphics::PurgeFontCache() {
@@ -720,13 +710,13 @@
 
 size_t SkGraphics::GetTLSFontCacheLimit() {
     const SkGlyphCache_Globals* tls = SkGlyphCache_Globals::FindTLS();
-    return tls ? tls->getFontCacheLimit() : 0;
+    return tls ? tls->getCacheSizeLimit() : 0;
 }
 
 void SkGraphics::SetTLSFontCacheLimit(size_t bytes) {
     if (0 == bytes) {
         SkGlyphCache_Globals::DeleteTLS();
     } else {
-        SkGlyphCache_Globals::GetTLS().setFontCacheLimit(bytes);
+        SkGlyphCache_Globals::GetTLS().setCacheSizeLimit(bytes);
     }
 }
diff --git a/core/SkGlyphCache.h b/core/SkGlyphCache.h
index 3da7a22..8447337 100644
--- a/core/SkGlyphCache.h
+++ b/core/SkGlyphCache.h
@@ -197,27 +197,6 @@
     SkGlyph* lookupMetrics(uint32_t id, MetricsType);
     static bool DetachProc(const SkGlyphCache*, void*) { return true; }
 
-    void detach(SkGlyphCache** head) {
-        if (fPrev) {
-            fPrev->fNext = fNext;
-        } else {
-            *head = fNext;
-        }
-        if (fNext) {
-            fNext->fPrev = fPrev;
-        }
-        fPrev = fNext = NULL;
-    }
-
-    void attachToHead(SkGlyphCache** head) {
-        SkASSERT(NULL == fPrev && NULL == fNext);
-        if (*head) {
-            (*head)->fPrev = this;
-            fNext = *head;
-        }
-        *head = this;
-    }
-
     SkGlyphCache*       fNext, *fPrev;
     SkDescriptor*       fDesc;
     SkScalerContext*    fScalerContext;
@@ -258,9 +237,6 @@
     AuxProcRec* fAuxProcList;
     void invokeAndRemoveAuxProcs();
 
-    // This relies on the caller to have already acquired the mutex to access the global cache
-    static size_t InternalFreeCache(SkGlyphCache_Globals*, size_t bytesNeeded);
-
     inline static SkGlyphCache* FindTail(SkGlyphCache* head);
 
     friend class SkGlyphCache_Globals;
diff --git a/core/SkGlyphCache_Globals.h b/core/SkGlyphCache_Globals.h
new file mode 100644
index 0000000..20b0f29
--- /dev/null
+++ b/core/SkGlyphCache_Globals.h
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2010 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkGlyphCache_Globals_DEFINED
+#define SkGlyphCache_Globals_DEFINED
+
+#include "SkGlyphCache.h"
+#include "SkTLS.h"
+
+#ifndef SK_DEFAULT_FONT_CACHE_COUNT_LIMIT
+    #define SK_DEFAULT_FONT_CACHE_COUNT_LIMIT   256
+#endif
+
+#ifndef SK_DEFAULT_FONT_CACHE_LIMIT
+    #define SK_DEFAULT_FONT_CACHE_LIMIT     (2 * 1024 * 1024)
+#endif
+
+///////////////////////////////////////////////////////////////////////////////
+
+class SkMutex;
+
+class SkGlyphCache_Globals {
+public:
+    enum UseMutex {
+        kNo_UseMutex,  // thread-local cache
+        kYes_UseMutex  // shared cache
+    };
+    
+    SkGlyphCache_Globals(UseMutex um) {
+        fHead = NULL;
+        fTotalMemoryUsed = 0;
+        fCacheSizeLimit = SK_DEFAULT_FONT_CACHE_LIMIT;
+        fCacheCount = 0;
+        fCacheCountLimit = SK_DEFAULT_FONT_CACHE_COUNT_LIMIT;
+    
+        fMutex = (kYes_UseMutex == um) ? SkNEW(SkMutex) : NULL;
+    }
+    
+    ~SkGlyphCache_Globals() {
+        SkGlyphCache* cache = fHead;
+        while (cache) {
+            SkGlyphCache* next = cache->fNext;
+            SkDELETE(cache);
+            cache = next;
+        }
+        
+        SkDELETE(fMutex);
+    }
+    
+    SkMutex*        fMutex;
+
+    SkGlyphCache* internalGetHead() const { return fHead; }
+    SkGlyphCache* internalGetTail() const;
+
+    size_t getTotalMemoryUsed() const { return fTotalMemoryUsed; }
+    int getCacheCountUsed() const { return fCacheCount; }
+
+#ifdef SK_DEBUG
+    void validate() const;
+#else
+    void validate() const {}
+#endif
+
+    int getCacheCountLimit() const { return fCacheCountLimit; }
+    int setCacheCountLimit(int limit);
+
+    size_t  getCacheSizeLimit() const { return fCacheSizeLimit; }
+    size_t  setCacheSizeLimit(size_t limit);
+
+    // returns true if this cache is over-budget either due to size limit
+    // or count limit.
+    bool isOverBudget() const {
+        return fCacheCount > fCacheCountLimit ||
+               fTotalMemoryUsed > fCacheSizeLimit;
+    }
+
+    void purgeAll(); // does not change budget
+
+    // call when a glyphcache is available for caching (i.e. not in use)
+    void attachCacheToHead(SkGlyphCache*);
+    
+    // can only be called when the mutex is already held
+    void internalDetachCache(SkGlyphCache*);
+    void internalAttachCacheToHead(SkGlyphCache*);
+
+    // can return NULL
+    static SkGlyphCache_Globals* FindTLS() {
+        return (SkGlyphCache_Globals*)SkTLS::Find(CreateTLS);
+    }
+    
+    static SkGlyphCache_Globals& GetTLS() {
+        return *(SkGlyphCache_Globals*)SkTLS::Get(CreateTLS, DeleteTLS);
+    }
+    
+    static void DeleteTLS() { SkTLS::Delete(CreateTLS); }
+    
+private:
+    SkGlyphCache* fHead;
+    size_t  fTotalMemoryUsed;
+    size_t  fCacheSizeLimit;
+    int32_t fCacheCountLimit;
+    int32_t fCacheCount;
+    
+    // Checkout budgets, modulated by the specified min-bytes-needed-to-purge,
+    // and attempt to purge caches to match.
+    // Returns number of bytes freed.
+    size_t internalPurge(size_t minBytesNeeded = 0);
+
+    static void* CreateTLS() {
+        return SkNEW_ARGS(SkGlyphCache_Globals, (kNo_UseMutex));
+    }
+    
+    static void DeleteTLS(void* ptr) {
+        SkDELETE((SkGlyphCache_Globals*)ptr);
+    }
+};
+
+#endif