Add custom equals and hashCode for HashMap implementation.

runtime/lib/collection_patch.dart

Index: runtime/lib/collection_patch.dart
diff --git a/runtime/lib/collection_patch.dart b/runtime/lib/collection_patch.dart
index 5bd4ab93657d4ff5f096a3ecdd303661da79e104..f78951f4374bbc044f0dd9df88e391f25985c694 100644
--- a/runtime/lib/collection_patch.dart
+++ b/runtime/lib/collection_patch.dart
@@ -3,23 +3,40 @@
 // 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>();
+      }
+      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> {
   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;
 
-  /* patch */ HashMap._internal();
-
-  /* patch */ int get length => _elementCount;
-  /* patch */ bool get isEmpty => _elementCount == 0;
-  /* patch */ bool get isNotEmpty => _elementCount != 0;
+  int get length => _elementCount;
+  bool get isEmpty => _elementCount == 0;
+  bool get isNotEmpty => _elementCount != 0;
 
-  /* patch */ Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
-  /* patch */ Iterable<V> get values => new _HashMapValueIterable<V>(this);
+  Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _HashMapValueIterable<V>(this);
 
-  /* patch */ bool containsKey(Object key) {
+  bool containsKey(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -31,7 +48,7 @@ patch class HashMap<K, V> {
     return false;
   }
 
-  /* patch */ bool containsValue(Object value) {
+  bool containsValue(Object value) {
     List buckets = _buckets;
     int length = buckets.length;
     for (int i = 0; i < length; i++) {
@@ -44,7 +61,7 @@ patch class HashMap<K, V> {
     return false;
   }
 
-  /* patch */ V operator[](Object key) {
+  V operator[](Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -58,7 +75,7 @@ patch class HashMap<K, V> {
     return null;
   }
 
-  /* patch */ void operator []=(K key, V value) {
+  void operator []=(K key, V value) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int length = buckets.length;
@@ -74,7 +91,7 @@ patch class HashMap<K, V> {
     _addEntry(buckets, index, length, key, value, hashCode);
   }
 
-  /* patch */ V putIfAbsent(K key, V ifAbsent()) {
+  V putIfAbsent(K key, V ifAbsent()) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int length = buckets.length;
@@ -96,13 +113,13 @@ patch class HashMap<K, V> {
     return value;
   }
 
-  /* patch */ void addAll(Map<K, V> other) {
+  void addAll(Map<K, V> other) {
     other.forEach((K key, V value) {
       this[key] = value;
     });
   }
 
-  /* patch */ void forEach(void action(K key, V value)) {
+  void forEach(void action(K key, V value)) {
     int stamp = _modificationCount;
     List buckets = _buckets;
     int length = buckets.length;
@@ -118,7 +135,7 @@ patch class HashMap<K, V> {
     }
   }
 
-  /* patch */ V remove(Object key) {
+  V remove(Object key) {
     int hashCode = key.hashCode;
     List buckets = _buckets;
     int index = hashCode & (buckets.length - 1);
@@ -143,7 +160,7 @@ patch class HashMap<K, V> {
     return null;
   }
 
-  /* patch */ void clear() {
+  void clear() {
     _elementCount = 0;
     _buckets = new List(_INITIAL_CAPACITY);
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
@@ -182,6 +199,193 @@ patch class HashMap<K, V> {
   }
 }
 
+class _CustomHashMap<K, V> extends _HashMapImpl<K, V> {

[floitsch, 2013/09/03 13:59:08]

File a bug against the VM asking for customization and add it here.
We shouldn't need to customize the classes ourselves.

Phrase the bug in a way that explains the problem (code duplication) but doesn't
fixate on one solution (customization). Maybe they have other ideas/approaches
to reduce code duplication without sacrificing speed.

[Lasse Reichstein Nielsen, 2013/09/04 05:59:21]

I can avoid the code duplication myself by abstracting the equals and hashcode
functionality into overridable methods. I just decided not to, because the
functions are so small and simple (well, except for putIfAbsent maybe) that
duplication is probably better. Performance-wise, it's the *safe* bet (it
doesn't change what we have now for HashMap), and we can always try to avoid the
code duplication later.

Whether the VM customizes functions or not was not part of the decision (since I
honestly don't know if it does).

+  final Function _equals;
+  final Function _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) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) return true;
+      entry = entry.next;
+    }
+    return false;
+  }
+
+  V operator[](Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    return null;
+  }
+
+  void operator []=(K key, V value) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(entry.key, key)) {
+        entry.value = value;
+        return;
+      }
+      entry = entry.next;
+    }
+    _addEntry(buckets, index, length, key, value, hashCode);
+  }
+
+  V putIfAbsent(K key, V ifAbsent()) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int length = buckets.length;
+    int index = hashCode & (length - 1);
+    _HashMapEntry entry = buckets[index];
+    while (entry != null) {
+      if (hashCode == entry.hashCode && _equals(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;
+  }
+
+  V remove(Object key) {
+    int hashCode = _hashCode(key);
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry 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;
+        }
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+}
+
+class _IdentityHashMap<K, V> extends _HashMapImpl<K, V> {

[floitsch, 2013/09/03 13:59:08]

I'm not sure we need to have Identity maps to be customized yet.
I would extend a base class, overwriting the _equals and _hashCode methods, and
wait for the VM to customize.

[Lasse Reichstein Nielsen, 2013/09/04 05:59:21]

I expect IdentityMap to be the main usage of customizable HashMap, so I don't
want to wait for an optimization to occur. I'd rather have it as efficient as
possible right now.

+  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;
+  }
+
+  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 && identical(entry.key, key)) {
+        return entry.value;
+      }
+      entry = entry.next;
+    }
+    return null;
+  }
+
+  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 && identical(entry.key, key)) {
+        entry.value = value;
+        return;
+      }
+      entry = entry.next;
+    }
+    _addEntry(buckets, index, length, key, value, hashCode);
+  }
+
+  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 && identical(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;
+  }
+
+  V remove(Object key) {
+    int hashCode = key.hashCode;
+    List buckets = _buckets;
+    int index = hashCode & (buckets.length - 1);
+    _HashMapEntry 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;
+        }
+        _elementCount--;
+        _modificationCount =
+            (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
+        return entry.value;
+      }
+      previous = entry;
+      entry = next;
+    }
+    return null;
+  }
+}
+
+
 class _HashMapEntry {
   final key;
   var value;