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

Side by Side Diff: lib/coreimpl/hash_map_set.dart

Issue 11191078: Make hashCode a getter and not a method. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Update status file with co19 issue number. Created 8 years, 2 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 unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a 2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file. 3 // BSD-style license that can be found in the LICENSE file.
4 4
5 // Hash map implementation with open addressing and quadratic probing. 5 // Hash map implementation with open addressing and quadratic probing.
6 class HashMapImplementation<K, V> implements HashMap<K, V> { 6 class HashMapImplementation<K, V> implements HashMap<K, V> {
7 7
8 // The [_keys] list contains the keys inserted in the map. 8 // The [_keys] list contains the keys inserted in the map.
9 // The [_keys] list must be a raw list because it 9 // The [_keys] list must be a raw list because it
10 // will contain both elements of type K, and the [_DELETED_KEY] of type 10 // will contain both elements of type K, and the [_DELETED_KEY] of type
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after
63 static int _firstProbe(int hashCode, int length) { 63 static int _firstProbe(int hashCode, int length) {
64 return hashCode & (length - 1); 64 return hashCode & (length - 1);
65 } 65 }
66 66
67 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { 67 static int _nextProbe(int currentProbe, int numberOfProbes, int length) {
68 return (currentProbe + numberOfProbes) & (length - 1); 68 return (currentProbe + numberOfProbes) & (length - 1);
69 } 69 }
70 70
71 int _probeForAdding(K key) { 71 int _probeForAdding(K key) {
72 if (key == null) throw const NullPointerException(); 72 if (key == null) throw const NullPointerException();
73 int hash = _firstProbe(key.hashCode(), _keys.length); 73 int hash = _firstProbe(key.hashCode, _keys.length);
74 int numberOfProbes = 1; 74 int numberOfProbes = 1;
75 int initialHash = hash; 75 int initialHash = hash;
76 // insertionIndex points to a slot where a key was deleted. 76 // insertionIndex points to a slot where a key was deleted.
77 int insertionIndex = -1; 77 int insertionIndex = -1;
78 while (true) { 78 while (true) {
79 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. 79 // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
80 Object existingKey = _keys[hash]; 80 Object existingKey = _keys[hash];
81 if (existingKey === null) { 81 if (existingKey === null) {
82 // We are sure the key is not already in the set. 82 // We are sure the key is not already in the set.
83 // If the current slot is empty and we didn't find any 83 // If the current slot is empty and we didn't find any
(...skipping 13 matching lines...) Expand all
97 97
98 // We did not find an insertion slot. Look at the next one. 98 // We did not find an insertion slot. Look at the next one.
99 hash = _nextProbe(hash, numberOfProbes++, _keys.length); 99 hash = _nextProbe(hash, numberOfProbes++, _keys.length);
100 // _ensureCapacity has guaranteed the following cannot happen. 100 // _ensureCapacity has guaranteed the following cannot happen.
101 // assert(hash != initialHash); 101 // assert(hash != initialHash);
102 } 102 }
103 } 103 }
104 104
105 int _probeForLookup(K key) { 105 int _probeForLookup(K key) {
106 if (key == null) throw const NullPointerException(); 106 if (key == null) throw const NullPointerException();
107 int hash = _firstProbe(key.hashCode(), _keys.length); 107 int hash = _firstProbe(key.hashCode, _keys.length);
108 int numberOfProbes = 1; 108 int numberOfProbes = 1;
109 int initialHash = hash; 109 int initialHash = hash;
110 while (true) { 110 while (true) {
111 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. 111 // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
112 Object existingKey = _keys[hash]; 112 Object existingKey = _keys[hash];
113 // If the slot does not contain anything (in particular, it does not 113 // If the slot does not contain anything (in particular, it does not
114 // contain a deleted key), we know the key is not in the map. 114 // contain a deleted key), we know the key is not in the map.
115 if (existingKey === null) return -1; 115 if (existingKey === null) return -1;
116 // The key is in the map, return its index. 116 // The key is in the map, return its index.
117 if (existingKey == key) return hash; 117 if (existingKey == key) return hash;
(...skipping 329 matching lines...) Expand 10 before | Expand all | Expand 10 after
447 447
448 /** 448 /**
449 * A singleton sentinel used to represent when a key is deleted from the map. 449 * A singleton sentinel used to represent when a key is deleted from the map.
450 * We can't use [: const Object() :] as a sentinel because it would end up 450 * We can't use [: const Object() :] as a sentinel because it would end up
451 * canonicalized and then we cannot distinguish the deleted key from the 451 * canonicalized and then we cannot distinguish the deleted key from the
452 * canonicalized [: Object() :]. 452 * canonicalized [: Object() :].
453 */ 453 */
454 class _DeletedKeySentinel { 454 class _DeletedKeySentinel {
455 const _DeletedKeySentinel(); 455 const _DeletedKeySentinel();
456 } 456 }
OLDNEW
« no previous file with comments | « lib/coreimpl/date.dart ('k') | lib/isolate/base.dart » ('j') | tests/co19/co19-dart2js.status » ('J')

Powered by Google App Engine
This is Rietveld 408576698