5 #include "src/identity-map.h" 7 #include "src/base/functional.h" 8 #include "src/heap/heap.h" 9 #include "src/roots-inl.h" 14 static const int kInitialIdentityMapSize = 4;
15 static const int kResizeFactor = 2;
17 IdentityMapBase::~IdentityMapBase() {
23 void IdentityMapBase::Clear() {
25 DCHECK(!is_iterable());
26 heap_->UnregisterStrongRoots(ObjectSlot(keys_));
37 void IdentityMapBase::EnableIteration() {
38 CHECK(!is_iterable());
42 void IdentityMapBase::DisableIteration() {
47 int IdentityMapBase::ScanKeysFor(Address address)
const {
48 int start = Hash(address) & mask_;
49 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
50 for (
int index = start; index < capacity_; index++) {
51 if (keys_[index] == address)
return index;
52 if (keys_[index] == not_mapped)
return -1;
54 for (
int index = 0; index < start; index++) {
55 if (keys_[index] == address)
return index;
56 if (keys_[index] == not_mapped)
return -1;
61 int IdentityMapBase::InsertKey(Address address) {
62 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
64 int start = Hash(address) & mask_;
65 int limit = capacity_ / 2;
67 for (
int index = start; --limit > 0; index = (index + 1) & mask_) {
68 if (keys_[index] == address)
return index;
69 if (keys_[index] == not_mapped) {
71 DCHECK_LE(size_, capacity_);
72 keys_[index] = address;
77 Resize(capacity_ * kResizeFactor);
82 bool IdentityMapBase::DeleteIndex(
int index,
void** deleted_value) {
83 if (deleted_value !=
nullptr) *deleted_value = values_[index];
84 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
85 DCHECK_NE(keys_[index], not_mapped);
86 keys_[index] = not_mapped;
87 values_[index] =
nullptr;
91 if (capacity_ > kInitialIdentityMapSize &&
92 size_ * kResizeFactor < capacity_ / kResizeFactor) {
93 Resize(capacity_ / kResizeFactor);
98 int next_index = index;
100 next_index = (next_index + 1) & mask_;
101 Address key = keys_[next_index];
102 if (key == not_mapped)
break;
104 int expected_index = Hash(key) & mask_;
105 if (index < next_index) {
106 if (index < expected_index && expected_index <= next_index)
continue;
108 DCHECK_GT(index, next_index);
109 if (index < expected_index || expected_index <= next_index)
continue;
112 DCHECK_EQ(not_mapped, keys_[index]);
113 DCHECK_NULL(values_[index]);
114 std::swap(keys_[index], keys_[next_index]);
115 std::swap(values_[index], values_[next_index]);
122 int IdentityMapBase::Lookup(Address key)
const {
123 int index = ScanKeysFor(key);
124 if (index < 0 && gc_counter_ != heap_->gc_count()) {
126 const_cast<IdentityMapBase*
>(
this)->Rehash();
127 index = ScanKeysFor(key);
132 int IdentityMapBase::LookupOrInsert(Address key) {
134 int index = ScanKeysFor(key);
137 if (gc_counter_ != heap_->gc_count()) Rehash();
138 index = InsertKey(key);
144 int IdentityMapBase::Hash(Address address)
const {
145 CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
146 return static_cast<int>(hasher_(address));
153 IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Address key) {
154 CHECK(!is_iterable());
155 if (capacity_ == 0) {
157 capacity_ = kInitialIdentityMapSize;
158 mask_ = kInitialIdentityMapSize - 1;
159 gc_counter_ = heap_->gc_count();
161 keys_ =
reinterpret_cast<Address*
>(NewPointerArray(capacity_));
162 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
163 for (
int i = 0;
i < capacity_;
i++) keys_[
i] = not_mapped;
164 values_ = NewPointerArray(capacity_);
165 memset(values_, 0,
sizeof(
void*) * capacity_);
167 heap_->RegisterStrongRoots(ObjectSlot(keys_),
168 ObjectSlot(keys_ + capacity_));
170 int index = LookupOrInsert(key);
171 return &values_[index];
178 IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Address key)
const {
180 CHECK(!is_iterable());
181 if (size_ == 0)
return nullptr;
183 int index = Lookup(key);
184 return index >= 0 ? &values_[index] :
nullptr;
190 bool IdentityMapBase::DeleteEntry(Address key,
void** deleted_value) {
191 CHECK(!is_iterable());
192 if (size_ == 0)
return false;
193 int index = Lookup(key);
194 if (index < 0)
return false;
195 return DeleteIndex(index, deleted_value);
198 Address IdentityMapBase::KeyAtIndex(
int index)
const {
200 DCHECK_LT(index, capacity_);
201 DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
202 CHECK(is_iterable());
206 IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(
int index)
const {
208 DCHECK_LT(index, capacity_);
209 DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
210 CHECK(is_iterable());
211 return &values_[index];
214 int IdentityMapBase::NextIndex(
int index)
const {
215 DCHECK_LE(-1, index);
216 DCHECK_LE(index, capacity_);
217 CHECK(is_iterable());
218 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
219 for (++index; index < capacity_; ++index) {
220 if (keys_[index] != not_mapped) {
227 void IdentityMapBase::Rehash() {
228 CHECK(!is_iterable());
230 gc_counter_ = heap_->gc_count();
232 std::vector<std::pair<Address, void*>> reinsert;
236 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
237 for (
int i = 0;
i < capacity_;
i++) {
238 if (keys_[
i] == not_mapped) {
241 int pos = Hash(keys_[
i]) & mask_;
242 if (pos <= last_empty || pos >
i) {
244 reinsert.push_back(std::pair<Address, void*>(keys_[
i], values_[
i]));
245 keys_[
i] = not_mapped;
246 values_[
i] =
nullptr;
253 for (
auto pair : reinsert) {
254 int index = InsertKey(pair.first);
256 values_[index] = pair.second;
260 void IdentityMapBase::Resize(
int new_capacity) {
261 CHECK(!is_iterable());
263 DCHECK_GT(new_capacity, size_);
264 int old_capacity = capacity_;
265 Address* old_keys = keys_;
266 void** old_values = values_;
268 capacity_ = new_capacity;
269 mask_ = capacity_ - 1;
270 gc_counter_ = heap_->gc_count();
273 keys_ =
reinterpret_cast<Address*
>(NewPointerArray(capacity_));
274 Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
275 for (
int i = 0;
i < capacity_;
i++) keys_[
i] = not_mapped;
276 values_ = NewPointerArray(capacity_);
277 memset(values_, 0,
sizeof(
void*) * capacity_);
279 for (
int i = 0;
i < old_capacity;
i++) {
280 if (old_keys[
i] == not_mapped)
continue;
281 int index = InsertKey(old_keys[
i]);
283 values_[index] = old_values[
i];
287 heap_->UnregisterStrongRoots(ObjectSlot(old_keys));
288 heap_->RegisterStrongRoots(ObjectSlot(keys_), ObjectSlot(keys_ + capacity_));
291 DeleteArray(old_keys);
292 DeleteArray(old_values);