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