| 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/bits.h" | 9 #include "src/base/bits.h" |
| 10 #include "src/base/logging.h" | 10 #include "src/base/logging.h" |
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 44 // If an entry with matching key is found, returns that entry. | 44 // If an entry with matching key is found, returns that entry. |
| 45 // Otherwise, NULL is returned. | 45 // Otherwise, NULL is returned. |
| 46 Entry* Lookup(void* key, uint32_t hash) const; | 46 Entry* Lookup(void* key, uint32_t hash) const; |
| 47 | 47 |
| 48 // If an entry with matching key is found, returns that entry. | 48 // If an entry with matching key is found, returns that entry. |
| 49 // If no matching entry is found, a new entry is inserted with | 49 // If no matching entry is found, a new entry is inserted with |
| 50 // corresponding key, key hash, and NULL value. | 50 // corresponding key, key hash, and NULL value. |
| 51 Entry* LookupOrInsert(void* key, uint32_t hash, | 51 Entry* LookupOrInsert(void* key, uint32_t hash, |
| 52 AllocationPolicy allocator = AllocationPolicy()); | 52 AllocationPolicy allocator = AllocationPolicy()); |
| 53 | 53 |
| 54 Entry* InsertNew(void* key, uint32_t hash, | |
| 55 AllocationPolicy allocator = AllocationPolicy()); | |
| 56 | |
| 57 // Removes the entry with matching key. | 54 // Removes the entry with matching key. |
| 58 // It returns the value of the deleted entry | 55 // It returns the value of the deleted entry |
| 59 // or null if there is no value for such key. | 56 // or null if there is no value for such key. |
| 60 void* Remove(void* key, uint32_t hash); | 57 void* Remove(void* key, uint32_t hash); |
| 61 | 58 |
| 62 // Empties the hash map (occupancy() == 0). | 59 // Empties the hash map (occupancy() == 0). |
| 63 void Clear(); | 60 void Clear(); |
| 64 | 61 |
| 65 // The number of (non-empty) entries in the table. | 62 // The number of (non-empty) entries in the table. |
| 66 uint32_t occupancy() const { return occupancy_; } | 63 uint32_t occupancy() const { return occupancy_; } |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 125 template <class AllocationPolicy> | 122 template <class AllocationPolicy> |
| 126 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 123 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
| 127 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | 124 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( |
| 128 void* key, uint32_t hash, AllocationPolicy allocator) { | 125 void* key, uint32_t hash, AllocationPolicy allocator) { |
| 129 // Find a matching entry. | 126 // Find a matching entry. |
| 130 Entry* p = Probe(key, hash); | 127 Entry* p = Probe(key, hash); |
| 131 if (p->key != NULL) { | 128 if (p->key != NULL) { |
| 132 return p; | 129 return p; |
| 133 } | 130 } |
| 134 | 131 |
| 135 return InsertNew(key, hash, allocator); | |
| 136 } | |
| 137 | |
| 138 template <class AllocationPolicy> | |
| 139 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
| 140 TemplateHashMapImpl<AllocationPolicy>::InsertNew(void* key, uint32_t hash, | |
| 141 AllocationPolicy allocator) { | |
| 142 // Find a matching entry. | |
| 143 Entry* p = Probe(key, hash); | |
| 144 DCHECK(p->key == NULL); | |
| 145 | |
| 146 // No entry found; insert one. | 132 // No entry found; insert one. |
| 147 p->key = key; | 133 p->key = key; |
| 148 p->value = NULL; | 134 p->value = NULL; |
| 149 p->hash = hash; | 135 p->hash = hash; |
| 150 p->order = occupancy_; | 136 p->order = occupancy_; |
| 151 occupancy_++; | 137 occupancy_++; |
| 152 | 138 |
| 153 // Grow the map if we reached >= 80% occupancy. | 139 // Grow the map if we reached >= 80% occupancy. |
| 154 if (occupancy_ + occupancy_ / 4 >= capacity_) { | 140 if (occupancy_ + occupancy_ / 4 >= capacity_) { |
| 155 Resize(allocator); | 141 Resize(allocator); |
| (...skipping 205 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 361 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 347 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
| 362 } | 348 } |
| 363 return Iterator(this, this->Lookup(key, key->Hash())); | 349 return Iterator(this, this->Lookup(key, key->Hash())); |
| 364 } | 350 } |
| 365 }; | 351 }; |
| 366 | 352 |
| 367 } // namespace internal | 353 } // namespace internal |
| 368 } // namespace v8 | 354 } // namespace v8 |
| 369 | 355 |
| 370 #endif // V8_HASHMAP_H_ | 356 #endif // V8_HASHMAP_H_ |
| OLD | NEW |