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 15 matching lines...) Expand all Loading... |
26 } | 26 } |
27 | 27 |
28 BaseDirectChainedHashMap(const BaseDirectChainedHashMap& other); | 28 BaseDirectChainedHashMap(const BaseDirectChainedHashMap& other); |
29 | 29 |
30 ~BaseDirectChainedHashMap() { | 30 ~BaseDirectChainedHashMap() { |
31 allocator_->template Free<HashMapListElement>(array_, array_size_); | 31 allocator_->template Free<HashMapListElement>(array_, array_size_); |
32 allocator_->template Free<HashMapListElement>(lists_, lists_size_); | 32 allocator_->template Free<HashMapListElement>(lists_, lists_size_); |
33 } | 33 } |
34 | 34 |
35 void Insert(typename KeyValueTrait::Pair kv); | 35 void Insert(typename KeyValueTrait::Pair kv); |
36 bool Remove(typename KeyValueTrait::Key key); | |
37 | 36 |
38 typename KeyValueTrait::Value LookupValue( | 37 typename KeyValueTrait::Value LookupValue( |
39 typename KeyValueTrait::Key key) const; | 38 typename KeyValueTrait::Key key) const; |
40 | 39 |
41 typename KeyValueTrait::Pair* Lookup(typename KeyValueTrait::Key key) const; | 40 typename KeyValueTrait::Pair* Lookup(typename KeyValueTrait::Key key) const; |
42 | 41 |
43 bool IsEmpty() const { return count_ == 0; } | 42 bool IsEmpty() const { return count_ == 0; } |
44 | 43 |
45 void Clear() { | 44 void Clear() { |
46 if (!IsEmpty()) { | 45 if (!IsEmpty()) { |
(...skipping 255 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
302 free_list_head_ = lists_[free_list_head_].next; | 301 free_list_head_ = lists_[free_list_head_].next; |
303 lists_[new_element_pos].kv = kv; | 302 lists_[new_element_pos].kv = kv; |
304 lists_[new_element_pos].next = array_[pos].next; | 303 lists_[new_element_pos].next = array_[pos].next; |
305 ASSERT(array_[pos].next == kNil || | 304 ASSERT(array_[pos].next == kNil || |
306 KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue); | 305 KeyValueTrait::ValueOf(lists_[array_[pos].next].kv) != kNoValue); |
307 array_[pos].next = new_element_pos; | 306 array_[pos].next = new_element_pos; |
308 } | 307 } |
309 } | 308 } |
310 | 309 |
311 | 310 |
312 template <typename KeyValueTrait, typename B, typename Allocator> | |
313 bool BaseDirectChainedHashMap<KeyValueTrait, B, Allocator>::Remove( | |
314 typename KeyValueTrait::Key key) { | |
315 uword pos = Bound(static_cast<uword>(KeyValueTrait::Hashcode(key))); | |
316 | |
317 // Check to see if the first element in the bucket is the one we want to | |
318 // remove. | |
319 if (KeyValueTrait::KeyOf(array_[pos].kv) == key) { | |
320 if (array_[pos].next == kNil) { | |
321 array_[pos] = HashMapListElement(); | |
322 } else { | |
323 intptr_t next = array_[pos].next; | |
324 array_[pos] = lists_[next]; | |
325 lists_[next] = HashMapListElement(); | |
326 lists_[next].next = free_list_head_; | |
327 free_list_head_ = next; | |
328 } | |
329 count_--; | |
330 return true; | |
331 } | |
332 | |
333 intptr_t current = array_[pos].next; | |
334 | |
335 // Check the case where the second element in the bucket is the one to be | |
336 // removed. | |
337 if (KeyValueTrait::KeyOf(lists_[current].kv) == key) { | |
338 array_[pos].next = lists_[current].next; | |
339 lists_[current] = HashMapListElement(); | |
340 lists_[current].next = free_list_head_; | |
341 free_list_head_ = current; | |
342 count_--; | |
343 return true; | |
344 } | |
345 | |
346 // Finally, iterate through the rest of the bucket to see if we can find the | |
347 // entry that matches our key. | |
348 intptr_t previous; | |
349 while (KeyValueTrait::KeyOf(lists_[current].kv) != key) { | |
350 previous = current; | |
351 current = lists_[current].next; | |
352 | |
353 if (current == kNil) { | |
354 // Could not find entry with provided key to remove. | |
355 return false; | |
356 } | |
357 } | |
358 | |
359 lists_[previous].next = lists_[current].next; | |
360 lists_[current] = HashMapListElement(); | |
361 lists_[current].next = free_list_head_; | |
362 free_list_head_ = current; | |
363 count_--; | |
364 return true; | |
365 } | |
366 | |
367 | |
368 template <typename KeyValueTrait> | 311 template <typename KeyValueTrait> |
369 class DirectChainedHashMap | 312 class DirectChainedHashMap |
370 : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> { | 313 : public BaseDirectChainedHashMap<KeyValueTrait, ValueObject> { |
371 public: | 314 public: |
372 DirectChainedHashMap() | 315 DirectChainedHashMap() |
373 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( | 316 : BaseDirectChainedHashMap<KeyValueTrait, ValueObject>( |
374 ASSERT_NOTNULL(Thread::Current()->zone())) {} | 317 ASSERT_NOTNULL(Thread::Current()->zone())) {} |
375 }; | 318 }; |
376 | 319 |
377 | 320 |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
431 | 374 |
432 static Key KeyOf(Pair kv) { return kv.key; } | 375 static Key KeyOf(Pair kv) { return kv.key; } |
433 static Value ValueOf(Pair kv) { return kv.value; } | 376 static Value ValueOf(Pair kv) { return kv.value; } |
434 static intptr_t Hashcode(Key key) { return reinterpret_cast<intptr_t>(key); } | 377 static intptr_t Hashcode(Key key) { return reinterpret_cast<intptr_t>(key); } |
435 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; } | 378 static bool IsKeyEqual(Pair kv, Key key) { return kv.key == key; } |
436 }; | 379 }; |
437 | 380 |
438 } // namespace dart | 381 } // namespace dart |
439 | 382 |
440 #endif // RUNTIME_VM_HASH_MAP_H_ | 383 #endif // RUNTIME_VM_HASH_MAP_H_ |
OLD | NEW |