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 |