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 // The reason we write our own hash map instead of using unordered_map in STL, | 5 // The reason we write our own hash map instead of using unordered_map in STL, |
6 // is that STL containers use a mutex pool on debug build, which will lead to | 6 // is that STL containers use a mutex pool on debug build, which will lead to |
7 // deadlock when we are using async signal handler. | 7 // deadlock when we are using async signal handler. |
8 | 8 |
9 #ifndef V8_BASE_HASHMAP_H_ | 9 #ifndef V8_BASE_HASHMAP_H_ |
10 #define V8_BASE_HASHMAP_H_ | 10 #define V8_BASE_HASHMAP_H_ |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
54 // If an entry with matching key is found, returns that entry. | 54 // If an entry with matching key is found, returns that entry. |
55 // Otherwise, NULL is returned. | 55 // Otherwise, NULL is returned. |
56 Entry* Lookup(void* key, uint32_t hash) const; | 56 Entry* Lookup(void* key, uint32_t hash) const; |
57 | 57 |
58 // If an entry with matching key is found, returns that entry. | 58 // If an entry with matching key is found, returns that entry. |
59 // If no matching entry is found, a new entry is inserted with | 59 // If no matching entry is found, a new entry is inserted with |
60 // corresponding key, key hash, and NULL value. | 60 // corresponding key, key hash, and NULL value. |
61 Entry* LookupOrInsert(void* key, uint32_t hash, | 61 Entry* LookupOrInsert(void* key, uint32_t hash, |
62 AllocationPolicy allocator = AllocationPolicy()); | 62 AllocationPolicy allocator = AllocationPolicy()); |
63 | 63 |
64 Entry* InsertNew(void* key, uint32_t hash, | |
65 AllocationPolicy allocator = AllocationPolicy()); | |
66 | |
67 // Removes the entry with matching key. | 64 // Removes the entry with matching key. |
68 // It returns the value of the deleted entry | 65 // It returns the value of the deleted entry |
69 // or null if there is no value for such key. | 66 // or null if there is no value for such key. |
70 void* Remove(void* key, uint32_t hash); | 67 void* Remove(void* key, uint32_t hash); |
71 | 68 |
72 // Empties the hash map (occupancy() == 0). | 69 // Empties the hash map (occupancy() == 0). |
73 void Clear(); | 70 void Clear(); |
74 | 71 |
75 // The number of (non-empty) entries in the table. | 72 // The number of (non-empty) entries in the table. |
76 uint32_t occupancy() const { return occupancy_; } | 73 uint32_t occupancy() const { return occupancy_; } |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 template <class AllocationPolicy> | 127 template <class AllocationPolicy> |
131 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 128 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
132 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | 129 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( |
133 void* key, uint32_t hash, AllocationPolicy allocator) { | 130 void* key, uint32_t hash, AllocationPolicy allocator) { |
134 // Find a matching entry. | 131 // Find a matching entry. |
135 Entry* p = Probe(key, hash); | 132 Entry* p = Probe(key, hash); |
136 if (p->key != NULL) { | 133 if (p->key != NULL) { |
137 return p; | 134 return p; |
138 } | 135 } |
139 | 136 |
140 return InsertNew(key, hash, allocator); | |
141 } | |
142 | |
143 template <class AllocationPolicy> | |
144 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
145 TemplateHashMapImpl<AllocationPolicy>::InsertNew(void* key, uint32_t hash, | |
146 AllocationPolicy allocator) { | |
147 // Find a matching entry. | |
148 Entry* p = Probe(key, hash); | |
149 DCHECK(p->key == NULL); | |
150 | |
151 // No entry found; insert one. | 137 // No entry found; insert one. |
152 p->key = key; | 138 p->key = key; |
153 p->value = NULL; | 139 p->value = NULL; |
154 p->hash = hash; | 140 p->hash = hash; |
155 p->order = occupancy_; | 141 p->order = occupancy_; |
156 occupancy_++; | 142 occupancy_++; |
157 | 143 |
158 // Grow the map if we reached >= 80% occupancy. | 144 // Grow the map if we reached >= 80% occupancy. |
159 if (occupancy_ + occupancy_ / 4 >= capacity_) { | 145 if (occupancy_ + occupancy_ / 4 >= capacity_) { |
160 Resize(allocator); | 146 Resize(allocator); |
(...skipping 196 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
357 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 343 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
358 } | 344 } |
359 return Iterator(this, this->Lookup(key, key->Hash())); | 345 return Iterator(this, this->Lookup(key, key->Hash())); |
360 } | 346 } |
361 }; | 347 }; |
362 | 348 |
363 } // namespace base | 349 } // namespace base |
364 } // namespace v8 | 350 } // namespace v8 |
365 | 351 |
366 #endif // V8_BASE_HASHMAP_H_ | 352 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |