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

Side by Side Diff: pkg/dev_compiler/tool/input_sdk/private/linked_hash_map.dart

Issue 2994203002: Optimize DDC private library files. (Closed)
Patch Set: Address comments Created 3 years, 3 months 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
OLDNEW
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698