| 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);
|
| }
|
|
|