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 |