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