OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #ifndef RUNTIME_VM_HASH_MAP_H_ | 5 #ifndef RUNTIME_VM_HASH_MAP_H_ |
6 #define RUNTIME_VM_HASH_MAP_H_ | 6 #define RUNTIME_VM_HASH_MAP_H_ |
7 | 7 |
8 #include "vm/growable_array.h" // For Malloc, EmptyBase | 8 #include "vm/growable_array.h" // For Malloc, EmptyBase |
9 #include "vm/zone.h" | 9 #include "vm/zone.h" |
10 | 10 |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
106 intptr_t array_size_; | 106 intptr_t array_size_; |
107 intptr_t lists_size_; | 107 intptr_t lists_size_; |
108 intptr_t count_; // The number of values stored in the HashMap. | 108 intptr_t count_; // The number of values stored in the HashMap. |
109 HashMapListElement* array_; // Primary store - contains the first value | 109 HashMapListElement* array_; // Primary store - contains the first value |
110 // with a given hash. Colliding elements are stored in linked lists. | 110 // with a given hash. Colliding elements are stored in linked lists. |
111 HashMapListElement* lists_; // The linked lists containing hash collisions. | 111 HashMapListElement* lists_; // The linked lists containing hash collisions. |
112 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. | 112 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. |
113 Allocator* allocator_; | 113 Allocator* allocator_; |
114 }; | 114 }; |
115 | 115 |
116 | |
117 template <typename KeyValueTrait, typename B, typename Allocator> | 116 template <typename KeyValueTrait, typename B, typename Allocator> |
118 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::BaseDirectChainedHashMap( | 117 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::BaseDirectChainedHashMap( |
119 const BaseDirectChainedHashMap& other) | 118 const BaseDirectChainedHashMap& other) |
120 : B(), | 119 : B(), |
121 array_size_(other.array_size_), | 120 array_size_(other.array_size_), |
122 lists_size_(other.lists_size_), | 121 lists_size_(other.lists_size_), |
123 count_(other.count_), | 122 count_(other.count_), |
124 array_(other.allocator_->template Alloc<HashMapListElement>( | 123 array_(other.allocator_->template Alloc<HashMapListElement>( |
125 other.array_size_)), | 124 other.array_size_)), |
126 lists_(other.allocator_->template Alloc<HashMapListElement>( | 125 lists_(other.allocator_->template Alloc<HashMapListElement>( |
127 other.lists_size_)), | 126 other.lists_size_)), |
128 free_list_head_(other.free_list_head_), | 127 free_list_head_(other.free_list_head_), |
129 allocator_(other.allocator_) { | 128 allocator_(other.allocator_) { |
130 memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement)); | 129 memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement)); |
131 memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement)); | 130 memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement)); |
132 } | 131 } |
133 | 132 |
134 | |
135 template <typename KeyValueTrait, typename B, typename Allocator> | 133 template <typename KeyValueTrait, typename B, typename Allocator> |
136 typename KeyValueTrait::Pair* | 134 typename KeyValueTrait::Pair* |
137 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Lookup( | 135 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Lookup( |
138 typename KeyValueTrait::Key key) const { | 136 typename KeyValueTrait::Key key) const { |
139 const typename KeyValueTrait::Value kNoValue = | 137 const typename KeyValueTrait::Value kNoValue = |
140 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); | 138 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); |
141 | 139 |
142 uword hash = static_cast<uword>(KeyValueTrait::Hashcode(key)); | 140 uword hash = static_cast<uword>(KeyValueTrait::Hashcode(key)); |
143 uword pos = Bound(hash); | 141 uword pos = Bound(hash); |
144 if (KeyValueTrait::ValueOf(array_[pos].kv) != kNoValue) { | 142 if (KeyValueTrait::ValueOf(array_[pos].kv) != kNoValue) { |
145 if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) { | 143 if (KeyValueTrait::IsKeyEqual(array_[pos].kv, key)) { |
146 return &array_[pos].kv; | 144 return &array_[pos].kv; |
147 } | 145 } |
148 | 146 |
149 intptr_t next = array_[pos].next; | 147 intptr_t next = array_[pos].next; |
150 while (next != kNil) { | 148 while (next != kNil) { |
151 if (KeyValueTrait::IsKeyEqual(lists_[next].kv, key)) { | 149 if (KeyValueTrait::IsKeyEqual(lists_[next].kv, key)) { |
152 return &lists_[next].kv; | 150 return &lists_[next].kv; |
153 } | 151 } |
154 next = lists_[next].next; | 152 next = lists_[next].next; |
155 } | 153 } |
156 } | 154 } |
157 return NULL; | 155 return NULL; |
158 } | 156 } |
159 | 157 |
160 | |
161 template <typename KeyValueTrait, typename B, typename Allocator> | 158 template <typename KeyValueTrait, typename B, typename Allocator> |
162 typename KeyValueTrait::Value | 159 typename KeyValueTrait::Value |
163 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::LookupValue( | 160 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::LookupValue( |
164 typename KeyValueTrait::Key key) const { | 161 typename KeyValueTrait::Key key) const { |
165 const typename KeyValueTrait::Value kNoValue = | 162 const typename KeyValueTrait::Value kNoValue = |
166 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); | 163 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); |
167 typename KeyValueTrait::Pair* pair = Lookup(key); | 164 typename KeyValueTrait::Pair* pair = Lookup(key); |
168 return (pair == NULL) ? kNoValue : KeyValueTrait::ValueOf(*pair); | 165 return (pair == NULL) ? kNoValue : KeyValueTrait::ValueOf(*pair); |
169 } | 166 } |
170 | 167 |
171 | |
172 template <typename KeyValueTrait, typename B, typename Allocator> | 168 template <typename KeyValueTrait, typename B, typename Allocator> |
173 typename KeyValueTrait::Pair* | 169 typename KeyValueTrait::Pair* |
174 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Iterator::Next() { | 170 BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Iterator::Next() { |
175 const typename KeyValueTrait::Value kNoValue = | 171 const typename KeyValueTrait::Value kNoValue = |
176 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); | 172 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); |
177 | 173 |
178 if (array_index_ < map_.array_size_) { | 174 if (array_index_ < map_.array_size_) { |
179 // If we're not in the middle of a list, find the next array slot. | 175 // If we're not in the middle of a list, find the next array slot. |
180 if (list_index_ == kNil) { | 176 if (list_index_ == kNil) { |
181 while ((array_index_ < map_.array_size_) && | 177 while ((array_index_ < map_.array_size_) && |
(...skipping 14 matching lines...) Expand all Loading... |
196 | 192 |
197 // Otherwise, return the current lists_ entry, advancing list_index_. | 193 // Otherwise, return the current lists_ entry, advancing list_index_. |
198 intptr_t current = list_index_; | 194 intptr_t current = list_index_; |
199 list_index_ = map_.lists_[current].next; | 195 list_index_ = map_.lists_[current].next; |
200 return &map_.lists_[current].kv; | 196 return &map_.lists_[current].kv; |
201 } | 197 } |
202 | 198 |
203 return NULL; | 199 return NULL; |
204 } | 200 } |
205 | 201 |
206 | |
207 template <typename KeyValueTrait, typename B, typename Allocator> | 202 template <typename KeyValueTrait, typename B, typename Allocator> |
208 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Resize( | 203 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Resize( |
209 intptr_t new_size) { | 204 intptr_t new_size) { |
210 const typename KeyValueTrait::Value kNoValue = | 205 const typename KeyValueTrait::Value kNoValue = |
211 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); | 206 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); |
212 | 207 |
213 ASSERT(new_size > count_); | 208 ASSERT(new_size > count_); |
214 // Hashing the values into the new array has no more collisions than in the | 209 // Hashing the values into the new array has no more collisions than in the |
215 // old hash map, so we can use the existing lists_ array, if we are careful. | 210 // old hash map, so we can use the existing lists_ array, if we are careful. |
216 | 211 |
(...skipping 29 matching lines...) Expand all Loading... |
246 // Rehash the directly stored value. | 241 // Rehash the directly stored value. |
247 Insert(old_array[i].kv); | 242 Insert(old_array[i].kv); |
248 } | 243 } |
249 } | 244 } |
250 } | 245 } |
251 USE(old_count); | 246 USE(old_count); |
252 ASSERT(count_ == old_count); | 247 ASSERT(count_ == old_count); |
253 allocator_->template Free<HashMapListElement>(old_array, old_size); | 248 allocator_->template Free<HashMapListElement>(old_array, old_size); |
254 } | 249 } |
255 | 250 |
256 | |
257 template <typename KeyValueTrait, typename B, typename Allocator> | 251 template <typename KeyValueTrait, typename B, typename Allocator> |
258 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::ResizeLists( | 252 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::ResizeLists( |
259 intptr_t new_size) { | 253 intptr_t new_size) { |
260 ASSERT(new_size > lists_size_); | 254 ASSERT(new_size > lists_size_); |
261 | 255 |
262 HashMapListElement* new_lists = | 256 HashMapListElement* new_lists = |
263 allocator_->template Alloc<HashMapListElement>(new_size); | 257 allocator_->template Alloc<HashMapListElement>(new_size); |
264 InitArray(new_lists, new_size); | 258 InitArray(new_lists, new_size); |
265 | 259 |
266 HashMapListElement* old_lists = lists_; | 260 HashMapListElement* old_lists = lists_; |
267 intptr_t old_size = lists_size_; | 261 intptr_t old_size = lists_size_; |
268 | 262 |
269 lists_size_ = new_size; | 263 lists_size_ = new_size; |
270 lists_ = new_lists; | 264 lists_ = new_lists; |
271 | 265 |
272 if (old_lists != NULL) { | 266 if (old_lists != NULL) { |
273 memmove(lists_, old_lists, old_size * sizeof(HashMapListElement)); | 267 memmove(lists_, old_lists, old_size * sizeof(HashMapListElement)); |
274 } | 268 } |
275 for (intptr_t i = old_size; i < lists_size_; ++i) { | 269 for (intptr_t i = old_size; i < lists_size_; ++i) { |
276 lists_[i].next = free_list_head_; | 270 lists_[i].next = free_list_head_; |
277 free_list_head_ = i; | 271 free_list_head_ = i; |
278 } | 272 } |
279 allocator_->template Free<HashMapListElement>(old_lists, old_size); | 273 allocator_->template Free<HashMapListElement>(old_lists, old_size); |
280 } | 274 } |
281 | 275 |
282 | |
283 template <typename KeyValueTrait, typename B, typename Allocator> | 276 template <typename KeyValueTrait, typename B, typename Allocator> |
284 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Insert( | 277 void BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Insert( |
285 typename KeyValueTrait::Pair kv) { | 278 typename KeyValueTrait::Pair kv) { |
286 const typename KeyValueTrait::Value kNoValue = | 279 const typename KeyValueTrait::Value kNoValue = |
287 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); | 280 KeyValueTrait::ValueOf(typename KeyValueTrait::Pair()); |
288 | 281 |
289 ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue); | 282 ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue); |
290 // Resizing when half of the hashtable is filled up. | 283 // Resizing when half of the hashtable is filled up. |
291 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1); | 284 if (count_ >= array_size_ >> 1) Resize(array_size_ << 1); |
292 ASSERT(count_ < array_size_); | 285 ASSERT(count_ < array_size_); |
(...skipping 11 matching lines...) Expand all Loading... |
304 ASSERT(new_element_pos != kNil); | 297 ASSERT(new_element_pos != kNil); |
305 free_list_head_ = lists_[free_list_head_].next; | 298 free_list_head_ = lists_[free_list_head_].next; |
306 lists_[new_element_pos].kv = kv; | 299 lists_[new_element_pos].kv = kv; |
307 lists_[new_element_pos].next = array_[pos].next; | 300 lists_[new_element_pos].next = array_[pos].next; |
308 ASSERT(array_[pos].next == kNil || | 301 ASSERT(array_[pos].next == kNil || |
309 KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue); | 302 KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue); |
310 array_[pos].next = new_element_pos; | 303 array_[pos].next = new_element_pos; |
311 } | 304 } |
312 } | 305 } |
313 | 306 |
314 | |
315 template <typename KeyValueTrait, typename B, typename Allocator> | 307 template <typename KeyValueTrait, typename B, typename Allocator> |
316 bool BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Remove( | 308 bool BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Remove( |
317 typename KeyValueTrait::Key key) { | 309 typename KeyValueTrait::Key key) { |
318 uword pos = Bound(static_cast<uword>(KeyValueTrait::Hashcode(key))); | 310 uword pos = Bound(static_cast<uword>(KeyValueTrait::Hashcode(key))); |
319 | 311 |
320 // Check to see if the first element in the bucket is the one we want to | 312 // Check to see if the first element in the bucket is the one we want to |
321 // remove. | 313 // remove. |
322 if (KeyValueTrait::KeyOf(array_[pos].kv) == key) { | 314 if (KeyValueTrait::KeyOf(array_[pos].kv) == key) { |
323 if (array_[pos].next == kNil) { | 315 if (array_[pos].next == kNil) { |
324 array_[pos] = HashMapListElement(); | 316 array_[pos] = HashMapListElement(); |
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
366 } | 358 } |
367 | 359 |
368 lists_[previous].next = lists_[current].next; | 360 lists_[previous].next = lists_[current].next; |
369 lists_[current] = HashMapListElement(); | 361 lists_[current] = HashMapListElement(); |
370 lists_[current].next = free_list_head_; | 362 lists_[current].next = free_list_head_; |
371 free_list_head_ = current; | 363 free_list_head_ = current; |
372 count_--; | 364 count_--; |
373 return true; | 365 return true; |
374 } | 366 } |
375 | 367 |
376 | |
377 template <typename KeyValueTrait> | 368 template <typename KeyValueTrait> |
378 class DirectChainedHashMap | 369 class DirectChainedHashMap |
379 : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> { | 370 : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> { |
380 public: | 371 public: |
381 DirectChainedHashMap() | 372 DirectChainedHashMap() |
382 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( | 373 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( |
383 ASSERT_NOTNULL(Thread::Current()->zone())) {} | 374 ASSERT_NOTNULL(Thread::Current()->zone())) {} |
384 | 375 |
385 explicit DirectChainedHashMap(Zone* zone) | 376 explicit DirectChainedHashMap(Zone* zone) |
386 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( | 377 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( |
387 ASSERT_NOTNULL(zone)) {} | 378 ASSERT_NOTNULL(zone)) {} |
388 }; | 379 }; |
389 | 380 |
390 | |
391 template <typename KeyValueTrait> | 381 template <typename KeyValueTrait> |
392 class MallocDirectChainedHashMap | 382 class MallocDirectChainedHashMap |
393 : public BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc> { | 383 : public BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc> { |
394 public: | 384 public: |
395 MallocDirectChainedHashMap() | 385 MallocDirectChainedHashMap() |
396 : BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc>(NULL) {} | 386 : BaseDirectChainedHashMap<KeyValueTrait, EmptyBase, Malloc>(NULL) {} |
397 }; | 387 }; |
398 | 388 |
399 | |
400 template <typename T> | 389 template <typename T> |
401 class PointerKeyValueTrait { | 390 class PointerKeyValueTrait { |
402 public: | 391 public: |
403 typedef T* Value; | 392 typedef T* Value; |
404 typedef T* Key; | 393 typedef T* Key; |
405 typedef T* Pair; | 394 typedef T* Pair; |
406 | 395 |
407 static Key KeyOf(Pair kv) { return kv; } | 396 static Key KeyOf(Pair kv) { return kv; } |
408 | 397 |
409 static Value ValueOf(Pair kv) { return kv; } | 398 static Value ValueOf(Pair kv) { return kv; } |
410 | 399 |
411 static inline intptr_t Hashcode(Key key) { return key->Hashcode(); } | 400 static inline intptr_t Hashcode(Key key) { return key->Hashcode(); } |
412 | 401 |
413 static inline bool IsKeyEqual(Pair kv, Key key) { return kv->Equals(key); } | 402 static inline bool IsKeyEqual(Pair kv, Key key) { return kv->Equals(key); } |
414 }; | 403 }; |
415 | 404 |
416 | |
417 template <typename T> | 405 template <typename T> |
418 class NumbersKeyValueTrait { | 406 class NumbersKeyValueTrait { |
419 public: | 407 public: |
420 typedef T Value; | 408 typedef T Value; |
421 typedef intptr_t Key; | 409 typedef intptr_t Key; |
422 typedef T Pair; | 410 typedef T Pair; |
423 | 411 |
424 static intptr_t KeyOf(Pair kv) { return kv.first(); } | 412 static intptr_t KeyOf(Pair kv) { return kv.first(); } |
425 static T ValueOf(Pair kv) { return kv; } | 413 static T ValueOf(Pair kv) { return kv; } |
426 static inline intptr_t Hashcode(Key key) { return key; } | 414 static inline intptr_t Hashcode(Key key) { return key; } |
427 static inline bool IsKeyEqual(Pair kv, Key key) { return kv.first() == key; } | 415 static inline bool IsKeyEqual(Pair kv, Key key) { return kv.first() == key; } |
428 }; | 416 }; |
429 | 417 |
430 | |
431 template <typename K, typename V> | 418 template <typename K, typename V> |
432 class RawPointerKeyValueTrait { | 419 class RawPointerKeyValueTrait { |
433 public: | 420 public: |
434 typedef K* Key; | 421 typedef K* Key; |
435 typedef V Value; | 422 typedef V Value; |
436 | 423 |
437 struct Pair { | 424 struct Pair { |
438 Key key; | 425 Key key; |
439 Value value; | 426 Value value; |
440 Pair() : key(NULL), value() {} | 427 Pair() : key(NULL), value() {} |
441 Pair(const Key key, const Value& value) : key(key), value(value) {} | 428 Pair(const Key key, const Value& value) : key(key), value(value) {} |
442 Pair(const Pair& other) : key(other.key), value(other.value) {} | 429 Pair(const Pair& other) : key(other.key), value(other.value) {} |
443 }; | 430 }; |
444 | 431 |
445 static Key KeyOf(Pair kv) { return kv.key; } | 432 static Key KeyOf(Pair kv) { return kv.key; } |
446 static Value ValueOf(Pair kv) { return kv.value; } | 433 static Value ValueOf(Pair kv) { return kv.value; } |
447 static intptr_t Hashcode(Key key) { return reinterpret_cast<intptr_t>(key); } | 434 static intptr_t Hashcode(Key key) { return reinterpret_cast<intptr_t>(key); } |
448 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; } | 435 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; } |
449 }; | 436 }; |
450 | 437 |
451 } // namespace dart | 438 } // namespace dart |
452 | 439 |
453 #endif // RUNTIME_VM_HASH_MAP_H_ | 440 #endif // RUNTIME_VM_HASH_MAP_H_ |
OLD | NEW |