V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
identity-map.cc
1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "src/identity-map.h"
6 
7 #include "src/base/functional.h"
8 #include "src/heap/heap.h"
9 #include "src/roots-inl.h"
10 
11 namespace v8 {
12 namespace internal {
13 
14 static const int kInitialIdentityMapSize = 4;
15 static const int kResizeFactor = 2;
16 
17 IdentityMapBase::~IdentityMapBase() {
18  // Clear must be called by the subclass to avoid calling the virtual
19  // DeleteArray function from the destructor.
20  DCHECK_NULL(keys_);
21 }
22 
23 void IdentityMapBase::Clear() {
24  if (keys_) {
25  DCHECK(!is_iterable());
26  heap_->UnregisterStrongRoots(ObjectSlot(keys_));
27  DeleteArray(keys_);
28  DeleteArray(values_);
29  keys_ = nullptr;
30  values_ = nullptr;
31  size_ = 0;
32  capacity_ = 0;
33  mask_ = 0;
34  }
35 }
36 
37 void IdentityMapBase::EnableIteration() {
38  CHECK(!is_iterable());
39  is_iterable_ = true;
40 }
41 
42 void IdentityMapBase::DisableIteration() {
43  CHECK(is_iterable());
44  is_iterable_ = false;
45 }
46 
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; // Found.
52  if (keys_[index] == not_mapped) return -1; // Not found.
53  }
54  for (int index = 0; index < start; index++) {
55  if (keys_[index] == address) return index; // Found.
56  if (keys_[index] == not_mapped) return -1; // Not found.
57  }
58  return -1;
59 }
60 
61 int IdentityMapBase::InsertKey(Address address) {
62  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
63  while (true) {
64  int start = Hash(address) & mask_;
65  int limit = capacity_ / 2;
66  // Search up to {limit} entries.
67  for (int index = start; --limit > 0; index = (index + 1) & mask_) {
68  if (keys_[index] == address) return index; // Found.
69  if (keys_[index] == not_mapped) { // Free entry.
70  size_++;
71  DCHECK_LE(size_, capacity_);
72  keys_[index] = address;
73  return index;
74  }
75  }
76  // Should only have to resize once, since we grow 4x.
77  Resize(capacity_ * kResizeFactor);
78  }
79  UNREACHABLE();
80 }
81 
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;
88  size_--;
89  DCHECK_GE(size_, 0);
90 
91  if (capacity_ > kInitialIdentityMapSize &&
92  size_ * kResizeFactor < capacity_ / kResizeFactor) {
93  Resize(capacity_ / kResizeFactor);
94  return true; // No need to fix collisions as resize reinserts keys.
95  }
96 
97  // Move any collisions to their new correct location.
98  int next_index = index;
99  for (;;) {
100  next_index = (next_index + 1) & mask_;
101  Address key = keys_[next_index];
102  if (key == not_mapped) break;
103 
104  int expected_index = Hash(key) & mask_;
105  if (index < next_index) {
106  if (index < expected_index && expected_index <= next_index) continue;
107  } else {
108  DCHECK_GT(index, next_index);
109  if (index < expected_index || expected_index <= next_index) continue;
110  }
111 
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]);
116  index = next_index;
117  }
118 
119  return true;
120 }
121 
122 int IdentityMapBase::Lookup(Address key) const {
123  int index = ScanKeysFor(key);
124  if (index < 0 && gc_counter_ != heap_->gc_count()) {
125  // Miss; rehash if there was a GC, then lookup again.
126  const_cast<IdentityMapBase*>(this)->Rehash();
127  index = ScanKeysFor(key);
128  }
129  return index;
130 }
131 
132 int IdentityMapBase::LookupOrInsert(Address key) {
133  // Perform an optimistic lookup.
134  int index = ScanKeysFor(key);
135  if (index < 0) {
136  // Miss; rehash if there was a GC, then insert.
137  if (gc_counter_ != heap_->gc_count()) Rehash();
138  index = InsertKey(key);
139  }
140  DCHECK_GE(index, 0);
141  return index;
142 }
143 
144 int IdentityMapBase::Hash(Address address) const {
145  CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
146  return static_cast<int>(hasher_(address));
147 }
148 
149 // Searches this map for the given key using the object's address
150 // as the identity, returning:
151 // found => a pointer to the storage location for the value
152 // not found => a pointer to a new storage location for the value
153 IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Address key) {
154  CHECK(!is_iterable()); // Don't allow insertion while iterable.
155  if (capacity_ == 0) {
156  // Allocate the initial storage for keys and values.
157  capacity_ = kInitialIdentityMapSize;
158  mask_ = kInitialIdentityMapSize - 1;
159  gc_counter_ = heap_->gc_count();
160 
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_);
166 
167  heap_->RegisterStrongRoots(ObjectSlot(keys_),
168  ObjectSlot(keys_ + capacity_));
169  }
170  int index = LookupOrInsert(key);
171  return &values_[index];
172 }
173 
174 // Searches this map for the given key using the object's address
175 // as the identity, returning:
176 // found => a pointer to the storage location for the value
177 // not found => {nullptr}
178 IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Address key) const {
179  // Don't allow find by key while iterable (might rehash).
180  CHECK(!is_iterable());
181  if (size_ == 0) return nullptr;
182  // Remove constness since lookup might have to rehash.
183  int index = Lookup(key);
184  return index >= 0 ? &values_[index] : nullptr;
185 }
186 
187 // Deletes the given key from the map using the object's address as the
188 // identity, returning true iff the key was found (in which case, the value
189 // argument will be set to the deleted entry's value).
190 bool IdentityMapBase::DeleteEntry(Address key, void** deleted_value) {
191  CHECK(!is_iterable()); // Don't allow deletion by key while iterable.
192  if (size_ == 0) return false;
193  int index = Lookup(key);
194  if (index < 0) return false; // No entry found.
195  return DeleteIndex(index, deleted_value);
196 }
197 
198 Address IdentityMapBase::KeyAtIndex(int index) const {
199  DCHECK_LE(0, index);
200  DCHECK_LT(index, capacity_);
201  DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
202  CHECK(is_iterable()); // Must be iterable to access by index;
203  return keys_[index];
204 }
205 
206 IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
207  DCHECK_LE(0, index);
208  DCHECK_LT(index, capacity_);
209  DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
210  CHECK(is_iterable()); // Must be iterable to access by index;
211  return &values_[index];
212 }
213 
214 int IdentityMapBase::NextIndex(int index) const {
215  DCHECK_LE(-1, index);
216  DCHECK_LE(index, capacity_);
217  CHECK(is_iterable()); // Must be iterable to access by index;
218  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
219  for (++index; index < capacity_; ++index) {
220  if (keys_[index] != not_mapped) {
221  return index;
222  }
223  }
224  return capacity_;
225 }
226 
227 void IdentityMapBase::Rehash() {
228  CHECK(!is_iterable()); // Can't rehash while iterating.
229  // Record the current GC counter.
230  gc_counter_ = heap_->gc_count();
231  // Assume that most objects won't be moved.
232  std::vector<std::pair<Address, void*>> reinsert;
233  // Search the table looking for keys that wouldn't be found with their
234  // current hashcode and evacuate them.
235  int last_empty = -1;
236  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
237  for (int i = 0; i < capacity_; i++) {
238  if (keys_[i] == not_mapped) {
239  last_empty = i;
240  } else {
241  int pos = Hash(keys_[i]) & mask_;
242  if (pos <= last_empty || pos > i) {
243  // Evacuate an entry that is in the wrong place.
244  reinsert.push_back(std::pair<Address, void*>(keys_[i], values_[i]));
245  keys_[i] = not_mapped;
246  values_[i] = nullptr;
247  last_empty = i;
248  size_--;
249  }
250  }
251  }
252  // Reinsert all the key/value pairs that were in the wrong place.
253  for (auto pair : reinsert) {
254  int index = InsertKey(pair.first);
255  DCHECK_GE(index, 0);
256  values_[index] = pair.second;
257  }
258 }
259 
260 void IdentityMapBase::Resize(int new_capacity) {
261  CHECK(!is_iterable()); // Can't resize while iterating.
262  // Resize the internal storage and reinsert all the key/value pairs.
263  DCHECK_GT(new_capacity, size_);
264  int old_capacity = capacity_;
265  Address* old_keys = keys_;
266  void** old_values = values_;
267 
268  capacity_ = new_capacity;
269  mask_ = capacity_ - 1;
270  gc_counter_ = heap_->gc_count();
271  size_ = 0;
272 
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_);
278 
279  for (int i = 0; i < old_capacity; i++) {
280  if (old_keys[i] == not_mapped) continue;
281  int index = InsertKey(old_keys[i]);
282  DCHECK_GE(index, 0);
283  values_[index] = old_values[i];
284  }
285 
286  // Unregister old keys and register new keys.
287  heap_->UnregisterStrongRoots(ObjectSlot(old_keys));
288  heap_->RegisterStrongRoots(ObjectSlot(keys_), ObjectSlot(keys_ + capacity_));
289 
290  // Delete old storage;
291  DeleteArray(old_keys);
292  DeleteArray(old_values);
293 }
294 
295 } // namespace internal
296 } // namespace v8
Definition: libplatform.h:13