Line data Source code
1 : /*
2 : * Copyright 2013 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 SkTDynamicHash_DEFINED
9 : #define SkTDynamicHash_DEFINED
10 :
11 : #include "SkMath.h"
12 : #include "SkTemplates.h"
13 : #include "SkTypes.h"
14 :
15 : // Traits requires:
16 : // static const Key& GetKey(const T&) { ... }
17 : // static uint32_t Hash(const Key&) { ... }
18 : // We'll look on T for these by default, or you can pass a custom Traits type.
19 : template <typename T,
20 : typename Key,
21 : typename Traits = T,
22 : int kGrowPercent = 75> // Larger -> more memory efficient, but slower.
23 : class SkTDynamicHash {
24 : public:
25 0 : SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
26 0 : SkASSERT(this->validate());
27 0 : }
28 :
29 0 : ~SkTDynamicHash() {
30 0 : sk_free(fArray);
31 0 : }
32 :
33 : class Iter {
34 : public:
35 0 : explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
36 0 : SkASSERT(hash);
37 0 : ++(*this);
38 0 : }
39 0 : bool done() const {
40 0 : SkASSERT(fCurrentIndex <= fHash->fCapacity);
41 0 : return fCurrentIndex == fHash->fCapacity;
42 : }
43 0 : T& operator*() const {
44 0 : SkASSERT(!this->done());
45 0 : return *this->current();
46 : }
47 0 : void operator++() {
48 0 : do {
49 0 : fCurrentIndex++;
50 0 : } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
51 0 : }
52 :
53 : private:
54 0 : T* current() const { return fHash->fArray[fCurrentIndex]; }
55 :
56 : SkTDynamicHash* fHash;
57 : int fCurrentIndex;
58 : };
59 :
60 : class ConstIter {
61 : public:
62 0 : explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
63 0 : SkASSERT(hash);
64 0 : ++(*this);
65 0 : }
66 0 : bool done() const {
67 0 : SkASSERT(fCurrentIndex <= fHash->fCapacity);
68 0 : return fCurrentIndex == fHash->fCapacity;
69 : }
70 0 : const T& operator*() const {
71 0 : SkASSERT(!this->done());
72 0 : return *this->current();
73 : }
74 0 : void operator++() {
75 0 : do {
76 0 : fCurrentIndex++;
77 0 : } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
78 0 : }
79 :
80 : private:
81 0 : const T* current() const { return fHash->fArray[fCurrentIndex]; }
82 :
83 : const SkTDynamicHash* fHash;
84 : int fCurrentIndex;
85 : };
86 :
87 0 : int count() const { return fCount; }
88 :
89 : // Return the entry with this key if we have it, otherwise nullptr.
90 0 : T* find(const Key& key) const {
91 0 : int index = this->firstIndex(key);
92 0 : for (int round = 0; round < fCapacity; round++) {
93 0 : SkASSERT(index >= 0 && index < fCapacity);
94 0 : T* candidate = fArray[index];
95 0 : if (Empty() == candidate) {
96 0 : return nullptr;
97 : }
98 0 : if (Deleted() != candidate && GetKey(*candidate) == key) {
99 0 : return candidate;
100 : }
101 0 : index = this->nextIndex(index, round);
102 : }
103 0 : SkASSERT(fCapacity == 0);
104 0 : return nullptr;
105 : }
106 :
107 : // Add an entry with this key. We require that no entry with newEntry's key is already present.
108 0 : void add(T* newEntry) {
109 0 : SkASSERT(nullptr == this->find(GetKey(*newEntry)));
110 0 : this->maybeGrow();
111 0 : this->innerAdd(newEntry);
112 0 : SkASSERT(this->validate());
113 0 : }
114 :
115 : // Remove the entry with this key. We require that an entry with this key is present.
116 0 : void remove(const Key& key) {
117 0 : SkASSERT(this->find(key));
118 0 : this->innerRemove(key);
119 0 : SkASSERT(this->validate());
120 0 : }
121 :
122 0 : void rewind() {
123 0 : if (fArray) {
124 0 : sk_bzero(fArray, sizeof(T*)* fCapacity);
125 : }
126 0 : fCount = 0;
127 0 : fDeleted = 0;
128 0 : }
129 :
130 0 : void reset() {
131 0 : fCount = 0;
132 0 : fDeleted = 0;
133 0 : fCapacity = 0;
134 0 : sk_free(fArray);
135 0 : fArray = nullptr;
136 0 : }
137 :
138 : protected:
139 : // These methods are used by tests only.
140 :
141 : int capacity() const { return fCapacity; }
142 :
143 : // How many collisions do we go through before finding where this entry should be inserted?
144 : int countCollisions(const Key& key) const {
145 : int index = this->firstIndex(key);
146 : for (int round = 0; round < fCapacity; round++) {
147 : SkASSERT(index >= 0 && index < fCapacity);
148 : const T* candidate = fArray[index];
149 : if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
150 : return round;
151 : }
152 : index = this->nextIndex(index, round);
153 : }
154 : SkASSERT(fCapacity == 0);
155 : return 0;
156 : }
157 :
158 : private:
159 : // We have two special values to indicate an empty or deleted entry.
160 0 : static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr
161 0 : static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer.
162 :
163 0 : bool validate() const {
164 : #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false
165 : static const int kLarge = 50; // Arbitrary, tweak to suit your patience.
166 :
167 : // O(1) checks, always done.
168 : // Is capacity sane?
169 0 : SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
170 :
171 : // O(N) checks, skipped when very large.
172 0 : if (fCount < kLarge * kLarge) {
173 : // Are fCount and fDeleted correct, and are all elements findable?
174 0 : int count = 0, deleted = 0;
175 0 : for (int i = 0; i < fCapacity; i++) {
176 0 : if (Deleted() == fArray[i]) {
177 0 : deleted++;
178 0 : } else if (Empty() != fArray[i]) {
179 0 : count++;
180 0 : SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
181 : }
182 : }
183 0 : SKTDYNAMICHASH_CHECK(count == fCount);
184 0 : SKTDYNAMICHASH_CHECK(deleted == fDeleted);
185 : }
186 :
187 : // O(N^2) checks, skipped when large.
188 0 : if (fCount < kLarge) {
189 : // Are all entries unique?
190 0 : for (int i = 0; i < fCapacity; i++) {
191 0 : if (Empty() == fArray[i] || Deleted() == fArray[i]) {
192 0 : continue;
193 : }
194 0 : for (int j = i+1; j < fCapacity; j++) {
195 0 : if (Empty() == fArray[j] || Deleted() == fArray[j]) {
196 0 : continue;
197 : }
198 0 : SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
199 0 : SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
200 : }
201 : }
202 : }
203 : #undef SKTDYNAMICHASH_CHECK
204 0 : return true;
205 : }
206 :
207 0 : void innerAdd(T* newEntry) {
208 0 : const Key& key = GetKey(*newEntry);
209 0 : int index = this->firstIndex(key);
210 0 : for (int round = 0; round < fCapacity; round++) {
211 0 : SkASSERT(index >= 0 && index < fCapacity);
212 0 : const T* candidate = fArray[index];
213 0 : if (Empty() == candidate || Deleted() == candidate) {
214 0 : if (Deleted() == candidate) {
215 0 : fDeleted--;
216 : }
217 0 : fCount++;
218 0 : fArray[index] = newEntry;
219 0 : return;
220 : }
221 0 : index = this->nextIndex(index, round);
222 : }
223 0 : SkASSERT(fCapacity == 0);
224 : }
225 :
226 0 : void innerRemove(const Key& key) {
227 0 : const int firstIndex = this->firstIndex(key);
228 0 : int index = firstIndex;
229 0 : for (int round = 0; round < fCapacity; round++) {
230 0 : SkASSERT(index >= 0 && index < fCapacity);
231 0 : const T* candidate = fArray[index];
232 0 : if (Deleted() != candidate && GetKey(*candidate) == key) {
233 0 : fDeleted++;
234 0 : fCount--;
235 0 : fArray[index] = Deleted();
236 0 : return;
237 : }
238 0 : index = this->nextIndex(index, round);
239 : }
240 0 : SkASSERT(fCapacity == 0);
241 : }
242 :
243 0 : void maybeGrow() {
244 0 : if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
245 0 : this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
246 : }
247 0 : }
248 :
249 0 : void resize(int newCapacity) {
250 0 : SkDEBUGCODE(int oldCount = fCount;)
251 0 : int oldCapacity = fCapacity;
252 0 : SkAutoTMalloc<T*> oldArray(fArray);
253 :
254 0 : fCount = fDeleted = 0;
255 0 : fCapacity = newCapacity;
256 0 : fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
257 :
258 0 : for (int i = 0; i < oldCapacity; i++) {
259 0 : T* entry = oldArray[i];
260 0 : if (Empty() != entry && Deleted() != entry) {
261 0 : this->innerAdd(entry);
262 : }
263 : }
264 0 : SkASSERT(oldCount == fCount);
265 0 : }
266 :
267 : // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
268 0 : uint32_t hashMask() const { return fCapacity - 1; }
269 :
270 0 : int firstIndex(const Key& key) const {
271 0 : return Hash(key) & this->hashMask();
272 : }
273 :
274 : // Given index at round N, what is the index to check at N+1? round should start at 0.
275 0 : int nextIndex(int index, int round) const {
276 : // This will search a power-of-two array fully without repeating an index.
277 0 : return (index + round + 1) & this->hashMask();
278 : }
279 :
280 0 : static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
281 0 : static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
282 :
283 : int fCount; // Number of non Empty(), non Deleted() entries in fArray.
284 : int fDeleted; // Number of Deleted() entries in fArray.
285 : int fCapacity; // Number of entries in fArray. Always a power of 2.
286 : T** fArray;
287 : };
288 :
289 : #endif
|
