| 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 |