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 // The reason we write our own hash map instead of using unordered_map in STL, |
6 #define V8_HASHMAP_H_ | 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 | 8 |
8 #include "src/allocation.h" | 9 #ifndef V8_BASE_HASHMAP_H_ |
| 10 #define V8_BASE_HASHMAP_H_ |
| 11 |
9 #include "src/base/bits.h" | 12 #include "src/base/bits.h" |
10 #include "src/base/logging.h" | 13 #include "src/base/logging.h" |
11 #include "src/utils.h" | |
12 | 14 |
13 namespace v8 { | 15 namespace v8 { |
14 namespace internal { | 16 namespace base { |
15 | 17 |
16 template<class AllocationPolicy> | 18 class DefaultAllocationPolicy { |
| 19 public: |
| 20 V8_INLINE void* New(size_t size) { return malloc(size); } |
| 21 V8_INLINE static void Delete(void* p) { free(p); } |
| 22 }; |
| 23 |
| 24 template <class AllocationPolicy> |
17 class TemplateHashMapImpl { | 25 class TemplateHashMapImpl { |
18 public: | 26 public: |
19 typedef bool (*MatchFun) (void* key1, void* key2); | 27 typedef bool (*MatchFun)(void* key1, void* key2); |
20 | 28 |
21 // The default capacity. This is used by the call sites which want | 29 // The default capacity. This is used by the call sites which want |
22 // to pass in a non-default AllocationPolicy but want to use the | 30 // to pass in a non-default AllocationPolicy but want to use the |
23 // default value of capacity specified by the implementation. | 31 // default value of capacity specified by the implementation. |
24 static const uint32_t kDefaultHashMapCapacity = 8; | 32 static const uint32_t kDefaultHashMapCapacity = 8; |
25 | 33 |
26 // initial_capacity is the size of the initial hash map; | 34 // initial_capacity is the size of the initial hash map; |
27 // it must be a power of 2 (and thus must not be 0). | 35 // it must be a power of 2 (and thus must not be 0). |
28 TemplateHashMapImpl(MatchFun match, | 36 TemplateHashMapImpl(MatchFun match, |
29 uint32_t capacity = kDefaultHashMapCapacity, | 37 uint32_t capacity = kDefaultHashMapCapacity, |
30 AllocationPolicy allocator = AllocationPolicy()); | 38 AllocationPolicy allocator = AllocationPolicy()); |
31 | 39 |
32 ~TemplateHashMapImpl(); | 40 ~TemplateHashMapImpl(); |
33 | 41 |
34 // HashMap entries are (key, value, hash) triplets. | 42 // HashMap entries are (key, value, hash) triplets. |
35 // Some clients may not need to use the value slot | 43 // Some clients may not need to use the value slot |
36 // (e.g. implementers of sets, where the key is the value). | 44 // (e.g. implementers of sets, where the key is the value). |
37 struct Entry { | 45 struct Entry { |
38 void* key; | 46 void* key; |
39 void* value; | 47 void* value; |
40 uint32_t hash; // The full hash value for key | 48 uint32_t hash; // The full hash value for key |
41 int order; // If you never remove entries this is the insertion order. | 49 int order; // If you never remove entries this is the insertion order. |
42 }; | 50 }; |
43 | 51 |
44 // If an entry with matching key is found, returns that entry. | 52 // If an entry with matching key is found, returns that entry. |
45 // Otherwise, NULL is returned. | 53 // Otherwise, NULL is returned. |
46 Entry* Lookup(void* key, uint32_t hash) const; | 54 Entry* Lookup(void* key, uint32_t hash) const; |
47 | 55 |
48 // If an entry with matching key is found, returns that entry. | 56 // If an entry with matching key is found, returns that entry. |
49 // If no matching entry is found, a new entry is inserted with | 57 // If no matching entry is found, a new entry is inserted with |
50 // corresponding key, key hash, and NULL value. | 58 // corresponding key, key hash, and NULL value. |
51 Entry* LookupOrInsert(void* key, uint32_t hash, | 59 Entry* LookupOrInsert(void* key, uint32_t hash, |
(...skipping 20 matching lines...) Expand all Loading... |
72 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | 80 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { |
73 // ... | 81 // ... |
74 // } | 82 // } |
75 // | 83 // |
76 // If entries are inserted during iteration, the effect of | 84 // If entries are inserted during iteration, the effect of |
77 // calling Next() is undefined. | 85 // calling Next() is undefined. |
78 Entry* Start() const; | 86 Entry* Start() const; |
79 Entry* Next(Entry* p) const; | 87 Entry* Next(Entry* p) const; |
80 | 88 |
81 // Some match functions defined for convenience. | 89 // Some match functions defined for convenience. |
82 static bool PointersMatch(void* key1, void* key2) { | 90 static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } |
83 return key1 == key2; | |
84 } | |
85 | 91 |
86 private: | 92 private: |
87 MatchFun match_; | 93 MatchFun match_; |
88 Entry* map_; | 94 Entry* map_; |
89 uint32_t capacity_; | 95 uint32_t capacity_; |
90 uint32_t occupancy_; | 96 uint32_t occupancy_; |
91 | 97 |
92 Entry* map_end() const { return map_ + capacity_; } | 98 Entry* map_end() const { return map_ + capacity_; } |
93 Entry* Probe(void* key, uint32_t hash) const; | 99 Entry* Probe(void* key, uint32_t hash) const; |
94 void Initialize(uint32_t capacity, AllocationPolicy allocator); | 100 void Initialize(uint32_t capacity, AllocationPolicy allocator); |
95 void Resize(AllocationPolicy allocator); | 101 void Resize(AllocationPolicy allocator); |
96 }; | 102 }; |
97 | 103 |
98 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; | 104 typedef TemplateHashMapImpl<DefaultAllocationPolicy> HashMap; |
99 | 105 |
100 template<class AllocationPolicy> | 106 template <class AllocationPolicy> |
101 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( | 107 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( |
102 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { | 108 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { |
103 match_ = match; | 109 match_ = match; |
104 Initialize(initial_capacity, allocator); | 110 Initialize(initial_capacity, allocator); |
105 } | 111 } |
106 | 112 |
107 | 113 template <class AllocationPolicy> |
108 template<class AllocationPolicy> | |
109 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { | 114 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { |
110 AllocationPolicy::Delete(map_); | 115 AllocationPolicy::Delete(map_); |
111 } | 116 } |
112 | 117 |
113 | |
114 template <class AllocationPolicy> | 118 template <class AllocationPolicy> |
115 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 119 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
116 TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { | 120 TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { |
117 Entry* p = Probe(key, hash); | 121 Entry* p = Probe(key, hash); |
118 return p->key != NULL ? p : NULL; | 122 return p->key != NULL ? p : NULL; |
119 } | 123 } |
120 | 124 |
121 | |
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 |
132 // No entry found; insert one. | 135 // No entry found; insert one. |
133 p->key = key; | 136 p->key = key; |
134 p->value = NULL; | 137 p->value = NULL; |
135 p->hash = hash; | 138 p->hash = hash; |
136 p->order = occupancy_; | 139 p->order = occupancy_; |
137 occupancy_++; | 140 occupancy_++; |
138 | 141 |
139 // Grow the map if we reached >= 80% occupancy. | 142 // Grow the map if we reached >= 80% occupancy. |
140 if (occupancy_ + occupancy_ / 4 >= capacity_) { | 143 if (occupancy_ + occupancy_ / 4 >= capacity_) { |
141 Resize(allocator); | 144 Resize(allocator); |
142 p = Probe(key, hash); | 145 p = Probe(key, hash); |
143 } | 146 } |
144 | 147 |
145 return p; | 148 return p; |
146 } | 149 } |
147 | 150 |
148 | 151 template <class AllocationPolicy> |
149 template<class AllocationPolicy> | |
150 void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { | 152 void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { |
151 // Lookup the entry for the key to remove. | 153 // Lookup the entry for the key to remove. |
152 Entry* p = Probe(key, hash); | 154 Entry* p = Probe(key, hash); |
153 if (p->key == NULL) { | 155 if (p->key == NULL) { |
154 // Key not found nothing to remove. | 156 // Key not found nothing to remove. |
155 return NULL; | 157 return NULL; |
156 } | 158 } |
157 | 159 |
158 void* value = p->value; | 160 void* value = p->value; |
159 // To remove an entry we need to ensure that it does not create an empty | 161 // To remove an entry we need to ensure that it does not create an empty |
(...skipping 27 matching lines...) Expand all Loading... |
187 if (q->key == NULL) { | 189 if (q->key == NULL) { |
188 break; | 190 break; |
189 } | 191 } |
190 | 192 |
191 // Find the initial position for the entry at position q. | 193 // Find the initial position for the entry at position q. |
192 Entry* r = map_ + (q->hash & (capacity_ - 1)); | 194 Entry* r = map_ + (q->hash & (capacity_ - 1)); |
193 | 195 |
194 // If the entry at position q has its initial position outside the range | 196 // If the entry at position q has its initial position outside the range |
195 // between p and q it can be moved forward to position p and will still be | 197 // between p and q it can be moved forward to position p and will still be |
196 // found. There is now a new candidate entry for clearing. | 198 // found. There is now a new candidate entry for clearing. |
197 if ((q > p && (r <= p || r > q)) || | 199 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { |
198 (q < p && (r <= p && r > q))) { | |
199 *p = *q; | 200 *p = *q; |
200 p = q; | 201 p = q; |
201 } | 202 } |
202 } | 203 } |
203 | 204 |
204 // Clear the entry which is allowed to en emptied. | 205 // Clear the entry which is allowed to en emptied. |
205 p->key = NULL; | 206 p->key = NULL; |
206 occupancy_--; | 207 occupancy_--; |
207 return value; | 208 return value; |
208 } | 209 } |
209 | 210 |
210 | 211 template <class AllocationPolicy> |
211 template<class AllocationPolicy> | |
212 void TemplateHashMapImpl<AllocationPolicy>::Clear() { | 212 void TemplateHashMapImpl<AllocationPolicy>::Clear() { |
213 // Mark all entries as empty. | 213 // Mark all entries as empty. |
214 const Entry* end = map_end(); | 214 const Entry* end = map_end(); |
215 for (Entry* p = map_; p < end; p++) { | 215 for (Entry* p = map_; p < end; p++) { |
216 p->key = NULL; | 216 p->key = NULL; |
217 } | 217 } |
218 occupancy_ = 0; | 218 occupancy_ = 0; |
219 } | 219 } |
220 | 220 |
221 | 221 template <class AllocationPolicy> |
222 template<class AllocationPolicy> | |
223 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 222 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
224 TemplateHashMapImpl<AllocationPolicy>::Start() const { | 223 TemplateHashMapImpl<AllocationPolicy>::Start() const { |
225 return Next(map_ - 1); | 224 return Next(map_ - 1); |
226 } | 225 } |
227 | 226 |
228 | 227 template <class AllocationPolicy> |
229 template<class AllocationPolicy> | |
230 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 228 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
231 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { | 229 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { |
232 const Entry* end = map_end(); | 230 const Entry* end = map_end(); |
233 DCHECK(map_ - 1 <= p && p < end); | 231 DCHECK(map_ - 1 <= p && p < end); |
234 for (p++; p < end; p++) { | 232 for (p++; p < end; p++) { |
235 if (p->key != NULL) { | 233 if (p->key != NULL) { |
236 return p; | 234 return p; |
237 } | 235 } |
238 } | 236 } |
239 return NULL; | 237 return NULL; |
240 } | 238 } |
241 | 239 |
242 | |
243 template <class AllocationPolicy> | 240 template <class AllocationPolicy> |
244 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 241 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |
245 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { | 242 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { |
246 DCHECK(key != NULL); | 243 DCHECK(key != NULL); |
247 | 244 |
248 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | 245 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
249 Entry* p = map_ + (hash & (capacity_ - 1)); | 246 Entry* p = map_ + (hash & (capacity_ - 1)); |
250 const Entry* end = map_end(); | 247 const Entry* end = map_end(); |
251 DCHECK(map_ <= p && p < end); | 248 DCHECK(map_ <= p && p < end); |
252 | 249 |
253 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 250 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
254 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 251 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
255 p++; | 252 p++; |
256 if (p >= end) { | 253 if (p >= end) { |
257 p = map_; | 254 p = map_; |
258 } | 255 } |
259 } | 256 } |
260 | 257 |
261 return p; | 258 return p; |
262 } | 259 } |
263 | 260 |
264 | 261 template <class AllocationPolicy> |
265 template<class AllocationPolicy> | |
266 void TemplateHashMapImpl<AllocationPolicy>::Initialize( | 262 void TemplateHashMapImpl<AllocationPolicy>::Initialize( |
267 uint32_t capacity, AllocationPolicy allocator) { | 263 uint32_t capacity, AllocationPolicy allocator) { |
268 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | 264 DCHECK(base::bits::IsPowerOfTwo32(capacity)); |
269 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | 265 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); |
270 if (map_ == NULL) { | 266 if (map_ == NULL) { |
271 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | 267 FATAL("Out of memory: HashMap::Initialize"); |
272 return; | 268 return; |
273 } | 269 } |
274 capacity_ = capacity; | 270 capacity_ = capacity; |
275 Clear(); | 271 Clear(); |
276 } | 272 } |
277 | 273 |
278 | 274 template <class AllocationPolicy> |
279 template<class AllocationPolicy> | |
280 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { | 275 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { |
281 Entry* map = map_; | 276 Entry* map = map_; |
282 uint32_t n = occupancy_; | 277 uint32_t n = occupancy_; |
283 | 278 |
284 // Allocate larger map. | 279 // Allocate larger map. |
285 Initialize(capacity_ * 2, allocator); | 280 Initialize(capacity_ * 2, allocator); |
286 | 281 |
287 // Rehash all current entries. | 282 // Rehash all current entries. |
288 for (Entry* p = map; n > 0; p++) { | 283 for (Entry* p = map; n > 0; p++) { |
289 if (p->key != NULL) { | 284 if (p->key != NULL) { |
290 Entry* entry = LookupOrInsert(p->key, p->hash, allocator); | 285 Entry* entry = LookupOrInsert(p->key, p->hash, allocator); |
291 entry->value = p->value; | 286 entry->value = p->value; |
292 entry->order = p->order; | 287 entry->order = p->order; |
293 n--; | 288 n--; |
294 } | 289 } |
295 } | 290 } |
296 | 291 |
297 // Delete old map. | 292 // Delete old map. |
298 AllocationPolicy::Delete(map); | 293 AllocationPolicy::Delete(map); |
299 } | 294 } |
300 | 295 |
301 | |
302 // A hash map for pointer keys and values with an STL-like interface. | 296 // A hash map for pointer keys and values with an STL-like interface. |
303 template<class Key, class Value, class AllocationPolicy> | 297 template <class Key, class Value, class AllocationPolicy> |
304 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { | 298 class TemplateHashMap : private TemplateHashMapImpl<AllocationPolicy> { |
305 public: | 299 public: |
306 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | 300 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT |
307 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | 301 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT |
308 struct value_type { | 302 struct value_type { |
309 Key* first; | 303 Key* first; |
310 Value* second; | 304 Value* second; |
311 }; | 305 }; |
312 | 306 |
313 class Iterator { | 307 class Iterator { |
314 public: | 308 public: |
315 Iterator& operator++() { | 309 Iterator& operator++() { |
316 entry_ = map_->Next(entry_); | 310 entry_ = map_->Next(entry_); |
317 return *this; | 311 return *this; |
318 } | 312 } |
319 | 313 |
320 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | 314 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } |
321 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | 315 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } |
322 | 316 |
323 private: | 317 private: |
324 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, | 318 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, |
325 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : | 319 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) |
326 map_(map), entry_(entry) { } | 320 : map_(map), entry_(entry) {} |
327 | 321 |
328 const TemplateHashMapImpl<AllocationPolicy>* map_; | 322 const TemplateHashMapImpl<AllocationPolicy>* map_; |
329 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; | 323 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; |
330 | 324 |
331 friend class TemplateHashMap; | 325 friend class TemplateHashMap; |
332 }; | 326 }; |
333 | 327 |
334 TemplateHashMap( | 328 TemplateHashMap( |
335 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, | 329 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, |
336 AllocationPolicy allocator = AllocationPolicy()) | 330 AllocationPolicy allocator = AllocationPolicy()) |
337 : TemplateHashMapImpl<AllocationPolicy>( | 331 : TemplateHashMapImpl<AllocationPolicy>( |
338 match, | 332 match, |
339 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, | 333 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, |
340 allocator) { } | 334 allocator) {} |
341 | 335 |
342 Iterator begin() const { return Iterator(this, this->Start()); } | 336 Iterator begin() const { return Iterator(this, this->Start()); } |
343 Iterator end() const { return Iterator(this, NULL); } | 337 Iterator end() const { return Iterator(this, NULL); } |
344 Iterator find(Key* key, bool insert = false, | 338 Iterator find(Key* key, bool insert = false, |
345 AllocationPolicy allocator = AllocationPolicy()) { | 339 AllocationPolicy allocator = AllocationPolicy()) { |
346 if (insert) { | 340 if (insert) { |
347 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 341 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); |
348 } | 342 } |
349 return Iterator(this, this->Lookup(key, key->Hash())); | 343 return Iterator(this, this->Lookup(key, key->Hash())); |
350 } | 344 } |
351 }; | 345 }; |
352 | 346 |
353 } // namespace internal | 347 } // namespace base |
354 } // namespace v8 | 348 } // namespace v8 |
355 | 349 |
356 #endif // V8_HASHMAP_H_ | 350 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |