add dox to SkTDynamicHash, fix typo of Key instead of KEY

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"
 
-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&)>
+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&)>
 class SkTDynamicHash {
 private:
-    T* fStorage[4];
+    T* fStorage[4];     // cheap storage for small arrays
     T** fArray;
-    int fCapacity;
-    int fCountUsed;
-    int fCountDeleted;
+    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.

[mtklein, 2013/07/29 18:51:22]

add a ) ?

     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 {
-        return ((hash >> 16) ^ hash) & (fCapacity - 1);
+        // this 16bit fold may be overkill, if we trust that hash is good
+        return ((hash >> 16) ^ hash) & this->hashMask();
     }
+
 public:
     SkTDynamicHash() {
         sk_bzero(fStorage, sizeof(fStorage));
         fArray = fStorage;
         fCapacity = SK_ARRAY_COUNT(fStorage);
         fCountUsed = fCountDeleted = 0;
     }
     ~SkTDynamicHash() {
         if (fArray != fStorage) {
             sk_free(fArray);
@@ skipping 67 matching lines @@
                 break;
             }
             index = (index + delta) & mask;
             delta <<= 1;
             SkASSERT(delta <= fCapacity);
         }
         this->checkStrink();
     }
 
 private:
-    int countCollisions(const Key& key) const {
+    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 (;;) {
             const T* candidate = fArray[index];
             SkASSERT(candidate);
             if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
@@ skipping 47 matching lines @@
         }
     }
 
     void checkStrink() {
         // todo: based on density and deadspace (fCountDeleted), consider
         // shrinking fArray and repopulating it.
     }
 };
 
 #endif