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// The reason we write our own hash map instead of using unordered_map in STL, 6// is that STL containers use a mutex pool on debug build, which will lead to 7// deadlock when we are using async signal handler. 8 9#ifndef V8_BASE_HASHMAP_H_ 10#define V8_BASE_HASHMAP_H_ 11 12#include <stdlib.h> 13 14#include "src/base/bits.h" 15#include "src/base/hashmap-entry.h" 16#include "src/base/logging.h" 17 18namespace v8 { 19namespace base { 20 21class DefaultAllocationPolicy { 22 public: 23 V8_INLINE void* New(size_t size) { return malloc(size); } 24 V8_INLINE static void Delete(void* p) { free(p); } 25}; 26 27template <typename Key, typename Value, class MatchFun, class AllocationPolicy> 28class TemplateHashMapImpl { 29 public: 30 typedef TemplateHashMapEntry<Key, Value> Entry; 31 32 // The default capacity. This is used by the call sites which want 33 // to pass in a non-default AllocationPolicy but want to use the 34 // default value of capacity specified by the implementation. 35 static const uint32_t kDefaultHashMapCapacity = 8; 36 37 // initial_capacity is the size of the initial hash map; 38 // it must be a power of 2 (and thus must not be 0). 39 TemplateHashMapImpl(uint32_t capacity = kDefaultHashMapCapacity, 40 MatchFun match = MatchFun(), 41 AllocationPolicy allocator = AllocationPolicy()); 42 43 ~TemplateHashMapImpl(); 44 45 // If an entry with matching key is found, returns that entry. 46 // Otherwise, nullptr is returned. 47 Entry* Lookup(const Key& key, uint32_t hash) const; 48 49 // If an entry with matching key is found, returns that entry. 50 // If no matching entry is found, a new entry is inserted with 51 // corresponding key, key hash, and default initialized value. 52 Entry* LookupOrInsert(const Key& key, uint32_t hash, 53 AllocationPolicy allocator = AllocationPolicy()); 54 55 // If an entry with matching key is found, returns that entry. 56 // If no matching entry is found, a new entry is inserted with 57 // corresponding key, key hash, and value created by func. 58 template <typename Func> 59 Entry* LookupOrInsert(const Key& key, uint32_t hash, const Func& value_func, 60 AllocationPolicy allocator = AllocationPolicy()); 61 62 Entry* InsertNew(const Key& key, uint32_t hash, 63 AllocationPolicy allocator = AllocationPolicy()); 64 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 Value Remove(const Key& key, uint32_t hash); 69 70 // Empties the hash map (occupancy() == 0). 71 void Clear(); 72 73 // The number of (non-empty) entries in the table. 74 uint32_t occupancy() const { return occupancy_; } 75 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_; } 80 81 // Iteration 82 // 83 // for (Entry* p = map.Start(); p != nullptr; p = map.Next(p)) { 84 // ... 85 // } 86 // 87 // If entries are inserted during iteration, the effect of 88 // calling Next() is undefined. 89 Entry* Start() const; 90 Entry* Next(Entry* entry) const; 91 92 private: 93 Entry* map_; 94 uint32_t capacity_; 95 uint32_t occupancy_; 96 // TODO(leszeks): This takes up space even if it has no state, maybe replace 97 // with something that does the empty base optimisation e.g. std::tuple 98 MatchFun match_; 99 100 Entry* map_end() const { return map_ + capacity_; } 101 Entry* Probe(const Key& key, uint32_t hash) const; 102 Entry* FillEmptyEntry(Entry* entry, const Key& key, const Value& value, 103 uint32_t hash, 104 AllocationPolicy allocator = AllocationPolicy()); 105 void Initialize(uint32_t capacity, AllocationPolicy allocator); 106 void Resize(AllocationPolicy allocator); 107}; 108template <typename Key, typename Value, typename MatchFun, 109 class AllocationPolicy> 110TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>:: 111 TemplateHashMapImpl(uint32_t initial_capacity, MatchFun match, 112 AllocationPolicy allocator) 113 : match_(match) { 114 Initialize(initial_capacity, allocator); 115} 116 117template <typename Key, typename Value, typename MatchFun, 118 class AllocationPolicy> 119TemplateHashMapImpl<Key, Value, MatchFun, 120 AllocationPolicy>::~TemplateHashMapImpl() { 121 AllocationPolicy::Delete(map_); 122} 123 124template <typename Key, typename Value, typename MatchFun, 125 class AllocationPolicy> 126typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 127TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Lookup( 128 const Key& key, uint32_t hash) const { 129 Entry* entry = Probe(key, hash); 130 return entry->exists() ? entry : nullptr; 131} 132 133template <typename Key, typename Value, typename MatchFun, 134 class AllocationPolicy> 135typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 136TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert( 137 const Key& key, uint32_t hash, AllocationPolicy allocator) { 138 return LookupOrInsert(key, hash, []() { return Value(); }, allocator); 139} 140 141template <typename Key, typename Value, typename MatchFun, 142 class AllocationPolicy> 143template <typename Func> 144typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 145TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::LookupOrInsert( 146 const Key& key, uint32_t hash, const Func& value_func, 147 AllocationPolicy allocator) { 148 // Find a matching entry. 149 Entry* entry = Probe(key, hash); 150 if (entry->exists()) { 151 return entry; 152 } 153 154 return FillEmptyEntry(entry, key, value_func(), hash, allocator); 155} 156 157template <typename Key, typename Value, typename MatchFun, 158 class AllocationPolicy> 159typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 160TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::InsertNew( 161 const Key& key, uint32_t hash, AllocationPolicy allocator) { 162 Entry* entry = Probe(key, hash); 163 return FillEmptyEntry(entry, key, Value(), hash, allocator); 164} 165 166template <typename Key, typename Value, typename MatchFun, 167 class AllocationPolicy> 168Value TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Remove( 169 const Key& key, uint32_t hash) { 170 // Lookup the entry for the key to remove. 171 Entry* p = Probe(key, hash); 172 if (!p->exists()) { 173 // Key not found nothing to remove. 174 return nullptr; 175 } 176 177 Value value = p->value; 178 // To remove an entry we need to ensure that it does not create an empty 179 // entry that will cause the search for another entry to stop too soon. If all 180 // the entries between the entry to remove and the next empty slot have their 181 // initial position inside this interval, clearing the entry to remove will 182 // not break the search. If, while searching for the next empty entry, an 183 // entry is encountered which does not have its initial position between the 184 // entry to remove and the position looked at, then this entry can be moved to 185 // the place of the entry to remove without breaking the search for it. The 186 // entry made vacant by this move is now the entry to remove and the process 187 // starts over. 188 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 189 190 // This guarantees loop termination as there is at least one empty entry so 191 // eventually the removed entry will have an empty entry after it. 192 DCHECK(occupancy_ < capacity_); 193 194 // p is the candidate entry to clear. q is used to scan forwards. 195 Entry* q = p; // Start at the entry to remove. 196 while (true) { 197 // Move q to the next entry. 198 q = q + 1; 199 if (q == map_end()) { 200 q = map_; 201 } 202 203 // All entries between p and q have their initial position between p and q 204 // and the entry p can be cleared without breaking the search for these 205 // entries. 206 if (!q->exists()) { 207 break; 208 } 209 210 // Find the initial position for the entry at position q. 211 Entry* r = map_ + (q->hash & (capacity_ - 1)); 212 213 // If the entry at position q has its initial position outside the range 214 // between p and q it can be moved forward to position p and will still be 215 // found. There is now a new candidate entry for clearing. 216 if ((q > p && (r <= p || r > q)) || (q < p && (r <= p && r > q))) { 217 *p = *q; 218 p = q; 219 } 220 } 221 222 // Clear the entry which is allowed to en emptied. 223 p->clear(); 224 occupancy_--; 225 return value; 226} 227 228template <typename Key, typename Value, typename MatchFun, 229 class AllocationPolicy> 230void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Clear() { 231 // Mark all entries as empty. 232 for (size_t i = 0; i < capacity_; ++i) { 233 map_[i].clear(); 234 } 235 occupancy_ = 0; 236} 237 238template <typename Key, typename Value, typename MatchFun, 239 class AllocationPolicy> 240typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 241TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Start() const { 242 return Next(map_ - 1); 243} 244 245template <typename Key, typename Value, typename MatchFun, 246 class AllocationPolicy> 247typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 248TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Next( 249 Entry* entry) const { 250 const Entry* end = map_end(); 251 DCHECK(map_ - 1 <= entry && entry < end); 252 for (entry++; entry < end; entry++) { 253 if (entry->exists()) { 254 return entry; 255 } 256 } 257 return nullptr; 258} 259 260template <typename Key, typename Value, typename MatchFun, 261 class AllocationPolicy> 262typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 263TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Probe( 264 const Key& key, uint32_t hash) const { 265 DCHECK(base::bits::IsPowerOfTwo32(capacity_)); 266 size_t i = hash & (capacity_ - 1); 267 DCHECK(i < capacity_); 268 269 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. 270 while (map_[i].exists() && !match_(hash, map_[i].hash, key, map_[i].key)) { 271 i = (i + 1) & (capacity_ - 1); 272 } 273 274 return &map_[i]; 275} 276 277template <typename Key, typename Value, typename MatchFun, 278 class AllocationPolicy> 279typename TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Entry* 280TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::FillEmptyEntry( 281 Entry* entry, const Key& key, const Value& value, uint32_t hash, 282 AllocationPolicy allocator) { 283 DCHECK(!entry->exists()); 284 285 new (entry) Entry(key, value, hash); 286 occupancy_++; 287 288 // Grow the map if we reached >= 80% occupancy. 289 if (occupancy_ + occupancy_ / 4 >= capacity_) { 290 Resize(allocator); 291 entry = Probe(key, hash); 292 } 293 294 return entry; 295} 296 297template <typename Key, typename Value, typename MatchFun, 298 class AllocationPolicy> 299void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Initialize( 300 uint32_t capacity, AllocationPolicy allocator) { 301 DCHECK(base::bits::IsPowerOfTwo32(capacity)); 302 map_ = reinterpret_cast<Entry*>(allocator.New(capacity * sizeof(Entry))); 303 if (map_ == nullptr) { 304 FATAL("Out of memory: HashMap::Initialize"); 305 return; 306 } 307 capacity_ = capacity; 308 Clear(); 309} 310 311template <typename Key, typename Value, typename MatchFun, 312 class AllocationPolicy> 313void TemplateHashMapImpl<Key, Value, MatchFun, AllocationPolicy>::Resize( 314 AllocationPolicy allocator) { 315 Entry* map = map_; 316 uint32_t n = occupancy_; 317 318 // Allocate larger map. 319 Initialize(capacity_ * 2, allocator); 320 321 // Rehash all current entries. 322 for (Entry* entry = map; n > 0; entry++) { 323 if (entry->exists()) { 324 Entry* new_entry = Probe(entry->key, entry->hash); 325 new_entry = FillEmptyEntry(new_entry, entry->key, entry->value, 326 entry->hash, allocator); 327 n--; 328 } 329 } 330 331 // Delete old map. 332 AllocationPolicy::Delete(map); 333} 334 335// Match function which compares hashes before executing a (potentially 336// expensive) key comparison. 337template <typename Key, typename MatchFun> 338struct HashEqualityThenKeyMatcher { 339 explicit HashEqualityThenKeyMatcher(MatchFun match) : match_(match) {} 340 341 bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1, 342 const Key& key2) const { 343 return hash1 == hash2 && match_(key1, key2); 344 } 345 346 private: 347 MatchFun match_; 348}; 349 350// Hashmap<void*, void*> which takes a custom key comparison function pointer. 351template <typename AllocationPolicy> 352class CustomMatcherTemplateHashMapImpl 353 : public TemplateHashMapImpl< 354 void*, void*, 355 HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>, 356 AllocationPolicy> { 357 typedef TemplateHashMapImpl< 358 void*, void*, HashEqualityThenKeyMatcher<void*, bool (*)(void*, void*)>, 359 AllocationPolicy> 360 Base; 361 362 public: 363 typedef bool (*MatchFun)(void*, void*); 364 365 CustomMatcherTemplateHashMapImpl( 366 MatchFun match, uint32_t capacity = Base::kDefaultHashMapCapacity, 367 AllocationPolicy allocator = AllocationPolicy()) 368 : Base(capacity, HashEqualityThenKeyMatcher<void*, MatchFun>(match), 369 allocator) {} 370}; 371 372typedef CustomMatcherTemplateHashMapImpl<DefaultAllocationPolicy> 373 CustomMatcherHashMap; 374 375// Match function which compares keys directly by equality. 376template <typename Key> 377struct KeyEqualityMatcher { 378 bool operator()(uint32_t hash1, uint32_t hash2, const Key& key1, 379 const Key& key2) const { 380 return key1 == key2; 381 } 382}; 383 384// Hashmap<void*, void*> which compares the key pointers directly. 385template <typename AllocationPolicy> 386class PointerTemplateHashMapImpl 387 : public TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>, 388 AllocationPolicy> { 389 typedef TemplateHashMapImpl<void*, void*, KeyEqualityMatcher<void*>, 390 AllocationPolicy> 391 Base; 392 393 public: 394 PointerTemplateHashMapImpl(uint32_t capacity = Base::kDefaultHashMapCapacity, 395 AllocationPolicy allocator = AllocationPolicy()) 396 : Base(capacity, KeyEqualityMatcher<void*>(), allocator) {} 397}; 398 399typedef PointerTemplateHashMapImpl<DefaultAllocationPolicy> HashMap; 400 401// A hash map for pointer keys and values with an STL-like interface. 402template <class Key, class Value, class MatchFun, class AllocationPolicy> 403class TemplateHashMap 404 : private TemplateHashMapImpl<void*, void*, 405 HashEqualityThenKeyMatcher<void*, MatchFun>, 406 AllocationPolicy> { 407 typedef TemplateHashMapImpl<void*, void*, 408 HashEqualityThenKeyMatcher<void*, MatchFun>, 409 AllocationPolicy> 410 Base; 411 412 public: 413 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 414 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 415 struct value_type { 416 Key* first; 417 Value* second; 418 }; 419 420 class Iterator { 421 public: 422 Iterator& operator++() { 423 entry_ = map_->Next(entry_); 424 return *this; 425 } 426 427 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 428 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 429 430 private: 431 Iterator(const Base* map, typename Base::Entry* entry) 432 : map_(map), entry_(entry) {} 433 434 const Base* map_; 435 typename Base::Entry* entry_; 436 437 friend class TemplateHashMap; 438 }; 439 440 TemplateHashMap(MatchFun match, 441 AllocationPolicy allocator = AllocationPolicy()) 442 : Base(Base::kDefaultHashMapCapacity, 443 HashEqualityThenKeyMatcher<void*, MatchFun>(match), allocator) {} 444 445 Iterator begin() const { return Iterator(this, this->Start()); } 446 Iterator end() const { return Iterator(this, nullptr); } 447 Iterator find(Key* key, bool insert = false, 448 AllocationPolicy allocator = AllocationPolicy()) { 449 if (insert) { 450 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); 451 } 452 return Iterator(this, this->Lookup(key, key->Hash())); 453 } 454}; 455 456} // namespace base 457} // namespace v8 458 459#endif // V8_BASE_HASHMAP_H_ 460