| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, 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 /** | 5 /** |
| 6 * A [Map] is an associative container, mapping a key to a value. | 6 * A [Map] is an associative container, mapping a key to a value. |
| 7 * Null values are supported, but null keys are not. | 7 * Null values are supported, but null keys are not. |
| 8 */ | 8 */ |
| 9 abstract class Map<K, V> { | 9 abstract class Map<K, V> { |
| 10 /** | 10 /** |
| (...skipping 171 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 182 | 182 |
| 183 static int _firstProbe(int hashCode, int length) { | 183 static int _firstProbe(int hashCode, int length) { |
| 184 return hashCode & (length - 1); | 184 return hashCode & (length - 1); |
| 185 } | 185 } |
| 186 | 186 |
| 187 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { | 187 static int _nextProbe(int currentProbe, int numberOfProbes, int length) { |
| 188 return (currentProbe + numberOfProbes) & (length - 1); | 188 return (currentProbe + numberOfProbes) & (length - 1); |
| 189 } | 189 } |
| 190 | 190 |
| 191 int _probeForAdding(K key) { | 191 int _probeForAdding(K key) { |
| 192 if (key == null) throw const NullPointerException(); | 192 if (key == null) throw new ArgumentError(null); |
| 193 int hash = _firstProbe(key.hashCode, _keys.length); | 193 int hash = _firstProbe(key.hashCode, _keys.length); |
| 194 int numberOfProbes = 1; | 194 int numberOfProbes = 1; |
| 195 int initialHash = hash; | 195 int initialHash = hash; |
| 196 // insertionIndex points to a slot where a key was deleted. | 196 // insertionIndex points to a slot where a key was deleted. |
| 197 int insertionIndex = -1; | 197 int insertionIndex = -1; |
| 198 while (true) { | 198 while (true) { |
| 199 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 199 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
| 200 Object existingKey = _keys[hash]; | 200 Object existingKey = _keys[hash]; |
| 201 if (existingKey == null) { | 201 if (existingKey == null) { |
| 202 // We are sure the key is not already in the set. | 202 // We are sure the key is not already in the set. |
| (...skipping 14 matching lines...) Expand all Loading... |
| 217 } | 217 } |
| 218 | 218 |
| 219 // We did not find an insertion slot. Look at the next one. | 219 // We did not find an insertion slot. Look at the next one. |
| 220 hash = _nextProbe(hash, numberOfProbes++, _keys.length); | 220 hash = _nextProbe(hash, numberOfProbes++, _keys.length); |
| 221 // _ensureCapacity has guaranteed the following cannot happen. | 221 // _ensureCapacity has guaranteed the following cannot happen. |
| 222 // assert(hash != initialHash); | 222 // assert(hash != initialHash); |
| 223 } | 223 } |
| 224 } | 224 } |
| 225 | 225 |
| 226 int _probeForLookup(K key) { | 226 int _probeForLookup(K key) { |
| 227 if (key == null) throw const NullPointerException(); | 227 if (key == null) throw new ArgumentError(null); |
| 228 int hash = _firstProbe(key.hashCode, _keys.length); | 228 int hash = _firstProbe(key.hashCode, _keys.length); |
| 229 int numberOfProbes = 1; | 229 int numberOfProbes = 1; |
| 230 int initialHash = hash; | 230 int initialHash = hash; |
| 231 while (true) { | 231 while (true) { |
| 232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. | 232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. |
| 233 Object existingKey = _keys[hash]; | 233 Object existingKey = _keys[hash]; |
| 234 // If the slot does not contain anything (in particular, it does not | 234 // If the slot does not contain anything (in particular, it does not |
| 235 // contain a deleted key), we know the key is not in the map. | 235 // contain a deleted key), we know the key is not in the map. |
| 236 if (existingKey == null) return -1; | 236 if (existingKey == null) return -1; |
| 237 // The key is in the map, return its index. | 237 // The key is in the map, return its index. |
| (...skipping 280 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 518 | 518 |
| 519 void clear() { | 519 void clear() { |
| 520 _map.clear(); | 520 _map.clear(); |
| 521 _list.clear(); | 521 _list.clear(); |
| 522 } | 522 } |
| 523 | 523 |
| 524 String toString() { | 524 String toString() { |
| 525 return Maps.mapToString(this); | 525 return Maps.mapToString(this); |
| 526 } | 526 } |
| 527 } | 527 } |
| OLD | NEW |