Index: runtime/lib/compact_hash.dart |
diff --git a/runtime/lib/compact_hash.dart b/runtime/lib/compact_hash.dart |
index 5557230a101cd705a020e4007b22448b54679f68..923c08f3371b80d2f5e3f46a8544b9147d4a1ff3 100644 |
--- a/runtime/lib/compact_hash.dart |
+++ b/runtime/lib/compact_hash.dart |
@@ -18,7 +18,7 @@ abstract class _HashFieldBase { |
// TODO(koda): Consider also using null _index for tiny, linear-search tables. |
Uint32List _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE); |
- // Cached in-place mask for the hash pattern component. |
+ // Cached in-place mask for the hash pattern component. |
int _hashMask = _HashBase._indexSizeToHashMask(_HashBase._INITIAL_INDEX_SIZE); |
// Fixed-length list of keys (set) or key/value at even/odd indices (map). |
@@ -63,10 +63,10 @@ abstract class _HashBase { |
// The length of _index is twice the number of entries in _data, and both |
// are doubled when _data is full. Thus, _index will have a max load factor |
// of 1/2, which enables one more bit to be used for the hash. |
- // TODO(koda): Consider growing _data by factor sqrt(2), twice as often. |
+ // TODO(koda): Consider growing _data by factor sqrt(2), twice as often. |
static const int _INITIAL_INDEX_BITS = 3; |
static const int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1); |
- |
+ |
// Unused and deleted entries are marked by 0 and 1, respectively. |
static const int _UNUSED_PAIR = 0; |
static const int _DELETED_PAIR = 1; |
@@ -76,8 +76,9 @@ abstract class _HashBase { |
// as unsigned words. |
static int _indexSizeToHashMask(int indexSize) { |
int indexBits = indexSize.bitLength - 2; |
- return internal.is64Bit ? (1 << (32 - indexBits)) - 1 : |
- (1 << (30 - indexBits)) - 1; |
+ return internal.is64Bit |
+ ? (1 << (32 - indexBits)) - 1 |
+ : (1 << (30 - indexBits)) - 1; |
} |
static int _hashPattern(int fullHash, int hashMask, int size) { |
@@ -92,8 +93,9 @@ abstract class _HashBase { |
// Light, fast shuffle to mitigate bad hashCode (e.g., sequential). |
return ((i << 1) + i) & sizeMask; |
} |
+ |
static int _nextProbe(int i, int sizeMask) => (i + 1) & sizeMask; |
- |
+ |
// A self-loop is used to mark a deleted key or value. |
static bool _isDeleted(List data, Object keyOrValue) => |
identical(keyOrValue, data); |
@@ -120,8 +122,11 @@ class _IdenticalAndIdentityHashCode { |
// VM-internalized implementation of a default-constructed LinkedHashMap. |
class _InternalLinkedHashMap<K, V> extends _HashVMBase |
- with MapMixin<K, V>, _LinkedHashMapMixin<K, V>, _HashBase, |
- _OperatorEqualsAndHashCode |
+ with |
+ MapMixin<K, V>, |
+ _LinkedHashMapMixin<K, V>, |
+ _HashBase, |
+ _OperatorEqualsAndHashCode |
implements LinkedHashMap<K, V> { |
_InternalLinkedHashMap() { |
_index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE); |
@@ -132,7 +137,7 @@ class _InternalLinkedHashMap<K, V> extends _HashVMBase |
} |
} |
-class _LinkedHashMapMixin<K, V> { |
+class _LinkedHashMapMixin<K, V> { |
int get length => (_usedData >> 1) - _deletedKeys; |
bool get isEmpty => length == 0; |
bool get isNotEmpty => !isEmpty; |
@@ -147,7 +152,7 @@ class _LinkedHashMapMixin<K, V> { |
_init(_index.length << 1, _hashMask >> 1, _data, _usedData); |
} |
} |
- |
+ |
void clear() { |
if (!isEmpty) { |
// Use _data.length, since _index might be null. |
@@ -192,13 +197,13 @@ class _LinkedHashMapMixin<K, V> { |
} |
return _index.length; |
} |
- |
+ |
void _insert(K key, V value, int hashPattern, int i) { |
if (_usedData == _data.length) { |
_rehash(); |
this[key] = value; |
} else { |
- assert(1 <= hashPattern && hashPattern < (1 << 32)); |
+ assert(1 <= hashPattern && hashPattern < (1 << 32)); |
final int index = _usedData >> 1; |
assert((index & hashPattern) == 0); |
_index[i] = hashPattern | index; |
@@ -206,7 +211,7 @@ class _LinkedHashMapMixin<K, V> { |
_data[_usedData++] = value; |
} |
} |
- |
+ |
// If key is present, returns the index of the value in _data, else returns |
// the negated insertion point in _index. |
int _findValueOrInsertPoint(K key, int fullHash, int hashPattern, int size) { |
@@ -234,8 +239,8 @@ class _LinkedHashMapMixin<K, V> { |
} |
return firstDeleted >= 0 ? -firstDeleted : -i; |
} |
- |
- void operator[]=(K key, V value) { |
+ |
+ void operator []=(K key, V value) { |
final int size = _getIndexLength(); |
final int sizeMask = size - 1; |
final int fullHash = _hashCode(key); |
@@ -248,7 +253,7 @@ class _LinkedHashMapMixin<K, V> { |
_insert(key, value, hashPattern, i); |
} |
} |
- |
+ |
V putIfAbsent(K key, V ifAbsent()) { |
final int size = _getIndexLength(); |
final int sizeMask = size - 1; |
@@ -271,7 +276,7 @@ class _LinkedHashMapMixin<K, V> { |
} |
return value; |
} |
- |
+ |
V remove(Object key) { |
final int size = _getIndexLength(); |
final int sizeMask = size - 1; |
@@ -300,7 +305,7 @@ class _LinkedHashMapMixin<K, V> { |
} |
return null; |
} |
- |
+ |
// If key is absent, return _data (which is never a value). |
Object _getValueOrData(Object key) { |
final int size = _getIndexLength(); |
@@ -325,14 +330,14 @@ class _LinkedHashMapMixin<K, V> { |
} |
return _data; |
} |
- |
+ |
bool containsKey(Object key) => !identical(_data, _getValueOrData(key)); |
- |
- V operator[](Object key) { |
+ |
+ V operator [](Object key) { |
var v = _getValueOrData(key); |
return identical(_data, v) ? null : v; |
} |
- |
+ |
bool containsValue(Object value) { |
for (var v in values) { |
// Spec. says this should always use "==", also for identity maps, etc. |
@@ -359,10 +364,12 @@ class _LinkedHashMapMixin<K, V> { |
} |
class _CompactLinkedIdentityHashMap<K, V> extends _HashFieldBase |
- with MapMixin<K, V>, _LinkedHashMapMixin<K, V>, _HashBase, |
- _IdenticalAndIdentityHashCode |
+ with |
+ MapMixin<K, V>, |
+ _LinkedHashMapMixin<K, V>, |
+ _HashBase, |
+ _IdenticalAndIdentityHashCode |
implements LinkedHashMap<K, V> { |
- |
_CompactLinkedIdentityHashMap() : super(_HashBase._INITIAL_INDEX_SIZE); |
} |
@@ -378,7 +385,7 @@ class _CompactLinkedCustomHashMap<K, V> extends _HashFieldBase |
bool _equals(e1, e2) => _equality(e1, e2); |
bool containsKey(Object o) => _validKey(o) ? super.containsKey(o) : false; |
- V operator[](Object o) => _validKey(o) ? super[o] : null; |
+ V operator [](Object o) => _validKey(o) ? super[o] : null; |
V remove(Object o) => _validKey(o) ? super.remove(o) : null; |
_CompactLinkedCustomHashMap(this._equality, this._hasher, validKey) |
@@ -395,8 +402,8 @@ class _CompactIterable<E> extends IterableBase<E> { |
final int _offset; |
final int _step; |
- _CompactIterable(this._table, this._data, this._len, |
- this._offset, this._step); |
+ _CompactIterable( |
+ this._table, this._data, this._len, this._offset, this._step); |
Iterator<E> get iterator => |
new _CompactIterator<E>(_table, _data, _len, _offset, _step); |
@@ -415,8 +422,9 @@ class _CompactIterator<E> implements Iterator<E> { |
final int _checkSum; |
E current; |
- _CompactIterator(table, this._data, this._len, this._offset, this._step) : |
- _table = table, _checkSum = table._checkSum; |
+ _CompactIterator(table, this._data, this._len, this._offset, this._step) |
+ : _table = table, |
+ _checkSum = table._checkSum; |
bool moveNext() { |
if (_table._isModifiedSince(_data, _checkSum)) { |
@@ -439,7 +447,6 @@ class _CompactIterator<E> implements Iterator<E> { |
class _CompactLinkedHashSet<E> extends _HashFieldBase |
with _HashBase, _OperatorEqualsAndHashCode, SetMixin<E> |
implements LinkedHashSet<E> { |
- |
_CompactLinkedHashSet() : super(_HashBase._INITIAL_INDEX_SIZE >> 1) { |
assert(_HashBase._UNUSED_PAIR == 0); |
} |
@@ -525,7 +532,7 @@ class _CompactLinkedHashSet<E> extends _HashFieldBase |
if (pair != _HashBase._DELETED_PAIR) { |
final int d = hashPattern ^ pair; |
if (d < maxEntries && _equals(key, _data[d])) { |
- return _data[d]; // Note: Must return the existing key. |
+ return _data[d]; // Note: Must return the existing key. |
} |
} |
i = _HashBase._nextProbe(i, sizeMask); |
@@ -574,13 +581,12 @@ class _CompactLinkedHashSet<E> extends _HashFieldBase |
Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this); |
} |
-class _CompactLinkedIdentityHashSet<E> |
- extends _CompactLinkedHashSet<E> with _IdenticalAndIdentityHashCode { |
+class _CompactLinkedIdentityHashSet<E> extends _CompactLinkedHashSet<E> |
+ with _IdenticalAndIdentityHashCode { |
Set<E> toSet() => new _CompactLinkedIdentityHashSet<E>()..addAll(this); |
} |
-class _CompactLinkedCustomHashSet<E> |
- extends _CompactLinkedHashSet<E> { |
+class _CompactLinkedCustomHashSet<E> extends _CompactLinkedHashSet<E> { |
final _equality; |
final _hasher; |
final _validKey; |
@@ -597,5 +603,5 @@ class _CompactLinkedCustomHashSet<E> |
Set<E> toSet() => |
new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey) |
- ..addAll(this); |
+ ..addAll(this); |
} |