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