| 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 |