New implementation of {,Linked}Hash{Set,Map}.

sdk/lib/collection/linked_hash_table.dart

Index: sdk/lib/collection/linked_hash_table.dart
diff --git a/sdk/lib/collection/linked_hash_table.dart b/sdk/lib/collection/linked_hash_table.dart
new file mode 100644
index 0000000000000000000000000000000000000000..f07561145952176e29e3e2ee97d2104b8503ab4c
--- /dev/null
+++ b/sdk/lib/collection/linked_hash_table.dart
@@ -0,0 +1,171 @@
+part of dart.collection;
+
+/** Unique marker object for the head of a linked list of entries. */
+class _LinkedHashTableHeadMarker {
+  const _LinkedHashTableHeadMarker();
+}
+
+const _LinkedHashTableHeadMarker _HEAD_MARKER =
+    const _LinkedHashTableHeadMarker();
+
+class _LinkedHashTable<K> extends _HashTable<K> {
+  static const _NEXT_INDEX = 1;
+  static const _PREV_INDEX = 2;
+  static const _HEAD_OFFSET = 0;
+
+  _LinkedHashTable(int initialCapacity) : super(initialCapacity);
+
+  int get _entrySize => 3;
+
+  List _createTable(int capacity) {
+    List result = new List.fixedLength(capacity * _entrySize);
+    result[_HEAD_OFFSET] = _HEAD_MARKER;
+    result[_HEAD_OFFSET + _NEXT_INDEX] = _HEAD_OFFSET;
+    result[_HEAD_OFFSET + _PREV_INDEX] = _HEAD_OFFSET;
+    return result;
+  }
+
+  int _next(int offset) => _table[offset + _NEXT_INDEX];
+  void _setNext(int offset, int to) { _table[offset + _NEXT_INDEX] = to; }
+
+  int _prev(int offset) => _table[offset + _PREV_INDEX];
+  void _setPrev(int offset, int to) { _table[offset + _PREV_INDEX] = to; }
+
+  void _linkLast(int offset) {
+    // Add entry at offset at end of double-linked list.
+    int last = _prev(_HEAD_OFFSET);
+    _setNext(offset, _HEAD_OFFSET);
+    _setPrev(offset, last);
+    _setNext(last, offset);
+    _setPrev(_HEAD_OFFSET, offset);
+  }
+
+  void _unlink(int offset) {
+    assert(offset != _HEAD_OFFSET);
+    int next = _next(offset);
+    int prev = _prev(offset);
+    _setNext(offset, null);
+    _setPrev(offset, null);
+    _setNext(prev, next);
+    _setPrev(next, prev);
+  }
+
+  /**
+   * Copies all non-free entries from the old table to the new empty table.
+   */
+  void _addAllEntries(List oldTable) {
+    int offset = oldTable[_HEAD_OFFSET + _NEXT_INDEX];
+    while (offset != _HEAD_OFFSET) {
+      Object object = oldTable[offset];
+      int nextOffset = oldTable[offset + _NEXT_INDEX];
+      int toOffset = _put(object);
+      _copyEntry(oldTable, offset, toOffset);
+      offset = nextOffset;
+    }
+  }
+
+  void _clear() {
+    _setNext(_HEAD_OFFSET, _HEAD_OFFSET);
+    _setPrev(_HEAD_OFFSET, _HEAD_OFFSET);
+    for (int i = _entrySize; i < _table.length; i++) {
+      _table[i] = null;
+    }
+    _entryCount = _deletedCount = 0;
+    _modificationCount++;

[floitsch, 2013/02/06 10:43:58]

This is the only place in the linked_hash_table where we update the modification
count. Should we move it out to the sub-classes entirely. Would be more
consistent.
Same for the non-linked version.

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

I have moved modification-count into the _put, _remove and _clear methods, so
only methods not working through those need to handle their own modification
count.

+  }
+
+  int _put(K key) {
+    Object keyOrNull = (key == null) ? _NULL : key;
+    int offset = _probeForAdd(_hashCodeOf(key), keyOrNull);
+    Object entry = _key(offset);
+    if (!_isFree(entry)) return offset;
+    if (identical(entry, _TOMBSTONE)) {
+      _deletedCount--;
+    } else {
+      _entryCount++;
+    }
+    _setKey(offset, keyOrNull);
+    _linkLast(offset);
+    return offset;
+  }
+
+  void _deleteEntry(int offset) {
+    _unlink(offset);
+    _setKey(offset, _TOMBSTONE);
+    _deletedCount++;
+  }
+}
+
+class _LinkedHashTableKeyIterable<K> extends Iterable<K> {
+  final _LinkedHashTable<K> _table;
+  _LinkedHashTableKeyIterable(this._table);
+  Iterator<K> get iterator => new _LinkedHashTableKeyIterator<K>(_table);
+
+  bool contains(Object value) => _table._get(value) >= 0;
+
+  int get length => _table._elementCount;
+}
+
+class _LinkedHashTableKeyIterator<K> implements Iterator<K> {
+  final _LinkedHashTable<K> _table;
+  final int _modificationCount;
+  int _offset;
+  K _current;
+
+  _LinkedHashTableKeyIterator(_LinkedHashTable<K> table)
+      : _table = table,
+        _modificationCount = table._modificationCount,
+        _offset = _LinkedHashTable._HEAD_OFFSET;
+
+  bool moveNext() {
+    if (_offset == null) return false;
+    _table._checkModification(_modificationCount);
+    _offset = _table._next(_offset);
+    if (_offset == _LinkedHashTable._HEAD_OFFSET) {
+      _current = null;
+      _offset = null;
+      return false;
+    }
+    _current = _table._key(_offset);
+    return true;
+  }
+
+  K get current => _current;
+}
+
+class _LinkedHashTableValueIterable<V> extends Iterable<V> {
+  final _LinkedHashTable _table;
+  final int _valueIndex;
+  _LinkedHashTableValueIterable(this._table, this._valueIndex);
+  Iterator<V> get iterator =>
+    new _LinkedHashTableValueIterator<V>(_table, _valueIndex);
+  int get length => _table._elementCount;
+}
+
+class _LinkedHashTableValueIterator<V> implements Iterator<V> {

[floitsch, 2013/02/06 10:43:58]

The Key and Value iterator could share a common super-class and just implement
"_setCurrent(offset)".

[Lasse Reichstein Nielsen, 2013/02/08 13:53:01]

Done.

+  final _LinkedHashTable _table;
+  final int _valueIndex;
+  final int _modificationCount;
+  int _offset;
+  V _current;
+
+  _LinkedHashTableValueIterator(_LinkedHashTable table, this._valueIndex)
+      : _table = table,
+        _modificationCount = table._modificationCount,
+        _offset = _LinkedHashTable._HEAD_OFFSET;
+
+  bool moveNext() {
+    if (_offset == null) return false;
+    _table._checkModification(_modificationCount);
+    _offset = _table._next(_offset);
+    if (_offset == _LinkedHashTable._HEAD_OFFSET) {
+      _current = null;
+      _offset = null;
+      return false;
+    }
+    _current = _table._table[_offset + _valueIndex];
+    return true;
+  }
+
+  V get current => _current;
+}