OLD | NEW |
| (Empty) |
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 | |
3 // found in the LICENSE file. | |
4 | |
5 // This file is ported from src/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 | |
14 namespace v8 { | |
15 namespace sampler { | |
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 | |
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 | |
277 | |
278 #endif // V8_LIBSAMPLER_HASHMAP_H_ | |
OLD | NEW |