identity-map.cc 8.76 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

namespace v8 {
namespace internal {

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

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
int IdentityMapBase::ScanKeysFor(Object* address) const {
47
  int start = Hash(address) & mask_;
48
  Object* not_mapped = heap_->not_mapped_symbol();
49
  for (int index = start; index < capacity_; index++) {
50
    if (keys_[index] == address) return index;  // Found.
51
    if (keys_[index] == not_mapped) return -1;  // Not found.
52 53 54
  }
  for (int index = 0; index < start; index++) {
    if (keys_[index] == address) return index;  // Found.
55
    if (keys_[index] == not_mapped) return -1;  // Not found.
56 57 58 59
  }
  return -1;
}

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

81 82 83 84 85 86 87 88 89
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);

90
  if (size_ * kResizeFactor < capacity_ / kResizeFactor) {
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
    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;
    }
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
    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);
  }
  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));
}
147 148 149 150 151

// 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
152
IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
153 154
  CHECK(!is_iterable());  // Don't allow insertion while iterable.
  if (capacity_ == 0) {
155
    // Allocate the initial storage for keys and values.
156
    capacity_ = kInitialIdentityMapSize;
157 158 159
    mask_ = kInitialIdentityMapSize - 1;
    gc_counter_ = heap_->gc_count();

160
    keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
161
    Object* not_mapped = heap_->not_mapped_symbol();
162 163 164 165 166
    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_);
167
  }
168 169
  int index = LookupOrInsert(key);
  return &values_[index];
170 171 172 173 174 175
}

// 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}
176 177 178
IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
  // Don't allow find by key while iterable (might rehash).
  CHECK(!is_iterable());
179
  if (size_ == 0) return nullptr;
180 181 182 183
  // Remove constness since lookup might have to rehash.
  int index = Lookup(key);
  return index >= 0 ? &values_[index] : nullptr;
}
184

185 186 187 188 189 190 191 192 193 194
// 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);
195 196
}

197 198 199 200 201 202 203 204 205 206 207 208 209
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();
210
  for (++index; index < capacity_; ++index) {
211 212 213 214 215 216
    if (keys_[index] != not_mapped) {
      return index;
    }
  }
  return capacity_;
}
217 218

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

251 252 253 254 255
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_;
256 257 258
  Object** old_keys = keys_;
  void** old_values = values_;

259 260
  capacity_ = new_capacity;
  mask_ = capacity_ - 1;
261
  gc_counter_ = heap_->gc_count();
262
  size_ = 0;
263

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

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

  // Unregister old keys and register new keys.
  heap_->UnregisterStrongRoots(old_keys);
279 280 281 282 283
  heap_->RegisterStrongRoots(keys_, keys_ + capacity_);

  // Delete old storage;
  DeleteArray(old_keys);
  DeleteArray(old_values);
284
}
285

286 287
}  // namespace internal
}  // namespace v8