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 VM_HASH_MAP_H_ | 5 #ifndef VM_HASH_MAP_H_ |
6 #define VM_HASH_MAP_H_ | 6 #define VM_HASH_MAP_H_ |
7 | 7 |
8 namespace dart { | 8 namespace dart { |
9 | 9 |
10 template <typename T> | 10 template <typename T> |
11 class DirectChainedHashMap: public ValueObject { | 11 class DirectChainedHashMap: public ValueObject { |
12 public: | 12 public: |
13 DirectChainedHashMap() : array_size_(0), | 13 DirectChainedHashMap() : array_size_(0), |
14 lists_size_(0), | 14 lists_size_(0), |
15 count_(0), | 15 count_(0), |
16 array_(NULL), | 16 array_(NULL), |
17 lists_(NULL), | 17 lists_(NULL), |
18 free_list_head_(kNil) { | 18 free_list_head_(kNil) { |
19 ResizeLists(kInitialSize); | 19 ResizeLists(kInitialSize); |
20 Resize(kInitialSize); | 20 Resize(kInitialSize); |
21 } | 21 } |
22 | 22 |
23 DirectChainedHashMap(const DirectChainedHashMap& other); | |
24 | |
25 void Insert(T value); | 23 void Insert(T value); |
26 | 24 |
27 T Lookup(T value) const; | 25 T Lookup(T value) const; |
28 | 26 |
29 bool IsEmpty() const { return count_ == 0; } | 27 bool IsEmpty() const { return count_ == 0; } |
30 | 28 |
31 private: | 29 private: |
32 // A linked list of T values. Stored in arrays. | 30 // A linked list of T values. Stored in arrays. |
33 struct HashMapListElement { | 31 struct HashMapListElement { |
34 T value; | 32 T value; |
35 intptr_t next; // Index in the array of the next list element. | 33 intptr_t next; // Index in the array of the next list element. |
36 }; | 34 }; |
37 static const intptr_t kNil = -1; // The end of a linked list | 35 static const intptr_t kNil = -1; // The end of a linked list |
38 | 36 |
39 // Must be a power of 2. | 37 // Must be a power of 2. |
40 static const intptr_t kInitialSize = 16; | 38 static const intptr_t kInitialSize = 16; |
41 | 39 |
42 void Resize(intptr_t new_size); | 40 void Resize(intptr_t new_size); |
43 void ResizeLists(intptr_t new_size); | 41 void ResizeLists(intptr_t new_size); |
44 uword Bound(uword value) const { return value & (array_size_ - 1); } | 42 uword Bound(uword value) const { return value & (array_size_ - 1); } |
45 | 43 |
46 intptr_t array_size_; | 44 intptr_t array_size_; |
47 intptr_t lists_size_; | 45 intptr_t lists_size_; |
48 intptr_t count_; // The number of values stored in the HashMap. | 46 intptr_t count_; // The number of values stored in the HashMap. |
49 HashMapListElement* array_; // Primary store - contains the first value | 47 HashMapListElement* array_; // Primary store - contains the first value |
50 // with a given hash. Colliding elements are stored in linked lists. | 48 // with a given hash. Colliding elements are stored in linked lists. |
51 HashMapListElement* lists_; // The linked lists containing hash collisions. | 49 HashMapListElement* lists_; // The linked lists containing hash collisions. |
52 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. | 50 intptr_t free_list_head_; // Unused elements in lists_ are on the free list. |
| 51 |
| 52 DISALLOW_COPY_AND_ASSIGN(DirectChainedHashMap); |
53 }; | 53 }; |
54 | 54 |
55 | 55 |
56 template <typename T> | 56 template <typename T> |
57 T DirectChainedHashMap<T>::Lookup(T value) const { | 57 T DirectChainedHashMap<T>::Lookup(T value) const { |
58 uword hash = static_cast<uword>(value->Hashcode()); | 58 uword hash = static_cast<uword>(value->Hashcode()); |
59 uword pos = Bound(hash); | 59 uword pos = Bound(hash); |
60 if (array_[pos].value != NULL) { | 60 if (array_[pos].value != NULL) { |
61 if (array_[pos].value->Equals(value)) return array_[pos].value; | 61 if (array_[pos].value->Equals(value)) return array_[pos].value; |
62 intptr_t next = array_[pos].next; | 62 intptr_t next = array_[pos].next; |
63 while (next != kNil) { | 63 while (next != kNil) { |
64 if (lists_[next].value->Equals(value)) return lists_[next].value; | 64 if (lists_[next].value->Equals(value)) return lists_[next].value; |
65 next = lists_[next].next; | 65 next = lists_[next].next; |
66 } | 66 } |
67 } | 67 } |
68 return NULL; | 68 return NULL; |
69 } | 69 } |
70 | 70 |
71 | 71 |
72 template <typename T> | 72 template <typename T> |
73 DirectChainedHashMap<T>::DirectChainedHashMap(const DirectChainedHashMap& other) | |
74 : array_size_(other.array_size_), | |
75 lists_size_(other.lists_size_), | |
76 count_(other.count_), | |
77 array_(Isolate::Current()->current_zone()-> | |
78 Alloc<HashMapListElement>(other.array_size_)), | |
79 lists_(Isolate::Current()->current_zone()-> | |
80 Alloc<HashMapListElement>(other.lists_size_)), | |
81 free_list_head_(other.free_list_head_) { | |
82 memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement)); | |
83 memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement)); | |
84 } | |
85 | |
86 | |
87 template <typename T> | |
88 void DirectChainedHashMap<T>::Resize(intptr_t new_size) { | 73 void DirectChainedHashMap<T>::Resize(intptr_t new_size) { |
89 ASSERT(new_size > count_); | 74 ASSERT(new_size > count_); |
90 // Hashing the values into the new array has no more collisions than in the | 75 // Hashing the values into the new array has no more collisions than in the |
91 // old hash map, so we can use the existing lists_ array, if we are careful. | 76 // old hash map, so we can use the existing lists_ array, if we are careful. |
92 | 77 |
93 // Make sure we have at least one free element. | 78 // Make sure we have at least one free element. |
94 if (free_list_head_ == kNil) { | 79 if (free_list_head_ == kNil) { |
95 ResizeLists(lists_size_ << 1); | 80 ResizeLists(lists_size_ << 1); |
96 } | 81 } |
97 | 82 |
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
175 lists_[new_element_pos].value = value; | 160 lists_[new_element_pos].value = value; |
176 lists_[new_element_pos].next = array_[pos].next; | 161 lists_[new_element_pos].next = array_[pos].next; |
177 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); | 162 ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL); |
178 array_[pos].next = new_element_pos; | 163 array_[pos].next = new_element_pos; |
179 } | 164 } |
180 } | 165 } |
181 | 166 |
182 } // namespace dart | 167 } // namespace dart |
183 | 168 |
184 #endif // VM_HASH_MAP_H_ | 169 #endif // VM_HASH_MAP_H_ |
OLD | NEW |