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, 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
98typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
99
100template<class AllocationPolicy>
101TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl(
102    MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) {
103  match_ = match;
104  Initialize(initial_capacity, allocator);
105}
106
107
108template<class AllocationPolicy>
109TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() {
110  AllocationPolicy::Delete(map_);
111}
112
113
114template <class AllocationPolicy>
115typename TemplateHashMapImpl<AllocationPolicy>::Entry*
116TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const {
117  Entry* p = Probe(key, hash);
118  return p->key != NULL ? p : NULL;
119}
120
121
122template <class AllocationPolicy>
123typename TemplateHashMapImpl<AllocationPolicy>::Entry*
124TemplateHashMapImpl<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
149template<class AllocationPolicy>
150void* 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
211template<class AllocationPolicy>
212void 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
222template<class AllocationPolicy>
223typename TemplateHashMapImpl<AllocationPolicy>::Entry*
224    TemplateHashMapImpl<AllocationPolicy>::Start() const {
225  return Next(map_ - 1);
226}
227
228
229template<class AllocationPolicy>
230typename 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
243template <class AllocationPolicy>
244typename TemplateHashMapImpl<AllocationPolicy>::Entry*
245TemplateHashMapImpl<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
265template<class AllocationPolicy>
266void 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
279template<class AllocationPolicy>
280void 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.
303template<class Key, class Value, class AllocationPolicy>
304class 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_
357