blob: e45e9c8c86be9a117b57ecaea5062cadff466c84 [file] [log] [blame]
// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "vm/weak_table.h"
#include "platform/assert.h"
#include "vm/raw_object.h"
namespace dart {
intptr_t WeakTable::SizeFor(intptr_t count, intptr_t size) {
intptr_t result = size;
if (count <= (size / 4)) {
// Reduce the capacity.
result = size / 2;
} else {
// Increase the capacity.
result = size * 2;
if (result < size) {
FATAL("Reached impossible state of having more weak table entries"
" than memory available for heap objects.");
}
}
if (result < kMinSize) {
result = kMinSize;
}
return result;
}
void WeakTable::SetValue(RawObject* key, intptr_t val) {
intptr_t mask = size() - 1;
intptr_t idx = Hash(key) & mask;
intptr_t empty_idx = -1;
RawObject* obj = ObjectAt(idx);
while (obj != NULL) {
if (obj == key) {
SetValueAt(idx, val);
return;
} else if ((empty_idx < 0) &&
(reinterpret_cast<intptr_t>(obj) == kDeletedEntry)) {
empty_idx = idx; // Insert at this location if not found.
}
idx = (idx + 1) & mask;
obj = ObjectAt(idx);
}
if (val == 0) {
// Do not enter an invalid value. Associating 0 with a key deletes it from
// this weak table above in SetValueAt. If the key was not present in the
// weak table we are done.
return;
}
if (empty_idx >= 0) {
// We will be reusing a slot below.
set_used(used() - 1);
idx = empty_idx;
}
ASSERT(!IsValidEntryAt(idx));
// Set the key and value.
SetObjectAt(idx, key);
SetValueAt(idx, val);
// Update the counts.
set_used(used() + 1);
set_count(count() + 1);
// Rehash if needed to ensure that there are empty slots available.
if (used_ >= limit()) {
Rehash();
}
}
void WeakTable::Reset() {
intptr_t* old_data = data_;
used_ = 0;
count_ = 0;
size_ = kMinSize;
data_ = reinterpret_cast<intptr_t*>(calloc(size_, kEntrySize * kWordSize));
free(old_data);
}
void WeakTable::Rehash() {
intptr_t old_size = size();
intptr_t* old_data = data_;
intptr_t new_size = SizeFor(count(), size());
ASSERT(Utils::IsPowerOfTwo(new_size));
intptr_t* new_data = reinterpret_cast<intptr_t*>(
calloc(new_size, kEntrySize * kWordSize));
intptr_t mask = new_size - 1;
set_used(0);
for (intptr_t i = 0; i < old_size; i++) {
if (IsValidEntryAt(i)) {
// Find the new hash location for this entry.
RawObject* key = ObjectAt(i);
intptr_t idx = Hash(key) & mask;
RawObject* obj = reinterpret_cast<RawObject*>(new_data[ObjectIndex(idx)]);
while (obj != NULL) {
ASSERT(obj != key); // Duplicate entry is not expected.
idx = (idx + 1) & mask;
obj = reinterpret_cast<RawObject*>(new_data[ObjectIndex(idx)]);
}
new_data[ObjectIndex(idx)] = reinterpret_cast<intptr_t>(key);
new_data[ValueIndex(idx)] = ValueAt(i);
set_used(used() + 1);
}
}
// We should only have used valid entries.
ASSERT(used() == count());
// Switch to using the newly allocated backing store.
size_ = new_size;
data_ = new_data;
free(old_data);
}
} // namespace dart