use SkTDynamicHash in picture recording

src/core/SkTDynamicHash.h

Index: src/core/SkTDynamicHash.h
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index b3d4b26476b34ede5c39d9b6d2699da1cd2c4911..fe65081542a732040e56863ed730f90cc5b5684b 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -9,185 +9,132 @@
 #define SkTDynamicHash_DEFINED
 
 #include "SkTypes.h"
+#include "SkMath.h"
 
 template <typename T,
-          typename KEY,
-          const KEY& (KEY_FROM_T)(const T&),
-          uint32_t (HASH_FROM_KEY)(const KEY&),
-          bool (EQ_T_KEY)(const T&, const KEY&)>
+          typename Key,
+          const Key& (GetKey)(const T&),
+          uint32_t (Hash)(const Key&),
+          bool (Equal)(const T&, const Key&)>
 class SkTDynamicHash {
-private:
-    T* fStorage[4];     // cheap storage for small arrays
-    T** fArray;
-    int fCapacity;      // number of slots in fArray. Must be pow2
-    int fCountUsed;     // number of valid entries in fArray
-    int fCountDeleted;  // number of deletedValue() entries in fArray
-
-    // Need an illegal ptr value different from NULL (which we use to
-    // signal empty/unused.
-    const T* deletedValue() const { return reinterpret_cast<const T*>(-1); }
-
-    // fCapacity is a pow2, so that minus one is a clean mask to grab
-    // the low bits of hash to use as an index.
-    uint32_t hashMask() const { return fCapacity - 1; }
+public:
+    SkTDynamicHash(int initialCapacity=64/sizeof(T*))

[reed1, 2013/08/05 15:43:29]

My scrape of the web sites showed a lot of font caches with 1..3 entries. Do you
think it is troublesome to support inline storage for small amounts?

[mtklein, 2013/08/05 18:14:46]

Nope, was just trying to keep things simple with a single place for the data to
live.  (As for the default here, I figured a cache line would be the smallest
alloc worth doing, and it can't hurt to keep us on an integral number of them.) 
Personally I'd not pay the extra size cost of an fStorage before seeing a
performance difference.  Maybe we add a variant with local storage with an 'S'
shoved into the name somewhere?

+    : fCount(0)
+    , fCapacity(SkNextPow2(initialCapacity))
+    , fArray(AllocArray(fCapacity)) {}
 
-    int hashToIndex(uint32_t hash) const {
-        // this 16bit fold may be overkill, if we trust that hash is good
-        return ((hash >> 16) ^ hash) & this->hashMask();
+    ~SkTDynamicHash() {
+        sk_free(fArray);
     }
 
-public:
-    SkTDynamicHash() {
-        sk_bzero(fStorage, sizeof(fStorage));
-        fArray = fStorage;
-        fCapacity = SK_ARRAY_COUNT(fStorage);
-        fCountUsed = fCountDeleted = 0;
-    }
-    ~SkTDynamicHash() {
-        if (fArray != fStorage) {
-            sk_free(fArray);
+    // Return the entry with this key if we have it, otherwise NULL.
+    T* find(const Key& key) const {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            T* candidate = fArray[index];
+            if (candidate == Empty()) return NULL;

[reed1, 2013/08/05 15:43:29]

prolly need to follow skia's "always use { }" rule for "ifs"

[mtklein, 2013/08/05 18:14:46]

ah, done.  That habit is dying hard.

+            if (candidate != Deleted() && Equal(*candidate, key)) return candidate;
+            index = this->nextIndex(index, round);
         }
+        SkASSERT(!"find: should be unreachable");
+        return NULL;
     }
 
-    T* find(const KEY& key) {
-        const T* const deleted = this->deletedValue();
-        const unsigned mask = this->hashMask();
-        int index = this->hashToIndex(HASH_FROM_KEY(key));
-        int delta = 1;
+    // Add an entry with this key.
+    void add(T* newEntry) {
+        this->maybeGrow();
 
-        do {
+        const Key& key = GetKey(*newEntry);
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
             T* candidate = fArray[index];
-            if (NULL == candidate) {
-                return NULL;
+            if (candidate == Empty() || candidate == Deleted()) {
+                fArray[index] = newEntry;
+                fCount++;
+                return;
             }
-            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
-                return candidate;
-            }
-            index = (index + delta) & mask;
-            delta <<= 1;
-        } while (delta <= fCapacity);
-        return NULL;
-    }
-
-    bool add(const KEY& key, T* newElement, bool autoGrow = true) {
-        const T* const deleted = this->deletedValue();
-        for (;;) {
-            const unsigned mask = this->hashMask();
-            int index = this->hashToIndex(HASH_FROM_KEY(key));
-            int delta = 1;
-
-            do {
-                const T* candidate = fArray[index];
-                if (NULL == candidate || deleted == candidate) {
-                    fArray[index] = newElement;
-                    fCountUsed += 1;
-                    if (deleted == candidate) {
-                        SkASSERT(fCountDeleted > 0);
-                        fCountDeleted -= 1;
-                    }
-                    return true;
-                }
-                index = (index + delta) & mask;
-                delta <<= 1;
-            } while (delta <= fCapacity);
-            if (autoGrow) {
-                this->grow();
-            } else {
-                return false;
+            if (Equal(*candidate, key)) {
+                fArray[index] = newEntry;
+                return;
             }
+            index = this->nextIndex(index, round);
         }
-        SkASSERT(!"never get here");
-        return false;
+        SkASSERT(!"add: should be unreachable");
     }
 
-    void remove(const KEY& key) {
-        const T* const deleted = this->deletedValue();
-        const unsigned mask = this->hashMask();
-        int index = this->hashToIndex(HASH_FROM_KEY(key));
-        int delta = 1;
-
-        for (;;) {
-            const T* candidate = fArray[index];
-            SkASSERT(candidate);
-            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
-                fArray[index] = const_cast<T*>(deleted);
-                fCountUsed -= 1;
-                fCountDeleted += 1;
-                break;
-            }
-            index = (index + delta) & mask;
-            delta <<= 1;
-            SkASSERT(delta <= fCapacity);
-        }
-        this->checkStrink();
+    // Remove entry with this key, if we have it.
+    void remove(const Key& key) {
+        this->innerRemove(key);
+        this->maybeShrink();
     }
 
 private:
-    int countCollisions(const KEY& key) const {
-        const T* const deleted = this->deletedValue();
-        const unsigned mask = this->hashMask();
-        int index = this->hashToIndex(HASH_FROM_KEY(key));
-        int delta = 1;
-        int collisionCount = 0;
-
-        for (;;) {
+    // We have two special values to indicate an empty or deleted entry.
+    static const T* Empty()   { return reinterpret_cast<const T*>(0); }  // i.e. NULL
+    static const T* Deleted() { return reinterpret_cast<const T*>(1); }  // Also an invalid pointer.
+
+    static T** AllocArray(int capacity) {
+        T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity);
+        sk_bzero(array, sizeof(T*) * capacity);  // All cells == Empty().
+        return array;
+    }
+
+    void innerRemove(const Key& key) {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
             const T* candidate = fArray[index];
-            SkASSERT(candidate);
-            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
-                break;
+            if (candidate == Empty()) return;
+            if (candidate != Deleted() && Equal(*candidate, key)) {
+                fArray[index] = const_cast<T*>(Deleted());
+                fCount--;
+                return;
             }
-            index = (index + delta) & mask;
-            delta <<= 1;
-            collisionCount += 1;
-            SkASSERT(delta <= fCapacity);
+            index = this->nextIndex(index, round);
         }
-        return collisionCount;
+        SkASSERT(!"innerRemove: should be unreachable");
     }
 
-    void grow() {
-        const T* const deleted = this->deletedValue();
-#if 0
-        SkDebugf("growing from %d: used=%d\n", fCapacity, fCountUsed);
-        for (int i = 0; i < fCapacity; ++i) {
-            T* elem = fArray[i];
-            if (NULL == elem || deleted == elem) {
-                continue;
-            }
-            SkDebugf("    entry[%d] had %d collisions\n", i, countCollisions(KEY_FROM_T(*elem)));
-        }
-#endif
+    void maybeGrow() {
+        if (fCount < fCapacity / 2) return;
+
+        SkDEBUGCODE(int oldCount = fCount;)
         int oldCapacity = fCapacity;
         T** oldArray = fArray;
 
-        int newCapacity = oldCapacity << 1;
-        T** newArray = (T**)sk_malloc_throw(sizeof(T*) * newCapacity);
-        sk_bzero(newArray, sizeof(T*) * newCapacity);
+        fCount = 0;
+        fCapacity *= 2;
+        fArray = AllocArray(fCapacity);
 
-        SkDEBUGCODE(int oldCountUsed = fCountUsed;)
-        fArray = newArray;
-        fCapacity = newCapacity;
-        fCountUsed = 0;
-        fCountDeleted = 0;
-
-        for (int i = 0; i < oldCapacity; ++i) {
-            T* elem = oldArray[i];
-            if (NULL == elem || deleted == elem) {
-                continue;
-            }
-            SkDEBUGCODE(bool success =) this->add(KEY_FROM_T(*elem), elem, false);
-            SkASSERT(success);
+        for (int i = 0; i < oldCapacity; i++) {
+            T* entry = oldArray[i];
+            if (entry == Empty() || entry == Deleted()) continue;
+            this->add(entry);
         }
-        SkASSERT(oldCountUsed == fCountUsed);
+        SkASSERT(oldCount == fCount);
 
-        if (oldArray != fStorage) {
-            sk_free(oldArray);
-        }
+        sk_free(oldArray);
+    }
+
+    void maybeShrink() {
+        // TODO
     }
 
-    void checkStrink() {
-        // todo: based on density and deadspace (fCountDeleted), consider
-        // shrinking fArray and repopulating it.
+    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
+    uint32_t hashMask() const { return fCapacity - 1; }
+
+    int firstIndex(const Key& key) const {
+        return Hash(key) & this->hashMask();
     }
+
+    // Given index at round N, what is the index to check at N+1?  round should start at 0.
+    int nextIndex(int index, int round) const {
+        // This will search a power-of-two array fully without repeating an index.
+        return (index + round + 1) & this->hashMask();
+    }
+
+    int fCount;     // Number of non-empty, non-deleted entries in fArray.
+    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
+    T** fArray;
 };
 
 #endif