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 18 matching lines...) Expand all Loading... | |
29 #define V8_HASHMAP_H_ | 29 #define V8_HASHMAP_H_ |
30 | 30 |
31 #include "allocation.h" | 31 #include "allocation.h" |
32 #include "checks.h" | 32 #include "checks.h" |
33 #include "utils.h" | 33 #include "utils.h" |
34 | 34 |
35 namespace v8 { | 35 namespace v8 { |
36 namespace internal { | 36 namespace internal { |
37 | 37 |
38 template<class AllocationPolicy> | 38 template<class AllocationPolicy> |
39 class TemplateHashMap { | 39 class TemplateHashMapImpl { |
40 public: | 40 public: |
41 typedef bool (*MatchFun) (void* key1, void* key2); | 41 typedef bool (*MatchFun) (void* key1, void* key2); |
42 | 42 |
43 // initial_capacity is the size of the initial hash map; | 43 // initial_capacity is the size of the initial hash map; |
44 // it must be a power of 2 (and thus must not be 0). | 44 // it must be a power of 2 (and thus must not be 0). |
45 TemplateHashMap(MatchFun match, uint32_t initial_capacity = 8); | 45 TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity = 8); |
46 | 46 |
47 ~TemplateHashMap(); | 47 ~TemplateHashMapImpl(); |
48 | 48 |
49 // HashMap entries are (key, value, hash) triplets. | 49 // HashMap entries are (key, value, hash) triplets. |
50 // Some clients may not need to use the value slot | 50 // Some clients may not need to use the value slot |
51 // (e.g. implementers of sets, where the key is the value). | 51 // (e.g. implementers of sets, where the key is the value). |
52 struct Entry { | 52 struct Entry { |
53 void* key; | 53 void* key; |
54 void* value; | 54 void* value; |
55 uint32_t hash; // the full hash value for key | 55 uint32_t hash; // the full hash value for key |
56 }; | 56 }; |
57 | 57 |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
92 Entry* map_; | 92 Entry* map_; |
93 uint32_t capacity_; | 93 uint32_t capacity_; |
94 uint32_t occupancy_; | 94 uint32_t occupancy_; |
95 | 95 |
96 Entry* map_end() const { return map_ + capacity_; } | 96 Entry* map_end() const { return map_ + capacity_; } |
97 Entry* Probe(void* key, uint32_t hash); | 97 Entry* Probe(void* key, uint32_t hash); |
98 void Initialize(uint32_t capacity); | 98 void Initialize(uint32_t capacity); |
99 void Resize(); | 99 void Resize(); |
100 }; | 100 }; |
101 | 101 |
102 typedef TemplateHashMap<FreeStoreAllocationPolicy> HashMap; | 102 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; |
103 | 103 |
104 template<class P> | 104 template<class P> |
105 TemplateHashMap<P>::TemplateHashMap(MatchFun match, | 105 TemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match, |
106 uint32_t initial_capacity) { | 106 uint32_t initial_capacity) { |
107 match_ = match; | 107 match_ = match; |
108 Initialize(initial_capacity); | 108 Initialize(initial_capacity); |
109 } | 109 } |
110 | 110 |
111 | 111 |
112 template<class P> | 112 template<class P> |
113 TemplateHashMap<P>::~TemplateHashMap() { | 113 TemplateHashMapImpl<P>::~TemplateHashMapImpl() { |
114 P::Delete(map_); | 114 P::Delete(map_); |
115 } | 115 } |
116 | 116 |
117 | 117 |
118 template<class P> | 118 template<class P> |
119 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Lookup( | 119 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( |
120 void* key, uint32_t hash, bool insert) { | 120 void* key, uint32_t hash, bool insert) { |
121 // Find a matching entry. | 121 // Find a matching entry. |
122 Entry* p = Probe(key, hash); | 122 Entry* p = Probe(key, hash); |
123 if (p->key != NULL) { | 123 if (p->key != NULL) { |
124 return p; | 124 return p; |
125 } | 125 } |
126 | 126 |
127 // No entry found; insert one if necessary. | 127 // No entry found; insert one if necessary. |
128 if (insert) { | 128 if (insert) { |
129 p->key = key; | 129 p->key = key; |
130 p->value = NULL; | 130 p->value = NULL; |
131 p->hash = hash; | 131 p->hash = hash; |
132 occupancy_++; | 132 occupancy_++; |
133 | 133 |
134 // Grow the map if we reached >= 80% occupancy. | 134 // Grow the map if we reached >= 80% occupancy. |
135 if (occupancy_ + occupancy_/4 >= capacity_) { | 135 if (occupancy_ + occupancy_/4 >= capacity_) { |
136 Resize(); | 136 Resize(); |
137 p = Probe(key, hash); | 137 p = Probe(key, hash); |
138 } | 138 } |
139 | 139 |
140 return p; | 140 return p; |
141 } | 141 } |
142 | 142 |
143 // No entry found and none inserted. | 143 // No entry found and none inserted. |
144 return NULL; | 144 return NULL; |
145 } | 145 } |
146 | 146 |
147 | 147 |
148 template<class P> | 148 template<class P> |
149 void TemplateHashMap<P>::Remove(void* key, uint32_t hash) { | 149 void TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) { |
150 // Lookup the entry for the key to remove. | 150 // Lookup the entry for the key to remove. |
151 Entry* p = Probe(key, hash); | 151 Entry* p = Probe(key, hash); |
152 if (p->key == NULL) { | 152 if (p->key == NULL) { |
153 // Key not found nothing to remove. | 153 // Key not found nothing to remove. |
154 return; | 154 return; |
155 } | 155 } |
156 | 156 |
157 // To remove an entry we need to ensure that it does not create an empty | 157 // To remove an entry we need to ensure that it does not create an empty |
158 // entry that will cause the search for another entry to stop too soon. If all | 158 // entry that will cause the search for another entry to stop too soon. If all |
159 // the entries between the entry to remove and the next empty slot have their | 159 // the entries between the entry to remove and the next empty slot have their |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
199 } | 199 } |
200 } | 200 } |
201 | 201 |
202 // Clear the entry which is allowed to en emptied. | 202 // Clear the entry which is allowed to en emptied. |
203 p->key = NULL; | 203 p->key = NULL; |
204 occupancy_--; | 204 occupancy_--; |
205 } | 205 } |
206 | 206 |
207 | 207 |
208 template<class P> | 208 template<class P> |
209 void TemplateHashMap<P>::Clear() { | 209 void TemplateHashMapImpl<P>::Clear() { |
210 // Mark all entries as empty. | 210 // Mark all entries as empty. |
211 const Entry* end = map_end(); | 211 const Entry* end = map_end(); |
212 for (Entry* p = map_; p < end; p++) { | 212 for (Entry* p = map_; p < end; p++) { |
213 p->key = NULL; | 213 p->key = NULL; |
214 } | 214 } |
215 occupancy_ = 0; | 215 occupancy_ = 0; |
216 } | 216 } |
217 | 217 |
218 | 218 |
219 template<class P> | 219 template<class P> |
220 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Start() const { | 220 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const { |
221 return Next(map_ - 1); | 221 return Next(map_ - 1); |
222 } | 222 } |
223 | 223 |
224 | 224 |
225 template<class P> | 225 template<class P> |
226 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Next(Entry* p) const { | 226 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p) |
227 const { | |
227 const Entry* end = map_end(); | 228 const Entry* end = map_end(); |
228 ASSERT(map_ - 1 <= p && p < end); | 229 ASSERT(map_ - 1 <= p && p < end); |
229 for (p++; p < end; p++) { | 230 for (p++; p < end; p++) { |
230 if (p->key != NULL) { | 231 if (p->key != NULL) { |
231 return p; | 232 return p; |
232 } | 233 } |
233 } | 234 } |
234 return NULL; | 235 return NULL; |
235 } | 236 } |
236 | 237 |
237 | 238 |
238 template<class P> | 239 template<class P> |
239 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Probe(void* key, | 240 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key, |
240 uint32_t hash) { | 241 uint32_t hash) { |
241 ASSERT(key != NULL); | 242 ASSERT(key != NULL); |
242 | 243 |
243 ASSERT(IsPowerOf2(capacity_)); | 244 ASSERT(IsPowerOf2(capacity_)); |
244 Entry* p = map_ + (hash & (capacity_ - 1)); | 245 Entry* p = map_ + (hash & (capacity_ - 1)); |
245 const Entry* end = map_end(); | 246 const Entry* end = map_end(); |
246 ASSERT(map_ <= p && p < end); | 247 ASSERT(map_ <= p && p < end); |
247 | 248 |
248 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. | 249 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. |
249 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 250 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
250 p++; | 251 p++; |
251 if (p >= end) { | 252 if (p >= end) { |
252 p = map_; | 253 p = map_; |
253 } | 254 } |
254 } | 255 } |
255 | 256 |
256 return p; | 257 return p; |
257 } | 258 } |
258 | 259 |
259 | 260 |
260 template<class P> | 261 template<class P> |
261 void TemplateHashMap<P>::Initialize(uint32_t capacity) { | 262 void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) { |
262 ASSERT(IsPowerOf2(capacity)); | 263 ASSERT(IsPowerOf2(capacity)); |
263 map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry))); | 264 map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry))); |
264 if (map_ == NULL) { | 265 if (map_ == NULL) { |
265 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | 266 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); |
266 return; | 267 return; |
267 } | 268 } |
268 capacity_ = capacity; | 269 capacity_ = capacity; |
269 Clear(); | 270 Clear(); |
270 } | 271 } |
271 | 272 |
272 | 273 |
273 template<class P> | 274 template<class P> |
274 void TemplateHashMap<P>::Resize() { | 275 void TemplateHashMapImpl<P>::Resize() { |
275 Entry* map = map_; | 276 Entry* map = map_; |
276 uint32_t n = occupancy_; | 277 uint32_t n = occupancy_; |
277 | 278 |
278 // Allocate larger map. | 279 // Allocate larger map. |
279 Initialize(capacity_ * 2); | 280 Initialize(capacity_ * 2); |
280 | 281 |
281 // Rehash all current entries. | 282 // Rehash all current entries. |
282 for (Entry* p = map; n > 0; p++) { | 283 for (Entry* p = map; n > 0; p++) { |
283 if (p->key != NULL) { | 284 if (p->key != NULL) { |
284 Lookup(p->key, p->hash, true)->value = p->value; | 285 Lookup(p->key, p->hash, true)->value = p->value; |
285 n--; | 286 n--; |
286 } | 287 } |
287 } | 288 } |
288 | 289 |
289 // Delete old map. | 290 // Delete old map. |
290 P::Delete(map); | 291 P::Delete(map); |
291 } | 292 } |
292 | 293 |
294 | |
295 // A hash map for pointer keys and values with an STL-like interface. | |
296 template<class Key, class Value, class AllocationPolicy> | |
297 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { | |
298 public: | |
299 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | |
300 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | |
301 struct value_type { | |
rossberg
2012/03/14 16:29:03
Hm, value_type doesn't seem to fit. I'd call this
Sven Panne
2012/03/15 07:12:57
The whole point of this finger exercise was to be
| |
302 Key* first; | |
303 Value* second; | |
304 }; | |
305 | |
306 class Iterator { | |
307 public: | |
308 Iterator& operator++() { | |
309 entry_ = map_->Next(entry_); | |
310 return *this; | |
311 } | |
312 | |
313 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | |
314 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | |
315 | |
316 private: | |
317 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, | |
318 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : | |
319 map_(map), entry_(entry) { } | |
320 | |
321 const TemplateHashMapImpl<AllocationPolicy>* map_; | |
322 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; | |
323 | |
324 friend class TemplateHashMap; | |
325 }; | |
326 | |
327 TemplateHashMap( | |
328 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match) | |
329 : TemplateHashMapImpl<AllocationPolicy>(match) { } | |
330 | |
331 Iterator begin() const { return Iterator(this, this->Start()); } | |
332 Iterator end() const { return Iterator(this, NULL); } | |
333 Iterator find(Key* key, bool insert = false) { | |
334 return Iterator(this, Lookup(key, key->Hash(), insert)); | |
335 } | |
336 }; | |
337 | |
293 } } // namespace v8::internal | 338 } } // namespace v8::internal |
294 | 339 |
295 #endif // V8_HASHMAP_H_ | 340 #endif // V8_HASHMAP_H_ |
OLD | NEW |