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 _js_helper; | 8 part of _js_helper; |
9 | 9 |
10 const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); | |
11 | |
12 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { | 10 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { |
13 int _length = 0; | 11 int _length = 0; |
14 | 12 |
15 // The hash map contents are divided into three parts: one part for | 13 // The hash map contents are divided into three parts: one part for |
16 // string keys, one for numeric keys, and one for the rest. String | 14 // string keys, one for numeric keys, and one for the rest. String |
17 // and numeric keys map directly to their linked cells, but the rest | 15 // and numeric keys map directly to their linked cells, but the rest |
18 // of the entries are stored in bucket lists of the form: | 16 // of the entries are stored in bucket lists of the form: |
19 // | 17 // |
20 // [cell-0, cell-1, ...] | 18 // [cell-0, cell-1, ...] |
21 // | 19 // |
22 // where all keys in the same bucket share the same hash code. | 20 // where all keys in the same bucket share the same hash code. |
23 var _strings; | 21 var _strings; |
24 var _nums; | 22 var _nums; |
25 var _rest; | 23 var _rest; |
26 | 24 |
27 // The keys and values are stored in cells that are linked together | 25 // The keys and values are stored in cells that are linked together |
28 // to form a double linked list. | 26 // to form a double linked list. |
29 LinkedHashMapCell _first; | 27 LinkedHashMapCell _first; |
30 LinkedHashMapCell _last; | 28 LinkedHashMapCell _last; |
31 | 29 |
32 // We track the number of modifications done to the key set of the | 30 // We track the number of modifications done to the key set of the |
33 // hash map to be able to throw when the map is modified while being | 31 // hash map to be able to throw when the map is modified while being |
34 // iterated over. | 32 // iterated over. |
35 int _modifications = 0; | 33 int _modifications = 0; |
36 | 34 |
37 static bool get _supportsEs6Maps { | |
38 return JS('returns:bool;depends:none;effects:none;', | |
39 'typeof Map != "undefined"'); | |
40 } | |
41 | |
42 JsLinkedHashMap(); | 35 JsLinkedHashMap(); |
43 | 36 |
44 /// If ES6 Maps are available returns a linked hash-map backed by an ES6 Map. | |
45 factory JsLinkedHashMap.es6() { | |
46 if (_USE_ES6_MAPS && JsLinkedHashMap._supportsEs6Maps) { | |
47 return new Es6LinkedHashMap<K, V>(); | |
48 } else { | |
49 return new JsLinkedHashMap<K, V>(); | |
50 } | |
51 } | |
52 | 37 |
53 int get length => _length; | 38 int get length => _length; |
54 bool get isEmpty => _length == 0; | 39 bool get isEmpty => _length == 0; |
55 bool get isNotEmpty => !isEmpty; | 40 bool get isNotEmpty => !isEmpty; |
56 | 41 |
57 Iterable<K> get keys { | 42 Iterable<K> get keys { |
58 return new LinkedHashMapKeyIterable<K>(this); | 43 return new LinkedHashMapKeyIterable<K>(this); |
59 } | 44 } |
60 | 45 |
61 Iterable<V> get values { | 46 Iterable<V> get values { |
62 return new MappedIterable<K, V>(keys, (each) => this[each]); | 47 return new MappedIterable<K, V>(keys, (each) => this[each]); |
63 } | 48 } |
64 | 49 |
65 bool containsKey(Object key) { | 50 bool containsKey(Object key) { |
66 if (_isStringKey(key)) { | 51 if (_isStringKey(key)) { |
67 var strings = _strings; | 52 var strings = _strings; |
68 if (strings == null) return false; | 53 if (strings == null) return false; |
69 return _containsTableEntry(strings, key); | 54 LinkedHashMapCell cell = _getTableEntry(strings, key); |
| 55 return cell != null; |
70 } else if (_isNumericKey(key)) { | 56 } else if (_isNumericKey(key)) { |
71 var nums = _nums; | 57 var nums = _nums; |
72 if (nums == null) return false; | 58 if (nums == null) return false; |
73 return _containsTableEntry(nums, key); | 59 LinkedHashMapCell cell = _getTableEntry(nums, key); |
| 60 return cell != null; |
74 } else { | 61 } else { |
75 return internalContainsKey(key); | 62 return internalContainsKey(key); |
76 } | 63 } |
77 } | 64 } |
78 | 65 |
79 bool internalContainsKey(Object key) { | 66 bool internalContainsKey(Object key) { |
80 var rest = _rest; | 67 var rest = _rest; |
81 if (rest == null) return false; | 68 if (rest == null) return false; |
82 var bucket = _getBucket(rest, key); | 69 var bucket = _getBucket(rest, key); |
83 return internalFindBucketIndex(bucket, key) >= 0; | 70 return internalFindBucketIndex(bucket, key) >= 0; |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
130 _addHashTableEntry(nums, key, value); | 117 _addHashTableEntry(nums, key, value); |
131 } else { | 118 } else { |
132 internalSet(key, value); | 119 internalSet(key, value); |
133 } | 120 } |
134 } | 121 } |
135 | 122 |
136 void internalSet(K key, V value) { | 123 void internalSet(K key, V value) { |
137 var rest = _rest; | 124 var rest = _rest; |
138 if (rest == null) _rest = rest = _newHashTable(); | 125 if (rest == null) _rest = rest = _newHashTable(); |
139 var hash = internalComputeHashCode(key); | 126 var hash = internalComputeHashCode(key); |
140 var bucket = _getTableEntry(rest, hash); | 127 var bucket = JS('var', '#[#]', rest, hash); |
141 if (bucket == null) { | 128 if (bucket == null) { |
142 LinkedHashMapCell cell = _newLinkedCell(key, value); | 129 LinkedHashMapCell cell = _newLinkedCell(key, value); |
143 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | 130 _setTableEntry(rest, hash, JS('var', '[#]', cell)); |
144 } else { | 131 } else { |
145 int index = internalFindBucketIndex(bucket, key); | 132 int index = internalFindBucketIndex(bucket, key); |
146 if (index >= 0) { | 133 if (index >= 0) { |
147 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | 134 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); |
148 cell.hashMapCellValue = value; | 135 cell.hashMapCellValue = value; |
149 } else { | 136 } else { |
150 LinkedHashMapCell cell = _newLinkedCell(key, value); | 137 LinkedHashMapCell cell = _newLinkedCell(key, value); |
(...skipping 108 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 assert(cell == _last); | 246 assert(cell == _last); |
260 _last = previous; | 247 _last = previous; |
261 } else { | 248 } else { |
262 next._previous = previous; | 249 next._previous = previous; |
263 } | 250 } |
264 _length--; | 251 _length--; |
265 _modified(); | 252 _modified(); |
266 } | 253 } |
267 | 254 |
268 static bool _isStringKey(var key) { | 255 static bool _isStringKey(var key) { |
269 return key is String; | 256 return key is String && key != '__proto__'; |
270 } | 257 } |
271 | 258 |
272 static bool _isNumericKey(var key) { | 259 static bool _isNumericKey(var key) { |
273 // Only treat unsigned 30-bit integers as numeric keys. This way, | 260 // Only treat unsigned 30-bit integers as numeric keys. This way, |
274 // we avoid converting them to strings when we use them as keys in | 261 // we avoid converting them to strings when we use them as keys in |
275 // the JavaScript hash table object. | 262 // the JavaScript hash table object. |
276 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | 263 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); |
277 } | 264 } |
278 | 265 |
279 int internalComputeHashCode(var key) { | 266 int internalComputeHashCode(var key) { |
280 // We force the hash codes to be unsigned 30-bit integers to avoid | 267 // We force the hash codes to be unsigned 30-bit integers to avoid |
281 // issues with problematic keys like '__proto__'. Another option | 268 // issues with problematic keys like '__proto__'. Another option |
282 // would be to throw an exception if the hash code isn't a number. | 269 // would be to throw an exception if the hash code isn't a number. |
283 return JS('int', '# & 0x3ffffff', key.hashCode); | 270 return JS('int', '# & 0x3ffffff', key.hashCode); |
284 } | 271 } |
285 | 272 |
| 273 static _getTableEntry(var table, var key) { |
| 274 return JS('var', '#[#]', table, key); |
| 275 } |
| 276 |
| 277 static void _setTableEntry(var table, var key, var value) { |
| 278 assert(value != null); |
| 279 JS('void', '#[#] = #', table, key, value); |
| 280 } |
| 281 |
| 282 static void _deleteTableEntry(var table, var key) { |
| 283 JS('void', 'delete #[#]', table, key); |
| 284 } |
| 285 |
286 List _getBucket(var table, var key) { | 286 List _getBucket(var table, var key) { |
287 var hash = internalComputeHashCode(key); | 287 var hash = internalComputeHashCode(key); |
288 return _getTableEntry(table, hash); | 288 return JS('var', '#[#]', table, hash); |
289 } | 289 } |
290 | 290 |
291 int internalFindBucketIndex(var bucket, var key) { | 291 int internalFindBucketIndex(var bucket, var key) { |
292 if (bucket == null) return -1; | 292 if (bucket == null) return -1; |
293 int length = JS('int', '#.length', bucket); | 293 int length = JS('int', '#.length', bucket); |
294 for (int i = 0; i < length; i++) { | 294 for (int i = 0; i < length; i++) { |
295 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | 295 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); |
296 if (cell.hashMapCellKey == key) return i; | 296 if (cell.hashMapCellKey == key) return i; |
297 } | 297 } |
298 return -1; | 298 return -1; |
299 } | 299 } |
300 | 300 |
301 String toString() => Maps.mapToString(this); | 301 static _newHashTable() { |
302 | |
303 _getTableEntry(var table, var key) { | |
304 return JS('var', '#[#]', table, key); | |
305 } | |
306 | |
307 void _setTableEntry(var table, var key, var value) { | |
308 assert(value != null); | |
309 JS('void', '#[#] = #', table, key, value); | |
310 } | |
311 | |
312 void _deleteTableEntry(var table, var key) { | |
313 JS('void', 'delete #[#]', table, key); | |
314 } | |
315 | |
316 bool _containsTableEntry(var table, var key) { | |
317 LinkedHashMapCell cell = _getTableEntry(table, key); | |
318 return cell != null; | |
319 } | |
320 | |
321 _newHashTable() { | |
322 // Create a new JavaScript object to be used as a hash table. Use | 302 // Create a new JavaScript object to be used as a hash table. Use |
323 // Object.create to avoid the properties on Object.prototype | 303 // Object.create to avoid the properties on Object.prototype |
324 // showing up as entries. | 304 // showing up as entries. |
325 var table = JS('var', 'Object.create(null)'); | 305 var table = JS('var', 'Object.create(null)'); |
326 // Attempt to force the hash table into 'dictionary' mode by | 306 // Attempt to force the hash table into 'dictionary' mode by |
327 // adding a property to it and deleting it again. | 307 // adding a property to it and deleting it again. |
328 var temporaryKey = '<non-identifier-key>'; | 308 var temporaryKey = '<non-identifier-key>'; |
329 _setTableEntry(table, temporaryKey, table); | 309 _setTableEntry(table, temporaryKey, table); |
330 _deleteTableEntry(table, temporaryKey); | 310 _deleteTableEntry(table, temporaryKey); |
331 return table; | 311 return table; |
332 } | 312 } |
333 } | |
334 | 313 |
335 class Es6LinkedHashMap<K, V> extends JsLinkedHashMap<K, V> { | 314 String toString() => Maps.mapToString(this); |
336 | |
337 @override | |
338 _getTableEntry(var table, var key) { | |
339 return JS('var', '#.get(#)', table, key); | |
340 } | |
341 | |
342 @override | |
343 void _setTableEntry(var table, var key, var value) { | |
344 JS('void', '#.set(#, #)', table, key, value); | |
345 } | |
346 | |
347 @override | |
348 void _deleteTableEntry(var table, var key) { | |
349 JS('void', '#.delete(#)', table, key); | |
350 } | |
351 | |
352 @override | |
353 bool _containsTableEntry(var table, var key) { | |
354 return JS('bool', '#.has(#)', table, key); | |
355 } | |
356 | |
357 @override | |
358 _newHashTable() { | |
359 return JS('var', 'new Map()'); | |
360 } | |
361 } | 315 } |
362 | 316 |
363 class LinkedHashMapCell { | 317 class LinkedHashMapCell { |
364 final hashMapCellKey; | 318 final hashMapCellKey; |
365 var hashMapCellValue; | 319 var hashMapCellValue; |
366 | 320 |
367 LinkedHashMapCell _next; | 321 LinkedHashMapCell _next; |
368 LinkedHashMapCell _previous; | 322 LinkedHashMapCell _previous; |
369 | 323 |
370 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue); | 324 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue); |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
417 } else if (_cell == null) { | 371 } else if (_cell == null) { |
418 _current = null; | 372 _current = null; |
419 return false; | 373 return false; |
420 } else { | 374 } else { |
421 _current = _cell.hashMapCellKey; | 375 _current = _cell.hashMapCellKey; |
422 _cell = _cell._next; | 376 _cell = _cell._next; |
423 return true; | 377 return true; |
424 } | 378 } |
425 } | 379 } |
426 } | 380 } |
OLD | NEW |