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
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.
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.
31 #include "allocation.h"
38 template<class AllocationPolicy>
39 class TemplateHashMapImpl {
41 typedef bool (*MatchFun) (void* key1, void* key2);
43 // initial_capacity is the size of the initial hash map;
44 // it must be a power of 2 (and thus must not be 0).
45 TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity = 8);
47 ~TemplateHashMapImpl();
49 // HashMap entries are (key, value, hash) triplets.
50 // Some clients may not need to use the value slot
51 // (e.g. implementers of sets, where the key is the value).
55 uint32_t hash; // the full hash value for key
58 // If an entry with matching key is found, Lookup()
59 // returns that entry. If no matching entry is found,
60 // but insert is set, a new entry is inserted with
61 // corresponding key, key hash, and NULL value.
62 // Otherwise, NULL is returned.
63 Entry* Lookup(void* key, uint32_t hash, bool insert);
65 // Removes the entry with matching key.
66 // It returns the value of the deleted entry
67 // or null if there is no value for such key.
68 void* Remove(void* key, uint32_t hash);
70 // Empties the hash map (occupancy() == 0).
73 // The number of (non-empty) entries in the table.
74 uint32_t occupancy() const { return occupancy_; }
76 // The capacity of the table. The implementation
77 // makes sure that occupancy is at most 80% of
78 // the table capacity.
79 uint32_t capacity() const { return capacity_; }
83 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) {
87 // If entries are inserted during iteration, the effect of
88 // calling Next() is undefined.
90 Entry* Next(Entry* p) const;
98 Entry* map_end() const { return map_ + capacity_; }
99 Entry* Probe(void* key, uint32_t hash);
100 void Initialize(uint32_t capacity);
104 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap;
107 TemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match,
108 uint32_t initial_capacity) {
110 Initialize(initial_capacity);
115 TemplateHashMapImpl<P>::~TemplateHashMapImpl() {
121 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup(
122 void* key, uint32_t hash, bool insert) {
123 // Find a matching entry.
124 Entry* p = Probe(key, hash);
125 if (p->key != NULL) {
129 // No entry found; insert one if necessary.
136 // Grow the map if we reached >= 80% occupancy.
137 if (occupancy_ + occupancy_/4 >= capacity_) {
139 p = Probe(key, hash);
145 // No entry found and none inserted.
151 void* TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) {
152 // Lookup the entry for the key to remove.
153 Entry* p = Probe(key, hash);
154 if (p->key == NULL) {
155 // Key not found nothing to remove.
159 void* value = p->value;
160 // To remove an entry we need to ensure that it does not create an empty
161 // entry that will cause the search for another entry to stop too soon. If all
162 // the entries between the entry to remove and the next empty slot have their
163 // initial position inside this interval, clearing the entry to remove will
164 // not break the search. If, while searching for the next empty entry, an
165 // entry is encountered which does not have its initial position between the
166 // entry to remove and the position looked at, then this entry can be moved to
167 // the place of the entry to remove without breaking the search for it. The
168 // entry made vacant by this move is now the entry to remove and the process
170 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing.
172 // This guarantees loop termination as there is at least one empty entry so
173 // eventually the removed entry will have an empty entry after it.
174 ASSERT(occupancy_ < capacity_);
176 // p is the candidate entry to clear. q is used to scan forwards.
177 Entry* q = p; // Start at the entry to remove.
179 // Move q to the next entry.
181 if (q == map_end()) {
185 // All entries between p and q have their initial position between p and q
186 // and the entry p can be cleared without breaking the search for these
188 if (q->key == NULL) {
192 // Find the initial position for the entry at position q.
193 Entry* r = map_ + (q->hash & (capacity_ - 1));
195 // If the entry at position q has its initial position outside the range
196 // between p and q it can be moved forward to position p and will still be
197 // found. There is now a new candidate entry for clearing.
198 if ((q > p && (r <= p || r > q)) ||
199 (q < p && (r <= p && r > q))) {
205 // Clear the entry which is allowed to en emptied.
213 void TemplateHashMapImpl<P>::Clear() {
214 // Mark all entries as empty.
215 const Entry* end = map_end();
216 for (Entry* p = map_; p < end; p++) {
224 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const {
225 return Next(map_ - 1);
230 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p)
232 const Entry* end = map_end();
233 ASSERT(map_ - 1 <= p && p < end);
234 for (p++; p < end; p++) {
235 if (p->key != NULL) {
244 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key,
248 ASSERT(IsPowerOf2(capacity_));
249 Entry* p = map_ + (hash & (capacity_ - 1));
250 const Entry* end = map_end();
251 ASSERT(map_ <= p && p < end);
253 ASSERT(occupancy_ < capacity_); // Guarantees loop termination.
254 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) {
266 void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) {
267 ASSERT(IsPowerOf2(capacity));
268 map_ = reinterpret_cast<Entry*>(P::New(capacity * sizeof(Entry)));
270 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize");
273 capacity_ = capacity;
279 void TemplateHashMapImpl<P>::Resize() {
281 uint32_t n = occupancy_;
283 // Allocate larger map.
284 Initialize(capacity_ * 2);
286 // Rehash all current entries.
287 for (Entry* p = map; n > 0; p++) {
288 if (p->key != NULL) {
289 Lookup(p->key, p->hash, true)->value = p->value;
299 // A hash map for pointer keys and values with an STL-like interface.
300 template<class Key, class Value, class AllocationPolicy>
301 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> {
303 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT
304 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT
312 Iterator& operator++() {
313 entry_ = map_->Next(entry_);
317 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); }
318 bool operator!=(const Iterator& other) { return entry_ != other.entry_; }
321 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map,
322 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) :
323 map_(map), entry_(entry) { }
325 const TemplateHashMapImpl<AllocationPolicy>* map_;
326 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_;
328 friend class TemplateHashMap;
332 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match)
333 : TemplateHashMapImpl<AllocationPolicy>(match) { }
335 Iterator begin() const { return Iterator(this, this->Start()); }
336 Iterator end() const { return Iterator(this, NULL); }
337 Iterator find(Key* key, bool insert = false) {
338 return Iterator(this, this->Lookup(key, key->Hash(), insert));
342 } } // namespace v8::internal
344 #endif // V8_HASHMAP_H_