SkTDynamicHash: support remove() without needing Deleted().

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& (GetKey)(const T&),
           uint32_t (Hash)(const Key&),
-          bool (Equal)(const T&, const Key&)>
+          bool (Equal)(const T&, const Key&),
+          int kGrowPercent   = 75,  // Larger -> more memory efficient, but slower.
+          int kShrinkPercent = 25>
 class SkTDynamicHash {
+    static const int kMinCapacity = 4;  // Smallest capacity we allow.
 public:
-    SkTDynamicHash(int initialCapacity=64/sizeof(T*))
-    : fCount(0)
-    , fCapacity(SkNextPow2(initialCapacity > 0 ? initialCapacity : 1))
-    , fArray(AllocArray(fCapacity)) {}
+    SkTDynamicHash(int initialCapacity=64/sizeof(T*)) {
+        this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity));
+        SkASSERT(this->validate());
+    }
 
     ~SkTDynamicHash() {
         sk_free(fArray);
     }
 
     int count() const { return fCount; }
 
     // 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()) {
+            if (Empty() == candidate) {
                 return NULL;
             }
-            if (candidate != Deleted() && Equal(*candidate, key)) {
+            if (Deleted() != candidate && Equal(*candidate, key)) {
                 return candidate;
             }
             index = this->nextIndex(index, round);
         }
         SkASSERT(!"find: should be unreachable");
         return NULL;
     }
 
-    // Add an entry with this key.
+    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
     void add(T* newEntry) {
+        SkASSERT(NULL == this->find(GetKey(*newEntry)));
         this->maybeGrow();
-
-        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(!"add: should be unreachable");
+        SkASSERT(this->validate());
+        this->innerAdd(newEntry);
+        SkASSERT(this->validate());
     }
 
-    // Remove entry with this key, if we have it.
+    // Remove the entry with this key.  We reqire that an entry with this key is present.
     void remove(const Key& key) {
+        SkASSERT(NULL != this->find(key));
         this->innerRemove(key);
+        SkASSERT(this->validate());
         this->maybeShrink();
+        SkASSERT(this->validate());
     }
 
 protected:
     // These methods are used by tests only.
 
     int capacity() const { return fCapacity; }
 
     // How many collisions do we go through before finding where this entry should be inserted?
     int countCollisions(const Key& key) const {
         int index = this->firstIndex(key);
         for (int round = 0; round < fCapacity; round++) {
             const T* candidate = fArray[index];
-            if (candidate == Empty() || candidate == Deleted() || Equal(*candidate, key)) {
+            if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
                 return round;
             }
             index = this->nextIndex(index, round);
         }
         SkASSERT(!"countCollisions: should be unreachable");
         return -1;
     }
 
 private:
     // 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* 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) {
         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) {
+    void reset(int capacity) {
+        fCount = 0;
+        fDeleted = 0;
+        fCapacity = capacity;
+        fArray = AllocArray(fCapacity);
+    }
+
+    bool validate() const {
+        #define CHECK(x) SkASSERT((x)); if (!(x)) return false
+
+        // Is capacity sane?
+        CHECK(SkIsPow2(fCapacity));
+        CHECK(fCapacity >= kMinCapacity);
+
+        // Is fCount correct?
+        int count = 0;
+        for (int i = 0; i < fCapacity; i++) {
+            if (Empty() != fArray[i] && Deleted() != fArray[i]) {
+                count++;
+            }
+        }
+        CHECK(count == fCount);
+
+        // Is fDeleted correct?
+        int deleted = 0;
+        for (int i = 0; i < fCapacity; i++) {
+            if (Deleted() == fArray[i]) {
+                deleted++;
+            }
+        }
+        CHECK(deleted == fDeleted);
+
+        // Are all entries findable?
+        for (int i = 0; i < fCapacity; i++) {
+            if (Empty() == fArray[i] || Deleted() == fArray[i]) {
+                continue;
+            }
+            CHECK(NULL != this->find(GetKey(*fArray[i])));
+        }
+
+        // Are all entries unique?
+        for (int i = 0; i < fCapacity; i++) {
+            if (Empty() == fArray[i] || Deleted() == fArray[i]) {
+                continue;
+            }
+            for (int j = i+1; j < fCapacity; j++) {
+                if (Empty() == fArray[j] || Deleted() == fArray[j]) {
+                    continue;
+                }
+                CHECK(fArray[i] != fArray[j]);
+                CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
+                CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
+            }
+        }
+        #undef CHECK
+        return true;
+    }
+
+    void innerAdd(T* newEntry) {
+        const Key& key = GetKey(*newEntry);
         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--;
+            if (Empty() == candidate || Deleted() == candidate) {
+                if (Deleted() == candidate) {
+                    fDeleted--;
+                }
+                fCount++;
+                fArray[index] = newEntry;
                 return;
             }
             index = this->nextIndex(index, round);
+        }
+        SkASSERT(!"add: should be unreachable");
+    }
+
+    void innerRemove(const Key& key) {
+        const int firstIndex = this->firstIndex(key);
+        int index = firstIndex;
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (Deleted() != candidate && Equal(*candidate, key)) {
+                fDeleted++;
+                fCount--;
+                fArray[index] = Deleted();
+                return;
+            }
+            index = this->nextIndex(index, round);
         }
         SkASSERT(!"innerRemove: should be unreachable");
     }
 
     void maybeGrow() {
-        if (fCount < fCapacity / 2) {
-            return;
+        if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) {
+            resize(fCapacity * 2);
         }
+    }
 
+    void maybeShrink() {
+        if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) {
+            resize(fCapacity / 2);
+        }
+    }
+
+    void resize(int newCapacity) {
         SkDEBUGCODE(int oldCount = fCount;)
         int oldCapacity = fCapacity;
         T** oldArray = fArray;
 
-        fCount = 0;
-        fCapacity *= 2;
-        fArray = AllocArray(fCapacity);
+        reset(newCapacity);
 
         for (int i = 0; i < oldCapacity; i++) {
             T* entry = oldArray[i];
-            if (entry != Empty() && entry != Deleted()) {
+            if (Empty() != entry && Deleted() != entry) {
                 this->add(entry);
             }
         }
         SkASSERT(oldCount == fCount);
 
         sk_free(oldArray);
     }
 
-    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 fCount;     // Number of non Empty(), non Deleted() entries in fArray.
+    int fDeleted;   // Number of Deleted() entries in fArray.
     int fCapacity;  // Number of entries in fArray.  Always a power of 2.
     T** fArray;
 };
 
 #endif