• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
SkTDynamicHash()25     SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
26         SkASSERT(this->validate());
27     }
28 
~SkTDynamicHash()29     ~SkTDynamicHash() {
30         sk_free(fArray);
31     }
32 
33     class Iter {
34     public:
Iter(SkTDynamicHash * hash)35         explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
36             SkASSERT(hash);
37             ++(*this);
38         }
done()39         bool done() const {
40             SkASSERT(fCurrentIndex <= fHash->fCapacity);
41             return fCurrentIndex == fHash->fCapacity;
42         }
43         T& operator*() const {
44             SkASSERT(!this->done());
45             return *this->current();
46         }
47         void operator++() {
48             do {
49                 fCurrentIndex++;
50             } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
51         }
52 
53     private:
current()54         T* current() const { return fHash->fArray[fCurrentIndex]; }
55 
56         SkTDynamicHash* fHash;
57         int fCurrentIndex;
58     };
59 
60     class ConstIter {
61     public:
ConstIter(const SkTDynamicHash * hash)62         explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
63             SkASSERT(hash);
64             ++(*this);
65         }
done()66         bool done() const {
67             SkASSERT(fCurrentIndex <= fHash->fCapacity);
68             return fCurrentIndex == fHash->fCapacity;
69         }
70         const T& operator*() const {
71             SkASSERT(!this->done());
72             return *this->current();
73         }
74         void operator++() {
75             do {
76                 fCurrentIndex++;
77             } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
78         }
79 
80     private:
current()81         const T* current() const { return fHash->fArray[fCurrentIndex]; }
82 
83         const SkTDynamicHash* fHash;
84         int fCurrentIndex;
85     };
86 
count()87     int count() const { return fCount; }
88 
89     // Return the entry with this key if we have it, otherwise nullptr.
find(const Key & key)90     T* find(const Key& key) const {
91         int index = this->firstIndex(key);
92         for (int round = 0; round < fCapacity; round++) {
93             SkASSERT(index >= 0 && index < fCapacity);
94             T* candidate = fArray[index];
95             if (Empty() == candidate) {
96                 return nullptr;
97             }
98             if (Deleted() != candidate && GetKey(*candidate) == key) {
99                 return candidate;
100             }
101             index = this->nextIndex(index, round);
102         }
103         SkASSERT(fCapacity == 0);
104         return nullptr;
105     }
106 
107     // Add an entry with this key.  We require that no entry with newEntry's key is already present.
add(T * newEntry)108     void add(T* newEntry) {
109         SkASSERT(nullptr == this->find(GetKey(*newEntry)));
110         this->maybeGrow();
111         this->innerAdd(newEntry);
112         SkASSERT(this->validate());
113     }
114 
115     // Remove the entry with this key.  We require that an entry with this key is present.
remove(const Key & key)116     void remove(const Key& key) {
117         SkASSERT(this->find(key));
118         this->innerRemove(key);
119         SkASSERT(this->validate());
120     }
121 
rewind()122     void rewind() {
123         if (fArray) {
124             sk_bzero(fArray, sizeof(T*)* fCapacity);
125         }
126         fCount = 0;
127         fDeleted = 0;
128     }
129 
reset()130     void reset() {
131         fCount = 0;
132         fDeleted = 0;
133         fCapacity = 0;
134         sk_free(fArray);
135         fArray = nullptr;
136     }
137 
138 protected:
139     // These methods are used by tests only.
140 
capacity()141     int capacity() const { return fCapacity; }
142 
143     // How many collisions do we go through before finding where this entry should be inserted?
countCollisions(const Key & key)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.
Empty()160     static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. nullptr
Deleted()161     static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
162 
validate()163     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         SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
170 
171         // O(N) checks, skipped when very large.
172         if (fCount < kLarge * kLarge) {
173             // Are fCount and fDeleted correct, and are all elements findable?
174             int count = 0, deleted = 0;
175             for (int i = 0; i < fCapacity; i++) {
176                 if (Deleted() == fArray[i]) {
177                     deleted++;
178                 } else if (Empty() != fArray[i]) {
179                     count++;
180                     SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
181                 }
182             }
183             SKTDYNAMICHASH_CHECK(count == fCount);
184             SKTDYNAMICHASH_CHECK(deleted == fDeleted);
185         }
186 
187         // O(N^2) checks, skipped when large.
188         if (fCount < kLarge) {
189             // Are all entries unique?
190             for (int i = 0; i < fCapacity; i++) {
191                 if (Empty() == fArray[i] || Deleted() == fArray[i]) {
192                     continue;
193                 }
194                 for (int j = i+1; j < fCapacity; j++) {
195                     if (Empty() == fArray[j] || Deleted() == fArray[j]) {
196                         continue;
197                     }
198                     SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
199                     SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
200                 }
201             }
202         }
203         #undef SKTDYNAMICHASH_CHECK
204         return true;
205     }
206 
innerAdd(T * newEntry)207     void innerAdd(T* newEntry) {
208         const Key& key = GetKey(*newEntry);
209         int index = this->firstIndex(key);
210         for (int round = 0; round < fCapacity; round++) {
211             SkASSERT(index >= 0 && index < fCapacity);
212             const T* candidate = fArray[index];
213             if (Empty() == candidate || Deleted() == candidate) {
214                 if (Deleted() == candidate) {
215                     fDeleted--;
216                 }
217                 fCount++;
218                 fArray[index] = newEntry;
219                 return;
220             }
221             index = this->nextIndex(index, round);
222         }
223         SkASSERT(fCapacity == 0);
224     }
225 
innerRemove(const Key & key)226     void innerRemove(const Key& key) {
227         const int firstIndex = this->firstIndex(key);
228         int index = firstIndex;
229         for (int round = 0; round < fCapacity; round++) {
230             SkASSERT(index >= 0 && index < fCapacity);
231             const T* candidate = fArray[index];
232             if (Deleted() != candidate && GetKey(*candidate) == key) {
233                 fDeleted++;
234                 fCount--;
235                 fArray[index] = Deleted();
236                 return;
237             }
238             index = this->nextIndex(index, round);
239         }
240         SkASSERT(fCapacity == 0);
241     }
242 
maybeGrow()243     void maybeGrow() {
244         if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
245             this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
246         }
247     }
248 
resize(int newCapacity)249     void resize(int newCapacity) {
250         SkDEBUGCODE(int oldCount = fCount;)
251         int oldCapacity = fCapacity;
252         SkAutoTMalloc<T*> oldArray(fArray);
253 
254         fCount = fDeleted = 0;
255         fCapacity = newCapacity;
256         fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
257 
258         for (int i = 0; i < oldCapacity; i++) {
259             T* entry = oldArray[i];
260             if (Empty() != entry && Deleted() != entry) {
261                 this->innerAdd(entry);
262             }
263         }
264         SkASSERT(oldCount == fCount);
265     }
266 
267     // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
hashMask()268     uint32_t hashMask() const { return fCapacity - 1; }
269 
firstIndex(const Key & key)270     int firstIndex(const Key& key) const {
271         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.
nextIndex(int index,int round)275     int nextIndex(int index, int round) const {
276         // This will search a power-of-two array fully without repeating an index.
277         return (index + round + 1) & this->hashMask();
278     }
279 
GetKey(const T & t)280     static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
Hash(const Key & key)281     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
290