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 #ifndef V8_HASHMAP_H_ | |
6 #define V8_HASHMAP_H_ | |
7 | |
8 #include "src/allocation.h" | |
9 #include "src/base/bits.h" | |
10 #include "src/base/logging.h" | |
11 #include "src/utils.h" | |
12 | |
13 namespace v8 { | |
14 namespace internal { | |
15 | |
16 template<class AllocationPolicy> | |
17 class TemplateHashMapImpl { | |
18 public: | |
19 typedef bool (*MatchFun) (void* key1, void* key2); | |
20 | |
21 // The default capacity. This is used by the call sites which want | |
22 // to pass in a non-default AllocationPolicy but want to use the | |
23 // default value of capacity specified by the implementation. | |
24 static const uint32_t kDefaultHashMapCapacity = 8; | |
25 | |
26 // initial_capacity is the size of the initial hash map; | |
27 // it must be a power of 2 (and thus must not be 0). | |
28 TemplateHashMapImpl(MatchFun match, | |
29 uint32_t capacity = kDefaultHashMapCapacity, | |
30 AllocationPolicy allocator = AllocationPolicy()); | |
31 | |
32 ~TemplateHashMapImpl(); | |
33 | |
34 // HashMap entries are (key, value, hash) triplets. | |
35 // Some clients may not need to use the value slot | |
36 // (e.g. implementers of sets, where the key is the value). | |
37 struct Entry { | |
38 void* key; | |
39 void* value; | |
40 uint32_t hash; // The full hash value for key | |
41 int order; // If you never remove entries this is the insertion order. | |
42 }; | |
43 | |
44 // If an entry with matching key is found, returns that entry. | |
45 // Otherwise, NULL is returned. | |
46 Entry* Lookup(void* key, uint32_t hash) const; | |
47 | |
48 // If an entry with matching key is found, returns that entry. | |
49 // If no matching entry is found, a new entry is inserted with | |
50 // corresponding key, key hash, and NULL value. | |
51 Entry* LookupOrInsert(void* key, uint32_t hash, | |
52 AllocationPolicy allocator = AllocationPolicy()); | |
53 | |
54 // Removes the entry with matching key. | |
55 // It returns the value of the deleted entry | |
56 // or null if there is no value for such key. | |
57 void* Remove(void* key, uint32_t hash); | |
58 | |
59 // Empties the hash map (occupancy() == 0). | |
60 void Clear(); | |
61 | |
62 // The number of (non-empty) entries in the table. | |
63 uint32_t occupancy() const { return occupancy_; } | |
64 | |
65 // The capacity of the table. The implementation | |
66 // makes sure that occupancy is at most 80% of | |
67 // the table capacity. | |
68 uint32_t capacity() const { return capacity_; } | |
69 | |
70 // Iteration | |
71 // | |
72 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | |
73 // ... | |
74 // } | |
75 // | |
76 // If entries are inserted during iteration, the effect of | |
77 // calling Next() is undefined. | |
78 Entry* Start() const; | |
79 Entry* Next(Entry* p) const; | |
80 | |
81 // Some match functions defined for convenience. | |
82 static bool PointersMatch(void* key1, void* key2) { | |
83 return key1 == key2; | |
84 } | |
85 | |
86 private: | |
87 MatchFun match_; | |
88 Entry* map_; | |
89 uint32_t capacity_; | |
90 uint32_t occupancy_; | |
91 | |
92 Entry* map_end() const { return map_ + capacity_; } | |
93 Entry* Probe(void* key, uint32_t hash) const; | |
94 void Initialize(uint32_t capacity, AllocationPolicy allocator); | |
95 void Resize(AllocationPolicy allocator); | |
96 }; | |
97 | |
98 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; | |
99 | |
100 template<class AllocationPolicy> | |
101 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( | |
102 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { | |
103 match_ = match; | |
104 Initialize(initial_capacity, allocator); | |
105 } | |
106 | |
107 | |
108 template<class AllocationPolicy> | |
109 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { | |
110 AllocationPolicy::Delete(map_); | |
111 } | |
112 | |
113 | |
114 template <class AllocationPolicy> | |
115 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
116 TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { | |
117 Entry* p = Probe(key, hash); | |
118 return p->key != NULL ? p : NULL; | |
119 } | |
120 | |
121 | |
122 template <class AllocationPolicy> | |
123 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
124 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | |
125 void* key, uint32_t hash, AllocationPolicy allocator) { | |
126 // Find a matching entry. | |
127 Entry* p = Probe(key, hash); | |
128 if (p->key != NULL) { | |
129 return p; | |
130 } | |
131 | |
132 // No entry found; insert one. | |
133 p->key = key; | |
134 p->value = NULL; | |
135 p->hash = hash; | |
136 p->order = occupancy_; | |
137 occupancy_++; | |
138 | |
139 // Grow the map if we reached >= 80% occupancy. | |
140 if (occupancy_ + occupancy_ / 4 >= capacity_) { | |
141 Resize(allocator); | |
142 p = Probe(key, hash); | |
143 } | |
144 | |
145 return p; | |
146 } | |
147 | |
148 | |
149 template<class AllocationPolicy> | |
150 void* TemplateHashMapImpl<AllocationPolicy>::Remove(void* key, uint32_t hash) { | |
151 // Lookup the entry for the key to remove. | |
152 Entry* p = Probe(key, hash); | |
153 if (p->key == NULL) { | |
154 // Key not found nothing to remove. | |
155 return NULL; | |
156 } | |
157 | |
158 void* value = p->value; | |
159 // To remove an entry we need to ensure that it does not create an empty | |
160 // entry that will cause the search for another entry to stop too soon. If all | |
161 // the entries between the entry to remove and the next empty slot have their | |
162 // initial position inside this interval, clearing the entry to remove will | |
163 // not break the search. If, while searching for the next empty entry, an | |
164 // entry is encountered which does not have its initial position between the | |
165 // entry to remove and the position looked at, then this entry can be moved to | |
166 // the place of the entry to remove without breaking the search for it. The | |
167 // entry made vacant by this move is now the entry to remove and the process | |
168 // starts over. | |
169 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. | |
170 | |
171 // This guarantees loop termination as there is at least one empty entry so | |
172 // eventually the removed entry will have an empty entry after it. | |
173 DCHECK(occupancy_ < capacity_); | |
174 | |
175 // p is the candidate entry to clear. q is used to scan forwards. | |
176 Entry* q = p; // Start at the entry to remove. | |
177 while (true) { | |
178 // Move q to the next entry. | |
179 q = q + 1; | |
180 if (q == map_end()) { | |
181 q = map_; | |
182 } | |
183 | |
184 // All entries between p and q have their initial position between p and q | |
185 // and the entry p can be cleared without breaking the search for these | |
186 // entries. | |
187 if (q->key == NULL) { | |
188 break; | |
189 } | |
190 | |
191 // Find the initial position for the entry at position q. | |
192 Entry* r = map_ + (q->hash & (capacity_ - 1)); | |
193 | |
194 // If the entry at position q has its initial position outside the range | |
195 // between p and q it can be moved forward to position p and will still be | |
196 // found. There is now a new candidate entry for clearing. | |
197 if ((q > p && (r <= p || r > q)) || | |
198 (q < p && (r <= p && r > q))) { | |
199 *p = *q; | |
200 p = q; | |
201 } | |
202 } | |
203 | |
204 // Clear the entry which is allowed to en emptied. | |
205 p->key = NULL; | |
206 occupancy_--; | |
207 return value; | |
208 } | |
209 | |
210 | |
211 template<class AllocationPolicy> | |
212 void TemplateHashMapImpl<AllocationPolicy>::Clear() { | |
213 // Mark all entries as empty. | |
214 const Entry* end = map_end(); | |
215 for (Entry* p = map_; p < end; p++) { | |
216 p->key = NULL; | |
217 } | |
218 occupancy_ = 0; | |
219 } | |
220 | |
221 | |
222 template<class AllocationPolicy> | |
223 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
224 TemplateHashMapImpl<AllocationPolicy>::Start() const { | |
225 return Next(map_ - 1); | |
226 } | |
227 | |
228 | |
229 template<class AllocationPolicy> | |
230 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
231 TemplateHashMapImpl<AllocationPolicy>::Next(Entry* p) const { | |
232 const Entry* end = map_end(); | |
233 DCHECK(map_ - 1 <= p && p < end); | |
234 for (p++; p < end; p++) { | |
235 if (p->key != NULL) { | |
236 return p; | |
237 } | |
238 } | |
239 return NULL; | |
240 } | |
241 | |
242 | |
243 template <class AllocationPolicy> | |
244 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | |
245 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { | |
246 DCHECK(key != NULL); | |
247 | |
248 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); | |
249 Entry* p = map_ + (hash & (capacity_ - 1)); | |
250 const Entry* end = map_end(); | |
251 DCHECK(map_ <= p && p < end); | |
252 | |
253 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. | |
254 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { | |
255 p++; | |
256 if (p >= end) { | |
257 p = map_; | |
258 } | |
259 } | |
260 | |
261 return p; | |
262 } | |
263 | |
264 | |
265 template<class AllocationPolicy> | |
266 void TemplateHashMapImpl<AllocationPolicy>::Initialize( | |
267 uint32_t capacity, AllocationPolicy allocator) { | |
268 DCHECK(base::bits::IsPowerOfTwo32(capacity)); | |
269 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); | |
270 if (map_ == NULL) { | |
271 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); | |
272 return; | |
273 } | |
274 capacity_ = capacity; | |
275 Clear(); | |
276 } | |
277 | |
278 | |
279 template<class AllocationPolicy> | |
280 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { | |
281 Entry* map = map_; | |
282 uint32_t n = occupancy_; | |
283 | |
284 // Allocate larger map. | |
285 Initialize(capacity_ * 2, allocator); | |
286 | |
287 // Rehash all current entries. | |
288 for (Entry* p = map; n > 0; p++) { | |
289 if (p->key != NULL) { | |
290 Entry* entry = LookupOrInsert(p->key, p->hash, allocator); | |
291 entry->value = p->value; | |
292 entry->order = p->order; | |
293 n--; | |
294 } | |
295 } | |
296 | |
297 // Delete old map. | |
298 AllocationPolicy::Delete(map); | |
299 } | |
300 | |
301 | |
302 // A hash map for pointer keys and values with an STL-like interface. | |
303 template<class Key, class Value, class AllocationPolicy> | |
304 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { | |
305 public: | |
306 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT | |
307 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT | |
308 struct value_type { | |
309 Key* first; | |
310 Value* second; | |
311 }; | |
312 | |
313 class Iterator { | |
314 public: | |
315 Iterator& operator++() { | |
316 entry_ = map_->Next(entry_); | |
317 return *this; | |
318 } | |
319 | |
320 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } | |
321 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } | |
322 | |
323 private: | |
324 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, | |
325 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : | |
326 map_(map), entry_(entry) { } | |
327 | |
328 const TemplateHashMapImpl<AllocationPolicy>* map_; | |
329 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; | |
330 | |
331 friend class TemplateHashMap; | |
332 }; | |
333 | |
334 TemplateHashMap( | |
335 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, | |
336 AllocationPolicy allocator = AllocationPolicy()) | |
337 : TemplateHashMapImpl<AllocationPolicy>( | |
338 match, | |
339 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, | |
340 allocator) { } | |
341 | |
342 Iterator begin() const { return Iterator(this, this->Start()); } | |
343 Iterator end() const { return Iterator(this, NULL); } | |
344 Iterator find(Key* key, bool insert = false, | |
345 AllocationPolicy allocator = AllocationPolicy()) { | |
346 if (insert) { | |
347 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | |
348 } | |
349 return Iterator(this, this->Lookup(key, key->Hash())); | |
350 } | |
351 }; | |
352 | |
353 } // namespace internal | |
354 } // namespace v8 | |
355 | |
356 #endif // V8_HASHMAP_H_ | |
OLD | NEW |