identity-map.cc 8.92 KB
Newer Older
1 2 3 4
// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/identity-map.h"
6

7
#include "src/base/functional.h"
8
#include "src/heap/heap-inl.h"
9 10 11 12 13 14 15

namespace v8 {
namespace internal {

static const int kInitialIdentityMapSize = 4;
static const int kResizeFactor = 4;

16 17 18 19 20
IdentityMapBase::~IdentityMapBase() {
  // Clear must be called by the subclass to avoid calling the virtual
  // DeleteArray function from the destructor.
  DCHECK_NULL(keys_);
}
21 22 23

void IdentityMapBase::Clear() {
  if (keys_) {
24
    DCHECK(!is_iterable());
25
    heap_->UnregisterStrongRoots(keys_);
26 27
    DeleteArray(keys_);
    DeleteArray(values_);
28 29 30
    keys_ = nullptr;
    values_ = nullptr;
    size_ = 0;
31
    capacity_ = 0;
32 33
    mask_ = 0;
  }
34 35
}

36 37 38
void IdentityMapBase::EnableIteration() {
  CHECK(!is_iterable());
  is_iterable_ = true;
39 40
}

41 42 43
void IdentityMapBase::DisableIteration() {
  CHECK(is_iterable());
  is_iterable_ = false;
44

45 46 47 48
  // We might need to resize due to iterator deletion - do this now.
  if (size_ * kResizeFactor < capacity_ / kResizeFactor) {
    Resize(capacity_ / kResizeFactor);
  }
49 50
}

51
int IdentityMapBase::ScanKeysFor(Object* address) const {
52
  int start = Hash(address) & mask_;
53
  Object* not_mapped = heap_->not_mapped_symbol();
54
  for (int index = start; index < capacity_; index++) {
55
    if (keys_[index] == address) return index;  // Found.
56
    if (keys_[index] == not_mapped) return -1;  // Not found.
57 58 59
  }
  for (int index = 0; index < start; index++) {
    if (keys_[index] == address) return index;  // Found.
60
    if (keys_[index] == not_mapped) return -1;  // Not found.
61 62 63 64
  }
  return -1;
}

65
int IdentityMapBase::InsertKey(Object* address) {
66
  Object* not_mapped = heap_->not_mapped_symbol();
67 68
  while (true) {
    int start = Hash(address) & mask_;
69
    int limit = capacity_ / 2;
70 71 72
    // Search up to {limit} entries.
    for (int index = start; --limit > 0; index = (index + 1) & mask_) {
      if (keys_[index] == address) return index;  // Found.
73
      if (keys_[index] == not_mapped) {           // Free entry.
74 75 76 77
        keys_[index] = address;
        return index;
      }
    }
78 79
    // Should only have to resize once, since we grow 4x.
    Resize(capacity_ * kResizeFactor);
80 81 82 83 84
  }
  UNREACHABLE();
  return -1;
}

85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
void* IdentityMapBase::DeleteIndex(int index) {
  void* ret_value = values_[index];
  Object* not_mapped = heap_->not_mapped_symbol();
  DCHECK_NE(keys_[index], not_mapped);
  keys_[index] = not_mapped;
  values_[index] = nullptr;
  size_--;
  DCHECK_GE(size_, 0);

  if (!is_iterable() && (size_ * kResizeFactor < capacity_ / kResizeFactor)) {
    Resize(capacity_ / kResizeFactor);
    return ret_value;  // No need to fix collisions as resize reinserts keys.
  }

  // Move any collisions to their new correct location.
  int next_index = index;
  for (;;) {
    next_index = (next_index + 1) & mask_;
    Object* key = keys_[next_index];
    if (key == not_mapped) break;

    int expected_index = Hash(key) & mask_;
    if (index < next_index) {
      if (index < expected_index && expected_index <= next_index) continue;
    } else {
      DCHECK_GT(index, next_index);
      if (index < expected_index || expected_index <= next_index) continue;
    }
    DCHECK_EQ(not_mapped, keys_[index]);
    DCHECK_NULL(values_[index]);
    std::swap(keys_[index], keys_[next_index]);
    std::swap(values_[index], values_[next_index]);
    index = next_index;
  }

  return ret_value;
}

int IdentityMapBase::Lookup(Object* key) const {
  int index = ScanKeysFor(key);
  if (index < 0 && gc_counter_ != heap_->gc_count()) {
    // Miss; rehash if there was a GC, then lookup again.
    const_cast<IdentityMapBase*>(this)->Rehash();
    index = ScanKeysFor(key);
  }
  return index;
}

int IdentityMapBase::LookupOrInsert(Object* key) {
  // Perform an optimistic lookup.
  int index = ScanKeysFor(key);
  if (index < 0) {
    // Miss; rehash if there was a GC, then insert.
    if (gc_counter_ != heap_->gc_count()) Rehash();
    index = InsertKey(key);
    size_++;
    DCHECK_LE(size_, capacity_);
  }
  DCHECK_GE(index, 0);
  return index;
}

int IdentityMapBase::Hash(Object* address) const {
  CHECK_NE(address, heap_->not_mapped_symbol());
  uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
  return static_cast<int>(hasher_(raw_address));
}
152 153 154 155 156

// Searches this map for the given key using the object's address
// as the identity, returning:
//    found => a pointer to the storage location for the value
//    not found => a pointer to a new storage location for the value
yangguo's avatar
yangguo committed
157
IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
158 159
  CHECK(!is_iterable());  // Don't allow insertion while iterable.
  if (capacity_ == 0) {
160
    // Allocate the initial storage for keys and values.
161
    capacity_ = kInitialIdentityMapSize;
162 163 164
    mask_ = kInitialIdentityMapSize - 1;
    gc_counter_ = heap_->gc_count();

165
    keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
166
    Object* not_mapped = heap_->not_mapped_symbol();
167 168 169 170 171
    for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
    values_ = NewPointerArray(capacity_);
    memset(values_, 0, sizeof(void*) * capacity_);

    heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
172
  }
173 174
  int index = LookupOrInsert(key);
  return &values_[index];
175 176 177 178 179 180
}

// Searches this map for the given key using the object's address
// as the identity, returning:
//    found => a pointer to the storage location for the value
//    not found => {nullptr}
181 182 183
IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
  // Don't allow find by key while iterable (might rehash).
  CHECK(!is_iterable());
184
  if (size_ == 0) return nullptr;
185 186 187 188
  // Remove constness since lookup might have to rehash.
  int index = Lookup(key);
  return index >= 0 ? &values_[index] : nullptr;
}
189

190 191 192 193 194 195 196 197 198 199
// Deletes the given key from the map using the object's address as the
// identity, returning:
//    found => the value
//    not found => {nullptr}
void* IdentityMapBase::DeleteEntry(Object* key) {
  CHECK(!is_iterable());  // Don't allow deletion by key while iterable.
  if (size_ == 0) return nullptr;
  int index = Lookup(key);
  if (index < 0) return nullptr;  // No entry found.
  return DeleteIndex(index);
200 201
}

202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221
IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
  DCHECK_LE(0, index);
  DCHECK_LT(index, capacity_);
  DCHECK_NE(keys_[index], heap_->not_mapped_symbol());
  CHECK(is_iterable());  // Must be iterable to access by index;
  return &values_[index];
}

int IdentityMapBase::NextIndex(int index) const {
  DCHECK_LE(-1, index);
  DCHECK_LE(index, capacity_);
  CHECK(is_iterable());  // Must be iterable to access by index;
  Object* not_mapped = heap_->not_mapped_symbol();
  for (index++; index < capacity_; index++) {
    if (keys_[index] != not_mapped) {
      return index;
    }
  }
  return capacity_;
}
222 223

void IdentityMapBase::Rehash() {
224
  CHECK(!is_iterable());  // Can't rehash while iterating.
225 226 227
  // Record the current GC counter.
  gc_counter_ = heap_->gc_count();
  // Assume that most objects won't be moved.
228
  std::vector<std::pair<Object*, void*>> reinsert;
229 230 231
  // Search the table looking for keys that wouldn't be found with their
  // current hashcode and evacuate them.
  int last_empty = -1;
232
  Object* not_mapped = heap_->not_mapped_symbol();
233
  for (int i = 0; i < capacity_; i++) {
234
    if (keys_[i] == not_mapped) {
235 236 237 238 239 240
      last_empty = i;
    } else {
      int pos = Hash(keys_[i]) & mask_;
      if (pos <= last_empty || pos > i) {
        // Evacuate an entry that is in the wrong place.
        reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
241
        keys_[i] = not_mapped;
242 243 244 245 246 247 248
        values_[i] = nullptr;
        last_empty = i;
      }
    }
  }
  // Reinsert all the key/value pairs that were in the wrong place.
  for (auto pair : reinsert) {
249
    int index = InsertKey(pair.first);
250 251 252 253 254
    DCHECK_GE(index, 0);
    values_[index] = pair.second;
  }
}

255 256 257 258 259
void IdentityMapBase::Resize(int new_capacity) {
  CHECK(!is_iterable());  // Can't resize while iterating.
  // Resize the internal storage and reinsert all the key/value pairs.
  DCHECK_GT(new_capacity, size_);
  int old_capacity = capacity_;
260 261 262
  Object** old_keys = keys_;
  void** old_values = values_;

263 264
  capacity_ = new_capacity;
  mask_ = capacity_ - 1;
265 266
  gc_counter_ = heap_->gc_count();

267
  keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
268
  Object* not_mapped = heap_->not_mapped_symbol();
269 270 271
  for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
  values_ = NewPointerArray(capacity_);
  memset(values_, 0, sizeof(void*) * capacity_);
272

273
  for (int i = 0; i < old_capacity; i++) {
274
    if (old_keys[i] == not_mapped) continue;
275
    int index = InsertKey(old_keys[i]);
276 277 278 279 280 281
    DCHECK_GE(index, 0);
    values_[index] = old_values[i];
  }

  // Unregister old keys and register new keys.
  heap_->UnregisterStrongRoots(old_keys);
282 283 284 285 286
  heap_->RegisterStrongRoots(keys_, keys_ + capacity_);

  // Delete old storage;
  DeleteArray(old_keys);
  DeleteArray(old_values);
287
}
288

289 290
}  // namespace internal
}  // namespace v8