OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #ifndef VM_HASH_TABLE_H_ | 5 #ifndef VM_HASH_TABLE_H_ |
6 #define VM_HASH_TABLE_H_ | 6 #define VM_HASH_TABLE_H_ |
7 | 7 |
8 // Temporarily used when sorting the indices in EnumIndexHashTable. | 8 // Temporarily used when sorting the indices in EnumIndexHashTable. |
9 // TODO(koda): Remove these dependencies before using in production. | 9 // TODO(koda): Remove these dependencies before using in production. |
10 #include <map> | 10 #include <map> |
(...skipping 25 matching lines...) Expand all Loading... |
36 // - LinkedListHashMap | 36 // - LinkedListHashMap |
37 // - UnorderedHashSet | 37 // - UnorderedHashSet |
38 // - EnumIndexHashSet | 38 // - EnumIndexHashSet |
39 // - LinkedListHashSet | 39 // - LinkedListHashSet |
40 // Each of these can be finally specialized with KeyTraits to support any set of | 40 // Each of these can be finally specialized with KeyTraits to support any set of |
41 // lookup key types (e.g., look up a char* in a set of String objects), and | 41 // lookup key types (e.g., look up a char* in a set of String objects), and |
42 // any equality and hash code computation. | 42 // any equality and hash code computation. |
43 // | 43 // |
44 // The classes all wrap an Array handle, and metods like HashSet::Insert can | 44 // The classes all wrap an Array handle, and metods like HashSet::Insert can |
45 // trigger growth into a new RawArray, updating the handle. Debug mode asserts | 45 // trigger growth into a new RawArray, updating the handle. Debug mode asserts |
46 // that 'Release' was called to get the final RawArray before destruction. | 46 // that 'Release' was called once to access the final array before destruction. |
47 // | 47 // |
48 // Example use: | 48 // Example use: |
49 // typedef UnorderedHashMap<FooTraits> ResolvedNamesMap; | 49 // typedef UnorderedHashMap<FooTraits> FooMap; |
50 // ... | 50 // ... |
51 // ResolvedNamesMap cache(Array::Handle(resolved_names())); | 51 // FooMap cache(get_foo_cache()); |
52 // cache.UpdateOrInsert(name0, obj0); | 52 // cache.UpdateOrInsert(name0, obj0); |
53 // cache.UpdateOrInsert(name1, obj1); | 53 // cache.UpdateOrInsert(name1, obj1); |
54 // ... | 54 // ... |
55 // StorePointer(&raw_ptr()->resolved_names_, cache.Release()); | 55 // set_foo_cache(cache.Release()); |
| 56 // |
| 57 // If you *know* that no mutating operations were called, you can optimize: |
| 58 // ... |
| 59 // obj ^= cache.GetOrNull(name); |
| 60 // ASSERT(cache.Release().raw() == get_foo_cache()); |
56 // | 61 // |
57 // TODO(koda): When exposing these to Dart code, document and assert that | 62 // TODO(koda): When exposing these to Dart code, document and assert that |
58 // KeyTraits methods must not run Dart code (since the C++ code doesn't check | 63 // KeyTraits methods must not run Dart code (since the C++ code doesn't check |
59 // for concurrent modification). | 64 // for concurrent modification). |
60 | 65 |
61 | 66 |
62 // Open-addressing hash table template using a RawArray as backing storage. | 67 // Open-addressing hash table template using a RawArray as backing storage. |
63 // | 68 // |
64 // The elements of the array are partitioned into entries: | 69 // The elements of the array are partitioned into entries: |
65 // [ header | metadata | entry0 | entry1 | ... | entryN ] | 70 // [ header | metadata | entry0 | entry1 | ... | entryN ] |
66 // Each entry contains a key, followed by zero or more payload components, | 71 // Each entry contains a key, followed by zero or more payload components, |
67 // and has 3 possible states: unused, occupied, or deleted. | 72 // and has 3 possible states: unused, occupied, or deleted. |
68 // The header tracks the number of entries in each state. | 73 // The header tracks the number of entries in each state. |
69 // Any object except Object::sentinel() and Object::transition_sentinel() | 74 // Any object except Object::sentinel() and Object::transition_sentinel() |
70 // may be stored as a key. Any object may be stored in a payload. | 75 // may be stored as a key. Any object may be stored in a payload. |
71 // | 76 // |
72 // Parameters | 77 // Parameters |
73 // KeyTraits: defines static methods | 78 // KeyTraits: defines static methods |
74 // bool IsMatch(const Key& key, const Object& obj) and | 79 // bool IsMatch(const Key& key, const Object& obj) and |
75 // uword Hash(const Key& key) for any number of desired lookup key types. | 80 // uword Hash(const Key& key) for any number of desired lookup key types. |
76 // kPayloadSize: number of components of the payload in each entry. | 81 // kPayloadSize: number of components of the payload in each entry. |
77 // kMetaDataSize: number of elements reserved (e.g., for iteration order data). | 82 // kMetaDataSize: number of elements reserved (e.g., for iteration order data). |
78 template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize> | 83 template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize> |
79 class HashTable : public ValueObject { | 84 class HashTable : public ValueObject { |
80 public: | 85 public: |
81 typedef KeyTraits Traits; | 86 typedef KeyTraits Traits; |
82 explicit HashTable(Array& data) : data_(data) {} | 87 // Uses 'isolate' for handle allocation. 'Release' must be called at the end |
| 88 // to obtain the final table after potential growth/shrinkage. |
| 89 HashTable(Isolate* isolate, RawArray* data) |
| 90 : isolate_(isolate), data_(&Array::Handle(isolate_, data)) {} |
| 91 // Like above, except uses current isolate. |
| 92 explicit HashTable(RawArray* data) |
| 93 : isolate_(Isolate::Current()), data_(&Array::Handle(isolate_, data)) {} |
83 | 94 |
84 RawArray* Release() { | 95 Array& Release() { |
85 ASSERT(!data_.IsNull()); | 96 ASSERT(data_ != NULL); |
86 RawArray* array = data_.raw(); | 97 Array* result = data_; |
87 data_ = Array::null(); | 98 // Ensure that no methods are called after 'Release'. |
88 return array; | 99 data_ = NULL; |
| 100 return *result; |
89 } | 101 } |
90 | 102 |
91 ~HashTable() { | 103 ~HashTable() { |
92 ASSERT(data_.IsNull()); | 104 // Ensure that 'Release' was called. |
| 105 ASSERT(data_ == NULL); |
93 } | 106 } |
94 | 107 |
95 // Returns a backing storage size such that 'num_occupied' distinct keys can | 108 // Returns a backing storage size such that 'num_occupied' distinct keys can |
96 // be inserted into the table. | 109 // be inserted into the table. |
97 static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) { | 110 static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) { |
98 // The current invariant requires at least one unoccupied entry. | 111 // The current invariant requires at least one unoccupied entry. |
99 // TODO(koda): Adjust if moving to quadratic probing. | 112 // TODO(koda): Adjust if moving to quadratic probing. |
100 intptr_t num_entries = num_occupied + 1; | 113 intptr_t num_entries = num_occupied + 1; |
101 return kFirstKeyIndex + (kEntrySize * num_entries); | 114 return kFirstKeyIndex + (kEntrySize * num_entries); |
102 } | 115 } |
103 | 116 |
104 // Initializes an empty table. | 117 // Initializes an empty table. |
105 void Initialize() const { | 118 void Initialize() const { |
106 ASSERT(data_.Length() >= ArrayLengthForNumOccupied(0)); | 119 ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0)); |
107 Smi& zero = Smi::Handle(Smi::New(0)); | 120 Smi& zero = Smi::Handle(isolate(), Smi::New(0)); |
108 data_.SetAt(kOccupiedEntriesIndex, zero); | 121 data_->SetAt(kOccupiedEntriesIndex, zero); |
109 data_.SetAt(kDeletedEntriesIndex, zero); | 122 data_->SetAt(kDeletedEntriesIndex, zero); |
110 for (intptr_t i = kHeaderSize; i < data_.Length(); ++i) { | 123 for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) { |
111 data_.SetAt(i, Object::sentinel()); | 124 data_->SetAt(i, Object::sentinel()); |
112 } | 125 } |
113 } | 126 } |
114 | 127 |
115 // Returns whether 'key' matches any key in the table. | 128 // Returns whether 'key' matches any key in the table. |
116 template<typename Key> | 129 template<typename Key> |
117 bool ContainsKey(const Key& key) const { | 130 bool ContainsKey(const Key& key) const { |
118 return FindKey(key) != -1; | 131 return FindKey(key) != -1; |
119 } | 132 } |
120 | 133 |
121 // Returns the entry that matches 'key', or -1 if none exists. | 134 // Returns the entry that matches 'key', or -1 if none exists. |
122 template<typename Key> | 135 template<typename Key> |
123 intptr_t FindKey(const Key& key) const { | 136 intptr_t FindKey(const Key& key) const { |
124 ASSERT(NumOccupied() < NumEntries()); | 137 ASSERT(NumOccupied() < NumEntries()); |
125 // TODO(koda): Add salt. | 138 // TODO(koda): Add salt. |
126 intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries(); | 139 intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries(); |
127 Object& obj = Object::Handle(); | 140 Object& obj = Object::Handle(isolate()); |
128 // TODO(koda): Consider quadratic probing. | 141 // TODO(koda): Consider quadratic probing. |
129 for (; ; probe = (probe + 1) % NumEntries()) { | 142 for (; ; probe = (probe + 1) % NumEntries()) { |
130 if (IsUnused(probe)) { | 143 if (IsUnused(probe)) { |
131 return -1; | 144 return -1; |
132 } else if (IsDeleted(probe)) { | 145 } else if (IsDeleted(probe)) { |
133 continue; | 146 continue; |
134 } else { | 147 } else { |
135 obj = GetKey(probe); | 148 obj = GetKey(probe); |
136 if (KeyTraits::IsMatch(key, obj)) { | 149 if (KeyTraits::IsMatch(key, obj)) { |
137 return probe; | 150 return probe; |
138 } | 151 } |
139 } | 152 } |
140 } | 153 } |
141 UNREACHABLE(); | 154 UNREACHABLE(); |
142 return -1; | 155 return -1; |
143 } | 156 } |
144 | 157 |
145 // Sets *entry to either: | 158 // Sets *entry to either: |
146 // - an occupied entry matching 'key', and returns true, or | 159 // - an occupied entry matching 'key', and returns true, or |
147 // - an unused/deleted entry where a matching key may be inserted, | 160 // - an unused/deleted entry where a matching key may be inserted, |
148 // and returns false. | 161 // and returns false. |
149 template<typename Key> | 162 template<typename Key> |
150 bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const { | 163 bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const { |
151 ASSERT(entry != NULL); | 164 ASSERT(entry != NULL); |
152 ASSERT(NumOccupied() < NumEntries()); | 165 ASSERT(NumOccupied() < NumEntries()); |
153 intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries(); | 166 intptr_t probe = static_cast<uword>(KeyTraits::Hash(key)) % NumEntries(); |
154 Object& obj = Object::Handle(); | 167 Object& obj = Object::Handle(isolate()); |
155 intptr_t deleted = -1; | 168 intptr_t deleted = -1; |
156 // TODO(koda): Consider quadratic probing. | 169 // TODO(koda): Consider quadratic probing. |
157 for (; ; probe = (probe + 1) % NumEntries()) { | 170 for (; ; probe = (probe + 1) % NumEntries()) { |
158 if (IsUnused(probe)) { | 171 if (IsUnused(probe)) { |
159 *entry = (deleted != -1) ? deleted : probe; | 172 *entry = (deleted != -1) ? deleted : probe; |
160 return false; | 173 return false; |
161 } else if (IsDeleted(probe)) { | 174 } else if (IsDeleted(probe)) { |
162 if (deleted == -1) { | 175 if (deleted == -1) { |
163 deleted = probe; | 176 deleted = probe; |
164 } | 177 } |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
198 bool IsDeleted(intptr_t entry) const { | 211 bool IsDeleted(intptr_t entry) const { |
199 return InternalGetKey(entry) == Object::transition_sentinel().raw(); | 212 return InternalGetKey(entry) == Object::transition_sentinel().raw(); |
200 } | 213 } |
201 | 214 |
202 RawObject* GetKey(intptr_t entry) const { | 215 RawObject* GetKey(intptr_t entry) const { |
203 ASSERT(IsOccupied(entry)); | 216 ASSERT(IsOccupied(entry)); |
204 return InternalGetKey(entry); | 217 return InternalGetKey(entry); |
205 } | 218 } |
206 RawObject* GetPayload(intptr_t entry, intptr_t component) const { | 219 RawObject* GetPayload(intptr_t entry, intptr_t component) const { |
207 ASSERT(IsOccupied(entry)); | 220 ASSERT(IsOccupied(entry)); |
208 return data_.At(PayloadIndex(entry, component)); | 221 return data_->At(PayloadIndex(entry, component)); |
209 } | 222 } |
210 void UpdatePayload(intptr_t entry, | 223 void UpdatePayload(intptr_t entry, |
211 intptr_t component, | 224 intptr_t component, |
212 const Object& value) const { | 225 const Object& value) const { |
213 ASSERT(IsOccupied(entry)); | 226 ASSERT(IsOccupied(entry)); |
214 ASSERT(0 <= component && component < kPayloadSize); | 227 ASSERT(0 <= component && component < kPayloadSize); |
215 data_.SetAt(PayloadIndex(entry, component), value); | 228 data_->SetAt(PayloadIndex(entry, component), value); |
216 } | 229 } |
217 // Deletes both the key and payload of the specified entry. | 230 // Deletes both the key and payload of the specified entry. |
218 void DeleteEntry(intptr_t entry) const { | 231 void DeleteEntry(intptr_t entry) const { |
219 ASSERT(IsOccupied(entry)); | 232 ASSERT(IsOccupied(entry)); |
220 for (intptr_t i = 0; i < kPayloadSize; ++i) { | 233 for (intptr_t i = 0; i < kPayloadSize; ++i) { |
221 UpdatePayload(entry, i, Object::transition_sentinel()); | 234 UpdatePayload(entry, i, Object::transition_sentinel()); |
222 } | 235 } |
223 InternalSetKey(entry, Object::transition_sentinel()); | 236 InternalSetKey(entry, Object::transition_sentinel()); |
224 AdjustSmiValueAt(kOccupiedEntriesIndex, -1); | 237 AdjustSmiValueAt(kOccupiedEntriesIndex, -1); |
225 AdjustSmiValueAt(kDeletedEntriesIndex, 1); | 238 AdjustSmiValueAt(kDeletedEntriesIndex, 1); |
226 } | 239 } |
227 intptr_t NumEntries() const { | 240 intptr_t NumEntries() const { |
228 return (data_.Length() - kFirstKeyIndex) / kEntrySize; | 241 return (data_->Length() - kFirstKeyIndex) / kEntrySize; |
229 } | 242 } |
230 intptr_t NumUnused() const { | 243 intptr_t NumUnused() const { |
231 return NumEntries() - NumOccupied() - NumDeleted(); | 244 return NumEntries() - NumOccupied() - NumDeleted(); |
232 } | 245 } |
233 intptr_t NumOccupied() const { | 246 intptr_t NumOccupied() const { |
234 return GetSmiValueAt(kOccupiedEntriesIndex); | 247 return GetSmiValueAt(kOccupiedEntriesIndex); |
235 } | 248 } |
236 intptr_t NumDeleted() const { | 249 intptr_t NumDeleted() const { |
237 return GetSmiValueAt(kDeletedEntriesIndex); | 250 return GetSmiValueAt(kDeletedEntriesIndex); |
238 } | 251 } |
(...skipping 10 matching lines...) Expand all Loading... |
249 ASSERT(0 <= entry && entry < NumEntries()); | 262 ASSERT(0 <= entry && entry < NumEntries()); |
250 return kFirstKeyIndex + (kEntrySize * entry); | 263 return kFirstKeyIndex + (kEntrySize * entry); |
251 } | 264 } |
252 | 265 |
253 intptr_t PayloadIndex(intptr_t entry, intptr_t component) const { | 266 intptr_t PayloadIndex(intptr_t entry, intptr_t component) const { |
254 ASSERT(0 <= component && component < kPayloadSize); | 267 ASSERT(0 <= component && component < kPayloadSize); |
255 return KeyIndex(entry) + 1 + component; | 268 return KeyIndex(entry) + 1 + component; |
256 } | 269 } |
257 | 270 |
258 RawObject* InternalGetKey(intptr_t entry) const { | 271 RawObject* InternalGetKey(intptr_t entry) const { |
259 return data_.At(KeyIndex(entry)); | 272 return data_->At(KeyIndex(entry)); |
260 } | 273 } |
261 | 274 |
262 void InternalSetKey(intptr_t entry, const Object& key) const { | 275 void InternalSetKey(intptr_t entry, const Object& key) const { |
263 data_.SetAt(KeyIndex(entry), key); | 276 data_->SetAt(KeyIndex(entry), key); |
264 } | 277 } |
265 | 278 |
266 intptr_t GetSmiValueAt(intptr_t index) const { | 279 intptr_t GetSmiValueAt(intptr_t index) const { |
267 ASSERT(Object::Handle(data_.At(index)).IsSmi()); | 280 ASSERT(Object::Handle(isolate(), data_->At(index)).IsSmi()); |
268 return Smi::Value(Smi::RawCast(data_.At(index))); | 281 return Smi::Value(Smi::RawCast(data_->At(index))); |
269 } | 282 } |
270 | 283 |
271 void SetSmiValueAt(intptr_t index, intptr_t value) const { | 284 void SetSmiValueAt(intptr_t index, intptr_t value) const { |
272 const Smi& smi = Smi::Handle(Smi::New(value)); | 285 const Smi& smi = Smi::Handle(isolate(), Smi::New(value)); |
273 data_.SetAt(index, smi); | 286 data_->SetAt(index, smi); |
274 } | 287 } |
275 | 288 |
276 void AdjustSmiValueAt(intptr_t index, intptr_t delta) const { | 289 void AdjustSmiValueAt(intptr_t index, intptr_t delta) const { |
277 SetSmiValueAt(index, (GetSmiValueAt(index) + delta)); | 290 SetSmiValueAt(index, (GetSmiValueAt(index) + delta)); |
278 } | 291 } |
279 | 292 |
280 Array& data_; | 293 Isolate* isolate() const { return isolate_; } |
| 294 |
| 295 Isolate* isolate_; |
| 296 // This is a pointer rather than a reference, to enable Release nulling it, |
| 297 // preventing post-Release modification. |
| 298 Array* data_; |
281 | 299 |
282 friend class HashTables; | 300 friend class HashTables; |
283 }; | 301 }; |
284 | 302 |
285 | 303 |
286 // Table with unspecified iteration order. No payload overhead or metadata. | 304 // Table with unspecified iteration order. No payload overhead or metadata. |
287 template<typename KeyTraits, intptr_t kUserPayloadSize> | 305 template<typename KeyTraits, intptr_t kUserPayloadSize> |
288 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> { | 306 class UnorderedHashTable : public HashTable<KeyTraits, kUserPayloadSize, 0> { |
289 public: | 307 public: |
290 typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable; | 308 typedef HashTable<KeyTraits, kUserPayloadSize, 0> BaseTable; |
291 static const intptr_t kPayloadSize = kUserPayloadSize; | 309 static const intptr_t kPayloadSize = kUserPayloadSize; |
292 explicit UnorderedHashTable(Array& data) : BaseTable(data) {} | 310 explicit UnorderedHashTable(RawArray* data) : BaseTable(data) {} |
| 311 UnorderedHashTable(Isolate* isolate, RawArray* data) |
| 312 : BaseTable(isolate, data) {} |
293 // Note: Does not check for concurrent modification. | 313 // Note: Does not check for concurrent modification. |
294 class Iterator { | 314 class Iterator { |
295 public: | 315 public: |
296 explicit Iterator(const UnorderedHashTable* table) | 316 explicit Iterator(const UnorderedHashTable* table) |
297 : table_(table), entry_(-1) {} | 317 : table_(table), entry_(-1) {} |
298 bool MoveNext() { | 318 bool MoveNext() { |
299 while (entry_ < (table_->NumEntries() - 1)) { | 319 while (entry_ < (table_->NumEntries() - 1)) { |
300 ++entry_; | 320 ++entry_; |
301 if (table_->IsOccupied(entry_)) { | 321 if (table_->IsOccupied(entry_)) { |
302 return true; | 322 return true; |
(...skipping 16 matching lines...) Expand all Loading... |
319 | 339 |
320 // Table with insertion order, using one payload component for the enumeration | 340 // Table with insertion order, using one payload component for the enumeration |
321 // index, and one metadata element for the next enumeration index. | 341 // index, and one metadata element for the next enumeration index. |
322 template<typename KeyTraits, intptr_t kUserPayloadSize> | 342 template<typename KeyTraits, intptr_t kUserPayloadSize> |
323 class EnumIndexHashTable | 343 class EnumIndexHashTable |
324 : public HashTable<KeyTraits, kUserPayloadSize + 1, 1> { | 344 : public HashTable<KeyTraits, kUserPayloadSize + 1, 1> { |
325 public: | 345 public: |
326 typedef HashTable<KeyTraits, kUserPayloadSize + 1, 1> BaseTable; | 346 typedef HashTable<KeyTraits, kUserPayloadSize + 1, 1> BaseTable; |
327 static const intptr_t kPayloadSize = kUserPayloadSize; | 347 static const intptr_t kPayloadSize = kUserPayloadSize; |
328 static const intptr_t kNextEnumIndex = BaseTable::kMetaDataIndex; | 348 static const intptr_t kNextEnumIndex = BaseTable::kMetaDataIndex; |
329 explicit EnumIndexHashTable(Array& data) : BaseTable(data) {} | 349 EnumIndexHashTable(Isolate* isolate, RawArray* data) |
| 350 : BaseTable(isolate, data) {} |
| 351 explicit EnumIndexHashTable(RawArray* data) : BaseTable(data) {} |
330 // Note: Does not check for concurrent modification. | 352 // Note: Does not check for concurrent modification. |
331 class Iterator { | 353 class Iterator { |
332 public: | 354 public: |
333 explicit Iterator(const EnumIndexHashTable* table) : index_(-1) { | 355 explicit Iterator(const EnumIndexHashTable* table) : index_(-1) { |
334 // TODO(koda): Use GrowableArray after adding stateful comparator support. | 356 // TODO(koda): Use GrowableArray after adding stateful comparator support. |
335 std::map<intptr_t, intptr_t> enum_to_entry; | 357 std::map<intptr_t, intptr_t> enum_to_entry; |
336 for (intptr_t i = 0; i < table->NumEntries(); ++i) { | 358 for (intptr_t i = 0; i < table->NumEntries(); ++i) { |
337 if (table->IsOccupied(i)) { | 359 if (table->IsOccupied(i)) { |
338 intptr_t enum_index = | 360 intptr_t enum_index = |
339 table->GetSmiValueAt(table->PayloadIndex(i, kPayloadSize)); | 361 table->GetSmiValueAt(table->PayloadIndex(i, kPayloadSize)); |
(...skipping 22 matching lines...) Expand all Loading... |
362 std::vector<intptr_t> entries_; | 384 std::vector<intptr_t> entries_; |
363 }; | 385 }; |
364 | 386 |
365 void Initialize() const { | 387 void Initialize() const { |
366 BaseTable::Initialize(); | 388 BaseTable::Initialize(); |
367 BaseTable::SetSmiValueAt(kNextEnumIndex, 0); | 389 BaseTable::SetSmiValueAt(kNextEnumIndex, 0); |
368 } | 390 } |
369 | 391 |
370 void InsertKey(intptr_t entry, const Object& key) const { | 392 void InsertKey(intptr_t entry, const Object& key) const { |
371 BaseTable::InsertKey(entry, key); | 393 BaseTable::InsertKey(entry, key); |
372 const Smi& next_enum_index = | 394 const Smi& next_enum_index = Smi::Handle(BaseTable::isolate(), |
373 Smi::Handle(Smi::New(BaseTable::GetSmiValueAt(kNextEnumIndex))); | 395 Smi::New(BaseTable::GetSmiValueAt(kNextEnumIndex))); |
374 BaseTable::UpdatePayload(entry, kPayloadSize, next_enum_index); | 396 BaseTable::UpdatePayload(entry, kPayloadSize, next_enum_index); |
375 // TODO(koda): Handle possible Smi overflow from repeated insert/delete. | 397 // TODO(koda): Handle possible Smi overflow from repeated insert/delete. |
376 BaseTable::AdjustSmiValueAt(kNextEnumIndex, 1); | 398 BaseTable::AdjustSmiValueAt(kNextEnumIndex, 1); |
377 } | 399 } |
378 | 400 |
379 // No extra book-keeping needed for DeleteEntry. | 401 // No extra book-keeping needed for DeleteEntry. |
380 }; | 402 }; |
381 | 403 |
382 | 404 |
383 class HashTables : public AllStatic { | 405 class HashTables : public AllStatic { |
384 public: | 406 public: |
385 // Allocates and initializes a table. | 407 // Allocates and initializes a table. |
386 template<typename Table> | 408 template<typename Table> |
387 static RawArray* New(intptr_t initial_capacity, | 409 static RawArray* New(intptr_t initial_capacity, |
388 Heap::Space space = Heap::kNew) { | 410 Heap::Space space = Heap::kNew) { |
389 Table table(Array::Handle(Array::New( | 411 Table table(Array::New( |
390 Table::ArrayLengthForNumOccupied(initial_capacity), space))); | 412 Table::ArrayLengthForNumOccupied(initial_capacity), space)); |
391 table.Initialize(); | 413 table.Initialize(); |
392 return table.Release(); | 414 return table.Release().raw(); |
393 } | 415 } |
394 | 416 |
395 // Clears 'to' and inserts all elements from 'from', in iteration order. | 417 // Clears 'to' and inserts all elements from 'from', in iteration order. |
396 // The tables must have the same user payload size. | 418 // The tables must have the same user payload size. |
397 template<typename From, typename To> | 419 template<typename From, typename To> |
398 static void Copy(const From& from, const To& to) { | 420 static void Copy(const From& from, const To& to) { |
399 COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize); | 421 COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize); |
400 to.Initialize(); | 422 to.Initialize(); |
401 ASSERT(from.NumOccupied() < to.NumEntries()); | 423 ASSERT(from.NumOccupied() < to.NumEntries()); |
402 typename From::Iterator it(&from); | 424 typename From::Iterator it(&from); |
(...skipping 15 matching lines...) Expand all Loading... |
418 | 440 |
419 template<typename Table> | 441 template<typename Table> |
420 static void EnsureLoadFactor(double low, double high, const Table& table) { | 442 static void EnsureLoadFactor(double low, double high, const Table& table) { |
421 double current = (1 + table.NumOccupied() + table.NumDeleted()) / | 443 double current = (1 + table.NumOccupied() + table.NumDeleted()) / |
422 static_cast<double>(table.NumEntries()); | 444 static_cast<double>(table.NumEntries()); |
423 if (low <= current && current < high) { | 445 if (low <= current && current < high) { |
424 return; | 446 return; |
425 } | 447 } |
426 double target = (low + high) / 2.0; | 448 double target = (low + high) / 2.0; |
427 intptr_t new_capacity = (1 + table.NumOccupied()) / target; | 449 intptr_t new_capacity = (1 + table.NumOccupied()) / target; |
428 Table new_table(Array::Handle(New<Table>( | 450 Table new_table(New<Table>( |
429 new_capacity, | 451 new_capacity, |
430 table.data_.IsOld() ? Heap::kOld : Heap::kNew))); | 452 table.data_->IsOld() ? Heap::kOld : Heap::kNew)); |
431 Copy(table, new_table); | 453 Copy(table, new_table); |
432 table.data_ = new_table.Release(); | 454 *table.data_ = new_table.Release().raw(); |
433 } | 455 } |
434 | 456 |
435 // Serializes a table by concatenating its entries as an array. | 457 // Serializes a table by concatenating its entries as an array. |
436 template<typename Table> | 458 template<typename Table> |
437 static RawArray* ToArray(const Table& table, bool include_payload) { | 459 static RawArray* ToArray(const Table& table, bool include_payload) { |
438 const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1; | 460 const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1; |
439 Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size)); | 461 Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size)); |
440 typename Table::Iterator it(&table); | 462 typename Table::Iterator it(&table); |
441 Object& obj = Object::Handle(); | 463 Object& obj = Object::Handle(); |
442 intptr_t result_index = 0; | 464 intptr_t result_index = 0; |
443 while (it.MoveNext()) { | 465 while (it.MoveNext()) { |
444 intptr_t entry = it.Current(); | 466 intptr_t entry = it.Current(); |
445 obj = table.GetKey(entry); | 467 obj = table.GetKey(entry); |
446 result.SetAt(result_index++, obj); | 468 result.SetAt(result_index++, obj); |
447 if (include_payload) { | 469 if (include_payload) { |
448 for (intptr_t i = 0; i < Table::kPayloadSize; ++i) { | 470 for (intptr_t i = 0; i < Table::kPayloadSize; ++i) { |
449 obj = table.GetPayload(entry, i); | 471 obj = table.GetPayload(entry, i); |
450 result.SetAt(result_index++, obj); | 472 result.SetAt(result_index++, obj); |
451 } | 473 } |
452 } | 474 } |
453 } | 475 } |
454 return result.raw(); | 476 return result.raw(); |
455 } | 477 } |
456 }; | 478 }; |
457 | 479 |
458 | 480 |
459 template<typename BaseIterTable> | 481 template<typename BaseIterTable> |
460 class HashMap : public BaseIterTable { | 482 class HashMap : public BaseIterTable { |
461 public: | 483 public: |
462 explicit HashMap(Array& data) : BaseIterTable(data) {} | 484 explicit HashMap(RawArray* data) : BaseIterTable(data) {} |
| 485 HashMap(Isolate* isolate, RawArray* data) : BaseIterTable(isolate, data) {} |
463 template<typename Key> | 486 template<typename Key> |
464 RawObject* GetOrNull(const Key& key, bool* present = NULL) const { | 487 RawObject* GetOrNull(const Key& key, bool* present = NULL) const { |
465 intptr_t entry = BaseIterTable::FindKey(key); | 488 intptr_t entry = BaseIterTable::FindKey(key); |
466 if (present != NULL) { | 489 if (present != NULL) { |
467 *present = (entry != -1); | 490 *present = (entry != -1); |
468 } | 491 } |
469 return (entry == -1) ? Object::null() : BaseIterTable::GetPayload(entry, 0); | 492 return (entry == -1) ? Object::null() : BaseIterTable::GetPayload(entry, 0); |
470 } | 493 } |
471 bool UpdateOrInsert(const Object& key, const Object& value) const { | 494 bool UpdateOrInsert(const Object& key, const Object& value) const { |
472 EnsureCapacity(); | 495 EnsureCapacity(); |
(...skipping 26 matching lines...) Expand all Loading... |
499 return BaseIterTable::GetPayload(entry, 0); | 522 return BaseIterTable::GetPayload(entry, 0); |
500 } | 523 } |
501 } | 524 } |
502 // Like InsertOrGetValue, but calls NewKey to allocate a key object if needed. | 525 // Like InsertOrGetValue, but calls NewKey to allocate a key object if needed. |
503 template<typename Key> | 526 template<typename Key> |
504 RawObject* InsertNewOrGetValue(const Key& key, | 527 RawObject* InsertNewOrGetValue(const Key& key, |
505 const Object& value_if_absent) const { | 528 const Object& value_if_absent) const { |
506 EnsureCapacity(); | 529 EnsureCapacity(); |
507 intptr_t entry = -1; | 530 intptr_t entry = -1; |
508 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { | 531 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { |
509 Object& new_key = Object::Handle( | 532 Object& new_key = Object::Handle(BaseIterTable::isolate(), |
510 BaseIterTable::BaseTable::Traits::NewKey(key)); | 533 BaseIterTable::BaseTable::Traits::NewKey(key)); |
511 BaseIterTable::InsertKey(entry, new_key); | 534 BaseIterTable::InsertKey(entry, new_key); |
512 BaseIterTable::UpdatePayload(entry, 0, value_if_absent); | 535 BaseIterTable::UpdatePayload(entry, 0, value_if_absent); |
513 return value_if_absent.raw(); | 536 return value_if_absent.raw(); |
514 } else { | 537 } else { |
515 return BaseIterTable::GetPayload(entry, 0); | 538 return BaseIterTable::GetPayload(entry, 0); |
516 } | 539 } |
517 } | 540 } |
518 | 541 |
519 template<typename Key> | 542 template<typename Key> |
(...skipping 12 matching lines...) Expand all Loading... |
532 static const double kMaxLoadFactor = 0.75; | 555 static const double kMaxLoadFactor = 0.75; |
533 HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this); | 556 HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this); |
534 } | 557 } |
535 }; | 558 }; |
536 | 559 |
537 | 560 |
538 template<typename KeyTraits> | 561 template<typename KeyTraits> |
539 class UnorderedHashMap : public HashMap<UnorderedHashTable<KeyTraits, 1> > { | 562 class UnorderedHashMap : public HashMap<UnorderedHashTable<KeyTraits, 1> > { |
540 public: | 563 public: |
541 typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap; | 564 typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap; |
542 explicit UnorderedHashMap(Array& data) : BaseMap(data) {} | 565 explicit UnorderedHashMap(RawArray* data) : BaseMap(data) {} |
| 566 UnorderedHashMap(Isolate* isolate, RawArray* data) : BaseMap(isolate, data) {} |
543 }; | 567 }; |
544 | 568 |
545 | 569 |
546 template<typename KeyTraits> | 570 template<typename KeyTraits> |
547 class EnumIndexHashMap : public HashMap<EnumIndexHashTable<KeyTraits, 1> > { | 571 class EnumIndexHashMap : public HashMap<EnumIndexHashTable<KeyTraits, 1> > { |
548 public: | 572 public: |
549 typedef HashMap<EnumIndexHashTable<KeyTraits, 1> > BaseMap; | 573 typedef HashMap<EnumIndexHashTable<KeyTraits, 1> > BaseMap; |
550 explicit EnumIndexHashMap(Array& data) : BaseMap(data) {} | 574 explicit EnumIndexHashMap(RawArray* data) : BaseMap(data) {} |
| 575 EnumIndexHashMap(Isolate* isolate, RawArray* data) : BaseMap(isolate, data) {} |
551 }; | 576 }; |
552 | 577 |
553 | 578 |
554 template<typename BaseIterTable> | 579 template<typename BaseIterTable> |
555 class HashSet : public BaseIterTable { | 580 class HashSet : public BaseIterTable { |
556 public: | 581 public: |
557 explicit HashSet(Array& data) : BaseIterTable(data) {} | 582 explicit HashSet(RawArray* data) : BaseIterTable(data) {} |
| 583 HashSet(Isolate* isolate, RawArray* data) : BaseIterTable(isolate, data) {} |
558 bool Insert(const Object& key) { | 584 bool Insert(const Object& key) { |
559 EnsureCapacity(); | 585 EnsureCapacity(); |
560 intptr_t entry = -1; | 586 intptr_t entry = -1; |
561 bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry); | 587 bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry); |
562 if (!present) { | 588 if (!present) { |
563 BaseIterTable::InsertKey(entry, key); | 589 BaseIterTable::InsertKey(entry, key); |
564 } | 590 } |
565 return present; | 591 return present; |
566 } | 592 } |
567 | 593 |
568 // If 'key' is not present, insert and return it. Else, return the existing | 594 // If 'key' is not present, insert and return it. Else, return the existing |
569 // key in the set (useful for canonicalization). | 595 // key in the set (useful for canonicalization). |
570 RawObject* InsertOrGet(const Object& key) const { | 596 RawObject* InsertOrGet(const Object& key) const { |
571 EnsureCapacity(); | 597 EnsureCapacity(); |
572 intptr_t entry = -1; | 598 intptr_t entry = -1; |
573 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { | 599 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { |
574 BaseIterTable::InsertKey(entry, key); | 600 BaseIterTable::InsertKey(entry, key); |
575 return key.raw(); | 601 return key.raw(); |
576 } else { | 602 } else { |
577 return BaseIterTable::GetPayload(entry, 0); | 603 return BaseIterTable::GetPayload(entry, 0); |
578 } | 604 } |
579 } | 605 } |
580 | 606 |
581 // Like InsertOrGet, but calls NewKey to allocate a key object if needed. | 607 // Like InsertOrGet, but calls NewKey to allocate a key object if needed. |
582 template<typename Key> | 608 template<typename Key> |
583 RawObject* InsertNewOrGet(const Key& key) const { | 609 RawObject* InsertNewOrGet(const Key& key) const { |
584 EnsureCapacity(); | 610 EnsureCapacity(); |
585 intptr_t entry = -1; | 611 intptr_t entry = -1; |
586 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { | 612 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) { |
587 Object& new_key = Object::Handle( | 613 Object& new_key = Object::Handle(BaseIterTable::isolate(), |
588 BaseIterTable::BaseTable::Traits::NewKey(key)); | 614 BaseIterTable::BaseTable::Traits::NewKey(key)); |
589 BaseIterTable::InsertKey(entry, new_key); | 615 BaseIterTable::InsertKey(entry, new_key); |
590 return new_key.raw(); | 616 return new_key.raw(); |
591 } else { | 617 } else { |
592 return BaseIterTable::GetKey(entry); | 618 return BaseIterTable::GetKey(entry); |
593 } | 619 } |
594 } | 620 } |
595 | 621 |
596 template<typename Key> | 622 template<typename Key> |
597 RawObject* GetOrNull(const Key& key, bool* present = NULL) const { | 623 RawObject* GetOrNull(const Key& key, bool* present = NULL) const { |
(...skipping 20 matching lines...) Expand all Loading... |
618 static const double kMaxLoadFactor = 0.75; | 644 static const double kMaxLoadFactor = 0.75; |
619 HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this); | 645 HashTables::EnsureLoadFactor(0.0, kMaxLoadFactor, *this); |
620 } | 646 } |
621 }; | 647 }; |
622 | 648 |
623 | 649 |
624 template<typename KeyTraits> | 650 template<typename KeyTraits> |
625 class UnorderedHashSet : public HashSet<UnorderedHashTable<KeyTraits, 0> > { | 651 class UnorderedHashSet : public HashSet<UnorderedHashTable<KeyTraits, 0> > { |
626 public: | 652 public: |
627 typedef HashSet<UnorderedHashTable<KeyTraits, 0> > BaseSet; | 653 typedef HashSet<UnorderedHashTable<KeyTraits, 0> > BaseSet; |
628 explicit UnorderedHashSet(Array& data) : BaseSet(data) {} | 654 explicit UnorderedHashSet(RawArray* data) : BaseSet(data) {} |
| 655 UnorderedHashSet(Isolate* isolate, RawArray* data) : BaseSet(isolate, data) {} |
629 }; | 656 }; |
630 | 657 |
631 | 658 |
632 template<typename KeyTraits> | 659 template<typename KeyTraits> |
633 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > { | 660 class EnumIndexHashSet : public HashSet<EnumIndexHashTable<KeyTraits, 0> > { |
634 public: | 661 public: |
635 typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet; | 662 typedef HashSet<EnumIndexHashTable<KeyTraits, 0> > BaseSet; |
636 explicit EnumIndexHashSet(Array& data) : BaseSet(data) {} | 663 explicit EnumIndexHashSet(RawArray* data) : BaseSet(data) {} |
| 664 EnumIndexHashSet(Isolate* isolate, RawArray* data) : BaseSet(isolate, data) {} |
637 }; | 665 }; |
638 | 666 |
639 } // namespace dart | 667 } // namespace dart |
640 | 668 |
641 #endif // VM_HASH_TABLE_H_ | 669 #endif // VM_HASH_TABLE_H_ |
OLD | NEW |