| 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 148 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 159 // The sentinel when a key is deleted from the map. | 159 // The sentinel when a key is deleted from the map. |
| 160 static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); | 160 static const _DeletedKeySentinel _DELETED_KEY = const _DeletedKeySentinel(); |
| 161 | 161 |
| 162 // The initial capacity of a hash map. | 162 // The initial capacity of a hash map. |
| 163 static const int _INITIAL_CAPACITY = 8; // must be power of 2 | 163 static const int _INITIAL_CAPACITY = 8; // must be power of 2 |
| 164 | 164 |
| 165 _HashMapImpl() { | 165 _HashMapImpl() { |
| 166 _numberOfEntries = 0; | 166 _numberOfEntries = 0; |
| 167 _numberOfDeleted = 0; | 167 _numberOfDeleted = 0; |
| 168 _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); | 168 _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY); |
| 169 _keys = new List(_INITIAL_CAPACITY); | 169 _keys = new List.fixedLength(_INITIAL_CAPACITY); |
| 170 _values = new List<V>(_INITIAL_CAPACITY); | 170 _values = new List<V>(_INITIAL_CAPACITY); |
| 171 } | 171 } |
| 172 | 172 |
| 173 factory _HashMapImpl.from(Map<K, V> other) { | 173 factory _HashMapImpl.from(Map<K, V> other) { |
| 174 Map<K, V> result = new _HashMapImpl<K, V>(); | 174 Map<K, V> result = new _HashMapImpl<K, V>(); |
| 175 other.forEach((K key, V value) { result[key] = value; }); | 175 other.forEach((K key, V value) { result[key] = value; }); |
| 176 return result; | 176 return result; |
| 177 } | 177 } |
| 178 | 178 |
| 179 static int _computeLoadLimit(int capacity) { | 179 static int _computeLoadLimit(int capacity) { |
| (...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 266 static bool _isPowerOfTwo(int x) { | 266 static bool _isPowerOfTwo(int x) { |
| 267 return ((x & (x - 1)) == 0); | 267 return ((x & (x - 1)) == 0); |
| 268 } | 268 } |
| 269 | 269 |
| 270 void _grow(int newCapacity) { | 270 void _grow(int newCapacity) { |
| 271 assert(_isPowerOfTwo(newCapacity)); | 271 assert(_isPowerOfTwo(newCapacity)); |
| 272 int capacity = _keys.length; | 272 int capacity = _keys.length; |
| 273 _loadLimit = _computeLoadLimit(newCapacity); | 273 _loadLimit = _computeLoadLimit(newCapacity); |
| 274 List oldKeys = _keys; | 274 List oldKeys = _keys; |
| 275 List<V> oldValues = _values; | 275 List<V> oldValues = _values; |
| 276 _keys = new List(newCapacity); | 276 _keys = new List.fixedLength(newCapacity); |
| 277 _values = new List<V>(newCapacity); | 277 _values = new List<V>(newCapacity); |
| 278 for (int i = 0; i < capacity; i++) { | 278 for (int i = 0; i < capacity; i++) { |
| 279 // [key] can be either of type [K] or [_DeletedKeySentinel]. | 279 // [key] can be either of type [K] or [_DeletedKeySentinel]. |
| 280 Object key = oldKeys[i]; | 280 Object key = oldKeys[i]; |
| 281 // 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. |
| 282 if (key == null || identical(key, _DELETED_KEY)) { | 282 if (key == null || identical(key, _DELETED_KEY)) { |
| 283 continue; | 283 continue; |
| 284 } | 284 } |
| 285 V value = oldValues[i]; | 285 V value = oldValues[i]; |
| 286 // Insert the {key, value} pair in their new slot. | 286 // Insert the {key, value} pair in their new slot. |
| (...skipping 231 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 |