| 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 // Traits requires: |
| 16 // static const Key& GetKey(const T&) { ... } |
| 17 // static uint32_t Hash(const Key&) { ... } |
| 18 // We'll look on T for these by default, or you can pass a custom Traits type. |
| 15 template <typename T, | 19 template <typename T, |
| 16 typename Key, | 20 typename Key, |
| 17 const Key& (GetKey)(const T&), | 21 typename Traits = T, |
| 18 uint32_t (Hash)(const Key&), | |
| 19 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. | 22 int kGrowPercent = 75> // Larger -> more memory efficient, but slower
. |
| 20 class SkTDynamicHash { | 23 class SkTDynamicHash { |
| 21 public: | 24 public: |
| 22 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { | 25 SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) { |
| 23 SkASSERT(this->validate()); | 26 SkASSERT(this->validate()); |
| 24 } | 27 } |
| 25 | 28 |
| 26 ~SkTDynamicHash() { | 29 ~SkTDynamicHash() { |
| 27 sk_free(fArray); | 30 sk_free(fArray); |
| 28 } | 31 } |
| (...skipping 191 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 220 int firstIndex(const Key& key) const { | 223 int firstIndex(const Key& key) const { |
| 221 return Hash(key) & this->hashMask(); | 224 return Hash(key) & this->hashMask(); |
| 222 } | 225 } |
| 223 | 226 |
| 224 // Given index at round N, what is the index to check at N+1? round should
start at 0. | 227 // Given index at round N, what is the index to check at N+1? round should
start at 0. |
| 225 int nextIndex(int index, int round) const { | 228 int nextIndex(int index, int round) const { |
| 226 // This will search a power-of-two array fully without repeating an inde
x. | 229 // This will search a power-of-two array fully without repeating an inde
x. |
| 227 return (index + round + 1) & this->hashMask(); | 230 return (index + round + 1) & this->hashMask(); |
| 228 } | 231 } |
| 229 | 232 |
| 233 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } |
| 234 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } |
| 235 |
| 230 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 236 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 231 int fDeleted; // Number of Deleted() entries in fArray. | 237 int fDeleted; // Number of Deleted() entries in fArray. |
| 232 int fCapacity; // Number of entries in fArray. Always a power of 2. | 238 int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 233 T** fArray; | 239 T** fArray; |
| 234 }; | 240 }; |
| 235 | 241 |
| 236 #endif | 242 #endif |
| OLD | NEW |