OLD | NEW |
---|---|
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // This file is ported from src/hashmap.h | 5 #include "src/base/hashmap.h" |
6 | |
7 #ifndef V8_LIBSAMPLER_HASHMAP_H_ | |
8 #define V8_LIBSAMPLER_HASHMAP_H_ | |
9 | |
10 #include "src/base/bits.h" | |
11 #include "src/base/logging.h" | |
12 #include "src/libsampler/utils.h" | |
13 | 6 |
14 namespace v8 { | 7 namespace v8 { |
15 namespace sampler { | 8 namespace base { |
16 | |
17 class HashMapImpl { | |
18 public: | |
19 typedef bool (*MatchFun) (void* key1, void* key2); | |
20 | |
21 // The default capacity. | |
22 static const uint32_t kDefaultHashMapCapacity = 8; | |
23 | |
24 // initial_capacity is the size of the initial hash map; | |
25 // it must be a power of 2 (and thus must not be 0). | |
26 HashMapImpl(MatchFun match, | |
27 uint32_t capacity = kDefaultHashMapCapacity); | |
28 | |
29 ~HashMapImpl(); | |
30 | |
31 // HashMap entries are (key, value, hash) triplets. | |
32 // Some clients may not need to use the value slot | |
33 // (e.g. implementers of sets, where the key is the value). | |
34 struct Entry { | |
35 void* key; | |
36 void* value; | |
37 uint32_t hash; // The full hash value for key | |
38 int order; // If you never remove entries this is the insertion order. | |
39 }; | |
40 | |
41 // If an entry with matching key is found, returns that entry. | |
42 // Otherwise, NULL is returned. | |
43 Entry* Lookup(void* key, uint32_t hash) const; | |
44 | |
45 // If an entry with matching key is found, returns that entry. | |
46 // If no matching entry is found, a new entry is inserted with | |
47 // corresponding key, key hash, and NULL value. | |
48 Entry* LookupOrInsert(void* key, uint32_t hash); | |
49 | |
50 // Removes the entry with matching key. | |
51 // It returns the value of the deleted entry | |
52 // or null if there is no value for such key. | |
53 void* Remove(void* key, uint32_t hash); | |
54 | |
55 // Empties the hash map (occupancy() == 0). | |
56 void Clear(); | |
57 | |
58 // The number of (non-empty) entries in the table. | |
59 uint32_t occupancy() const { return occupancy_; } | |
60 | |
61 // The capacity of the table. The implementation | |
62 // makes sure that occupancy is at most 80% of | |
63 // the table capacity. | |
64 uint32_t capacity() const { return capacity_; } | |
65 | |
66 // Iteration | |
67 // | |
68 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | |
69 // ... | |
70 // } | |
71 // | |
72 // If entries are inserted during iteration, the effect of | |
73 // calling Next() is undefined. | |
74 Entry* Start() const; | |
75 Entry* Next(Entry* p) const; | |
76 | |
77 // Some match functions defined for convenience. | |
78 static bool PointersMatch(void* key1, void* key2) { | |
79 return key1 == key2; | |
80 } | |
81 | |
82 private: | |
83 MatchFun match_; | |
84 Entry* map_; | |
85 uint32_t capacity_; | |
86 uint32_t occupancy_; | |
87 | |
88 Entry* map_end() const { return map_ + capacity_; } | |
89 Entry* Probe(void* key, uint32_t hash) const; | |
90 void Initialize(uint32_t capacity); | |
91 void Resize(); | |
92 }; | |
93 | |
94 typedef HashMapImpl HashMap; | |
95 | |
96 HashMapImpl::HashMapImpl(MatchFun match, uint32_t initial_capacity) { | |
97 match_ = match; | |
98 Initialize(initial_capacity); | |
99 } | |
100 | |
101 | |
102 HashMapImpl::~HashMapImpl() { | |
103 Malloced::Delete(map_); | |
104 } | |
105 | |
106 | 9 |
107 HashMapImpl::Entry* HashMapImpl::Lookup(void* key, uint32_t hash) const { | 10 HashMapImpl::Entry* HashMapImpl::Lookup(void* key, uint32_t hash) const { |
108 Entry* p = Probe(key, hash); | 11 Entry* p = Probe(key, hash); |
109 return p->key != NULL ? p : NULL; | 12 return p->key != NULL ? p : NULL; |
110 } | 13 } |
111 | 14 |
112 | |
113 HashMapImpl::Entry* HashMapImpl::LookupOrInsert(void* key, uint32_t hash) { | |
114 // Find a matching entry. | |
115 Entry* p = Probe(key, hash); | |
116 if (p->key != NULL) { | |
117 return p; | |
118 } | |
119 | |
120 // No entry found; insert one. | |
121 p->key = key; | |
122 p->value = NULL; | |
123 p->hash = hash; | |
124 p->order = occupancy_; | |
125 occupancy_++; | |
126 | |
127 // Grow the map if we reached >= 80% occupancy. | |
128 if (occupancy_ + occupancy_ / 4 >= capacity_) { | |
129 Resize(); | |
130 p = Probe(key, hash); | |
131 } | |
132 | |
133 return p; | |
134 } | |
135 | |
136 | |
137 void* HashMapImpl::Remove(void* key, uint32_t hash) { | 15 void* HashMapImpl::Remove(void* key, uint32_t hash) { |
138 // Lookup the entry for the key to remove. | 16 // Lookup the entry for the key to remove. |
139 Entry* p = Probe(key, hash); | 17 Entry* p = Probe(key, hash); |
140 if (p->key == NULL) { | 18 if (p->key == NULL) { |
141 // Key not found nothing to remove. | 19 // Key not found nothing to remove. |
142 return NULL; | 20 return NULL; |
143 } | 21 } |
144 | 22 |
145 void* value = p->value; | 23 void* value = p->value; |
146 // To remove an entry we need to ensure that it does not create an empty | 24 // To remove an entry we need to ensure that it does not create an empty |
(...skipping 27 matching lines...) Expand all Loading... | |
174 if (q->key == NULL) { | 52 if (q->key == NULL) { |
175 break; | 53 break; |
176 } | 54 } |
177 | 55 |
178 // Find the initial position for the entry at position q. | 56 // Find the initial position for the entry at position q. |
179 Entry* r = map_ + (q->hash & (capacity_ - 1)); | 57 Entry* r = map_ + (q->hash & (capacity_ - 1)); |
180 | 58 |
181 // If the entry at position q has its initial position outside the range | 59 // If the entry at position q has its initial position outside the range |
182 // between p and q it can be moved forward to position p and will still be | 60 // between p and q it can be moved forward to position p and will still be |
183 // found. There is now a new candidate entry for clearing. | 61 // found. There is now a new candidate entry for clearing. |
184 if ((q > p && (r <= p || r > q)) || | 62 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { |
185 (q < p && (r <= p && r > q))) { | |
186 *p = *q; | 63 *p = *q; |
187 p = q; | 64 p = q; |
188 } | 65 } |
189 } | 66 } |
190 | 67 |
191 // Clear the entry which is allowed to en emptied. | 68 // Clear the entry which is allowed to en emptied. |
192 p->key = NULL; | 69 p->key = NULL; |
193 occupancy_--; | 70 occupancy_--; |
194 return value; | 71 return value; |
195 } | 72 } |
196 | 73 |
197 | |
198 void HashMapImpl::Clear() { | 74 void HashMapImpl::Clear() { |
199 // Mark all entries as empty. | 75 // Mark all entries as empty. |
200 const Entry* end = map_end(); | 76 const Entry* end = map_end(); |
201 for (Entry* p = map_; p < end; p++) { | 77 for (Entry* p = map_; p < end; p++) { |
202 p->key = NULL; | 78 p->key = NULL; |
203 } | 79 } |
204 occupancy_ = 0; | 80 occupancy_ = 0; |
205 } | 81 } |
206 | 82 |
207 | 83 HashMapImpl::Entry* HashMapImpl::Start() const { return Next(map_ - 1); } |
208 HashMapImpl::Entry* HashMapImpl::Start() const { | |
209 return Next(map_ - 1); | |
210 } | |
211 | |
212 | 84 |
213 HashMapImpl::Entry* HashMapImpl::Next(Entry* p) const { | 85 HashMapImpl::Entry* HashMapImpl::Next(Entry* p) const { |
214 const Entry* end = map_end(); | 86 const Entry* end = map_end(); |
215 DCHECK(map_ - 1 <= p && p < end); | 87 DCHECK(map_ - 1 <= p && p < end); |
216 for (p++; p < end; p++) { | 88 for (p++; p < end; p++) { |
217 if (p->key != NULL) { | 89 if (p->key != NULL) { |
218 return p; | 90 return p; |
219 } | 91 } |
220 } | 92 } |
221 return NULL; | 93 return NULL; |
222 } | 94 } |
223 | 95 |
224 | |
225 HashMapImpl::Entry* HashMapImpl::Probe(void* key, uint32_t hash) const { | 96 HashMapImpl::Entry* HashMapImpl::Probe(void* key, uint32_t hash) const { |
226 DCHECK(key != NULL); | 97 DCHECK(key != NULL); |
227 | 98 |
228 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | 99 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); |
229 Entry* p = map_ + (hash & (capacity_ - 1)); | 100 Entry* p = map_ + (hash & (capacity_ - 1)); |
230 const Entry* end = map_end(); | 101 const Entry* end = map_end(); |
231 DCHECK(map_ <= p && p < end); | 102 DCHECK(map_ <= p && p < end); |
232 | 103 |
233 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | 104 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. |
234 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | 105 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
235 p++; | 106 p++; |
236 if (p >= end) { | 107 if (p >= end) { |
237 p = map_; | 108 p = map_; |
238 } | 109 } |
239 } | 110 } |
240 | 111 |
241 return p; | 112 return p; |
242 } | 113 } |
243 | 114 |
115 HashMapImpl::Entry* HashMapImpl::LookupOrInsert(void* key, uint32_t hash) { | |
Yang
2016/05/30 09:19:04
This is still very similar to TemplateHashMapImpl<
| |
116 // Find a matching entry. | |
117 Entry* p = Probe(key, hash); | |
118 if (p->key != NULL) { | |
119 return p; | |
120 } | |
244 | 121 |
245 void HashMapImpl::Initialize(uint32_t capacity) { | 122 // No entry found; insert one. |
246 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | 123 p->key = key; |
247 map_ = reinterpret_cast<Entry*>(Malloced::New(capacity * sizeof(Entry))); | 124 p->value = NULL; |
248 CHECK(map_ != NULL); | 125 p->hash = hash; |
249 capacity_ = capacity; | 126 p->order = occupancy_; |
250 Clear(); | 127 occupancy_++; |
128 | |
129 // Grow the map if we reached >= 80% occupancy. | |
130 if (occupancy_ + occupancy_ / 4 >= capacity_) { | |
131 Resize(); | |
132 p = Probe(key, hash); | |
133 } | |
134 | |
135 return p; | |
251 } | 136 } |
252 | 137 |
138 HashMap::HashMap(MatchFun match, uint32_t initial_capacity) : HashMapImpl() { | |
139 match_ = match; | |
140 Initialize(initial_capacity); | |
141 } | |
253 | 142 |
254 void HashMapImpl::Resize() { | 143 HashMap::~HashMap() { free(map_); } |
144 | |
145 void HashMap::Resize() { | |
255 Entry* map = map_; | 146 Entry* map = map_; |
256 uint32_t n = occupancy_; | 147 uint32_t n = occupancy_; |
257 | 148 |
258 // Allocate larger map. | 149 // Allocate larger map. |
259 Initialize(capacity_ * 2); | 150 Initialize(capacity_ * 2); |
260 | 151 |
261 // Rehash all current entries. | 152 // Rehash all current entries. |
262 for (Entry* p = map; n > 0; p++) { | 153 for (Entry* p = map; n > 0; p++) { |
263 if (p->key != NULL) { | 154 if (p->key != NULL) { |
264 Entry* entry = LookupOrInsert(p->key, p->hash); | 155 Entry* entry = LookupOrInsert(p->key, p->hash); |
265 entry->value = p->value; | 156 entry->value = p->value; |
266 entry->order = p->order; | 157 entry->order = p->order; |
267 n--; | 158 n--; |
268 } | 159 } |
269 } | 160 } |
270 | 161 |
271 // Delete old map. | 162 // Delete old map. |
272 Malloced::Delete(map); | 163 free(map); |
273 } | 164 } |
274 | 165 |
275 } // namespace sampler | 166 void HashMap::Initialize(uint32_t capacity) { |
167 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | |
168 map_ = reinterpret_cast<Entry*>(malloc(capacity * sizeof(Entry))); | |
169 if (map_ == NULL) { | |
170 FATAL("HashMapImpl::Initialize"); | |
171 return; | |
172 } | |
173 capacity_ = capacity; | |
174 Clear(); | |
175 } | |
176 | |
177 } // namespace base | |
276 } // namespace v8 | 178 } // namespace v8 |
277 | |
278 #endif // V8_LIBSAMPLER_HASHMAP_H_ | |
OLD | NEW |