OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2010 Google Inc. | 3 * Copyright 2010 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 | 10 |
11 #ifndef GrTHashTable_DEFINED | 11 #ifndef GrTHashTable_DEFINED |
12 #define GrTHashTable_DEFINED | 12 #define GrTHashTable_DEFINED |
13 | 13 |
14 #include "GrTypes.h" | 14 #include "GrTypes.h" |
15 #include "SkTDArray.h" | 15 #include "SkTDArray.h" |
16 | 16 |
17 // GrTDefaultFindFunctor implements the default find behavior for | |
18 // GrTHashTable (i.e., return the first resource that matches the | |
19 // provided key) | |
20 template <typename T> class GrTDefaultFindFunctor { | |
21 public: | |
22 // always accept the first element examined | |
23 bool operator()(const T*) const { return true; } | |
24 }; | |
25 | |
26 /** | 17 /** |
27 * Key needs | 18 * Key needs |
28 * static bool EQ(const Entry&, const HashKey&); | 19 * static bool EQ(const Entry&, const HashKey&); |
29 * static bool LT(const Entry&, const HashKey&); | 20 * static bool LT(const Entry&, const HashKey&); |
30 * uint32_t getHash() const; | 21 * uint32_t getHash() const; |
31 * | 22 * |
32 * Allows duplicate key entries but on find you may get | 23 * Allows duplicate key entries but on find you may get |
33 * any of the duplicate entries returned. | 24 * any of the duplicate entries returned. |
34 */ | 25 */ |
35 template <typename T, typename Key, size_t kHashBits> class GrTHashTable { | 26 template <typename T, typename Key, size_t kHashBits> class GrTHashTable { |
36 public: | 27 public: |
37 GrTHashTable() { sk_bzero(fHash, sizeof(fHash)); } | 28 GrTHashTable() { this->clearHash(); } |
38 ~GrTHashTable() {} | 29 ~GrTHashTable() {} |
39 | 30 |
40 int count() const { return fSorted.count(); } | 31 int count() const { return fSorted.count(); } |
41 T* find(const Key&) const; | 32 |
42 template <typename FindFuncType> T* find(const Key&, const FindFuncType&) c
onst; | 33 struct Any { |
| 34 // Return the first resource that matches the key. |
| 35 bool operator()(const T*) const { return true; } |
| 36 }; |
| 37 |
| 38 T* find(const Key& key) const { return this->find(key, Any()); } |
| 39 template <typename Filter> T* find(const Key&, Filter filter) const; |
| 40 |
43 // return true if key was unique when inserted. | 41 // return true if key was unique when inserted. |
44 bool insert(const Key&, T*); | 42 bool insert(const Key&, T*); |
45 void remove(const Key&, const T*); | 43 void remove(const Key&, const T*); |
46 T* removeAt(int index, uint32_t hash); | 44 |
47 void removeAll(); | |
48 void deleteAll(); | 45 void deleteAll(); |
49 void unrefAll(); | |
50 | |
51 /** | |
52 * Return the index for the element, using a linear search. | |
53 */ | |
54 int slowFindIndex(T* elem) const { return fSorted.find(elem); } | |
55 | 46 |
56 #ifdef SK_DEBUG | 47 #ifdef SK_DEBUG |
57 void validate() const; | 48 void validate() const; |
58 bool contains(T*) const; | 49 bool contains(T*) const; |
59 #endif | 50 #endif |
60 | 51 |
61 // testing | 52 // testing |
62 const SkTDArray<T*>& getArray() const { return fSorted; } | 53 const SkTDArray<T*>& getArray() const { return fSorted; } |
63 SkTDArray<T*>& getArray() { return fSorted; } | 54 SkTDArray<T*>& getArray() { return fSorted; } |
64 private: | 55 private: |
| 56 void clearHash() { sk_bzero(fHash, sizeof(fHash)); } |
| 57 |
65 enum { | 58 enum { |
66 kHashCount = 1 << kHashBits, | 59 kHashCount = 1 << kHashBits, |
67 kHashMask = kHashCount - 1 | 60 kHashMask = kHashCount - 1 |
68 }; | 61 }; |
69 static unsigned hash2Index(uint32_t hash) { | 62 static unsigned hash2Index(uint32_t hash) { |
70 hash ^= hash >> 16; | 63 hash ^= hash >> 16; |
71 if (kHashBits <= 8) { | 64 if (kHashBits <= 8) { |
72 hash ^= hash >> 8; | 65 hash ^= hash >> 8; |
73 } | 66 } |
74 return hash & kHashMask; | 67 return hash & kHashMask; |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
113 } | 106 } |
114 | 107 |
115 // now return the ~ of where we should insert it | 108 // now return the ~ of where we should insert it |
116 if (Key::LT(*array[high], key)) { | 109 if (Key::LT(*array[high], key)) { |
117 high += 1; | 110 high += 1; |
118 } | 111 } |
119 return ~high; | 112 return ~high; |
120 } | 113 } |
121 | 114 |
122 template <typename T, typename Key, size_t kHashBits> | 115 template <typename T, typename Key, size_t kHashBits> |
123 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const { | 116 template <typename Filter> |
124 GrTDefaultFindFunctor<T> find; | 117 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const { |
125 | |
126 return this->find(key, find); | |
127 } | |
128 | |
129 template <typename T, typename Key, size_t kHashBits> | |
130 template <typename FindFuncType> | |
131 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& fin
dFunc) const { | |
132 | 118 |
133 int hashIndex = hash2Index(key.getHash()); | 119 int hashIndex = hash2Index(key.getHash()); |
134 T* elem = fHash[hashIndex]; | 120 T* elem = fHash[hashIndex]; |
135 | 121 |
136 if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) { | 122 if (NULL != elem && Key::EQ(*elem, key) && filter(elem)) { |
137 return elem; | 123 return elem; |
138 } | 124 } |
139 | 125 |
140 // bsearch for the key in our sorted array | 126 // bsearch for the key in our sorted array |
141 int index = this->searchArray(key); | 127 int index = this->searchArray(key); |
142 if (index < 0) { | 128 if (index < 0) { |
143 return NULL; | 129 return NULL; |
144 } | 130 } |
145 | 131 |
146 const T* const* array = fSorted.begin(); | 132 const T* const* array = fSorted.begin(); |
147 | 133 |
148 // above search should have found the first occurrence if there | 134 // above search should have found the first occurrence if there |
149 // are multiple. | 135 // are multiple. |
150 SkASSERT(0 == index || Key::LT(*array[index - 1], key)); | 136 SkASSERT(0 == index || Key::LT(*array[index - 1], key)); |
151 | 137 |
152 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { | 138 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { |
153 if (findFunc(fSorted[index])) { | 139 if (filter(fSorted[index])) { |
154 // update the hash | 140 // update the hash |
155 fHash[hashIndex] = fSorted[index]; | 141 fHash[hashIndex] = fSorted[index]; |
156 return fSorted[index]; | 142 return fSorted[index]; |
157 } | 143 } |
158 } | 144 } |
159 | 145 |
160 return NULL; | 146 return NULL; |
161 } | 147 } |
162 | 148 |
163 template <typename T, typename Key, size_t kHashBits> | 149 template <typename T, typename Key, size_t kHashBits> |
(...skipping 25 matching lines...) Expand all Loading... |
189 // march forward until we find elem. | 175 // march forward until we find elem. |
190 while (elem != fSorted[index]) { | 176 while (elem != fSorted[index]) { |
191 ++index; | 177 ++index; |
192 SkASSERT(index < fSorted.count()); | 178 SkASSERT(index < fSorted.count()); |
193 } | 179 } |
194 SkASSERT(elem == fSorted[index]); | 180 SkASSERT(elem == fSorted[index]); |
195 fSorted.remove(index); | 181 fSorted.remove(index); |
196 } | 182 } |
197 | 183 |
198 template <typename T, typename Key, size_t kHashBits> | 184 template <typename T, typename Key, size_t kHashBits> |
199 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) { | |
200 int hashIndex = hash2Index(hash); | |
201 if (fHash[hashIndex] == fSorted[elemIndex]) { | |
202 fHash[hashIndex] = NULL; | |
203 } | |
204 // remove from our sorted array | |
205 T* elem = fSorted[elemIndex]; | |
206 fSorted.remove(elemIndex); | |
207 return elem; | |
208 } | |
209 | |
210 template <typename T, typename Key, size_t kHashBits> | |
211 void GrTHashTable<T, Key, kHashBits>::removeAll() { | |
212 fSorted.reset(); | |
213 sk_bzero(fHash, sizeof(fHash)); | |
214 } | |
215 | |
216 template <typename T, typename Key, size_t kHashBits> | |
217 void GrTHashTable<T, Key, kHashBits>::deleteAll() { | 185 void GrTHashTable<T, Key, kHashBits>::deleteAll() { |
218 fSorted.deleteAll(); | 186 fSorted.deleteAll(); |
219 sk_bzero(fHash, sizeof(fHash)); | 187 this->clearHash(); |
220 } | |
221 | |
222 template <typename T, typename Key, size_t kHashBits> | |
223 void GrTHashTable<T, Key, kHashBits>::unrefAll() { | |
224 fSorted.unrefAll(); | |
225 sk_bzero(fHash, sizeof(fHash)); | |
226 } | 188 } |
227 | 189 |
228 #ifdef SK_DEBUG | 190 #ifdef SK_DEBUG |
229 template <typename T, typename Key, size_t kHashBits> | 191 template <typename T, typename Key, size_t kHashBits> |
230 void GrTHashTable<T, Key, kHashBits>::validate() const { | 192 void GrTHashTable<T, Key, kHashBits>::validate() const { |
231 int count = fSorted.count(); | 193 int count = fSorted.count(); |
232 for (int i = 1; i < count; i++) { | 194 for (int i = 1; i < count; i++) { |
233 SkASSERT(Key::LT(*fSorted[i - 1], *fSorted[i]) || | 195 SkASSERT(Key::LT(*fSorted[i - 1], *fSorted[i]) || |
234 Key::EQ(*fSorted[i - 1], *fSorted[i])); | 196 Key::EQ(*fSorted[i - 1], *fSorted[i])); |
235 } | 197 } |
236 } | 198 } |
237 | 199 |
238 template <typename T, typename Key, size_t kHashBits> | 200 template <typename T, typename Key, size_t kHashBits> |
239 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { | 201 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { |
240 int index = fSorted.find(elem); | 202 int index = fSorted.find(elem); |
241 return index >= 0; | 203 return index >= 0; |
242 } | 204 } |
243 | 205 |
244 #endif | 206 #endif |
245 | 207 |
246 #endif | 208 #endif |
OLD | NEW |