| 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 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { | 10 class JsLinkedHashMap<K, V> implements LinkedHashMap<K, V>, InternalMap { |
| (...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 78 other.forEach((K key, V value) { | 78 other.forEach((K key, V value) { |
| 79 this[key] = value; | 79 this[key] = value; |
| 80 }); | 80 }); |
| 81 } | 81 } |
| 82 | 82 |
| 83 V operator[](Object key) { | 83 V operator[](Object key) { |
| 84 if (_isStringKey(key)) { | 84 if (_isStringKey(key)) { |
| 85 var strings = _strings; | 85 var strings = _strings; |
| 86 if (strings == null) return null; | 86 if (strings == null) return null; |
| 87 LinkedHashMapCell cell = _getTableEntry(strings, key); | 87 LinkedHashMapCell cell = _getTableEntry(strings, key); |
| 88 return (cell == null) ? null : cell.value; | 88 return (cell == null) ? null : cell.hashMapCellValue; |
| 89 } else if (_isNumericKey(key)) { | 89 } else if (_isNumericKey(key)) { |
| 90 var nums = _nums; | 90 var nums = _nums; |
| 91 if (nums == null) return null; | 91 if (nums == null) return null; |
| 92 LinkedHashMapCell cell = _getTableEntry(nums, key); | 92 LinkedHashMapCell cell = _getTableEntry(nums, key); |
| 93 return (cell == null) ? null : cell.value; | 93 return (cell == null) ? null : cell.hashMapCellValue; |
| 94 } else { | 94 } else { |
| 95 return internalGet(key); | 95 return internalGet(key); |
| 96 } | 96 } |
| 97 } | 97 } |
| 98 | 98 |
| 99 V internalGet(Object key) { | 99 V internalGet(Object key) { |
| 100 var rest = _rest; | 100 var rest = _rest; |
| 101 if (rest == null) return null; | 101 if (rest == null) return null; |
| 102 var bucket = _getBucket(rest, key); | 102 var bucket = _getBucket(rest, key); |
| 103 int index = internalFindBucketIndex(bucket, key); | 103 int index = internalFindBucketIndex(bucket, key); |
| 104 if (index < 0) return null; | 104 if (index < 0) return null; |
| 105 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | 105 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); |
| 106 return cell.value; | 106 return cell.hashMapCellValue; |
| 107 } | 107 } |
| 108 | 108 |
| 109 void operator[]=(K key, V value) { | 109 void operator[]=(K key, V value) { |
| 110 if (_isStringKey(key)) { | 110 if (_isStringKey(key)) { |
| 111 var strings = _strings; | 111 var strings = _strings; |
| 112 if (strings == null) _strings = strings = _newHashTable(); | 112 if (strings == null) _strings = strings = _newHashTable(); |
| 113 _addHashTableEntry(strings, key, value); | 113 _addHashTableEntry(strings, key, value); |
| 114 } else if (_isNumericKey(key)) { | 114 } else if (_isNumericKey(key)) { |
| 115 var nums = _nums; | 115 var nums = _nums; |
| 116 if (nums == null) _nums = nums = _newHashTable(); | 116 if (nums == null) _nums = nums = _newHashTable(); |
| 117 _addHashTableEntry(nums, key, value); | 117 _addHashTableEntry(nums, key, value); |
| 118 } else { | 118 } else { |
| 119 internalSet(key, value); | 119 internalSet(key, value); |
| 120 } | 120 } |
| 121 } | 121 } |
| 122 | 122 |
| 123 void internalSet(K key, V value) { | 123 void internalSet(K key, V value) { |
| 124 var rest = _rest; | 124 var rest = _rest; |
| 125 if (rest == null) _rest = rest = _newHashTable(); | 125 if (rest == null) _rest = rest = _newHashTable(); |
| 126 var hash = internalComputeHashCode(key); | 126 var hash = internalComputeHashCode(key); |
| 127 var bucket = JS('var', '#[#]', rest, hash); | 127 var bucket = JS('var', '#[#]', rest, hash); |
| 128 if (bucket == null) { | 128 if (bucket == null) { |
| 129 LinkedHashMapCell cell = _newLinkedCell(key, value); | 129 LinkedHashMapCell cell = _newLinkedCell(key, value); |
| 130 _setTableEntry(rest, hash, JS('var', '[#]', cell)); | 130 _setTableEntry(rest, hash, JS('var', '[#]', cell)); |
| 131 } else { | 131 } else { |
| 132 int index = internalFindBucketIndex(bucket, key); | 132 int index = internalFindBucketIndex(bucket, key); |
| 133 if (index >= 0) { | 133 if (index >= 0) { |
| 134 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); | 134 LinkedHashMapCell cell = JS('var', '#[#]', bucket, index); |
| 135 cell.value = value; | 135 cell.hashMapCellValue = value; |
| 136 } else { | 136 } else { |
| 137 LinkedHashMapCell cell = _newLinkedCell(key, value); | 137 LinkedHashMapCell cell = _newLinkedCell(key, value); |
| 138 JS('void', '#.push(#)', bucket, cell); | 138 JS('void', '#.push(#)', bucket, cell); |
| 139 } | 139 } |
| 140 } | 140 } |
| 141 } | 141 } |
| 142 | 142 |
| 143 V putIfAbsent(K key, V ifAbsent()) { | 143 V putIfAbsent(K key, V ifAbsent()) { |
| 144 if (containsKey(key)) return this[key]; | 144 if (containsKey(key)) return this[key]; |
| 145 V value = ifAbsent(); | 145 V value = ifAbsent(); |
| (...skipping 16 matching lines...) Expand all Loading... |
| 162 if (rest == null) return null; | 162 if (rest == null) return null; |
| 163 var bucket = _getBucket(rest, key); | 163 var bucket = _getBucket(rest, key); |
| 164 int index = internalFindBucketIndex(bucket, key); | 164 int index = internalFindBucketIndex(bucket, key); |
| 165 if (index < 0) return null; | 165 if (index < 0) return null; |
| 166 // Use splice to remove the [cell] element at the index and | 166 // Use splice to remove the [cell] element at the index and |
| 167 // unlink the cell before returning its value. | 167 // unlink the cell before returning its value. |
| 168 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); | 168 LinkedHashMapCell cell = JS('var', '#.splice(#, 1)[0]', bucket, index); |
| 169 _unlinkCell(cell); | 169 _unlinkCell(cell); |
| 170 // TODO(kasperl): Consider getting rid of the bucket list when | 170 // TODO(kasperl): Consider getting rid of the bucket list when |
| 171 // the length reaches zero. | 171 // the length reaches zero. |
| 172 return cell.value; | 172 return cell.hashMapCellValue; |
| 173 } | 173 } |
| 174 | 174 |
| 175 void clear() { | 175 void clear() { |
| 176 if (_length > 0) { | 176 if (_length > 0) { |
| 177 _strings = _nums = _rest = _first = _last = null; | 177 _strings = _nums = _rest = _first = _last = null; |
| 178 _length = 0; | 178 _length = 0; |
| 179 _modified(); | 179 _modified(); |
| 180 } | 180 } |
| 181 } | 181 } |
| 182 | 182 |
| 183 void forEach(void action(K key, V value)) { | 183 void forEach(void action(K key, V value)) { |
| 184 LinkedHashMapCell cell = _first; | 184 LinkedHashMapCell cell = _first; |
| 185 int modifications = _modifications; | 185 int modifications = _modifications; |
| 186 while (cell != null) { | 186 while (cell != null) { |
| 187 action(cell.key, cell.value); | 187 action(cell.hashMapCellKey, cell.hashMapCellValue); |
| 188 if (modifications != _modifications) { | 188 if (modifications != _modifications) { |
| 189 throw new ConcurrentModificationError(this); | 189 throw new ConcurrentModificationError(this); |
| 190 } | 190 } |
| 191 cell = cell._next; | 191 cell = cell._next; |
| 192 } | 192 } |
| 193 } | 193 } |
| 194 | 194 |
| 195 void _addHashTableEntry(var table, K key, V value) { | 195 void _addHashTableEntry(var table, K key, V value) { |
| 196 LinkedHashMapCell cell = _getTableEntry(table, key); | 196 LinkedHashMapCell cell = _getTableEntry(table, key); |
| 197 if (cell == null) { | 197 if (cell == null) { |
| 198 _setTableEntry(table, key, _newLinkedCell(key, value)); | 198 _setTableEntry(table, key, _newLinkedCell(key, value)); |
| 199 } else { | 199 } else { |
| 200 cell.value = value; | 200 cell.hashMapCellValue = value; |
| 201 } | 201 } |
| 202 } | 202 } |
| 203 | 203 |
| 204 V _removeHashTableEntry(var table, Object key) { | 204 V _removeHashTableEntry(var table, Object key) { |
| 205 if (table == null) return null; | 205 if (table == null) return null; |
| 206 LinkedHashMapCell cell = _getTableEntry(table, key); | 206 LinkedHashMapCell cell = _getTableEntry(table, key); |
| 207 if (cell == null) return null; | 207 if (cell == null) return null; |
| 208 _unlinkCell(cell); | 208 _unlinkCell(cell); |
| 209 _deleteTableEntry(table, key); | 209 _deleteTableEntry(table, key); |
| 210 return cell.value; | 210 return cell.hashMapCellValue; |
| 211 } | 211 } |
| 212 | 212 |
| 213 void _modified() { | 213 void _modified() { |
| 214 // Value cycles after 2^30 modifications. If you keep hold of an | 214 // Value cycles after 2^30 modifications. If you keep hold of an |
| 215 // iterator for that long, you might miss a modification | 215 // iterator for that long, you might miss a modification |
| 216 // detection, and iteration can go sour. Don't do that. | 216 // detection, and iteration can go sour. Don't do that. |
| 217 _modifications = (_modifications + 1) & 0x3ffffff; | 217 _modifications = (_modifications + 1) & 0x3ffffff; |
| 218 } | 218 } |
| 219 | 219 |
| 220 // Create a new cell and link it in as the last one in the list. | 220 // Create a new cell and link it in as the last one in the list. |
| (...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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 JS('var', '#[#]', 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.key == key) return i; | 296 if (cell.hashMapCellKey == key) return i; |
| 297 } | 297 } |
| 298 return -1; | 298 return -1; |
| 299 } | 299 } |
| 300 | 300 |
| 301 static _newHashTable() { | 301 static _newHashTable() { |
| 302 // 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 |
| 303 // Object.create to avoid the properties on Object.prototype | 303 // Object.create to avoid the properties on Object.prototype |
| 304 // showing up as entries. | 304 // showing up as entries. |
| 305 var table = JS('var', 'Object.create(null)'); | 305 var table = JS('var', 'Object.create(null)'); |
| 306 // Attempt to force the hash table into 'dictionary' mode by | 306 // Attempt to force the hash table into 'dictionary' mode by |
| 307 // adding a property to it and deleting it again. | 307 // adding a property to it and deleting it again. |
| 308 var temporaryKey = '<non-identifier-key>'; | 308 var temporaryKey = '<non-identifier-key>'; |
| 309 _setTableEntry(table, temporaryKey, table); | 309 _setTableEntry(table, temporaryKey, table); |
| 310 _deleteTableEntry(table, temporaryKey); | 310 _deleteTableEntry(table, temporaryKey); |
| 311 return table; | 311 return table; |
| 312 } | 312 } |
| 313 | 313 |
| 314 String toString() => Maps.mapToString(this); | 314 String toString() => Maps.mapToString(this); |
| 315 } | 315 } |
| 316 | 316 |
| 317 class LinkedHashMapCell { | 317 class LinkedHashMapCell { |
| 318 final key; | 318 final hashMapCellKey; |
| 319 var value; | 319 var hashMapCellValue; |
| 320 | 320 |
| 321 LinkedHashMapCell _next; | 321 LinkedHashMapCell _next; |
| 322 LinkedHashMapCell _previous; | 322 LinkedHashMapCell _previous; |
| 323 | 323 |
| 324 LinkedHashMapCell(this.key, this.value); | 324 LinkedHashMapCell(this.hashMapCellKey, this.hashMapCellValue); |
| 325 } | 325 } |
| 326 | 326 |
| 327 class LinkedHashMapKeyIterable<E> extends IterableBase<E> | 327 class LinkedHashMapKeyIterable<E> extends IterableBase<E> |
| 328 implements EfficientLength { | 328 implements EfficientLength { |
| 329 final _map; | 329 final _map; |
| 330 LinkedHashMapKeyIterable(this._map); | 330 LinkedHashMapKeyIterable(this._map); |
| 331 | 331 |
| 332 int get length => _map._length; | 332 int get length => _map._length; |
| 333 bool get isEmpty => _map._length == 0; | 333 bool get isEmpty => _map._length == 0; |
| 334 | 334 |
| 335 Iterator<E> get iterator { | 335 Iterator<E> get iterator { |
| 336 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); | 336 return new LinkedHashMapKeyIterator<E>(_map, _map._modifications); |
| 337 } | 337 } |
| 338 | 338 |
| 339 bool contains(Object element) { | 339 bool contains(Object element) { |
| 340 return _map.containsKey(element); | 340 return _map.containsKey(element); |
| 341 } | 341 } |
| 342 | 342 |
| 343 void forEach(void f(E element)) { | 343 void forEach(void f(E element)) { |
| 344 LinkedHashMapCell cell = _map._first; | 344 LinkedHashMapCell cell = _map._first; |
| 345 int modifications = _map._modifications; | 345 int modifications = _map._modifications; |
| 346 while (cell != null) { | 346 while (cell != null) { |
| 347 f(cell.key); | 347 f(cell.hashMapCellKey); |
| 348 if (modifications != _map._modifications) { | 348 if (modifications != _map._modifications) { |
| 349 throw new ConcurrentModificationError(_map); | 349 throw new ConcurrentModificationError(_map); |
| 350 } | 350 } |
| 351 cell = cell._next; | 351 cell = cell._next; |
| 352 } | 352 } |
| 353 } | 353 } |
| 354 } | 354 } |
| 355 | 355 |
| 356 class LinkedHashMapKeyIterator<E> implements Iterator<E> { | 356 class LinkedHashMapKeyIterator<E> implements Iterator<E> { |
| 357 final _map; | 357 final _map; |
| 358 final int _modifications; | 358 final int _modifications; |
| 359 LinkedHashMapCell _cell; | 359 LinkedHashMapCell _cell; |
| 360 E _current; | 360 E _current; |
| 361 | 361 |
| 362 LinkedHashMapKeyIterator(this._map, this._modifications) { | 362 LinkedHashMapKeyIterator(this._map, this._modifications) { |
| 363 _cell = _map._first; | 363 _cell = _map._first; |
| 364 } | 364 } |
| 365 | 365 |
| 366 E get current => _current; | 366 E get current => _current; |
| 367 | 367 |
| 368 bool moveNext() { | 368 bool moveNext() { |
| 369 if (_modifications != _map._modifications) { | 369 if (_modifications != _map._modifications) { |
| 370 throw new ConcurrentModificationError(_map); | 370 throw new ConcurrentModificationError(_map); |
| 371 } else if (_cell == null) { | 371 } else if (_cell == null) { |
| 372 _current = null; | 372 _current = null; |
| 373 return false; | 373 return false; |
| 374 } else { | 374 } else { |
| 375 _current = _cell.key; | 375 _current = _cell.hashMapCellKey; |
| 376 _cell = _cell._next; | 376 _cell = _cell._next; |
| 377 return true; | 377 return true; |
| 378 } | 378 } |
| 379 } | 379 } |
| 380 } | 380 } |
| OLD | NEW |