| OLD | NEW | 
|---|
| 1 // Copyright 2012 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be | 
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. | 
| 4 | 4 | 
| 5 #ifndef V8_HASHMAP_H_ | 5 #ifndef V8_HASHMAP_H_ | 
| 6 #define V8_HASHMAP_H_ | 6 #define V8_HASHMAP_H_ | 
| 7 | 7 | 
| 8 #include "src/allocation.h" | 8 #include "src/allocation.h" | 
| 9 #include "src/base/bits.h" | 9 #include "src/base/bits.h" | 
| 10 #include "src/base/logging.h" | 10 #include "src/base/logging.h" | 
| (...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 44   // If an entry with matching key is found, returns that entry. | 44   // If an entry with matching key is found, returns that entry. | 
| 45   // Otherwise, NULL is returned. | 45   // Otherwise, NULL is returned. | 
| 46   Entry* Lookup(void* key, uint32_t hash) const; | 46   Entry* Lookup(void* key, uint32_t hash) const; | 
| 47 | 47 | 
| 48   // If an entry with matching key is found, returns that entry. | 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 | 49   // If no matching entry is found, a new entry is inserted with | 
| 50   // corresponding key, key hash, and NULL value. | 50   // corresponding key, key hash, and NULL value. | 
| 51   Entry* LookupOrInsert(void* key, uint32_t hash, | 51   Entry* LookupOrInsert(void* key, uint32_t hash, | 
| 52                         AllocationPolicy allocator = AllocationPolicy()); | 52                         AllocationPolicy allocator = AllocationPolicy()); | 
| 53 | 53 | 
| 54   Entry* InsertNew(void* key, uint32_t hash, |  | 
| 55                    AllocationPolicy allocator = AllocationPolicy()); |  | 
| 56 |  | 
| 57   // Removes the entry with matching key. | 54   // Removes the entry with matching key. | 
| 58   // It returns the value of the deleted entry | 55   // It returns the value of the deleted entry | 
| 59   // or null if there is no value for such key. | 56   // or null if there is no value for such key. | 
| 60   void* Remove(void* key, uint32_t hash); | 57   void* Remove(void* key, uint32_t hash); | 
| 61 | 58 | 
| 62   // Empties the hash map (occupancy() == 0). | 59   // Empties the hash map (occupancy() == 0). | 
| 63   void Clear(); | 60   void Clear(); | 
| 64 | 61 | 
| 65   // The number of (non-empty) entries in the table. | 62   // The number of (non-empty) entries in the table. | 
| 66   uint32_t occupancy() const { return occupancy_; } | 63   uint32_t occupancy() const { return occupancy_; } | 
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 125 template <class AllocationPolicy> | 122 template <class AllocationPolicy> | 
| 126 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 123 typename TemplateHashMapImpl<AllocationPolicy>::Entry* | 
| 127 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | 124 TemplateHashMapImpl<AllocationPolicy>::LookupOrInsert( | 
| 128     void* key, uint32_t hash, AllocationPolicy allocator) { | 125     void* key, uint32_t hash, AllocationPolicy allocator) { | 
| 129   // Find a matching entry. | 126   // Find a matching entry. | 
| 130   Entry* p = Probe(key, hash); | 127   Entry* p = Probe(key, hash); | 
| 131   if (p->key != NULL) { | 128   if (p->key != NULL) { | 
| 132     return p; | 129     return p; | 
| 133   } | 130   } | 
| 134 | 131 | 
| 135   return InsertNew(key, hash, allocator); |  | 
| 136 } |  | 
| 137 |  | 
| 138 template <class AllocationPolicy> |  | 
| 139 typename TemplateHashMapImpl<AllocationPolicy>::Entry* |  | 
| 140 TemplateHashMapImpl<AllocationPolicy>::InsertNew(void* key, uint32_t hash, |  | 
| 141                                                  AllocationPolicy allocator) { |  | 
| 142   // Find a matching entry. |  | 
| 143   Entry* p = Probe(key, hash); |  | 
| 144   DCHECK(p->key == NULL); |  | 
| 145 |  | 
| 146   // No entry found; insert one. | 132   // No entry found; insert one. | 
| 147   p->key = key; | 133   p->key = key; | 
| 148   p->value = NULL; | 134   p->value = NULL; | 
| 149   p->hash = hash; | 135   p->hash = hash; | 
| 150   p->order = occupancy_; | 136   p->order = occupancy_; | 
| 151   occupancy_++; | 137   occupancy_++; | 
| 152 | 138 | 
| 153   // Grow the map if we reached >= 80% occupancy. | 139   // Grow the map if we reached >= 80% occupancy. | 
| 154   if (occupancy_ + occupancy_ / 4 >= capacity_) { | 140   if (occupancy_ + occupancy_ / 4 >= capacity_) { | 
| 155     Resize(allocator); | 141     Resize(allocator); | 
| (...skipping 205 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 361       return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 347       return Iterator(this, this->LookupOrInsert(key, key->Hash(), allocator)); | 
| 362     } | 348     } | 
| 363     return Iterator(this, this->Lookup(key, key->Hash())); | 349     return Iterator(this, this->Lookup(key, key->Hash())); | 
| 364   } | 350   } | 
| 365 }; | 351 }; | 
| 366 | 352 | 
| 367 }  // namespace internal | 353 }  // namespace internal | 
| 368 }  // namespace v8 | 354 }  // namespace v8 | 
| 369 | 355 | 
| 370 #endif  // V8_HASHMAP_H_ | 356 #endif  // V8_HASHMAP_H_ | 
| OLD | NEW | 
|---|