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 |