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