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