sdk/lib/_internal/vm/lib/compact_hash.dart

// Copyright (c) 2015, 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.

// part of "collection_patch.dart";

// Hash table with open addressing that separates the index from keys/values.

// This function takes care of rehashing of the linked hashmaps in [objects]. We
// do this eagerly after snapshot deserialization.
@pragma("vm:entry-point", "call")
void _rehashObjects(List objects) {
  final int length = objects.length;
  for (int i = 0; i < length; ++i) {
    objects[i]._regenerateIndex();
  }
}

abstract class _HashFieldBase {
  // Each occupied entry in _index is a fixed-size integer that encodes a pair:
  //   [ hash pattern for key | index of entry in _data ]
  // The hash pattern is based on hashCode, but is guaranteed to be non-zero.
  // The length of _index is always a power of two, and there is always at
  // least one unoccupied entry.
  // NOTE: When maps are deserialized, their _index and _hashMask is regenerated
  // eagerly by _regenerateIndex.
  Uint32List _index = _uninitializedIndex;

  // Cached in-place mask for the hash pattern component.
  int _hashMask = _HashBase._UNINITIALIZED_HASH_MASK;

  // Fixed-length list of keys (set) or key/value at even/odd indices (map).
  //
  // Can be either a mutable or immutable list.
  List _data = _uninitializedData;

  // Length of _data that is used (i.e., keys + values for a map).
  int _usedData = 0;

  // Number of deleted keys.
  int _deletedKeys = 0;

  // Note: All fields are initialized in a single constructor so that the VM
  // recognizes they cannot hold null values. This makes a big (20%) performance
  // difference on some operations.
  _HashFieldBase(int dataSize);
}

// Base class for VM-internal classes; keep in sync with _HashFieldBase.
abstract class _HashVMBase {
  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:typed_data#_Uint32List")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_getIndex")
  external Uint32List get _index;
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_setIndex")
  external void set _index(Uint32List value);

  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:core#_Smi")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_getHashMask")
  external int get _hashMask;
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_setHashMask")
  external void set _hashMask(int value);

  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:core#_List")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_getData")
  external List get _data;
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_setData")
  external void set _data(List value);

  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:core#_Smi")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_getUsedData")
  external int get _usedData;
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_setUsedData")
  external void set _usedData(int value);

  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:core#_Smi")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_getDeletedKeys")
  external int get _deletedKeys;
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  @pragma("vm:external-name", "LinkedHashBase_setDeletedKeys")
  external void set _deletedKeys(int value);
}

// Base class for VM-internal classes; keep in sync with _HashFieldBase.
abstract class _HashVMImmutableBase extends _HashVMBase {
  // The data is an immutable list rather than a mutable list.
  @pragma("vm:recognized", "other")
  @pragma("vm:exact-result-type", "dart:core#_ImmutableList")
  @pragma("vm:prefer-inline")
  List get _data native "ImmutableLinkedHashBase_getData";

  // The index is nullable rather than not nullable.
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  Uint32List? get _indexNullable native "ImmutableLinkedHashBase_getIndex";
  Uint32List get _index => _indexNullable!;

  // Uses store-release atomic.
  @pragma("vm:recognized", "other")
  @pragma("vm:prefer-inline")
  void set _index(Uint32List value)
      native "ImmutableLinkedHashBase_setIndexStoreRelease";
}

// This mixin can be applied to _HashFieldBase or _HashVMBase (for
// normal and VM-internalized classes, respectiveley), which provide the
// actual fields/accessors that this mixin assumes.
// TODO(koda): Consider moving field comments to _HashFieldBase.
abstract class _HashBase implements _HashVMBase {
  // The number of bits used for each component is determined by table size.
  // If initialized, the length of _index is (at least) 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.
  static const int _INITIAL_INDEX_BITS = 2;
  static const int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1);
  static const int _UNINITIALIZED_INDEX_SIZE = 1;
  static const int _UNINITIALIZED_HASH_MASK = 0;

  // Unused and deleted entries are marked by 0 and 1, respectively.
  static const int _UNUSED_PAIR = 0;
  static const int _DELETED_PAIR = 1;

  // On 32-bit, the top bits are wasted to avoid Mint allocation.
  // TODO(koda): Reclaim the bits by making the compiler treat hash patterns
  // as unsigned words.
  // Keep consistent with IndexSizeToHashMask in runtime/vm/object.h.
  static int _indexSizeToHashMask(int indexSize) {
    assert(indexSize >= _INITIAL_INDEX_SIZE ||
        indexSize == _UNINITIALIZED_INDEX_SIZE);
    if (indexSize == _UNINITIALIZED_INDEX_SIZE) {
      return _UNINITIALIZED_HASH_MASK;
    }
    int indexBits = indexSize.bitLength - 2;
    return internal.has63BitSmis
        ? (1 << (32 - indexBits)) - 1
        : (1 << (30 - indexBits)) - 1;
  }

  static int _hashPattern(int fullHash, int hashMask, int size) {
    final int maskedHash = fullHash & hashMask;
    // TODO(koda): Consider keeping bit length and use left shift.
    return (maskedHash == 0) ? (size >> 1) : maskedHash * (size >> 1);
  }

  // Linear probing.
  static int _firstProbe(int fullHash, int sizeMask) {
    final int i = fullHash & sizeMask;
    // 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);
  static void _setDeletedAt(List data, int d) {
    data[d] = data;
  }

  // Concurrent modification detection relies on this checksum monotonically
  // increasing between reallocations of _data.
  int get _checkSum => _usedData + _deletedKeys;
  bool _isModifiedSince(List oldData, int oldCheckSum) =>
      !identical(_data, oldData) || (_checkSum != oldCheckSum);

  int get length;
}

class _OperatorEqualsAndHashCode {
  int _hashCode(e) => e.hashCode;
  bool _equals(e1, e2) => e1 == e2;
}

class _IdenticalAndIdentityHashCode {
  int _hashCode(e) => identityHashCode(e);
  bool _equals(e1, e2) => identical(e1, e2);
}

class _OperatorEqualsAndCanonicalHashCode {
  static final int cidSymbol = ClassID.getID(#a);

  int _hashCode(e) {
    final int cid = ClassID.getID(e);
    if (cid < ClassID.numPredefinedCids || cid == cidSymbol) {
      return e.hashCode;
    }
    return identityHashCode(e);
  }

  bool _equals(e1, e2) => e1 == e2;
}

final _uninitializedIndex = new Uint32List(_HashBase._UNINITIALIZED_INDEX_SIZE);
// Note: not const. Const arrays are made immutable by having a different class
// than regular arrays that throws on element assignment. We want the data field
// in maps and sets to be monomorphic.
final _uninitializedData = new List.filled(0, null);

// VM-internalized implementation of a default-constructed LinkedHashMap.
@pragma("vm:entry-point")
class _InternalLinkedHashMap<K, V> extends _HashVMBase
    with
        MapMixin<K, V>,
        _LinkedHashMapMixin<K, V>,
        _HashBase,
        _OperatorEqualsAndHashCode
    implements LinkedHashMap<K, V> {
  _InternalLinkedHashMap() {
    _index = _uninitializedIndex;
    _hashMask = _HashBase._UNINITIALIZED_HASH_MASK;
    _data = _uninitializedData;
    _usedData = 0;
    _deletedKeys = 0;
  }
}

// This is essentially the same class as _InternalLinkedHashMap, but it does
// not permit any modification of map entries from Dart code. We use
// this class for maps constructed from Dart constant maps.
@pragma("vm:entry-point")
class _InternalImmutableLinkedHashMap<K, V> extends _HashVMImmutableBase
    with
        MapMixin<K, V>,
        _LinkedHashMapMixin<K, V>,
        _HashBase,
        _OperatorEqualsAndCanonicalHashCode,
        _UnmodifiableMapMixin<K, V>
    implements LinkedHashMap<K, V> {
  factory _InternalImmutableLinkedHashMap._uninstantiable() {
    throw new UnsupportedError("ImmutableMap can only be allocated by the VM");
  }

  bool containsKey(Object? key) {
    if (_indexNullable == null) {
      _createIndex();
    }
    return super.containsKey(key);
  }

  V? operator [](Object? key) {
    if (_indexNullable == null) {
      _createIndex();
    }
    return super[key];
  }

  void _createIndex() {
    final size = max(_data.length, _HashBase._INITIAL_INDEX_SIZE);
    assert(size == _roundUpToPowerOfTwo(size));
    final newIndex = new Uint32List(size);
    final hashMask = _HashBase._indexSizeToHashMask(size);
    assert(_hashMask == hashMask);

    for (int j = 0; j < _usedData; j += 2) {
      final key = _data[j];
      final value = _data[j + 1];

      final fullHash = _hashCode(key);
      final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
      final d =
          _findValueOrInsertPoint(key, fullHash, hashPattern, size, newIndex);
      // We just allocated the index, so we should not find this key in it yet.
      assert(d <= 0);

      final i = -d;

      assert(1 <= hashPattern && hashPattern < (1 << 32));
      final index = j >> 1;
      assert((index & hashPattern) == 0);
      newIndex[i] = hashPattern | index;
    }

    // Publish new index, uses store release semantics.
    _index = newIndex;
  }
}

// Implementation is from "Hacker's Delight" by Henry S. Warren, Jr.,
// figure 3-3, page 48, where the function is called clp2.
int _roundUpToPowerOfTwo(int x) {
  x = x - 1;
  x = x | (x >> 1);
  x = x | (x >> 2);
  x = x | (x >> 4);
  x = x | (x >> 8);
  x = x | (x >> 16);
  x = x | (x >> 32);
  return x + 1;
}

abstract class _LinkedHashMapMixin<K, V> implements _HashBase {
  int _hashCode(e);
  bool _equals(e1, e2);
  int get _checkSum;
  bool _isModifiedSince(List oldData, int oldCheckSum);

  int get length => (_usedData >> 1) - _deletedKeys;
  bool get isEmpty => length == 0;
  bool get isNotEmpty => !isEmpty;

  void _rehash() {
    if ((_deletedKeys << 2) > _usedData) {
      // TODO(koda): Consider shrinking.
      // TODO(koda): Consider in-place compaction and more costly CME check.
      _init(_index.length, _hashMask, _data, _usedData);
    } else {
      // TODO(koda): Support 32->64 bit transition (and adjust _hashMask).
      _init(_index.length << 1, _hashMask >> 1, _data, _usedData);
    }
  }

  void clear() {
    if (!isEmpty) {
      _index = _uninitializedIndex;
      _hashMask = _HashBase._UNINITIALIZED_HASH_MASK;
      _data = _uninitializedData;
      _usedData = 0;
      _deletedKeys = 0;
    }
  }

  // Allocate new _index and _data, and optionally copy existing contents.
  void _init(int size, int hashMask, List? oldData, int oldUsed) {
    if (size < _HashBase._INITIAL_INDEX_SIZE) {
      size = _HashBase._INITIAL_INDEX_SIZE;
      hashMask = _HashBase._indexSizeToHashMask(size);
    }
    assert(size & (size - 1) == 0);
    assert(_HashBase._UNUSED_PAIR == 0);
    _index = new Uint32List(size);
    _hashMask = hashMask;
    _data = new List.filled(size, null);
    _usedData = 0;
    _deletedKeys = 0;
    if (oldData != null) {
      for (int i = 0; i < oldUsed; i += 2) {
        var key = oldData[i];
        if (!_HashBase._isDeleted(oldData, key)) {
          // TODO(koda): While there are enough hash bits, avoid hashCode calls.
          this[key] = oldData[i + 1];
        }
      }
    }
  }

  // This method is called by [_rehashObjects] (see above).
  void _regenerateIndex() {
    _index =
        _data.length == 0 ? _uninitializedIndex : new Uint32List(_data.length);
    assert(_hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
    _hashMask = _HashBase._indexSizeToHashMask(_index.length);
    final int tmpUsed = _usedData;
    _usedData = 0;
    _deletedKeys = 0;
    for (int i = 0; i < tmpUsed; i += 2) {
      final key = _data[i];
      if (!_HashBase._isDeleted(_data, key)) {
        this[key] = _data[i + 1];
      }
    }
  }

  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));
      final int index = _usedData >> 1;
      assert((index & hashPattern) == 0);
      _index[i] = hashPattern | index;
      _data[_usedData++] = key;
      _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, Uint32List index) {
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int firstDeleted = -1;
    int pair = index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      if (pair == _HashBase._DELETED_PAIR) {
        if (firstDeleted < 0) {
          firstDeleted = i;
        }
      } else {
        final int entry = hashPattern ^ pair;
        if (entry < maxEntries) {
          final int d = entry << 1;
          if (_equals(key, _data[d])) {
            return d + 1;
          }
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = index[i];
    }
    return firstDeleted >= 0 ? -firstDeleted : -i;
  }

  void operator []=(K key, V value) {
    final int size = _index.length;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    final int d =
        _findValueOrInsertPoint(key, fullHash, hashPattern, size, _index);
    if (d > 0) {
      _data[d] = value;
    } else {
      final int i = -d;
      _insert(key, value, hashPattern, i);
    }
  }

  V putIfAbsent(K key, V ifAbsent()) {
    final int size = _index.length;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    final int d =
        _findValueOrInsertPoint(key, fullHash, hashPattern, size, _index);
    if (d > 0) {
      return _data[d];
    }
    // 'ifAbsent' is allowed to modify the map.
    List oldData = _data;
    int oldCheckSum = _checkSum;
    V value = ifAbsent();
    if (_isModifiedSince(oldData, oldCheckSum)) {
      this[key] = value;
    } else {
      final int i = -d;
      _insert(key, value, hashPattern, i);
    }
    return value;
  }

  V? remove(Object? key) {
    final int size = _index.length;
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int pair = _index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      if (pair != _HashBase._DELETED_PAIR) {
        final int entry = hashPattern ^ pair;
        if (entry < maxEntries) {
          final int d = entry << 1;
          if (_equals(key, _data[d])) {
            _index[i] = _HashBase._DELETED_PAIR;
            _HashBase._setDeletedAt(_data, d);
            V value = _data[d + 1];
            _HashBase._setDeletedAt(_data, d + 1);
            ++_deletedKeys;
            return value;
          }
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = _index[i];
    }
    return null;
  }

  // If key is absent, return _data (which is never a value).
  Object? _getValueOrData(Object? key) {
    final int size = _index.length;
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int pair = _index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      if (pair != _HashBase._DELETED_PAIR) {
        final int entry = hashPattern ^ pair;
        if (entry < maxEntries) {
          final int d = entry << 1;
          if (_equals(key, _data[d])) {
            return _data[d + 1];
          }
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = _index[i];
    }
    return _data;
  }

  bool containsKey(Object? key) => !identical(_data, _getValueOrData(key));

  V? operator [](Object? key) {
    var v = _getValueOrData(key);
    return identical(_data, v) ? null : internal.unsafeCast<V>(v);
  }

  bool containsValue(Object? value) {
    for (var v in values) {
      // Spec. says this should always use "==", also for identity maps, etc.
      if (v == value) {
        return true;
      }
    }
    return false;
  }

  void forEach(void f(K key, V value)) {
    var ki = keys.iterator;
    var vi = values.iterator;
    while (ki.moveNext()) {
      vi.moveNext();
      f(ki.current, vi.current);
    }
  }

  Iterable<K> get keys =>
      new _CompactIterable<K>(this, _data, _usedData, -2, 2);
  Iterable<V> get values =>
      new _CompactIterable<V>(this, _data, _usedData, -1, 2);
}

class _CompactLinkedIdentityHashMap<K, V> extends _HashFieldBase
    with
        MapMixin<K, V>,
        _LinkedHashMapMixin<K, V>,
        _HashBase,
        _IdenticalAndIdentityHashCode
    implements LinkedHashMap<K, V> {
  _CompactLinkedIdentityHashMap() : super(_HashBase._INITIAL_INDEX_SIZE);
}

class _CompactLinkedCustomHashMap<K, V> extends _HashFieldBase
    with MapMixin<K, V>, _LinkedHashMapMixin<K, V>, _HashBase
    implements LinkedHashMap<K, V> {
  final _equality;
  final _hasher;
  final _validKey;

  // TODO(koda): Ask gbracha why I cannot have fields _equals/_hashCode.
  int _hashCode(e) => _hasher(e);
  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? remove(Object? o) => _validKey(o) ? super.remove(o) : null;

  _CompactLinkedCustomHashMap(this._equality, this._hasher, validKey)
      : _validKey = (validKey != null) ? validKey : new _TypeTest<K>().test,
        super(_HashBase._INITIAL_INDEX_SIZE);
}

// Iterates through _data[_offset + _step], _data[_offset + 2*_step], ...
// and checks for concurrent modification.
class _CompactIterable<E> extends Iterable<E> {
  final _HashBase _table;
  final List _data;
  final int _len;
  final int _offset;
  final int _step;

  _CompactIterable(
      this._table, this._data, this._len, this._offset, this._step);

  Iterator<E> get iterator =>
      new _CompactIterator<E>(_table, _data, _len, _offset, _step);

  int get length => _table.length;
  bool get isEmpty => length == 0;
  bool get isNotEmpty => !isEmpty;
}

class _CompactIterator<E> implements Iterator<E> {
  final _HashBase _table;
  final List _data;
  final int _len;
  int _offset;
  final int _step;
  final int _checkSum;
  E? _current;

  _CompactIterator(
      _HashBase table, this._data, this._len, this._offset, this._step)
      : _table = table,
        _checkSum = table._checkSum;

  bool moveNext() {
    if (_table._isModifiedSince(_data, _checkSum)) {
      throw new ConcurrentModificationError(_table);
    }
    do {
      _offset += _step;
    } while (_offset < _len && _HashBase._isDeleted(_data, _data[_offset]));
    if (_offset < _len) {
      _current = internal.unsafeCast<E>(_data[_offset]);
      return true;
    } else {
      _current = null;
      return false;
    }
  }

  E get current => _current as E;
}

abstract class _LinkedHashSetMixin<E> implements _HashBase {
  int _hashCode(e);
  bool _equals(e1, e2);
  int get _checkSum;
  bool _isModifiedSince(List oldData, int oldCheckSum);

  bool get isEmpty => length == 0;
  bool get isNotEmpty => !isEmpty;
  int get length => _usedData - _deletedKeys;

  E get first {
    for (int offset = 0; offset < _usedData; offset++) {
      Object? current = _data[offset];
      if (!_HashBase._isDeleted(_data, current)) {
        return current as E;
      }
    }
    throw IterableElementError.noElement();
  }

  E get last {
    for (int offset = _usedData - 1; offset >= 0; offset--) {
      Object? current = _data[offset];
      if (!_HashBase._isDeleted(_data, current)) {
        return current as E;
      }
    }
    throw IterableElementError.noElement();
  }

  void _rehash() {
    if ((_deletedKeys << 1) > _usedData) {
      _init(_index.length, _hashMask, _data, _usedData);
    } else {
      _init(_index.length << 1, _hashMask >> 1, _data, _usedData);
    }
  }

  void clear() {
    if (!isEmpty) {
      _index = _uninitializedIndex;
      _hashMask = _HashBase._UNINITIALIZED_HASH_MASK;
      _data = _uninitializedData;
      _usedData = 0;
      _deletedKeys = 0;
    }
  }

  void _init(int size, int hashMask, List? oldData, int oldUsed) {
    if (size < _HashBase._INITIAL_INDEX_SIZE) {
      size = _HashBase._INITIAL_INDEX_SIZE;
      hashMask = _HashBase._indexSizeToHashMask(size);
    }
    _index = new Uint32List(size);
    _hashMask = hashMask;
    _data = new List.filled(size >> 1, null);
    _usedData = 0;
    _deletedKeys = 0;
    if (oldData != null) {
      for (int i = 0; i < oldUsed; i += 1) {
        var key = oldData[i];
        if (!_HashBase._isDeleted(oldData, key)) {
          add(key);
        }
      }
    }
  }

  bool add(E key) {
    final int size = _index.length;
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int firstDeleted = -1;
    int pair = _index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      if (pair == _HashBase._DELETED_PAIR) {
        if (firstDeleted < 0) {
          firstDeleted = i;
        }
      } else {
        final int d = hashPattern ^ pair;
        if (d < maxEntries && _equals(key, _data[d])) {
          return false;
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = _index[i];
    }
    if (_usedData == _data.length) {
      _rehash();
      add(key);
    } else {
      final int insertionPoint = (firstDeleted >= 0) ? firstDeleted : i;
      assert(1 <= hashPattern && hashPattern < (1 << 32));
      assert((hashPattern & _usedData) == 0);
      _index[insertionPoint] = hashPattern | _usedData;
      _data[_usedData++] = key;
    }
    return true;
  }

  // If key is absent, return _data (which is never a value).
  Object? _getKeyOrData(Object? key) {
    final int size = _index.length;
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int pair = _index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      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.
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = _index[i];
    }
    return _data;
  }

  E? lookup(Object? key) {
    var k = _getKeyOrData(key);
    return identical(_data, k) ? null : internal.unsafeCast<E>(k);
  }

  bool contains(Object? key) => !identical(_data, _getKeyOrData(key));

  bool remove(Object? key) {
    final int size = _index.length;
    final int sizeMask = size - 1;
    final int maxEntries = size >> 1;
    final int fullHash = _hashCode(key);
    final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
    int i = _HashBase._firstProbe(fullHash, sizeMask);
    int pair = _index[i];
    while (pair != _HashBase._UNUSED_PAIR) {
      if (pair != _HashBase._DELETED_PAIR) {
        final int d = hashPattern ^ pair;
        if (d < maxEntries && _equals(key, _data[d])) {
          _index[i] = _HashBase._DELETED_PAIR;
          _HashBase._setDeletedAt(_data, d);
          ++_deletedKeys;
          return true;
        }
      }
      i = _HashBase._nextProbe(i, sizeMask);
      pair = _index[i];
    }
    return false;
  }

  Iterator<E> get iterator =>
      new _CompactIterator<E>(this, _data, _usedData, -1, 1);

  // This method is called by [_rehashObjects] (see above).
  void _regenerateIndex() {
    final size =
        _roundUpToPowerOfTwo(max(_data.length, _HashBase._INITIAL_INDEX_SIZE));
    _index = _data.length == 0 ? _uninitializedIndex : new Uint32List(size);
    assert(_hashMask == _HashBase._UNINITIALIZED_HASH_MASK);
    _hashMask = _HashBase._indexSizeToHashMask(_index.length);
    _rehash();
  }
}

// Set implementation, analogous to _CompactLinkedHashMap.
@pragma('vm:entry-point')
class _CompactLinkedHashSet<E> extends _HashVMBase
    with
        SetMixin<E>,
        _LinkedHashSetMixin<E>,
        _HashBase,
        _OperatorEqualsAndHashCode
    implements LinkedHashSet<E> {
  _CompactLinkedHashSet() {
    _index = _uninitializedIndex;
    _hashMask = _HashBase._UNINITIALIZED_HASH_MASK;
    _data = _uninitializedData;
    _usedData = 0;
    _deletedKeys = 0;
  }

  Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);

  static Set<R> _newEmpty<R>() => new _CompactLinkedHashSet<R>();

  // Returns a set of the same type, although this
  // is not required by the spec. (For instance, always using an identity set
  // would be technically correct, albeit surprising.)
  Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this);
}

@pragma("vm:entry-point")
class _CompactImmutableLinkedHashSet<E> extends _HashVMImmutableBase
    with
        SetMixin<E>,
        _LinkedHashSetMixin<E>,
        _HashBase,
        _OperatorEqualsAndCanonicalHashCode,
        _UnmodifiableSetMixin<E>
    implements LinkedHashSet<E> {
  factory _CompactImmutableLinkedHashSet._uninstantiable() {
    throw new UnsupportedError("ImmutableSet can only be allocated by the VM");
  }

  E? lookup(Object? key) {
    if (_indexNullable == null) {
      _createIndex();
    }
    return super.lookup(key);
  }

  bool contains(Object? key) {
    if (_indexNullable == null) {
      _createIndex();
    }
    return super.contains(key);
  }

  void _createIndex() {
    final size = _roundUpToPowerOfTwo(
        max(_data.length * 2, _HashBase._INITIAL_INDEX_SIZE));
    final index = new Uint32List(size);
    final hashMask = _HashBase._indexSizeToHashMask(size);
    assert(_hashMask == hashMask);

    final sizeMask = size - 1;
    final maxEntries = size >> 1;

    for (int j = 0; j < _usedData; j++) {
      final key = _data[j];

      final fullHash = _hashCode(key);
      final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);

      int i = _HashBase._firstProbe(fullHash, sizeMask);
      int pair = index[i];
      while (pair != _HashBase._UNUSED_PAIR) {
        assert(pair != _HashBase._DELETED_PAIR);

        final int d = hashPattern ^ pair;
        if (d < maxEntries) {
          // We should not already find an entry in the index.
          assert(!_equals(key, _data[d]));
        }

        i = _HashBase._nextProbe(i, sizeMask);
        pair = index[i];
      }

      final int insertionPoint = i;
      assert(1 <= hashPattern && hashPattern < (1 << 32));
      assert((hashPattern & j) == 0);
      index[insertionPoint] = hashPattern | j;
    }

    // Publish new index, uses store release semantics.
    _index = index;
  }

  Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);

  static Set<R> _newEmpty<R>() => new _CompactLinkedHashSet<R>();

  // Returns a mutable set.
  Set<E> toSet() => new _CompactLinkedHashSet<E>()..addAll(this);
}

class _CompactLinkedIdentityHashSet<E> extends _HashFieldBase
    with
        SetMixin<E>,
        _LinkedHashSetMixin<E>,
        _HashBase,
        _IdenticalAndIdentityHashCode
    implements LinkedHashSet<E> {
  _CompactLinkedIdentityHashSet() : super(_HashBase._INITIAL_INDEX_SIZE);

  Set<E> toSet() => new _CompactLinkedIdentityHashSet<E>()..addAll(this);

  static Set<R> _newEmpty<R>() => new _CompactLinkedIdentityHashSet<R>();

  Set<R> cast<R>() => Set.castFrom<E, R>(this, newSet: _newEmpty);
}

class _CompactLinkedCustomHashSet<E> extends _HashFieldBase
    with SetMixin<E>, _LinkedHashSetMixin<E>, _HashBase
    implements LinkedHashSet<E> {
  final _equality;
  final _hasher;
  final _validKey;

  int _hashCode(e) => _hasher(e);
  bool _equals(e1, e2) => _equality(e1, e2);

  bool contains(Object? o) => _validKey(o) ? super.contains(o) : false;
  E? lookup(Object? o) => _validKey(o) ? super.lookup(o) : null;
  bool remove(Object? o) => _validKey(o) ? super.remove(o) : false;

  _CompactLinkedCustomHashSet(this._equality, this._hasher, validKey)
      : _validKey = (validKey != null) ? validKey : new _TypeTest<E>().test,
        super(_HashBase._INITIAL_INDEX_SIZE);

  Set<R> cast<R>() => Set.castFrom<E, R>(this);
  Set<E> toSet() =>
      new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey)
        ..addAll(this);
}