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 | |
17 HashMap::~HashMap() { | 16 HashMap::~HashMap() { |
18 delete[] map_; | 17 delete[] map_; |
19 } | 18 } |
20 | 19 |
21 | |
22 HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { | 20 HashMap::Entry* HashMap::Lookup(void* key, uint32_t hash, bool insert) { |
23 // Find a matching entry. | 21 // Find a matching entry. |
24 Entry* p = Probe(key, hash); | 22 Entry* p = Probe(key, hash); |
25 if (p->key != NULL) { | 23 if (p->key != NULL) { |
26 return p; | 24 return p; |
27 } | 25 } |
28 | 26 |
29 // No entry found; insert one if necessary. | 27 // No entry found; insert one if necessary. |
30 if (insert) { | 28 if (insert) { |
31 p->key = key; | 29 p->key = key; |
32 p->value = NULL; | 30 p->value = NULL; |
33 p->hash = hash; | 31 p->hash = hash; |
34 occupancy_++; | 32 occupancy_++; |
35 | 33 |
36 // Grow the map if we reached >= 80% occupancy. | 34 // Grow the map if we reached >= 80% occupancy. |
37 if ((occupancy_ + (occupancy_ / 4)) >= capacity_) { | 35 if ((occupancy_ + (occupancy_ / 4)) >= capacity_) { |
38 Resize(); | 36 Resize(); |
39 p = Probe(key, hash); | 37 p = Probe(key, hash); |
40 } | 38 } |
41 | 39 |
42 return p; | 40 return p; |
43 } | 41 } |
44 | 42 |
45 // No entry found and none inserted. | 43 // No entry found and none inserted. |
46 return NULL; | 44 return NULL; |
47 } | 45 } |
48 | 46 |
49 | |
50 void HashMap::Remove(void* key, uint32_t hash) { | 47 void HashMap::Remove(void* key, uint32_t hash) { |
51 // Lookup the entry for the key to remove. | 48 // Lookup the entry for the key to remove. |
52 Entry* candidate = Probe(key, hash); | 49 Entry* candidate = Probe(key, hash); |
53 if (candidate->key == NULL) { | 50 if (candidate->key == NULL) { |
54 // Key not found nothing to remove. | 51 // Key not found nothing to remove. |
55 return; | 52 return; |
56 } | 53 } |
57 | 54 |
58 // To remove an entry we need to ensure that it does not create an empty | 55 // To remove an entry we need to ensure that it does not create an empty |
59 // entry that will cause the search for another entry to stop too soon. If all | 56 // entry that will cause the search for another entry to stop too soon. If all |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
102 *candidate = *next; | 99 *candidate = *next; |
103 candidate = next; | 100 candidate = next; |
104 } | 101 } |
105 } | 102 } |
106 | 103 |
107 // Clear the candidate which will not break searching the hash table. | 104 // Clear the candidate which will not break searching the hash table. |
108 candidate->key = NULL; | 105 candidate->key = NULL; |
109 occupancy_--; | 106 occupancy_--; |
110 } | 107 } |
111 | 108 |
112 | |
113 void HashMap::Clear(ClearFun clear) { | 109 void HashMap::Clear(ClearFun clear) { |
114 // Mark all entries as empty. | 110 // Mark all entries as empty. |
115 const Entry* end = map_end(); | 111 const Entry* end = map_end(); |
116 for (Entry* p = map_; p < end; p++) { | 112 for (Entry* p = map_; p < end; p++) { |
117 if ((clear != NULL) && (p->key != NULL)) { | 113 if ((clear != NULL) && (p->key != NULL)) { |
118 clear(p->value); | 114 clear(p->value); |
119 } | 115 } |
120 p->key = NULL; | 116 p->key = NULL; |
121 } | 117 } |
122 occupancy_ = 0; | 118 occupancy_ = 0; |
123 } | 119 } |
124 | 120 |
125 | |
126 HashMap::Entry* HashMap::Start() const { | 121 HashMap::Entry* HashMap::Start() const { |
127 return Next(map_ - 1); | 122 return Next(map_ - 1); |
128 } | 123 } |
129 | 124 |
130 | |
131 HashMap::Entry* HashMap::Next(Entry* p) const { | 125 HashMap::Entry* HashMap::Next(Entry* p) const { |
132 const Entry* end = map_end(); | 126 const Entry* end = map_end(); |
133 ASSERT(map_ - 1 <= p && p < end); | 127 ASSERT(map_ - 1 <= p && p < end); |
134 for (p++; p < end; p++) { | 128 for (p++; p < end; p++) { |
135 if (p->key != NULL) { | 129 if (p->key != NULL) { |
136 return p; | 130 return p; |
137 } | 131 } |
138 } | 132 } |
139 return NULL; | 133 return NULL; |
140 } | 134 } |
141 | 135 |
142 | |
143 HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) { | 136 HashMap::Entry* HashMap::Probe(void* key, uint32_t hash) { |
144 ASSERT(key != NULL); | 137 ASSERT(key != NULL); |
145 | 138 |
146 ASSERT(dart::Utils::IsPowerOfTwo(capacity_)); | 139 ASSERT(dart::Utils::IsPowerOfTwo(capacity_)); |
147 Entry* p = map_ + (hash & (capacity_ - 1)); | 140 Entry* p = map_ + (hash & (capacity_ - 1)); |
148 const Entry* end = map_end(); | 141 const Entry* end = map_end(); |
149 ASSERT(map_ <= p && p < end); | 142 ASSERT(map_ <= p && p < end); |
150 | 143 |
151 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. | 144 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. |
152 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 145 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
153 p++; | 146 p++; |
154 if (p >= end) { | 147 if (p >= end) { |
155 p = map_; | 148 p = map_; |
156 } | 149 } |
157 } | 150 } |
158 | 151 |
159 return p; | 152 return p; |
160 } | 153 } |
161 | 154 |
162 | |
163 void HashMap::Initialize(uint32_t capacity) { | 155 void HashMap::Initialize(uint32_t capacity) { |
164 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); | 156 ASSERT(dart::Utils::IsPowerOfTwo(capacity)); |
165 map_ = new Entry[capacity]; | 157 map_ = new Entry[capacity]; |
166 if (map_ == NULL) { | 158 if (map_ == NULL) { |
167 OUT_OF_MEMORY(); | 159 OUT_OF_MEMORY(); |
168 } | 160 } |
169 capacity_ = capacity; | 161 capacity_ = capacity; |
170 occupancy_ = 0; | 162 occupancy_ = 0; |
171 } | 163 } |
172 | 164 |
173 | |
174 void HashMap::Resize() { | 165 void HashMap::Resize() { |
175 Entry* map = map_; | 166 Entry* map = map_; |
176 uint32_t n = occupancy_; | 167 uint32_t n = occupancy_; |
177 | 168 |
178 // Allocate larger map. | 169 // Allocate larger map. |
179 Initialize(capacity_ * 2); | 170 Initialize(capacity_ * 2); |
180 | 171 |
181 // Rehash all current entries. | 172 // Rehash all current entries. |
182 for (Entry* p = map; n > 0; p++) { | 173 for (Entry* p = map; n > 0; p++) { |
183 if (p->key != NULL) { | 174 if (p->key != NULL) { |
184 Lookup(p->key, p->hash, true)->value = p->value; | 175 Lookup(p->key, p->hash, true)->value = p->value; |
185 n--; | 176 n--; |
186 } | 177 } |
187 } | 178 } |
188 | 179 |
189 // Delete old map. | 180 // Delete old map. |
190 delete[] map; | 181 delete[] map; |
191 } | 182 } |
192 | 183 |
193 } // namespace dart | 184 } // namespace dart |
OLD | NEW |