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