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