| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 // Efficient JavaScript based implementation of a linked hash map used as a | |
| 6 // backing map for constant maps and the [LinkedHashMap] patch | |
| 7 | |
| 8 part of _js_helper; | |
| 9 | |
| 10 const _USE_ES6_MAPS = const bool.fromEnvironment("dart2js.use.es6.maps"); | |
| 11 | |
| 12 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { | |
| 13 int _length = 0; | |
| 14 | |
| 15 // 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 | |
| 17 // and numeric keys map directly to their linked cells, but the rest | |
| 18 // of the entries are stored in bucket lists of the form: | |
| 19 // | |
| 20 // [cell-0, cell-1, ...] | |
| 21 // | |
| 22 // where all keys in the same bucket share the same hash code. | |
| 23 var _strings; | |
| 24 var _nums; | |
| 25 var _rest; | |
| 26 | |
| 27 // The keys and values are stored in cells that are linked together | |
| 28 // to form a double linked list. | |
| 29 LinkedHashMapCell _first; | |
| 30 LinkedHashMapCell _last; | |
| 31 | |
| 32 // 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 | |
| 34 // iterated over. | |
| 35 int _modifications = 0; | |
| 36 | |
| 37 static bool get _supportsEs6Maps { | |
| 38 return JS('returns:bool;depends:none;effects:none;throws:never;gvn:true', | |
| 39 'typeof Map != "undefined"'); | |
| 40 } | |
| 41 | |
| 42 JsLinkedHashMap(); | |
| 43 | |
| 44 /// If ES6 Maps are available returns a linked hash-map backed by an ES6 Map. | |
| 45 @ForceInline() | |
| 46 factory JsLinkedHashMap.es6() { | |
| 47 return (_USE_ES6_MAPS && JsLinkedHashMap._supportsEs6Maps) | |
| 48 ? new Es6LinkedHashMap<K, V>() | |
| 49 : new JsLinkedHashMap<K, V>(); | |
| 50 } | |
| 51 | |
| 52 int get length => _length; | |
| 53 bool get isEmpty => _length == 0; | |
| 54 bool get isNotEmpty => !isEmpty; | |
| 55 | |
| 56 Iterable<K> get keys { | |
| 57 return new LinkedHashMapKeyIterable<K>(this); | |
| 58 } | |
| 59 | |
| 60 Iterable<V> get values { | |
| 61 return new MappedIterable<K, V>(keys, (each) => this[each]); | |
| 62 } | |
| 63 | |
| 64 bool containsKey(Object key) { | |
| 65 if (_isStringKey(key)) { | |
| 66 var strings = _strings; | |
| 67 if (strings == null) return false; | |
| 68 return _containsTableEntry(strings, key); | |
| 69 } else if (_isNumericKey(key)) { | |
| 70 var nums = _nums; | |
| 71 if (nums == null) return false; | |
| 72 return _containsTableEntry(nums, key); | |
| 73 } else { | |
| 74 return internalContainsKey(key); | |
| 75 } | |
| 76 } | |
| 77 | |
| 78 bool internalContainsKey(Object key) { | |
| 79 var rest = _rest; | |
| 80 if (rest == null) return false; | |
| 81 var bucket = _getBucket(rest, key); | |
| 82 return internalFindBucketIndex(bucket, key) >= 0; | |
| 83 } | |
| 84 | |
| 85 bool containsValue(Object value) { | |
| 86 return keys.any((each) => this[each] == value); | |
| 87 } | |
| 88 | |
| 89 void addAll(Map<K, V> other) { | |
| 90 other.forEach((K key, V value) { | |
| 91 this[key] = value; | |
| 92 }); | |
| 93 } | |
| 94 | |
| 95 V operator[](Object key) { | |
| 96 if (_isStringKey(key)) { | |
| 97 var strings = _strings; | |
| 98 if (strings == null) return null; | |
| 99 LinkedHashMapCell cell = _getTableEntry(strings, key); | |
| 100 return (cell == null) ? null : cell.hashMapCellValue; | |
| 101 } else if (_isNumericKey(key)) { | |
| 102 var nums = _nums; | |
| 103 if (nums == null) return null; | |
| 104 LinkedHashMapCell cell = _getTableEntry(nums, key); | |
| 105 return (cell == null) ? null : cell.hashMapCellValue; | |
| 106 } else { | |
| 107 return internalGet(key); | |
| 108 } | |
| 109 } | |
| 110 | |
| 111 V internalGet(Object key) { | |
| 112 var rest = _rest; | |
| 113 if (rest == null) return null; | |
| 114 var bucket = _getBucket(rest, key); | |
| 115 int index = internalFindBucketIndex(bucket, key); | |
| 116 if (index < 0) return null; | |
| 117 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 118 return cell.hashMapCellValue; | |
| 119 } | |
| 120 | |
| 121 void operator[]=(K key, V value) { | |
| 122 if (_isStringKey(key)) { | |
| 123 var strings = _strings; | |
| 124 if (strings == null) _strings = strings = _newHashTable(); | |
| 125 _addHashTableEntry(strings, key, value); | |
| 126 } else if (_isNumericKey(key)) { | |
| 127 var nums = _nums; | |
| 128 if (nums == null) _nums = nums = _newHashTable(); | |
| 129 _addHashTableEntry(nums, key, value); | |
| 130 } else { | |
| 131 internalSet(key, value); | |
| 132 } | |
| 133 } | |
| 134 | |
| 135 void internalSet(K key, V value) { | |
| 136 var rest = _rest; | |
| 137 if (rest == null) _rest = rest = _newHashTable(); | |
| 138 var hash = internalComputeHashCode(key); | |
| 139 var bucket = _getTableEntry(rest, hash); | |
| 140 if (bucket == null) { | |
| 141 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 142 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | |
| 143 } else { | |
| 144 int index = internalFindBucketIndex(bucket, key); | |
| 145 if (index >= 0) { | |
| 146 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | |
| 147 cell.hashMapCellValue = value; | |
| 148 } else { | |
| 149 LinkedHashMapCell cell = _newLinkedCell(key, value); | |
| 150 JS('void', '#.push(#)', bucket, cell); | |
| 151 } | |
| 152 } | |
| 153 } | |
| 154 | |
| 155 V putIfAbsent(K key, V ifAbsent()) { | |
| 156 if (containsKey(key)) return this[key]; | |
| 157 V value = ifAbsent(); | |
| 158 this[key] = value; | |
| 159 return value; | |
| 160 } | |
| 161 | |
| 162 V remove(Object key) { | |
| 163 if (_isStringKey(key)) { | |
| 164 return _removeHashTableEntry(_strings, key); | |
| 165 } else if (_isNumericKey(key)) { | |
| 166 return _removeHashTableEntry(_nums, key); | |
| 167 } else { | |
| 168 return internalRemove(key); | |
| 169 } | |
| 170 } | |
| 171 | |
| 172 V internalRemove(Object key) { | |
| 173 var rest = _rest; | |
| 174 if (rest == null) return null; | |
| 175 var bucket = _getBucket(rest, key); | |
| 176 int index = internalFindBucketIndex(bucket, key); | |
| 177 if (index < 0) return null; | |
| 178 // Use splice to remove the [cell] element at the index and | |
| 179 // unlink the cell before returning its value. | |
| 180 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | |
| 181 _unlinkCell(cell); | |
| 182 // TODO(kasperl): Consider getting rid of the bucket list when | |
| 183 // the length reaches zero. | |
| 184 return cell.hashMapCellValue; | |
| 185 } | |
| 186 | |
| 187 void clear() { | |
| 188 if (_length > 0) { | |
| 189 _strings = _nums = _rest = _first = _last = null; | |
| 190 _length = 0; | |
| 191 _modified(); | |
| 192 } | |
| 193 } | |
| 194 | |
| 195 void forEach(void action(K key, V value)) { | |
| 196 LinkedHashMapCell cell = _first; | |
| 197 int modifications = _modifications; | |
| 198 while (cell != null) { | |
| 199 action(cell.hashMapCellKey, cell.hashMapCellValue); | |
| 200 if (modifications != _modifications) { | |
| 201 throw new ConcurrentModificationError(this); | |
| 202 } | |
| 203 cell = cell._next; | |
| 204 } | |
| 205 } | |
| 206 | |
| 207 void _addHashTableEntry(var table, K key, V value) { | |
| 208 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 209 if (cell == null) { | |
| 210 _setTableEntry(table, key, _newLinkedCell(key, value)); | |
| 211 } else { | |
| 212 cell.hashMapCellValue = value; | |
| 213 } | |
| 214 } | |
| 215 | |
| 216 V _removeHashTableEntry(var table, Object key) { | |
| 217 if (table == null) return null; | |
| 218 LinkedHashMapCell cell = _getTableEntry(table, key); | |
| 219 if (cell == null) return null; | |
| 220 _unlinkCell(cell); | |
| 221 _deleteTableEntry(table, key); | |
| 222 return cell.hashMapCellValue; | |
| 223 } | |
| 224 | |
| 225 void _modified() { | |
| 226 // Value cycles after 2^30 modifications so that modification counts are | |
| 227 // always unboxed (Smi) values. Modification detection will be missed if you | |
| 228 // make exactly some multiple of 2^30 modifications between advances of an | |
| 229 // iterator. | |
| 230 _modifications = (_modifications + 1) & 0x3ffffff; | |
| 231 } | |
| 232 | |
| 233 // Create a new cell and link it in as the last one in the list. | |
| 234 LinkedHashMapCell _newLinkedCell(K key, V value) { | |
| 235 LinkedHashMapCell cell = new LinkedHashMapCell(key, value); | |
| 236 if (_first == null) { | |
| 237 _first = _last = cell; | |
| 238 } else { | |
| 239 LinkedHashMapCell last = _last; | |
| 240 cell._previous = last; | |
| 241 _last = last._next = cell; | |
| 242 } | |
| 243 _length++; | |
| 244 _modified(); | |
| 245 return cell; | |
| 246 } | |
| 247 | |
| 248 // Unlink the given cell from the linked list of cells. | |
| 249 void _unlinkCell(LinkedHashMapCell cell) { | |
| 250 LinkedHashMapCell previous = cell._previous; | |
| 251 LinkedHashMapCell next = cell._next; | |
| 252 if (previous == null) { | |
| 253 assert(cell == _first); | |
| 254 _first = next; | |
| 255 } else { | |
| 256 previous._next = next; | |
| 257 } | |
| 258 if (next == null) { | |
| 259 assert(cell == _last); | |
| 260 _last = previous; | |
| 261 } else { | |
| 262 next._previous = previous; | |
| 263 } | |
| 264 _length--; | |
| 265 _modified(); | |
| 266 } | |
| 267 | |
| 268 static bool _isStringKey(var key) { | |
| 269 return key is String; | |
| 270 } | |
| 271 | |
| 272 static bool _isNumericKey(var key) { | |
| 273 // 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 | |
| 275 // the JavaScript hash table object. | |
| 276 return key is num && JS('bool', '(# & 0x3ffffff) === #', key, key); | |
| 277 } | |
| 278 | |
| 279 int internalComputeHashCode(var key) { | |
| 280 // We force the hash codes to be unsigned 30-bit integers to avoid | |
| 281 // issues with problematic keys like '__proto__'. Another option | |
| 282 // would be to throw an exception if the hash code isn't a number. | |
| 283 return JS('int', '# & 0x3ffffff', key.hashCode); | |
| 284 } | |
| 285 | |
| 286 List _getBucket(var table, var key) { | |
| 287 var hash = internalComputeHashCode(key); | |
| 288 return _getTableEntry(table, hash); | |
| 289 } | |
| 290 | |
| 291 int internalFindBucketIndex(var bucket, var key) { | |
| 292 if (bucket == null) return -1; | |
| 293 int length = JS('int', '#.length', bucket); | |
| 294 for (int i = 0; i < length; i++) { | |
| 295 LinkedHashMapCell cell = JS('var', '#[#]', bucket, i); | |
| 296 if (cell.hashMapCellKey == key) return i; | |
| 297 } | |
| 298 return -1; | |
| 299 } | |
| 300 | |
| 301 String toString() => Maps.mapToString(this); | |
| 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 | |
| 323 // Object.create to avoid the properties on Object.prototype | |
| 324 // showing up as entries. | |
| 325 var table = JS('var', 'Object.create(null)'); | |
| 326 // Attempt to force the hash table into 'dictionary' mode by | |
| 327 // adding a property to it and deleting it again. | |
| 328 var temporaryKey = '<non-identifier-key>'; | |
| 329 _setTableEntry(table, temporaryKey, table); | |
| 330 _deleteTableEntry(table, temporaryKey); | |
| 331 return table; | |
| 332 } | |
| 333 } | |
| 334 | |
| 335 class Es6LinkedHashMap<K, V> extends JsLinkedHashMap<K, V> { | |
| 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 } | |
| 362 | |
| 363 class LinkedHashMapCell { | |
| 364 final hashMapCellKey; | |
| 365 var hashMapCellValue; | |
| 366 | |
| 367 LinkedHashMapCell _next; | |
| 368 LinkedHashMapCell _previous; | |
| 369 | |
| 370 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue); | |
| 371 } | |
| 372 | |
| 373 class LinkedHashMapKeyIterable<E> extends Iterable<E> | |
| 374 implements EfficientLength { | |
| 375 final _map; | |
| 376 LinkedHashMapKeyIterable(this._map); | |
| 377 | |
| 378 int get length => _map._length; | |
| 379 bool get isEmpty => _map._length == 0; | |
| 380 | |
| 381 Iterator<E> get iterator { | |
| 382 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); | |
| 383 } | |
| 384 | |
| 385 bool contains(Object element) { | |
| 386 return _map.containsKey(element); | |
| 387 } | |
| 388 | |
| 389 void forEach(void f(E element)) { | |
| 390 LinkedHashMapCell cell = _map._first; | |
| 391 int modifications = _map._modifications; | |
| 392 while (cell != null) { | |
| 393 f(cell.hashMapCellKey); | |
| 394 if (modifications != _map._modifications) { | |
| 395 throw new ConcurrentModificationError(_map); | |
| 396 } | |
| 397 cell = cell._next; | |
| 398 } | |
| 399 } | |
| 400 } | |
| 401 | |
| 402 class LinkedHashMapKeyIterator<E> implements Iterator<E> { | |
| 403 final _map; | |
| 404 final int _modifications; | |
| 405 LinkedHashMapCell _cell; | |
| 406 E _current; | |
| 407 | |
| 408 LinkedHashMapKeyIterator(this._map, this._modifications) { | |
| 409 _cell = _map._first; | |
| 410 } | |
| 411 | |
| 412 E get current => _current; | |
| 413 | |
| 414 bool moveNext() { | |
| 415 if (_modifications != _map._modifications) { | |
| 416 throw new ConcurrentModificationError(_map); | |
| 417 } else if (_cell == null) { | |
| 418 _current = null; | |
| 419 return false; | |
| 420 } else { | |
| 421 _current = _cell.hashMapCellKey; | |
| 422 _cell = _cell._next; | |
| 423 return true; | |
| 424 } | |
| 425 } | |
| 426 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1212513002:
sdk files reorganization to make dart2js a proper package (Closed)
Base URL: git@github.com:dart-lang/sdk.git@master