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 #ifndef V8_BASE_HASHMAP_H_ |
6 | 6 #define V8_BASE_HASHMAP_H_ |
7 #ifndef V8_LIBSAMPLER_HASHMAP_H_ | |
8 #define V8_LIBSAMPLER_HASHMAP_H_ | |
9 | 7 |
10 #include "src/base/bits.h" | 8 #include "src/base/bits.h" |
11 #include "src/base/logging.h" | 9 #include "src/base/logging.h" |
12 #include "src/libsampler/utils.h" | |
13 | 10 |
14 namespace v8 { | 11 namespace v8 { |
15 namespace sampler { | 12 namespace base { |
16 | 13 |
17 class HashMapImpl { | 14 class HashMapImpl { |
Yang
2016/05/30 09:19:04
Imo this name is misleading. "Impl" stands for imp
| |
18 public: | 15 public: |
19 typedef bool (*MatchFun) (void* key1, void* key2); | 16 typedef bool (*MatchFun)(void* key1, void* key2); |
20 | 17 |
21 // The default capacity. | 18 // The default capacity. This is used by the call sites which want |
19 // to pass in a non-default AllocationPolicy but want to use the | |
20 // default value of capacity specified by the implementation. | |
22 static const uint32_t kDefaultHashMapCapacity = 8; | 21 static const uint32_t kDefaultHashMapCapacity = 8; |
23 | 22 |
24 // initial_capacity is the size of the initial hash map; | 23 HashMapImpl() {} |
25 // it must be a power of 2 (and thus must not be 0). | |
26 HashMapImpl(MatchFun match, | |
27 uint32_t capacity = kDefaultHashMapCapacity); | |
28 | 24 |
29 ~HashMapImpl(); | 25 virtual ~HashMapImpl() {} |
30 | 26 |
31 // HashMap entries are (key, value, hash) triplets. | 27 // HashMap entries are (key, value, hash) triplets. |
32 // Some clients may not need to use the value slot | 28 // Some clients may not need to use the value slot |
33 // (e.g. implementers of sets, where the key is the value). | 29 // (e.g. implementers of sets, where the key is the value). |
34 struct Entry { | 30 struct Entry { |
35 void* key; | 31 void* key; |
36 void* value; | 32 void* value; |
37 uint32_t hash; // The full hash value for key | 33 uint32_t hash; // The full hash value for key |
38 int order; // If you never remove entries this is the insertion order. | 34 int order; // If you never remove entries this is the insertion order. |
39 }; | 35 }; |
40 | 36 |
41 // If an entry with matching key is found, returns that entry. | 37 // If an entry with matching key is found, returns that entry. |
42 // Otherwise, NULL is returned. | 38 // Otherwise, NULL is returned. |
43 Entry* Lookup(void* key, uint32_t hash) const; | 39 Entry* Lookup(void* key, uint32_t hash) const; |
44 | 40 |
45 // If an entry with matching key is found, returns that entry. | 41 // If an entry with matching key is found, returns that entry. |
46 // If no matching entry is found, a new entry is inserted with | 42 // If no matching entry is found, a new entry is inserted with |
47 // corresponding key, key hash, and NULL value. | 43 // corresponding key, key hash, and NULL value. |
48 Entry* LookupOrInsert(void* key, uint32_t hash); | 44 Entry* LookupOrInsert(void* key, uint32_t hash); |
(...skipping 19 matching lines...) Expand all Loading... | |
68 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | 64 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { |
69 // ... | 65 // ... |
70 // } | 66 // } |
71 // | 67 // |
72 // If entries are inserted during iteration, the effect of | 68 // If entries are inserted during iteration, the effect of |
73 // calling Next() is undefined. | 69 // calling Next() is undefined. |
74 Entry* Start() const; | 70 Entry* Start() const; |
75 Entry* Next(Entry* p) const; | 71 Entry* Next(Entry* p) const; |
76 | 72 |
77 // Some match functions defined for convenience. | 73 // Some match functions defined for convenience. |
78 static bool PointersMatch(void* key1, void* key2) { | 74 static bool PointersMatch(void* key1, void* key2) { return key1 == key2; } |
79 return key1 == key2; | |
80 } | |
81 | 75 |
82 private: | 76 protected: |
83 MatchFun match_; | 77 MatchFun match_; |
84 Entry* map_; | 78 Entry* map_; |
85 uint32_t capacity_; | 79 uint32_t capacity_; |
86 uint32_t occupancy_; | 80 uint32_t occupancy_; |
87 | 81 |
82 Entry* Probe(void* key, uint32_t hash) const; | |
83 virtual void Resize() = 0; | |
88 Entry* map_end() const { return map_ + capacity_; } | 84 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 }; | 85 }; |
93 | 86 |
94 typedef HashMapImpl HashMap; | 87 class HashMap : public HashMapImpl { |
88 public: | |
89 // initial_capacity is the size of the initial hash map; | |
90 // it must be a power of 2 (and thus must not be 0). | |
91 explicit HashMap(MatchFun match, uint32_t capacity = kDefaultHashMapCapacity); | |
95 | 92 |
96 HashMapImpl::HashMapImpl(MatchFun match, uint32_t initial_capacity) { | 93 ~HashMap() override; |
97 match_ = match; | |
98 Initialize(initial_capacity); | |
99 } | |
100 | 94 |
95 private: | |
96 void Initialize(uint32_t capacity); | |
97 void Resize() override; | |
98 }; | |
101 | 99 |
102 HashMapImpl::~HashMapImpl() { | 100 } // namespace base |
103 Malloced::Delete(map_); | |
104 } | |
105 | |
106 | |
107 HashMapImpl::Entry* HashMapImpl::Lookup(void* key, uint32_t hash) const { | |
108 Entry* p = Probe(key, hash); | |
109 return p->key != NULL ? p : NULL; | |
110 } | |
111 | |
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) { | |
138 // Lookup the entry for the key to remove. | |
139 Entry* p = Probe(key, hash); | |
140 if (p->key == NULL) { | |
141 // Key not found nothing to remove. | |
142 return NULL; | |
143 } | |
144 | |
145 void* value = p->value; | |
146 // To remove an entry we need to ensure that it does not create an empty | |
147 // entry that will cause the search for another entry to stop too soon. If all | |
148 // the entries between the entry to remove and the next empty slot have their | |
149 // initial position inside this interval, clearing the entry to remove will | |
150 // not break the search. If, while searching for the next empty entry, an | |
151 // entry is encountered which does not have its initial position between the | |
152 // entry to remove and the position looked at, then this entry can be moved to | |
153 // the place of the entry to remove without breaking the search for it. The | |
154 // entry made vacant by this move is now the entry to remove and the process | |
155 // starts over. | |
156 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | |
157 | |
158 // This guarantees loop termination as there is at least one empty entry so | |
159 // eventually the removed entry will have an empty entry after it. | |
160 DCHECK(occupancy_ < capacity_); | |
161 | |
162 // p is the candidate entry to clear. q is used to scan forwards. | |
163 Entry* q = p; // Start at the entry to remove. | |
164 while (true) { | |
165 // Move q to the next entry. | |
166 q = q + 1; | |
167 if (q == map_end()) { | |
168 q = map_; | |
169 } | |
170 | |
171 // All entries between p and q have their initial position between p and q | |
172 // and the entry p can be cleared without breaking the search for these | |
173 // entries. | |
174 if (q->key == NULL) { | |
175 break; | |
176 } | |
177 | |
178 // Find the initial position for the entry at position q. | |
179 Entry* r = map_ + (q->hash & (capacity_ - 1)); | |
180 | |
181 // 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 | |
183 // found. There is now a new candidate entry for clearing. | |
184 if ((q > p && (r <= p || r > q)) || | |
185 (q < p && (r <= p && r > q))) { | |
186 *p = *q; | |
187 p = q; | |
188 } | |
189 } | |
190 | |
191 // Clear the entry which is allowed to en emptied. | |
192 p->key = NULL; | |
193 occupancy_--; | |
194 return value; | |
195 } | |
196 | |
197 | |
198 void HashMapImpl::Clear() { | |
199 // Mark all entries as empty. | |
200 const Entry* end = map_end(); | |
201 for (Entry* p = map_; p < end; p++) { | |
202 p->key = NULL; | |
203 } | |
204 occupancy_ = 0; | |
205 } | |
206 | |
207 | |
208 HashMapImpl::Entry* HashMapImpl::Start() const { | |
209 return Next(map_ - 1); | |
210 } | |
211 | |
212 | |
213 HashMapImpl::Entry* HashMapImpl::Next(Entry* p) const { | |
214 const Entry* end = map_end(); | |
215 DCHECK(map_ - 1 <= p && p < end); | |
216 for (p++; p < end; p++) { | |
217 if (p->key != NULL) { | |
218 return p; | |
219 } | |
220 } | |
221 return NULL; | |
222 } | |
223 | |
224 | |
225 HashMapImpl::Entry* HashMapImpl::Probe(void* key, uint32_t hash) const { | |
226 DCHECK(key != NULL); | |
227 | |
228 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | |
229 Entry* p = map_ + (hash & (capacity_ - 1)); | |
230 const Entry* end = map_end(); | |
231 DCHECK(map_ <= p && p < end); | |
232 | |
233 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | |
234 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | |
235 p++; | |
236 if (p >= end) { | |
237 p = map_; | |
238 } | |
239 } | |
240 | |
241 return p; | |
242 } | |
243 | |
244 | |
245 void HashMapImpl::Initialize(uint32_t capacity) { | |
246 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | |
247 map_ = reinterpret_cast<Entry*>(Malloced::New(capacity * sizeof(Entry))); | |
248 CHECK(map_ != NULL); | |
249 capacity_ = capacity; | |
250 Clear(); | |
251 } | |
252 | |
253 | |
254 void HashMapImpl::Resize() { | |
255 Entry* map = map_; | |
256 uint32_t n = occupancy_; | |
257 | |
258 // Allocate larger map. | |
259 Initialize(capacity_ * 2); | |
260 | |
261 // Rehash all current entries. | |
262 for (Entry* p = map; n > 0; p++) { | |
263 if (p->key != NULL) { | |
264 Entry* entry = LookupOrInsert(p->key, p->hash); | |
265 entry->value = p->value; | |
266 entry->order = p->order; | |
267 n--; | |
268 } | |
269 } | |
270 | |
271 // Delete old map. | |
272 Malloced::Delete(map); | |
273 } | |
274 | |
275 } // namespace sampler | |
276 } // namespace v8 | 101 } // namespace v8 |
277 | 102 |
278 #endif // V8_LIBSAMPLER_HASHMAP_H_ | 103 #endif // V8_BASE_HASHMAP_H_ |
OLD | NEW |