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
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_HASH_TABLE_H_
6#define RUNTIME_VM_HASH_TABLE_H_
7
8#include "platform/assert.h"
9#include "vm/object.h"
10
11namespace dart {
12
13// Storage traits control how memory is allocated for HashTable.
14// Default ArrayStorageTraits use an Array to store HashTable contents.
15struct ArrayStorageTraits {
16 using ArrayHandle = Array;
17 using ArrayPtr = dart::ArrayPtr;
18 static constexpr intptr_t ArrayCid = kArrayCid;
19
20 static ArrayHandle& PtrToHandle(ArrayPtr ptr) { return Array::Handle(ptr); }
21
22 static void SetHandle(ArrayHandle& dst, const ArrayHandle& src) { // NOLINT
23 dst = src.ptr();
24 }
25
26 static void ClearHandle(ArrayHandle& handle) { // NOLINT
27 handle = Array::null();
28 }
29
30 static ArrayPtr New(Zone* zone, intptr_t length, Heap::Space space) {
31 return Array::New(len: length, space);
32 }
33
34 static bool IsImmutable(const ArrayHandle& handle) {
35 return handle.ptr()->untag()->InVMIsolateHeap();
36 }
37
38 static ObjectPtr At(ArrayHandle* array, intptr_t index) {
39 return array->At(index);
40 }
41
42 static void SetAt(ArrayHandle* array, intptr_t index, const Object& value) {
43 array->SetAt(index, value);
44 }
45};
46
47struct WeakArrayStorageTraits {
48 using ArrayHandle = WeakArray;
49 using ArrayPtr = dart::WeakArrayPtr;
50 static constexpr intptr_t ArrayCid = kWeakArrayCid;
51
52 static ArrayHandle& PtrToHandle(ArrayPtr ptr) {
53 return WeakArray::Handle(ptr);
54 }
55
56 static void SetHandle(ArrayHandle& dst, const ArrayHandle& src) { // NOLINT
57 dst = src.ptr();
58 }
59
60 static void ClearHandle(ArrayHandle& handle) { // NOLINT
61 handle = WeakArray::null();
62 }
63
64 static ArrayPtr New(Zone* zone, intptr_t length, Heap::Space space) {
65 return WeakArray::New(length, space);
66 }
67
68 static bool IsImmutable(const ArrayHandle& handle) {
69 return handle.ptr()->untag()->InVMIsolateHeap();
70 }
71
72 static ObjectPtr At(ArrayHandle* array, intptr_t index) {
73 return array->At(index);
74 }
75
76 static void SetAt(ArrayHandle* array, intptr_t index, const Object& value) {
77 array->SetAt(index, value);
78 }
79};
80
81struct AcqRelStorageTraits : ArrayStorageTraits {
82 static ObjectPtr At(ArrayHandle* array, intptr_t index) {
83 return array->AtAcquire(index);
84 }
85
86 static void SetAt(ArrayHandle* array, intptr_t index, const Object& value) {
87 array->SetAtRelease(index, value);
88 }
89};
90
91struct WeakAcqRelStorageTraits : WeakArrayStorageTraits {
92 static ObjectPtr At(ArrayHandle* array, intptr_t index) {
93 return array->AtAcquire(index);
94 }
95
96 static void SetAt(ArrayHandle* array, intptr_t index, const Object& value) {
97 array->SetAtRelease(index, value);
98 }
99};
100
101class HashTableBase : public ValueObject {
102 public:
103 static const Object& UnusedMarker() { return Object::transition_sentinel(); }
104 static const Object& DeletedMarker() { return Object::null_object(); }
105};
106
107// OVERVIEW:
108//
109// Hash maps and hash sets all use RawArray as backing storage. At the lowest
110// level is a generic open-addressing table that supports deletion.
111// - HashTable
112// The next layer provides ordering and iteration functionality:
113// - UnorderedHashTable
114// - LinkedListHashTable (TODO(koda): Implement.)
115// The utility class HashTables handles growth and conversion.
116// The next layer fixes the payload size and provides a natural interface:
117// - HashMap
118// - HashSet
119// Combining either of these with an iteration strategy, we get the templates
120// intended for use outside this file:
121// - UnorderedHashMap
122// - LinkedListHashMap
123// - UnorderedHashSet
124// - LinkedListHashSet
125// Each of these can be finally specialized with KeyTraits to support any set of
126// lookup key types (e.g., look up a char* in a set of String objects), and
127// any equality and hash code computation.
128//
129// The classes all wrap an Array handle, and methods like HashSet::Insert can
130// trigger growth into a new RawArray, updating the handle. Debug mode asserts
131// that 'Release' was called once to access the final array before destruction.
132// NOTE: The handle returned by 'Release' is cleared by ~HashTable.
133//
134// Example use:
135// typedef UnorderedHashMap<FooTraits> FooMap;
136// ...
137// FooMap cache(get_foo_cache());
138// cache.UpdateOrInsert(name0, obj0);
139// cache.UpdateOrInsert(name1, obj1);
140// ...
141// set_foo_cache(cache.Release());
142//
143// If you *know* that no mutating operations were called, you can optimize:
144// ...
145// obj ^= cache.GetOrNull(name);
146// ASSERT(cache.Release().ptr() == get_foo_cache());
147//
148// TODO(koda): When exposing these to Dart code, document and assert that
149// KeyTraits methods must not run Dart code (since the C++ code doesn't check
150// for concurrent modification).
151
152// Open-addressing hash table template using a RawArray as backing storage.
153//
154// The elements of the array are partitioned into entries:
155// [ header | metadata | entry0 | entry1 | ... | entryN ]
156// Each entry contains a key, followed by zero or more payload components,
157// and has 3 possible states: unused, occupied, or deleted.
158// The header tracks the number of entries in each state.
159// Any object except the backing storage array and Object::transition_sentinel()
160// may be stored as a key. Any object may be stored in a payload.
161//
162// Parameters
163// KeyTraits: defines static methods
164// bool IsMatch(const Key& key, const Object& obj) and
165// uword Hash(const Key& key) for any number of desired lookup key types.
166// kPayloadSize: number of components of the payload in each entry.
167// kMetaDataSize: number of elements reserved (e.g., for iteration order data).
168template <typename KeyTraits,
169 intptr_t kPayloadSize,
170 intptr_t kMetaDataSize,
171 typename StorageTraits = ArrayStorageTraits>
172class HashTable : public HashTableBase {
173 public:
174 typedef KeyTraits Traits;
175 typedef StorageTraits Storage;
176
177 // Uses the passed in handles for all handle operations.
178 // 'Release' must be called at the end to obtain the final table
179 // after potential growth/shrinkage.
180 HashTable(Object* key, Smi* index, typename StorageTraits::ArrayHandle* data)
181 : key_handle_(key),
182 smi_handle_(index),
183 data_(data),
184 released_data_(nullptr) {}
185 // Uses 'zone' for handle allocation. 'Release' must be called at the end
186 // to obtain the final table after potential growth/shrinkage.
187 HashTable(Zone* zone, typename StorageTraits::ArrayPtr data)
188 : key_handle_(&Object::Handle(zone)),
189 smi_handle_(&Smi::Handle(zone)),
190 data_(&StorageTraits::PtrToHandle(data)),
191 released_data_(nullptr) {}
192
193 // Returns the final table. The handle is cleared when this HashTable is
194 // destroyed.
195 typename StorageTraits::ArrayHandle& Release() {
196 ASSERT(data_ != nullptr);
197 ASSERT(released_data_ == nullptr);
198 // Ensure that no methods are called after 'Release'.
199 released_data_ = data_;
200 data_ = nullptr;
201 return *released_data_;
202 }
203
204 ~HashTable() {
205 // In DEBUG mode, calling 'Release' is mandatory.
206 ASSERT(data_ == nullptr);
207 if (released_data_ != nullptr) {
208 StorageTraits::ClearHandle(*released_data_);
209 }
210 }
211
212 // Returns a backing storage size such that 'num_occupied' distinct keys can
213 // be inserted into the table.
214 static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied) {
215 // Because we use quadratic (actually triangle number) probing it is
216 // important that the size is a power of two (otherwise we could fail to
217 // find an empty slot). This is described in Knuth's The Art of Computer
218 // Programming Volume 2, Chapter 6.4, exercise 20 (solution in the
219 // appendix, 2nd edition).
220 intptr_t num_entries = Utils::RoundUpToPowerOfTwo(x: num_occupied + 1);
221 return kFirstKeyIndex + (kEntrySize * num_entries);
222 }
223
224 // Initializes an empty table.
225 void Initialize() const {
226 ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
227 *smi_handle_ = Smi::New(value: 0);
228 StorageTraits::SetAt(data_, kOccupiedEntriesIndex, *smi_handle_);
229 StorageTraits::SetAt(data_, kDeletedEntriesIndex, *smi_handle_);
230
231#if !defined(PRODUCT)
232 StorageTraits::SetAt(data_, kNumGrowsIndex, *smi_handle_);
233 StorageTraits::SetAt(data_, kNumLT5LookupsIndex, *smi_handle_);
234 StorageTraits::SetAt(data_, kNumLT25LookupsIndex, *smi_handle_);
235 StorageTraits::SetAt(data_, kNumGT25LookupsIndex, *smi_handle_);
236 StorageTraits::SetAt(data_, kNumProbesIndex, *smi_handle_);
237#endif // !defined(PRODUCT)
238
239 for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
240 StorageTraits::SetAt(data_, i, UnusedMarker());
241 }
242 }
243
244 // Returns whether 'key' matches any key in the table.
245 template <typename Key>
246 bool ContainsKey(const Key& key) const {
247 return FindKey(key) != -1;
248 }
249
250 // Returns the entry that matches 'key', or -1 if none exists.
251 template <typename Key>
252 intptr_t FindKey(const Key& key) const {
253 const intptr_t num_entries = NumEntries();
254 // TODO(koda): Add salt.
255 NOT_IN_PRODUCT(intptr_t collisions = 0;)
256 uword hash = KeyTraits::Hash(key);
257 ASSERT(Utils::IsPowerOfTwo(num_entries));
258 intptr_t probe = hash & (num_entries - 1);
259 int probe_distance = 1;
260 while (true) {
261 if (IsUnused(entry: probe)) {
262 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
263 return -1;
264 } else if (!IsDeleted(entry: probe)) {
265 *key_handle_ = GetKey(entry: probe);
266 if (KeyTraits::IsMatch(key, *key_handle_)) {
267 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
268 return probe;
269 }
270 NOT_IN_PRODUCT(collisions += 1;)
271 }
272 // Advance probe. See ArrayLengthForNumOccupied comment for
273 // explanation of how we know this hits all slots.
274 probe = (probe + probe_distance) & (num_entries - 1);
275 probe_distance++;
276 }
277 UNREACHABLE();
278 return -1;
279 }
280
281 // Sets *entry to either:
282 // - an occupied entry matching 'key', and returns true, or
283 // - an unused/deleted entry where a matching key may be inserted,
284 // and returns false.
285 template <typename Key>
286 bool FindKeyOrDeletedOrUnused(const Key& key, intptr_t* entry) const {
287 const intptr_t num_entries = NumEntries();
288 ASSERT(entry != nullptr);
289 NOT_IN_PRODUCT(intptr_t collisions = 0;)
290 uword hash = KeyTraits::Hash(key);
291 ASSERT(Utils::IsPowerOfTwo(num_entries));
292 intptr_t probe = hash & (num_entries - 1);
293 int probe_distance = 1;
294 intptr_t deleted = -1;
295 while (true) {
296 if (IsUnused(entry: probe)) {
297 *entry = (deleted != -1) ? deleted : probe;
298 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
299 return false;
300 } else if (IsDeleted(entry: probe)) {
301 if (deleted == -1) {
302 deleted = probe;
303 }
304 } else {
305 *key_handle_ = GetKey(entry: probe);
306 if (KeyTraits::IsMatch(key, *key_handle_)) {
307 *entry = probe;
308 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
309 return true;
310 }
311 NOT_IN_PRODUCT(collisions += 1;)
312 }
313 // Advance probe. See ArrayLengthForNumOccupied comment for
314 // explanation of how we know this hits all slots.
315 probe = (probe + probe_distance) & (num_entries - 1);
316 probe_distance++;
317 }
318 UNREACHABLE();
319 return false;
320 }
321
322 // Sets the key of a previously unoccupied entry. This must not be the last
323 // unoccupied entry.
324 void InsertKey(intptr_t entry, const Object& key) const {
325 ASSERT(key.ptr() != UnusedMarker().ptr());
326 ASSERT(key.ptr() != DeletedMarker().ptr());
327 ASSERT(!IsOccupied(entry));
328 AdjustSmiValueAt(index: kOccupiedEntriesIndex, delta: 1);
329 if (IsDeleted(entry)) {
330 AdjustSmiValueAt(index: kDeletedEntriesIndex, delta: -1);
331 } else {
332 ASSERT(IsUnused(entry));
333 }
334 InternalSetKey(entry, key);
335 ASSERT(IsOccupied(entry));
336 }
337
338 bool IsUnused(intptr_t entry) const {
339 return InternalGetKey(entry) == UnusedMarker().ptr();
340 }
341 bool IsOccupied(intptr_t entry) const {
342 return !IsUnused(entry) && !IsDeleted(entry);
343 }
344 bool IsDeleted(intptr_t entry) const {
345 return InternalGetKey(entry) == DeletedMarker().ptr();
346 }
347
348 ObjectPtr GetKey(intptr_t entry) const {
349 ASSERT(IsOccupied(entry));
350 return InternalGetKey(entry);
351 }
352 ObjectPtr GetPayload(intptr_t entry, intptr_t component) const {
353 ASSERT(IsOccupied(entry));
354 return WeakSerializationReference::Unwrap(
355 StorageTraits::At(data_, PayloadIndex(entry, component)));
356 }
357 void UpdatePayload(intptr_t entry,
358 intptr_t component,
359 const Object& value) const {
360 ASSERT(IsOccupied(entry));
361 ASSERT(0 <= component && component < kPayloadSize);
362 StorageTraits::SetAt(data_, PayloadIndex(entry, component), value);
363 }
364 // Deletes both the key and payload of the specified entry.
365 void DeleteEntry(intptr_t entry) const {
366 ASSERT(IsOccupied(entry));
367 for (intptr_t i = 0; i < kPayloadSize; ++i) {
368 UpdatePayload(entry, component: i, value: DeletedMarker());
369 }
370 InternalSetKey(entry, key: DeletedMarker());
371 AdjustSmiValueAt(index: kOccupiedEntriesIndex, delta: -1);
372 AdjustSmiValueAt(index: kDeletedEntriesIndex, delta: 1);
373 }
374 intptr_t NumEntries() const {
375 return (data_->Length() - kFirstKeyIndex) / kEntrySize;
376 }
377 intptr_t NumUnused() const {
378 return NumEntries() - NumOccupied() - NumDeleted();
379 }
380 intptr_t NumOccupied() const { return GetSmiValueAt(index: kOccupiedEntriesIndex); }
381 intptr_t NumDeleted() const { return GetSmiValueAt(index: kDeletedEntriesIndex); }
382 Object& KeyHandle() const { return *key_handle_; }
383 Smi& SmiHandle() const { return *smi_handle_; }
384
385#if !defined(PRODUCT)
386 intptr_t NumGrows() const { return GetSmiValueAt(index: kNumGrowsIndex); }
387 intptr_t NumLT5Collisions() const {
388 return GetSmiValueAt(index: kNumLT5LookupsIndex);
389 }
390 intptr_t NumLT25Collisions() const {
391 return GetSmiValueAt(index: kNumLT25LookupsIndex);
392 }
393 intptr_t NumGT25Collisions() const {
394 return GetSmiValueAt(index: kNumGT25LookupsIndex);
395 }
396 intptr_t NumProbes() const { return GetSmiValueAt(index: kNumProbesIndex); }
397 void UpdateGrowth() const {
398 if (KeyTraits::ReportStats()) {
399 AdjustSmiValueAt(index: kNumGrowsIndex, delta: 1);
400 }
401 }
402 void UpdateCollisions(intptr_t collisions) const {
403 if (KeyTraits::ReportStats()) {
404 if (Storage::IsImmutable(*data_)) {
405 return;
406 }
407 AdjustSmiValueAt(index: kNumProbesIndex, delta: collisions + 1);
408 if (collisions < 5) {
409 AdjustSmiValueAt(index: kNumLT5LookupsIndex, delta: 1);
410 } else if (collisions < 25) {
411 AdjustSmiValueAt(index: kNumLT25LookupsIndex, delta: 1);
412 } else {
413 AdjustSmiValueAt(index: kNumGT25LookupsIndex, delta: 1);
414 }
415 }
416 }
417 void PrintStats() const {
418 if (!KeyTraits::ReportStats()) {
419 return;
420 }
421 const intptr_t num5 = NumLT5Collisions();
422 const intptr_t num25 = NumLT25Collisions();
423 const intptr_t num_more = NumGT25Collisions();
424 // clang-format off
425 OS::PrintErr("Stats for %s table :\n"
426 " Size of table = %" Pd ",Number of Occupied entries = %" Pd "\n"
427 " Number of Grows = %" Pd "\n"
428 " Number of lookups with < 5 collisions = %" Pd "\n"
429 " Number of lookups with < 25 collisions = %" Pd "\n"
430 " Number of lookups with > 25 collisions = %" Pd "\n"
431 " Average number of probes = %g\n",
432 KeyTraits::Name(),
433 NumEntries(), NumOccupied(), NumGrows(),
434 num5, num25, num_more,
435 static_cast<double>(NumProbes()) / (num5 + num25 + num_more));
436 // clang-format on
437 }
438#endif // !PRODUCT
439
440 void UpdateWeakDeleted() const {
441 if (StorageTraits::ArrayCid != kWeakArrayCid) return;
442
443 // As entries are deleted by GC, NumOccupied and NumDeleted become stale.
444 // Re-count before growing/rehashing to prevent table growth when the
445 // number of live entries is not increasing.
446 intptr_t num_occupied = 0;
447 intptr_t num_deleted = 0;
448 for (intptr_t i = 0, n = NumEntries(); i < n; i++) {
449 if (IsDeleted(entry: i)) {
450 num_deleted++;
451 }
452 if (IsOccupied(entry: i)) {
453 num_occupied++;
454 }
455 }
456 SetSmiValueAt(index: kOccupiedEntriesIndex, value: num_occupied);
457 SetSmiValueAt(index: kDeletedEntriesIndex, value: num_deleted);
458 }
459
460 protected:
461 static constexpr intptr_t kOccupiedEntriesIndex = 0;
462 static constexpr intptr_t kDeletedEntriesIndex = 1;
463#if defined(PRODUCT)
464 static constexpr intptr_t kHeaderSize = kDeletedEntriesIndex + 1;
465#else
466 static constexpr intptr_t kNumGrowsIndex = 2;
467 static constexpr intptr_t kNumLT5LookupsIndex = 3;
468 static constexpr intptr_t kNumLT25LookupsIndex = 4;
469 static constexpr intptr_t kNumGT25LookupsIndex = 5;
470 static constexpr intptr_t kNumProbesIndex = 6;
471 static constexpr intptr_t kHeaderSize = kNumProbesIndex + 1;
472#endif
473 static constexpr intptr_t kMetaDataIndex = kHeaderSize;
474 static constexpr intptr_t kFirstKeyIndex = kHeaderSize + kMetaDataSize;
475 static constexpr intptr_t kEntrySize = 1 + kPayloadSize;
476
477 intptr_t KeyIndex(intptr_t entry) const {
478 ASSERT(0 <= entry && entry < NumEntries());
479 return kFirstKeyIndex + (kEntrySize * entry);
480 }
481
482 intptr_t PayloadIndex(intptr_t entry, intptr_t component) const {
483 ASSERT(0 <= component && component < kPayloadSize);
484 return KeyIndex(entry) + 1 + component;
485 }
486
487 ObjectPtr InternalGetKey(intptr_t entry) const {
488 return WeakSerializationReference::Unwrap(
489 StorageTraits::At(data_, KeyIndex(entry)));
490 }
491
492 void InternalSetKey(intptr_t entry, const Object& key) const {
493 StorageTraits::SetAt(data_, KeyIndex(entry), key);
494 }
495
496 intptr_t GetSmiValueAt(intptr_t index) const {
497 ASSERT(!data_->IsNull());
498 if (StorageTraits::At(data_, index)->IsHeapObject()) {
499 Object::Handle(StorageTraits::At(data_, index)).Print();
500 }
501 ASSERT(!StorageTraits::At(data_, index)->IsHeapObject());
502 return Smi::Value(Smi::RawCast(raw: StorageTraits::At(data_, index)));
503 }
504
505 void SetSmiValueAt(intptr_t index, intptr_t value) const {
506 *smi_handle_ = Smi::New(value);
507 StorageTraits::SetAt(data_, index, *smi_handle_);
508 }
509
510 void AdjustSmiValueAt(intptr_t index, intptr_t delta) const {
511 SetSmiValueAt(index, value: (GetSmiValueAt(index) + delta));
512 }
513
514 Object* key_handle_;
515 Smi* smi_handle_;
516 // Exactly one of these is non-null, depending on whether Release was called.
517 typename StorageTraits::ArrayHandle* data_;
518 typename StorageTraits::ArrayHandle* released_data_;
519
520 friend class HashTables;
521 template <typename Table, bool kAllCanonicalObjectsAreIncludedIntoSet>
522 friend class CanonicalSetDeserializationCluster;
523 template <typename Table,
524 typename HandleType,
525 typename PointerType,
526 bool kAllCanonicalObjectsAreIncludedIntoSet>
527 friend class CanonicalSetSerializationCluster;
528};
529
530// Table with unspecified iteration order. No payload overhead or metadata.
531template <typename KeyTraits,
532 intptr_t kUserPayloadSize,
533 typename StorageTraits = ArrayStorageTraits>
534class UnorderedHashTable
535 : public HashTable<KeyTraits, kUserPayloadSize, 0, StorageTraits> {
536 public:
537 typedef HashTable<KeyTraits, kUserPayloadSize, 0, StorageTraits> BaseTable;
538 typedef typename StorageTraits::ArrayPtr ArrayPtr;
539 typedef typename StorageTraits::ArrayHandle ArrayHandle;
540 static constexpr intptr_t kPayloadSize = kUserPayloadSize;
541 explicit UnorderedHashTable(ArrayPtr data)
542 : BaseTable(Thread::Current()->zone(), data) {}
543 UnorderedHashTable(Zone* zone, ArrayPtr data) : BaseTable(zone, data) {}
544 UnorderedHashTable(Object* key, Smi* value, ArrayHandle* data)
545 : BaseTable(key, value, data) {}
546 // Note: Does not check for concurrent modification.
547 class Iterator {
548 public:
549 explicit Iterator(const UnorderedHashTable* table)
550 : table_(table), entry_(-1) {}
551 bool MoveNext() {
552 while (entry_ < (table_->NumEntries() - 1)) {
553 ++entry_;
554 if (table_->IsOccupied(entry_)) {
555 return true;
556 }
557 }
558 return false;
559 }
560 intptr_t Current() { return entry_; }
561
562 private:
563 const UnorderedHashTable* table_;
564 intptr_t entry_;
565 };
566
567 // No extra book-keeping needed for Initialize, InsertKey, DeleteEntry.
568};
569
570class HashTables : public AllStatic {
571 public:
572 // Allocates and initializes a table.
573 template <typename Table>
574 static typename Table::Storage::ArrayPtr New(intptr_t initial_capacity,
575 Heap::Space space = Heap::kNew) {
576 auto zone = Thread::Current()->zone();
577 Table table(
578 zone,
579 Table::Storage::New(
580 zone, Table::ArrayLengthForNumOccupied(initial_capacity), space));
581 table.Initialize();
582 return table.Release().ptr();
583 }
584
585 template <typename Table>
586 static typename Table::Storage::ArrayPtr New(
587 const typename Table::Storage::ArrayHandle& array) {
588 Table table(Thread::Current()->zone(), array.ptr());
589 table.Initialize();
590 return table.Release().ptr();
591 }
592
593 // Clears 'to' and inserts all elements from 'from', in iteration order.
594 // The tables must have the same user payload size.
595 template <typename From, typename To>
596 static void Copy(const From& from, const To& to) {
597 COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize);
598 to.Initialize();
599 ASSERT(from.NumOccupied() < to.NumEntries());
600 typename From::Iterator it(&from);
601 Object& obj = Object::Handle();
602 while (it.MoveNext()) {
603 intptr_t from_entry = it.Current();
604 obj = from.GetKey(from_entry);
605 intptr_t to_entry = -1;
606 const Object& key = obj;
607 bool present = to.FindKeyOrDeletedOrUnused(key, &to_entry);
608 ASSERT(!present);
609 to.InsertKey(to_entry, obj);
610 for (intptr_t i = 0; i < From::kPayloadSize; ++i) {
611 obj = from.GetPayload(from_entry, i);
612 to.UpdatePayload(to_entry, i, obj);
613 }
614 }
615 }
616
617 static constexpr double kMaxLoadFactor = 0.71;
618
619 template <typename Table>
620 static void EnsureLoadFactor(double high, const Table& table) {
621 // We count deleted elements because they take up space just
622 // like occupied slots in order to cause a rehashing.
623 const double current = (1 + table.NumOccupied() + table.NumDeleted()) /
624 static_cast<double>(table.NumEntries());
625 const bool too_many_deleted = table.NumOccupied() <= table.NumDeleted();
626 if (current < high && !too_many_deleted) {
627 return;
628 }
629
630 table.UpdateWeakDeleted();
631
632 // Normally we double the size here, but if less than half are occupied
633 // then it won't grow (this would imply that there were quite a lot of
634 // deleted slots). We don't want to constantly rehash if we are adding
635 // and deleting entries at just under the load factor limit, so we may
636 // double the size even though the number of occupied slots would not
637 // necessarily justify it. For example if the max load factor is 71% and
638 // the table is 70% full we will double the size to avoid a rehash every
639 // time 1% has been added and deleted.
640 const intptr_t new_capacity = table.NumOccupied() * 2 + 1;
641 ASSERT(table.NumOccupied() == 0 ||
642 ((1.0 + table.NumOccupied()) /
643 Utils::RoundUpToPowerOfTwo(new_capacity)) <= high);
644 Table new_table(New<Table>(new_capacity, // Is rounded up to power of 2.
645 table.data_->IsOld() ? Heap::kOld : Heap::kNew));
646 Copy(table, new_table);
647 Table::Storage::SetHandle(*table.data_, new_table.Release());
648 NOT_IN_PRODUCT(table.UpdateGrowth(); table.PrintStats();)
649 }
650
651 // Serializes a table by concatenating its entries as an array.
652 template <typename Table>
653 static ArrayPtr ToArray(const Table& table, bool include_payload) {
654 const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1;
655 Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size));
656 typename Table::Iterator it(&table);
657 Object& obj = Object::Handle();
658 intptr_t result_index = 0;
659 while (it.MoveNext()) {
660 intptr_t entry = it.Current();
661 obj = table.GetKey(entry);
662 result.SetAt(result_index++, obj);
663 if (include_payload) {
664 for (intptr_t i = 0; i < Table::kPayloadSize; ++i) {
665 obj = table.GetPayload(entry, i);
666 result.SetAt(result_index++, obj);
667 }
668 }
669 }
670 return result.ptr();
671 }
672
673#if defined(DART_PRECOMPILER)
674 // Replace elements of this set with WeakSerializationReferences.
675 static void Weaken(const Array& table) {
676 if (!table.IsNull()) {
677 Object& element = Object::Handle();
678 for (intptr_t i = 0; i < table.Length(); i++) {
679 element = table.At(i);
680 if (!element.IsSmi()) {
681 element = WeakSerializationReference::New(
682 element, HashTableBase::DeletedMarker());
683 table.SetAt(i, element);
684 }
685 }
686 }
687 }
688#endif
689};
690
691template <typename BaseIterTable>
692class HashMap : public BaseIterTable {
693 public:
694 explicit HashMap(ArrayPtr data)
695 : BaseIterTable(Thread::Current()->zone(), data) {}
696 HashMap(Zone* zone, ArrayPtr data) : BaseIterTable(zone, data) {}
697 HashMap(Object* key, Smi* value, Array* data)
698 : BaseIterTable(key, value, data) {}
699 template <typename Key>
700 ObjectPtr GetOrNull(const Key& key, bool* present = nullptr) const {
701 intptr_t entry = BaseIterTable::FindKey(key);
702 if (present != nullptr) {
703 *present = (entry != -1);
704 }
705 return (entry == -1) ? Object::null() : BaseIterTable::GetPayload(entry, 0);
706 }
707 template <typename Key>
708 ObjectPtr GetOrDie(const Key& key) const {
709 intptr_t entry = BaseIterTable::FindKey(key);
710 if (entry == -1) UNREACHABLE();
711 return BaseIterTable::GetPayload(entry, 0);
712 }
713 bool UpdateOrInsert(const Object& key, const Object& value) const {
714 EnsureCapacity();
715 intptr_t entry = -1;
716 bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
717 if (!present) {
718 BaseIterTable::InsertKey(entry, key);
719 }
720 BaseIterTable::UpdatePayload(entry, 0, value);
721 return present;
722 }
723 // Update the value of an existing key. Note that 'key' need not be an Object.
724 template <typename Key>
725 void UpdateValue(const Key& key, const Object& value) const {
726 intptr_t entry = BaseIterTable::FindKey(key);
727 ASSERT(entry != -1);
728 BaseIterTable::UpdatePayload(entry, 0, value);
729 }
730 // If 'key' is not present, maps it to 'value_if_absent'. Returns the final
731 // value in the map.
732 ObjectPtr InsertOrGetValue(const Object& key,
733 const Object& value_if_absent) const {
734 EnsureCapacity();
735 intptr_t entry = -1;
736 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
737 BaseIterTable::InsertKey(entry, key);
738 BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
739 return value_if_absent.ptr();
740 } else {
741 return BaseIterTable::GetPayload(entry, 0);
742 }
743 }
744 // Like InsertOrGetValue, but calls NewKey to allocate a key object if needed.
745 template <typename Key>
746 ObjectPtr InsertNewOrGetValue(const Key& key,
747 const Object& value_if_absent) const {
748 EnsureCapacity();
749 intptr_t entry = -1;
750 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
751 BaseIterTable::KeyHandle() =
752 BaseIterTable::BaseTable::Traits::NewKey(key);
753 BaseIterTable::InsertKey(entry, BaseIterTable::KeyHandle());
754 BaseIterTable::UpdatePayload(entry, 0, value_if_absent);
755 return value_if_absent.ptr();
756 } else {
757 return BaseIterTable::GetPayload(entry, 0);
758 }
759 }
760
761 template <typename Key>
762 bool Remove(const Key& key) const {
763 intptr_t entry = BaseIterTable::FindKey(key);
764 if (entry == -1) {
765 return false;
766 } else {
767 BaseIterTable::DeleteEntry(entry);
768 return true;
769 }
770 }
771
772 void Clear() const { BaseIterTable::Initialize(); }
773
774 protected:
775 void EnsureCapacity() const {
776 HashTables::EnsureLoadFactor(HashTables::kMaxLoadFactor, *this);
777 }
778};
779
780template <typename KeyTraits>
781class UnorderedHashMap : public HashMap<UnorderedHashTable<KeyTraits, 1> > {
782 public:
783 typedef HashMap<UnorderedHashTable<KeyTraits, 1> > BaseMap;
784 explicit UnorderedHashMap(ArrayPtr data)
785 : BaseMap(Thread::Current()->zone(), data) {}
786 UnorderedHashMap(Zone* zone, ArrayPtr data) : BaseMap(zone, data) {}
787 UnorderedHashMap(Object* key, Smi* value, Array* data)
788 : BaseMap(key, value, data) {}
789};
790
791template <typename BaseIterTable, typename StorageTraits>
792class HashSet : public BaseIterTable {
793 public:
794 typedef typename StorageTraits::ArrayPtr ArrayPtr;
795 typedef typename StorageTraits::ArrayHandle ArrayHandle;
796 explicit HashSet(ArrayPtr data)
797 : BaseIterTable(Thread::Current()->zone(), data) {}
798 HashSet(Zone* zone, ArrayPtr data) : BaseIterTable(zone, data) {}
799 HashSet(Object* key, Smi* value, ArrayHandle* data)
800 : BaseIterTable(key, value, data) {}
801 bool Insert(const Object& key) {
802 EnsureCapacity();
803 intptr_t entry = -1;
804 bool present = BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry);
805 if (!present) {
806 BaseIterTable::InsertKey(entry, key);
807 }
808 return present;
809 }
810
811 // If 'key' is not present, insert and return it. Else, return the existing
812 // key in the set (useful for canonicalization).
813 ObjectPtr InsertOrGet(const Object& key) const {
814 EnsureCapacity();
815 intptr_t entry = -1;
816 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
817 BaseIterTable::InsertKey(entry, key);
818 return key.ptr();
819 } else {
820 return BaseIterTable::GetKey(entry);
821 }
822 }
823
824 // Like InsertOrGet, but calls NewKey to allocate a key object if needed.
825 template <typename Key>
826 ObjectPtr InsertNewOrGet(const Key& key) const {
827 EnsureCapacity();
828 intptr_t entry = -1;
829 if (!BaseIterTable::FindKeyOrDeletedOrUnused(key, &entry)) {
830 BaseIterTable::KeyHandle() =
831 BaseIterTable::BaseTable::Traits::NewKey(key);
832 BaseIterTable::InsertKey(entry, BaseIterTable::KeyHandle());
833 return BaseIterTable::KeyHandle().ptr();
834 } else {
835 return BaseIterTable::GetKey(entry);
836 }
837 }
838
839 template <typename Key>
840 ObjectPtr GetOrNull(const Key& key, bool* present = nullptr) const {
841 intptr_t entry = BaseIterTable::FindKey(key);
842 if (present != nullptr) {
843 *present = (entry != -1);
844 }
845 return (entry == -1) ? Object::null() : BaseIterTable::GetKey(entry);
846 }
847
848 template <typename Key>
849 bool Remove(const Key& key) const {
850 intptr_t entry = BaseIterTable::FindKey(key);
851 if (entry == -1) {
852 return false;
853 } else {
854 BaseIterTable::DeleteEntry(entry);
855 return true;
856 }
857 }
858
859 void Clear() const { BaseIterTable::Initialize(); }
860
861 protected:
862 void EnsureCapacity() const {
863 HashTables::EnsureLoadFactor(HashTables::kMaxLoadFactor, *this);
864 }
865};
866
867template <typename KeyTraits, typename TableStorageTraits = ArrayStorageTraits>
868class UnorderedHashSet
869 : public HashSet<UnorderedHashTable<KeyTraits, 0, TableStorageTraits>,
870 TableStorageTraits> {
871 using UnderlyingTable = UnorderedHashTable<KeyTraits, 0, TableStorageTraits>;
872
873 public:
874 typedef HashSet<UnderlyingTable, TableStorageTraits> BaseSet;
875 typedef typename TableStorageTraits::ArrayPtr ArrayPtr;
876 typedef typename TableStorageTraits::ArrayHandle ArrayHandle;
877 explicit UnorderedHashSet(ArrayPtr data)
878 : BaseSet(Thread::Current()->zone(), data) {
879 ASSERT(data != Object::null());
880 }
881 UnorderedHashSet(Zone* zone, ArrayPtr data) : BaseSet(zone, data) {}
882 UnorderedHashSet(Object* key, Smi* value, ArrayHandle* data)
883 : BaseSet(key, value, data) {}
884
885 void Dump() const {
886 Object& entry = Object::Handle();
887 for (intptr_t i = 0; i < this->data_->Length(); i++) {
888 entry = WeakSerializationReference::Unwrap(
889 TableStorageTraits::At(this->data_, i));
890 if (entry.ptr() == BaseSet::UnusedMarker().ptr() ||
891 entry.ptr() == BaseSet::DeletedMarker().ptr() || entry.IsSmi()) {
892 // empty, deleted, num_used/num_deleted
893 OS::PrintErr("%" Pd ": %s\n", i, entry.ToCString());
894 } else {
895 intptr_t hash = KeyTraits::Hash(entry);
896 OS::PrintErr("%" Pd ": %" Pd ", %s\n", i, hash, entry.ToCString());
897 }
898 }
899 }
900};
901
902typedef UnorderedHashMap<SmiTraits> IntHashMap;
903
904} // namespace dart
905
906#endif // RUNTIME_VM_HASH_TABLE_H_
907

source code of dart_sdk/runtime/vm/hash_table.h