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