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.
8 #include "src/allocation.h"
9 #include "src/base/bits.h"
10 #include "src/base/logging.h"
11 #include "src/utils.h"
16 template<class AllocationPolicy>
17 class TemplateHashMapImpl {
19 typedef bool (*MatchFun) (void* key1, void* key2);
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;
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());
32 ~TemplateHashMapImpl();
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).
40 uint32_t hash; // The full hash value for key
41 int order; // If you never remove entries this is the insertion order.
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;
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());
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);
59 // Empties the hash map (occupancy() == 0).
62 // The number of (non-empty) entries in the table.
63 uint32_t occupancy() const { return occupancy_; }
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_; }
72 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
76 // If entries are inserted during iteration, the effect of
77 // calling Next() is undefined.
79 Entry* Next(Entry* p) const;
81 // Some match functions defined for convenience.
82 static bool PointersMatch(void* key1, void* key2) {
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);
98 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
100 template<class AllocationPolicy>
101 TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl(
102 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) {
104 Initialize(initial_capacity, allocator);
108 template<class AllocationPolicy>
109 TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() {
110 AllocationPolicy::Delete(map_);
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;
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) {
132 // No entry found; insert one.
136 p->order = occupancy_;
139 // Grow the map if we reached >= 80% occupancy.
140 if (occupancy_ + occupancy_ / 4 >= capacity_) {
142 p = Probe(key, hash);
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.
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
169 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
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_);
175 // p is the candidate entry to clear. q is used to scan forwards.
176 Entry* q = p; // Start at the entry to remove.
178 // Move q to the next entry.
180 if (q == map_end()) {
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
187 if (q->key == NULL) {
191 // Find the initial position for the entry at position q.
192 Entry* r = map_ + (q->hash & (capacity_ - 1));
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))) {
204 // Clear the entry which is allowed to en emptied.
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++) {
222 template<class AllocationPolicy>
223 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
224 TemplateHashMapImpl<AllocationPolicy>::Start() const {
225 return Next(map_ - 1);
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) {
243 template <class AllocationPolicy>
244 typename TemplateHashMapImpl<AllocationPolicy>::Entry*
245 TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const {
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);
253 DCHECK(occupancy_ < capacity_); // Guarantees loop termination.
254 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
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)));
271 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize");
274 capacity_ = capacity;
279 template<class AllocationPolicy>
280 void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) {
282 uint32_t n = occupancy_;
284 // Allocate larger map.
285 Initialize(capacity_ * 2, allocator);
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;
298 AllocationPolicy::Delete(map);
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> {
306 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT
307 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT
315 Iterator& operator++() {
316 entry_ = map_->Next(entry_);
320 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
321 bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
324 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map,
325 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
326 map_(map), entry_(entry) { }
328 const TemplateHashMapImpl<AllocationPolicy>* map_;
329 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;
331 friend class TemplateHashMap;
335 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match,
336 AllocationPolicy allocator = AllocationPolicy())
337 : TemplateHashMapImpl<AllocationPolicy>(
339 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity,
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()) {
347 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator));
349 return Iterator(this, this->Lookup(key, key->Hash()));
353 } // namespace internal
356 #endif // V8_HASHMAP_H_