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