| 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 delete[] map_; | 18 free(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; | |
| 110 occupancy_--; | 109 occupancy_--; |
| 111 } | 110 } |
| 112 | 111 |
| 113 | 112 |
| 114 void HashMap::Clear(ClearFun clear) { | 113 void HashMap::Clear() { |
| 115 // Mark all entries as empty. | 114 // Mark all entries as empty. |
| 116 const Entry* end = map_end(); | 115 const Entry* end = map_end(); |
| 117 for (Entry* p = map_; p < end; p++) { | 116 for (Entry* p = map_; p < end; p++) { |
| 118 if ((clear != NULL) && (p->key != NULL)) { | |
| 119 clear(p->value); | |
| 120 } | |
| 121 p->value = NULL; | |
| 122 p->key = NULL; | 117 p->key = NULL; |
| 123 } | 118 } |
| 124 occupancy_ = 0; | 119 occupancy_ = 0; |
| 125 } | 120 } |
| 126 | 121 |
| 127 | 122 |
| 128 HashMap::Entry* HashMap::Start() const { | 123 HashMap::Entry* HashMap::Start() const { |
| 129 return Next(map_ - 1); | 124 return Next(map_ - 1); |
| 130 } | 125 } |
| 131 | 126 |
| (...skipping 25 matching lines...) Expand all Loading... |
| 157 p = map_; | 152 p = map_; |
| 158 } | 153 } |
| 159 } | 154 } |
| 160 | 155 |
| 161 return p; | 156 return p; |
| 162 } | 157 } |
| 163 | 158 |
| 164 | 159 |
| 165 void HashMap::Initialize(uint32_t capacity) { | 160 void HashMap::Initialize(uint32_t capacity) { |
| 166 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); | 161 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); |
| 167 map_ = new Entry[capacity]; | 162 map_ = reinterpret_cast<Entry*>(malloc(capacity * sizeof(Entry))); |
| 168 if (map_ == NULL) { | 163 if (map_ == NULL) { |
| 169 // TODO(sgjesse): Handle out of memory. | 164 // TODO(sgjesse): Handle out of memory. |
| 170 FATAL("Cannot allocate memory for hashmap"); | 165 FATAL("Cannot allocate memory for hashmap"); |
| 171 return; | 166 return; |
| 172 } | 167 } |
| 173 capacity_ = capacity; | 168 capacity_ = capacity; |
| 174 occupancy_ = 0; | 169 Clear(); |
| 175 } | 170 } |
| 176 | 171 |
| 177 | 172 |
| 178 void HashMap::Resize() { | 173 void HashMap::Resize() { |
| 179 Entry* map = map_; | 174 Entry* map = map_; |
| 180 uint32_t n = occupancy_; | 175 uint32_t n = occupancy_; |
| 181 | 176 |
| 182 // Allocate larger map. | 177 // Allocate larger map. |
| 183 Initialize(capacity_ * 2); | 178 Initialize(capacity_ * 2); |
| 184 | 179 |
| 185 // Rehash all current entries. | 180 // Rehash all current entries. |
| 186 for (Entry* p = map; n > 0; p++) { | 181 for (Entry* p = map; n > 0; p++) { |
| 187 if (p->key != NULL) { | 182 if (p->key != NULL) { |
| 188 Lookup(p->key, p->hash, true)->value = p->value; | 183 Lookup(p->key, p->hash, true)->value = p->value; |
| 189 n--; | 184 n--; |
| 190 } | 185 } |
| 191 } | 186 } |
| 192 | 187 |
| 193 // Delete old map. | 188 // Delete old map. |
| 194 delete[] map; | 189 free(map); |
| 195 } | 190 } |
| 196 | 191 |
| 197 } // namespace dart | 192 } // namespace dart |
| OLD | NEW |