Allocate memory in SkTDynamicHash on first use.

This eliminates any dynamic allocation for hash tables that are never used.
This helps SkPicture, where some tables (SkPaint) are almost always used, but
some rarely (SkMatrix) or never (SkRegion).

This also removes the (as yet unimportant) ability for the hash table to
shrink.  This makes resizing harder to reason about, so I'd like to leave it
out until we see a need.

BUG=skia:1850
R=tomhudson@chromium.org, reed@google.com

Author: mtklein@google.com

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

git-svn-id: http://skia.googlecode.com/svn/trunk@13051 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 14 insertions, 37 deletions

diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index 4cb44204c8..4893fb384f 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -16,13 +16,10 @@ template <typename T,
           const Key& (GetKey)(const T&),
           uint32_t (Hash)(const Key&),
           bool (Equal)(const T&, const Key&),
-          int kGrowPercent   = 75,  // Larger -> more memory efficient, but slower.
-          int kShrinkPercent = 25>
+          int kGrowPercent = 75>  // Larger -> more memory efficient, but slower.
 class SkTDynamicHash {
-    static const int kMinCapacity = 4;  // Smallest capacity we allow.
 public:
-    SkTDynamicHash(int initialCapacity=64/sizeof(T*)) {
-        this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity));
+    SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) {
         SkASSERT(this->validate());
     }
 
@@ -45,7 +42,7 @@ public:
             }
             index = this->nextIndex(index, round);
         }
-        SkASSERT(0); //  find: should be unreachable
+        SkASSERT(fCapacity == 0);
         return NULL;
     }
 
@@ -63,8 +60,6 @@ public:
         SkASSERT(NULL != this->find(key));
         this->innerRemove(key);
         SkASSERT(this->validate());
-        this->maybeShrink();
-        SkASSERT(this->validate());
     }
 
 protected:
@@ -82,8 +77,8 @@ protected:
             }
             index = this->nextIndex(index, round);
         }
-        SkASSERT(0); // countCollisions: should be unreachable
-        return -1;
+        SkASSERT(fCapacity == 0);
+        return 0;
     }
 
 private:
@@ -91,23 +86,11 @@ private:
     static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
     static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
 
-    static T** AllocArray(int capacity) {
-        return (T**)sk_calloc_throw(sizeof(T*) * capacity);  // All cells == Empty().
-    }
-
-    void reset(int capacity) {
-        fCount = 0;
-        fDeleted = 0;
-        fCapacity = capacity;
-        fArray = AllocArray(fCapacity);
-    }
-
     bool validate() const {
         #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
 
         // Is capacity sane?
         SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
-        SKTDYNAMICHASH_CHECK(fCapacity >= kMinCapacity);
 
         // Is fCount correct?
         int count = 0;
@@ -168,7 +151,7 @@ private:
             }
             index = this->nextIndex(index, round);
         }
-        SkASSERT(0); // add: should be unreachable
+        SkASSERT(fCapacity == 0);
     }
 
     void innerRemove(const Key& key) {
@@ -184,37 +167,31 @@ private:
             }
             index = this->nextIndex(index, round);
         }
-        SkASSERT(0); // innerRemove: should be unreachable
+        SkASSERT(fCapacity == 0);
     }
 
     void maybeGrow() {
-        if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) {
-            resize(fCapacity * 2);
-        }
-    }
-
-    void maybeShrink() {
-        if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) {
-            resize(fCapacity / 2);
+        if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
+            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
         }
     }
 
     void resize(int newCapacity) {
         SkDEBUGCODE(int oldCount = fCount;)
         int oldCapacity = fCapacity;
-        T** oldArray = fArray;
+        SkAutoTMalloc<T*> oldArray(fArray);
 
-        reset(newCapacity);
+        fCount = fDeleted = 0;
+        fCapacity = newCapacity;
+        fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
 
         for (int i = 0; i < oldCapacity; i++) {
             T* entry = oldArray[i];
             if (Empty() != entry && Deleted() != entry) {
-                this->add(entry);
+                this->innerAdd(entry);
             }
         }
         SkASSERT(oldCount == fCount);
-
-        sk_free(oldArray);
     }
 
     // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.