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 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
107 // Add an entry with this key. We require that no entry with newEntry's key
is already present. | 107 // Add an entry with this key. We require that no entry with newEntry's key
is already present. |
108 void add(T* newEntry) { | 108 void add(T* newEntry) { |
109 SkASSERT(NULL == this->find(GetKey(*newEntry))); | 109 SkASSERT(NULL == this->find(GetKey(*newEntry))); |
110 this->maybeGrow(); | 110 this->maybeGrow(); |
111 this->innerAdd(newEntry); | 111 this->innerAdd(newEntry); |
112 SkASSERT(this->validate()); | 112 SkASSERT(this->validate()); |
113 } | 113 } |
114 | 114 |
115 // Remove the entry with this key. We require that an entry with this key i
s present. | 115 // Remove the entry with this key. We require that an entry with this key i
s present. |
116 void remove(const Key& key) { | 116 void remove(const Key& key) { |
117 SkASSERT(NULL != this->find(key)); | 117 SkASSERT(this->find(key)); |
118 this->innerRemove(key); | 118 this->innerRemove(key); |
119 SkASSERT(this->validate()); | 119 SkASSERT(this->validate()); |
120 } | 120 } |
121 | 121 |
122 void rewind() { | 122 void rewind() { |
123 if (NULL != fArray) { | 123 if (fArray) { |
124 sk_bzero(fArray, sizeof(T*)* fCapacity); | 124 sk_bzero(fArray, sizeof(T*)* fCapacity); |
125 } | 125 } |
126 fCount = 0; | 126 fCount = 0; |
127 fDeleted = 0; | 127 fDeleted = 0; |
128 } | 128 } |
129 | 129 |
130 void reset() { | 130 void reset() { |
131 fCount = 0; | 131 fCount = 0; |
132 fDeleted = 0; | 132 fDeleted = 0; |
133 fCapacity = 0; | 133 fCapacity = 0; |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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; |
175 for (int i = 0; i < fCapacity; i++) { | 175 for (int i = 0; i < fCapacity; i++) { |
176 if (Deleted() == fArray[i]) { | 176 if (Deleted() == fArray[i]) { |
177 deleted++; | 177 deleted++; |
178 } else if (Empty() != fArray[i]) { | 178 } else if (Empty() != fArray[i]) { |
179 count++; | 179 count++; |
180 SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])))
; | 180 SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i]))); |
181 } | 181 } |
182 } | 182 } |
183 SKTDYNAMICHASH_CHECK(count == fCount); | 183 SKTDYNAMICHASH_CHECK(count == fCount); |
184 SKTDYNAMICHASH_CHECK(deleted == fDeleted); | 184 SKTDYNAMICHASH_CHECK(deleted == fDeleted); |
185 } | 185 } |
186 | 186 |
187 // O(N^2) checks, skipped when large. | 187 // O(N^2) checks, skipped when large. |
188 if (fCount < kLarge) { | 188 if (fCount < kLarge) { |
189 // Are all entries unique? | 189 // Are all entries unique? |
190 for (int i = 0; i < fCapacity; i++) { | 190 for (int i = 0; i < fCapacity; i++) { |
(...skipping 89 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 |