OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_HASHMAP_H_ | 5 #ifndef V8_HASHMAP_H_ |
6 #define V8_HASHMAP_H_ | 6 #define V8_HASHMAP_H_ |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
9 #include "src/base/logging.h" | 9 #include "src/base/logging.h" |
10 #include "src/utils.h" | 10 #include "src/utils.h" |
(...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
157 // not break the search. If, while searching for the next empty entry, an | 157 // not break the search. If, while searching for the next empty entry, an |
158 // entry is encountered which does not have its initial position between the | 158 // entry is encountered which does not have its initial position between the |
159 // entry to remove and the position looked at, then this entry can be moved to | 159 // entry to remove and the position looked at, then this entry can be moved to |
160 // the place of the entry to remove without breaking the search for it. The | 160 // the place of the entry to remove without breaking the search for it. The |
161 // entry made vacant by this move is now the entry to remove and the process | 161 // entry made vacant by this move is now the entry to remove and the process |
162 // starts over. | 162 // starts over. |
163 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | 163 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. |
164 | 164 |
165 // This guarantees loop termination as there is at least one empty entry so | 165 // This guarantees loop termination as there is at least one empty entry so |
166 // eventually the removed entry will have an empty entry after it. | 166 // eventually the removed entry will have an empty entry after it. |
167 ASSERT(occupancy_ < capacity_); | 167 DCHECK(occupancy_ < capacity_); |
168 | 168 |
169 // p is the candidate entry to clear. q is used to scan forwards. | 169 // p is the candidate entry to clear. q is used to scan forwards. |
170 Entry* q = p; // Start at the entry to remove. | 170 Entry* q = p; // Start at the entry to remove. |
171 while (true) { | 171 while (true) { |
172 // Move q to the next entry. | 172 // Move q to the next entry. |
173 q = q + 1; | 173 q = q + 1; |
174 if (q == map_end()) { | 174 if (q == map_end()) { |
175 q = map_; | 175 q = map_; |
176 } | 176 } |
177 | 177 |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
217 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 217 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
218 TemplateHashMapImpl<AllocationPolicy>::Start() const { | 218 TemplateHashMapImpl<AllocationPolicy>::Start() const { |
219 return Next(map_ - 1); | 219 return Next(map_ - 1); |
220 } | 220 } |
221 | 221 |
222 | 222 |
223 template<class AllocationPolicy> | 223 template<class AllocationPolicy> |
224 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 224 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
225 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { | 225 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { |
226 const Entry* end = map_end(); | 226 const Entry* end = map_end(); |
227 ASSERT(map_ - 1 <= p && p < end); | 227 DCHECK(map_ - 1 <= p && p < end); |
228 for (p++; p < end; p++) { | 228 for (p++; p < end; p++) { |
229 if (p->key != NULL) { | 229 if (p->key != NULL) { |
230 return p; | 230 return p; |
231 } | 231 } |
232 } | 232 } |
233 return NULL; | 233 return NULL; |
234 } | 234 } |
235 | 235 |
236 | 236 |
237 template<class AllocationPolicy> | 237 template<class AllocationPolicy> |
238 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 238 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
239 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { | 239 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) { |
240 ASSERT(key != NULL); | 240 DCHECK(key != NULL); |
241 | 241 |
242 ASSERT(IsPowerOf2(capacity_)); | 242 DCHECK(IsPowerOf2(capacity_)); |
243 Entry* p = map_ + (hash & (capacity_ - 1)); | 243 Entry* p = map_ + (hash & (capacity_ - 1)); |
244 const Entry* end = map_end(); | 244 const Entry* end = map_end(); |
245 ASSERT(map_ <= p && p < end); | 245 DCHECK(map_ <= p && p < end); |
246 | 246 |
247 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. | 247 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
248 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 248 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
249 p++; | 249 p++; |
250 if (p >= end) { | 250 if (p >= end) { |
251 p = map_; | 251 p = map_; |
252 } | 252 } |
253 } | 253 } |
254 | 254 |
255 return p; | 255 return p; |
256 } | 256 } |
257 | 257 |
258 | 258 |
259 template<class AllocationPolicy> | 259 template<class AllocationPolicy> |
260 void TemplateHashMapImpl<AllocationPolicy>::Initialize( | 260 void TemplateHashMapImpl<AllocationPolicy>::Initialize( |
261 uint32_t capacity, AllocationPolicy allocator) { | 261 uint32_t capacity, AllocationPolicy allocator) { |
262 ASSERT(IsPowerOf2(capacity)); | 262 DCHECK(IsPowerOf2(capacity)); |
263 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | 263 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); |
264 if (map_ == NULL) { | 264 if (map_ == NULL) { |
265 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | 265 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); |
266 return; | 266 return; |
267 } | 267 } |
268 capacity_ = capacity; | 268 capacity_ = capacity; |
269 Clear(); | 269 Clear(); |
270 } | 270 } |
271 | 271 |
272 | 272 |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
337 Iterator end() const { return Iterator(this, NULL); } | 337 Iterator end() const { return Iterator(this, NULL); } |
338 Iterator find(Key* key, bool insert = false, | 338 Iterator find(Key* key, bool insert = false, |
339 AllocationPolicy allocator = AllocationPolicy()) { | 339 AllocationPolicy allocator = AllocationPolicy()) { |
340 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); | 340 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); |
341 } | 341 } |
342 }; | 342 }; |
343 | 343 |
344 } } // namespace v8::internal | 344 } } // namespace v8::internal |
345 | 345 |
346 #endif // V8_HASHMAP_H_ | 346 #endif // V8_HASHMAP_H_ |
OLD | NEW |