use SkTDynamicHash in picture recording

src/core/SkTDynamicHash.h

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTDynamicHash_DEFINED
 #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
+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)) {}
 
-    // 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; }
-
-    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);
         }
-    }
-
-    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;
-
-        do {
-            T* candidate = fArray[index];
-            if (NULL == candidate) {
-                return NULL;
-            }
-            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
-                return candidate;
-            }
-            index = (index + delta) & mask;
-            delta <<= 1;
-        } while (delta <= fCapacity);
+        SkASSERT(!"find: should be unreachable");
         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;
+    // Add an entry with this key.
+    void add(T* newEntry) {
+        this->maybeGrow();
 
-            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;
+        const Key& key = GetKey(*newEntry);
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            T* candidate = fArray[index];
+            if (candidate == Empty() || candidate == Deleted()) {
+                fArray[index] = newEntry;
+                fCount++;
+                return;
             }
+            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;
+    // 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.
 
-        for (;;) {
-            const T* candidate = fArray[index];
-            SkASSERT(candidate);
-            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
-                break;
-            }
-            index = (index + delta) & mask;
-            delta <<= 1;
-            collisionCount += 1;
-            SkASSERT(delta <= fCapacity);
-        }
-        return collisionCount;
+    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 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;
+    void innerRemove(const Key& key) {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (candidate == Empty()) return;
+            if (candidate != Deleted() && Equal(*candidate, key)) {
+                fArray[index] = const_cast<T*>(Deleted());
+                fCount--;
+                return;
             }
-            SkDebugf("    entry[%d] had %d collisions\n", i, countCollisions(KEY_FROM_T(*elem)));
+            index = this->nextIndex(index, round);
         }
-#endif
+        SkASSERT(!"innerRemove: should be unreachable");
+    }
+
+    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* entry = oldArray[i];
+            if (entry == Empty() || entry == Deleted()) continue;
+            this->add(entry);
+        }
+        SkASSERT(oldCount == fCount);
 
-        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);
-        }
-        SkASSERT(oldCountUsed == fCountUsed);
-
-        if (oldArray != fStorage) {
-            sk_free(oldArray);
-        }
+        sk_free(oldArray);
     }
 
-    void checkStrink() {
-        // todo: based on density and deadspace (fCountDeleted), consider
-        // shrinking fArray and repopulating it.
+    void maybeShrink() {
+        // TODO
     }
+
+    // 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