blob: df0234d4d8ab0fb01a513ea64094f20852b38e90 [file] [log] [blame]
// Copyright (c) 2012, 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.
patch class Expando<T> {
/* patch */ Expando([String this.name])
: _data = new List(_minSize),
_used = 0;
static const _minSize = 8;
static final _deletedEntry = new _WeakProperty(null, null);
/* patch */ T operator[](Object object) {
_checkType(object);
var mask = _size - 1;
var idx = object._identityHashCode & mask;
var wp = _data[idx];
while (wp != null) {
if (identical(wp.key, object)) {
return wp.value;
} else if (wp.key == null) {
// This entry has been cleared by the GC.
_data[idx] = _deletedEntry;
}
idx = (idx + 1) & mask;
wp = _data[idx];
}
return null;
}
/* patch */ void operator[]=(Object object, T value) {
_checkType(object);
var mask = _size - 1;
var idx = object._identityHashCode & mask;
var empty_idx = -1;
var wp = _data[idx];
while (wp != null) {
if (identical(wp.key, object)) {
if (value != null) {
// Update the associated value.
wp.value = value;
} else {
// Mark the entry as deleted.
_data[idx] = _deletedEntry;
}
return;
} else if ((empty_idx < 0) && identical(wp, _deletedEntry)) {
empty_idx = idx; // Insert at this location if not found.
} else if (wp.key == null) {
// This entry has been cleared by the GC.
_data[idx] = _deletedEntry;
if (empty_idx < 0) {
empty_idx = idx; // Insert at this location if not found.
}
}
idx = (idx + 1) & mask;
wp = _data[idx];
}
if (value == null) {
// Not entering a null value. We just needed to make sure to clear an
// existing value if it existed.
return;
}
if (empty_idx >= 0) {
// We will be reusing the empty slot below.
_used--;
idx = empty_idx;
}
if (_used < _limit) {
_data[idx] = new _WeakProperty(object, value);
_used++;
return;
}
// Grow/reallocate if too many slots have been used.
_rehash();
this[object] = value; // Recursively add the value.
}
_rehash() {
// Determine the population count of the map to allocate an appropriately
// sized map below.
var count = 0;
var old_data = _data;
var len = old_data.length;
for (var i = 0; i < len; i++) {
var entry = old_data[i];
if ((entry != null) && (entry.key != null)) {
// Only count non-cleared entries.
count++;
}
}
var new_size = _size;
if (count <= (new_size >> 2)) {
new_size = new_size >> 1;
} else if (count > (new_size >> 1)) {
new_size = new_size << 1;
}
new_size = (new_size < _minSize) ? _minSize : new_size;
// Reset the mappings to empty so that we can just add the existing
// valid entries.
_data = new List(new_size);
_used = 0;
for (var i = 0; i < old_data.length; i++) {
var entry = old_data[i];
if (entry != null) {
// Ensure that the entry.key is not cleared between checking for it and
// inserting it into the new table.
var val = entry.value;
var key = entry.key;
if (key != null) {
this[key] = val;
}
}
}
}
static _checkType(object) {
if ((object == null) ||
(object is bool) ||
(object is num) ||
(object is String)) {
throw new ArgumentError.value(object,
"Expandos are not allowed on strings, numbers, booleans or null");
}
}
get _size => _data.length;
get _limit => (3 * (_size ~/ 4));
List _data;
int _used; // Number of used (active and deleted) slots.
}