OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
52 AllocationPolicy allocator = AllocationPolicy()); | 52 AllocationPolicy allocator = AllocationPolicy()); |
53 | 53 |
54 ~TemplateHashMapImpl(); | 54 ~TemplateHashMapImpl(); |
55 | 55 |
56 // HashMap entries are (key, value, hash) triplets. | 56 // HashMap entries are (key, value, hash) triplets. |
57 // Some clients may not need to use the value slot | 57 // Some clients may not need to use the value slot |
58 // (e.g. implementers of sets, where the key is the value). | 58 // (e.g. implementers of sets, where the key is the value). |
59 struct Entry { | 59 struct Entry { |
60 void* key; | 60 void* key; |
61 void* value; | 61 void* value; |
62 uint32_t hash; // the full hash value for key | 62 uint32_t hash; // The full hash value for key |
| 63 int order; // If you never remove entries this is the insertion order. |
63 }; | 64 }; |
64 | 65 |
65 // If an entry with matching key is found, Lookup() | 66 // If an entry with matching key is found, Lookup() |
66 // returns that entry. If no matching entry is found, | 67 // returns that entry. If no matching entry is found, |
67 // but insert is set, a new entry is inserted with | 68 // but insert is set, a new entry is inserted with |
68 // corresponding key, key hash, and NULL value. | 69 // corresponding key, key hash, and NULL value. |
69 // Otherwise, NULL is returned. | 70 // Otherwise, NULL is returned. |
70 Entry* Lookup(void* key, uint32_t hash, bool insert, | 71 Entry* Lookup(void* key, uint32_t hash, bool insert, |
71 AllocationPolicy allocator = AllocationPolicy()); | 72 AllocationPolicy allocator = AllocationPolicy()); |
72 | 73 |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
133 Entry* p = Probe(key, hash); | 134 Entry* p = Probe(key, hash); |
134 if (p->key != NULL) { | 135 if (p->key != NULL) { |
135 return p; | 136 return p; |
136 } | 137 } |
137 | 138 |
138 // No entry found; insert one if necessary. | 139 // No entry found; insert one if necessary. |
139 if (insert) { | 140 if (insert) { |
140 p->key = key; | 141 p->key = key; |
141 p->value = NULL; | 142 p->value = NULL; |
142 p->hash = hash; | 143 p->hash = hash; |
| 144 p->order = occupancy_; |
143 occupancy_++; | 145 occupancy_++; |
144 | 146 |
145 // Grow the map if we reached >= 80% occupancy. | 147 // Grow the map if we reached >= 80% occupancy. |
146 if (occupancy_ + occupancy_/4 >= capacity_) { | 148 if (occupancy_ + occupancy_/4 >= capacity_) { |
147 Resize(allocator); | 149 Resize(allocator); |
148 p = Probe(key, hash); | 150 p = Probe(key, hash); |
149 } | 151 } |
150 | 152 |
151 return p; | 153 return p; |
152 } | 154 } |
(...skipping 137 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
290 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { | 292 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { |
291 Entry* map = map_; | 293 Entry* map = map_; |
292 uint32_t n = occupancy_; | 294 uint32_t n = occupancy_; |
293 | 295 |
294 // Allocate larger map. | 296 // Allocate larger map. |
295 Initialize(capacity_ * 2, allocator); | 297 Initialize(capacity_ * 2, allocator); |
296 | 298 |
297 // Rehash all current entries. | 299 // Rehash all current entries. |
298 for (Entry* p = map; n > 0; p++) { | 300 for (Entry* p = map; n > 0; p++) { |
299 if (p->key != NULL) { | 301 if (p->key != NULL) { |
300 Lookup(p->key, p->hash, true, allocator)->value = p->value; | 302 Entry* entry = Lookup(p->key, p->hash, true, allocator); |
| 303 entry->value = p->value; |
| 304 entry->order = p->order; |
301 n--; | 305 n--; |
302 } | 306 } |
303 } | 307 } |
304 | 308 |
305 // Delete old map. | 309 // Delete old map. |
306 AllocationPolicy::Delete(map); | 310 AllocationPolicy::Delete(map); |
307 } | 311 } |
308 | 312 |
309 | 313 |
310 // A hash map for pointer keys and values with an STL-like interface. | 314 // A hash map for pointer keys and values with an STL-like interface. |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
351 Iterator end() const { return Iterator(this, NULL); } | 355 Iterator end() const { return Iterator(this, NULL); } |
352 Iterator find(Key* key, bool insert = false, | 356 Iterator find(Key* key, bool insert = false, |
353 AllocationPolicy allocator = AllocationPolicy()) { | 357 AllocationPolicy allocator = AllocationPolicy()) { |
354 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); | 358 return Iterator(this, this->Lookup(key, key->Hash(), insert, allocator)); |
355 } | 359 } |
356 }; | 360 }; |
357 | 361 |
358 } } // namespace v8::internal | 362 } } // namespace v8::internal |
359 | 363 |
360 #endif // V8_HASHMAP_H_ | 364 #endif // V8_HASHMAP_H_ |
OLD | NEW |