• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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