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 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
109 } | 109 } |
110 | 110 |
111 | 111 |
112 template<class P> | 112 template<class P> |
113 TemplateHashMap<P>::~TemplateHashMap() { | 113 TemplateHashMap<P>::~TemplateHashMap() { |
114 P::Delete(map_); | 114 P::Delete(map_); |
115 } | 115 } |
116 | 116 |
117 | 117 |
118 template<class P> | 118 template<class P> |
119 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Lookup( | 119 typename TemplateHashMap<P>::Entry* TemplateHashMap<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; |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
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 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Start() const { | 220 typename TemplateHashMap<P>::Entry* TemplateHashMap<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 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Next(Entry* p) const { | 226 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Next(Entry* p) const { |
227 const Entry* end = map_end(); | 227 const Entry* end = map_end(); |
228 ASSERT(map_ - 1 <= p && p < end); | 228 ASSERT(map_ - 1 <= p && p < end); |
229 for (p++; p < end; p++) { | 229 for (p++; p < end; p++) { |
230 if (p->key != NULL) { | 230 if (p->key != NULL) { |
231 return p; | 231 return p; |
232 } | 232 } |
233 } | 233 } |
234 return NULL; | 234 return NULL; |
235 } | 235 } |
236 | 236 |
237 | 237 |
238 template<class P> | 238 template<class P> |
239 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Probe(void* key, | 239 typename TemplateHashMap<P>::Entry* TemplateHashMap<P>::Probe(void* key, |
240 uint32_t hash) { | 240 uint32_t hash) { |
241 ASSERT(key != NULL); | 241 ASSERT(key != NULL); |
242 | 242 |
243 ASSERT(IsPowerOf2(capacity_)); | 243 ASSERT(IsPowerOf2(capacity_)); |
244 Entry* p = map_ + (hash & (capacity_ - 1)); | 244 Entry* p = map_ + (hash & (capacity_ - 1)); |
245 const Entry* end = map_end(); | 245 const Entry* end = map_end(); |
246 ASSERT(map_ <= p && p < end); | 246 ASSERT(map_ <= p && p < end); |
247 | 247 |
248 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. | 248 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. |
249 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 249 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
286 } | 286 } |
287 } | 287 } |
288 | 288 |
289 // Delete old map. | 289 // Delete old map. |
290 P::Delete(map); | 290 P::Delete(map); |
291 } | 291 } |
292 | 292 |
293 } } // namespace v8::internal | 293 } } // namespace v8::internal |
294 | 294 |
295 #endif // V8_HASHMAP_H_ | 295 #endif // V8_HASHMAP_H_ |
OLD | NEW |