OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
11 // with the distribution. | 11 // with the distribution. |
(...skipping 10 matching lines...) Expand all Loading... |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 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. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #ifndef V8_HASHMAP_H_ | 28 #ifndef V8_HASHMAP_H_ |
29 #define V8_HASHMAP_H_ | 29 #define V8_HASHMAP_H_ |
30 | 30 |
31 #include "allocation.h" | 31 #include "allocation.h" |
| 32 #include "checks.h" |
| 33 #include "utils.h" |
32 | 34 |
33 namespace v8 { | 35 namespace v8 { |
34 namespace internal { | 36 namespace internal { |
35 | 37 |
36 | 38 template<class AllocationPolicy> |
37 // Allocator defines the memory allocator interface | 39 class TemplateHashMap { |
38 // used by HashMap and implements a default allocator. | |
39 class Allocator BASE_EMBEDDED { | |
40 public: | 40 public: |
41 virtual ~Allocator() {} | |
42 virtual void* New(size_t size) { return Malloced::New(size); } | |
43 virtual void Delete(void* p) { Malloced::Delete(p); } | |
44 }; | |
45 | |
46 | |
47 class HashMap { | |
48 public: | |
49 static Allocator* DefaultAllocator; | |
50 | |
51 typedef bool (*MatchFun) (void* key1, void* key2); | 41 typedef bool (*MatchFun) (void* key1, void* key2); |
52 | 42 |
53 // initial_capacity is the size of the initial hash map; | 43 // initial_capacity is the size of the initial hash map; |
54 // it must be a power of 2 (and thus must not be 0). | 44 // it must be a power of 2 (and thus must not be 0). |
55 explicit HashMap(MatchFun match, | 45 TemplateHashMap(MatchFun match, uint32_t initial_capacity = 8); |
56 Allocator* allocator = DefaultAllocator, | |
57 uint32_t initial_capacity = 8); | |
58 | 46 |
59 ~HashMap(); | 47 ~TemplateHashMap(); |
60 | 48 |
61 // HashMap entries are (key, value, hash) triplets. | 49 // HashMap entries are (key, value, hash) triplets. |
62 // Some clients may not need to use the value slot | 50 // Some clients may not need to use the value slot |
63 // (e.g. implementers of sets, where the key is the value). | 51 // (e.g. implementers of sets, where the key is the value). |
64 struct Entry { | 52 struct Entry { |
65 void* key; | 53 void* key; |
66 void* value; | 54 void* value; |
67 uint32_t hash; // the full hash value for key | 55 uint32_t hash; // the full hash value for key |
68 }; | 56 }; |
69 | 57 |
(...skipping 23 matching lines...) Expand all Loading... |
93 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { | 81 // for (Entry* p = map.Start(); p != NULL; p = map.Next(p)) { |
94 // ... | 82 // ... |
95 // } | 83 // } |
96 // | 84 // |
97 // If entries are inserted during iteration, the effect of | 85 // If entries are inserted during iteration, the effect of |
98 // calling Next() is undefined. | 86 // calling Next() is undefined. |
99 Entry* Start() const; | 87 Entry* Start() const; |
100 Entry* Next(Entry* p) const; | 88 Entry* Next(Entry* p) const; |
101 | 89 |
102 private: | 90 private: |
103 Allocator* allocator_; | |
104 MatchFun match_; | 91 MatchFun match_; |
105 Entry* map_; | 92 Entry* map_; |
106 uint32_t capacity_; | 93 uint32_t capacity_; |
107 uint32_t occupancy_; | 94 uint32_t occupancy_; |
108 | 95 |
109 Entry* map_end() const { return map_ + capacity_; } | 96 Entry* map_end() const { return map_ + capacity_; } |
110 Entry* Probe(void* key, uint32_t hash); | 97 Entry* Probe(void* key, uint32_t hash); |
111 void Initialize(uint32_t capacity); | 98 void Initialize(uint32_t capacity); |
112 void Resize(); | 99 void Resize(); |
113 }; | 100 }; |
114 | 101 |
| 102 typedef TemplateHashMap<FreeStoreAllocationPolicy> HashMap; |
| 103 |
| 104 template<class P> |
| 105 TemplateHashMap<P>::TemplateHashMap(MatchFun match, |
| 106 uint32_t initial_capacity) { |
| 107 match_ = match; |
| 108 Initialize(initial_capacity); |
| 109 } |
| 110 |
| 111 |
| 112 template<class P> |
| 113 TemplateHashMap<P>::~TemplateHashMap() { |
| 114 P::Delete(map_); |
| 115 } |
| 116 |
| 117 |
| 118 template<class P> |
| 119 struct TemplateHashMap<P>::Entry* TemplateHashMap<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 TemplateHashMap<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 TemplateHashMap<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 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Start() const { |
| 221 return Next(map_ - 1); |
| 222 } |
| 223 |
| 224 |
| 225 template<class P> |
| 226 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Next(Entry* p) const { |
| 227 const Entry* end = map_end(); |
| 228 ASSERT(map_ - 1 <= p && p < end); |
| 229 for (p++; p < end; p++) { |
| 230 if (p->key != NULL) { |
| 231 return p; |
| 232 } |
| 233 } |
| 234 return NULL; |
| 235 } |
| 236 |
| 237 |
| 238 template<class P> |
| 239 struct TemplateHashMap<P>::Entry* TemplateHashMap<P>::Probe(void* key, |
| 240 uint32_t hash) { |
| 241 ASSERT(key != NULL); |
| 242 |
| 243 ASSERT(IsPowerOf2(capacity_)); |
| 244 Entry* p = map_ + (hash & (capacity_ - 1)); |
| 245 const Entry* end = map_end(); |
| 246 ASSERT(map_ <= p && p < end); |
| 247 |
| 248 ASSERT(occupancy_ < capacity_); // Guarantees loop termination. |
| 249 while (p->key != NULL && (hash != p->hash || !match_(key, p->key))) { |
| 250 p++; |
| 251 if (p >= end) { |
| 252 p = map_; |
| 253 } |
| 254 } |
| 255 |
| 256 return p; |
| 257 } |
| 258 |
| 259 |
| 260 template<class P> |
| 261 void TemplateHashMap<P>::Initialize(uint32_t capacity) { |
| 262 ASSERT(IsPowerOf2(capacity)); |
| 263 map_ = reinterpret_cast<Entry*>(P::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 P> |
| 274 void TemplateHashMap<P>::Resize() { |
| 275 Entry* map = map_; |
| 276 uint32_t n = occupancy_; |
| 277 |
| 278 // Allocate larger map. |
| 279 Initialize(capacity_ * 2); |
| 280 |
| 281 // Rehash all current entries. |
| 282 for (Entry* p = map; n > 0; p++) { |
| 283 if (p->key != NULL) { |
| 284 Lookup(p->key, p->hash, true)->value = p->value; |
| 285 n--; |
| 286 } |
| 287 } |
| 288 |
| 289 // Delete old map. |
| 290 P::Delete(map); |
| 291 } |
115 | 292 |
116 } } // namespace v8::internal | 293 } } // namespace v8::internal |
117 | 294 |
118 #endif // V8_HASHMAP_H_ | 295 #endif // V8_HASHMAP_H_ |
OLD | NEW |