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.
25template <typename T, typename K, typename Traits = T>
26class SkTHashTable {
27public:
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
137private:
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.
250template <typename K, typename V, typename HashK = SkGoodHash>
251class SkTHashMap {
252public:
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
309private:
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.
324template <typename T, typename HashT = SkGoodHash>
325class SkTHashSet {
326public:
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
365private:
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