| 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 |
| (...skipping 143 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 154 SkASSERT(fCapacity == 0); | 154 SkASSERT(fCapacity == 0); |
| 155 return 0; | 155 return 0; |
| 156 } | 156 } |
| 157 | 157 |
| 158 private: | 158 private: |
| 159 // We have two special values to indicate an empty or deleted entry. | 159 // We have two special values to indicate an empty or deleted entry. |
| 160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL | 160 static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL |
| 161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. | 161 static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid
pointer. |
| 162 | 162 |
| 163 bool validate() const { | 163 bool validate() const { |
| 164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false | 164 #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false |
| 165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience
. | 165 static const int kLarge = 50; // Arbitrary, tweak to suit your patience
. |
| 166 | 166 |
| 167 // O(1) checks, always done. | 167 // O(1) checks, always done. |
| 168 // Is capacity sane? | 168 // Is capacity sane? |
| 169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); | 169 SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); |
| 170 | 170 |
| 171 // O(N) checks, skipped when very large. | 171 // O(N) checks, skipped when very large. |
| 172 if (fCount < kLarge * kLarge) { | 172 if (fCount < kLarge * kLarge) { |
| 173 // Are fCount and fDeleted correct, and are all elements findable? | 173 // Are fCount and fDeleted correct, and are all elements findable? |
| 174 int count = 0, deleted = 0; | 174 int count = 0, deleted = 0; |
| (...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } | 280 static const Key& GetKey(const T& t) { return Traits::GetKey(t); } |
| 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } | 281 static uint32_t Hash(const Key& key) { return Traits::Hash(key); } |
| 282 | 282 |
| 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. | 283 int fCount; // Number of non Empty(), non Deleted() entries in fArray. |
| 284 int fDeleted; // Number of Deleted() entries in fArray. | 284 int fDeleted; // Number of Deleted() entries in fArray. |
| 285 int fCapacity; // Number of entries in fArray. Always a power of 2. | 285 int fCapacity; // Number of entries in fArray. Always a power of 2. |
| 286 T** fArray; | 286 T** fArray; |
| 287 }; | 287 }; |
| 288 | 288 |
| 289 #endif | 289 #endif |
| OLD | NEW |