OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 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 SkTDynamicHash_DEFINED | 8 #ifndef SkTDynamicHash_DEFINED |
9 #define SkTDynamicHash_DEFINED | 9 #define SkTDynamicHash_DEFINED |
10 | 10 |
11 #include "SkTypes.h" | 11 #include "SkTypes.h" |
12 #include "SkMath.h" | 12 #include "SkMath.h" |
13 | 13 |
14 template <typename T, | 14 template <typename T, |
15 typename Key, | 15 typename Key, |
16 const Key& (GetKey)(const T&), | 16 const Key& (GetKey)(const T&), |
17 uint32_t (Hash)(const Key&), | 17 uint32_t (Hash)(const Key&), |
18 bool (Equal)(const T&, const Key&), | 18 bool (Equal)(const T&, const Key&), |
19 int kGrowPercent = 75, // Larger -> more memory efficient, but slow
er. | 19 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. |
20 int kShrinkPercent = 25> | |
21 class SkTDynamicHash { | 20 class SkTDynamicHash { |
22 static const int kMinCapacity = 4; // Smallest capacity we allow. | |
23 public: | 21 public: |
24 SkTDynamicHash(int initialCapacity=64/sizeof(T*)) { | 22 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { |
25 this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity
: kMinCapacity)); | |
26 SkASSERT(this->validate()); | 23 SkASSERT(this->validate()); |
27 } | 24 } |
28 | 25 |
29 ~SkTDynamicHash() { | 26 ~SkTDynamicHash() { |
30 sk_free(fArray); | 27 sk_free(fArray); |
31 } | 28 } |
32 | 29 |
33 int count() const { return fCount; } | 30 int count() const { return fCount; } |
34 | 31 |
35 // Return the entry with this key if we have it, otherwise NULL. | 32 // Return the entry with this key if we have it, otherwise NULL. |
36 T* find(const Key& key) const { | 33 T* find(const Key& key) const { |
37 int index = this->firstIndex(key); | 34 int index = this->firstIndex(key); |
38 for (int round = 0; round < fCapacity; round++) { | 35 for (int round = 0; round < fCapacity; round++) { |
39 T* candidate = fArray[index]; | 36 T* candidate = fArray[index]; |
40 if (Empty() == candidate) { | 37 if (Empty() == candidate) { |
41 return NULL; | 38 return NULL; |
42 } | 39 } |
43 if (Deleted() != candidate && Equal(*candidate, key)) { | 40 if (Deleted() != candidate && Equal(*candidate, key)) { |
44 return candidate; | 41 return candidate; |
45 } | 42 } |
46 index = this->nextIndex(index, round); | 43 index = this->nextIndex(index, round); |
47 } | 44 } |
48 SkASSERT(0); // find: should be unreachable | 45 SkASSERT(fCapacity == 0); |
49 return NULL; | 46 return NULL; |
50 } | 47 } |
51 | 48 |
52 // Add an entry with this key. We require that no entry with newEntry's key
is already present. | 49 // Add an entry with this key. We require that no entry with newEntry's key
is already present. |
53 void add(T* newEntry) { | 50 void add(T* newEntry) { |
54 SkASSERT(NULL == this->find(GetKey(*newEntry))); | 51 SkASSERT(NULL == this->find(GetKey(*newEntry))); |
55 this->maybeGrow(); | 52 this->maybeGrow(); |
56 SkASSERT(this->validate()); | 53 SkASSERT(this->validate()); |
57 this->innerAdd(newEntry); | 54 this->innerAdd(newEntry); |
58 SkASSERT(this->validate()); | 55 SkASSERT(this->validate()); |
59 } | 56 } |
60 | 57 |
61 // Remove the entry with this key. We reqire that an entry with this key is
present. | 58 // Remove the entry with this key. We reqire that an entry with this key is
present. |
62 void remove(const Key& key) { | 59 void remove(const Key& key) { |
63 SkASSERT(NULL != this->find(key)); | 60 SkASSERT(NULL != this->find(key)); |
64 this->innerRemove(key); | 61 this->innerRemove(key); |
65 SkASSERT(this->validate()); | 62 SkASSERT(this->validate()); |
66 this->maybeShrink(); | |
67 SkASSERT(this->validate()); | |
68 } | 63 } |
69 | 64 |
70 protected: | 65 protected: |
71 // These methods are used by tests only. | 66 // These methods are used by tests only. |
72 | 67 |
73 int capacity() const { return fCapacity; } | 68 int capacity() const { return fCapacity; } |
74 | 69 |
75 // How many collisions do we go through before finding where this entry shou
ld be inserted? | 70 // How many collisions do we go through before finding where this entry shou
ld be inserted? |
76 int countCollisions(const Key& key) const { | 71 int countCollisions(const Key& key) const { |
77 int index = this->firstIndex(key); | 72 int index = this->firstIndex(key); |
78 for (int round = 0; round < fCapacity; round++) { | 73 for (int round = 0; round < fCapacity; round++) { |
79 const T* candidate = fArray[index]; | 74 const T* candidate = fArray[index]; |
80 if (Empty() == candidate || Deleted() == candidate || Equal(*candida
te, key)) { | 75 if (Empty() == candidate || Deleted() == candidate || Equal(*candida
te, key)) { |
81 return round; | 76 return round; |
82 } | 77 } |
83 index = this->nextIndex(index, round); | 78 index = this->nextIndex(index, round); |
84 } | 79 } |
85 SkASSERT(0); // countCollisions: should be unreachable | 80 SkASSERT(fCapacity == 0); |
86 return -1; | 81 return 0; |
87 } | 82 } |
88 | 83 |
89 private: | 84 private: |
90 // We have two special values to indicate an empty or deleted entry. | 85 // We have two special values to indicate an empty or deleted entry. |
91 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL | 86 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL |
92 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. | 87 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. |
93 | 88 |
94 static T** AllocArray(int capacity) { | |
95 return (T**)sk_calloc_throw(sizeof(T*) * capacity); // All cells == Emp
ty(). | |
96 } | |
97 | |
98 void reset(int capacity) { | |
99 fCount = 0; | |
100 fDeleted = 0; | |
101 fCapacity = capacity; | |
102 fArray = AllocArray(fCapacity); | |
103 } | |
104 | |
105 bool validate() const { | 89 bool validate() const { |
106 #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false | 90 #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false |
107 | 91 |
108 // Is capacity sane? | 92 // Is capacity sane? |
109 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); | 93 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); |
110 SKTDYNAMICHASH_CHECK(fCapacity >= kMinCapacity); | |
111 | 94 |
112 // Is fCount correct? | 95 // Is fCount correct? |
113 int count = 0; | 96 int count = 0; |
114 for (int i = 0; i < fCapacity; i++) { | 97 for (int i = 0; i < fCapacity; i++) { |
115 if (Empty() != fArray[i] && Deleted() != fArray[i]) { | 98 if (Empty() != fArray[i] && Deleted() != fArray[i]) { |
116 count++; | 99 count++; |
117 } | 100 } |
118 } | 101 } |
119 SKTDYNAMICHASH_CHECK(count == fCount); | 102 SKTDYNAMICHASH_CHECK(count == fCount); |
120 | 103 |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
161 if (Empty() == candidate || Deleted() == candidate) { | 144 if (Empty() == candidate || Deleted() == candidate) { |
162 if (Deleted() == candidate) { | 145 if (Deleted() == candidate) { |
163 fDeleted--; | 146 fDeleted--; |
164 } | 147 } |
165 fCount++; | 148 fCount++; |
166 fArray[index] = newEntry; | 149 fArray[index] = newEntry; |
167 return; | 150 return; |
168 } | 151 } |
169 index = this->nextIndex(index, round); | 152 index = this->nextIndex(index, round); |
170 } | 153 } |
171 SkASSERT(0); // add: should be unreachable | 154 SkASSERT(fCapacity == 0); |
172 } | 155 } |
173 | 156 |
174 void innerRemove(const Key& key) { | 157 void innerRemove(const Key& key) { |
175 const int firstIndex = this->firstIndex(key); | 158 const int firstIndex = this->firstIndex(key); |
176 int index = firstIndex; | 159 int index = firstIndex; |
177 for (int round = 0; round < fCapacity; round++) { | 160 for (int round = 0; round < fCapacity; round++) { |
178 const T* candidate = fArray[index]; | 161 const T* candidate = fArray[index]; |
179 if (Deleted() != candidate && Equal(*candidate, key)) { | 162 if (Deleted() != candidate && Equal(*candidate, key)) { |
180 fDeleted++; | 163 fDeleted++; |
181 fCount--; | 164 fCount--; |
182 fArray[index] = Deleted(); | 165 fArray[index] = Deleted(); |
183 return; | 166 return; |
184 } | 167 } |
185 index = this->nextIndex(index, round); | 168 index = this->nextIndex(index, round); |
186 } | 169 } |
187 SkASSERT(0); // innerRemove: should be unreachable | 170 SkASSERT(fCapacity == 0); |
188 } | 171 } |
189 | 172 |
190 void maybeGrow() { | 173 void maybeGrow() { |
191 if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) { | 174 if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) { |
192 resize(fCapacity * 2); | 175 this->resize(fCapacity > 0 ? fCapacity * 2 : 4); |
193 } | |
194 } | |
195 | |
196 void maybeShrink() { | |
197 if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinC
apacity) { | |
198 resize(fCapacity / 2); | |
199 } | 176 } |
200 } | 177 } |
201 | 178 |
202 void resize(int newCapacity) { | 179 void resize(int newCapacity) { |
203 SkDEBUGCODE(int oldCount = fCount;) | 180 SkDEBUGCODE(int oldCount = fCount;) |
204 int oldCapacity = fCapacity; | 181 int oldCapacity = fCapacity; |
205 T** oldArray = fArray; | 182 SkAutoTMalloc<T*> oldArray(fArray); |
206 | 183 |
207 reset(newCapacity); | 184 fCount = fDeleted = 0; |
| 185 fCapacity = newCapacity; |
| 186 fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity); |
208 | 187 |
209 for (int i = 0; i < oldCapacity; i++) { | 188 for (int i = 0; i < oldCapacity; i++) { |
210 T* entry = oldArray[i]; | 189 T* entry = oldArray[i]; |
211 if (Empty() != entry && Deleted() != entry) { | 190 if (Empty() != entry && Deleted() != entry) { |
212 this->add(entry); | 191 this->innerAdd(entry); |
213 } | 192 } |
214 } | 193 } |
215 SkASSERT(oldCount == fCount); | 194 SkASSERT(oldCount == fCount); |
216 | |
217 sk_free(oldArray); | |
218 } | 195 } |
219 | 196 |
220 // fCapacity is always a power of 2, so this masks the correct low bits to i
ndex into our hash. | 197 // fCapacity is always a power of 2, so this masks the correct low bits to i
ndex into our hash. |
221 uint32_t hashMask() const { return fCapacity - 1; } | 198 uint32_t hashMask() const { return fCapacity - 1; } |
222 | 199 |
223 int firstIndex(const Key& key) const { | 200 int firstIndex(const Key& key) const { |
224 return Hash(key) & this->hashMask(); | 201 return Hash(key) & this->hashMask(); |
225 } | 202 } |
226 | 203 |
227 // Given index at round N, what is the index to check at N+1? round should
start at 0. | 204 // Given index at round N, what is the index to check at N+1? round should
start at 0. |
228 int nextIndex(int index, int round) const { | 205 int nextIndex(int index, int round) const { |
229 // This will search a power-of-two array fully without repeating an inde
x. | 206 // This will search a power-of-two array fully without repeating an inde
x. |
230 return (index + round + 1) & this->hashMask(); | 207 return (index + round + 1) & this->hashMask(); |
231 } | 208 } |
232 | 209 |
233 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 210 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
234 int fDeleted; // Number of Deleted() entries in fArray. | 211 int fDeleted; // Number of Deleted() entries in fArray. |
235 int fCapacity; // Number of entries in fArray. Always a power of 2. | 212 int fCapacity; // Number of entries in fArray. Always a power of 2. |
236 T** fArray; | 213 T** fArray; |
237 }; | 214 }; |
238 | 215 |
239 #endif | 216 #endif |
OLD | NEW |