OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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 // Efficient JavaScript based implementation of a linked hash map used as a | 5 // Efficient JavaScript based implementation of a linked hash map used as a |
6 // backing map for constant maps and the [LinkedHashMap] patch | 6 // backing map for constant maps and the [LinkedHashMap] patch |
7 | 7 |
8 part of dart._js_helper; | 8 part of dart._js_helper; |
9 | 9 |
10 // DDC-specific, just use Object-backed maps | 10 // DDC-specific, just use Object-backed maps |
11 //const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); | 11 //const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); |
12 | 12 |
13 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap<K, V> { | 13 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap<K, V> { |
| 14 @notNull |
14 int _length = 0; | 15 int _length = 0; |
15 | 16 |
16 // The hash map contents are divided into three parts: one part for | 17 // The hash map contents are divided into three parts: one part for |
17 // string keys, one for numeric keys, and one for the rest. String | 18 // string keys, one for numeric keys, and one for the rest. String |
18 // and numeric keys map directly to their linked cells, but the rest | 19 // and numeric keys map directly to their linked cells, but the rest |
19 // of the entries are stored in bucket lists of the form: | 20 // of the entries are stored in bucket lists of the form: |
20 // | 21 // |
21 // [cell-0, cell-1, ...] | 22 // [cell-0, cell-1, ...] |
22 // | 23 // |
23 // where all keys in the same bucket share the same hash code. | 24 // where all keys in the same bucket share the same hash code. |
24 var _strings; | 25 var _strings; |
25 var _nums; | 26 var _nums; |
26 var _rest; | 27 var _rest; |
27 | 28 |
28 // The keys and values are stored in cells that are linked together | 29 // The keys and values are stored in cells that are linked together |
29 // to form a double linked list. | 30 // to form a double linked list. |
30 LinkedHashMapCell/*<K, V>*/ _first; | 31 LinkedHashMapCell<K, V> _first; |
31 LinkedHashMapCell/*<K, V>*/ _last; | 32 LinkedHashMapCell<K, V> _last; |
32 | 33 |
33 // We track the number of modifications done to the key set of the | 34 // We track the number of modifications done to the key set of the |
34 // hash map to be able to throw when the map is modified while being | 35 // hash map to be able to throw when the map is modified while being |
35 // iterated over. | 36 // iterated over. |
36 int _modifications = 0; | 37 int _modifications = 0; |
37 | 38 |
38 // static bool get _supportsEs6Maps { | 39 // static bool get _supportsEs6Maps { |
39 // return JS('returns:bool;depends:none;effects:none;throws:never;gvn:true', | 40 // return JS('returns:bool;depends:none;effects:none;throws:never;gvn:true', |
40 // 'typeof Map != "undefined"'); | 41 // 'typeof Map != "undefined"'); |
41 // } | 42 // } |
42 | 43 |
43 JsLinkedHashMap(); | 44 JsLinkedHashMap(); |
44 | 45 |
45 /// If ES6 Maps are available returns a linked hash-map backed by an ES6 Map. | 46 /// If ES6 Maps are available returns a linked hash-map backed by an ES6 Map. |
46 // @ForceInline() | 47 // @ForceInline() |
47 factory JsLinkedHashMap.es6() { | 48 factory JsLinkedHashMap.es6() { |
48 // return (_USE_ES6_MAPS && JsLinkedHashMap._supportsEs6Maps) | 49 // return (_USE_ES6_MAPS && JsLinkedHashMap._supportsEs6Maps) |
49 // ? new Es6LinkedHashMap<K, V>() | 50 // ? new Es6LinkedHashMap<K, V>() |
50 // : new JsLinkedHashMap<K, V>(); | 51 // : new JsLinkedHashMap<K, V>(); |
51 return new JsLinkedHashMap<K, V>(); | 52 return new JsLinkedHashMap<K, V>(); |
52 } | 53 } |
53 | 54 |
| 55 @notNull |
54 int get length => _length; | 56 int get length => _length; |
| 57 @notNull |
55 bool get isEmpty => _length == 0; | 58 bool get isEmpty => _length == 0; |
| 59 @notNull |
56 bool get isNotEmpty => !isEmpty; | 60 bool get isNotEmpty => !isEmpty; |
57 | 61 |
58 Iterable<K> get keys { | 62 Iterable<K> get keys { |
59 return new LinkedHashMapKeyIterable<K>(this); | 63 return new LinkedHashMapKeyIterable<K>(this); |
60 } | 64 } |
61 | 65 |
62 Iterable<V> get values { | 66 Iterable<V> get values { |
63 return new MappedIterable<K, V>(keys, (each) => this[each]); | 67 return new MappedIterable<K, V>(keys, (each) => this[each]); |
64 } | 68 } |
65 | 69 |
| 70 @notNull |
66 bool containsKey(Object key) { | 71 bool containsKey(Object key) { |
67 if (_isStringKey(key)) { | 72 if (_isStringKey(key)) { |
68 var strings = _strings; | 73 var strings = _strings; |
69 if (strings == null) return false; | 74 if (strings == null) return false; |
70 return _containsTableEntry(strings, key); | 75 return _containsTableEntry(strings, key); |
71 } else if (_isNumericKey(key)) { | 76 } else if (_isNumericKey(key)) { |
72 var nums = _nums; | 77 var nums = _nums; |
73 if (nums == null) return false; | 78 if (nums == null) return false; |
74 return _containsTableEntry(nums, key); | 79 return _containsTableEntry(nums, key); |
75 } else { | 80 } else { |
76 return internalContainsKey(key); | 81 return internalContainsKey(key); |
77 } | 82 } |
78 } | 83 } |
79 | 84 |
| 85 @notNull |
80 bool internalContainsKey(Object key) { | 86 bool internalContainsKey(Object key) { |
81 var rest = _rest; | 87 var rest = _rest; |
82 if (rest == null) return false; | 88 if (rest == null) return false; |
83 var bucket = _getBucket(rest, key); | 89 var bucket = _getBucket(rest, key); |
84 return internalFindBucketIndex(bucket, key) >= 0; | 90 return internalFindBucketIndex(bucket, key) >= 0; |
85 } | 91 } |
86 | 92 |
87 bool containsValue(Object value) { | 93 bool containsValue(Object value) { |
88 return keys.any((each) => this[each] == value); | 94 return keys.any((each) => this[each] == value); |
89 } | 95 } |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
262 if (next == null) { | 268 if (next == null) { |
263 assert(cell == _last); | 269 assert(cell == _last); |
264 _last = previous; | 270 _last = previous; |
265 } else { | 271 } else { |
266 next._previous = previous; | 272 next._previous = previous; |
267 } | 273 } |
268 _length--; | 274 _length--; |
269 _modified(); | 275 _modified(); |
270 } | 276 } |
271 | 277 |
| 278 @notNull |
272 static bool _isStringKey(var key) { | 279 static bool _isStringKey(var key) { |
273 return key is String; | 280 return key is String; |
274 } | 281 } |
275 | 282 |
| 283 @notNull |
276 static bool _isNumericKey(var key) { | 284 static bool _isNumericKey(var key) { |
277 // Only treat unsigned 30-bit integers as numeric keys. This way, | 285 // Only treat unsigned 30-bit integers as numeric keys. This way, |
278 // we avoid converting them to strings when we use them as keys in | 286 // we avoid converting them to strings when we use them as keys in |
279 // the JavaScript hash table object. | 287 // the JavaScript hash table object. |
280 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | 288 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); |
281 } | 289 } |
282 | 290 |
283 int internalComputeHashCode(var key) { | 291 int internalComputeHashCode(var key) { |
284 // We force the hash codes to be unsigned 30-bit integers to avoid | 292 // We force the hash codes to be unsigned 30-bit integers to avoid |
285 // issues with problematic keys like '__proto__'. Another option | 293 // issues with problematic keys like '__proto__'. Another option |
286 // would be to throw an exception if the hash code isn't a number. | 294 // would be to throw an exception if the hash code isn't a number. |
287 return JS('int', '# & 0x3ffffff', key.hashCode); | 295 return JS('int', '# & 0x3ffffff', key.hashCode); |
288 } | 296 } |
289 | 297 |
290 List<dynamic/*=LinkedHashMapCell<K, V>*/ > _getBucket(var table, var key) { | 298 List<dynamic/*=LinkedHashMapCell<K, V>*/ > _getBucket(var table, var key) { |
291 var hash = internalComputeHashCode(key); | 299 var hash = internalComputeHashCode(key); |
292 return _getTableBucket(table, hash); | 300 return _getTableBucket(table, hash); |
293 } | 301 } |
294 | 302 |
| 303 @notNull |
295 int internalFindBucketIndex(var bucket, var key) { | 304 int internalFindBucketIndex(var bucket, var key) { |
296 if (bucket == null) return -1; | 305 if (bucket == null) return -1; |
297 int length = JS('int', '#.length', bucket); | 306 int length = JS('int', '#.length', bucket); |
298 for (int i = 0; i < length; i++) { | 307 for (int i = 0; i < length; i++) { |
299 LinkedHashMapCell/*<K, V>*/ cell = JS('var', '#[#]', bucket, i); | 308 LinkedHashMapCell/*<K, V>*/ cell = JS('var', '#[#]', bucket, i); |
300 if (cell.hashMapCellKey == key) return i; | 309 if (cell.hashMapCellKey == key) return i; |
301 } | 310 } |
302 return -1; | 311 return -1; |
303 } | 312 } |
304 | 313 |
305 String toString() => Maps.mapToString(this); | 314 String toString() => Maps.mapToString(this); |
306 | 315 |
307 /*=LinkedHashMapCell<K, V>*/ _getTableCell(var table, var key) { | 316 /*=LinkedHashMapCell<K, V>*/ _getTableCell(var table, var key) { |
308 return JS('var', '#[#]', table, key); | 317 return JS('var', '#[#]', table, key); |
309 } | 318 } |
310 | 319 |
311 /*=List<LinkedHashMapCell<K, V>>*/ _getTableBucket(var table, var key) { | 320 /*=List<LinkedHashMapCell<K, V>>*/ _getTableBucket(var table, var key) { |
312 return JS('var', '#[#]', table, key); | 321 return JS('var', '#[#]', table, key); |
313 } | 322 } |
314 | 323 |
315 void _setTableEntry(var table, var key, var value) { | 324 void _setTableEntry(var table, var key, var value) { |
316 assert(value != null); | 325 assert(value != null); |
317 JS('void', '#[#] = #', table, key, value); | 326 JS('void', '#[#] = #', table, key, value); |
318 } | 327 } |
319 | 328 |
320 void _deleteTableEntry(var table, var key) { | 329 void _deleteTableEntry(var table, var key) { |
321 JS('void', 'delete #[#]', table, key); | 330 JS('void', 'delete #[#]', table, key); |
322 } | 331 } |
323 | 332 |
| 333 @notNull |
324 bool _containsTableEntry(var table, var key) { | 334 bool _containsTableEntry(var table, var key) { |
325 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(table, key); | 335 LinkedHashMapCell/*<K, V>*/ cell = _getTableCell(table, key); |
326 return cell != null; | 336 return cell != null; |
327 } | 337 } |
328 | 338 |
329 _newHashTable() { | 339 _newHashTable() { |
330 // Create a new JavaScript object to be used as a hash table. Use | 340 // Create a new JavaScript object to be used as a hash table. Use |
331 // Object.create to avoid the properties on Object.prototype | 341 // Object.create to avoid the properties on Object.prototype |
332 // showing up as entries. | 342 // showing up as entries. |
333 var table = JS('var', 'Object.create(null)'); | 343 var table = JS('var', 'Object.create(null)'); |
(...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
428 } else if (_cell == null) { | 438 } else if (_cell == null) { |
429 _current = null; | 439 _current = null; |
430 return false; | 440 return false; |
431 } else { | 441 } else { |
432 _current = _cell.hashMapCellKey; | 442 _current = _cell.hashMapCellKey; |
433 _cell = _cell._next; | 443 _cell = _cell._next; |
434 return true; | 444 return true; |
435 } | 445 } |
436 } | 446 } |
437 } | 447 } |
OLD | NEW |