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 "include/core/SkTypes.h" |
12 | #include "include/private/SkChecksum.h" |
13 | #include "include/private/SkTemplates.h" |
14 | #include <new> |
15 | |
16 | // Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you. |
17 | // They're easier to use, usually perform the same, and have fewer sharp edges. |
18 | |
19 | // T and K are treated as ordinary copyable C++ types. |
20 | // Traits must have: |
21 | // - static K GetKey(T) |
22 | // - static uint32_t Hash(K) |
23 | // If the key is large and stored inside T, you may want to make K a const&. |
24 | // Similarly, if T is large you might want it to be a pointer. |
25 | template <typename T, typename K, typename Traits = T> |
26 | class SkTHashTable { |
27 | public: |
28 | SkTHashTable() : fCount(0), fCapacity(0) {} |
29 | SkTHashTable(SkTHashTable&& other) |
30 | : fCount(other.fCount) |
31 | , fCapacity(other.fCapacity) |
32 | , fSlots(std::move(other.fSlots)) { other.fCount = other.fCapacity = 0; } |
33 | |
34 | SkTHashTable& operator=(SkTHashTable&& other) { |
35 | if (this != &other) { |
36 | this->~SkTHashTable(); |
37 | new (this) SkTHashTable(std::move(other)); |
38 | } |
39 | return *this; |
40 | } |
41 | |
42 | // Clear the table. |
43 | void reset() { *this = SkTHashTable(); } |
44 | |
45 | // How many entries are in the table? |
46 | int count() const { return fCount; } |
47 | |
48 | // Approximately how many bytes of memory do we use beyond sizeof(*this)? |
49 | size_t approxBytesUsed() const { return fCapacity * sizeof(Slot); } |
50 | |
51 | // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!! |
52 | // set(), find() and foreach() all allow mutable access to table entries. |
53 | // If you change an entry so that it no longer has the same key, all hell |
54 | // will break loose. Do not do that! |
55 | // |
56 | // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger. |
57 | |
58 | // The pointers returned by set() and find() are valid only until the next call to set(). |
59 | // The pointers you receive in foreach() are only valid for its duration. |
60 | |
61 | // Copy val into the hash table, returning a pointer to the copy now in the table. |
62 | // If there already is an entry in the table with the same key, we overwrite it. |
63 | T* set(T val) { |
64 | if (4 * fCount >= 3 * fCapacity) { |
65 | this->resize(fCapacity > 0 ? fCapacity * 2 : 4); |
66 | } |
67 | return this->uncheckedSet(std::move(val)); |
68 | } |
69 | |
70 | // If there is an entry in the table with this key, return a pointer to it. If not, null. |
71 | T* find(const K& key) const { |
72 | uint32_t hash = Hash(key); |
73 | int index = hash & (fCapacity-1); |
74 | for (int n = 0; n < fCapacity; n++) { |
75 | Slot& s = fSlots[index]; |
76 | if (s.empty()) { |
77 | return nullptr; |
78 | } |
79 | if (hash == s.hash && key == Traits::GetKey(s.val)) { |
80 | return &s.val; |
81 | } |
82 | index = this->next(index); |
83 | } |
84 | SkASSERT(fCapacity == 0); |
85 | return nullptr; |
86 | } |
87 | |
88 | // If there is an entry in the table with this key, return it. If not, null. |
89 | // This only works for pointer type T, and cannot be used to find an nullptr entry. |
90 | T findOrNull(const K& key) const { |
91 | if (T* p = this->find(key)) { |
92 | return *p; |
93 | } |
94 | return nullptr; |
95 | } |
96 | |
97 | // Remove the value with this key from the hash table. |
98 | void remove(const K& key) { |
99 | SkASSERT(this->find(key)); |
100 | |
101 | uint32_t hash = Hash(key); |
102 | int index = hash & (fCapacity-1); |
103 | for (int n = 0; n < fCapacity; n++) { |
104 | Slot& s = fSlots[index]; |
105 | SkASSERT(!s.empty()); |
106 | if (hash == s.hash && key == Traits::GetKey(s.val)) { |
107 | this->removeSlot(index); |
108 | if (4 * fCount <= fCapacity && fCapacity > 4) { |
109 | this->resize(fCapacity / 2); |
110 | } |
111 | return; |
112 | } |
113 | index = this->next(index); |
114 | } |
115 | } |
116 | |
117 | // Call fn on every entry in the table. You may mutate the entries, but be very careful. |
118 | template <typename Fn> // f(T*) |
119 | void foreach(Fn&& fn) { |
120 | for (int i = 0; i < fCapacity; i++) { |
121 | if (!fSlots[i].empty()) { |
122 | fn(&fSlots[i].val); |
123 | } |
124 | } |
125 | } |
126 | |
127 | // Call fn on every entry in the table. You may not mutate anything. |
128 | template <typename Fn> // f(T) or f(const T&) |
129 | void foreach(Fn&& fn) const { |
130 | for (int i = 0; i < fCapacity; i++) { |
131 | if (!fSlots[i].empty()) { |
132 | fn(fSlots[i].val); |
133 | } |
134 | } |
135 | } |
136 | |
137 | private: |
138 | T* uncheckedSet(T&& val) { |
139 | const K& key = Traits::GetKey(val); |
140 | uint32_t hash = Hash(key); |
141 | int index = hash & (fCapacity-1); |
142 | for (int n = 0; n < fCapacity; n++) { |
143 | Slot& s = fSlots[index]; |
144 | if (s.empty()) { |
145 | // New entry. |
146 | s.val = std::move(val); |
147 | s.hash = hash; |
148 | fCount++; |
149 | return &s.val; |
150 | } |
151 | if (hash == s.hash && key == Traits::GetKey(s.val)) { |
152 | // Overwrite previous entry. |
153 | // Note: this triggers extra copies when adding the same value repeatedly. |
154 | s.val = std::move(val); |
155 | return &s.val; |
156 | } |
157 | |
158 | index = this->next(index); |
159 | } |
160 | SkASSERT(false); |
161 | return nullptr; |
162 | } |
163 | |
164 | void resize(int capacity) { |
165 | int oldCapacity = fCapacity; |
166 | SkDEBUGCODE(int oldCount = fCount); |
167 | |
168 | fCount = 0; |
169 | fCapacity = capacity; |
170 | SkAutoTArray<Slot> oldSlots = std::move(fSlots); |
171 | fSlots = SkAutoTArray<Slot>(capacity); |
172 | |
173 | for (int i = 0; i < oldCapacity; i++) { |
174 | Slot& s = oldSlots[i]; |
175 | if (!s.empty()) { |
176 | this->uncheckedSet(std::move(s.val)); |
177 | } |
178 | } |
179 | SkASSERT(fCount == oldCount); |
180 | } |
181 | |
182 | void removeSlot(int index) { |
183 | fCount--; |
184 | |
185 | // Rearrange elements to restore the invariants for linear probing. |
186 | for (;;) { |
187 | Slot& emptySlot = fSlots[index]; |
188 | int emptyIndex = index; |
189 | int originalIndex; |
190 | // Look for an element that can be moved into the empty slot. |
191 | // If the empty slot is in between where an element landed, and its native slot, then |
192 | // move it to the empty slot. Don't move it if its native slot is in between where |
193 | // the element landed and the empty slot. |
194 | // [native] <= [empty] < [candidate] == GOOD, can move candidate to empty slot |
195 | // [empty] < [native] < [candidate] == BAD, need to leave candidate where it is |
196 | do { |
197 | index = this->next(index); |
198 | Slot& s = fSlots[index]; |
199 | if (s.empty()) { |
200 | // We're done shuffling elements around. Clear the last empty slot. |
201 | emptySlot = Slot(); |
202 | return; |
203 | } |
204 | originalIndex = s.hash & (fCapacity - 1); |
205 | } while ((index <= originalIndex && originalIndex < emptyIndex) |
206 | || (originalIndex < emptyIndex && emptyIndex < index) |
207 | || (emptyIndex < index && index <= originalIndex)); |
208 | // Move the element to the empty slot. |
209 | Slot& moveFrom = fSlots[index]; |
210 | emptySlot = std::move(moveFrom); |
211 | } |
212 | } |
213 | |
214 | int next(int index) const { |
215 | index--; |
216 | if (index < 0) { index += fCapacity; } |
217 | return index; |
218 | } |
219 | |
220 | static uint32_t Hash(const K& key) { |
221 | uint32_t hash = Traits::Hash(key) & 0xffffffff; |
222 | return hash ? hash : 1; // We reserve hash 0 to mark empty. |
223 | } |
224 | |
225 | struct Slot { |
226 | Slot() : val{}, hash(0) {} |
227 | Slot(T&& v, uint32_t h) : val(std::move(v)), hash(h) {} |
228 | Slot(Slot&& o) { *this = std::move(o); } |
229 | Slot& operator=(Slot&& o) { |
230 | val = std::move(o.val); |
231 | hash = o.hash; |
232 | return *this; |
233 | } |
234 | |
235 | bool empty() const { return this->hash == 0; } |
236 | |
237 | T val; |
238 | uint32_t hash; |
239 | }; |
240 | |
241 | int fCount, fCapacity; |
242 | SkAutoTArray<Slot> fSlots; |
243 | |
244 | SkTHashTable(const SkTHashTable&) = delete; |
245 | SkTHashTable& operator=(const SkTHashTable&) = delete; |
246 | }; |
247 | |
248 | // Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases. |
249 | // K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two. |
250 | template <typename K, typename V, typename HashK = SkGoodHash> |
251 | class SkTHashMap { |
252 | public: |
253 | SkTHashMap() {} |
254 | SkTHashMap(SkTHashMap&&) = default; |
255 | SkTHashMap& operator=(SkTHashMap&&) = default; |
256 | |
257 | // Clear the map. |
258 | void reset() { fTable.reset(); } |
259 | |
260 | // How many key/value pairs are in the table? |
261 | int count() const { return fTable.count(); } |
262 | |
263 | // Approximately how many bytes of memory do we use beyond sizeof(*this)? |
264 | size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } |
265 | |
266 | // N.B. The pointers returned by set() and find() are valid only until the next call to set(). |
267 | |
268 | // Set key to val in the table, replacing any previous value with the same key. |
269 | // We copy both key and val, and return a pointer to the value copy now in the table. |
270 | V* set(K key, V val) { |
271 | Pair* out = fTable.set({std::move(key), std::move(val)}); |
272 | return &out->val; |
273 | } |
274 | |
275 | // If there is key/value entry in the table with this key, return a pointer to the value. |
276 | // If not, return null. |
277 | V* find(const K& key) const { |
278 | if (Pair* p = fTable.find(key)) { |
279 | return &p->val; |
280 | } |
281 | return nullptr; |
282 | } |
283 | |
284 | V& operator[](const K& key) { |
285 | if (V* val = this->find(key)) { |
286 | return *val; |
287 | } |
288 | return *this->set(key, V{}); |
289 | } |
290 | |
291 | // Remove the key/value entry in the table with this key. |
292 | void remove(const K& key) { |
293 | SkASSERT(this->find(key)); |
294 | fTable.remove(key); |
295 | } |
296 | |
297 | // Call fn on every key/value pair in the table. You may mutate the value but not the key. |
298 | template <typename Fn> // f(K, V*) or f(const K&, V*) |
299 | void foreach(Fn&& fn) { |
300 | fTable.foreach([&fn](Pair* p){ fn(p->key, &p->val); }); |
301 | } |
302 | |
303 | // Call fn on every key/value pair in the table. You may not mutate anything. |
304 | template <typename Fn> // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&). |
305 | void foreach(Fn&& fn) const { |
306 | fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); }); |
307 | } |
308 | |
309 | private: |
310 | struct Pair { |
311 | K key; |
312 | V val; |
313 | static const K& GetKey(const Pair& p) { return p.key; } |
314 | static auto Hash(const K& key) { return HashK()(key); } |
315 | }; |
316 | |
317 | SkTHashTable<Pair, K> fTable; |
318 | |
319 | SkTHashMap(const SkTHashMap&) = delete; |
320 | SkTHashMap& operator=(const SkTHashMap&) = delete; |
321 | }; |
322 | |
323 | // A set of T. T is treated as an ordinary copyable C++ type. |
324 | template <typename T, typename HashT = SkGoodHash> |
325 | class SkTHashSet { |
326 | public: |
327 | SkTHashSet() {} |
328 | SkTHashSet(SkTHashSet&&) = default; |
329 | SkTHashSet& operator=(SkTHashSet&&) = default; |
330 | |
331 | // Clear the set. |
332 | void reset() { fTable.reset(); } |
333 | |
334 | // How many items are in the set? |
335 | int count() const { return fTable.count(); } |
336 | |
337 | // Is empty? |
338 | bool empty() const { return fTable.count() == 0; } |
339 | |
340 | // Approximately how many bytes of memory do we use beyond sizeof(*this)? |
341 | size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } |
342 | |
343 | // Copy an item into the set. |
344 | void add(T item) { fTable.set(std::move(item)); } |
345 | |
346 | // Is this item in the set? |
347 | bool contains(const T& item) const { return SkToBool(this->find(item)); } |
348 | |
349 | // If an item equal to this is in the set, return a pointer to it, otherwise null. |
350 | // This pointer remains valid until the next call to add(). |
351 | const T* find(const T& item) const { return fTable.find(item); } |
352 | |
353 | // Remove the item in the set equal to this. |
354 | void remove(const T& item) { |
355 | SkASSERT(this->contains(item)); |
356 | fTable.remove(item); |
357 | } |
358 | |
359 | // Call fn on every item in the set. You may not mutate anything. |
360 | template <typename Fn> // f(T), f(const T&) |
361 | void foreach (Fn&& fn) const { |
362 | fTable.foreach(fn); |
363 | } |
364 | |
365 | private: |
366 | struct Traits { |
367 | static const T& GetKey(const T& item) { return item; } |
368 | static auto Hash(const T& item) { return HashT()(item); } |
369 | }; |
370 | SkTHashTable<T, T, Traits> fTable; |
371 | |
372 | SkTHashSet(const SkTHashSet&) = delete; |
373 | SkTHashSet& operator=(const SkTHashSet&) = delete; |
374 | }; |
375 | |
376 | #endif//SkTHash_DEFINED |
377 | |