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