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 |
(...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
101 low = index + 1; | 101 low = index + 1; |
102 } else { | 102 } else { |
103 high = index; | 103 high = index; |
104 } | 104 } |
105 } | 105 } |
106 | 106 |
107 // check if we found it | 107 // check if we found it |
108 if (Key::EQ(*array[high], key)) { | 108 if (Key::EQ(*array[high], key)) { |
109 // above search should have found the first occurrence if there | 109 // above search should have found the first occurrence if there |
110 // are multiple. | 110 // are multiple. |
111 GrAssert(0 == high || Key::LT(*array[high - 1], key)); | 111 SkASSERT(0 == high || Key::LT(*array[high - 1], key)); |
112 return high; | 112 return high; |
113 } | 113 } |
114 | 114 |
115 // now return the ~ of where we should insert it | 115 // now return the ~ of where we should insert it |
116 if (Key::LT(*array[high], key)) { | 116 if (Key::LT(*array[high], key)) { |
117 high += 1; | 117 high += 1; |
118 } | 118 } |
119 return ~high; | 119 return ~high; |
120 } | 120 } |
121 | 121 |
(...skipping 18 matching lines...) Expand all Loading... |
140 // bsearch for the key in our sorted array | 140 // bsearch for the key in our sorted array |
141 int index = this->searchArray(key); | 141 int index = this->searchArray(key); |
142 if (index < 0) { | 142 if (index < 0) { |
143 return NULL; | 143 return NULL; |
144 } | 144 } |
145 | 145 |
146 const T* const* array = fSorted.begin(); | 146 const T* const* array = fSorted.begin(); |
147 | 147 |
148 // above search should have found the first occurrence if there | 148 // above search should have found the first occurrence if there |
149 // are multiple. | 149 // are multiple. |
150 GrAssert(0 == index || Key::LT(*array[index - 1], key)); | 150 SkASSERT(0 == index || Key::LT(*array[index - 1], key)); |
151 | 151 |
152 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { | 152 for ( ; index < count() && Key::EQ(*array[index], key); ++index) { |
153 if (findFunc(fSorted[index])) { | 153 if (findFunc(fSorted[index])) { |
154 // update the hash | 154 // update the hash |
155 fHash[hashIndex] = fSorted[index]; | 155 fHash[hashIndex] = fSorted[index]; |
156 return fSorted[index]; | 156 return fSorted[index]; |
157 } | 157 } |
158 } | 158 } |
159 | 159 |
160 return NULL; | 160 return NULL; |
(...skipping 16 matching lines...) Expand all Loading... |
177 | 177 |
178 template <typename T, typename Key, size_t kHashBits> | 178 template <typename T, typename Key, size_t kHashBits> |
179 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) { | 179 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) { |
180 int index = hash2Index(key.getHash()); | 180 int index = hash2Index(key.getHash()); |
181 if (fHash[index] == elem) { | 181 if (fHash[index] == elem) { |
182 fHash[index] = NULL; | 182 fHash[index] = NULL; |
183 } | 183 } |
184 | 184 |
185 // remove from our sorted array | 185 // remove from our sorted array |
186 index = this->searchArray(key); | 186 index = this->searchArray(key); |
187 GrAssert(index >= 0); | 187 SkASSERT(index >= 0); |
188 // if there are multiple matches searchArray will give us the first match | 188 // if there are multiple matches searchArray will give us the first match |
189 // march forward until we find elem. | 189 // march forward until we find elem. |
190 while (elem != fSorted[index]) { | 190 while (elem != fSorted[index]) { |
191 ++index; | 191 ++index; |
192 GrAssert(index < fSorted.count()); | 192 SkASSERT(index < fSorted.count()); |
193 } | 193 } |
194 GrAssert(elem == fSorted[index]); | 194 SkASSERT(elem == fSorted[index]); |
195 fSorted.remove(index); | 195 fSorted.remove(index); |
196 } | 196 } |
197 | 197 |
198 template <typename T, typename Key, size_t kHashBits> | 198 template <typename T, typename Key, size_t kHashBits> |
199 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) { | 199 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) { |
200 int hashIndex = hash2Index(hash); | 200 int hashIndex = hash2Index(hash); |
201 if (fHash[hashIndex] == fSorted[elemIndex]) { | 201 if (fHash[hashIndex] == fSorted[elemIndex]) { |
202 fHash[hashIndex] = NULL; | 202 fHash[hashIndex] = NULL; |
203 } | 203 } |
204 // remove from our sorted array | 204 // remove from our sorted array |
(...skipping 18 matching lines...) Expand all Loading... |
223 void GrTHashTable<T, Key, kHashBits>::unrefAll() { | 223 void GrTHashTable<T, Key, kHashBits>::unrefAll() { |
224 fSorted.unrefAll(); | 224 fSorted.unrefAll(); |
225 Gr_bzero(fHash, sizeof(fHash)); | 225 Gr_bzero(fHash, sizeof(fHash)); |
226 } | 226 } |
227 | 227 |
228 #if GR_DEBUG | 228 #if GR_DEBUG |
229 template <typename T, typename Key, size_t kHashBits> | 229 template <typename T, typename Key, size_t kHashBits> |
230 void GrTHashTable<T, Key, kHashBits>::validate() const { | 230 void GrTHashTable<T, Key, kHashBits>::validate() const { |
231 int count = fSorted.count(); | 231 int count = fSorted.count(); |
232 for (int i = 1; i < count; i++) { | 232 for (int i = 1; i < count; i++) { |
233 GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) || | 233 SkASSERT(Key::LT(*fSorted[i - 1], *fSorted[i]) || |
234 Key::EQ(*fSorted[i - 1], *fSorted[i])); | 234 Key::EQ(*fSorted[i - 1], *fSorted[i])); |
235 } | 235 } |
236 } | 236 } |
237 | 237 |
238 template <typename T, typename Key, size_t kHashBits> | 238 template <typename T, typename Key, size_t kHashBits> |
239 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { | 239 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const { |
240 int index = fSorted.find(elem); | 240 int index = fSorted.find(elem); |
241 return index >= 0; | 241 return index >= 0; |
242 } | 242 } |
243 | 243 |
244 #endif | 244 #endif |
245 | 245 |
246 #endif | 246 #endif |
OLD | NEW |