| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #ifndef SkTDynamicHash_DEFINED | 8 #ifndef SkTDynamicHash_DEFINED |
| 9 #define SkTDynamicHash_DEFINED | 9 #define SkTDynamicHash_DEFINED |
| 10 | 10 |
| 11 #include "SkMath.h" | 11 #include "SkMath.h" |
| 12 #include "SkTemplates.h" | 12 #include "SkTemplates.h" |
| 13 #include "SkTypes.h" | 13 #include "SkTypes.h" |
| 14 | 14 |
| 15 template <typename T, | 15 template <typename T, |
| 16 typename Key, | 16 typename Key, |
| 17 const Key& (GetKey)(const T&), | 17 const Key& (GetKey)(const T&), |
| 18 uint32_t (Hash)(const Key&), | 18 uint32_t (Hash)(const Key&), |
| 19 bool (Equal)(const T&, const Key&), | |
| 20 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. | 19 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. |
| 21 class SkTDynamicHash { | 20 class SkTDynamicHash { |
| 22 public: | 21 public: |
| 23 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { | 22 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { |
| 24 SkASSERT(this->validate()); | 23 SkASSERT(this->validate()); |
| 25 } | 24 } |
| 26 | 25 |
| 27 ~SkTDynamicHash() { | 26 ~SkTDynamicHash() { |
| 28 sk_free(fArray); | 27 sk_free(fArray); |
| 29 } | 28 } |
| (...skipping 28 matching lines...) Expand all Loading... |
| 58 int count() const { return fCount; } | 57 int count() const { return fCount; } |
| 59 | 58 |
| 60 // Return the entry with this key if we have it, otherwise NULL. | 59 // Return the entry with this key if we have it, otherwise NULL. |
| 61 T* find(const Key& key) const { | 60 T* find(const Key& key) const { |
| 62 int index = this->firstIndex(key); | 61 int index = this->firstIndex(key); |
| 63 for (int round = 0; round < fCapacity; round++) { | 62 for (int round = 0; round < fCapacity; round++) { |
| 64 T* candidate = fArray[index]; | 63 T* candidate = fArray[index]; |
| 65 if (Empty() == candidate) { | 64 if (Empty() == candidate) { |
| 66 return NULL; | 65 return NULL; |
| 67 } | 66 } |
| 68 if (Deleted() != candidate && Equal(*candidate, key)) { | 67 if (Deleted() != candidate && GetKey(*candidate) == key) { |
| 69 return candidate; | 68 return candidate; |
| 70 } | 69 } |
| 71 index = this->nextIndex(index, round); | 70 index = this->nextIndex(index, round); |
| 72 } | 71 } |
| 73 SkASSERT(fCapacity == 0); | 72 SkASSERT(fCapacity == 0); |
| 74 return NULL; | 73 return NULL; |
| 75 } | 74 } |
| 76 | 75 |
| 77 // Add an entry with this key. We require that no entry with newEntry's key
is already present. | 76 // Add an entry with this key. We require that no entry with newEntry's key
is already present. |
| 78 void add(T* newEntry) { | 77 void add(T* newEntry) { |
| (...skipping 13 matching lines...) Expand all Loading... |
| 92 protected: | 91 protected: |
| 93 // These methods are used by tests only. | 92 // These methods are used by tests only. |
| 94 | 93 |
| 95 int capacity() const { return fCapacity; } | 94 int capacity() const { return fCapacity; } |
| 96 | 95 |
| 97 // How many collisions do we go through before finding where this entry shou
ld be inserted? | 96 // How many collisions do we go through before finding where this entry shou
ld be inserted? |
| 98 int countCollisions(const Key& key) const { | 97 int countCollisions(const Key& key) const { |
| 99 int index = this->firstIndex(key); | 98 int index = this->firstIndex(key); |
| 100 for (int round = 0; round < fCapacity; round++) { | 99 for (int round = 0; round < fCapacity; round++) { |
| 101 const T* candidate = fArray[index]; | 100 const T* candidate = fArray[index]; |
| 102 if (Empty() == candidate || Deleted() == candidate || Equal(*candida
te, key)) { | 101 if (Empty() == candidate || Deleted() == candidate || GetKey(*candid
ate) == key) { |
| 103 return round; | 102 return round; |
| 104 } | 103 } |
| 105 index = this->nextIndex(index, round); | 104 index = this->nextIndex(index, round); |
| 106 } | 105 } |
| 107 SkASSERT(fCapacity == 0); | 106 SkASSERT(fCapacity == 0); |
| 108 return 0; | 107 return 0; |
| 109 } | 108 } |
| 110 | 109 |
| 111 private: | 110 private: |
| 112 // We have two special values to indicate an empty or deleted entry. | 111 // We have two special values to indicate an empty or deleted entry. |
| (...skipping 29 matching lines...) Expand all Loading... |
| 142 // Are all entries unique? | 141 // Are all entries unique? |
| 143 for (int i = 0; i < fCapacity; i++) { | 142 for (int i = 0; i < fCapacity; i++) { |
| 144 if (Empty() == fArray[i] || Deleted() == fArray[i]) { | 143 if (Empty() == fArray[i] || Deleted() == fArray[i]) { |
| 145 continue; | 144 continue; |
| 146 } | 145 } |
| 147 for (int j = i+1; j < fCapacity; j++) { | 146 for (int j = i+1; j < fCapacity; j++) { |
| 148 if (Empty() == fArray[j] || Deleted() == fArray[j]) { | 147 if (Empty() == fArray[j] || Deleted() == fArray[j]) { |
| 149 continue; | 148 continue; |
| 150 } | 149 } |
| 151 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); | 150 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); |
| 152 SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])))
; | 151 SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[
j]))); |
| 153 SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])))
; | |
| 154 } | 152 } |
| 155 } | 153 } |
| 156 } | 154 } |
| 157 #undef SKTDYNAMICHASH_CHECK | 155 #undef SKTDYNAMICHASH_CHECK |
| 158 return true; | 156 return true; |
| 159 } | 157 } |
| 160 | 158 |
| 161 void innerAdd(T* newEntry) { | 159 void innerAdd(T* newEntry) { |
| 162 const Key& key = GetKey(*newEntry); | 160 const Key& key = GetKey(*newEntry); |
| 163 int index = this->firstIndex(key); | 161 int index = this->firstIndex(key); |
| (...skipping 10 matching lines...) Expand all Loading... |
| 174 index = this->nextIndex(index, round); | 172 index = this->nextIndex(index, round); |
| 175 } | 173 } |
| 176 SkASSERT(fCapacity == 0); | 174 SkASSERT(fCapacity == 0); |
| 177 } | 175 } |
| 178 | 176 |
| 179 void innerRemove(const Key& key) { | 177 void innerRemove(const Key& key) { |
| 180 const int firstIndex = this->firstIndex(key); | 178 const int firstIndex = this->firstIndex(key); |
| 181 int index = firstIndex; | 179 int index = firstIndex; |
| 182 for (int round = 0; round < fCapacity; round++) { | 180 for (int round = 0; round < fCapacity; round++) { |
| 183 const T* candidate = fArray[index]; | 181 const T* candidate = fArray[index]; |
| 184 if (Deleted() != candidate && Equal(*candidate, key)) { | 182 if (Deleted() != candidate && GetKey(*candidate) == key) { |
| 185 fDeleted++; | 183 fDeleted++; |
| 186 fCount--; | 184 fCount--; |
| 187 fArray[index] = Deleted(); | 185 fArray[index] = Deleted(); |
| 188 return; | 186 return; |
| 189 } | 187 } |
| 190 index = this->nextIndex(index, round); | 188 index = this->nextIndex(index, round); |
| 191 } | 189 } |
| 192 SkASSERT(fCapacity == 0); | 190 SkASSERT(fCapacity == 0); |
| 193 } | 191 } |
| 194 | 192 |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 229 return (index + round + 1) & this->hashMask(); | 227 return (index + round + 1) & this->hashMask(); |
| 230 } | 228 } |
| 231 | 229 |
| 232 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 230 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 233 int fDeleted; // Number of Deleted() entries in fArray. | 231 int fDeleted; // Number of Deleted() entries in fArray. |
| 234 int fCapacity; // Number of entries in fArray. Always a power of 2. | 232 int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 235 T** fArray; | 233 T** fArray; |
| 236 }; | 234 }; |
| 237 | 235 |
| 238 #endif | 236 #endif |
| OLD | NEW |