Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(601)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: runtime/lib/compact_hash.dart

Issue 983703003: Replace Linked{Identity,Custom}Hash{Map,Set} with compact implementation; remove old code and flag. (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/lib/collection_patch.dart ('k') | runtime/lib/linked_hash_map.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: runtime/lib/compact_hash.dart
===================================================================
--- runtime/lib/compact_hash.dart (revision 44194)
+++ runtime/lib/compact_hash.dart (working copy)
@@ -68,10 +68,20 @@
!identical(_data, oldData) || (_checkSum != oldCheckSum);
}
+abstract class _OperatorEqualsAndHashCode {
Ivan Posva 2015/03/05 20:45:34 Why "abstract"?
+ int _hashCode(e) => e.hashCode;
+ bool _equals(e1, e2) => e1 == e2;
+}
+
+abstract class _IdenticalAndIdentityHashCode {
+ int _hashCode(e) => identityHashCode(e);
+ bool _equals(e1, e2) => identical(e1, e2);
+}
+
// Map with iteration in insertion order (hence "Linked"). New keys are simply
// appended to _data.
class _CompactLinkedHashMap<K, V>
- extends MapBase<K, V> with _HashBase
+ extends MapBase<K, V> with _HashBase, _OperatorEqualsAndHashCode
implements HashMap<K, V>, LinkedHashMap<K, V> {
Ivan Posva 2015/03/05 20:45:34 I think you can drop the "HashMap<K,V>" from the i
_CompactLinkedHashMap() {
@@ -152,7 +162,7 @@
final int entry = hashPattern ^ pair;
if (entry < maxEntries) {
final int d = entry << 1;
- if (key == _data[d]) {
+ if (_equals(key, _data[d])) {
return d + 1;
}
}
@@ -166,7 +176,7 @@
void operator[]=(K key, V value) {
final int size = _index.length;
final int sizeMask = size - 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
if (d > 0) {
@@ -181,7 +191,7 @@
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
final int d = _findValueOrInsertPoint(key, fullHash, hashPattern, size);
if (d > 0) {
@@ -204,7 +214,7 @@
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int pair = _index[i];
@@ -213,7 +223,7 @@
final int entry = hashPattern ^ pair;
if (entry < maxEntries) {
final int d = entry << 1;
- if (key == _data[d]) {
+ if (_equals(key, _data[d])) {
_index[i] = _HashBase._DELETED_PAIR;
_HashBase._setDeletedAt(_data, d);
V value = _data[d + 1];
@@ -234,7 +244,7 @@
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int pair = _index[i];
@@ -243,7 +253,7 @@
final int entry = hashPattern ^ pair;
if (entry < maxEntries) {
final int d = entry << 1;
- if (key == _data[d]) {
+ if (_equals(key, _data[d])) {
return _data[d + 1];
}
}
@@ -263,6 +273,7 @@
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;
}
@@ -285,6 +296,28 @@
new _CompactIterable<V>(this, _data, _usedData, -1, 2);
}
+class _CompactLinkedIdentityHashMap<K, V>
+ extends _CompactLinkedHashMap<K, V> with _IdenticalAndIdentityHashCode {
+}
+
+class _CompactLinkedCustomHashMap<K, V>
+ extends _CompactLinkedHashMap<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<E>().test;
+}
+
// Iterates through _data[_offset + _step], _data[_offset + 2*_step], ...
// and checks for concurrent modification.
class _CompactIterable<E> extends IterableBase<E> {
@@ -335,9 +368,9 @@
}
// Set implementation, analogous to _CompactLinkedHashMap.
-class _CompactLinkedHashSet<K>
- extends SetBase<K> with _HashBase
- implements LinkedHashSet<K> {
+class _CompactLinkedHashSet<E>
+ extends SetBase<E> with _HashBase, _OperatorEqualsAndHashCode
+ implements LinkedHashSet<E> {
_CompactLinkedHashSet() {
assert(_HashBase._UNUSED_PAIR == 0);
@@ -377,11 +410,11 @@
}
}
- bool add(K key) {
+ bool add(E key) {
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int firstDeleted = -1;
@@ -393,7 +426,7 @@
}
} else {
final int d = hashPattern ^ pair;
- if (d < maxEntries && key == _data[d]) {
+ if (d < maxEntries && _equals(key, _data[d])) {
return false;
}
}
@@ -418,7 +451,7 @@
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int pair = _index[i];
@@ -425,7 +458,7 @@
while (pair != _HashBase._UNUSED_PAIR) {
if (pair != _HashBase._DELETED_PAIR) {
final int d = hashPattern ^ pair;
- if (d < maxEntries && key == _data[d]) {
+ if (d < maxEntries && _equals(key, _data[d])) {
return _data[d]; // Note: Must return the existing key.
}
}
@@ -435,7 +468,7 @@
return _data;
}
- K lookup(Object key) {
+ E lookup(Object key) {
var k = _getKeyOrData(key);
return identical(_data, k) ? null : k;
}
@@ -446,7 +479,7 @@
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = key.hashCode;
+ final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int pair = _index[i];
@@ -453,7 +486,7 @@
while (pair != _HashBase._UNUSED_PAIR) {
if (pair != _HashBase._DELETED_PAIR) {
final int d = hashPattern ^ pair;
- if (d < maxEntries && key == _data[d]) {
+ if (d < maxEntries && _equals(key, _data[d])) {
_index[i] = _HashBase._DELETED_PAIR;
_HashBase._setDeletedAt(_data, d);
++_deletedKeys;
@@ -466,8 +499,37 @@
return false;
}
- Iterator<K> get iterator =>
- new _CompactIterator<K>(this, _data, _usedData, -1, 1);
+ Iterator<E> get iterator =>
+ new _CompactIterator<E>(this, _data, _usedData, -1, 1);
- Set<K> toSet() => new Set<K>()..addAll(this);
+ // 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);
}
+
+class _CompactLinkedIdentityHashSet<E>
+ extends _CompactLinkedHashSet<E> with _IdenticalAndIdentityHashCode {
+ Set<E> toSet() => new _CompactLinkedIdentityHashSet<E>()..addAll(this);
+}
+
+class _CompactLinkedCustomHashSet<E>
+ extends _CompactLinkedHashSet<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;
+
+ Set<E> toSet() =>
+ new _CompactLinkedCustomHashSet<E>(_equality, _hasher, _validKey)
+ ..addAll(this);
+}
« no previous file with comments | « runtime/lib/collection_patch.dart ('k') | runtime/lib/linked_hash_map.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698