Index: runtime/lib/expando_patch.dart |
=================================================================== |
--- runtime/lib/expando_patch.dart (revision 24817) |
+++ runtime/lib/expando_patch.dart (working copy) |
@@ -3,61 +3,135 @@ |
// BSD-style license that can be found in the LICENSE file. |
patch class Expando<T> { |
- /* patch */ Expando([this.name]) : _data = new List(); |
+ /* patch */ Expando([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 doCompact = false; |
- var result = null; |
- for (int i = 0; i < _data.length; ++i) { |
- var key = _data[i].key; |
- if (identical(key, object)) { |
- result = _data[i].value; |
- break; |
+ |
+ var mask = _size - 1; |
+ var idx = object.hashCode & 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; |
} |
- if (key == null) { |
- doCompact = true; |
- _data[i] = null; |
- } |
+ idx = (idx + 1) & mask; |
+ wp = _data[idx]; |
} |
- if (doCompact) { |
- _data = _data.where((e) => (e != null)).toList(); |
- } |
- return result; |
+ |
+ return null; |
} |
/* patch */ void operator[]=(Object object, T value) { |
_checkType(object); |
- var doCompact = false; |
- int i = 0; |
- for (; i < _data.length; ++i) { |
- var key = _data[i].key; |
- if (identical(key, object)) { |
- break; |
+ |
+ var mask = _size - 1; |
+ var idx = object.hashCode & 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. |
+ } |
} |
- if (key == null) { |
- doCompact = true; |
- _data[i] = null; |
+ 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++; |
} |
} |
- if (i != _data.length && value == null) { |
- doCompact = true; |
- _data[i] = null; |
- } else if (i != _data.length) { |
- _data[i].value = value; |
- } else { |
- _data.add(new _WeakProperty(object, value)); |
+ |
+ 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; |
} |
- if (doCompact) { |
- _data = _data.where((e) => (e != null)).toList(); |
+ 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) && (entry.key != null)) { |
+ this[entry.key] = entry.value; |
+ } |
} |
} |
static _checkType(object) { |
- if (object == null || object is bool || object is num || object is String) { |
+ if ((object == null) || |
+ (object is bool) || |
+ (object is num) || |
+ (object is String)) { |
throw new ArgumentError(object); |
} |
} |
+ get _size => _data.length; |
+ get _limit => (3 * (_size ~/ 4)); |
+ |
List _data; |
+ int _used; // Number of used (active and deleted) slots. |
} |