Spin off SkTHashTable, SkTHashMap, SkTHashSet

src/core/SkTHash.h

+#ifndef SkTHash_DEFINED
+#define SkTHash_DEFINED
+
+#include "SkTypes.h"
+#include "SkTemplates.h"
+
+// Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you.
+// They're easier to use, usually perform the same, and have fewer sharp edges.
+
+// T and K are treated as ordinary copyable C++ types.
+// Traits must have:
+//   - static K GetKey(T)
+//   - static uint32_t Hash(K)
+// If the key is large and stored inside T, you may want to make K a const&.
+// Similarly, if T is large you might want it to be a pointer.
+template <typename T, typename K, typename Traits = T>
+class SkTHashTable : SkNoncopyable {
+public:
+    SkTHashTable() : fCount(0), fCapacity(0) {}
+
+    // How many entries are in the table?
+    int count() const { return fCount; }
+
+    // N.B. The pointers returned by set() and find() are valid only until the next call to set().
+
+    // Copy val into the hash table, returning a pointer to the copy now in the table.
+    // If there already is an entry in the table with the same key, we overwrite it.
+    T* set(T val) {

[f(malita), 2015/02/12 19:37:11]

Shouldn't all these return const T* (if anything)? Mutating an item in the table
is likely to change its key/hash and break the hashtable invariants.

[reed1, 2015/02/12 19:49:15]

When is (const T& val) better or worse?

[mtklein, 2015/02/12 20:09:52]

So far, I haven't seen it matter.  This all being a template, everything here is
elided except the final copy into the table.

There are a few places where we might want to add const& if we see unnecessary
copying (here, the key passed to find, the signature of GetKey and Hash), but I
think we can probably leave that until we see a problem.

[mtklein, 2015/02/12 20:09:52]

Yeah, that's one of the sharp edges of why we don't want to generally use
SkTHashTable.  It's the same problem as foreach()... you want to be able to
modify parts of the T, but you need to be careful not to affect the Key.  We
actually need the mutability here to be able to implement things like SkTHashMap
that allow mutating the value but not the key.

I've expanded the warnings.  How's this look?

+        if (4 * fCount >= 3 * fCapacity) {
+            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
+        }
+        return this->uncheckedSet(val);
+    }
+
+    // If there is an entry in the table with this key, return a pointer to it.  If not, NULL.
+    T* find(K key) const {
+        uint32_t hash = Hash(key);
+        int index = hash & (fCapacity-1);
+        for (int n = 0; n < fCapacity; n++) {
+            Slot& s = fSlots[index];
+            if (s.empty()) {
+                return NULL;
+            }
+            if (hash == s.hash && key == Traits::GetKey(s.val)) {
+                return &s.val;
+            }
+            index = this->next(index, n);
+        }
+        SkASSERT(fCapacity == 0);
+        return NULL;
+    }
+
+    // Call fn on every entry in the table.  You may mutate the entries, but be very careful.
+    // If you change an entry so that it no longer has the same key,
+    // all hell will break loose the next time you call set() or find().  Do not do that!
+    template <typename Arg>
+    void foreach(void(*fn)(T*, Arg), Arg arg) {
+        for (int i = 0; i < fCapacity; i++) {
+            Slot& s = fSlots[i];
+            if (!s.empty()) {
+                fn(&s.val, arg);
+            }
+        }
+    }
+
+private:
+    T* uncheckedSet(T val) {
+        K key = Traits::GetKey(val);
+        uint32_t hash = Hash(key);
+        int index = hash & (fCapacity-1);
+        for (int n = 0; n < fCapacity; n++) {
+            Slot& s = fSlots[index];
+            if (s.empty()) {
+                // New entry.
+                s.val  = val;
+                s.hash = hash;
+                fCount++;
+                return &s.val;
+            }
+            if (hash == s.hash && key == Traits::GetKey(s.val)) {
+                // Overwrite previous entry.
+                s.val = val;
+                return &s.val;
+            }
+            index = this->next(index, n);
+        }
+        SkASSERT(false);
+        return NULL;
+    }
+
+    void resize(int capacity) {
+        int oldCapacity = fCapacity;
+        SkDEBUGCODE(int oldCount = fCount);
+
+        fCount = 0;
+        fCapacity = capacity;
+        SkAutoTArray<Slot> oldSlots(capacity);
+        oldSlots.swap(fSlots);
+
+        for (int i = 0; i < oldCapacity; i++) {
+            const Slot& s = oldSlots[i];
+            if (!s.empty()) {
+                this->uncheckedSet(s.val);
+            }
+        }
+        SkASSERT(fCount == oldCount);
+    }
+
+    int next(int index, int n) const {
+        // A valid strategy explores all slots in [0, fCapacity) as n walks from 0 to fCapacity-1.
+        // Both of these stragegies are valid:
+        //return (index + 0 + 1) & (fCapacity-1);      // Linear probing.
+        return (index + n + 1) & (fCapacity-1);        // Quadratic probing.
+    }
+
+    static uint32_t Hash(K key) {
+        uint32_t hash = Traits::Hash(key);
+        return hash == 0 ? 1 : hash;  // We reserve hash == 0 to mark empty slots.
+    }
+
+    struct Slot {
+        Slot() : hash(0) {}
+        bool empty() const { return hash == 0; }
+
+        T val;
+        uint32_t hash;
+    };
+
+    int fCount, fCapacity;
+    SkAutoTArray<Slot> fSlots;
+};
+
+// Maps K->V.  A more user-friendly wrapper around SkTHashTable, suitable for most use cases.
+// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two.
+template <typename K, typename V, uint32_t(*HashK)(K)>
+class SkTHashMap : SkNoncopyable {
+public:
+    SkTHashMap() {}
+
+    // How many key/value pairs are in the table?
+    int count() const { return fTable.count(); }
+
+    // N.B. The pointers returned by set() and find() are valid only until the next call to set().
+
+    // Set key to val in the table, replacing any previous value with the same key.
+    // We copy both key and val, and return a pointer to the value copy now in the table.
+    V* set(K key, V val) {
+        Pair in = { key, val };
+        Pair* out = fTable.set(in);
+        return &out->val;
+    }
+
+    // If there is key/value entry in the table with this key, return a pointer to the value.
+    // If not, return NULL.
+    V* find(K key) const {
+        if (Pair* p = fTable.find(key)) {
+            return &p->val;
+        }
+        return NULL;
+    }
+
+    // Call fn on every key/value pair in the table.  You may mutate the value but not the key.
+    void foreach(void(*fn)(K, V*)) { fTable.foreach(ForEach, fn); }
+
+private:
+    struct Pair {
+        K key;
+        V val;
+        static K GetKey(Pair p) { return p.key; }
+        static uint32_t Hash(K key) { return HashK(key); }
+    };
+    static void ForEach(Pair* p, void (*fn)(K, V*)) { fn(p->key, &p->val); }
+
+    SkTHashTable<Pair, K> fTable;
+};
+
+// A set of T.  T is treated as an ordiary copyable C++ type.
+template <typename T, uint32_t(*HashT)(T)>
+class SkTHashSet : SkNoncopyable {
+public:
+    SkTHashSet() {}
+
+    // How many items are in the set?
+    int count() const { return fTable.count(); }
+
+    // N.B. The pointers returned by add() and find() are valid only until the next call to add().
+
+    // Copy an item into the set.  If there is an item in the set already that is equal
+    // to this one, overwrite it.  Returns a pointer to the copy of the item now in the set.
+    T* add(T item) {
+        return fTable.set(item);
+    }
+
+    // If an item is in the set equal to this one, return a pointer to it, otherwise return NULL.
+    T* find(T item) {

[f(malita), 2015/02/12 19:37:11]

Nit: I think we could use an even simpler interface for sets:

void add(T)
bool contains(T)

(this also avoids all mutability issues)

[f(malita), 2015/02/12 19:37:11]

const

[mtklein, 2015/02/12 20:09:52]

Done.

[mtklein, 2015/02/12 20:09:52]

Done.

+        return fTable.find(item);
+    }
+
+private:
+    struct Traits {
+        static T GetKey(T item) { return item; }
+        static uint32_t Hash(T item) { return HashT(item); }
+    };
+    SkTHashTable<T, T, Traits> fTable;
+};
+
+#endif//SkTHash_DEFINED