1// Copyright (c) 2013, 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#include "vm/heap/weak_table.h"
6
7#include "platform/assert.h"
8#include "vm/raw_object.h"
9
10namespace dart {
11
12intptr_t WeakTable::SizeFor(intptr_t count, intptr_t size) {
13 intptr_t result = size;
14 if (count <= (size / 4)) {
15 // Reduce the capacity.
16 result = size / 2;
17 } else {
18 // Increase the capacity.
19 result = size * 2;
20 if (result < size) {
21 FATAL(
22 "Reached impossible state of having more weak table entries"
23 " than memory available for heap objects.");
24 }
25 }
26 if (result < kMinSize) {
27 result = kMinSize;
28 }
29 return result;
30}
31
32void WeakTable::SetValueExclusive(ObjectPtr key, intptr_t val) {
33 intptr_t mask = size() - 1;
34 intptr_t idx = Hash(key) & mask;
35 intptr_t empty_idx = -1;
36 ObjectPtr obj = ObjectAtExclusive(idx);
37
38 while (obj != nullptr) {
39 if (obj == key) {
40 SetValueAt(idx, val);
41 return;
42 } else if ((empty_idx < 0) &&
43 (static_cast<intptr_t>(obj) == kDeletedEntry)) {
44 empty_idx = idx; // Insert at this location if not found.
45 }
46 idx = (idx + 1) & mask;
47 obj = ObjectAtExclusive(idx);
48 }
49
50 if (val == 0) {
51 // Do not enter an invalid value. Associating 0 with a key deletes it from
52 // this weak table above in SetValueAt. If the key was not present in the
53 // weak table we are done.
54 return;
55 }
56
57 if (empty_idx >= 0) {
58 // We will be reusing a slot below.
59 set_used(used() - 1);
60 idx = empty_idx;
61 }
62
63 ASSERT(!IsValidEntryAtExclusive(idx));
64 // Set the key and value.
65 SetObjectAt(idx, key);
66 SetValueAt(idx, val);
67 // Update the counts.
68 set_used(used() + 1);
69 set_count(count() + 1);
70
71 // Rehash if needed to ensure that there are empty slots available.
72 if (used_ >= limit()) {
73 Rehash();
74 }
75}
76
77void WeakTable::Reset() {
78 intptr_t* old_data = data_;
79 used_ = 0;
80 count_ = 0;
81 size_ = kMinSize;
82 free(old_data);
83 data_ = reinterpret_cast<intptr_t*>(calloc(size_, kEntrySize * kWordSize));
84}
85
86void WeakTable::Forward(ObjectPointerVisitor* visitor) {
87 if (used_ == 0) return;
88
89 for (intptr_t i = 0; i < size_; i++) {
90 if (IsValidEntryAtExclusive(i)) {
91 visitor->VisitPointer(ObjectPointerAt(i));
92 }
93 }
94
95 Rehash();
96}
97
98void WeakTable::Rehash() {
99 intptr_t old_size = size();
100 intptr_t* old_data = data_;
101
102 intptr_t new_size = SizeFor(count(), size());
103 ASSERT(Utils::IsPowerOfTwo(new_size));
104 intptr_t* new_data =
105 reinterpret_cast<intptr_t*>(calloc(new_size, kEntrySize * kWordSize));
106
107 intptr_t mask = new_size - 1;
108 set_used(0);
109 for (intptr_t i = 0; i < old_size; i++) {
110 if (IsValidEntryAtExclusive(i)) {
111 // Find the new hash location for this entry.
112 ObjectPtr key = ObjectAtExclusive(i);
113 intptr_t idx = Hash(key) & mask;
114 ObjectPtr obj = static_cast<ObjectPtr>(new_data[ObjectIndex(idx)]);
115 while (obj != nullptr) {
116 ASSERT(obj != key); // Duplicate entry is not expected.
117 idx = (idx + 1) & mask;
118 obj = static_cast<ObjectPtr>(new_data[ObjectIndex(idx)]);
119 }
120
121 new_data[ObjectIndex(idx)] = static_cast<intptr_t>(key);
122 new_data[ValueIndex(idx)] = ValueAtExclusive(i);
123 set_used(used() + 1);
124 }
125 }
126 // We should only have used valid entries.
127 ASSERT(used() == count());
128
129 // Switch to using the newly allocated backing store.
130 size_ = new_size;
131 data_ = new_data;
132 free(old_data);
133}
134
135void WeakTable::MergeFrom(WeakTable* donor) {
136 for (intptr_t i = 0; i < donor->size(); i++) {
137 if (donor->IsValidEntryAtExclusive(i)) {
138 SetValueExclusive(donor->ObjectAtExclusive(i), ValueIndex(i));
139 }
140 }
141}
142
143} // namespace dart
144