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