Make LinkedHashMap also have a factory constructor and be customizable

runtime/lib/collection_patch.dart

 // Copyright (c) 2013, 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.
 
 patch class HashMap<K, V> {
   /* patch */ factory HashMap({ bool equals(K key1, K key2),
                                 int hashCode(K key) }) {
     if (hashCode == null) {
       if (equals == null) {
-        return new _HashMapImpl<K, V>();
+        return new _HashMap<K, V>();
       }
       if (identical(identical, equals)) {
         return new _IdentityHashMap<K, V>();
       }
       hashCode = _defaultHashCode;
     } else if (equals == null) {
       equals = _defaultEquals;
     }
     return new _CustomHashMap<K, V>(equals, hashCode);
   }
 }
 
 const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
 
-class _HashMapImpl<K, V> implements HashMap<K, V> {
+class _HashMap<K, V> implements HashMap<K, V> {
   static const int _INITIAL_CAPACITY = 8;
 
   int _elementCount = 0;
   List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY);
   int _modificationCount = 0;
 
   int get length => _elementCount;
   bool get isEmpty => _elementCount == 0;
   bool get isNotEmpty => _elementCount != 0;
 
@@ skipping 158 matching lines @@
         newBuckets[index] = entry;
         entry = next;
       }
     }
     _buckets = newBuckets;
   }
 
   String toString() => Maps.mapToString(this);
 }
 
-class _CustomHashMap<K, V> extends _HashMapImpl<K, V> {
+class _CustomHashMap<K, V> extends _HashMap<K, V> {
   final _Equality<K> _equals;
   final _Hasher<K> _hashCode;
   _CustomHashMap(this._equals, this._hashCode);
 
   bool containsKey(Object key) {
     int hashCode = _hashCode(key);
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
     _HashMapEntry entry = buckets[index];
     while (entry != null) {
@@ skipping 76 matching lines @@
       }
       previous = entry;
       entry = next;
     }
     return null;
   }
 
   String toString() => Maps.mapToString(this);
 }
 
-class _IdentityHashMap<K, V> extends _HashMapImpl<K, V> {
+class _IdentityHashMap<K, V> extends _HashMap<K, V> {
   bool containsKey(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
     _HashMapEntry entry = buckets[index];
     while (entry != null) {
       if (hashCode == entry.hashCode && identical(entry.key, key)) return true;
       entry = entry.next;
     }
     return false;
@@ skipping 277 matching lines @@
   LinkedHashMap<dynamic, V> _map;
   _LinkedHashMapValueIterable(this._map);
   Iterator<K> get iterator => new _LinkedHashMapValueIterator<V>(_map);
   bool contains(V value) => _map.containsValue(value);
   bool get isEmpty => _map.isEmpty;
   bool get isNotEmpty => _map.isNotEmpty;
   int get length => _map.length;
 }
 
 abstract class _LinkedHashMapIterator<T> implements Iterator<T> {
-  final _LinkedHashMap _map;
+  final LinkedHashMap _map;
   var _next;
   T _current;
   int _modificationCount;
-  _LinkedHashMapIterator(_LinkedHashMap map)
+  _LinkedHashMapIterator(LinkedHashMap map)
       : _map = map,
         _current = null,
         _next = map._nextEntry,
         _modificationCount = map._modificationCount;
 
   bool moveNext() {
     if (_modificationCount != _map._modificationCount) {
       throw new ConcurrentModificationError(_map);
     }
     if (identical(_map, _next)) {
       _current = null;
       return false;
     }
     _LinkedHashMapEntry entry = _next;
     _next = entry._nextEntry;
     _current = _getValue(entry);
     return true;
   }
 
   T _getValue(_LinkedHashMapEntry entry);
 
   T get current => _current;
 }
 
 class _LinkedHashMapKeyIterator<K> extends _LinkedHashMapIterator<K> {
-  _LinkedHashMapKeyIterator(_LinkedHashMap map) : super(map);
+  _LinkedHashMapKeyIterator(LinkedHashMap map) : super(map);
   K _getValue(_LinkedHashMapEntry entry) => entry.key;
 }
 
 class _LinkedHashMapValueIterator<V> extends _LinkedHashMapIterator<V> {
-  _LinkedHashMapValueIterator(_LinkedHashMap map) : super(map);
+  _LinkedHashMapValueIterator(LinkedHashMap map) : super(map);
   V _getValue(_LinkedHashMapEntry entry) => entry.value;
 }
 
 
 /**
  * A hash-based map that iterates keys and values in key insertion order.
  */
 patch class LinkedHashMap<K, V> {
-  static const int _INITIAL_CAPACITY = 8;
-  static const int _MODIFICATION_COUNT_MASK = 0x3fffffff;
-
-  int _elementCount = 0;
-  List<_HashMapEntry> _buckets = new List(_INITIAL_CAPACITY);
-  int _modificationCount = 0;
-
-  var _nextEntry;
-  var _previousEntry;
-
-  /* patch */ LinkedHashMap() {
-    _nextEntry = _previousEntry = this;
-  }
-
-  /* patch */ int get length => _elementCount;
-  /* patch */ bool get isEmpty => _elementCount == 0;
-  /* patch */ bool get isNotEmpty => _elementCount != 0;
-
-  /* patch */ Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
-  /* patch */ Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
-
-  /* patch */ bool containsKey(Object key) {
-    int hashCode = key.hashCode;
-    List buckets = _buckets;
-    int index = hashCode & (buckets.length - 1);
-    _HashMapEntry entry = buckets[index];
-    while (entry != null) {
-      if (hashCode == entry.hashCode && entry.key == key) return true;
-      entry = entry.next;
+  var _nextEntry;
+  var _previousEntry;
+
+  /* patch */ factory LinkedHashMap({ bool equals(K key1, K key2),
+                                      int hashCode(K key) }) {
+    if (hashCode == null) {
+      if (equals == null) {
+        return new _LinkedHashMap<K, V>();
+      }
+      if (identical(identical, equals)) {
+        return new _LinkedIdentityHashMap<K, V>();
+      }
+      hashCode = _defaultHashCode;
+    } else if (equals == null) {
+      equals = _defaultEquals;
+    }
+    return new _LinkedCustomHashMap<K, V>(equals, hashCode);
+  }
+}
+
+class _LinkedHashMap<K, V> extends _HashMap<K, V>
+                               implements LinkedHashMap<K, V> {

[floitsch, 2013/09/05 13:44:28]

nit: indentation.

[Lasse Reichstein Nielsen, 2013/09/06 08:49:24]

Done.

+  var _nextEntry;
+  var _previousEntry;
+
+  _LinkedHashMap() {
+    _nextEntry = _previousEntry = this;
+  }
+
+  bool containsValue(Object value) {
+    int modificationCount = _modificationCount;
+    var cursor = _nextEntry;
+    while (!identical(cursor, this)) {
+      _HashMapEntry entry = cursor;
+      if (entry.value == value) return true;
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      cursor = cursor._nextEntry;
     }
     return false;
   }
 
-  /* patch */ bool containsValue(Object value) {
-    var cursor = _nextEntry;
-    int modificationCount = _modificationCount;
-    while (!identical(cursor, this)) {
-      _HashMapEntry entry = cursor;
-      if (entry.value == value) return true;
-      cursor = cursor._nextEntry;
-    }
-    return false;
-  }
-
-  /* patch */ V operator[](Object key) {
-    int hashCode = key.hashCode;
-    List buckets = _buckets;
-    int index = hashCode & (buckets.length - 1);
-    _HashMapEntry entry = buckets[index];
-    while (entry != null) {
-      if (hashCode == entry.hashCode && entry.key == key) {
-        return entry.value;
-      }
-      entry = entry.next;
-    }
-    return null;
-  }
-
-  /* patch */ void operator []=(K key, V value) {
-    int hashCode = key.hashCode;
-    List buckets = _buckets;
-    int length = buckets.length;
-    int index = hashCode & (length - 1);
-    _HashMapEntry entry = buckets[index];
-    while (entry != null) {
-      if (hashCode == entry.hashCode && entry.key == key) {
-        entry.value = value;
-        return;
-      }
-      entry = entry.next;
-    }
-    _addEntry(buckets, index, length, key, value, hashCode);
-  }
-
-  /* patch */ V putIfAbsent(K key, V ifAbsent()) {
-    int hashCode = key.hashCode;
-    List buckets = _buckets;
-    int length = buckets.length;
-    int index = hashCode & (length - 1);
-    _HashMapEntry entry = buckets[index];
-    while (entry != null) {
-      if (hashCode == entry.hashCode && entry.key == key) {
-        return entry.value;
-      }
-      entry = entry.next;
-    }
-    int stamp = _modificationCount;
-    V value = ifAbsent();
-    if (stamp == _modificationCount) {
-      _addEntry(buckets, index, length, key, value, hashCode);
-    } else {
-      this[key] = value;
-    }
-    return value;
-  }
-
-  /* patch */ void addAll(Map<K, V> other) {
-    other.forEach((K key, V value) {
-      this[key] = value;
-    });
-  }
-
-  /* patch */ void forEach(void action(K key, V value)) {
-    int stamp = _modificationCount;
+  void forEach(void action(K key, V value)) {
+    int modificationCount = _modificationCount;
     var cursor = _nextEntry;
     while (!identical(cursor, this)) {
       _HashMapEntry entry = cursor;
       action(entry.key, entry.value);
-      if (stamp != _modificationCount) {
+      if (modificationCount != _modificationCount) {
         throw new ConcurrentModificationError(this);
       }
       cursor = cursor._nextEntry;
     }
   }
 
   /* patch */ V remove(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
     _LinkedHashMapEntry entry = buckets[index];
     _HashMapEntry previous = null;
     while (entry != null) {
       _HashMapEntry next = entry.next;
       if (hashCode == entry.hashCode && entry.key == key) {
         if (previous == null) {
           buckets[index] = next;
         } else {
+          previous.next = next;
+        }
+        entry._previousEntry._nextEntry = entry._nextEntry;

[floitsch, 2013/09/05 13:44:28]

As usual: I prefer temporary variables:
previous = entry._previousEntry;
next = entry._nextEntry;
previous.next = next;
next.previous = previous;
entry.next = entry.previous = null;
...

[floitsch, 2013/09/05 13:44:28]

Starting at this line this code is the same for all implementations.
Maybe add TODO for refactoring to share at least some code.

[Lasse Reichstein Nielsen, 2013/09/06 08:49:24]

Similar code. It may differ on equality and hashcode computations.
I want to make a version that doesn't duplicate the code unnecessarily, and see
if it's much slower.
Will do.

+        entry._nextEntry._previousEntry = entry._previousEntry;
+        entry._nextEntry = entry._previousEntry = null;
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+
+  void clear() {
+    _nextEntry = _previousEntry = this;
+    super.clear();
+  }
+
+  void _addEntry(List buckets, int index, int length,

[floitsch, 2013/09/05 13:44:28]

same code too. right?

[Lasse Reichstein Nielsen, 2013/09/06 08:49:24]

Exactly same code in all three sub-classes, yes.

I'll make it a mixin (and hope that won't break anything, including
performance).
In fact, I'll refactory remove to call a _removeEntry that can be specialized in
linked hash maps. That should make all the linked hash maps just one mixin.

+                 K key, V value, int hashCode) {
+    _HashMapEntry entry =
+        new _LinkedHashMapEntry(key, value, hashCode, buckets[index],
+                                _previousEntry, this);
+    buckets[index] = entry;
+    int newElements = _elementCount + 1;
+    _elementCount = newElements;
+    // If we end up with more than 75% non-empty entries, we
+    // resize the backing store.
+    if ((newElements << 2) > ((length << 1) + length)) _resize();
+    _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+  }
+
+  Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
+}
+
+class _LinkedIdentityHashMap<K, V> extends _IdentityHashMap<K, V>
+                                   implements LinkedHashMap<K, V> {
+  var _nextEntry;
+  var _previousEntry;
+
+  _LinkedIdentityHashMap() {
+    _nextEntry = _previousEntry = this;
+  }
+
+  bool containsValue(Object value) {
+    int modificationCount = _modificationCount;
+    var cursor = _nextEntry;
+    while (!identical(cursor, this)) {
+      _HashMapEntry entry = cursor;
+      if (entry.value == value) return true;
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      cursor = cursor._nextEntry;
+    }
+    return false;
+  }
+
+  void forEach(void action(K key, V value)) {
+    int modificationCount = _modificationCount;
+    var cursor = _nextEntry;
+    while (!identical(cursor, this)) {
+      _HashMapEntry entry = cursor;
+      action(entry.key, entry.value);
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      cursor = cursor._nextEntry;
+    }
+  }
+
+  V remove(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _LinkedHashMapEntry entry = buckets[index];
+    _HashMapEntry previous = null;
+    while (entry != null) {
+      _HashMapEntry next = entry.next;
+      if (hashCode == entry.hashCode && identical(entry.key, key)) {
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
+          previous.next = next;
+        }
+        entry._previousEntry._nextEntry = entry._nextEntry;

[floitsch, 2013/09/05 13:44:28]

temporary variables.

[Lasse Reichstein Nielsen, 2013/09/06 08:49:24]

Done.

+        entry._nextEntry._previousEntry = entry._previousEntry;
+        entry._nextEntry = entry._previousEntry = null;
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+
+  void clear() {
+    _nextEntry = _previousEntry = this;
+    super.clear();
+  }
+
+  void _addEntry(List buckets, int index, int length,
+                 K key, V value, int hashCode) {
+    buckets[index] =
+        new _LinkedHashMapEntry(key, value, hashCode, buckets[index],
+                                _previousEntry, this);
+    int newElements = _elementCount + 1;
+    _elementCount = newElements;
+    // If we end up with more than 75% non-empty entries, we
+    // resize the backing store.
+    if ((newElements << 2) > ((length << 1) + length)) _resize();
+    _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+  }
+
+  Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
+}
+
+class _LinkedCustomHashMap<K, V> extends _CustomHashMap<K, V>
+                                 implements LinkedHashMap<K, V> {
+  var _nextEntry;
+  var _previousEntry;
+
+  _LinkedCustomHashMap(bool equals(K key1, K key2),
+                       int hashCode(K key))
+      : super(equals, hashCode) {
+    _nextEntry = _previousEntry = this;
+  }
+
+  bool containsValue(Object value) {
+    int modificationCount = _modificationCount;
+    var cursor = _nextEntry;
+    while (!identical(cursor, this)) {
+      _HashMapEntry entry = cursor;
+      if (entry.value == value) return true;
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      cursor = cursor._nextEntry;
+    }
+    return false;
+  }
+
+  void forEach(void action(K key, V value)) {
+    int modificationCount = _modificationCount;
+    var cursor = _nextEntry;
+    while (!identical(cursor, this)) {
+      _HashMapEntry entry = cursor;
+      action(entry.key, entry.value);
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      cursor = cursor._nextEntry;
+    }
+  }
+
+  V remove(Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _LinkedHashMapEntry entry = buckets[index];
+    _HashMapEntry previous = null;
+    while (entry != null) {
+      _HashMapEntry next = entry.next;
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        if (previous == null) {
+          buckets[index] = next;
+        } else {
           previous.next = next;
         }
         entry._previousEntry._nextEntry = entry._nextEntry;

[floitsch, 2013/09/05 13:44:28]

ditto.

[Lasse Reichstein Nielsen, 2013/09/06 08:49:24]

Done.

         entry._nextEntry._previousEntry = entry._previousEntry;
         entry._nextEntry = entry._previousEntry = null;
         _elementCount--;
         _modificationCount =
             (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
         return entry.value;
       }
       previous = entry;
       entry = next;
     }
     return null;
   }
 
-  /* patch */ void clear() {
-    _elementCount = 0;
+  void clear() {
     _nextEntry = _previousEntry = this;
-    _buckets = new List(_INITIAL_CAPACITY);
-    _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+    super.clear();
   }
 
   void _addEntry(List buckets, int index, int length,
                  K key, V value, int hashCode) {
-    _HashMapEntry entry =
+    buckets[index] =
         new _LinkedHashMapEntry(key, value, hashCode, buckets[index],
                                 _previousEntry, this);
-    buckets[index] = entry;
     int newElements = _elementCount + 1;
     _elementCount = newElements;
     // If we end up with more than 75% non-empty entries, we
     // resize the backing store.
     if ((newElements << 2) > ((length << 1) + length)) _resize();
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
   }
 
-  void _resize() {
-    List oldBuckets = _buckets;
-    int oldLength = oldBuckets.length;
-    int newLength = oldLength << 1;
-    List newBuckets = new List(newLength);
-    for (int i = 0; i < oldLength; i++) {
-      _HashMapEntry entry = oldBuckets[i];
-      while (entry != null) {
-        _HashMapEntry next = entry.next;
-        int hashCode = entry.hashCode;
-        int index = hashCode & (newLength - 1);
-        entry.next = newBuckets[index];
-        newBuckets[index] = entry;
-        entry = next;
-      }
-    }
-    _buckets = newBuckets;
-  }
+  Iterable<K> get keys => new _LinkedHashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _LinkedHashMapValueIterable<V>(this);
 }
 
+
 patch class LinkedHashSet<E> extends _HashSetBase<E> {
   static const int _INITIAL_CAPACITY = 8;
   _LinkedHashTable<E> _table;
 
   /* patch */ LinkedHashSet() {
     _table = new _LinkedHashTable(_INITIAL_CAPACITY);
     _table._container = this;
   }
 
   // Iterable.
@@ skipping 680 matching lines @@
 
   _LinkedHashMapTable() : super(_INITIAL_CAPACITY);
 
   V _value(int offset) => _table[offset + _VALUE_INDEX];
   void _setValue(int offset, V value) { _table[offset + _VALUE_INDEX] = value; }
 
   _copyEntry(List oldTable, int fromOffset, int toOffset) {
     _table[toOffset + _VALUE_INDEX] = oldTable[fromOffset + _VALUE_INDEX];
   }
 }