Add custom equals and hashCode for HashMap implementation.

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>();
+      }
+      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();
+  int get length => _elementCount;
+  bool get isEmpty => _elementCount == 0;
+  bool get isNotEmpty => _elementCount != 0;
 
-  /* patch */ int get length => _elementCount;
-  /* patch */ bool get isEmpty => _elementCount == 0;
-  /* patch */ bool get isNotEmpty => _elementCount != 0;
+  Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
+  Iterable<V> get values => new _HashMapValueIterable<V>(this);
 
-  /* patch */ Iterable<K> get keys => new _HashMapKeyIterable<K>(this);
-  /* patch */ 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);
     _HashMapEntry entry = buckets[index];
     while (entry != null) {
       if (hashCode == entry.hashCode && entry.key == key) return true;
       entry = entry.next;
     }
     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++) {
       _HashMapEntry entry = buckets[i];
       while (entry != null) {
         if (entry.value == value) return true;
         entry = entry.next;
       }
     }
     return false;
   }
 
-  /* patch */ V operator[](Object key) {
+  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) {
+  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()) {
+  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) {
+  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;
     for (int i = 0; i < length; i++) {
       _HashMapEntry entry = buckets[i];
       while (entry != null) {
         action(entry.key, entry.value);
         if (stamp != _modificationCount) {
           throw new ConcurrentModificationError(this);
         }
         entry = entry.next;
       }
     }
   }
 
-  /* patch */ V remove(Object key) {
+  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 && 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;
   }
 
-  /* patch */ void clear() {
+  void clear() {
     _elementCount = 0;
     _buckets = new List(_INITIAL_CAPACITY);
     _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK;
   }
 
   void _addEntry(List buckets, int index, int length,
                  K key, V value, int hashCode) {
     _HashMapEntry entry =
         new _HashMapEntry(key, value, hashCode, buckets[index]);
     buckets[index] = entry;
@@ skipping 18 matching lines @@
         int index = hashCode & (newLength - 1);
         entry.next = newBuckets[index];
         newBuckets[index] = entry;
         entry = next;
       }
     }
     _buckets = newBuckets;
   }
 }
 
+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;
   final int hashCode;
   _HashMapEntry next;
   _HashMapEntry(this.key, this.value, this.hashCode, this.next);
 }
 
 abstract class _HashMapIterable<E> extends IterableBase<E> {
   final HashMap _map;
@@ skipping 1112 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];
   }
 }