1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #ifndef V8_HASHMAP_H_ 29 #define V8_HASHMAP_H_ 30 31 #include "allocation.h" 32 #include "checks.h" 33 #include "utils.h" 34 35 namespace v8 { 36 namespace internal { 37 38 template<class AllocationPolicy> 39 class TemplateHashMapImpl { 40 public: 41 typedef bool (*MatchFun) (void* key1, void* key2); 42 43 // initial_capacity is the size of the initial hash map; 44 // it must be a power of 2 (and thus must not be 0). 45 TemplateHashMapImpl(MatchFun match, uint32_t initial_capacity = 8); 46 47 ~TemplateHashMapImpl(); 48 49 // HashMap entries are (key, value, hash) triplets. 50 // Some clients may not need to use the value slot 51 // (e.g. implementers of sets, where the key is the value). 52 struct Entry { 53 void* key; 54 void* value; 55 uint32_t hash; // the full hash value for key 56 }; 57 58 // If an entry with matching key is found, Lookup() 59 // returns that entry. If no matching entry is found, 60 // but insert is set, a new entry is inserted with 61 // corresponding key, key hash, and NULL value. 62 // Otherwise, NULL is returned. 63 Entry* Lookup(void* key, uint32_t hash, bool insert); 64 65 // Removes the entry with matching key. 66 void Remove(void* key, uint32_t hash); 67 68 // Empties the hash map (occupancy() == 0). 69 void Clear(); 70 71 // The number of (non-empty) entries in the table. 72 uint32_t occupancy() const { return occupancy_; } 73 74 // The capacity of the table. The implementation 75 // makes sure that occupancy is at most 80% of 76 // the table capacity. 77 uint32_t capacity() const { return capacity_; } 78 79 // Iteration 80 // 81 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { 82 // ... 83 // } 84 // 85 // If entries are inserted during iteration, the effect of 86 // calling Next() is undefined. 87 Entry* Start() const; 88 Entry* Next(Entry* p) const; 89 90 private: 91 MatchFun match_; 92 Entry* map_; 93 uint32_t capacity_; 94 uint32_t occupancy_; 95 96 Entry* map_end() const { return map_ + capacity_; } 97 Entry* Probe(void* key, uint32_t hash); 98 void Initialize(uint32_t capacity); 99 void Resize(); 100 }; 101 102 typedef TemplateHashMapImpl<FreeStoreAllocationPolicy> HashMap; 103 104 template<class P> 105 TemplateHashMapImpl<P>::TemplateHashMapImpl(MatchFun match, 106 uint32_t initial_capacity) { 107 match_ = match; 108 Initialize(initial_capacity); 109 } 110 111 112 template<class P> 113 TemplateHashMapImpl<P>::~TemplateHashMapImpl() { 114 P::Delete(map_); 115 } 116 117 118 template<class P> 119 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Lookup( 120 void* key, uint32_t hash, bool insert) { 121 // Find a matching entry. 122 Entry* p = Probe(key, hash); 123 if (p->key != NULL) { 124 return p; 125 } 126 127 // No entry found; insert one if necessary. 128 if (insert) { 129 p->key = key; 130 p->value = NULL; 131 p->hash = hash; 132 occupancy_++; 133 134 // Grow the map if we reached >= 80% occupancy. 135 if (occupancy_ + occupancy_/4 >= capacity_) { 136 Resize(); 137 p = Probe(key, hash); 138 } 139 140 return p; 141 } 142 143 // No entry found and none inserted. 144 return NULL; 145 } 146 147 148 template<class P> 149 void TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) { 150 // Lookup the entry for the key to remove. 151 Entry* p = Probe(key, hash); 152 if (p->key == NULL) { 153 // Key not found nothing to remove. 154 return; 155 } 156 157 // To remove an entry we need to ensure that it does not create an empty 158 // entry that will cause the search for another entry to stop too soon. If all 159 // the entries between the entry to remove and the next empty slot have their 160 // initial position inside this interval, clearing the entry to remove will 161 // not break the search. If, while searching for the next empty entry, an 162 // entry is encountered which does not have its initial position between the 163 // entry to remove and the position looked at, then this entry can be moved to 164 // the place of the entry to remove without breaking the search for it. The 165 // entry made vacant by this move is now the entry to remove and the process 166 // starts over. 167 // Algorithm from http://en.wikipedia.org/wiki/Open_addressing. 168 169 // This guarantees loop termination as there is at least one empty entry so 170 // eventually the removed entry will have an empty entry after it. 171 ASSERT(occupancy_ < capacity_); 172 173 // p is the candidate entry to clear. q is used to scan forwards. 174 Entry* q = p; // Start at the entry to remove. 175 while (true) { 176 // Move q to the next entry. 177 q = q + 1; 178 if (q == map_end()) { 179 q = map_; 180 } 181 182 // All entries between p and q have their initial position between p and q 183 // and the entry p can be cleared without breaking the search for these 184 // entries. 185 if (q->key == NULL) { 186 break; 187 } 188 189 // Find the initial position for the entry at position q. 190 Entry* r = map_ + (q->hash & (capacity_ - 1)); 191 192 // If the entry at position q has its initial position outside the range 193 // between p and q it can be moved forward to position p and will still be 194 // found. There is now a new candidate entry for clearing. 195 if ((q > p && (r <= p || r > q)) || 196 (q < p && (r <= p && r > q))) { 197 *p = *q; 198 p = q; 199 } 200 } 201 202 // Clear the entry which is allowed to en emptied. 203 p->key = NULL; 204 occupancy_--; 205 } 206 207 208 template<class P> 209 void TemplateHashMapImpl<P>::Clear() { 210 // Mark all entries as empty. 211 const Entry* end = map_end(); 212 for (Entry* p = map_; p < end; p++) { 213 p->key = NULL; 214 } 215 occupancy_ = 0; 216 } 217 218 219 template<class P> 220 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Start() const { 221 return Next(map_ - 1); 222 } 223 224 225 template<class P> 226 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Next(Entry* p) 227 const { 228 const Entry* end = map_end(); 229 ASSERT(map_ - 1 <= p && p < end); 230 for (p++; p < end; p++) { 231 if (p->key != NULL) { 232 return p; 233 } 234 } 235 return NULL; 236 } 237 238 239 template<class P> 240 typename TemplateHashMapImpl<P>::Entry* TemplateHashMapImpl<P>::Probe(void* key, 241 uint32_t hash) { 242 ASSERT(key != NULL); 243 244 ASSERT(IsPowerOf2(capacity_)); 245 Entry* p = map_ + (hash & (capacity_ - 1)); 246 const Entry* end = map_end(); 247 ASSERT(map_ <= p && p < end); 248 249 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. 250 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { 251 p++; 252 if (p >= end) { 253 p = map_; 254 } 255 } 256 257 return p; 258 } 259 260 261 template<class P> 262 void TemplateHashMapImpl<P>::Initialize(uint32_t capacity) { 263 ASSERT(IsPowerOf2(capacity)); 264 map_ = reinterpret_cast<Entry*>(P::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 P> 275 void TemplateHashMapImpl<P>::Resize() { 276 Entry* map = map_; 277 uint32_t n = occupancy_; 278 279 // Allocate larger map. 280 Initialize(capacity_ * 2); 281 282 // Rehash all current entries. 283 for (Entry* p = map; n > 0; p++) { 284 if (p->key != NULL) { 285 Lookup(p->key, p->hash, true)->value = p->value; 286 n--; 287 } 288 } 289 290 // Delete old map. 291 P::Delete(map); 292 } 293 294 295 // A hash map for pointer keys and values with an STL-like interface. 296 template<class Key, class Value, class AllocationPolicy> 297 class TemplateHashMap: private TemplateHashMapImpl<AllocationPolicy> { 298 public: 299 STATIC_ASSERT(sizeof(Key*) == sizeof(void*)); // NOLINT 300 STATIC_ASSERT(sizeof(Value*) == sizeof(void*)); // NOLINT 301 struct value_type { 302 Key* first; 303 Value* second; 304 }; 305 306 class Iterator { 307 public: 308 Iterator& operator++() { 309 entry_ = map_->Next(entry_); 310 return *this; 311 } 312 313 value_type* operator->() { return reinterpret_cast<value_type*>(entry_); } 314 bool operator!=(const Iterator& other) { return entry_ != other.entry_; } 315 316 private: 317 Iterator(const TemplateHashMapImpl<AllocationPolicy>* map, 318 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry) : 319 map_(map), entry_(entry) { } 320 321 const TemplateHashMapImpl<AllocationPolicy>* map_; 322 typename TemplateHashMapImpl<AllocationPolicy>::Entry* entry_; 323 324 friend class TemplateHashMap; 325 }; 326 327 TemplateHashMap( 328 typename TemplateHashMapImpl<AllocationPolicy>::MatchFun match) 329 : TemplateHashMapImpl<AllocationPolicy>(match) { } 330 331 Iterator begin() const { return Iterator(this, this->Start()); } 332 Iterator end() const { return Iterator(this, NULL); } 333 Iterator find(Key* key, bool insert = false) { 334 return Iterator(this, this->Lookup(key, key->Hash(), insert)); 335 } 336 }; 337 338 } } // namespace v8::internal 339 340 #endif // V8_HASHMAP_H_ 341