• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
24 template <typename T, typename K, typename Traits = T>
25 class SkTHashTable : SkNoncopyable {
26 public:
SkTHashTable()27     SkTHashTable() : fCount(0), fRemoved(0), fCapacity(0) {}
28 
29     // Clear the table.
reset()30     void reset() {
31         this->~SkTHashTable();
32         SkNEW_PLACEMENT(this, SkTHashTable);
33     }
34 
35     // How many entries are in the table?
count()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.
set(const T & val)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.
find(const K & key)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.
remove(const K & key)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*)
foreach(Fn && fn)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&)
foreach(Fn && fn)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 
115 private:
uncheckedSet(const T & val)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 
resize(int capacity)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 
next(int index,int n)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 
Hash(const K & key)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 {
SlotSlot175         Slot() : hash(0) {}
emptySlot176         bool   empty() const { return this->hash == 0; }
removedSlot177         bool removed() const { return this->hash == 1; }
178 
markRemovedSlot179         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.
191 template <typename K, typename V, uint32_t(*HashK)(const K&) = &SkGoodHash>
192 class SkTHashMap : SkNoncopyable {
193 public:
SkTHashMap()194     SkTHashMap() {}
195 
196     // Clear the map.
reset()197     void reset() { fTable.reset(); }
198 
199     // How many key/value pairs are in the table?
count()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.
set(const K & key,const V & val)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.
find(const K & key)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.
remove(const K & 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*)
foreach(Fn && fn)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&).
foreach(Fn && fn)235     void foreach(Fn&& fn) const {
236         fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); });
237     }
238 
239 private:
240     struct Pair {
241         K key;
242         V val;
GetKeyPair243         static const K& GetKey(const Pair& p) { return p.key; }
HashPair244         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.
251 template <typename T, uint32_t(*HashT)(const T&) = &SkGoodHash>
252 class SkTHashSet : SkNoncopyable {
253 public:
SkTHashSet()254     SkTHashSet() {}
255 
256     // Clear the set.
reset()257     void reset() { fTable.reset(); }
258 
259     // How many items are in the set?
count()260     int count() const { return fTable.count(); }
261 
262     // Copy an item into the set.
add(const T & item)263     void add(const T& item) { fTable.set(item); }
264 
265     // Is this item in the set?
contains(const T & item)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().
find(const T & item)270     const T* find(const T& item) const { return fTable.find(item); }
271 
272     // Remove the item in the set equal to this.
remove(const T & item)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&)
foreach(Fn && fn)280     void foreach (Fn&& fn) const {
281         fTable.foreach(fn);
282     }
283 
284 private:
285     struct Traits {
GetKeyTraits286         static const T& GetKey(const T& item) { return item; }
HashTraits287         static uint32_t Hash(const T& item) { return HashT(item); }
288     };
289     SkTHashTable<T, T, Traits> fTable;
290 };
291 
292 #endif//SkTHash_DEFINED
293