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#ifndef V8_HASHMAP_H_ 6#define V8_HASHMAP_H_ 7 8#include "src/allocation.h" 9#include "src/base/bits.h" 10#include "src/base/logging.h" 11#include "src/utils.h" 12 13namespace v8 { 14namespace internal { 15 16template<class AllocationPolicy> 17class TemplateHashMapImpl { 18 public: 19 typedef bool (*MatchFun) (void* key1, void* key2); 20 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; 25 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()); 31 32 ~TemplateHashMapImpl(); 33 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). 37 struct Entry { 38 void* key; 39 void* value; 40 uint32_t hash; // The full hash value for key 41 int order; // If you never remove entries this is the insertion order. 42 }; 43 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; 47 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()); 53 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); 58 59 // Empties the hash map (occupancy() == 0). 60 void Clear(); 61 62 // The number of (non-empty) entries in the table. 63 uint32_t occupancy() const { return occupancy_; } 64 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_; } 69 70 // Iteration 71 // 72 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 73 // ... 74 // } 75 // 76 // If entries are inserted during iteration, the effect of 77 // calling Next() is undefined. 78 Entry* Start() const; 79 Entry* Next(Entry* p) const; 80 81 // Some match functions defined for convenience. 82 static bool PointersMatch(void* key1, void* key2) { 83 return key1 == key2; 84 } 85 86 private: 87 MatchFun match_; 88 Entry* map_; 89 uint32_t capacity_; 90 uint32_t occupancy_; 91 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); 96}; 97 98typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; 99 100template<class AllocationPolicy> 101TemplateHashMapImpl<AllocationPolicy>::TemplateHashMapImpl( 102 MatchFun match, uint32_t initial_capacity, AllocationPolicy allocator) { 103 match_ = match; 104 Initialize(initial_capacity, allocator); 105} 106 107 108template<class AllocationPolicy> 109TemplateHashMapImpl<AllocationPolicy>::~TemplateHashMapImpl() { 110 AllocationPolicy::Delete(map_); 111} 112 113 114template <class AllocationPolicy> 115typename TemplateHashMapImpl<AllocationPolicy>::Entry* 116TemplateHashMapImpl<AllocationPolicy>::Lookup(void* key, uint32_t hash) const { 117 Entry* p = Probe(key, hash); 118 return p->key != NULL ? p : NULL; 119} 120 121 122template <class AllocationPolicy> 123typename TemplateHashMapImpl<AllocationPolicy>::Entry* 124TemplateHashMapImpl<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) { 129 return p; 130 } 131 132 // No entry found; insert one. 133 p->key = key; 134 p->value = NULL; 135 p->hash = hash; 136 p->order = occupancy_; 137 occupancy_++; 138 139 // Grow the map if we reached >= 80% occupancy. 140 if (occupancy_ + occupancy_ / 4 >= capacity_) { 141 Resize(allocator); 142 p = Probe(key, hash); 143 } 144 145 return p; 146} 147 148 149template<class AllocationPolicy> 150void* 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. 155 return NULL; 156 } 157 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 168 // starts over. 169 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 170 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_); 174 175 // p is the candidate entry to clear. q is used to scan forwards. 176 Entry* q = p; // Start at the entry to remove. 177 while (true) { 178 // Move q to the next entry. 179 q = q + 1; 180 if (q == map_end()) { 181 q = map_; 182 } 183 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 186 // entries. 187 if (q->key == NULL) { 188 break; 189 } 190 191 // Find the initial position for the entry at position q. 192 Entry* r = map_ + (q->hash & (capacity_ - 1)); 193 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))) { 199 *p = *q; 200 p = q; 201 } 202 } 203 204 // Clear the entry which is allowed to en emptied. 205 p->key = NULL; 206 occupancy_--; 207 return value; 208} 209 210 211template<class AllocationPolicy> 212void TemplateHashMapImpl<AllocationPolicy>::Clear() { 213 // Mark all entries as empty. 214 const Entry* end = map_end(); 215 for (Entry* p = map_; p < end; p++) { 216 p->key = NULL; 217 } 218 occupancy_ = 0; 219} 220 221 222template<class AllocationPolicy> 223typename TemplateHashMapImpl<AllocationPolicy>::Entry* 224 TemplateHashMapImpl<AllocationPolicy>::Start() const { 225 return Next(map_ - 1); 226} 227 228 229template<class AllocationPolicy> 230typename 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) { 236 return p; 237 } 238 } 239 return NULL; 240} 241 242 243template <class AllocationPolicy> 244typename TemplateHashMapImpl<AllocationPolicy>::Entry* 245TemplateHashMapImpl<AllocationPolicy>::Probe(void* key, uint32_t hash) const { 246 DCHECK(key != NULL); 247 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); 252 253 DCHECK(occupancy_ < capacity_); // Guarantees loop termination. 254 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { 255 p++; 256 if (p >= end) { 257 p = map_; 258 } 259 } 260 261 return p; 262} 263 264 265template<class AllocationPolicy> 266void 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))); 270 if (map_ == NULL) { 271 v8::internal::FatalProcessOutOfMemory("HashMap::Initialize"); 272 return; 273 } 274 capacity_ = capacity; 275 Clear(); 276} 277 278 279template<class AllocationPolicy> 280void TemplateHashMapImpl<AllocationPolicy>::Resize(AllocationPolicy allocator) { 281 Entry* map = map_; 282 uint32_t n = occupancy_; 283 284 // Allocate larger map. 285 Initialize(capacity_ * 2, allocator); 286 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; 293 n--; 294 } 295 } 296 297 // Delete old map. 298 AllocationPolicy::Delete(map); 299} 300 301 302// A hash map for pointer keys and values with an STL-like interface. 303template<class Key, class Value, class AllocationPolicy> 304class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { 305 public: 306 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 307 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 308 struct value_type { 309 Key* first; 310 Value* second; 311 }; 312 313 class Iterator { 314 public: 315 Iterator& operator++() { 316 entry_ = map_->Next(entry_); 317 return *this; 318 } 319 320 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 321 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 322 323 private: 324 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, 325 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : 326 map_(map), entry_(entry) { } 327 328 const TemplateHashMapImpl<AllocationPolicy>* map_; 329 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; 330 331 friend class TemplateHashMap; 332 }; 333 334 TemplateHashMap( 335 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match, 336 AllocationPolicy allocator = AllocationPolicy()) 337 : TemplateHashMapImpl<AllocationPolicy>( 338 match, 339 TemplateHashMapImpl<AllocationPolicy>::kDefaultHashMapCapacity, 340 allocator) { } 341 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()) { 346 if (insert) { 347 return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); 348 } 349 return Iterator(this, this->Lookup(key, key->Hash())); 350 } 351}; 352 353} // namespace internal 354} // namespace v8 355 356#endif // V8_HASHMAP_H_ 357