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

Side by Side Diff: sdk/lib/core/map.dart

Issue 11361190: a === b -> identical(a, b) (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Address comments. Created 8 years, 1 month 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
« no previous file with comments | « sdk/lib/core/expect.dart ('k') | sdk/lib/core/options.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 180 matching lines...) Expand 10 before | Expand all | Expand 10 after
191 int _probeForAdding(K key) { 191 int _probeForAdding(K key) {
192 if (key == null) throw const NullPointerException(); 192 if (key == null) throw const NullPointerException();
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.
203 // If the current slot is empty and we didn't find any 203 // If the current slot is empty and we didn't find any
204 // insertion slot before, return this slot. 204 // insertion slot before, return this slot.
205 if (insertionIndex < 0) return hash; 205 if (insertionIndex < 0) return hash;
206 // If we did find an insertion slot before, return it. 206 // If we did find an insertion slot before, return it.
207 return insertionIndex; 207 return insertionIndex;
208 } else if (existingKey == key) { 208 } else if (existingKey == key) {
209 // The key is already in the map. Return its slot. 209 // The key is already in the map. Return its slot.
210 return hash; 210 return hash;
211 } else if ((insertionIndex < 0) && (_DELETED_KEY === existingKey)) { 211 } else if ((insertionIndex < 0) &&
212 (identical(existingKey, _DELETED_KEY))) {
212 // The slot contains a deleted element. Because previous calls to this 213 // The slot contains a deleted element. Because previous calls to this
213 // method may not have had this slot deleted, we must continue iterate 214 // method may not have had this slot deleted, we must continue iterate
214 // to find if there is a slot with the given key. 215 // to find if there is a slot with the given key.
215 insertionIndex = hash; 216 insertionIndex = hash;
216 } 217 }
217 218
218 // 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.
219 hash = _nextProbe(hash, numberOfProbes++, _keys.length); 220 hash = _nextProbe(hash, numberOfProbes++, _keys.length);
220 // _ensureCapacity has guaranteed the following cannot happen. 221 // _ensureCapacity has guaranteed the following cannot happen.
221 // assert(hash != initialHash); 222 // assert(hash != initialHash);
222 } 223 }
223 } 224 }
224 225
225 int _probeForLookup(K key) { 226 int _probeForLookup(K key) {
226 if (key == null) throw const NullPointerException(); 227 if (key == null) throw const NullPointerException();
227 int hash = _firstProbe(key.hashCode, _keys.length); 228 int hash = _firstProbe(key.hashCode, _keys.length);
228 int numberOfProbes = 1; 229 int numberOfProbes = 1;
229 int initialHash = hash; 230 int initialHash = hash;
230 while (true) { 231 while (true) {
231 // [existingKey] can be either of type [K] or [_DeletedKeySentinel]. 232 // [existingKey] can be either of type [K] or [_DeletedKeySentinel].
232 Object existingKey = _keys[hash]; 233 Object existingKey = _keys[hash];
233 // 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
234 // 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.
235 if (existingKey === null) return -1; 236 if (existingKey == null) return -1;
236 // The key is in the map, return its index. 237 // The key is in the map, return its index.
237 if (existingKey == key) return hash; 238 if (existingKey == key) return hash;
238 // Go to the next probe. 239 // Go to the next probe.
239 hash = _nextProbe(hash, numberOfProbes++, _keys.length); 240 hash = _nextProbe(hash, numberOfProbes++, _keys.length);
240 // _ensureCapacity has guaranteed the following cannot happen. 241 // _ensureCapacity has guaranteed the following cannot happen.
241 // assert(hash != initialHash); 242 // assert(hash != initialHash);
242 } 243 }
243 } 244 }
244 245
245 void _ensureCapacity() { 246 void _ensureCapacity() {
(...skipping 25 matching lines...) Expand all
271 int capacity = _keys.length; 272 int capacity = _keys.length;
272 _loadLimit = _computeLoadLimit(newCapacity); 273 _loadLimit = _computeLoadLimit(newCapacity);
273 List oldKeys = _keys; 274 List oldKeys = _keys;
274 List<V> oldValues = _values; 275 List<V> oldValues = _values;
275 _keys = new List(newCapacity); 276 _keys = new List(newCapacity);
276 _values = new List<V>(newCapacity); 277 _values = new List<V>(newCapacity);
277 for (int i = 0; i < capacity; i++) { 278 for (int i = 0; i < capacity; i++) {
278 // [key] can be either of type [K] or [_DeletedKeySentinel]. 279 // [key] can be either of type [K] or [_DeletedKeySentinel].
279 Object key = oldKeys[i]; 280 Object key = oldKeys[i];
280 // If there is no key, we don't need to deal with the current slot. 281 // If there is no key, we don't need to deal with the current slot.
281 if (key === null || key === _DELETED_KEY) { 282 if (key == null || identical(key, _DELETED_KEY)) {
282 continue; 283 continue;
283 } 284 }
284 V value = oldValues[i]; 285 V value = oldValues[i];
285 // Insert the {key, value} pair in their new slot. 286 // Insert the {key, value} pair in their new slot.
286 int newIndex = _probeForAdding(key); 287 int newIndex = _probeForAdding(key);
287 _keys[newIndex] = key; 288 _keys[newIndex] = key;
288 _values[newIndex] = value; 289 _values[newIndex] = value;
289 } 290 }
290 _numberOfDeleted = 0; 291 _numberOfDeleted = 0;
291 } 292 }
292 293
293 void clear() { 294 void clear() {
294 _numberOfEntries = 0; 295 _numberOfEntries = 0;
295 _numberOfDeleted = 0; 296 _numberOfDeleted = 0;
296 int length = _keys.length; 297 int length = _keys.length;
297 for (int i = 0; i < length; i++) { 298 for (int i = 0; i < length; i++) {
298 _keys[i] = null; 299 _keys[i] = null;
299 _values[i] = null; 300 _values[i] = null;
300 } 301 }
301 } 302 }
302 303
303 void operator []=(K key, V value) { 304 void operator []=(K key, V value) {
304 _ensureCapacity(); 305 _ensureCapacity();
305 int index = _probeForAdding(key); 306 int index = _probeForAdding(key);
306 if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) { 307 if ((_keys[index] == null) || (identical(_keys[index], _DELETED_KEY))) {
307 _numberOfEntries++; 308 _numberOfEntries++;
308 } 309 }
309 _keys[index] = key; 310 _keys[index] = key;
310 _values[index] = value; 311 _values[index] = value;
311 } 312 }
312 313
313 V operator [](K key) { 314 V operator [](K key) {
314 int index = _probeForLookup(key); 315 int index = _probeForLookup(key);
315 if (index < 0) return null; 316 if (index < 0) return null;
316 return _values[index]; 317 return _values[index];
(...skipping 27 matching lines...) Expand all
344 } 345 }
345 346
346 int get length { 347 int get length {
347 return _numberOfEntries; 348 return _numberOfEntries;
348 } 349 }
349 350
350 void forEach(void f(K key, V value)) { 351 void forEach(void f(K key, V value)) {
351 int length = _keys.length; 352 int length = _keys.length;
352 for (int i = 0; i < length; i++) { 353 for (int i = 0; i < length; i++) {
353 var key = _keys[i]; 354 var key = _keys[i];
354 if ((key !== null) && (key !== _DELETED_KEY)) { 355 if ((key != null) && (!identical(key, _DELETED_KEY))) {
355 f(key, _values[i]); 356 f(key, _values[i]);
356 } 357 }
357 } 358 }
358 } 359 }
359 360
360 361
361 Collection<K> get keys { 362 Collection<K> get keys {
362 List<K> list = new List<K>(length); 363 List<K> list = new List<K>(length);
363 int i = 0; 364 int i = 0;
364 forEach(void _(K key, V value) { 365 forEach(void _(K key, V value) {
(...skipping 12 matching lines...) Expand all
377 } 378 }
378 379
379 bool containsKey(K key) { 380 bool containsKey(K key) {
380 return (_probeForLookup(key) != -1); 381 return (_probeForLookup(key) != -1);
381 } 382 }
382 383
383 bool containsValue(V value) { 384 bool containsValue(V value) {
384 int length = _values.length; 385 int length = _values.length;
385 for (int i = 0; i < length; i++) { 386 for (int i = 0; i < length; i++) {
386 var key = _keys[i]; 387 var key = _keys[i];
387 if ((key !== null) && (key !== _DELETED_KEY)) { 388 if ((key != null) && (!identical(key, _DELETED_KEY))) {
388 if (_values[i] == value) return true; 389 if (_values[i] == value) return true;
389 } 390 }
390 } 391 }
391 return false; 392 return false;
392 } 393 }
393 394
394 String toString() { 395 String toString() {
395 return Maps.mapToString(this); 396 return Maps.mapToString(this);
396 } 397 }
397 } 398 }
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
443 if (_map.containsKey(key)) { 444 if (_map.containsKey(key)) {
444 _map[key].element.value = value; 445 _map[key].element.value = value;
445 } else { 446 } else {
446 _list.addLast(new _KeyValuePair<K, V>(key, value)); 447 _list.addLast(new _KeyValuePair<K, V>(key, value));
447 _map[key] = _list.lastEntry(); 448 _map[key] = _list.lastEntry();
448 } 449 }
449 } 450 }
450 451
451 V operator [](K key) { 452 V operator [](K key) {
452 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key]; 453 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map[key];
453 if (entry === null) return null; 454 if (entry == null) return null;
454 return entry.element.value; 455 return entry.element.value;
455 } 456 }
456 457
457 V remove(K key) { 458 V remove(K key) {
458 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key); 459 DoubleLinkedQueueEntry<_KeyValuePair<K, V>> entry = _map.remove(key);
459 if (entry === null) return null; 460 if (entry == null) return null;
460 entry.remove(); 461 entry.remove();
461 return entry.element.value; 462 return entry.element.value;
462 } 463 }
463 464
464 V putIfAbsent(K key, V ifAbsent()) { 465 V putIfAbsent(K key, V ifAbsent()) {
465 V value = this[key]; 466 V value = this[key];
466 if ((this[key] === null) && !(containsKey(key))) { 467 if ((this[key] == null) && !(containsKey(key))) {
467 value = ifAbsent(); 468 value = ifAbsent();
468 this[key] = value; 469 this[key] = value;
469 } 470 }
470 return value; 471 return value;
471 } 472 }
472 473
473 Collection<K> get keys { 474 Collection<K> get keys {
474 List<K> list = new List<K>(length); 475 List<K> list = new List<K>(length);
475 int index = 0; 476 int index = 0;
476 _list.forEach(void _(_KeyValuePair<K, V> entry) { 477 _list.forEach(void _(_KeyValuePair<K, V> entry) {
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after
517 518
518 void clear() { 519 void clear() {
519 _map.clear(); 520 _map.clear();
520 _list.clear(); 521 _list.clear();
521 } 522 }
522 523
523 String toString() { 524 String toString() {
524 return Maps.mapToString(this); 525 return Maps.mapToString(this);
525 } 526 }
526 } 527 }
OLDNEW
« no previous file with comments | « sdk/lib/core/expect.dart ('k') | sdk/lib/core/options.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698