1
2 /*
3 * Copyright 2010 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10
11 #ifndef GrTHashCache_DEFINED
12 #define GrTHashCache_DEFINED
13
14 #include "GrTypes.h"
15 #include "SkTDArray.h"
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
operator()23 bool operator()(const T* elem) const { return true; }
24 };
25
26 /**
27 * Key needs
28 * static bool EQ(const Entry&, const HashKey&);
29 * static bool LT(const Entry&, const HashKey&);
30 * uint32_t getHash() const;
31 *
32 * Allows duplicate key entries but on find you may get
33 * any of the duplicate entries returned.
34 */
35 template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
36 public:
GrTHashTable()37 GrTHashTable() { Gr_bzero(fHash, sizeof(fHash)); }
~GrTHashTable()38 ~GrTHashTable() {}
39
count()40 int count() const { return fSorted.count(); }
41 T* find(const Key&) const;
42 template <typename FindFuncType> T* find(const Key&, const FindFuncType&) const;
43 // return true if key was unique when inserted.
44 bool insert(const Key&, T*);
45 void remove(const Key&, const T*);
46 T* removeAt(int index, uint32_t hash);
47 void removeAll();
48 void deleteAll();
49 void unrefAll();
50
51 /**
52 * Return the index for the element, using a linear search.
53 */
slowFindIndex(T * elem)54 int slowFindIndex(T* elem) const { return fSorted.find(elem); }
55
56 #if GR_DEBUG
57 void validate() const;
58 bool contains(T*) const;
59 #endif
60
61 // testing
getArray()62 const SkTDArray<T*>& getArray() const { return fSorted; }
63 private:
64 enum {
65 kHashCount = 1 << kHashBits,
66 kHashMask = kHashCount - 1
67 };
hash2Index(uint32_t hash)68 static unsigned hash2Index(uint32_t hash) {
69 hash ^= hash >> 16;
70 if (kHashBits <= 8) {
71 hash ^= hash >> 8;
72 }
73 return hash & kHashMask;
74 }
75
76 mutable T* fHash[kHashCount];
77 SkTDArray<T*> fSorted;
78
79 // search fSorted, and return the found index, or ~index of where it
80 // should be inserted
81 int searchArray(const Key&) const;
82 };
83
84 ///////////////////////////////////////////////////////////////////////////////
85
86 template <typename T, typename Key, size_t kHashBits>
searchArray(const Key & key)87 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
88 int count = fSorted.count();
89 if (0 == count) {
90 // we should insert it at 0
91 return ~0;
92 }
93
94 const T* const* array = fSorted.begin();
95 int high = count - 1;
96 int low = 0;
97 while (high > low) {
98 int index = (low + high) >> 1;
99 if (Key::LT(*array[index], key)) {
100 low = index + 1;
101 } else {
102 high = index;
103 }
104 }
105
106 // check if we found it
107 if (Key::EQ(*array[high], key)) {
108 // above search should have found the first occurrence if there
109 // are multiple.
110 GrAssert(0 == high || Key::LT(*array[high - 1], key));
111 return high;
112 }
113
114 // now return the ~ of where we should insert it
115 if (Key::LT(*array[high], key)) {
116 high += 1;
117 }
118 return ~high;
119 }
120
121 template <typename T, typename Key, size_t kHashBits>
find(const Key & key)122 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const {
123 GrTDefaultFindFunctor<T> find;
124
125 return this->find(key, find);
126 }
127
128 template <typename T, typename Key, size_t kHashBits>
129 template <typename FindFuncType>
find(const Key & key,const FindFuncType & findFunc)130 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const {
131
132 int hashIndex = hash2Index(key.getHash());
133 T* elem = fHash[hashIndex];
134
135 if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) {
136 return elem;
137 }
138
139 // bsearch for the key in our sorted array
140 int index = this->searchArray(key);
141 if (index < 0) {
142 return NULL;
143 }
144
145 const T* const* array = fSorted.begin();
146
147 // above search should have found the first occurrence if there
148 // are multiple.
149 GrAssert(0 == index || Key::LT(*array[index - 1], key));
150
151 for ( ; index < count() && Key::EQ(*array[index], key); ++index) {
152 if (findFunc(fSorted[index])) {
153 // update the hash
154 fHash[hashIndex] = fSorted[index];
155 return fSorted[index];
156 }
157 }
158
159 return NULL;
160 }
161
162 template <typename T, typename Key, size_t kHashBits>
insert(const Key & key,T * elem)163 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
164 int index = this->searchArray(key);
165 bool first = index < 0;
166 if (first) {
167 // turn it into the actual index
168 index = ~index;
169 }
170 // add it to our array
171 *fSorted.insert(index) = elem;
172 // update our hash table (overwrites any dupe's position in the hash)
173 fHash[hash2Index(key.getHash())] = elem;
174 return first;
175 }
176
177 template <typename T, typename Key, size_t kHashBits>
remove(const Key & key,const T * elem)178 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
179 int index = hash2Index(key.getHash());
180 if (fHash[index] == elem) {
181 fHash[index] = NULL;
182 }
183
184 // remove from our sorted array
185 index = this->searchArray(key);
186 GrAssert(index >= 0);
187 // if there are multiple matches searchArray will give us the first match
188 // march forward until we find elem.
189 while (elem != fSorted[index]) {
190 ++index;
191 GrAssert(index < fSorted.count());
192 }
193 GrAssert(elem == fSorted[index]);
194 fSorted.remove(index);
195 }
196
197 template <typename T, typename Key, size_t kHashBits>
removeAt(int elemIndex,uint32_t hash)198 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) {
199 int hashIndex = hash2Index(hash);
200 if (fHash[hashIndex] == fSorted[elemIndex]) {
201 fHash[hashIndex] = NULL;
202 }
203 // remove from our sorted array
204 T* elem = fSorted[elemIndex];
205 fSorted.remove(elemIndex);
206 return elem;
207 }
208
209 template <typename T, typename Key, size_t kHashBits>
removeAll()210 void GrTHashTable<T, Key, kHashBits>::removeAll() {
211 fSorted.reset();
212 Gr_bzero(fHash, sizeof(fHash));
213 }
214
215 template <typename T, typename Key, size_t kHashBits>
deleteAll()216 void GrTHashTable<T, Key, kHashBits>::deleteAll() {
217 fSorted.deleteAll();
218 Gr_bzero(fHash, sizeof(fHash));
219 }
220
221 template <typename T, typename Key, size_t kHashBits>
unrefAll()222 void GrTHashTable<T, Key, kHashBits>::unrefAll() {
223 fSorted.unrefAll();
224 Gr_bzero(fHash, sizeof(fHash));
225 }
226
227 #if GR_DEBUG
228 template <typename T, typename Key, size_t kHashBits>
validate()229 void GrTHashTable<T, Key, kHashBits>::validate() const {
230 int count = fSorted.count();
231 for (int i = 1; i < count; i++) {
232 GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) ||
233 Key::EQ(*fSorted[i - 1], *fSorted[i]));
234 }
235 }
236
237 template <typename T, typename Key, size_t kHashBits>
contains(T * elem)238 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
239 int index = fSorted.find(elem);
240 return index >= 0;
241 }
242
243 #endif
244
245 #endif
246