1/*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkTHash_DEFINED
9#define SkTHash_DEFINED
10
11#include "SkChecksum.h"
12#include "SkTypes.h"
13#include "SkTemplates.h"
14
15// Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you.
16// They're easier to use, usually perform the same, and have fewer sharp edges.
17
18// T and K are treated as ordinary copyable C++ types.
19// Traits must have:
20//   - static K GetKey(T)
21//   - static uint32_t Hash(K)
22// If the key is large and stored inside T, you may want to make K a const&.
23// Similarly, if T is large you might want it to be a pointer.
24template <typename T, typename K, typename Traits = T>
25class SkTHashTable : SkNoncopyable {
26public:
27    SkTHashTable() : fCount(0), fRemoved(0), fCapacity(0) {}
28
29    // Clear the table.
30    void reset() {
31        this->~SkTHashTable();
32        SkNEW_PLACEMENT(this, SkTHashTable);
33    }
34
35    // How many entries are in the table?
36    int count() const { return fCount; }
37
38    // !!!!!!!!!!!!!!!!!                 CAUTION                   !!!!!!!!!!!!!!!!!
39    // set(), find() and foreach() all allow mutable access to table entries.
40    // If you change an entry so that it no longer has the same key, all hell
41    // will break loose.  Do not do that!
42    //
43    // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger.
44
45    // The pointers returned by set() and find() are valid only until the next call to set().
46    // The pointers you receive in foreach() are only valid for its duration.
47
48    // Copy val into the hash table, returning a pointer to the copy now in the table.
49    // If there already is an entry in the table with the same key, we overwrite it.
50    T* set(const T& val) {
51        if (4 * (fCount+fRemoved) >= 3 * fCapacity) {
52            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
53        }
54        return this->uncheckedSet(val);
55    }
56
57    // If there is an entry in the table with this key, return a pointer to it.  If not, NULL.
58    T* find(const K& key) const {
59        uint32_t hash = Hash(key);
60        int index = hash & (fCapacity-1);
61        for (int n = 0; n < fCapacity; n++) {
62            Slot& s = fSlots[index];
63            if (s.empty()) {
64                return NULL;
65            }
66            if (!s.removed() && hash == s.hash && key == Traits::GetKey(s.val)) {
67                return &s.val;
68            }
69            index = this->next(index, n);
70        }
71        SkASSERT(fCapacity == 0);
72        return NULL;
73    }
74
75    // Remove the value with this key from the hash table.
76    void remove(const K& key) {
77        SkASSERT(this->find(key));
78
79        uint32_t hash = Hash(key);
80        int index = hash & (fCapacity-1);
81        for (int n = 0; n < fCapacity; n++) {
82            Slot& s = fSlots[index];
83            SkASSERT(!s.empty());
84            if (!s.removed() && hash == s.hash && key == Traits::GetKey(s.val)) {
85                fRemoved++;
86                fCount--;
87                s.markRemoved();
88                return;
89            }
90            index = this->next(index, n);
91        }
92        SkASSERT(fCapacity == 0);
93    }
94
95    // Call fn on every entry in the table.  You may mutate the entries, but be very careful.
96    template <typename Fn>  // f(T*)
97    void foreach(Fn&& fn) {
98        for (int i = 0; i < fCapacity; i++) {
99            if (!fSlots[i].empty() && !fSlots[i].removed()) {
100                fn(&fSlots[i].val);
101            }
102        }
103    }
104
105    // Call fn on every entry in the table.  You may not mutate anything.
106    template <typename Fn>  // f(T) or f(const T&)
107    void foreach(Fn&& fn) const {
108        for (int i = 0; i < fCapacity; i++) {
109            if (!fSlots[i].empty() && !fSlots[i].removed()) {
110                fn(fSlots[i].val);
111            }
112        }
113    }
114
115private:
116    T* uncheckedSet(const T& val) {
117        const K& key = Traits::GetKey(val);
118        uint32_t hash = Hash(key);
119        int index = hash & (fCapacity-1);
120        for (int n = 0; n < fCapacity; n++) {
121            Slot& s = fSlots[index];
122            if (s.empty() || s.removed()) {
123                // New entry.
124                if (s.removed()) {
125                    fRemoved--;
126                }
127                s.val  = val;
128                s.hash = hash;
129                fCount++;
130                return &s.val;
131            }
132            if (hash == s.hash && key == Traits::GetKey(s.val)) {
133                // Overwrite previous entry.
134                // Note: this triggers extra copies when adding the same value repeatedly.
135                s.val = val;
136                return &s.val;
137            }
138            index = this->next(index, n);
139        }
140        SkASSERT(false);
141        return NULL;
142    }
143
144    void resize(int capacity) {
145        int oldCapacity = fCapacity;
146        SkDEBUGCODE(int oldCount = fCount);
147
148        fCount = fRemoved = 0;
149        fCapacity = capacity;
150        SkAutoTArray<Slot> oldSlots(capacity);
151        oldSlots.swap(fSlots);
152
153        for (int i = 0; i < oldCapacity; i++) {
154            const Slot& s = oldSlots[i];
155            if (!s.empty() && !s.removed()) {
156                this->uncheckedSet(s.val);
157            }
158        }
159        SkASSERT(fCount == oldCount);
160    }
161
162    int next(int index, int n) const {
163        // A valid strategy explores all slots in [0, fCapacity) as n walks from 0 to fCapacity-1.
164        // Both of these strategies are valid:
165        //return (index + 0 + 1) & (fCapacity-1);      // Linear probing.
166        return (index + n + 1) & (fCapacity-1);        // Quadratic probing.
167    }
168
169    static uint32_t Hash(const K& key) {
170        uint32_t hash = Traits::Hash(key);
171        return hash < 2 ? hash+2 : hash;  // We reserve hash 0 and 1 to mark empty or removed slots.
172    }
173
174    struct Slot {
175        Slot() : hash(0) {}
176        bool   empty() const { return this->hash == 0; }
177        bool removed() const { return this->hash == 1; }
178
179        void markRemoved() { this->hash = 1; }
180
181        T val;
182        uint32_t hash;
183    };
184
185    int fCount, fRemoved, fCapacity;
186    SkAutoTArray<Slot> fSlots;
187};
188
189// Maps K->V.  A more user-friendly wrapper around SkTHashTable, suitable for most use cases.
190// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two.
191template <typename K, typename V, uint32_t(*HashK)(const K&) = &SkGoodHash>
192class SkTHashMap : SkNoncopyable {
193public:
194    SkTHashMap() {}
195
196    // Clear the map.
197    void reset() { fTable.reset(); }
198
199    // How many key/value pairs are in the table?
200    int count() const { return fTable.count(); }
201
202    // N.B. The pointers returned by set() and find() are valid only until the next call to set().
203
204    // Set key to val in the table, replacing any previous value with the same key.
205    // We copy both key and val, and return a pointer to the value copy now in the table.
206    V* set(const K& key, const V& val) {
207        Pair in = { key, val };
208        Pair* out = fTable.set(in);
209        return &out->val;
210    }
211
212    // If there is key/value entry in the table with this key, return a pointer to the value.
213    // If not, return NULL.
214    V* find(const K& key) const {
215        if (Pair* p = fTable.find(key)) {
216            return &p->val;
217        }
218        return NULL;
219    }
220
221    // Remove the key/value entry in the table with this key.
222    void remove(const K& key) {
223        SkASSERT(this->find(key));
224        fTable.remove(key);
225    }
226
227    // Call fn on every key/value pair in the table.  You may mutate the value but not the key.
228    template <typename Fn>  // f(K, V*) or f(const K&, V*)
229    void foreach(Fn&& fn) {
230        fTable.foreach([&fn](Pair* p){ fn(p->key, &p->val); });
231    }
232
233    // Call fn on every key/value pair in the table.  You may not mutate anything.
234    template <typename Fn>  // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&).
235    void foreach(Fn&& fn) const {
236        fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); });
237    }
238
239private:
240    struct Pair {
241        K key;
242        V val;
243        static const K& GetKey(const Pair& p) { return p.key; }
244        static uint32_t Hash(const K& key) { return HashK(key); }
245    };
246
247    SkTHashTable<Pair, K> fTable;
248};
249
250// A set of T.  T is treated as an ordiary copyable C++ type.
251template <typename T, uint32_t(*HashT)(const T&) = &SkGoodHash>
252class SkTHashSet : SkNoncopyable {
253public:
254    SkTHashSet() {}
255
256    // Clear the set.
257    void reset() { fTable.reset(); }
258
259    // How many items are in the set?
260    int count() const { return fTable.count(); }
261
262    // Copy an item into the set.
263    void add(const T& item) { fTable.set(item); }
264
265    // Is this item in the set?
266    bool contains(const T& item) const { return SkToBool(this->find(item)); }
267
268    // If an item equal to this is in the set, return a pointer to it, otherwise null.
269    // This pointer remains valid until the next call to add().
270    const T* find(const T& item) const { return fTable.find(item); }
271
272    // Remove the item in the set equal to this.
273    void remove(const T& item) {
274        SkASSERT(this->contains(item));
275        fTable.remove(item);
276    }
277
278    // Call fn on every item in the set.  You may not mutate anything.
279    template <typename Fn>  // f(T), f(const T&)
280    void foreach (Fn&& fn) const {
281        fTable.foreach(fn);
282    }
283
284private:
285    struct Traits {
286        static const T& GetKey(const T& item) { return item; }
287        static uint32_t Hash(const T& item) { return HashT(item); }
288    };
289    SkTHashTable<T, T, Traits> fTable;
290};
291
292#endif//SkTHash_DEFINED
293