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 #include "platform/hashmap.h" | 5 #include "platform/hashmap.h" |
6 | 6 |
7 #include "platform/utils.h" | 7 #include "platform/utils.h" |
8 | 8 |
9 namespace dart { | 9 namespace dart { |
10 | 10 |
11 HashMap::HashMap(MatchFun match, uint32_t initial_capacity) { | 11 HashMap::HashMap(MatchFun match, uint32_t initial_capacity) { |
12 match_ = match; | 12 match_ = match; |
13 Initialize(initial_capacity); | 13 Initialize(initial_capacity); |
14 } | 14 } |
15 | 15 |
16 | 16 |
17 HashMap::~HashMap() { | 17 HashMap::~HashMap() { |
18 free(map_); | 18 delete[] map_; |
19 } | 19 } |
20 | 20 |
21 | 21 |
22 HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { | 22 HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { |
23 // Find a matching entry. | 23 // Find a matching entry. |
24 Entry* p = Probe(key, hash); | 24 Entry* p = Probe(key, hash); |
25 if (p->key != NULL) { | 25 if (p->key != NULL) { |
26 return p; | 26 return p; |
27 } | 27 } |
28 | 28 |
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
99 // candidate entry for clearing. | 99 // candidate entry for clearing. |
100 if ((next > candidate && (start <= candidate || start > next)) || | 100 if ((next > candidate && (start <= candidate || start > next)) || |
101 (next < candidate && (start <= candidate && start > next))) { | 101 (next < candidate && (start <= candidate && start > next))) { |
102 *candidate = *next; | 102 *candidate = *next; |
103 candidate = next; | 103 candidate = next; |
104 } | 104 } |
105 } | 105 } |
106 | 106 |
107 // Clear the candidate which will not break searching the hash table. | 107 // Clear the candidate which will not break searching the hash table. |
108 candidate->key = NULL; | 108 candidate->key = NULL; |
| 109 candidate->value = NULL; |
109 occupancy_--; | 110 occupancy_--; |
110 } | 111 } |
111 | 112 |
112 | 113 |
113 void HashMap::Clear() { | 114 void HashMap::Clear(ClearFun clear) { |
114 // Mark all entries as empty. | 115 // Mark all entries as empty. |
115 const Entry* end = map_end(); | 116 const Entry* end = map_end(); |
116 for (Entry* p = map_; p < end; p++) { | 117 for (Entry* p = map_; p < end; p++) { |
| 118 if ((clear != NULL) && (p->key != NULL)) { |
| 119 clear(p->value); |
| 120 } |
| 121 p->value = NULL; |
117 p->key = NULL; | 122 p->key = NULL; |
118 } | 123 } |
119 occupancy_ = 0; | 124 occupancy_ = 0; |
120 } | 125 } |
121 | 126 |
122 | 127 |
123 HashMap::Entry* HashMap::Start() const { | 128 HashMap::Entry* HashMap::Start() const { |
124 return Next(map_ - 1); | 129 return Next(map_ - 1); |
125 } | 130 } |
126 | 131 |
(...skipping 25 matching lines...) Expand all Loading... |
152 p = map_; | 157 p = map_; |
153 } | 158 } |
154 } | 159 } |
155 | 160 |
156 return p; | 161 return p; |
157 } | 162 } |
158 | 163 |
159 | 164 |
160 void HashMap::Initialize(uint32_t capacity) { | 165 void HashMap::Initialize(uint32_t capacity) { |
161 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); | 166 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); |
162 map_ = reinterpret_cast<Entry*>(malloc(capacity * sizeof(Entry))); | 167 map_ = new Entry[capacity]; |
163 if (map_ == NULL) { | 168 if (map_ == NULL) { |
164 // TODO(sgjesse): Handle out of memory. | 169 // TODO(sgjesse): Handle out of memory. |
165 FATAL("Cannot allocate memory for hashmap"); | 170 FATAL("Cannot allocate memory for hashmap"); |
166 return; | 171 return; |
167 } | 172 } |
168 capacity_ = capacity; | 173 capacity_ = capacity; |
169 Clear(); | 174 occupancy_ = 0; |
170 } | 175 } |
171 | 176 |
172 | 177 |
173 void HashMap::Resize() { | 178 void HashMap::Resize() { |
174 Entry* map = map_; | 179 Entry* map = map_; |
175 uint32_t n = occupancy_; | 180 uint32_t n = occupancy_; |
176 | 181 |
177 // Allocate larger map. | 182 // Allocate larger map. |
178 Initialize(capacity_ * 2); | 183 Initialize(capacity_ * 2); |
179 | 184 |
180 // Rehash all current entries. | 185 // Rehash all current entries. |
181 for (Entry* p = map; n > 0; p++) { | 186 for (Entry* p = map; n > 0; p++) { |
182 if (p->key != NULL) { | 187 if (p->key != NULL) { |
183 Lookup(p->key, p->hash, true)->value = p->value; | 188 Lookup(p->key, p->hash, true)->value = p->value; |
184 n--; | 189 n--; |
185 } | 190 } |
186 } | 191 } |
187 | 192 |
188 // Delete old map. | 193 // Delete old map. |
189 free(map); | 194 delete[] map; |
190 } | 195 } |
191 | 196 |
192 } // namespace dart | 197 } // namespace dart |
OLD | NEW |